LiteOS內核源碼分析系列一 盤點那些重要的數據結構 （1）

LiteOS內核源碼分析系列一 盤點那些重要的數據結構 -- DL

在學習Huawei LiteOS源代碼的時候，常常會遇到一些數據結構的使用。如果沒有掌握這它們的用法，閱讀LiteOS源代碼的時候會很費解、很吃力。本文會給讀者介紹下LiteOS源碼中常用的幾個數據結構，包括: 雙向循環鏈表LOS_DL_LIST，優先級隊列Priority Queue，排序鏈表SortLinkList等。在講解時，會結合相關的繪圖，培養數據結構的平面想象能力，幫助更好的學習和理解這些數據結構用法。

本文中所涉及的LiteOS源碼，均可以在LiteOS開源站點https://gitee.com/LiteOS/LiteOS?獲取。

我們首先來看看使用最多的雙向循環鏈表Doubly Linked List。

1、LOS_DL_LIST 雙向循環鏈表

雙向鏈表LOS_DL_LIST核心的代碼都在kernel\include\los_list.h頭文件中，包含LOS_DL_LIST結構體定義、一些inline內聯函數LOS_ListXXX，還有一些雙向鏈表相關的宏定義LOS_DL_LIST_XXXX。

雙向鏈表源代碼、示例程序代碼、開發文檔如下：

kernel\include\los_list.h 雙向鏈表頭文件

網頁獲取源碼?https://gitee.com/LiteOS/LiteOS/blob/master/kernel/include/los_list.h。

demos\kernel\api\los_api_list.c 雙向鏈表Demo程序

網頁獲取源碼?https://gitee.com/LiteOS/LiteOS/blob/master/demos/kernel/api/los_api_list.c。

開發指南雙向鏈表文檔

在線文檔https://gitee.com/LiteOS/LiteOS/blob/master/doc/Huawei_LiteOS_Kernel_Developer_Guide_zh.md#%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8

1.1 LOS_DL_LIST 雙向鏈表結構體

雙向鏈表結構體LOS_DL_LIST定義如下。看得出來，雙向鏈表的結構非常簡單、通用、抽象，只包含前驅、后繼兩個節點，負責承上啟下的雙向鏈表作用。雙向鏈表不包任何業務數據信息，業務數據信息維護在業務的結構體中。雙向鏈表作為業務結構體的成員使用，使用示例稍后會有講述。

typedef struct LOS_DL_LIST { struct LOS_DL_LIST *pstPrev; /** 當前節點的指向前驅節點的指針 */ struct LOS_DL_LIST *pstNext; /** 當前節點的指向后繼節點的指針 */ } LOS_DL_LIST;

從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點，這種數據結構形式使得雙向鏈表在查找、插入、刪除等操作，對于非常方便。由于雙向鏈表的環狀結構，任何一個節點的地位都是平等的。從業務上，可以創建一個節點作為Head頭節點，業務結構體的鏈表節點從HEAD節點開始掛載。從head節點的依次遍歷下一個節點，最后一個不等于Head節點的節點稱之為Tail尾節點。這個Tail節點也是Head節點的前驅。從Head向前查找，可以更快的找到Tail節點。

我們看看LiteOS內核代碼中如何使用雙向鏈表結構體的。下面是互斥鎖結構體LosMuxCB定義，其中包含雙向鏈表LOS_DL_LIST muxList;成員變量：

typedef struct { LOS_DL_LIST muxList; /** 互斥鎖的雙向鏈表*/ LosTaskCB *owner; /** 當前持有鎖的任務TCB */ UINT16 muxCount; /** 持有互斥鎖的次數 */ UINT8 muxStat; /** 互斥鎖狀態OS_MUX_UNUSED, OS_MUX_USED */ UINT32 muxId; /** 互斥鎖handler ID*/ } LosMuxCB;

雙向循環鏈表可以把各個互斥鎖鏈接起來，鏈表和其他業務成員關系如下圖所示：

LiteOS的雙向鏈表為用戶提供下面初始化雙向列表，增加、刪除鏈表節點，判斷節點是否為空，獲取鏈表節點，獲取鏈表所在的結構體，遍歷雙向鏈表，遍歷包含雙向鏈表的結構體等功能。我們一一來詳細的學習、分析下代碼。

1.2 LOS_DL_LIST 雙向鏈表初始化

1.2.1 LOS_ListInit(LOS_DL_LIST *list)

LOS_DL_LIST的兩個成員*pstPrev和*pstNext, 是LOS_DL_LIST結構體類型的指針。需要為雙向鏈表節點申請長度為sizeof(LOS_DL_LIST)的一段內存空間。為鏈表節點申請完畢內存后，可以調用初始化LOS_ListInit(LOS_DL_LIST *list)方法，把這個節點鏈接為環狀的雙向鏈表。初始化鏈表的時候，只有一個鏈表節點，這個節點的前序和后繼節點都是自身。

鏈表節點初始化為鏈表，如圖所示：

源碼如下：

LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListInit(LOS_DL_LIST *list) { list->pstNext = list; list->pstPrev = list; }

另外，還提供了一個宏LOS_DL_LIST_HEAD，直接定義一個雙向鏈表節點并以該節點初始化為雙向鏈表。

#define LOS_DL_LIST_HEAD(list) LOS_DL_LIST list = { &(list), &(list) }

1.2.2 LOS_ListEmpty(LOS_DL_LIST *list)

該接口用于判斷鏈表是否為空。如果雙向鏈表的前驅/后繼節點均為自身，只有一個鏈表HEAD頭節點，沒有掛載業務結構體的鏈表節點，稱該鏈表為空鏈表。

源碼如下：

LITE_OS_SEC_ALW_INLINE STATIC INLINE BOOL LOS_ListEmpty(LOS_DL_LIST *list) { return (BOOL)(list->pstNext == list); }

1.3 LOS_DL_LIST 雙向鏈表節點操作

LiteOS雙向鏈表提供三種鏈表節點插入方法，指定鏈表節點后面插入LOS_ListAdd、尾部插入LOS_ListTailInsert、頭部插入LOS_ListHeadInsert。在頭部插入的節點，從頭部開始遍歷時第一個遍歷到，從尾部插入的節點，最后一個遍歷到。

1.3.1 LOS_ListAdd(LOS_DL_LIST *list, LOS_DL_LIST *node)

這個API接口往鏈表節點*list所在的雙向鏈表中插入一個鏈表節點*node，插入位置在鏈表節點*list的后面。如圖所示，完成插入后，*node的后繼節點是list->pstNext，*node的前序節點是*list。list->pstNext的前序節點是*node，*list的后續是*node節點。

圖示：

源碼如下：

LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListAdd(LOS_DL_LIST *list, LOS_DL_LIST *node) { node->pstNext = list->pstNext; node->pstPrev = list; list->pstNext->pstPrev = node; list->pstNext = node; }

1.3.2 LOS_ListTailInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)

這個API接口往鏈表節點*list所在的雙向鏈表中插入一個鏈表節點*node，插入位置在鏈表節點*list的前面，在list->pstPrev節點的后面。

源碼如下：

LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListTailInsert(LOS_DL_LIST *list, LOS_DL_LIST *node) { LOS_ListAdd(list->pstPrev, node); }

1.3.3 LOS_ListHeadInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)

這個API接口和LOS_ListAdd()接口實現同樣的功能，往鏈表節點*list所在的雙向鏈表中插入一個鏈表節點*node，插入位置在鏈表節點*list的后面。

源碼如下：

LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListHeadInsert(LOS_DL_LIST *list, LOS_DL_LIST *node) { LOS_ListAdd(list, node); }

LiteOS雙向鏈表提供兩種鏈表節點的刪除方法，指定節點刪除LOS_ListDelete、刪除并初始化為一個新鏈表LOS_ListDelInit。

1.3.4 LOS_ListDelete(LOS_DL_LIST *node)

這個API接口將鏈表節點*node從所在的雙向鏈表中刪除。節點刪除后，可能需要調用Free()函數釋放節點所占用的內存。如圖所示，*node節點后繼節點的前序改為*node的前序，*node節點前序節點的后續改為*node的后續，并把*node節點的前序、后續節點設置為null。

圖示：

源碼如下：

LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListDelete(LOS_DL_LIST *node) { node->pstNext->pstPrev = node->pstPrev; node->pstPrev->pstNext = node->pstNext; node->pstNext = NULL; node->pstPrev = NULL; }

1.3.5 LOS_ListDelInit(LOS_DL_LIST *list)

這個API接口將鏈表節點*list從所在的雙向鏈表中刪除, 并把刪除后的節點重新初始化為一個新的雙向鏈表。

*list節點后繼節點的前序改為*list的前序，*list節點前序節點的后續改為*list的后續。和LOS_ListDelete()方法不同的是，并不并把*list節點的前序、后續節點設置為null，而是把這個刪除的節點重新初始化為一個新的以*list為頭結點的雙向鏈表。

源碼如下：

LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListDelInit(LOS_DL_LIST *list) { list->pstNext->pstPrev = list->pstPrev; list->pstPrev->pstNext = list->pstNext; LOS_ListInit(list); }

LiteOS雙向鏈表還提供獲取鏈表節點、獲取包含鏈表的結構體地址的操作。

1.3.6 LOS_DL_LIST_LAST(object)

這個宏定義獲取鏈表的前驅節點。

源碼如下：

#define LOS_DL_LIST_LAST(object) ((object)->pstPrev)

1.3.7 LOS_DL_LIST_FIRST(object)

這個宏定義獲取鏈表的后繼節點。

源碼如下：

#define LOS_DL_LIST_FIRST(object) ((object)->pstNext)

1.3.8 LOS_OFF_SET_OF(type, member)

這個宏定義根據結構體類型名稱type和其中的成員變量名稱member，獲取member成員變量相對于結構體type的內存地址偏移量。在應用場景上，業務結構體包含雙向鏈表作為成員，當知道雙向鏈表成員變量的內存地址時，和這個偏移量，可以進一步獲取業務結構體的內存地址。

源碼如下：

#define LOS_OFF_SET_OF(type, member) ((UINTPTR)&((type *)0)->member)

1.3.9 LOS_DL_LIST_ENTRY(item, type, member)

根據業務結構體類型名稱type、其中的雙向鏈表成員變量名稱member，和雙向鏈表的內存指針變量item，使用該宏定義LOS_DL_LIST_ENTRY可以獲取業務結構體的內存地址。

我們以實際例子演示下這個宏LOS_DL_LIST_ENTRY是如何使用的。互斥鎖的control block結構體LosMuxCB在上文已經展示過其代碼，有個雙向鏈表的成員變量LOS_DL_LIST muxList。在創建互斥鎖的方法LOS_MuxCreate()中，⑴ 處代碼從空閑互斥鎖鏈表中獲取一個空閑的雙向鏈表節點指針地址LOS_DL_LIST *unusedMux，把這個作為第一個參數，結構體名稱LosMuxCB及其成員變量muxList，分別作為第二、第三個參數，使用宏LOS_DL_LIST_ENTRY可以計算出結構體的指針變量地址LosMuxCB *muxCreated，見⑵處代碼。

LITE_OS_SEC_TEXT UINT32 LOS_MuxCreate(UINT32 *muxHandle) { ...... LosMuxCB *muxCreated = NULL; LOS_DL_LIST *unusedMux = NULL; ...... ⑴ unusedMux = LOS_DL_LIST_FIRST(&g_unusedMuxList); LOS_ListDelete(unusedMux); ⑵ muxCreated = LOS_DL_LIST_ENTRY(unusedMux, LosMuxCB, muxList); ...... }

從這個例子上，就比較容易理解，這個宏定義可以用于什么樣的場景，讀者們可以閱讀查看更多使用這個宏的例子，加強理解。

源碼如下：

源碼實現上，基于雙向鏈表節點的內存地址，和雙向鏈表成員變量在結構體中的地址偏移量，可以計算出結構體的內存地址。

#define LOS_DL_LIST_ENTRY(item, type, member) \ ((type *)(VOID *)((CHAR *)(item) - LOS_OFF_SET_OF(type, member)))

1.4 LOS_DL_LIST 雙向循環鏈表遍歷

LiteOS雙向循環鏈表提供兩種遍歷雙向鏈表的方法，LOS_DL_LIST_FOR_EACH和LOS_DL_LIST_FOR_EACH_SAFE。

1.4.1 LOS_DL_LIST_FOR_EACH(item, list)

該宏定義LOS_DL_LIST_FOR_EACH遍歷雙向鏈表，接口的第一個入參表示的是雙向鏈表節點的指針變量，在遍歷過程中依次指向下一個鏈表節點。第二個入參是要遍歷的雙向鏈表的起始節點。這個宏是個循環條件部分，用戶的業務代碼寫在宏后面的代碼塊{}內。

我們以實際例子來演示這個宏LOS_DL_LIST_FOR_EACH是如何使用的。在kernel\base\sched\sched_sq\los_priqueue.c文件中，UINT32 OsPriQueueSize(UINT32 priority)函數的片段如下：

&g_priQueueList[priority]是我們要遍歷的雙向鏈表，curNode指向遍歷過程中的鏈表節點，見⑴處代碼代碼。完整代碼請訪問我們的開源站點。

UINT32 OsPriQueueSize(UINT32 priority) { UINT32 itemCnt = 0; LOS_DL_LIST *curNode = NULL; ...... ⑴ LOS_DL_LIST_FOR_EACH(curNode, &g_priQueueList[priority]) { ...... task = OS_TCB_FROM_PENDLIST(curNode); ...... } return itemCnt; }

源碼如下：

#define LOS_DL_LIST_FOR_EACH(item, list) \ for (item = (list)->pstNext; \ (item) != (list); \ item = (item)->pstNext)

1.4.2 LOS_DL_LIST_FOR_EACH_SAFE(item, next, list)

該宏定義LOS_DL_LIST_FOR_EACH_SAFE和LOS_DL_LIST_FOR_EACH唯一的區別就是多個入參next, 這個參數表示遍歷到的雙向鏈表節點的下一個節點。該宏用于安全刪除，如果刪除遍歷到的item, 不影響繼續遍歷。

源碼如下：

#define LOS_DL_LIST_FOR_EACH_SAFE(item, next, list) \ for (item = (list)->pstNext, next = (item)->pstNext; \ (item) != (list); \ item = next, next = (item)->pstNext)

1.5 LOS_DL_LIST 遍歷包含雙向鏈表的結構體

LiteOS雙向鏈表提供三個宏定義來遍歷包含雙向鏈表成員的結構體，LOS_DL_LIST_FOR_EACH_ENTRY、LOS_DL_LIST_FOR_EACH_ENTRY_SAFE和LOS_DL_LIST_FOR_EACH_ENTRY_HOOK。

1.5.1 LOS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member)

該宏定義LOS_DL_LIST_FOR_EACH_ENTRY遍歷雙向鏈表，接口的第一個入參表示的是包含雙向鏈表成員的結構體的指針變量，第二個入參是要遍歷的雙向鏈表的起始節點，第三個入參是要獲取的結構體名稱，第四個入參是在該結構體中的雙向鏈表的成員變量名稱。

我們以實際例子來演示這個宏LOS_DL_LIST_FOR_EACH_ENTRY是如何使用的。在kernel\base\sched\sched_sq\los_priqueue.c文件中，LosTaskCB *OsGetTopTask(VOID)函數的片段如下。結構體LosTaskCB包含雙向鏈表成員變量pendList,&g_priQueueList[priority]?是對應任務優先級priority的pendList的雙向鏈表。會依次遍歷這個雙向鏈表&g_priQueueList[priority]，根據遍歷到的鏈表節點，依次獲取任務結構體LosTaskCB的指針變量newTask，如⑴處代碼所示。

LITE_OS_SEC_TEXT_MINOR LosTaskCB *OsGetTopTask(VOID) { UINT32 priority; UINT32 bitmap; LosTaskCB *newTask = NULL; ...... ⑴ LOS_DL_LIST_FOR_EACH_ENTRY(newTask, &g_priQueueList[priority], LosTaskCB, pendList) { ...... OsPriQueueDequeue(&newTask->pendList); ...... } ...... }

源碼如下：

源碼實現上，for循環的初始化語句item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member)表示包含雙向鏈表成員的結構體的指針變量item，條件測試語句&(item)->member != (list)循環條件表示當雙向鏈表遍歷一圈到自身節點的時候，停止循環。循環更新語句item = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))中，使用(item)->member.pstNext遍歷到下一個鏈表節點，然后根據這個節點獲取對應的下一個結構體的指針變量item，直至遍歷完畢。

#define LOS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member) \ for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member); \ &(item)->member != (list); \ item = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))

1.5.2 LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member)

該宏定義和LOS_DL_LIST_FOR_EACH_ENTRY唯一的區別就是多個個入參next, 這個參數表示遍歷到的結構體的下一個結構體地址的指針變量。該宏用于安全刪除，如果刪除遍歷到的item，不影響繼續遍歷。

源碼如下：

#define LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member) \ for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member), \ next = LOS_DL_LIST_ENTRY((item)->member->pstNext, type, member); \ &(item)->member != (list); \ item = next, next = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))

1.5.3 LOS_DL_LIST_FOR_EACH_ENTRY_HOOK(item, list, type, member, hook)

該宏定義和LOS_DL_LIST_FOR_EACH_ENTRY的區別就是多了個入參hook個鉤子函數。在每次遍歷循環中，調用該鉤子函數做些用戶定制的工作。

源碼如下：

#define LOS_DL_LIST_FOR_EACH_ENTRY_HOOK(item, list, type, member, hook) \ for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member), hook; \ &(item)->member != (list); \ item = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member), hook)

數據結構 輕量級操作系統 LiteOS

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。