FreeRTOS串列&串列項的原始碼解讀
第一次看串列與串列項的時候，感覺很像是鏈表，雖然我自己的鏈表也不太會，但是就是感覺很像，
在FreeRTOS中，串列與串列項使用得非常多，是FreeRTOS的一個資料結構，學習過資料結構的同學都知道，資料結構能使我們處理資料更加方便快速，能快速找到資料，在FreeRTOS中，這種串列與串列項更是必不可少的，能讓我們的系統跑起來更加流暢迅速，
言歸正傳，FreeRTOS中使用了大量的串列（List）與串列項（Listitem），在FreeRTOS調度器中，就是用到這些來跟著任務，了解任務的狀態，處于掛起、阻塞態、還是就緒態亦或者是運行態，這些資訊都會在各自任務的串列中得到，
看任務控制塊（tskTaskControlBlock）中的兩個串列項：
ListItem_t xStateListItem; /* <任務的狀態串列專案參考的串列表示該任務的狀態（就緒，已阻止，暫停），*/
ListItem_t xEventListItem; /* <用于從事件串列中參考任務，*/
一個是狀態的串列項，一個是事件串列項，他們在創建任務就會被初始化，串列項的初始化是根據實際需要來初始化的，下面會說，
FreeRTOS串列&串列項的結構體
既然知道串列與串列項的重要性，那么我們來解讀FreeRTOS中的list.c與list.h的原始碼吧，從頭檔案lsit.h開始，看到定義了一些結構體：
struct xLIST_ITEM
{
listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /* <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES設定為1，則設定為已知值，*/
configLIST_VOLATILE TickType_t xItemValue; /* <正在列出的值，在大多數情況下，這用于按降序對串列進行排序， */
struct xLIST_ITEM * configLIST_VOLATILE pxNext; /* <指向串列中下一個ListItem_t的指標， */
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /* <指向串列中前一個ListItem_t的指標， */
void * pvOwner; /* <指向包含串列專案的物件（通常是TCB）的指標，因此，包含串列專案的物件與串列專案本身之間存在雙向鏈接， */
void * configLIST_VOLATILE pvContainer; /* <指向此串列專案所在串列的指標（如果有）， */
listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE /* <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES設定為1，則設定為已知值，*/
};
typedef struct xLIST_ITEM ListItem_t; /* 由于某種原因，lint希望將其作為兩個單獨的定義， */
串列項結構體的一些注意的地方：
xItemValue 用于串列項的排序，類似1—2—3—4
pxNext 指向下一個串列項的指標
pxPrevious 指向上（前）一個串列項的指標
這兩個指標實作了類似雙向鏈表的功能
pvOwner 指向包含串列專案的物件（通常是任務控制塊TCB）的指標，因此，包含串列專案的物件與串列專案本身之間存在雙向鏈接，
pvContainer 記錄了該串列項屬于哪個串列，說白點就是這個兒子是誰生的，，，
同時定義了一個MINI的串列項的結構體，MINI串列項是刪減版的串列項，因為很多時候不需要完全版的串列項，就不用浪費那么多記憶體空間了，這或許就是FreeRTOS是輕量級作業系統的原因吧，能省一點是一點，MINI串列項：
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;
再定義了一個串列的結構體，可能看到這里，一些同學已經蒙了，串列與串列項是啥關系啊，按照杰杰的理解，是類似父子關系的，一個串列中，包含多個串列項，就像一個父親，生了好多孩子，而串列就是父親，串列項就是孩子，
typedef struct xLIST
{
listFIRST_LIST_INTEGRITY_CHECK_VALUE /* <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES設定為1，則設定為已知值，*/
configLIST_VOLATILE UBaseType_t uxNumberOfItems;
ListItem_t * configLIST_VOLATILE pxIndex; /* <用于遍歷串列， 指向由listGET_OWNER_OF_NEXT_ENTRY（）呼叫回傳的后一個串列項，*/
MiniListItem_t xListEnd; /* <List item包含最大可能的專案值，這意味著它始終在串列的末尾，因此用作標記，*/
listSECOND_LIST_INTEGRITY_CHECK_VALUE /* <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES設定為1，則設定為已知值，*/
} List_t;
串列的結構體中值得注意的是：
uxNumberOfItems 是用來記錄串列中串列項的數量的，就是記錄父親有多少個兒子，當然女兒也行~，
pxIndex 是索引編號，用來遍歷串列的，呼叫宏listGET_OWNER_OF_NEXT_ENTRY（）之后索引就會指向回傳當前串列項的下一個串列項，
xListEnd 指向的是最后一個串列項，并且這個串列項是MiniListItem屬性的，是一個迷你串列項，
串列的初始化
函式：
void vListInitialise( List_t * const pxList )
{
pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); /*lint The mini list structure is used as the list end to save RAM. This is checked and valid. */
pxList->xListEnd.xItemValue = https://www.cnblogs.com/iot-dev/p/portMAX_DELAY;
pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); /*lint The mini list structure is used as the list end to save RAM. This is checked and valid. */
pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );/*lint The mini list structure is used as the list end to save RAM. This is checked and valid. */
pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}
將串列的索引指向串列中的xListEnd，也就是末尾的串列項（迷你串列項）
串列項的xItemValue數值為portMAX_DELAY，也就是0xffffffffUL，如果在16位處理器中則為0xffff，
串列項的pxNext與pxPrevious這兩個指標都指向自己本身xListEnd，
初始化完成的時候串列項的數目為0個，因為還沒添加串列項嘛~，
串列項的初始化
函式：
void vListInitialiseItem( ListItem_t * const pxItem )
{
/* Make sure the list item is not recorded as being on a list. */
pxItem->pvContainer = NULL;
/* Write known values into the list item if
configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}
只需要讓串列項的pvContainer指標指向NULL即可，這樣子就使得串列項不屬于任何一個串列，因為串列項的初始化是要根據實際的情況來進行初始化的，
例如任務創建時用到的一些串列項初始化：
pxNewTCB->pcTaskName[ configMAX_TASK_NAME_LEN - 1 ] = '\0';
pxNewTCB->uxPriority = uxPriority;
pxNewTCB->uxBasePriority = uxPriority;
pxNewTCB->uxMutexesHeld = 0;
vListInitialiseItem( &( pxNewTCB->xStateListItem ) );
vListInitialiseItem( &( pxNewTCB->xEventListItem ) );
或者是在定時器相關的初始化中：
pxNewTimer->pcTimerName = pcTimerName;
pxNewTimer->xTimerPeriodInTicks = xTimerPeriodInTicks;
pxNewTimer->uxAutoReload = uxAutoReload;
pxNewTimer->pvTimerID = pvTimerID;
pxNewTimer->pxCallbackFunction = pxCallbackFunction;
vListInitialiseItem( &( pxNewTimer->xTimerListItem ) );
串列項的末尾插入
函式：
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 );
listGET_OWNER_OF_NEXT_ENTRY(). */
pxNewListItem->pxNext = pxIndex; // 1
pxNewListItem->pxPrevious = pxIndex->pxPrevious; // 2
/* Only used during decision coverage testing. */
mtCOVERAGE_TEST_DELAY();
pxIndex->pxPrevious->pxNext = pxNewListItem; // 3
pxIndex->pxPrevious = pxNewListItem; // 4
/* Remember which list the item is in. */
pxNewListItem->pvContainer = ( void * ) pxList;
( pxList->uxNumberOfItems )++;
}
傳入的引數：
-
pxList：串列項要插入的串列，
-
pxNewListItem：要插入的串列項是什么，
從末尾插入，那就要先知道哪里是頭咯，我們在串列中的成員pxIndex就是用來遍歷串列項的啊，那它指向的地方就是串列項的頭，那么既然FreeRTOS中的串列很像資料結構中的雙向鏈表，那么，我們可以把它看成一個環，是首尾相連的，那么函式中說的末尾，就是串列項頭的前一個，很顯然其結構圖應該是下圖這樣子的（初始化結束后pxIndex指向了xListEnd）：
為什么是這樣子的呢，一句句代碼來解釋：
一開始：
ListItem_t * const pxIndex = pxList->pxIndex;
保存了一開始的索引串列項（xListEnd）的指向，
pxNewListItem->pxNext = pxIndex; // 1
新串列項的下一個指向為索引串列項，也就是綠色的箭頭，
pxNewListItem->pxPrevious = pxIndex->pxPrevious; // 2
剛開始我們初始化完成的時候pxIndex->pxPrevious的指向為自己xListEnd，那么xNewListItem->pxPrevious的指向為xListEnd，如2紫色的箭頭，
pxIndex->pxPrevious->pxNext = pxNewListItem; // 3
索引串列項（xListEnd）的上一個串列項還是自己，那么自己的下一個串列項指向就是指向了pxNewListItem，
pxIndex->pxPrevious = pxNewListItem; // 4
這句就很容易理解啦，如圖的4橙色的箭頭，
插入完畢的時候標記一下新的串列項插入了哪個串列，并且將uxNumberOfItems進行加一，以表示多了一個串列項，
為什么原始碼要這樣子寫呢？因為這只是兩個串列項，一個串列含有多個串列項，那么這段代碼的通用性就很強了，無論原本串列中有多少個串列項，也無論pxIndex指向哪個串列項！
看看是不是按照原始碼中那樣插入呢？
串列項的插入
原始碼：
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 ) /*lint !e826 !e740 The mini list structure is used as the list end to save RAM. This is checked and valid. */
{
/* There is nothing to do here, just iterating to the wanted
insertion position. */
}
}
pxNewListItem->pxNext = pxIterator->pxNext;
pxNewListItem->pxNext->pxPrevious = pxNewListItem;
pxNewListItem->pxPrevious = pxIterator;
pxIterator->pxNext = pxNewListItem;
/* Remember which list the item is in. This allows fast removal of the
item later. */
pxNewListItem->pvContainer = ( void * ) pxList;
( pxList->uxNumberOfItems )++;
}
傳入的引數：
-
pxList：串列項要插入的串列，
-
pxNewListItem：要插入的串列項是什么，
pxList決定了插入哪個串列，pxNewListItem中的xItemValue值決定了串列項插入串列的位置，
ListItem_t *pxIterator;
const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
定義一個輔助的串列項pxIterator，用來迭代找出插入新串列項的位置，并且保存獲取要插入的串列項pxNewListItem的xItemValue，
如果打開了串列項完整性檢查，就要用戶實作configASSERT()，原始碼中有說明，
既然是要插入串列項，那么肯定是要知道串列項的位置了，如果新插入串列項的xItemValue是最大的話（portMAX_DELAY），就直接插入串列項的末尾，否則就需要比較串列中各個串列項的xItemValue的大小來進行排列，然后得出新串列項插入的位置，
for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )
上面原始碼就是實作比較的程序，
與上面的從串列項末尾插入的原始碼一樣，FreeRTOS的代碼通用性很強，邏輯思維也很強，
如果串列中串列項的數量為0，那么插入的串列項就是在初始化串列項的后面，如下圖所示：
程序分析：
新串列項的pxNext指向pxIterator->pxNext，也就是指向了xListEnd（pxIterator），
pxNewListItem->pxNext = pxIterator->pxNext;
而xListEnd（pxIterator）的pxPrevious指向則為pxNewListItem，
pxNewListItem->pxNext->pxPrevious = pxNewListItem;
新串列項的（pxPrevious）指標指向xListEnd（pxIterator）
pxIterator 的 pxNext 指向了新串列項
pxNewListItem->pxPrevious = pxIterator;
pxIterator->pxNext = pxNewListItem;
與從末尾插入串列項其實是一樣的，前提是當前串列中串列項的數目為0，
假如串列項中已經有了元素呢，程序又是不一樣的了，原來的串列是下圖這樣子的：
假設插入的串列項的xItemValue是2，而原有的串列項的xItemValue值是3，那么，按照原始碼，我們插入的串列項是在中間了，而pxIterator則是①號串列項，
插入后的效果：
分析一下插入的程序：
新的串列項的pxNext指向的是pxIterator->pxNext，也就是③號串列項，因為一開始pxIterator->pxNext=指向的就是③號串列項！！
pxNewListItem->pxNext = pxIterator->pxNext;
而pxNewListItem->pxNext 即③號串列項的指向上一個串列項指標（pxPrevious）的則指向新插入的串列項，也就是②號串列項了，
pxNewListItem->pxNext->pxPrevious = pxNewListItem;
新插入串列項的指向上一個串列項的指標pxNewListItem->pxPrevious指向了輔助串列項pxIterator，很顯然要連接起來嘛！
pxNewListItem->pxPrevious = pxIterator;
同理，pxIterator串列項的指向下一個串列項的指標則指向新插入的串列項了pxNewListItem，
pxIterator->pxNext = pxNewListItem;
而其他沒改變指向的地方不需改動，（圖中的兩條直線做的連接線是不需要改動的）
當插入完成的時候，記錄一下新插入的串列項屬于哪個串列，并且讓該串列下的串列項數目加一，
pxNewListItem->pvContainer = ( void * ) pxList;
( pxList->uxNumberOfItems )++;
洗掉串列項
原始碼：
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
/* The list item knows which list it is in. Obtain the list from the list
item. */
List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;
pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
/* Only used during decision coverage testing. */
mtCOVERAGE_TEST_DELAY();
/* Make sure the index is left pointing to a valid item. */
if( pxList->pxIndex == pxItemToRemove )
{
pxList->pxIndex = pxItemToRemove->pxPrevious;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
pxItemToRemove->pvContainer = NULL;
( pxList->uxNumberOfItems )--;
return pxList->uxNumberOfItems;
}
其實洗掉是很簡單的，不用想都知道，要洗掉串列項，那肯定要知道該串列項是屬于哪個串列吧，pvContainer就是記錄串列項是屬于哪個串列的，
洗掉就是把串列中的串列項從串列中去掉，其本質其實就是把他們的連接關系洗掉掉，然后讓洗掉的串列項的前后兩個串列連接起來就行了，假如是只有一個串列項，那么洗掉之后，串列就回到了初始化的狀態了，
pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
這兩句代碼就實作了將洗掉串列項的前后兩個串列項連接起來，
按照上面的講解可以理解這兩句簡單的代碼啦，
假如洗掉的串列項是當前索引的串列項，那么在洗掉之后，串列中的pxIndex就要指向洗掉串列項的上一個串列項了，
if( pxList->pxIndex == pxItemToRemove )
{
pxList->pxIndex = pxItemToRemove->pxPrevious;
}
當然還要把當前洗掉的串列項的pvContainer指向NULL，讓它不屬于任何一個串列，因為，洗掉的本質是洗掉的僅僅是串列項的連接關系，其記憶體是沒有釋放掉的，假如是動態記憶體分配的話，
并且要把當前串列中串列項的數目回傳一下，
至此，串列的原始碼基本講解完畢，
最后
大家還可以了解一下遍歷串列的宏，它在list.h檔案中：
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; \
} \
( pxTCB ) = ( pxConstList )->pxIndex->pvOwner; \
}
這是一個宏，用于串列的遍歷，回傳的是串列中串列項的pxOwner成員，每次呼叫這個宏（函式）的時候，其pxIndex索引會指向當前回傳串列項的下一個串列項，
關注我
更多資料歡迎關注“物聯網IoT開發”公眾號！
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/33395.html
標籤：嵌入式