部分内容参考野火的FreeRTOS相关开发资料，在此做一个学习记录总结。
FreeRTOS源码实现中存在很多链表相关操作，理解链表相关操作对掌握FreeRTOS实现原理至关重要。
FreeRTOS使用双向链表，与数组通过开辟一段连续内存存储数据不同，链表通过把离散的数据（标准C类型或者是用户自定义结构体）链接成一个表，通过对节点的插入和删除操作来实现对数据的存取。 双向链表是一个圈，没有头尾之分，但是为了方便节点的插入和删除操作，需要人为规定一个根节点（root节点）。 如上图所示，如果链表为空，这只有一个root节点，node_num为0，next和previous均指向自身。 为了有助于理解后面相关初始化以及插入删除操作，此处需要记住下面两点： 1）root_node->next指向链表的第一项node1（或自身，如果是空链表） 2）root_node->previous指向链表的最后一项noden（或自身，如果是空链表）
上面关键的一点是pxList->pxIndex指向根节点，这样后续插入删除操作便可以有了一个其实参考点。
节点初始化 这里的节点指的是除根节点外的有效挂载数据的节点，初始化就是告诉程序，该节点未挂到任何链表上，实现代码如下： void vListInitialiseItem(ListItem_t * const pxItem) { /* 初始化该节点所在的链表为空，表示该节点没有插入任何链表，没人能管得了我了！！ */ pxItem->pvContainer = NULL; } 插入节点至尾部 从前分析可知，链表的根节点，即xListEnd->pxPrevious指向的就是原链表的尾部节点，节点插入尾部时，就是要让新的节点跟在原来尾部节点之后，可以理解为在原尾部节点与根节点之间插入一个节点，代码实现如下： void vListInsertEnd(List_t * const pxList, ListItem_t * const pxNewListItem) { ListItem_t * const pxIndex = pxList->pxIndex; /* 链表索引节点，链表初始化后指向根节点*/ pxNewListItem->pxNext = pxIndex; /* 先插入尾部的节点的pxNext指向根节点 */ pxNewListItem->pxPrevious = pxIndex->pxPrevious; /* pxIndex->pxPrevious 是原来的链表尾部节点 */ pxIndex->pxPrevious->pxNext = pxNewListItem; pxIndex->pxPrevious = pxNewListItem; //pxIndex->pxNext 指向不变化 /* 记住该节点所在的链表 */ pxNewListItem->pvContainer = (void *)pxList; /* 链表节点计数器++ */ (pxList->uxNumberOfItems)++; } 升序插入节点 根据节点的xItemValue辅助值对接点进行排序，如果xItemValue相同，就根据插入顺序排列了。 插入后一定要记得更新链表中节点数据计数器pxList->uxNumberOfItems和新插入节点的pxNewListItem->pvContainer（否则节点就是未挂载在任何链表上）。 void vListInsert(List_t * const pxList, ListItem_t * const pxNewListItem) { /* * 记录辅助值比 pxNewListItem-> xItemValue 小的的列表项 ItemX ， * ItemX再往后的列表项 ItemX++ 的辅助值会大于或等于 pxNewListItem-> xItemValue * 插入的位置即 ItemX 之后 */ ListItem_t *pxIterator = NULL; /* 获取节点排序辅助值 */ const TickType_t xValueOfInsertion = pxNewListItem->xItemValue; /* 节点要插入到链表的尾部 */ 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; //或者 pxIterator->pxNext->pxPrevious = pxNewListItem pxNewListItem->pxPrevious = pxIterator; pxIterator->pxNext = pxNewListItem; /* 记住该节点所在的链表 */ pxNewListItem->pvContainer = (void *)pxList; /* 链表节点计数器++ */ (pxList->uxNumberOfItems)++; } 删除节点 删除节点后需要清除删除节点的pvContain指向，做好已删除节点原pxNext和pxPrevious指向节点的衔接工作，并且链表节点数目要相应自减。 其中特别注意的是，当删除最后一个节点时，需要调整节点索引指针，即让根节点指向自己，即链表初始化后为空的状态。 UBaseType_t uxListRemove(ListItem_t * const pxItemToRemove) { /* 获取节点所在列表 */ List_t * const pxList = pxItemToRemove->pvContainer; /* 类似离职后，做好前上级下级的交接工作 */ pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext; pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious; /* 在使用链表进行任务调度的过程中节点索引会变化， 如找到当前优先级最高的任务的TCB时就调用了listGET_OWNER_OF_NEXT_ENTRY 来不断遍历节点， 因此，我如果删除的节点刚好是最终pxIndex停留的节点，则需要重新给pxIndex进行赋值， 不管是待删除节点的上级还是下级都可以，通过其中一个，总能找到其他人 */ if( pxList->pxIndex == pxItemToRemove ) { pxList->pxIndex = pxItemToRemove->pxPrevious; // 或者 pxItemToRemove->pxNext，反正都能通过它们遍历其他节点 } /* 初始化节点所在的链表为空，表示节点还没有插入任何链表，没人能管得了我了！！ */ pxItemToRemove->pvContainer = NULL; /* 链表节点计数器--*/ (pxList->uxNumberOfItems)--; /* 返回链表中剩余节点的个数 */ return pxList->uxNumberOfItems; } 链表宏操作函数小结 /* 初始化节点的拥有者 */ #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) /* 获取下一个节点的Onwer，即 TCB */ #define listGET_OWNER_OF_NEXT_ENTRY(pxTCB, pxList) \ { \ List_t * const pxConstList = (pxList); \ /* Increment the index to the next item and return the item, */ \ /* ensuring we don't return the marker used at the end of the list */ \ (pxConstList)->pxIndex = (pxConstList)->pxIndex->pxNext; \ if((void *)(pxConstList)->pxIndex == (void *)&((pxConstList)->xListEnd)) \ { \ (pxConstList)->pxIndex = (pxConstList)->pxIndex->pxNext; \ } \ /* 获取节点的OWNER，即TCB */ \ (pxTCB) = (pxConstList)->pxIndex->pvOwner; \ } #define listGET_OWNER_OF_HEAD_ENTRY(pxList) ((&((pxList)->xListEnd))->pxNext->pvOwner)