[原创] RT-Thread系统常用数据结构

常用数据结构

单向链表、双向链表、侵入式链表

三种链表在RT-Thread系统内的参考结构类型，如下：

// rtdef.h

/**
 * Single List structure
 */
struct rt_slist_node
{
    struct rt_slist_node *next;                         /**< point to next node. */
};
typedef struct rt_slist_node rt_slist_t;                /**< Type for single list. */

/**
 * Double List structure
 */
struct rt_list_node
{
    struct rt_list_node *next;                          /**< point to next node. */
    struct rt_list_node *prev;                          /**< point to prev node. */
};
typedef struct rt_list_node rt_list_t;                  /**< Type for lists. */

/**
 * Base structure of Kernel object
 */
struct rt_object
{
    char       name[RT_NAME_MAX];                       /**< name of kernel object */
    rt_uint8_t type;                                    /**< type of kernel object */
    rt_uint8_t flag;                                    /**< flag of kernel object */

#ifdef RT_USING_MODULE
    void      *module_id;                               /**< id of application module */
#endif
    rt_list_t  list;                                    /**< list node of kernel object */
};
typedef struct rt_object *rt_object_t;                  /**< Type for kernel objects. */

双向链表和侵入式链表都是基于单项链表进行的扩展；

单项链表和双向链表的指针一般都是指向链表的首地址，而侵入式链表的指针指向的是链表的成员指针，

单链表管理函数

函数位置rtservice.h

单项链表

双向链表

侵入式链表的具体实现

/**
 * This function will initialize an object and add it to object system
 * management.
 *
 * @param object the specified object to be initialized.
 * @param type the object type.
 * @param name the object name. In system, the object's name must be unique.
 */
void rt_object_init(struct rt_object         *object,
                    enum rt_object_class_type type,
                    const char               *name)
{
    register rt_base_t temp;
    struct rt_object_information *information;
#ifdef RT_USING_MODULE
    struct rt_dlmodule *module = dlmodule_self();
#endif

    /* get object information */
    information = rt_object_get_information(type);
    RT_ASSERT(information != RT_NULL);

    /* initialize object's parameters */

    /* set object type to static */
    object->type = type | RT_Object_Class_Static;

    /* copy name */
    rt_strncpy(object->name, name, RT_NAME_MAX);

    RT_OBJECT_HOOK_CALL(rt_object_attach_hook, (object));

    /* lock interrupt */
    temp = rt_hw_interrupt_disable();

#ifdef RT_USING_MODULE
    if (module)
    {
        rt_list_insert_after(&(module->object_list), &(object->list));
        object->module_id = (void *)module;
    }
    else
#endif
    {
        /* insert object into information object list */
        rt_list_insert_after(&(information->object_list), &(object->list));
    }

    /* unlock interrupt */
    rt_hw_interrupt_enable(temp);
}

/**
 * This function will detach a static object from object system,
 * and the memory of static object is not freed.
 *
 * @param object the specified object to be detached.
 */
void rt_object_detach(rt_object_t object)
{
    register rt_base_t temp;

    /* object check */
    RT_ASSERT(object != RT_NULL);

    RT_OBJECT_HOOK_CALL(rt_object_detach_hook, (object));

    /* reset object type */
    object->type = 0;

    /* lock interrupt */
    temp = rt_hw_interrupt_disable();

    /* remove from old list */
    rt_list_remove(&(object->list));

    /* unlock interrupt */
    rt_hw_interrupt_enable(temp);
}

从上述代码可以看到侵入式的链表都是指向object->list成员，而不是指向object的首地址

队列

一般是先进先出的模式，分顺序队列，循环队列

顺序队列一般结构

/*
 * Serial FIFO mode 
 */
struct rt_serial_rx_fifo
{
    /* software fifo */
    rt_uint8_t *buffer;

    rt_uint16_t put_index, get_index;

    rt_bool_t s_full;
};

循环队列一般结构

/* ring buffer */
struct rt_ringbuffer
{
    rt_uint8_t *buffer_ptr;
    /* use the msb of the {read,write}_index as mirror bit. You can see this as
     * if the buffer adds a virtual mirror and the pointers point either to the
     * normal or to the mirrored buffer. If the write_index has the same value
     * with the read_index, but in a different mirror, the buffer is full.
     * While if the write_index and the read_index are the same and within the
     * same mirror, the buffer is empty. The ASCII art of the ringbuffer is:
     *
     *          mirror = 0                    mirror = 1
     * +---+---+---+---+---+---+---+|+~~~+~~~+~~~+~~~+~~~+~~~+~~~+
     * | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||| 0 | 1 | 2 | 3 | 4 | 5 | 6 | Full
     * +---+---+---+---+---+---+---+|+~~~+~~~+~~~+~~~+~~~+~~~+~~~+
     *  read_idx-^                   write_idx-^
     *
     * +---+---+---+---+---+---+---+|+~~~+~~~+~~~+~~~+~~~+~~~+~~~+
     * | 0 | 1 | 2 | 3 | 4 | 5 | 6 ||| 0 | 1 | 2 | 3 | 4 | 5 | 6 | Empty
     * +---+---+---+---+---+---+---+|+~~~+~~~+~~~+~~~+~~~+~~~+~~~+
     * read_idx-^ ^-write_idx
     *
     * The tradeoff is we could only use 32KiB of buffer for 16 bit of index.
     * But it should be enough for most of the cases.
     *
     * Ref: http://en.wikipedia.org/wiki/Circular_buffer#Mirroring */
    rt_uint16_t read_mirror : 1;
    rt_uint16_t read_index : 15;
    rt_uint16_t write_mirror : 1;
    rt_uint16_t write_index : 15;
    /* as we use msb of index as mirror bit, the size should be signed and
     * could only be positive. */
    rt_int16_t buffer_size;
};

队列的差异性

相同点：在顺序队列和循环队列中,进行出队、入队操作时,队首、队尾指针都要加 1 ,朝前移动。

不同点:

1. 在循环队列中当队首、队尾指针指向向量上界(MAX_QUEUE_SIZE-1) 时,其加1 操作的结果是指向向量的下界 0 。而在顺序队列中,说明队已满,若此时采用的是动态顺序链,可以增加申请内存.若是采用静态顺序链,只能退出程序.

2. 顺序队列中head和tail相等 表示队空,tail= MAX_QUEUE_SIZE表示队满.而在循环队列中head= tail表示队空,而无法用tail=MAX_QUEUE_SIZE表示队满.

判断循环队列队满的两种方法:

1.另设一个标志位以区分队列是空还是满

2.少用一个元素空间,约定以”队列头指针在队列尾指针的下一位置上”,作为队列呈满状态的标志.

堆，栈

栈：栈用于维护函数调用的上下文，离开栈函数调用就会无法实现。栈通常在用户空间的最高地址处分配，先进后出。

堆：堆用来容纳应用程序动态分配的内存区域，我们使用malloc 或者new分配内存时，得到的内存来自堆里。堆通常存于栈的下方（低地址方向），一般用于内存的动态分配。

内存管理

RT-Thread系统对于内存和堆专门做了一个内存管理，方便用户进行内存的分配和管理

总体上可分为两类：内存堆管理与内存池管理，而内存堆管理又根据具体内存设备划分为三种情况：

第一种是针对小内存块的分配管理（小内存管理算法，一般小于2MB）；

第二种是针对大内存块的分配管理（slab 管理算法）；

第三种是针对多内存堆的分配情况（memheap 管理算法）

涉及到的函数实现

rt_err_t rt_memheap_init(struct rt_memheap *memheap,
                         const char        *name,
                         void              *start_addr,
                         rt_size_t         size);
rt_err_t rt_memheap_detach(struct rt_memheap *heap);

内存池，采用链表串联的结构，提高效率和减少碎片。

涉及到的函数实现

总结

RT-Thread内核运用了大量的链表结构，动态删减相应的模块，减少了内核代码量，方便裁剪系统。

此内容由EEWORLD论坛网友ID.LODA原创，如需转载或用于商业用途需征得作者同意并注明出处