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

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

鏈表是由眾多鏈表節(jié)點組成的，在FreeRTOS中，鏈表節(jié)點有兩種定義，分別是xLIST_ITEM和xMINI_LIST_ITEM。這兩種有什么區(qū)別呢？可以說，xMINI_LIST_ITEM是xLIST_ITEM的濃縮版。看看兩者的定義。
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里的成員。
第一個成員是xItemValue，根據(jù)注釋可以看出這個成員是存放鏈表節(jié)點的實際內(nèi)容，是一個16位或32位的無符號整數(shù)，具體位數(shù)在portmacro.h里定義，同時這個成員可以用configLIST_VOLATILE修飾，這是一個類似于volatile的關鍵字，用戶自己定義。

第二個成員pxNext和第三個成員pxPrevious是一個指針，分別指向當前節(jié)點的下一個和上一個節(jié)點。

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

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

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

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

那實際上整條鏈表是如何組織的呢？可以看一下鏈表初始化函數(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;
}

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

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

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

上圖的添加節(jié)點New4是屬于第二種節(jié)點插入的情況，根據(jù)代碼描述，是按值的順序來決定插入位置的，只要遇到鏈表中的其中一個節(jié)點B的值比新節(jié)點A的值要大，那么A就插入到B的前面。例如，節(jié)點值排序為NEW2