目录

1 FreeRTOS中链表的实现

1.1 实现链表节点

1.2 实现链表根节点

1.3 将节点插入到链表的尾部

1.4 将节点按照升序排列插入到链表

1.5 将节点从链表删除

1.6 节点带参宏小函数

2 链表操作实验

---

1 FreeRTOS中链表的实现

1.1 实现链表节点

在FreeRTOS操作系统中，任务、事件和定时器等经常需要被添加、移除或重新排序，链表能够高效且灵活的方式来管理动态变化的数据集合。

xLIST_ITEM结构体定义了一个双向链表节点，它包含一个用于排序的辅助值、指向链表中前一个和后一个节点的指针、一个指向拥有该节点的内核对象的指针（通常是任务控制块TCB），以及一个指向该节点所属链表的指针。

struct xLIST_ITEM{TickType_t xItemValue;         /*辅助值，用于帮助节点做顺序排列*/struct xLIST_ITEM * pxNext;      /*指向链表下一个节点*/struct xLIST_ITEM * pxPrevious;  /*指向链表前一个节点*/void * pvOwner;                 /*指向拥有该节点的内核对象，通常是TCB*/void * pvContainer;             /*指向该节点所在的链表*/
};
typedef struct xLIST_ITEM ListItem_t;/*节点数据类型重定义*/

MiniListItem_t是ListItem_t的一个简化版本，通常用于表示链表的起始和结束节点。

struct xMINI_LIST_ITEM
{TickType_t xItemValue;         /*辅助值，用于帮助节点做升序排列*/struct xLIST_ITEM * pxNext;      /*指向链表下一个节点*/struct xLIST_ITEM * pxPrevious;  /*指向链表前一个节点*/
};
typedef struct xMINI_LIST_ITEMMiniListItem_t; /*精简节点数据类型重定义*/

节点示意图如图：

             

xItemValue：TickType_t类型的变量，通常用于存储与节点相关的值，比如任务的优先级或者任务的等待时间等，可以帮助在排序链表时确定节点的顺序。TickType_t具体表示16位还是32位，由configUSE_16_BIT_TICKS这个宏决定，当该宏定义为1时，TickType_t为16位，否则为32位。

pxNext：xLIST_ITEM类型的指针，它指向链表中的下一个节点。在双向链表中，每个节点都通过pxNext和pxPrevious指针与相邻节点相连。

pxPrevious：xLIST_ITEM类型的指针，它指向链表中的前一个节点，使得链表可以双向遍历。

pvOwner：指向void类型的指针，它通常用来指向拥有该节点的内核对象。在FreeRTOS中，这通常是任务控制块（TaskControlBlock，TCB），表示这个节点是由哪个任务拥有的。

pvContainer：指向void类型的指针，它指向包含该节点的容器，比如任务列表或者队列。

链表节点初始化函数在list.c中实现，初始化的时候只需将pvContainer初始化为空即可，表示该节点还没有插入到任何链表，具体实现见代码清单。

void vListInitialiseItem(ListItem_t*constpxItem)
{/*初始化该节点所在的链表为空，表示节点还没有插入任何链表*/pxItem->pvContainer=NULL;}

1.2 实现链表根节点

链表根节点是链表的头部，它包含了链表的元数据和指向链表中第一个和最后一个节点的指针。

typedef structxLIST
{UBaseType_t uxNumberOfItems; /*链表节点计数器*/ListItem_t * pxIndex;         /*链表节点索引指针*/MiniListItem_t xListEnd;     /*链表最后一个节点*/
}List_t;

链表根结点和完整的数据结构示意图如图：

uxNumberOfItems：UBaseType_t类型的变量，用于存储链表中当前的节点数量。

pxIndex：指向ListItem_t类型的指针，它用作链表的索引指针。用于快速访问链表中的节点，特别是在需要遍历链表时。

xListEnd：MiniListItem_t类型的结构体，它代表链表的最后一个节点。

链表节点初始化函数在list.c中实现，具体实现见代码清单6-10，初始化好的根节点示意图具体见。

void vListInitialise(List_t*constpxList)
{/*将链表索引指针指向最后一个节点*/pxList->pxIndex=(ListItem_t*) &(pxList->xListEnd);/*将链表最后一个节点的辅助排序的值设置为最大，确保该节点就是链表的最后节点*/pxList->xListEnd.xItemValue = portMAX_DELAY;/*将最后一个节点的pxNext和pxPrevious指针均指向节点自身，表示链表为空*/pxList->xListEnd.pxNext=(ListItem_t*) &(pxList->xListEnd);pxList->xListEnd.pxPrevious=(ListItem_t*) &(pxList->xListEnd);/*初始化链表节点计数器的值为0，表示链表为空*/pxList->uxNumberOfItems=(UBaseType_t)0U;
}

链表根结点初始化示意图如图：

pxList->pxIndex=(ListItem_t*) &(pxList->xListEnd)：这行代码将链表的索引指针pxIndex设置为指向链表的最后一个节点xListEnd。在初始化时，由于链表为空，索引指针指向最后一个节点，这样在添加第一个节点时，可以很容易地将其插入到链表的末尾。

pxList->xListEnd.xItemValue=portMAX_DELAY：这行代码将链表最后一个节点的xItemValue设置为portMAX_DELAY。portMAX_DELAY是FreeRTOS中定义的一个常量，表示最大的延迟时间。由于xItemValue用于排序，将最后一个节点的值设置为最大值可以确保它始终位于链表的末尾。

pxList->xListEnd.pxNext=(ListItem_t*) &(pxList->xListEnd)：这行代码将链表最后一个节点的pxNext指针设置为指向自身。在链表为空时，最后一个节点的pxNext和pxPrevious指针都指向自身，形成一个循环，表示链表没有其他节点。

pxList->xListEnd.pxPrevious=(ListItem_t*) &(pxList->xListEnd)：这行代码将链表最后一个节点的pxPrevious指针也设置为指向自身。这样，无论是向前遍历还是向后遍历链表，都会遇到这个节点，从而知道已经到达链表的末尾。

pxList->uxNumberOfItems=(UBaseType_t)0U：这行代码将链表的节点计数器uxNumberOfItems初始化为0，表示链表在开始时是空的。

1.3 将节点插入到链表的尾部

将节点插入到链表的尾部（可以理解为头部）就是将一个新的节点插入到一个空的链表，具体代码实现见代码。

void vListInsertEnd(List_t* constpxList, ListItem_t* constpxNewListItem)
{ListItem_t* constpxIndex = pxList->pxIndex;pxNewListItem->pxNext = pxIndex;pxNewListItem->pxPrevious = pxIndex->pxPrevious;pxIndex->pxPrevious->pxNext = pxNewListItem;pxIndex->pxPrevious = pxNewListItem;/*记住该节点所在的链表*/pxNewListItem->pvContainer = (void*) pxList;/*链表节点计数器++*/(pxList->uxNumberOfItems)++;
}

1.4 将节点按照升序排列插入到链表

将一个新节点按照其排序值插入到链表中，如果新节点的排序值为portMAX_DELAY，则将其插入到链表末尾；否则，遍历链表找到适当的位置，然后按照升序插入新节点，并更新链表的节点计数器。

void vListInsert(List_t * const pxList, ListItem_t * const pxNewListItem)
{ListItem_t *pxIterator;/*获取节点的排序辅助值*/const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;/* 确定新节点的插入位置 */if (xValueOfInsertion == portMAX_DELAY) {/* 如果排序值是portMAX_DELAY，则插入到链表末尾 */pxIterator = pxList->xListEnd.pxPrevious;} else {/* 否则，遍历链表以找到正确的插入位置 */for (pxIterator = (ListItem_t *)&(pxList->xListEnd);pxIterator->pxNext->xItemValue <= xValueOfInsertion;pxIterator = pxIterator->pxNext) {/* 遍历直到找到第一个xItemValue大于新节点值的节点 */}}/* 将新节点插入链表 */pxNewListItem->pxNext = pxIterator->pxNext;pxNewListItem->pxNext->pxPrevious = pxNewListItem;pxNewListItem->pxPrevious = pxIterator;pxIterator->pxNext = pxNewListItem;/* 记录新节点所在的链表 */pxNewListItem->pvContainer = (void *)pxList;/* 更新链表的节点计数 */(pxList->uxNumberOfItems)++;
}

1.5 将节点从链表删除

uxListRemove函数用于从的链表中移除一个指定的节点。首先获取节点所在的链表，然后更新链表中相邻节点的指针以移除目标节点。如果移除的节点是链表的索引节点，还会更新链表的索引。最后，将节点的容器指针设置为NULL以标记它不再属于任何链表，并减少链表的节点计数，函数返回链表中剩余的节点数量。

UBaseType_t uxListRemove(ListItem_t * const pxItemToRemove)
{/* 获取要删除节点所在的链表 */List_t * const pxList = (List_t *)pxItemToRemove->pvContainer;/* 从链表中移除指定节点 */pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;/* 如果删除的节点是链表索引节点，则更新索引 */if (pxList->pxIndex == pxItemToRemove) {pxList->pxIndex = pxItemToRemove->pxPrevious;}/* 将节点的容器指针设置为空，表示节点已从链表中移除 */pxItemToRemove->pvContainer = NULL;/* 更新链表的节点计数 */(pxList->uxNumberOfItems)--;/* 返回链表中剩余的节点数量 */return pxList->uxNumberOfItems;
}

1.6 节点带参宏小函数

FreeRTOS定义了一系列宏用于操作节点，包括设置和获取节点拥有者、排序值、链表头节点、链表结束标记、判断链表是否为空、获取链表长度以及获取链表第一个节点的拥有者等功能。

/* 设置节点的拥有者（通常是任务控制块TCB） */
#define listSET_LIST_ITEM_OWNER(pxListItem, pxOwner) \((pxListItem)->pvOwner = (void*)(pxOwner))/* 获取节点的拥有者 */
#define listGET_LIST_ITEM_OWNER(pxListItem) \((pxListItem)->pvOwner)/* 设置节点的排序辅助值 */
#define listSET_LIST_ITEM_VALUE(pxListItem, xValue) \((pxListItem)->xItemValue = (xValue))/* 获取节点的排序辅助值 */
#define listGET_LIST_ITEM_VALUE(pxListItem) \((pxListItem)->xItemValue)/* 获取链表头节点的排序辅助值 */
#define listGET_ITEM_VALUE_OF_HEAD_ENTRY(pxList) \(((pxList)->xListEnd).pxNext->xItemValue)/* 获取链表的头节点 */
#define listGET_HEAD_ENTRY(pxList) \(((pxList)->xListEnd).pxNext)/* 获取节点的下一个节点 */
#define listGET_NEXT(pxListItem) \((pxListItem)->pxNext)/* 获取链表的结束标记节点 */
#define listGET_END_MARKER(pxList) \((ListItem_t const*)(&((pxList)->xListEnd)))/* 判断链表是否为空 */
#define listLIST_IS_EMPTY(pxList) \((BaseType_t)(((pxList)->uxNumberOfItems) == (UBaseType_t)0))/* 获取链表的节点数 */
#define listCURRENT_LIST_LENGTH(pxList) \((pxList)->uxNumberOfItems)/* 获取链表第一个节点的拥有者（TCB） */
#define listGET_OWNER_OF_NEXT_ENTRY(pxTCB, pxList) \do { \List_t * const pxConstList = (pxList); \/* 将节点索引指向链表的第一个节点 */ \(pxConstList)->pxIndex = (pxConstList)->pxIndex->pxNext; \/* 确保索引不指向结束标记 */ \if ((void*)(pxConstList)->pxIndex == (void*)&((pxConstList)->xListEnd)) { \(pxConstList)->pxIndex = (pxConstList)->pxIndex->pxNext; \} \/* 获取节点的拥有者，即TCB */ \(pxTCB) = (pxConstList)->pxIndex->pvOwner; \} while (0)

2 链表操作实验

通过下面的代码定义和初始化一个链表及其节点，然后将这些节点按照升序插入到链表中。

  #include "stm32f4xx.h"
#include "list.h"/* 定义链表根节点 */
struct xLIST List_Test;/* 定义节点 */
struct xLIST_ITEM List_Item1;
struct xLIST_ITEM List_Item2;
struct xLIST_ITEM List_Item3;int main(void)
{/* 链表根节点初始化 */vListInitialise(&List_Test); /* 节点 1 初始化 */vListInitialiseItem(&List_Item1); List_Item1.xItemValue = 1;/* 节点 2 初始化 */vListInitialiseItem(&List_Item2);List_Item2.xItemValue = 2;/* 节点 3 初始化 */vListInitialiseItem(&List_Item3);List_Item3.xItemValue = 3;/* 将节点插入链表，按照升序排列 */ vListInsert(&List_Test, &List_Item2);vListInsert(&List_Test, &List_Item1);vListInsert(&List_Test, &List_Item3);for (;;){}
}

程序编译好之后，配置好硬件环境，点击调试按钮，然后全速运行，再然后把 List_Test、 List_Item1 、List_Item2 和 List_Item3 这四个全局变量添加到观察窗口，然后查看这几个数据结构中pxNext 和 pxPrevious 的值和我们理解的数据结构一致。

在运行过程中，可能会报如下的错误，根据报错位置，如果我们调用了list.h头文件，那还必须在调用FreeRTOS.h才行，否则编译时候会直接出现相应的预处理错误。

..\..\FreeRTOS\include\list.h(62): error: #35: #error directive: "FreeRTOS.h must be included before list.h"