目录
一、概念及其应用
1.1列表List_t
1.2列表项ListItem_t
1.3迷你列表项MiniListItem_t
二、相关API
三、实现原理
3.1列表初始化
3.2列表项初始化
3.3插入列表项
3.4尾插列表项
3.5列表项的删除
3.6列表的遍历
一、概念及其应用
作为多任务的核心，列表和列表项在FreeRTOS中被大量使用，功不可没
列表和列表项是一个数据结构，简单地说，列表是一个结构体，列表项也是一个结构体，但它作为列表的一个成员，而在freertos中的列表和列表项构成的是双向链表结构
1.1列表List_t
typedef struct xLIST
{
listFIRST_LIST_INTEGRITY_CHECK_VALUE /*列表完整性检查1*/
volatile UBaseType_t uxNumberOfItems; //列表中的列表项数量
ListItem_t * configLIST_VOLATILE pxIndex;/*列表项索引，用于列表的遍历*/
MiniListItem_t xListEnd; /*< 迷你列表项 列表中的最后一个列表项 列表尾*/
listSECOND_LIST_INTEGRITY_CHECK_VALUE /*列表完整性检查2*/
} List_t;
1.2列表项ListItem_t
struct xLIST_ITEM
{
listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*列表完整性检查1*/
configLIST_VOLATILE TickType_t xItemValue; /* 列表项的值 可用来有序管理列表 */
struct xLIST_ITEM * configLIST_VOLATILE pxNext; /* 指向下一个列表项*/
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /* 指向上一个列表项*/
void * pvOwner; /*列表项的所属任务控制块*/
struct xLIST * configLIST_VOLATILE pxContainer; /*列表项的所属列表*/
listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE /*列表完整性检查2*/
};
typedef struct xLIST_ITEM ListItem_t;对于pvOwner、pxContainer 可以简单理解成，列表项是文件，pxContainer是文件夹，pvOwner是执行程序
1.3迷你列表项MiniListItem_t
struct xMINI_LIST_ITEM
{
listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /* 列表完整性检查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;
二、相关API
#inlcude "list.h"
/*初始化列表*/
void vListInitialise(List_t * const pxList)
/*初始化列表项*/
void vListInitialiseItem(List_t * const pxItem)
/*插入列表项 根据成员 xItemValue来寻找插入点*/
void vListInset(List_t *const pxList, ListItem_t * const pxNewListItem)
/*尾插列表项 可简单理解 一般插入按升序 而尾插是倒序 可用于同一优先级插入就序列表*/
void vListInsetEnd(List_t *const pxList, ListItem_t * const pxNewListItem)
/*删除列表项 只需要列表项指针，因为列表项成员pxContainer表示了它归属的列表 成功返回列表项个数*/
UBaseType_t uxListRemove(ListItem_t * const pxNewListItem)三、实现原理
3.1列表初始化
void vListInitialise( List_t * const pxList )
{
/* 因为xListEnd是迷你列表项表示列表尾，而Index索引列表项，初始化时只能指向列表尾*/
pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );
/* 列表尾的值赋值最大 便于查找*/
pxList->xListEnd.xItemValue = portMAX_DELAY;
/* next指向自己 previous也指向自己*/
pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );
pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );
pxList->uxNumberOfItems = ( UBaseType_t ) 0U;//列表中列表项数量为0
/* 列表完整性检查*/
listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}3.2列表项初始化
void vListInitialiseItem( ListItem_t * const pxItem )
{
/* 列表项初始化当然还没有归属哪个列表，因而赋值NULL */
pxItem->pxContainer = NULL;
/* 列表项完整性检查*/
listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}3.3插入列表项
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t *pxIterator; //插入点
const TickType_t xValueOfInsertion = pxNewListItem->xItemValue; //获取待插入列表项的值
/* 列表和列表项完整性检查*/
listTEST_LIST_INTEGRITY( pxList );
listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
/*如果列表项的值最大，插入到列表尾xListEnd的前面*/
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; //待插入列表项的next继承插入点的next
pxNewListItem->pxNext->pxPrevious = pxNewListItem;//待插入列表项的next的previous更新为待插入列表项
pxNewListItem->pxPrevious = pxIterator; //待插入列表项的previous更新为插入点
pxIterator->pxNext = pxNewListItem; //插入点的next更新为previous
//至此，升序 插入点、待插入列表项、待插入列表项后的列表项 中间的关系全部整理完毕 很严谨！
/* 待插入列表项的归属赋值为要插入进的列表 */
pxNewListItem->pxContainer = pxList;
( pxList->uxNumberOfItems )++; //列表中列表项数量+1
}
3.4尾插列表项
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 );
/*pxIndex 指向列表中的第一个列表项 尾插则会更新第一个列表项为待尾插的列表项 */
pxNewListItem->pxNext = pxIndex;
pxNewListItem->pxPrevious = pxIndex->pxPrevious;
/* Only used during decision coverage testing. */
mtCOVERAGE_TEST_DELAY();
/*更新列表的索引*/
pxIndex->pxPrevious->pxNext = pxNewListItem;
pxIndex->pxPrevious = pxNewListItem;
/* 标记列表项归属 */
pxNewListItem->pxContainer = pxList;
( pxList->uxNumberOfItems )++;//列表中列表项数量+1
}3.5列表项的删除
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
List_t * const pxList = pxItemToRemove->pxContainer; //获取列表项的归属列表
/*修改前后指向*/
pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
/* Only used during decision coverage testing. */
mtCOVERAGE_TEST_DELAY();
/*确保pxIndex指向第一个列表项*/
if( pxList->pxIndex == pxItemToRemove )
{
pxList->pxIndex = pxItemToRemove->pxPrevious;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
pxItemToRemove->pxContainer = NULL;//待删除列表项的归属 赋值NULL
( pxList->uxNumberOfItems )--; //列表中列表项数量-1
return pxList->uxNumberOfItems; //返回列表项数量
}3.6列表的遍历
前面说列表结构体List_t中的成员变量pxIndex是用来遍历列表的
FreeRTOS提供了一个函数来完成列表的遍历
listGET_OWNER_OF_NEXT_ENTRY()
每调用一次这个函数列表的 pxIndex变量就会指向下一个列表项，并且返回这个列表项的pxOwner变量值。
这个函数本质上是一个宏，list.h 中如下定义:
#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList ) \
{ \
List_t * const pxConstList = ( pxList ); \
\ /*获取列表 列表的索引更新为索引的next */ \
( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \
/*如果索引指向了列表尾，更新为第一个列表项*/ \
if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) ) \
{ \
( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \
} \
( pxTCB ) = ( pxConstList )->pxIndex->pvOwner; /*返回列表项的任务控制块归属 赋值给传入的pxTCB*/\ \
}
