列表和列表项是直接从 FreeRTOS 源码的注释中的 list 和 list item 翻译过来的，其实就是对应我们 C 语言当中的链表和节点，在后续的讲解中，我们说的链表就是列表，节点就是列表项

3.1 C语言链表

3.1.1 单向链表

1. 链表定义

该链表中共有 n 个节点， 前一个节点都有一个箭头指向后一个节点，首尾相连，组成一个圈。
image.png
节点本身必须包含一个节点指针，用于指向后一个节点，除了这个节点指针是必须有的之外，节点本身还可以携带一些私有信息，怎么携带？
节点都是一个自定义类型的数据结构，在这个数据结构里面可以有单个的数据、数组、指针数据和自定义的结构体数据类型等等信息。

  1. struct node
  2. {
  3.     struct node *next;             /* 指向链表的下一个节点 */
  4.     char data1;                 /* 单个的数据 */
  5.     unsigned char array[];        /* 数组 */
  6.     unsigned long *prt             /* 指针数据 */
  7.     struct userstruct data2;     /* 自定义结构体类型数据 */
  8. }

除了 struct node *next 这个节点指针之外，剩下的成员都可以理解为节点携带的数据，但是这种方法很少用。 通常的做法是节点里面只包含一个用于指向下一个节点的指针。 

  1. /* 节点定义 */
  2. struct node
  3. {
  4.     struct node *next; /* 指向链表的下一个节点 */
  5. }
  7. struct userstruct
  8. {
  9.     /* 在结构体中，内嵌一个节点指针，通过这个节点将数据挂接到链表 */
  10.     struct node *next;
  11.     /* 各种各样......，要存储的数据 */
  12.  }

image.png
2. 链表的操作

链表常规的操作就是节点的插入和删除，为了顺利的插入，通常一条链表我们会人为地规定一个根节点， 这个根节点称为生产者。 通常根节点还会有一个节点计数器，用于统计整条链表的节点个数，
image.png
FreeRTO 中链表的实现：详细解释

3.1.2 双向链表

双向链表与单向链表的区别就是节点中有两个节点指针，分别指向前后两个节点，其它完全一样。有关双向链表的文字描述参考单向链表小节即可
image.png

3.1.3 链表和数组的对比

在很多公司的嵌入式面试中，通常会问到链表和数组的区别。 在 C 语言中，链表与数、组确实很像。
image.png
区别：

  1. 链表的空间不连续、数组是连续的
  2. 数组有起始和结束地址、链表没有
  3. 链表可以自由的增加和删除、数组不行，在初始化的时候就要定义大小

3.1 FreeRTOS链表实现

6.2.1 实现链表节点

1. 定义链表节点数据结构

FreeRTOS 中与链表相关的操作均在 list.h 和 list.c 这两个文件中实现， list.h 第一次使用需要在 include 文件夹下面新建然后添加到工程 freertos/source 这个组文件， list.c 第一次使用需要在 freertos 文件夹下面新建然后添加到工程 freertos/source 这个组文件。
TCB：TASK CONTROL BLOCK 任务控制块

  1. struct xLIST_ITEM
  2. {        
  3.     configLIST_VOLATILE TickType_t xItemValue;            /* 辅助值，用于帮助节点做顺序排列 */ 
  4.     struct xLIST_ITEM * configLIST_VOLATILE pxNext;        /*< Pointer to the next ListItem_t in the list. */
  5.     struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;    /*< Pointer to the previous ListItem_t in the list. */
  6.     void * pvOwner;                                        /* 指向拥有该节点的内核对象，通常是 TCB */
  7.     void * configLIST_VOLATILE pvContainer;                /* 指向该节点所在的链表 */
  8. };
  9. typedef struct xLIST_ITEM ListItem_t;                     /* 节点数据类型重定义 */

image.png
一个辅助值，用于帮助节点做顺序排列。 该辅助值的数据类型为TickType_t， 在 FreeRTOS 中，凡是涉及到数据类型的地方， FreeRTOS 都会将标准的 C 数据类型用 typedef 重新取一个类型名。 

  1. #ifndef PORTMACRO_H
  2. #define PORTMACRO_H
  4. /* 数据类型重定义 */
  5. #define portCHAR        char
  6. #define portFLOAT        float
  7. #define portDOUBLE        double
  8. #define portLONG        long
  9. #define portSHORT        short
  10. #define portSTACK_TYPE    uint32_t
  11. #define portBASE_TYPE    long
  13. typedef portSTACK_TYPE StackType_t;
  14. typedef long BaseType_t;
  15. typedef unsigned long UBaseType_t;
  17. #if( configUSE_16_BIT_TICKS == 1 )
  18.     typedef uint16_t TickType_t;
  19.     #define portMAX_DELAY ( TickType_t ) 0xffff
  20. #else
  21.     typedef uint32_t TickType_t;
  22.     #define portMAX_DELAY ( TickType_t ) 0xffffffffUL
  23. #endif

configUSE_16_BIT_TICKS 宏 默认为0 因此portMAX_DELAY 表示 32位
配置在：FreeRTOSConfig.h 中


2. 链表初始

  1. void vListInitialiseItem( ListItem_t *const pxItem )
  2. {
  3.     /* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */
  4.     pxItem->pvContainer = NULL;
  5. }

链表节点 ListItem_t 总共有 5 个成员，但是初始化的时候只需将pvContainer 初始化为空即可， 表示该节点还没有插入到任何链表。

image.png

6.2.2 实现链表根节点

1. 定义根节点数据结构

链表根节点的数据结构在 list.h 中定义 

  1. // 链表尾-头  生产者  除了链表指针，不携带其它的信息
  2. struct xMINI_LIST_ITEM
  3. {
  4.     TickType_t xItemValue;            /* 辅助值，用于帮助节点做升序排列 */
  5.     struct xLIST_ITEM *pxNext;        /* 指向链表下一个节点 */
  6.     struct xLIST_ITEM *pxPrevious;    /* 指向链表前一个节点 */
  7. };
  1. typedef struct xLIST
  2. {
  3.     UBaseType_t uxNumberOfItems;        /* 链表节点计数器 */         (1)
  4.     ListItem_t *pxIndex;                /* 链表节点索引指针 */        (2)
  5.     MiniListItem_t xListEnd;            /* 链表最后一个节点 */        (3)
  6. }List_t;

image.png
详解：
(1) : 链表节点计数器， 用于表示该链表下有多少个节点， 根节点除外。
(2) : 链表节点索引指针， 用于遍历节点。
(3) : 链表最后一个节点。我们知道，链表是首尾相连的，是一个圈，首就是尾，尾就是首，这里从字面上理解就是链表的最后一个节点，实际也就是链表的第一个节点，我们称之为生产者。该生产者的数据类型是一个精简的节点， 也在 list.h 中定义，

具体实现见：
除了链表指针，不携带其它的信息

  1. struct xMINI_LIST_ITEM
  2. {
  3.     TickType_t xItemValue;            /* 辅助值，用于帮助节点做升序排列 */
  4.     struct xLIST_ITEM *preNext;        /* 指向链表下一个节点 */
  5.     struct xLIST_ITEM *pxPrevious;    /* 指向链表前一个节点 */
  6. };
  7. typedef struct xMINI_LIST_ITEM MiniListItem_t;    /* 精简节点数据类型重定义 */


2. 链表根节点初始化

链表节点初始化函数在 list.c 中实现 

  1. void vListInitialise( List_t *const pxList )
  2. {
  3.     /* 将链表索引指针指向最后一个节点 */
  4.     pxList->pxIndex = (ListItem_t *)&(pxList->xListEnd);
  6.     /* 将链表最后一个节点的辅助排序的值设置为最大，确保该节点就是链表的最后节点 */
  7.     pxList->xListEnd.xItemValue = portMAX_DELAY;
  8.     /* 将最后一个节点的 pxNext 和 pxPrevious 指针均指向节点自身，表示链表为空 */
  9.     pxList->xListEnd.preNext = (ListItem_t *)&(pxList->xListEnd);
  10.     pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );
  12.     /* 初始化链表节点计数器的值为 0，表示链表为空 */
  13.     pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
  14. }

image.png
没有特别需要解释的，看图比较清晰

3. 将节点插入到链表的尾部（尾插）

将节点插入到链表的尾部， 就是将一个新的节点插入到一个空的链表。这个应该就初始化用了一下

  1. void vListInsertEnd( List_t *const pxList, ListItem_t *const pxNewListItem)
  2. {
  3.     ListItem_t *const pxIndex = pxList->pxIndex;
  5.     pxNewListItem->pxNext = pxIndex;
  6.     pxNewListItem->pxPrevious = pxIndex->pxPrevious;
  7.     pxIndex->pxPrevious->pxNext = pxNewListItem;
  8.     pxIndex->pxPrevious = pxNewListItem;
  10.     /* 记住该节点所在的链表 */
  11.     pxNewListItem->pvContainer = ( void * ) pxList;
  13.     /* 链表节点计数器++ */
  14.     ( pxList->uxNumberOfItems )++;
  15. }

image.png
3. 数据结构—列表与列表项讲解 - 图12

4. 将节点按照升序排列插入到链表

将节点按照升序排列插入到链表，如果有两个节点的值相同，则新节点在旧节点的后面插入。

  1. void vListInsert( List_t *const pxList, ListItem_t *const pxNewListItem )
  2. {
  3.     ListItem_t *pxIterator;
  5.     /* 获取节点的排序辅助值 */
  6.     const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
  8.     if (xValueOfInsertion == portMAX_DELAY)
  9.     {
  10.         /* 指向的是最后一个 */
  11.         pxIterator = pxList->xListEnd.pxPrevious;
  12.     }
  13.     else
  14.     {
  15.         for (pxIterator = (ListItem_t *) &(pxList->xListEnd); 
  16.         pxIterator->pxNext->xItemValue <= xValueOfInsertion;    
  17.         pxIterator = pxIterator->pxNext)
  18.         {
  19.             /* 没有事情可做，不断迭代只为了找到节点要插入的位置 */
  20.         }
  21.     }
  22.     /* 根据升序排列，将节点插入 */
  23.     pxNewListItem->pxNext = pxIterator->pxNext;            //1
  24.     pxNewListItem->pxNext->pxPrevious = pxNewListItem;    //2
  26.     pxNewListItem->pxPrevious = pxIterator;                //3
  27.     pxIterator->pxNext = pxNewListItem;                    //4
  29.     /* 记住该节点所在的链表 */
  30.     pxNewListItem->pvContainer = ( void * ) pxList;           //5
  33.     /* 链表节点计数器++ */
  34.     ( pxList->uxNumberOfItems )++;
  35. }

image.png

5. 将节点从列表删除

假设将一个有三个节点的链表中的中间节点节点删除，删除操作的过程示意图具体可见图。

  1. UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
  2. {
  3.     /* 获取节点所在的链表 */
  4.     List_t *const pxList = (List_t *) pxItemToRemove->pvContainer;
  5.     /* 将指定的节点从链表删除*/
  6.     pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
  7.     pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
  9.     /*调整链表的节点索引指针 */
  10.     if (pxList->pxIndex == pxItemToRemove)
  11.     {
  12.         pxList->pxIndex = pxItemToRemove->pxPrevious;
  13.     }
  14.     /* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */
  15.     pxItemToRemove->pvContainer = NULL;
  17.     /* 链表节点计数器-- */
  18.     ( pxList->uxNumberOfItems )--;
  20.     /* 返回链表中剩余节点的个数 */
  21.     return pxList->uxNumberOfItems;
  22. }

image.png

6. 节点带参宏小函数

在 list.h 中，还定义了各种各样的带参宏，方便对节点做一些简单的操作，具体实现见

  1. /* 初始化节点的拥有者 */
  2. #define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner )        ( ( pxListItem )->pvOwner = ( void * ) ( pxOwner ) )
  3. /* 获取节点拥有者 */
  4. #define listGET_LIST_ITEM_OWNER( pxListItem )    ( ( pxListItem )->pvOwner )
  6. /* 初始化节点排序辅助值 */
  7. #define listSET_LIST_ITEM_VALUE( pxListItem, xValue )    ( ( pxListItem )->xItemValue = ( xValue ) )
  9. /* 获取节点排序辅助值 */
  10. #define listGET_LIST_ITEM_VALUE( pxListItem )    ( ( pxListItem )->xItemValue )
  12. /* 获取链表根节点的节点计数器的值 */
  13. #define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList )    ( ( ( pxList )->xListEnd ).pxNext->xItemValue )
  15. /* 获取链表的入口节点 */
  16. #define listGET_HEAD_ENTRY( pxList )    ( ( ( pxList )->xListEnd ).pxNext )
  18. /* 获取链表的下一个节点 */
  19. #define listGET_NEXT( pxListItem )    ( ( pxListItem )->pxNext )
  21. /* 获取链表的最后一个节点 */
  22. #define listGET_END_MARKER( pxList )    ( ( ListItem_t const * ) ( &( ( pxList )->xListEnd ) ) )
  24. /* 判断链表是否为空 */
  25. #define listLIST_IS_EMPTY( pxList )    ( ( BaseType_t ) ( ( pxList )->uxNumberOfItems == ( UBaseType_t ) 0 ) )
  27. /* 获取链表的节点数 */
  28. #define listCURRENT_LIST_LENGTH( pxList )    ( ( pxList )->uxNumberOfItems )
  30. /* 获取链表节点的OWNER，即TCB */
  31. #define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )                                        \
  32. {                                                                                            \
  33.     List_t * const pxConstList = ( pxList );                                                \
  34.     /* 节点索引指向链表第一个节点调整节点索引指针，指向下一个节点，
  35.     如果当前链表有N个节点，当第N次调用该函数时，pxInedex则指向第N个节点 */\
  36.     ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                            \
  37.     /* 当前链表为空  应该是获取第一个不为空的ITEM */                                                                       \
  38.     if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) )    \
  39.     {                                                                                        \
  40.         ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                        \
  41.     }                                                                                        \
  42.     /* 获取节点的OWNER，即TCB */                                                             \
  43.     ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;                                             \
  44. }

3.1.2 链表插入小实验

我们新建一个根节点（也可以理解为链表）和三个普通节点，然后将这三个普通节点按照节点的排序辅助值做升序排列插入到链表中。

  1. /* 定义链表根节点 */
  2. struct xLIST       List_Test;
  4. /* 定义节点 */
  5. struct xLIST_ITEM  List_Item1;
  6. struct xLIST_ITEM  List_Item2;
  7. struct xLIST_ITEM  List_Item3;
  9. int main(void)
  10. {    
  12.     /* 链表根节点初始化 */
  13.     vListInitialise( &List_Test );
  15.     /* 节点1初始化 */
  16.     vListInitialiseItem( &List_Item1 );
  17.     List_Item1.xItemValue = 1;
  18.     // listSET_LIST_ITEM_VALUE(&List_Item1 , 1);  通过宏初始化
  20.     /* 节点2初始化 */    
  21.     vListInitialiseItem( &List_Item2 );
  22.     List_Item2.xItemValue = 2;
  24.     /* 节点3初始化 */
  25.     vListInitialiseItem( &List_Item3 );
  26.     List_Item3.xItemValue = 3;
  28.     /* 将节点插入链表，按照升序排列 */
  29.     vListInsert( &List_Test, &List_Item2 );    
  30.     vListInsert( &List_Test, &List_Item1 );
  31.     vListInsert( &List_Test, &List_Item3 );    
  33.     for(;;)
  34.     {
  35.         /* 啥事不干 */
  36.     }
  37. }

仿真结果：
image.png