FreeRTOS代碼剖析之5：鏈表管理list.c

鏈表是操作系統(tǒng)中常用的數(shù)據(jù)結(jié)構(gòu)，其結(jié)構(gòu)比較簡單，因此在剖析FreeRTOS的內(nèi)核時(shí)先從這里開始入手。

鏈表是由眾多鏈表節(jié)點(diǎn)組成的，在FreeRTOS中，鏈表節(jié)點(diǎn)有兩種定義，分別是xLIST_ITEM和xMINI_LIST_ITEM。這兩種有什么區(qū)別呢？可以說，xMINI_LIST_ITEM是xLIST_ITEM的濃縮版?？纯磧烧叩亩x。
struct xLIST_ITEM
{
configLIST_VOLATILE TickType_t xItemValue; /*< The value being listed. In most cases this is used to sort the list in descending order. */
struct xLIST_ITEM * configLIST_VOLATILE pxNext; /*< Pointer to the next ListItem_t in the list. */
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /*< Pointer to the previous ListItem_t in the list. */
void * pvOwner; /*< Pointer to the object (normally a TCB) that contains the list item. There is therefore a two way link between the object containing the list item and the list item itself. */
void * configLIST_VOLATILE pvContainer; /*< Pointer to the list in which this list item is placed (if any). */
};
typedef struct xLIST_ITEM ListItem_t; /* For some reason lint wants this as two separate definitions. */

struct xMINI_LIST_ITEM
{
configLIST_VOLATILE TickType_t xItemValue;
struct xLIST_ITEM * configLIST_VOLATILE pxNext;
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;

首先看看xLIST_ITEM里的成員。
第一個(gè)成員是xItemValue，根據(jù)注釋可以看出這個(gè)成員是存放鏈表節(jié)點(diǎn)的實(shí)際內(nèi)容，是一個(gè)16位或32位的無符號(hào)整數(shù)，具體位數(shù)在portmacro.h里定義，同時(shí)這個(gè)成員可以用configLIST_VOLATILE修飾，這是一個(gè)類似于volatile的關(guān)鍵字，用戶自己定義。

第二個(gè)成員pxNext和第三個(gè)成員pxPrevious是一個(gè)指針，分別指向當(dāng)前節(jié)點(diǎn)的下一個(gè)和上一個(gè)節(jié)點(diǎn)。

第四個(gè)成員是pvOwner，根據(jù)注釋說明，這是一個(gè)指向鏈表擁有者的指針，通常是指向TCB（Task Control Block）。

最后一個(gè)成員是pvContainer，根據(jù)注釋說明，這是一個(gè)指向擁有當(dāng)前節(jié)點(diǎn)的鏈表的指針。不過個(gè)人感覺這個(gè)成員挺別扭的。

而xMINI_LIST_ITEM則是只保留xLIST_ITEM中的前三個(gè)成員，其它的都去掉。

接下來要介紹的是鏈表組織結(jié)構(gòu)xLIST。根據(jù)注釋說明，這是給調(diào)度程序使用的鏈表定義。這個(gè)結(jié)構(gòu)有三個(gè)成員。第一個(gè)是uxNumberOfItems，這是一個(gè)long類型整數(shù)，用于記錄鏈表中的節(jié)點(diǎn)數(shù)目。第二個(gè)成員是pxIndex，是一個(gè)xLIST_ITEM類型的指針，用于遍歷鏈表中的所有節(jié)點(diǎn)。最后一個(gè)成員是xListEnd，是一個(gè)xMINI_LIST_ITEM類型的數(shù)據(jù)，用于記錄結(jié)束節(jié)點(diǎn)標(biāo)志。

那實(shí)際上整條鏈表是如何組織的呢？可以看一下鏈表初始化函數(shù)vListInitialise.
void vListInitialise( List_t * const pxList )
{
/* The list structure contains a list item which is used to mark the
end of the list. To initialise the list the list end is inserted
as the only list entry. */
pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 The mini list structure is used as the list end to save RAM. This is checked and valid. */

/* The list end value is the highest possible value in the list to
ensure it remains at the end of the list. */
pxList->xListEnd.xItemValue = portMAX_DELAY;

/* The list end next and previous pointers point to itself so we know
when the list is empty. */
pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 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 !e826 !e740 The mini list structure is used as the list end to save RAM. This is checked and valid. */

pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
}

從整段代碼中可以看出，初始化后的鏈表是一個(gè)循環(huán)鏈表，以xListEnd為尾。整個(gè)鏈表只有一個(gè)節(jié)點(diǎn)（就是xListEnd）。而頭節(jié)點(diǎn)則是xListEnd的下一個(gè)節(jié)點(diǎn)。另外，尾節(jié)點(diǎn)的節(jié)點(diǎn)值為portMAX_DELAY。

感覺再用代碼和文字說明會(huì)比較吃力，還是上圖描述比較好。可以說，整條鏈表是按以下方式進(jìn)行管理的。首先是初始化狀態(tài)，如下圖所示：

P指針為前一節(jié)點(diǎn)指針，N為下一節(jié)點(diǎn)指針。接下來是插入操作。插入節(jié)點(diǎn)有兩種類型，第一種是添加新節(jié)點(diǎn)到尾部。根據(jù)代碼描述，這種類型的插入結(jié)果如下圖所示。可以看出整條鏈表是一條循環(huán)鏈表，用鏈表中的xListEnd來指示鏈表結(jié)尾，并用來給出鏈表頭入口。