FreeRTOS列表和列表項

FreeRTOS內核調度使用了大量的列表（list）和列表項（listitem）數據結構。它的源碼中涉及到很多列表的操作，對于FreeRTOS來說，列表就是它最基礎的一部分，列表被用作FreeRTOS調度器使用，用于跟蹤任務，處于就緒，掛起，延時的任務都會被掛接到各自的列表中，用戶程序如果有需要，也可以使用列表，其中就連FreeRTOS的任務調度其實核心也涉及到列表。

? FreeRTOS列表使用指針指向列表項。一個列表（list）下面可能有很多個列表項（list item），每個列表項都有一個指針指向列表。如圖所示

列表和列表項

列表項有兩種形式，全功能版的列表項xLIST_ITEM和迷你版的列表項xMINI_LIST_ITEM。我們來看一下它們具體的定義，先看全功能版。

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;                                     /*指向一個任務TCB*/void * configLIST_VOLATILE pvContainer;             /*指向包含該列表項的列表 */listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE          /*用于檢測列表項數據是否完整*/
};
typedef struct xLIST_ITEM ListItem_t;

? ?宏listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE和listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE用于檢查列表項數據是否完整，在projdefs.h中，如果將宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES設置為1，則使能列表項數據完整性檢查，則宏listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE和listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE會被兩個已知的數值代替。

? ? ? xItemValue是列表項值，通常是一個被跟蹤的任務優先級或是一個調度事件的計數器值。如果任務因為等待從隊列取數據而進入阻塞狀態，則任務的事件列表項的列表項值保存任務優先級有關信息，狀態列表項的列表項值保存阻塞時間有關的信息。這個變量被configLIST_VOLATILE修飾，configLIST_VOLATILE被映射成C語言關鍵字volatile，表明這個變量是“易變的”，告訴編譯器不得對這個變量進行代碼優化，因為列表項的成員可能會在中斷服務程序中被更新。

? pxNext和pxPrevious是列表項類型指針，用來指向列表中下一個和上一個列表項，通過這兩個指針，列表項之間可以形成類似雙向鏈表結構。

? ? ? 指針pvOwner通常指向一個任務TCB。

? ? ? 指針pvContainer指向包含該列表項的列表。

? ? ? 迷你版的列表項xMINI_LIST_ITEM是全功能版列表項xLIST_ITEM的一個子集，定義如下所示：
?

struct xMINI_LIST_ITEM
{listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE           /*用于檢測列表項數據是否完整*/configLIST_VOLATILE TickType_t xItemValue;struct xLIST_ITEM * configLIST_VOLATILE pxNext;struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;

??? 既然有了全功能版的列表項，為什么還要聲明迷你版的列表項呢？這是因為列表結構體需要一個列表項成員，但又不需要列表項中的所有字段，所以才有了迷你版列表項。迷你列表項起到的主要作用就是標識列表的末尾，所以它的值也設置成了最大值，列表結構體定義為：

typedef struct xLIST
{listFIRST_LIST_INTEGRITY_CHECK_VALUE                        /*用于檢測列表項數據是否完整*/configLIST_VOLATILE UBaseType_t uxNumberOfItems;ListItem_t * configLIST_VOLATILE pxIndex;                   /*用于遍歷列表*/MiniListItem_t xListEnd;                                    /*列表項*/listSECOND_LIST_INTEGRITY_CHECK_VALUE                       /*用于檢測列表項數據是否完整*/
}List_t;

和列表項定義相同，宏listFIRST_LIST_INTEGRITY_CHECK_VALUE和listSECOND_LIST_INTEGRITY_CHECK_VALUE用于檢查列表項數據是否完整，在projdefs.h中，如果將宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES設置為1，則使能列表項數據完整性檢查，則宏listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE和listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE會被兩個已知的數值代替。

? ? ? uxNumberOfItems表示該列表中掛接的列表項數目，0表示列表為空。

? ? ? 列表項類型指針用于遍歷列表，列表初始化后，這個指針指向&xListEnd。通過宏listGET_OWNER_OF_NEXT_ENTRY()來獲取列表中的下一個列表項。

? ? ? 列表項xListEnd用于標記列表結束。xListEnd.xItemValue被初始化為一個常數，其值與硬件架構相關，為0xFFFF（16位架構）或者0xFFFFFFFF（32位架構）。
?

關于列表的一些操作

初始化列表

列表結構體中包含一個列表項成員，主要用于標記列表結束。初始化列表就是把這個列表項插入到列表中。

void vListInitialise( List_t * const pxList )
{/*列表索引指向列表項*/pxList->pxIndex = ( ListItem_t * )&( pxList->xListEnd );                  /* 設置為最大可能值 */pxList->xListEnd.xItemValue =portMAX_DELAY;/* 列表項xListEnd的pxNext和pxPrevious指針指向了它自己 */pxList->xListEnd.pxNext = (ListItem_t * ) &( pxList->xListEnd );pxList->xListEnd.pxPrevious= ( ListItem_t * ) &( pxList->xListEnd );pxList->uxNumberOfItems = ( UBaseType_t) 0U;/* 設置為已知值，用于檢測列表數據是否完整*/listSET_LIST_INTEGRITY_CHECK_1_VALUE(pxList );listSET_LIST_INTEGRITY_CHECK_2_VALUE(pxList );
}

如果宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES設置為1，則使能列表項數據完整性檢查，則宏listSET_LIST_INTEGRITY_CHECK_1_VALUE()和listSET_LIST_INTEGRITY_CHECK_2_VALUE被一個已知值代替，默認為0x5a5a（16位架構）或者0x5a5a5a5a（32位架構）。

? ? ? 假設禁止列表數據完整性檢查，初始化后的列表如圖1-2所示，uxNumberOfItems被初始化為0，xListEnd.xItemValue初始化為0xffffffff，pxIndex、xListEnd.pxNext和xListEnd.pxPrevious初始化為指向列表項xListEnd。
?

?初始化列表項

列表項的初始化很簡答，只需要聲明該列表項不屬于任何一個列表就可以了。

void vListInitialiseItem( ListItem_t * const pxItem )
{pxItem->pvContainer = NULL;/*設置為已知值，用于檢測列表項數據是否完整*/listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem );listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem );
}

如果宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES設置為1，則使能列表項數據完整性檢查，則宏listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE和listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE會被兩個已知的數值代替，默認為0x5a5a（16位架構）或者0x5a5a5a5a（32位架構）。

? ? ? 假設禁止列表項數據完整性檢查，初始化后的列表項如圖1-3所示。僅是將指針pvContainer設置為空指針，該指針用于指向包含該列表項的列表，這里設置為NULL表示這個列表項不屬于任何列表。
?

列表插入列表項

每個列表項對象都有一個列表項值（xItemValue），通常是一個被跟蹤的任務優先級或是一個調度事件的計數器值。調用API函數vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem)可以將pxNewListItem指向的列表項插入到pxList指向的列表中，列表項在列表的位置由pxNewListItem->xItemValue決定，按照升序排列。

void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t *pxIterator;
const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;/* 檢查列表和列表項數據的完整性，僅當configASSERT()定義時有效。*/listTEST_LIST_INTEGRITY( pxList );listTEST_LIST_ITEM_INTEGRITY(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 )++;
}

?列表項末尾插入

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t* const pxIndex = pxList->pxIndex;/*檢查列表和列表項數據的完整性，僅當configASSERT()定義時有效。*/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->pvContainer = ( void* ) pxList;( pxList->uxNumberOfItems )++;
}

Tips: 這個函數是最容易造成誤解的一個函數，字面理解，在我開始學的時候我以為就是插入到最后一個迷你列表項的前面，所謂末尾插入肯定是最后一項嘛，閱讀源碼之后，其實不然，因為列表中有一項成員?

ListItem_t * configLIST_VOLATILE pxIndex;

該成員主要作用就是用來遍歷列表的。閱讀源碼發現它是插入在pxIndex所指的列表項的前面。這里體現了FreeRTOS的哲學理念，“公平”，如果pxIndex，指向的是當前的索引的列表項表示正在使用，這時比如順序是1->2->3，現在pxIndex指向2，要插入4，這時你4肯定是要最后遍歷訪問的，意味著就是訪問順序應該是2->3->1->4，所以它要插入在2前面，我的方法是記住一個口訣，末尾插入就是插入pxIndex所指列表項的前一項的后面，可能聽著有點別扭（不就是所指列表項的前面嘛🤣 ，細細體會，有公平的哲學思想）

重點

重點：一開始學習的時候，一直不明白這個pxIndex有什么用，因為我在有關列表的list.c中的API函數中根本沒發現有改變它的代碼，以為它一直是初始化的值，就是一直指向迷你列表項，其實不然，作為一名程序員，一切從源碼中得到答案。

搜索代碼之后發現，中間對pxIndex賦值的地方只有listGET_OWNER_OF_NEXT_ENTRY這個接口（list.h中的一個有參宏）

?每調用一次listGET_OWNER_OF_NEXT_ENTRY，列表的pxIndex會指向下一個列表項。
而調用listGET_OWNER_OF_NEXT_ENTRY，主要是

FreeRTOS的列表和列表項采用了一種統一的列表管理，不像我以前學的數據結構中的鏈表操作一樣，其中的節點都是具體的結構體的內容，所以是針對具體的一類結構體，比如struct people，這樣導致的后果就是所有有關鏈表操作的內容都是針對這類結構體，如果稍微改成struct dog，這樣就需要全部重寫鏈表的所有操作了。FreeRTOS采用一種方法，寫出了通用的鏈表操作，讓我不得不感嘆這代碼確實是寫的好！🤣?