简介

列表和列表项是 FreeRTOS 的一个数据结构，FreeRTOS 大量使用到了列表和列表项，它是 FreeRTOS 的基石。这个列表和我们在数据结构里接触的列表是很像的。

列表和列表项的定义

列表

列表是 FreeRTOS 中的一个数据结构，概念上和链表有点类似，列表被用来跟踪 FreeRTOS中的任务。与列表相关的全部东西都在文件 list.c 和 list.h 中。在 list.h 中定义了一个叫 List_t 的结构体，如下：

  1. typedef struct xLIST
  2. {
  3.   listFIRST_LIST_INTEGRITY_CHECK_VALUE                     //检查列表完整性的
  4.   configLIST_VOLATILE UBaseType_t uxNumberOfItems;     //用来记录列表中列表项的数量
  5.   ListItem_t * configLIST_VOLATILE pxIndex;                         //用来记录当前列表项索引号
  6.   MiniListItem_t xListEnd;                                                         //列表中最后一个列表项，用来表示列表结束
  7.   listSECOND_LIST_INTEGRITY_CHECK_VALUE                 //检查列表完整性的
  8. } List_t;

检查列表完整性：需要将宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设置为 1，开启以后会分别在listFIRST_LIST_INTEGRITY_CHECK_VALUE和listSECOND_LIST_INTEGRITY_CHECK_VALUE上添加一个变量xListIntegrityValue1和xListIntegrityValue2，在初始化列表的时候会这两个变量中写入一个特殊的值，默认不开启这个功能。
06.列表和列表项 - 图1

列表项

列表项就是存放在列表中的项目，FreeRTOS 提供了两种列表项：列表项和迷你列表项。这两个都在文件 list.h 中有定义。
列表项

  1. struct xLIST_ITEM
  2. {
  3.    listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE       //检查列表项完整性          
  4.    configLIST_VOLATILE TickType_t xItemValue;                 //列表项值
  5.    struct xLIST_ITEM * configLIST_VOLATILE pxNext;         //指向下一个列表项
  6.    struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;  //指向前一个列表项
  7.    void * pvOwner;                                                                  //记录此链表项归谁拥有
  8.    void * configLIST_VOLATILE pvContainer;                        //记录此列表项归哪个列表
  9.    listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE  //列表完整性检查
  10. };
  11. typedef struct xLIST_ITEM ListItem_t;

pvContainer和pvOwner的区别：当创建一个任务以后 xStateListItem 的 pvOwner 变量就指向这个任务的任务控制块，表示 xSateListItem属于此任务。当任务就绪态以后 xStateListItem 的变量 pvContainer 就指向就绪列表，表明此列表项在就绪列表中。
06.列表和列表项 - 图2
迷你列表项
迷你列表项在文件 list.h 中有定义，如下：

  1. struct xMINI_LIST_ITEM
  2. {
  3.    listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE         //列表项完整性检查
  4.    configLIST_VOLATILE TickType_t xItemValue;                   //列表项的值
  5.    struct xLIST_ITEM * configLIST_VOLATILE pxNext;           //指向下一个列表项
  6.    struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;    //指向上一个列表项
  7. };
  8. typedef struct xMINI_LIST_ITEM MiniListItem_t;

06.列表和列表项 - 图3

列表和列表项初始化

列表初始化

列表的初始化其实就是初始化列表结构体List_t 中的各个成员变量，列表的初始化通过使函数 vListInitialise()来完成。

  1. void vListInitialise( List_t * const pxList )
  2. {
  3.     pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); 
  4.    pxList->xListEnd.xItemValue = portMAX_DELAY; 
  5.    pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); 
  6.    pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd ); 
  7.    pxList->uxNumberOfItems = ( UBaseType_t ) 0U; 
  8.    listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList ); 
  9.    listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList ); 
  10. }
  • xListEnd 用来表示列表的末尾，而 pxIndex 表示列表项的索引号，此时列表只有一个列表项，那就是 xListEnd，所以 pxIndex 指向 xListEnd。
  • xListEnd 的列表项值初始化为 portMAX_DELAY， portMAX_DELAY 是个宏，在文件portmacro.h 中有定义。根据所使用的 MCU 的不同，portMAX_DELAY 值也不相同，可以为 0xffff或者 0xffffffffUL，本教程中为 0xffffffffUL。
  • 初始化列表项xListEnd的pxNext和pxPrevious变量，因为此时列表只有一个列表项xListEnd，因此 pxNext和pxPrevious只能指向自身。
  • 由于此时没有其他的列表项，因此 uxNumberOfItems 为 0，注意这里没有算 xListEnd。
  • listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList )和listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList )是为了检查列表完整性的

06.列表和列表项 - 图4

列表项初始化

同列表一样，列表项在使用的时候也需要初始化，列表项初始化由函数 vListInitialiseItem()来完成。

  1. void vListInitialiseItem( ListItem_t * const pxItem )
  2. {
  3.    pxItem->pvContainer = NULL; //初始化 pvContainer 为 NULL
  4.    //初始化用于完整性检查的变量，如果开启了这个功能的话。
  5.    listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
  6.    listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
  7. }

列表项的初始化很简单，只是将列表项成员变量 pvContainer 初始化为 NULL，并且给用于完整性检查的变量赋值。

列表项插入

列表项的插入操作通过函数 vListInsert()来完成。

  1. void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )

参数

  • pxList: 列表项要插入的列表。
  • pxNewListItem: 要插入的列表项。

返回值
无
函数 vListInsert()的参数 pxList 决定了列表项要插入到哪个列表中，pxNewListItem 决定了要插入的列表项，但是这个列表项具体插入到什么地方呢？要插入的位置由列表项中成员变量xItemValue 来决定。列表项的插入根据 xItemValue 的值按照升序的方式排列。

  1. void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
  2. {
  3.    ListItem_t *pxIterator;
  4.    const TickType_t xValueOfInsertion = pxNewListItem->xItemValue; 
  5.    listTEST_LIST_INTEGRITY( pxList ); 
  6.    listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
  7.    if( xValueOfInsertion == portMAX_DELAY ) {
  8.      pxIterator = pxList->xListEnd.pxPrevious;  
  9.    }
  10.    else
  11.    {
  12.       for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->\ 
  13.       pxNext->xItemValue <=xValueOfInsertion; pxIterator = pxIterator->pxNext ) 
  14.       {
  15.          //空循环，什么也不做！
  16.       } 
  17.    }
  18.    pxNewListItem->pxNext = pxIterator->pxNext; 
  19.    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
  20.    pxNewListItem->pxPrevious = pxIterator;
  21.    pxIterator->pxNext = pxNewListItem;
  22.    pxNewListItem->pvContainer = ( void * ) pxList; 
  23.    ( pxList->uxNumberOfItems )++; 
  24. }

从上面的代码可以看出来列表项的插入其实就是根据需要插入列表项的值找到插入的位置，然后将列表插入进去就可以了。接下来将当前插入的列表项的pvContainer 指针指向当前的列表，将列表数量加一。

列表项末尾插入

列表末尾插入列表项的操作通过函数 vListInsertEnd ()来完成。

  1. void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )

参数

  • pxList: 列表项要插入的列表。
  • pxNewListItem: 要插入的列表项。

返回值
无

  1. void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
  2. {
  3.    ListItem_t * const pxIndex = pxList->pxIndex;
  4.    listTEST_LIST_INTEGRITY( pxList ); (1)
  5.    listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
  6.    pxNewListItem->pxNext = pxIndex; (2)
  7.    pxNewListItem->pxPrevious = pxIndex->pxPrevious;
  8.    mtCOVERAGE_TEST_DELAY();
  9.    pxIndex->pxPrevious->pxNext = pxNewListItem;
  10.    pxIndex->pxPrevious = pxNewListItem;
  11.    pxNewListItem->pvContainer = ( void * ) pxList; (3)
  12.    ( pxList->uxNumberOfItems )++; (4)
  13. }

使用函数vListInsert()向列表中插入一个列表项的时候这个列表项的位置是通过列表项的值，也就是列表项成员变量 xItemValue 来确定。vListInsertEnd()完成列表插入的时候不通过xItemValue 值确定位置，而是直接插入到列表的末尾。这里列表中的pxIndex代表的就是开头的列表项的。由于列表项是一个双向循环列表，所以直接将新的列表项插入到pxIndex之前就可以了。从代码可以看出实际插入不是初始化时的最后一个位置，而是当前列表的最后一个位置。可以有点绕，这里需要理解pxIndex到底指向了哪里。

列表的删除

列表项的删除通过函数 uxListRemove()来完成。

  1. UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )

参数

  • pxItemToRemove: 要删除的列表项

返回值

  • 返回删除列表项以后的列表剩余列表项数目。

列表项的删除只是将指定的列表项从列表中删除掉，并不会将这个列表项的内存给释放掉。因此需要我们自己去释放内存。

  1. UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
  2. {
  3.    List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;
  4.    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious; 
  5.    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
  6.    mtCOVERAGE_TEST_DELAY();
  7.    if( pxList->pxIndex == pxItemToRemove )
  8.    {
  9.       pxList->pxIndex = pxItemToRemove->pxPrevious; 
  10.    }
  11.    else
  12.    {
  13.       mtCOVERAGE_TEST_MARKER();
  14.    }
  15.    pxItemToRemove->pvContainer = NULL; 
  16.    ( pxList->uxNumberOfItems )--;
  17.    return pxList->uxNumberOfItems; 
  18. }

列表项的遍历

介绍列表结构体的时候说过列表 List_t 中的成员变量 pxIndex 是用来遍历列表的，FreeRTOS提供了一个函数来完成列表的遍历，这个函数是 listGET_OWNER_OF_NEXT_ENTRY()。每调用一次这个函数列表的 pxIndex 变量就会指向下一个列表项，并且返回这个列表项的 pxOwner变量值。这个函数本质上是一个宏，这个宏在文件 list.h 中如下定义：

  1. #define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList ) \ 
  2. { \
  3.    List_t * const pxConstList = ( pxList ); \
  4.    ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \ 
  5.    if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) )\ 
  6.    { \
  7.       ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \ 
  8.    } \
  9.    ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner; \ 
  10. }

pxTCB 用来保存 pxIndex 所指向的列表项的 pvOwner 变量值，也就是这个列表项属于谁的