1. 什么是列表和列表项
1.1 列表
列表是FreeRTOS的一个数据结构，被用来跟踪FreeRTOS中的任务。与列表有关的东西都在list.c和list.h文件里。在list.h中定义了一个List_t的结构体：

1. typedef struct xLIST
   
2. {
   
3.   listFIRST_LIST_INTEGRITY_CHECK_VALUE          // 检查列表完整性，将configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设1。默认不开启
   
4.   configLIST_VOLATILE UBaseType_t uxNumberOfItems; // 用来记录列表中列表项的数量
   
5.   ListItem_t * configLIST_VOLATILE pxIndex;               // 用来记录当前列表项索引号，用于遍历列表
   
6.   MiniListItem_t xListEnd;                                       // 列表中最后一个列表项，用来表示列表结束，此变量类型为MiniListItem_t
   
7.   listSECOND_LIST_INTEGRITY_CHECK_VALUE                       // 检查列表完整性，将configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设1。默认不开启
   
8. } List_t;

复制代码

列表结构示意图为：


1.2 列表项
列表项就是存放在列表中的项目，FreeRTOS有两种列表项：列表项和迷你列表项，在list.h中定义：

1. struct xLIST_ITEM
   
2. {
   
3.         listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE        
   
4.         configLIST_VOLATILE TickType_t xItemValue;                // xItemValue列表项值        
   
5.         struct xLIST_ITEM * configLIST_VOLATILE pxNext;                // pxNext指向下一个列表项
   
6.         struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;        // 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再多说两句，在任务控制块TCB_t中有两个变量xStateListItem和xEventListItem，这两个变量类型是ListItem_t，即这两个成员变量是列表项。以xStateListItem为例，当创建一个任务后，xStateListItem的pvOwner变量指向这个任务的任务控制块，表示xStateListItem属于此任务。当任务就绪态以后，xStateListItem的变量pvContainer就指向就绪列表，表面此列表项在就绪列表中。
列表项结构示意图如下：



1.3 迷你列表项
迷你列表项在list.h中定义：

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

复制代码

迷你列表项结构示意图如下：



2. 列表和列表项初始化
2.1 列表初始化
新创建或定义的列表需要对其做初始化处理，列表的初始化其实就是初始化列表结构体List_t中的各个成员变量，列表的初始化通过使函数vListInitialise()来完成，此函数在list.c中有定义：

1. void vListInitialise( List_t * const pxList )
   
2. {
   
3.     // xListEnd用来表示列表的末尾，而pxIndex表示索引号，此时列表只有一个列表项，就是xListEnd,所以pxIndex指向xListEnd。
   
4.         pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );  
   
5.         // xListEnd列表项值初始化为portMAX_DELAY(在portmacro.h中定义)。本教程为0xffffffffUL
   
6.         pxList->xListEnd.xItemValue = portMAX_DELAY;
   
7.         // 初始化列表项xListEnd的pxNext变量，因为此列表只有一个列表项，因此pxNext指向自身
   
8.         pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );        
   
9.         // 初始化xListEnd的pxPrevious变量，指向xListEnd自身
   
10.         pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );
    
11.         // 由于此时没有其他的列表项，因此uxNumberOfItems为0，注意：这里不算xListEnd
    
12.         pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
    
13.         // 以下两行用于完整性检查字段，只有configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES为1时有效。STM32写入的是0x5a5a5a5aUL
    
14.         listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
    
15.         listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
    
16. }

复制代码

列表初始化如下图：



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

1. void vListInitialiseItem( ListItem_t * const pxItem )
   
2. {
   
3.         pxItem->pvContainer = NULL;    // 初始化pvContainer为NULL
   
4.         listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
   
5.         listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
   
6. }

复制代码

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

3. 列表项插入
3.1 列表项插入函数分析
列表项的插入操作用vListInsert()完成：

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.         // 判断插入列表项的值是否等于portMAX_DELAY，即列表项最大值，是的话就插入列表的最末尾
   
8.         if( xValueOfInsertion == portMAX_DELAY )
   
9.         // 获取要插入点，xListEnd表示列表末尾，初始化时xListEnd=portMAX_DELAY，此时要插入的列表项的列表值也是portMAX_DELAY,放在前面
   
10.         {        pxIterator = pxList->xListEnd.pxPrevious;        }
    
11.         else
    
12.         {
    
13.                 // 否则，需要在列表中一个一个的找位置，for循环就是找位置的过程，当找到合适的列表项位置时就跳出。
    
14.                 for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd );
    
15.                 pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )
    
16.                 {        /* 空循环 */        }
    
17.         }
    
18.         // 经过上面查找，找到列表项插入点。以下四行代码是将列表项插入到列表中，
    
19.     pxNewListItem->pxNext = pxIterator->pxNext;
    
20.         pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    
21.         pxNewListItem->pxPrevious = pxIterator;
    
22.         pxIterator->pxNext = pxNewListItem;
    
23.         // 列表项已经插入到列表中，那么成员变量pvContainer也记录此列表项属于哪个列表
    
24.         pxNewListItem->pvContainer = ( void * ) pxList;
    
25.         // 列表的成员变量uxNumberOfItems加一，表示添加一个列表项
    
26.         ( pxList->uxNumberOfItems )++;
    
27. }

复制代码

3.2 列表项插入过程示意图

1）插入值为40的列表项
在一个空列表List中插入一个列表值为40的列表项ListItem1，完成后如图：



由图可知，列表List和列表项ListItem1中，uxNumberOfItem值为1，表示现在列表中有一个列表项，pvContainer值为List，表示该列表项属于List，此列表是一个环形列表！

2）再插入值为60的列表项
完成后如下图：



列表项是按照升序的方式插入的，所以ListItem2是插入到ListItem1的后面、xListEnd的前面。

3）在插入值为50的列表项
完成后如下图所示：



按照升序排列的方式，ListItem3放到ListItem1和ListItem2中间。

4. 列表项末尾插入
4.1 列表项末尾插入函数分析
列表末尾插入列表项的操作通过函数vListInsertEnd()实现：

1. void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
   
2. {
   
3.         ListItem_t * const pxIndex = pxList->pxIndex;
   
4.         listTEST_LIST_INTEGRITY( pxList );              // 列表完整性检查
   
5.         listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );  // 列表项完整性检查
   
6.         // 将要插入的列表项插入列表末尾，往列表的末尾添加列表项，由成员变量pxIndex确定，pxIndex指向列表项代表列表头，新列表项插入到pxIndex前面
   
7.         pxNewListItem->pxNext = pxIndex;
   
8.         pxNewListItem->pxPrevious = pxIndex->pxPrevious;
   
9.         mtCOVERAGE_TEST_DELAY();
   
10.         pxIndex->pxPrevious->pxNext = pxNewListItem;
    
11.         pxIndex->pxPrevious = pxNewListItem;
    
12.         pxNewListItem->pvContainer = ( void * ) pxList;   // 标记新的列表项pxNewListItem，属于列表PxList
    
13.         ( pxList->uxNumberOfItems )++;                    // 记录列表中的列表项数目的变量加一
    
14. }

复制代码

4.2 列表项末尾插入图示

1）默认列表
在插入列表项前准备一个默认列表：



注意pxIndex指向的列表项为ListItem1。

2） 插入值为50的列表项
在上面的列表中插入值为50的列表项ListItem3，插入完成后如图：



列表List的pxIndex指向列表项的ListItem1，因此用vListInsertEnd()函数插入ListItem3的话就会在ListItem1的前面插入。

5. 列表项的删除
列表项的删除通过函数uxListRemove()完成，如下：

1. UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
   
2. {
   
3.         // 读取列表项成员变量pvContainer获知此列表项处于哪个列表中
   
4.         List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;
   
5.         // 与下面一行代码完成列表项的删除
   
6.         pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
   
7.         pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
   
8.         mtCOVERAGE_TEST_DELAY();
   
9.         if( pxList->pxIndex == pxItemToRemove )
   
10.         // 如果pxIndex正好指向要删除的列表项，那么删除后要重新给pxIndex找对象，新对象是被删除的列表项的前一个列表项
    
11.         {        pxList->pxIndex = pxItemToRemove->pxPrevious;        }
    
12.         else        {        mtCOVERAGE_TEST_MARKER();        }
    
13.         pxItemToRemove->pvContainer = NULL;  // 被删除的列表项的成员变量pvContainer清零
    
14.         ( pxList->uxNumberOfItems )--;
    
15.         return pxList->uxNumberOfItems;      // 返回新列表的当前列表项数目
    
16. }

复制代码

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

1. // pxTCB用来保存pxIndex所指向的列表项的pvOwner变量值。pxList表示要遍历的列表
   
2. #define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )                                                                                
   
3. {                                                                                                                                                                                       
   
4.         List_t * const pxConstList = ( pxList );                                                                                                                                                        
   
5.         ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;        // PxIndex变量指向下一个列表项
   
6.         // 如果pxIndex指向列表的xListEnd成员变量，表示到列表末尾                                                
   
7.         if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) )        
   
8.         {        // 如果到列表末尾的话就跳过xListEnd，pxIndex再一次重新指向处于列表头的列表项，完成一次对列表的遍历                                                                                                                                                                        
   
9.                 ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                                                
   
10.         }                                                                                                                                                                                
    
11.         ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;        // 将pxIndex所指向的新列表项的pvOwner赋值为pxTCB                                                                                
    
12. }

复制代码

————————————————
版权声明：天亮继续睡