FreeRTOS列表&列表項的源碼解讀 第一次看列表與列表項的時候,感覺很像是鏈表,雖然我自己的鏈表也不太會,但是就是感覺很像。 在 中,列表與列表項使用得非常多,是 的一個數據結構,學習過數據結構的同學都知道,數據結構能使我們處理數據更加方便快速,能快速找到數據,在 中,這種列表與列表項更是必不可 ...
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 = 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開發”公眾號!