freertos中的链表1 - 链表的数据结构

1.概述

freertos中链表的实现在 list.c 和 list.h。
旨在通过学习freertos中的链表的数据结构，对freertos中的链表实现有一个整体的认识。
freertos使用了三个数据结构来描述链表，分别是：List_t， MiniListItem_t，ListItem_t
MiniListItem_t 是 List_t 的一部分，List_t 用来定义一个链表，如 就绪链表(pxReadyTasksLists)， 就绪链表(pxReadyTasksLists) 作用是将已经定义好的任务以链表的形式串起来，供调度器调度。
```
RIVILEGED_DATA static List_t pxReadyTasksLists[ configMAX_PRIORITIES ]; /**< Prioritised ready tasks. */
```
MiniListItem_t 叫做链表项，它通常被其他数据结构包含，比如用来描述一个任务的 TCB 结构体，这样TCB结构体就可以借助 ListItem_t(链表项) 插入到合适的链表中了。
List_t， MiniListItem_t，ListItem_t 最终结构如下图所示：

2. List_t 结构

typedef struct xLIST
{
    listFIRST_LIST_INTEGRITY_CHECK_VALUE      /**< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
    configLIST_VOLATILE UBaseType_t uxNumberOfItems;
    ListItem_t * configLIST_VOLATILE pxIndex; /**< Used to walk through the list.  Points to the last item returned by a call to listGET_OWNER_OF_NEXT_ENTRY (). */
    MiniListItem_t xListEnd;                  /**< List item that contains the maximum possible item value meaning it is always at the end of the list and is therefore used as a marker. */
    listSECOND_LIST_INTEGRITY_CHECK_VALUE     /**< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
} List_t;

元素	用途
listFIRST_LIST_INTEGRITY_CHECK_VALUE listSECOND_LIST_INTEGRITY_CHECK_VALUE	freertos 中用于数据完整性检查的宏定义。它的主要作用是确保链表项（ListItem_t）和链表（List_t）的数据结构在内存中没有被意外覆盖或损坏。原理是在数据结构的第一项和最后一项定义一组特别的数如0x5a5a5a，在运行过程中只要这一组数没被破坏，即可认为链表项（ListItem_t）和链表（List_t) 内容是没有被破坏的
uxNumberOfItems	当前链表中链表项的个数
pxIndex	一个用于指向链表项的指针，用于遍历链表
xListEnd	一个 MiniListItem_t

3. MiniListItem_t结构

#if ( configUSE_MINI_LIST_ITEM == 1 )
    struct xMINI_LIST_ITEM
    {
        listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /**< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
        configLIST_VOLATILE TickType_t xItemValue;
        struct xLIST_ITEM * configLIST_VOLATILE pxNext;
        struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
    };
    typedef struct xMINI_LIST_ITEM MiniListItem_t;
#else
    typedef struct xLIST_ITEM      MiniListItem_t;
#endif

元素	用途
xItemValue	在 freertos 中，链表项通常根据 xItemValue 进行排序。xItemValue 可以表示任务的优先级、延迟时间或其他用于排序的值。 MiniListItem_t 中的 xItemValue 通常被设置为最大值（例如 portMAX_DELAY），以确保它始终位于链表的末尾。
pxNext	指向链表中的下一个链表项
pxPrevious	指向链表中的上一个链表项

在初始化链表时，xListEnd（类型为 MiniListItem_t）的 xItemValue 被设置为 portMAX_DELAY，并且 pxNext 和 pxPrevious 都指向自身，形成一个环形链表。

3.ListItem_t结构

struct xLIST;
struct xLIST_ITEM
{
    listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE           /**< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
    configLIST_VOLATILE TickType_t xItemValue;          /**< The value being listed.  In most cases this is used to sort the list in ascending order. */
    struct xLIST_ITEM * configLIST_VOLATILE pxNext;     /**< Pointer to the next ListItem_t in the list. */
    struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /**< Pointer to the previous ListItem_t in the list. */
    void * pvOwner;                                     /**< Pointer to the object (normally a TCB) that contains the list item.  There is therefore a two way link between the object containing the list item and the list item itself. */
    struct xLIST * configLIST_VOLATILE pxContainer;     /**< Pointer to the list in which this list item is placed (if any). */
    listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE          /**< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
};
typedef struct xLIST_ITEM ListItem_t;

元素	用途
xItemValue	在 freertos 中，链表项通常根据 xItemValue 进行排序。xItemValue 可以表示任务的优先级、延迟时间或其他用于排序的值。
pxNext	指向链表中的下一个链表项
pxPrevious	指向链表中的上一个链表项
pvOwner	它的主要作用是指向拥有该链表项的对象，通常是任务控制块（TCB）
pxContainer	指向包含该链表项的链表