详解FreeRTOS开发过程（二）-- 列表和列表项

一.列表和列表项

1.列表

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

typedef struct xLIST
{listFIRST_LIST_INTEGRITY_CHECK_VALUE    //用来检查列表完整性	configLIST_VOLATILE UBaseType_t uxNumberOfItems;    //用来记录列表中列表项的数量ListItem_t * configLIST_VOLATILE pxIndex;    //用来记录当前列表项索引号，用于遍历列表	MiniListItem_t xListEnd;	//列表中最后一个列表项，用来表示列表结束						listSECOND_LIST_INTEGRITY_CHECK_VALUE	//用来检查列表完整性	
} List_t;

        列表结构的示意图如下图所示：

 2.列表项

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

struct xLIST_ITEM
{listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE    //用来检查列表项完整性的	configLIST_VOLATILE TickType_t xItemValue;    //列表项值			struct xLIST_ITEM * configLIST_VOLATILE pxNext;    //指向下一个列表项		struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;	//指向前一个列表项void * pvOwner;    //记录此链表项归谁拥有，通常是任务控制块。										void * configLIST_VOLATILE pvContainer;		//用来记录此列表项归哪个列表		listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE    //用来检查列表项完整性的			
};
typedef struct xLIST_ITEM ListItem_t;					

        列表项结构的示意图如下图所示：

3.迷你列表项 

        迷你列表项的定义如下所示：

struct xMINI_LIST_ITEM
{listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE			configLIST_VOLATILE TickType_t xItemValue;struct xLIST_ITEM * configLIST_VOLATILE pxNext;struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;

        有些情况下我 们不需要列表项这么全的功能，可能只需要其中的某几个成员变量，如果此时用列表项的话会 造成内存浪费，比如上面列表结构体 List_t 中表示最后一个列表项的成员变量 xListEnd 就是 MiniListItem_t 类型的。

二.列表和列表项初始化 

1.列表初始化 

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

void vListInitialise( List_t * const pxList )
{pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );			//xListEnd用来表示列表的末尾，而pxIndex表示列表项的索引号，此时列表只有一个列表项，那就是xListEnd，所以pxIndex指向xListEnd。 pxList->xListEnd.xItemValue = portMAX_DELAY;//xListEnd 的列表项值初始化为portMAX_DELAY，在文件portmacro.h 中有定义。根据所使用的MCU的不同，portMAX_DELAY值也不相同，pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );	//初始化列表项xListEnd 的 pxNext 变量，因为此时列表只有一个列表项xListEnd，因此pxNext只能指向自身。 pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );//初始化xListEnd的pxPrevious 变量，指向xListEnd自身。pxList->uxNumberOfItems = ( UBaseType_t ) 0U;//由于此时没有其他的列表项，因此uxNumberOfItems为0listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}

        列表初始化完以后如下图所示：

2.列表项初始化

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

void vListInitialiseItem( ListItem_t * const pxItem )
{pxItem->pvContainer = NULL;listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}

        列表项的初始化很简单，只是将列表项成员变量pvContainer初始化为NULL，并且给用于完整性检查的变量赋值。列表项要根据实际使用情况来初始化，比如任务创建函数xTaskCreate()就会对任务堆栈中的xStateListItem和xEventListItem这两个列表项中的其他成员变量在做初始化。

3.列表项插入 

        列表项的插入操作通过函数vListInsert()来完成，函数原型如下：

void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
pxList:列表项要插入的列表
pxNewListItem:要插入的列表项。

        函数vListInsert()的参数pxList决定了列表项要插入到哪个列表中，pxNewListItem决定了要插入的列表项，要插入的位置由列表项中成员变量 xItemValue来决定。vListInsert()的整个运行过程，函数代码如下：

void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{ListItem_t *pxIterator;//获取要插入的列表项值，即列表项成员变量xItemValue的值，//因为要根据这个值来确定列表项要插入的位置。const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;//检查列表和列表项的完整性的。//其实就是检查列表和列表项中用于完整性检查的变量值是否被改变。listTEST_LIST_INTEGRITY( pxList );listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );//如果要插入的列表项的值等于portMAX_DELAY,要插入的位置就是列表最末尾了。if( xValueOfInsertion == portMAX_DELAY ){pxIterator = pxList->xListEnd.pxPrevious;}else{for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd );pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) {}}//始接下来的四行代码就是将列表项插入到列表中，插入过程和数据结构中双向链表的插入类似。pxNewListItem->pxNext = pxIterator->pxNext;pxNewListItem->pxNext->pxPrevious = pxNewListItem;pxNewListItem->pxPrevious = pxIterator;pxIterator->pxNext = pxNewListItem;pxNewListItem->pvContainer = ( void * ) pxList;( pxList->uxNumberOfItems )++;
}

4.列表项插入过程图示

        a.插入值为40的列表项

        在一个空的列表List中插入一个列表值为40的列表项ListItem1，插入完成以后如下图所示：

        注意观察插入完成以后列表List 和列表项 ListItem1 中各个成员变量之间的变化，比如列表List 中的uxNumberOfItems 变为了1，表示现在列表中有一个列表项。列表项ListItem1中的 pvContainer 变成了List，表示此列表项属于列表List。通过上图可以看出，列表是一个环形的，即环形列表。

        b.插入值为60的列表项

        接着再插入一个值为60的列表项ListItem2，插入完成以后如下图所示：

        函数vListInsert()在插入列表项是按照升序的方式插入的，所以ListItem2 肯定是插入到ListItem1的后面、xListEnd的前面。同样的，列表List的uxNumberOfItems再次加一变为2了，说明此时列表中有两个列表项。 

5.列表项末尾插入

        列表末尾插入列表项的操作通过函数vListInsertEnd()来完成，函数原型如下：

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )pxList:列表项要插入的列表
pxNewListItem:要插入的列表项

        函数vListInsertEnd()源码如下：

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{ListItem_t * const pxIndex = pxList->pxIndex;//对列表和列表项的完整性检查listTEST_LIST_INTEGRITY( pxList );listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );//vListInsertEnd()是往列表的末尾添加列表项的，这里所谓的末尾要根据列表的成员变量
//pxIndex来确定的,前面说了列表中的pxIndex成员变量是用来遍历列表的，pxIndex所指向的
//列表项就是要遍历的开始列表项，也就是说pxIndex所指向的列表项就代表列表头,由于是个
//环形列表，所以新的列表项就应该插入到pxIndex所指向的列表项的前面。pxNewListItem->pxNext = pxIndex;pxNewListItem->pxPrevious = pxIndex->pxPrevious;mtCOVERAGE_TEST_DELAY();pxIndex->pxPrevious->pxNext = pxNewListItem;pxIndex->pxPrevious = pxNewListItem;//标记新的列表项pxNewListItem属于列表pxList。pxNewListItem->pvContainer = ( void * ) pxList;//记录列表中的列表项数目的变量加一( pxList->uxNumberOfItems )++;
}

6.列表项末尾插入图示

        a.默认列表

        在插入列表项之前我们先准备一个默认列表，如下图所示：

        列表的pxIndex 所指向的列表项，这里为ListItem1，不再是xListEnd了 。

        b.插入值为50的列表项

        在上面的列表中插入一个值为50的列表项ListItem3，插入完成以后如下图所示：        

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

7.列表项的删除

        列表项的删除通过函数 uxListRemove()来完成，函数原型如下： 

UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
pxItemToRemove:要删除的列表项

        列表项的删除只是将指定的列表项从列表中删除掉，并不会将这个列表项的内存给释放掉，如果这个列表项是动态分配内存的话。函数uxListRemove()的源码如下：

UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{//要删除一个列表项我们得先知道这个列表项处于哪个列表中，直接读取列表项中的成员变量pvContainerList_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;//将要删除的列表项的前后两个列表项“连接”在一起。 pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;mtCOVERAGE_TEST_DELAY();//pxIndex正好指向要删除的列表项，删除列表项以后pxIndex就是被删除列表项的前一个列表项。if( pxList->pxIndex == pxItemToRemove ){pxList->pxIndex = pxItemToRemove->pxPrevious;}else{mtCOVERAGE_TEST_MARKER();}//被删除列表项的成员变量pvContainer清零。pxItemToRemove->pvContainer = NULL;( pxList->uxNumberOfItems )--;//返回新列表的当前列表项数目。return pxList->uxNumberOfItems;
}

8.列表的遍历

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

#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )										
{		//pxTCB 用来保存pxIndex所指向的列表项的pvOwner变量值																					List_t * const pxConstList = ( pxList );													( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;							if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) )	{																						( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;						}																						( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;											
}