正点原子FreeRTOS学习笔记—

一、什么是列表和列表项

1、概念

在FreeRTOS中，有三个列表分别是就绪列表、阻塞列表与挂起列表。当任务状态改变就会迁移到其他列表中。

列表是一个双向环形链表,而链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表可以任意的插入与删除节点，并且不限制元素的数量。

列表项是存放在列表中的项目，用来存放FreeRTOS中的任务。

以右图举例，三个人组成的整体就作为一个列表，而每个人是这个列表中的列表项。列表项之间地址是非连续，是人为的连接到一起的。是依靠列表项中的pxNext（指向下一个地址指针）、pxPrevious（指向上一个地址指针）互相连接。相当于右图中的胳膊互相拉着。

2、FreeRTOS代码

（1）列表

typedef struct xLIST
{listFIRST_LIST_INTEGRITY_CHECK_VALUE      /*用来检测列表完整性*/volatile UBaseType_t uxNumberOfItems;     /*列表中列表项个数*/ListItem_t * configLIST_VOLATILE pxIndex; /*指向列表项的指针 */MiniListItem_t xListEnd;                  /*末尾列表项，由迷你列表项定义*/listSECOND_LIST_INTEGRITY_CHECK_VALUE     /*用来检测列表完整性*/
} List_t;

（2）列表项

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;                                     /*任务控制块 */struct xLIST * configLIST_VOLATILE pxContainer;     /*列表项所在列表 */listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE          /*校验值 */ 
};
typedef struct xLIST_ITEM ListItem_t;

（3）迷你列表项

struct xMINI_LIST_ITEM
{listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 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;

二、列表与列表项初始化

1、列表初始化

#define portMAX_DELAY    ( TickType_t ) 0xffffffffUL/*形参：待初始化列表*/
void vListInitialise( List_t * const pxList ) 
{/*列表的pxIndex指向末尾列表项*/pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );/*将末尾列表项数值设为最大*/pxList->xListEnd.xItemValue = portMAX_DELAY;/*列表的末尾列表项上一个下一个都指向自己，因为初始化只有末尾列表项*/pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );     pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );/*列表中列表项个数设为0，末尾列表项不计入*/pxList->uxNumberOfItems = ( UBaseType_t ) 0U;/*检测数据完整性*/listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}

2、列表项初始化

/*形参：待初始化列表项*/
void vListInitialiseItem( ListItem_t * const pxItem )
{/* 列表项所在列表设为空，初始化时不属于任何列表*/pxItem->pxContainer = NULL;/* 检测数据完整性 */listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}

三、列表插入与删除列表项

1、原理解释

在小红和小黑之间加入小蓝。小红的pxNext对应小黑，小黑的pxPrevious对应小红。现在小蓝加入列表之中，小红先把pxNext接上小蓝，小蓝把pxPrevious接上小红，小蓝就和小红牵上手；小黑把pxPrevious接上小蓝，小蓝又把pxNext接上小黑，小蓝就和小黑牵上手。这样小蓝这个列表项就加入到列表之中。

2、升序插入列表项

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 );/* 是否是末尾列表项*/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->pxContainer = pxList;/* 更新列表中列表项的数量 */( pxList->uxNumberOfItems )++;
}

3、末尾插入列表项

形参：待插入的列表，插入列表项
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 );/*更新待插入列表项的指针成员变量*/pxNewListItem->pxNext = pxIndex;pxNewListItem->pxPrevious = pxIndex->pxPrevious;/* 测试使用 */mtCOVERAGE_TEST_DELAY();/*更新列表中原本列表项的指针成员变量*/pxIndex->pxPrevious->pxNext = pxNewListItem;pxIndex->pxPrevious = pxNewListItem;/* 更新待插入列表项的所在成员变量 */pxNewListItem->pxContainer = pxList;/* 更新列表中列表项的数量 */( pxList->uxNumberOfItems )++;
}

4、移除列表项

形参：待移除的列表项
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 ){   /* pxIndex指向上一个列表项*/pxList->pxIndex = pxItemToRemove->pxPrevious;}else{mtCOVERAGE_TEST_MARKER();}/* 将待移除的列表项的所在列表指针清空 */pxItemToRemove->pxContainer = NULL;/* 更新列表中列表项的数量 */( pxList->uxNumberOfItems )--;/* 返回移除后列表中列表项的数量 */return pxList->uxNumberOfItems;
}