重要數據

節點的命名都以_ITEM后綴進行，鏈表取消了后綴，直接LIST

普通的節點數據類型

/* 節點結構體定義 */

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; ?/* 節點數據類型重定義 */

迷你節點數據類型

/* mini節點結構體定義，作為雙向鏈表的結尾

? ?因為雙向鏈表是首尾相連的，頭即是尾，尾即是頭 */

struct xMINI_LIST_ITEM

{

? ? TickType_t xItemValue; ? ? ? ? ? ? ? ? ? ? ?/* 輔助值，用于幫助節點做升序排列 */

? ? struct xLIST_ITEM * ?pxNext; ? ? ? ? ? ? ? ?/* 指向鏈表下一個節點 */

? ? struct xLIST_ITEM * ?pxPrevious; ? ? ? ? ? ?/* 指向鏈表前一個節點 */

};

typedef struct xMINI_LIST_ITEM MiniListItem_t; ?/* 最小節點數據類型重定義 */

鏈表數據類型

/* 鏈表結構體定義 */

typedef struct xLIST

{

? ? UBaseType_t uxNumberOfItems; ? ?/* 鏈表節點計數器 */

? ? ListItem_t * ?pxIndex; ? ? ? ? ?/* 鏈表節點索引指針 */

? ? MiniListItem_t xListEnd; ? ? ? ?/* 鏈表最后一個節點 */

} List_t;

函數

1. 鏈表插入函數? vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )

升序插入函數

新的節點項插入后，需要解開原來的鏈接，建立新的鏈接：

語句1：向后看：新的節點項指向插入出（后面的）

pxNewListItem->pxNext = pxIterator->pxNext; // 插入，建立新的鏈接；

語句2：向前看：插入出（后面的）指向新的節點項

pxNewListItem->pxNext->pxPrevious = pxNewListItem; // 插入，建立新的鏈接；

語句3：向前看：新的節點項的前面為插入出（前面的）

pxNewListItem->pxPrevious = pxIterator; // 插入，建立新的鏈接；

語句4：向后看：插入出（前面的）指向新的節點項

pxIterator->pxNext = pxNewListItem;// 插入，建立新的鏈接；

/* 將節點按照升序排列插入到鏈表 */
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
?? ?ListItem_t *pxIterator;
?? ?
?? ?/* 獲取節點的排序輔助值 */
?? ?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;
?? ?pxNewListItem->pxPrevious = pxIterator;
?? ?pxIterator->pxNext = pxNewListItem;

?? ?/* 記住該節點所在的鏈表 */
?? ?pxNewListItem->pvContainer = ( void * ) pxList;

?? ?/* 鏈表節點計數器++ */
?? ?( pxList->uxNumberOfItems )++;
}

2. 鏈表尾部插入函數? void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )

根節點既是頭部也是尾部，當Item4插入，調用vListInsertEnd，插入如圖所示位置，尾部插入

/* 將節點插入到鏈表的尾部 */

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )

{

? ? ListItem_t * const pxIndex = pxList->pxIndex;

? ? pxNewListItem->pxNext = pxIndex;

? ? pxNewListItem->pxPrevious = pxIndex->pxPrevious;

? ? pxIndex->pxPrevious->pxNext = pxNewListItem;

? ? pxIndex->pxPrevious = pxNewListItem;

? ? /* 記住該節點所在的鏈表 */

? ? pxNewListItem->pvContainer = ( void * ) pxList;

? ? /* 鏈表節點計數器++ */

? ? ( pxList->uxNumberOfItems )++;

}

3. 鏈表刪除節點函數?

刪除節點，解開原來的鏈接，建立新的鏈接：

函數中為何會修改：pxList->pxIndex = pxItemToRemove->pxPrevious，

上面的建立函數一直沒有修改鏈表中根節點的索引值的，索引值一直是指向根節點內部的xListEnd（根節點初始化的時候設置的。），既然建立的時候沒有改變，為何刪除的時候改變？

《我的理解是保護用的，其實用處不大》

/* 將節點從鏈表中刪除 */

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;

? ? /* Make sure the index is left pointing to a valid item. */

? ? if( pxList->pxIndex == pxItemToRemove )

? ? {

? ? ? ? pxList->pxIndex = pxItemToRemove->pxPrevious;

? ? }

? ? /* 初始化該節點所在的鏈表為空，表示節點還沒有插入任何鏈表 */

? ? pxItemToRemove->pvContainer = NULL;

? ?

? ? /* 鏈表節點計數器-- */

? ? ( pxList->uxNumberOfItems )--;

? ? /* 返回鏈表中剩余節點的個數 */

? ? return pxList->uxNumberOfItems;

}