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. */
  1

• 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;
1
2
3
4
5
6
7
8

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
1
2
3
4
5
6
7
8
9
10
11
12

在初始化链表时，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;
1
2
3
4
5
6
7
8
9
10
11
12