【連載】從單片機到操作系統⑤——FreeRTOS列表&列表項的源碼解讀

來自專欄創客飛夢空間4 人贊了文章

實現，傑傑感覺這兒的排版不算好看，大家可以去我的博客看文章。

傑傑_MCU的博客 - CSDN博客

FreeRTOS列表&列表項的源碼解讀

第一次看列表與列表項的時候，感覺很像是鏈表，雖然我自己的鏈表也不太會，但是就是感覺很像。

在FreeRTOS中，列表與列表項使用得非常多，是FreeRTOS的一個數據結構，學習過數據結構的同學都知道，數據結構能使我們處理數據更加方便快速，能快速找到數據，在FreeRTOS中，這種列表與列表項更是必不可少的，能讓我們的系統跑起來更加流暢迅速。

言歸正傳，FreeRTOS中使用了大量的列表（List）與列表項（Listitem），在FreeRTOS調度器中，就是用到這些來跟著任務，了解任務的狀態，處於掛起、阻塞態、還是就緒態亦或者是運行態。這些信息都會在各自任務的列表中得到。

看任務控制塊（tskTaskControlBlock）中的兩個列表項：

1ListItem_t xStateListItem; / * <任務的狀態列表項目引用的列表表示該任務的狀態（就緒，已阻止，暫停）。*/2ListItem_t xEventListItem; / * <用於從事件列表中引用任務。*/

一個是狀態的列表項，一個是事件列表項。他們在創建任務就會被初始化，列表項的初始化是根據實際需要來初始化的，下面會說。

FreeRTOS列表&列表項的結構體

既然知道列表與列表項的重要性，那麼我們來解讀FreeRTOS中的list.c與list.h的源碼吧。從頭文件lsit.h開始，看到定義了一些結構體：

1struct xLIST_ITEM 2{ 3listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE / * <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES設置為1，則設置為已知值。* / 4configLIST_VOLATILE TickType_t xItemValue; / * <正在列出的值。在大多數情況下，這用於按降序對列表進行排序。 * / 5struct xLIST_ITEM * configLIST_VOLATILE pxNext; / * <指向列表中下一個ListItem_t的指針。 * / 6struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; / * <指向列表中前一個ListItem_t的指針。 * / 7void * pvOwner; / * <指向包含列表項目的對象（通常是TCB）的指針。因此，包含列表項目的對象與列表項目本身之間存在雙向鏈接。 * / 8void * configLIST_VOLATILE pvContainer; / * <指向此列表項目所在列表的指針（如果有）。 * / 9listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE / * <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES設置為1，則設置為已知值。* /10};11typedef struct xLIST_ITEM ListItem_t; / *由於某種原因，lint希望將其作為兩個單獨的定義。 * /

列表項結構體的一些注意的地方：

xItemValue 用於列表項的排序，類似1—2—3—4

pxNext 指向下一個列表項的指針

pxPrevious 指向上（前）一個列表項的指針

這兩個指針實現了類似雙向鏈表的功能

pvOwner 指向包含列表項目的對象（通常是任務控制塊TCB）的指針。因此，包含列表項目的對象與列表項目本身之間存在雙向鏈接。

pvContainer 記錄了該列表項屬於哪個列表，說白點就是這個兒子是誰生的。。。

同時定義了一個MINI的列表項的結構體，MINI列表項是刪減版的列表項，因為很多時候不需要完全版的列表項。就不用浪費那麼多內存空間了，這或許就是FreeRTOS是輕量級操作系統的原因吧，能省一點是一點。MINI列表項：

1struct xMINI_LIST_ITEM2{3 listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */4 configLIST_VOLATILE TickType_t xItemValue;5 struct xLIST_ITEM * configLIST_VOLATILE pxNext;6 struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;7};8typedef struct xMINI_LIST_ITEM MiniListItem_t;

再定義了一個列表的結構體，可能看到這裡，一些同學已經蒙了，列表與列表項是啥關係啊，按照傑傑的理解，是類似父子關係的，一個列表中，包含多個列表項，就像一個父親，生了好多孩子，而列表就是父親，列表項就是孩子。

1typedef struct xLIST2{3listFIRST_LIST_INTEGRITY_CHECK_VALUE / * <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES設置為1，則設置為已知值。* /4configLIST_VOLATILE UBaseType_t uxNumberOfItems;5ListItem_t * configLIST_VOLATILE pxIndex; / * <用於遍歷列表。 指向由listGET_OWNER_OF_NEXT_ENTRY（）調用返回的後一個列表項。*/6MiniListItem_t xListEnd; / * <List item包含最大可能的項目值，這意味著它始終在列表的末尾，因此用作標記。*/7listSECOND_LIST_INTEGRITY_CHECK_VALUE / * <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES設置為1，則設置為已知值。* /8} List_t;

列表的結構體中值得注意的是：

uxNumberOfItems 是用來記錄列表中列表項的數量的，就是記錄父親有多少個兒子，當然女兒也行~。

pxIndex 是索引編號，用來遍歷列表的，調用宏listGET_OWNER_OF_NEXT_ENTRY（）之後索引就會指向返回當前列表項的下一個列表項。

xListEnd 指向的是最後一個列表項，並且這個列表項是MiniListItem屬性的，是一個迷你列表項。

列表的初始化

函數：

1void vListInitialise( List_t * const pxList ) 2{ 3 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. */ 4 pxList->xListEnd.xItemValue = portMAX_DELAY; 5 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. */ 6 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. */ 7 pxList->uxNumberOfItems = ( UBaseType_t ) 0U; 8 listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList ); 9 listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );10}

將列表的索引指向列表中的xListEnd，也就是末尾的列表項（迷你列表項）

列表項的xItemValue數值為portMAX_DELAY，也就是0xffffffffUL，如果在16位處理器中則為0xffff。

列表項的pxNext與pxPrevious這兩個指針都指向自己本身xListEnd。

初始化完成的時候列表項的數目為0個。因為還沒添加列表項嘛~。

列表項的初始化

函數：

1void vListInitialiseItem( ListItem_t * const pxItem )2{3 /* Make sure the list item is not recorded as being on a list. */4 pxItem->pvContainer = NULL;5 /* Write known values into the list item if6 configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */7 listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );8 listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );9}

只需要讓列表項的pvContainer指針指向NULL即可，這樣子就使得列表項不屬於任何一個列表，因為列表項的初始化是要根據實際的情況來進行初始化的。

例如任務創建時用到的一些列表項初始化：

1pxNewTCB->pcTaskName[ configMAX_TASK_NAME_LEN - 1 ] = ;2pxNewTCB->uxPriority = uxPriority;3pxNewTCB->uxBasePriority = uxPriority;4pxNewTCB->uxMutexesHeld = 0;56vListInitialiseItem( &( pxNewTCB->xStateListItem ) );7vListInitialiseItem( &( pxNewTCB->xEventListItem ) );

又或者是在定時器相關的初始化中：

1pxNewTimer->pcTimerName = pcTimerName;2pxNewTimer->xTimerPeriodInTicks = xTimerPeriodInTicks;3pxNewTimer->uxAutoReload = uxAutoReload;4pxNewTimer->pvTimerID = pvTimerID;5pxNewTimer->pxCallbackFunction = pxCallbackFunction;67vListInitialiseItem( &( pxNewTimer->xTimerListItem ) );

列表項的末尾插入

函數：

1void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem ) 2{ 3 ListItem_t * const pxIndex = pxList->pxIndex; 4 listTEST_LIST_INTEGRITY( pxList ); 5 listTEST_LIST_ITEM_INTEGRITY( pxNewListItem ); 6 listGET_OWNER_OF_NEXT_ENTRY(). */ 7 pxNewListItem->pxNext = pxIndex; // 1 8 pxNewListItem->pxPrevious = pxIndex->pxPrevious; // 2 9 /* Only used during decision coverage testing. */10 mtCOVERAGE_TEST_DELAY();11 pxIndex->pxPrevious->pxNext = pxNewListItem; // 3 12 pxIndex->pxPrevious = pxNewListItem; // 413 /* Remember which list the item is in. */14 pxNewListItem->pvContainer = ( void * ) pxList;15 ( pxList->uxNumberOfItems )++;16}

傳入的參數：

pxList：列表項要插入的列表。

pxNewListItem：要插入的列表項是什麼。

從末尾插入，那就要先知道哪裡是頭咯，我們在列表中的成員pxIndex就是用來遍歷列表項的啊，那它指向的地方就是列表項的頭，那麼既然FreeRTOS中的列表很像數據結構中的雙向鏈表，那麼，我們可以把它看成一個環，是首尾相連的，那麼函數中說的末尾，就是列表項頭的前一個，很顯然其結構圖應該是下圖這樣子的（初始化結束後pxIndex指向了xListEnd）：

為什麼是這樣子的呢，一句句代碼來解釋：

一開始：

1ListItem_t * const pxIndex = pxList->pxIndex;

保存了一開始的索引列表項（xListEnd）的指向。

1pxNewListItem->pxNext = pxIndex; // 1

新列表項的下一個指向為索引列表項，也就是綠色的箭頭。

1pxNewListItem->pxPrevious = pxIndex->pxPrevious; // 2

剛開始我們初始化完成的時候pxIndex->pxPrevious的指向為自己xListEnd，那麼xNewListItem->pxPrevious的指向為xListEnd。如2紫色的箭頭。

1pxIndex->pxPrevious->pxNext = pxNewListItem; // 3

索引列表項（xListEnd）的上一個列表項還是自己，那麼自己的下一個列表項指向就是指向了pxNewListItem。

1pxIndex->pxPrevious = pxNewListItem; // 4

這句就很容易理解啦。如圖的4橙色的箭頭。

插入完畢的時候標記一下新的列表項插入了哪個列表，並且將uxNumberOfItems進行加一，以表示多了一個列表項。

為什麼源碼要這樣子寫呢？因為這只是兩個列表項，一個列表含有多個列表項，那麼這段代碼的通用性就很強了。無論原本列表中有多少個列表項，也無論pxIndex指向哪個列表項！

看看是不是按照源碼中那樣插入呢？

列表項的插入

源碼：

1void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem ) 2{ 3ListItem_t *pxIterator; 4const TickType_t xValueOfInsertion = pxNewListItem->xItemValue; 5 listTEST_LIST_INTEGRITY( pxList ); 6 listTEST_LIST_ITEM_INTEGRITY( pxNewListItem ); 7 if( xValueOfInsertion == portMAX_DELAY ) 8 { 9 pxIterator = pxList->xListEnd.pxPrevious;10 }11 else12 {13 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. */14 {15 /* There is nothing to do here, just iterating to the wanted16 insertion position. */17 }18 }19 pxNewListItem->pxNext = pxIterator->pxNext;20 pxNewListItem->pxNext->pxPrevious = pxNewListItem;21 pxNewListItem->pxPrevious = pxIterator;22 pxIterator->pxNext = pxNewListItem;23 /* Remember which list the item is in. This allows fast removal of the24 item later. */25 pxNewListItem->pvContainer = ( void * ) pxList;26 ( pxList->uxNumberOfItems )++;27}

傳入的參數：

pxList：列表項要插入的列表。

pxNewListItem：要插入的列表項是什麼。

pxList決定了插入哪個列表，pxNewListItem中的xItemValue值決定了列表項插入列表的位置。

1ListItem_t *pxIterator; 2const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;

定義一個輔助的列表項pxIterator，用來迭代找出插入新列表項的位置，並且保存獲取要插入的列表項pxNewListItem的xItemValue。

如果打開了列表項完整性檢查，就要用戶實現configASSERT()，源碼中有說明。

既然是要插入列表項，那麼肯定是要知道列表項的位置了，如果新插入列表項的xItemValue是最大的話（portMAX_DELAY），就直接插入列表項的末尾。否則就需要比較列表中各個列表項的xItemValue的大小來進行排列。然後得出新列表項插入的位置。

1for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )

上面源碼就是實現比較的過程。

與上面的從列表項末尾插入的源碼一樣，FreeRTOS的代碼通用性很強，邏輯思維也很強。

如果列表中列表項的數量為0，那麼插入的列表項就是在初始化列表項的後面。如下圖所示：

過程分析：

新列表項的pxNext指向pxIterator->pxNext，也就是指向了xListEnd（pxIterator）。

1pxNewListItem->pxNext = pxIterator->pxNext;

而xListEnd（pxIterator）的pxPrevious指向則為pxNewListItem。

1 pxNewListItem->pxNext->pxPrevious = pxNewListItem;

新列表項的（pxPrevious）指針指向xListEnd（pxIterator）

pxIterator 的 pxNext 指向了新列表項

1pxNewListItem->pxPrevious = pxIterator;2pxIterator->pxNext = pxNewListItem;

與從末尾插入列表項其實是一樣的，前提是當前列表中列表項的數目為0。

假如列表項中已經有了元素呢，過程又是不一樣的了。原來的列表是下圖這樣子的：

假設插入的列表項的xItemValue是2，而原有的列表項的xItemValue值是3，那麼，按照源碼，我們插入的列表項是在中間了。而pxIterator則是①號列表項。

插入後的效果：

分析一下插入的過程：

新的列表項的pxNext指向的是pxIterator->pxNext，也就是③號列表項。因為一開始pxIterator->pxNext=指向的就是③號列表項！！

1pxNewListItem->pxNext = pxIterator->pxNext;

而pxNewListItem->pxNext 即③號列表項的指向上一個列表項指針（pxPrevious）的則指向新插入的列表項，也就是②號列表項了。

1pxNewListItem->pxNext->pxPrevious = pxNewListItem;

新插入列表項的指向上一個列表項的指針pxNewListItem->pxPrevious指向了輔助列表項pxIterator。很顯然要連接起來嘛！

1pxNewListItem->pxPrevious = pxIterator;

同理，pxIterator列表項的指向下一個列表項的指針則指向新插入的列表項了pxNewListItem。

1pxIterator->pxNext = pxNewListItem;

而其他沒改變指向的地方不需改動。（圖中的兩條直線做的連接線是不需要改動的）

當插入完成的時候，記錄一下新插入的列表項屬於哪個列表。並且讓該列表下的列表項數目加一。

1pxNewListItem->pvContainer = ( void * ) pxList;2 ( pxList->uxNumberOfItems )++;

刪除列表項

源碼：

1UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove ) 2{ 3/* The list item knows which list it is in. Obtain the list from the list 4item. */ 5List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer; 6 pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious; 7 pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext; 8 /* Only used during decision coverage testing. */ 9 mtCOVERAGE_TEST_DELAY();10 /* Make sure the index is left pointing to a valid item. */11 if( pxList->pxIndex == pxItemToRemove )12 {13 pxList->pxIndex = pxItemToRemove->pxPrevious;14 }15 else16 {17 mtCOVERAGE_TEST_MARKER();18 }19 pxItemToRemove->pvContainer = NULL;20 ( pxList->uxNumberOfItems )--;21 return pxList->uxNumberOfItems;22}

其實刪除是很簡單的，不用想都知道，要刪除列表項，那肯定要知道該列表項是屬於哪個列表吧，pvContainer就是記錄列表項是屬於哪個列表的。

刪除就是把列表中的列表項從列表中去掉，其本質其實就是把他們的連接關係刪除掉，然後讓刪除的列表項的前後兩個列表連接起來就行了，假如是只有一個列表項，那麼刪除之後，列表就回到了初始化的狀態了。

1 pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;2 pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

這兩句代碼就實現了將刪除列表項的前後兩個列表項連接起來。

按照上面的講解可以理解這兩句簡單的代碼啦。

假如刪除的列表項是當前索引的列表項，那麼在刪除之後，列表中的pxIndex就要指向刪除列表項的上一個列表項了。

1if( pxList->pxIndex == pxItemToRemove )2 {3 pxList->pxIndex = pxItemToRemove->pxPrevious;4 }

當然還要把當前刪除的列表項的pvContainer指向NULL，讓它不屬於任何一個列表，因為，刪除的本質是刪除的僅僅是列表項的連接關係，其內存是沒有釋放掉的，假如是動態內存分配的話。

並且要把當前列表中列表項的數目返回一下。

至此，列表的源碼基本講解完畢。

最後

大家還可以了解一下遍歷列表的宏，它在list.h文件中：

1define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList ) 2{ 3List_t * const pxConstList = ( pxList ); 4 /* Increment the index to the next item and return the item, ensuring */ 5 /* we dont return the marker used at the end of the list. */ 6 ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; 7 if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) ) 8 { 9 ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; 10 } 11 ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner; 12}

這是一個宏，用於列表的遍歷，返回的是列表中列表項的pxOwner成員，每次調用這個宏（函數）的時候，其pxIndex索引會指向當前返回列表項的下一個列表項。

本文為傑傑原創，轉載請說明出處

往期精彩回顧

STM32進階之串口環形緩衝區實現

【連載】從單片機到操作系統④——FreeRTOS創建任務&開啟調度詳解

【連載】從單片機到操作系統③——走進FreeRTOS

openmv學習之旅②之色塊追蹤演算法的改善

歡迎大家一起來討論操作系統的知識

我們的群號是：783234154

傑傑：

創客飛夢空間是開源公眾號

歡迎大家分享出去

也歡迎大家投稿