鴻蒙輕內(nèi)核M核源碼分析系列一 數(shù)據(jù)結(jié)構(gòu)-雙向循環(huán)鏈表
想了解更多內(nèi)容，請(qǐng)?jiān)L問(wèn)：
51CTO和華為官方合作共建的鴻蒙技術(shù)社區(qū)
在學(xué)習(xí)OpenHarmony鴻蒙輕內(nèi)核源代碼的時(shí)候，常常會(huì)遇到一些數(shù)據(jù)結(jié)構(gòu)的使用。如果沒(méi)有掌握它們的用法，會(huì)導(dǎo)致閱讀源代碼時(shí)很費(fèi)解、很吃力。本文會(huì)給讀者介紹源碼中重要的數(shù)據(jù)結(jié)構(gòu)，雙向循環(huán)鏈表Doubly Linked List。在講解時(shí)，會(huì)結(jié)合數(shù)據(jù)結(jié)構(gòu)相關(guān)繪圖，培養(yǎng)讀者們的數(shù)據(jù)結(jié)構(gòu)的平面想象能力，幫助更好的學(xué)習(xí)和理解這些數(shù)據(jù)結(jié)構(gòu)的用法。
1 雙向循環(huán)鏈表
雙向鏈表LOS_DL_LIST的源代碼在utils\los_list.h雙向鏈表頭文件中，包含LOS_DL_LIST結(jié)構(gòu)體定義、inline內(nèi)聯(lián)函數(shù)LOS_ListXXX，還有相關(guān)的函數(shù)宏定義LOS_DL_LIST_XXXX。雙向鏈表頭文件可以網(wǎng)頁(yè)訪問(wèn)utils/los_list.h，也可以檢出到本地閱讀。
1.1 雙向鏈表結(jié)構(gòu)體
雙向鏈表節(jié)點(diǎn)結(jié)構(gòu)體LOS_DL_LIST定義如下。其結(jié)構(gòu)非常簡(jiǎn)單、通用、抽象，只包含前驅(qū)、后繼兩個(gè)節(jié)點(diǎn)，負(fù)責(zé)承上啟下的雙向鏈表作用。雙向鏈表不包含任何業(yè)務(wù)數(shù)據(jù)信息，一般不會(huì)單獨(dú)使用。通常，雙向鏈表節(jié)點(diǎn)和業(yè)務(wù)數(shù)據(jù)信息作為結(jié)構(gòu)體成員，一起組成業(yè)務(wù)結(jié)構(gòu)體來(lái)使用，使用示例稍后會(huì)有講述。
- typedef struct LOS_DL_LIST {
- struct LOS_DL_LIST *pstPrev; /** 指向當(dāng)前鏈表節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針 */
- struct LOS_DL_LIST *pstNext; /** 指向當(dāng)前鏈表節(jié)點(diǎn)的后繼節(jié)點(diǎn)的指針 */
- } LOS_DL_LIST;
從雙向鏈表中的任意一個(gè)節(jié)點(diǎn)開(kāi)始，都可以很方便地訪問(wèn)它的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)，這種環(huán)狀數(shù)據(jù)結(jié)構(gòu)形式使得雙向鏈表在查找、插入、刪除等操作上非常方便。業(yè)務(wù)場(chǎng)景使用雙向鏈表時(shí)，可以定義一個(gè)LOS_DL_LIST類(lèi)型的全局變量作為雙向循環(huán)鏈表Head頭結(jié)點(diǎn)，業(yè)務(wù)結(jié)構(gòu)體的鏈表成員節(jié)點(diǎn)依次掛載在頭結(jié)點(diǎn)上。還有些業(yè)務(wù)結(jié)構(gòu)體的雙向鏈表節(jié)點(diǎn)作為Head頭節(jié)點(diǎn)，依次掛載其他業(yè)務(wù)結(jié)構(gòu)體的鏈表成員節(jié)點(diǎn)。從Head節(jié)點(diǎn)可以依次遍歷下一個(gè)節(jié)點(diǎn)，Head節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)就是Tail尾節(jié)點(diǎn)。
下面通過(guò)鴻蒙輕內(nèi)核代碼中互斥鎖結(jié)構(gòu)體LosMuxCB定義，來(lái)了解如何使用雙向鏈表結(jié)構(gòu)體：
- typedef struct {
- UINT8 muxStat; /**< 互斥鎖狀態(tài) */
- UINT16 muxCount; /**< 互斥鎖當(dāng)前被持有的次數(shù) */
- UINT32 muxID; /**< 互斥鎖編號(hào)ID */
- LOS_DL_LIST muxList; /**< 互斥鎖的雙向鏈表 */
- LosTaskCB *owner; /**< 當(dāng)前持有鎖的任務(wù)TCB */
- UINT16 priority; /**< 持有互斥鎖的任務(wù)優(yōu)先級(jí) */
- } LosMuxCB;
互斥鎖結(jié)構(gòu)體中包括雙向鏈表LOS_DL_LIST muxList成員變量和其他包含互斥鎖業(yè)務(wù)信息的成員變量，這里通過(guò)雙向鏈表把各個(gè)互斥鎖鏈接起來(lái)，掛載在頭結(jié)點(diǎn)LOS_DL_LIST g_unusedMuxList;通過(guò)其他業(yè)務(wù)成員變量承載業(yè)務(wù)數(shù)據(jù)，鏈表和其他業(yè)務(wù)成員關(guān)系如下圖所示：
2 初始化雙向鏈表
2.1 LOS_ListInit(LOS_DL_LIST *list)
LOS_DL_LIST的兩個(gè)成員pstPrev和pstNext, 是LOS_DL_LIST結(jié)構(gòu)體類(lèi)型的指針。需要為雙向鏈表節(jié)點(diǎn)申請(qǐng)長(zhǎng)度為sizeof(LOS_DL_LIST)的一段內(nèi)存空間。為鏈表節(jié)點(diǎn)申請(qǐng)到內(nèi)存后，可以調(diào)用初始化LOS_ListInit(LOS_DL_LIST *list)方法，把這個(gè)節(jié)點(diǎn)鏈接為環(huán)狀的雙向鏈表。初始化鏈表時(shí)，只有一個(gè)鏈表節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)都是自身。鏈表節(jié)點(diǎn)初始化為鏈表，如圖所示：
源碼如下：
- LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListInit(LOS_DL_LIST *list)
- {
- list->pstNext = list;
- list->pstPrev = list;
- }
2.2 LOS_DL_LIST_HEAD(LOS_DL_LIST list)
除了LOS_ListInit()，還提供了一個(gè)相同功能的函數(shù)式宏LOS_DL_LIST_HEAD，通過(guò)直接定義一個(gè)雙向鏈表節(jié)點(diǎn)，實(shí)現(xiàn)將該節(jié)點(diǎn)初始化為雙向鏈表。區(qū)別于LOS_ListInit()，在調(diào)用函數(shù)式宏前，不需要?jiǎng)討B(tài)申請(qǐng)內(nèi)存空間。
- #define LOS_DL_LIST_HEAD(list) LOS_DL_LIST list = { &(list), &(list) }
3 判斷空鏈表
3.1 LOS_ListEmpty(LOS_DL_LIST *list)
該內(nèi)聯(lián)函數(shù)用于判斷鏈表是否為空。如果雙向鏈表的前驅(qū)/后繼節(jié)點(diǎn)均為自身，只有一個(gè)鏈節(jié)點(diǎn)，沒(méi)有掛載業(yè)務(wù)結(jié)構(gòu)體的鏈表節(jié)點(diǎn)，稱(chēng)該鏈表為空鏈表。
源碼如下：
- LITE_OS_SEC_ALW_INLINE STATIC_INLINE BOOL LOS_ListEmpty(LOS_DL_LIST *node)
- {
- return (BOOL)(node->pstNext == node);
- }
4 插入雙向鏈表節(jié)點(diǎn)
雙向鏈表提供三種鏈表節(jié)點(diǎn)插入方法，在指定鏈表節(jié)點(diǎn)后面插入LOS_ListAdd、尾部插入LOS_ListTailInsert、頭部插入LOS_ListHeadInsert。在頭部插入的節(jié)點(diǎn)，從頭部開(kāi)始遍歷時(shí)第一個(gè)遍歷到，從尾部插入的節(jié)點(diǎn)，最后一個(gè)遍歷到。
4.1 LOS_ListAdd(LOS_DL_LIST *list, LOS_DL_LIST *node)
該內(nèi)聯(lián)函數(shù)往鏈表節(jié)點(diǎn)*list所在的雙向鏈表中插入一個(gè)鏈表節(jié)點(diǎn)*node，插入位置在鏈表節(jié)點(diǎn)*list的后面。如圖所示，在插入過(guò)程中，會(huì)將*node的后繼節(jié)點(diǎn)設(shè)置為list->pstNext，*node的前驅(qū)節(jié)點(diǎn)為*list，并將list->pstNext的前驅(qū)節(jié)點(diǎn)從*list修改為*node，*list的后繼節(jié)點(diǎn)從list->pstNext修改為*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;
- }
4.2 LOS_ListTailInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
該內(nèi)聯(lián)函數(shù)往鏈表節(jié)點(diǎn)*list所在的雙向鏈表中插入一個(gè)鏈表節(jié)點(diǎn)*node，插入位置在鏈表節(jié)點(diǎn)*list的前面，list->pstPrev節(jié)點(diǎn)的后面。
源碼如下：
- LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListTailInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
- {
- LOS_ListAdd(list->pstPrev, node);
- }
4.3 LOS_ListHeadInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
該內(nèi)聯(lián)函數(shù)和LOS_ListAdd()實(shí)現(xiàn)同樣的功能，往鏈表節(jié)點(diǎn)*list所在的雙向鏈表中插入一個(gè)鏈表節(jié)點(diǎn)*node，插入位置在鏈表節(jié)點(diǎn)*list的后面。
源碼如下：
- LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListHeadInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
- {
- LOS_ListAdd(list, node);
- }
5 刪除雙向鏈表節(jié)點(diǎn)
雙向鏈表提供兩種鏈表節(jié)點(diǎn)的刪除方法，刪除指定節(jié)點(diǎn)LOS_ListDelete()、刪除并初始化為一個(gè)新鏈表LOS_ListDelInit()。
5.1 LOS_ListDelete(LOS_DL_LIST *node)
該內(nèi)聯(lián)函數(shù)將鏈表節(jié)點(diǎn)*node從所在的雙向鏈表中刪除。節(jié)點(diǎn)刪除后，可能需要主動(dòng)釋放節(jié)點(diǎn)所占用的內(nèi)存。如圖所示，刪除節(jié)點(diǎn)過(guò)程中，會(huì)將*node的后繼節(jié)點(diǎn)的前驅(qū)改為*node的前驅(qū)節(jié)點(diǎn)，*node的前驅(qū)節(jié)點(diǎn)的后繼改為*node的后繼節(jié)點(diǎn)，并把*node節(jié)點(diǎn)的前驅(qū)、后繼節(jié)點(diǎn)設(shè)置為null，這樣*node節(jié)點(diǎn)就脫離了該雙向鏈表。
圖示：
源碼如下：
- 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;
- }
5.2 LOS_ListDelInit(LOS_DL_LIST *list)
該內(nèi)聯(lián)函數(shù)將鏈表節(jié)點(diǎn)*list從所在的雙向鏈表中刪除, 并把刪除后的節(jié)點(diǎn)重新初始化為一個(gè)新的雙向鏈表。
和LOS_ListDelete()類(lèi)似，該函數(shù)也會(huì)將*list的后繼節(jié)點(diǎn)的前驅(qū)改為*list的前驅(qū)，*list的前驅(qū)節(jié)點(diǎn)的后繼改為*list的后繼，但不同的是，因?yàn)橐匦鲁跏蓟癁樾码p向鏈表，所以這個(gè)函數(shù)并不會(huì)把*list的前驅(qū)、后繼節(jié)點(diǎn)設(shè)置為null，而是把這個(gè)刪除的節(jié)點(diǎn)重新初始化為以*list為頭節(jié)點(diǎn)的新雙向鏈表。
源碼如下：
- 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);
- }
6 獲取雙向鏈表節(jié)點(diǎn)
雙向鏈表還提供獲取鏈表節(jié)點(diǎn)、獲取包含鏈表的結(jié)構(gòu)體地址的操作。
6.1 LOS_DL_LIST_LAST(object)
獲取指定鏈表節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)。
源碼如下：
- #define LOS_DL_LIST_LAST(object) ((object)->pstPrev)
6.2 LOS_DL_LIST_FIRST(object)
獲取指定鏈表節(jié)點(diǎn)的后繼節(jié)點(diǎn)。
源碼如下：
- #define LOS_DL_LIST_FIRST(object) ((object)->pstNext)
7 遍歷雙向循環(huán)鏈表節(jié)點(diǎn)
雙向循環(huán)鏈表提供兩種遍歷雙向鏈表的方法，LOS_DL_LIST_FOR_EACH和LOS_DL_LIST_FOR_EACH_SAFE。
7.1 LOS_DL_LIST_FOR_EACH(item, list)
該宏定義LOS_DL_LIST_FOR_EACH遍歷雙向鏈表，將每次循環(huán)獲取的鏈表節(jié)點(diǎn)保存在第一個(gè)入?yún)⒅?，第二個(gè)入?yún)⑹且闅v的雙向鏈表的起始節(jié)點(diǎn)。這個(gè)宏是個(gè)for循環(huán)條件，在每次循環(huán)中，獲取下一個(gè)鏈表節(jié)點(diǎn)保存到入?yún)tem。業(yè)務(wù)代碼寫(xiě)在宏后面的代碼塊{}內(nèi)。
源碼如下：
- #define LOS_DL_LIST_FOR_EACH(item, list) \
- for ((item) = (list)->pstNext; (item) != (list); (item) = (item)->pstNext)
我們以實(shí)例演示如何使用LOS_DL_LIST_FOR_EACH。在kernel\src\los_task.c文件中，UINT32 OsPriqueueSize(UINT32 priority)函數(shù)的片段如下：
- STATIC UINT32 OsPriqueueSize(UINT32 priority)
- {
- UINT32 itemCnt = 0;
- LOS_DL_LIST *curPQNode = (LOS_DL_LIST *)NULL;
- ⑴ LOS_DL_LIST_FOR_EACH(curPQNode, &g_losPriorityQueueList[priority]) {
- ++itemCnt;
- }
- return itemCnt;
- }
其中⑴處代碼，g_losPriorityQueueList[priority]是要循環(huán)遍歷的雙向鏈表，curPQNode指向遍歷過(guò)程中的鏈表節(jié)點(diǎn)。
7.2 LOS_DL_LIST_FOR_EACH_SAFE(item, next, list)
該宏定義LOS_DL_LIST_FOR_EACH_SAFE和LOS_DL_LIST_FOR_EACH的唯一區(qū)別就是多了一個(gè)入?yún)ext, 這個(gè)參數(shù)表示遍歷到的雙向鏈表節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。該宏用于安全刪除，如果刪除遍歷到的item, 不影響繼續(xù)遍歷。
源碼如下：
- #define LOS_DL_LIST_FOR_EACH_SAFE(item, next, list) \
- for ((item) = (list)->pstNext, (next) = (item)->pstNext; (item) != (list); \
- (item) = (next), (next) = (item)->pstNext)
8 獲取鏈表節(jié)點(diǎn)所在結(jié)構(gòu)體
8.1 LOS_OFF_SET_OF(type, member)
根據(jù)結(jié)構(gòu)體類(lèi)型名稱(chēng)type和其中的成員變量名稱(chēng)member，獲取member成員變量相對(duì)于結(jié)構(gòu)體type的內(nèi)存地址偏移量。在鏈表的應(yīng)用場(chǎng)景上，業(yè)務(wù)結(jié)構(gòu)體包含雙向鏈表作為成員，當(dāng)知道雙向鏈表成員變量的內(nèi)存地址和相對(duì)于業(yè)務(wù)結(jié)構(gòu)體的偏移時(shí)，就可以進(jìn)一步獲取業(yè)務(wù)結(jié)構(gòu)體的內(nèi)存地址，具體見(jiàn)下面LOS_DL_LIST_ENTRY的宏實(shí)現(xiàn)。
源碼如下：
- #define LOS_OFF_SET_OF(type, member) ((UINTPTR)&((type *)0)->member)
8.2 LOS_DL_LIST_ENTRY(item, type, member)
函數(shù)宏中的三個(gè)參數(shù)分別為：業(yè)務(wù)結(jié)構(gòu)體類(lèi)型名稱(chēng)type，作為結(jié)構(gòu)體成員的雙向鏈表成員變量名稱(chēng)member，作為結(jié)構(gòu)體成員的雙向鏈表節(jié)點(diǎn)指針item。通過(guò)調(diào)用該宏函數(shù)LOS_DL_LIST_ENTRY即可以獲取雙向鏈表節(jié)點(diǎn)所在的業(yè)務(wù)結(jié)構(gòu)體的內(nèi)存地址。
源碼如下：
基于雙向鏈表節(jié)點(diǎn)的內(nèi)存地址，和雙向鏈表成員變量在結(jié)構(gòu)體中的地址偏移量，可以計(jì)算出結(jié)構(gòu)體的內(nèi)存地址。
- #define LOS_DL_LIST_ENTRY(item, type, member) \
- ((type *)(VOID *)((CHAR *)(item) - LOS_OFF_SET_OF(type, member)))
9 遍歷包含雙向鏈表的結(jié)構(gòu)體
雙向鏈表提供三個(gè)宏定義來(lái)遍歷包含雙向鏈表成員的結(jié)構(gòu)體，LOS_DL_LIST_FOR_EACH_ENTRY、LOS_DL_LIST_FOR_EACH_ENTRY_SAFE和LOS_DL_LIST_FOR_EACH_ENTRY_HOOK。
9.1 LOS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member)
該宏定義LOS_DL_LIST_FOR_EACH_ENTRY通過(guò)遍歷雙向鏈表，在每次循環(huán)中獲取包含該雙向鏈表成員的結(jié)構(gòu)體變量并保存在第一個(gè)入?yún)⒅?。第二個(gè)入?yún)⑹且闅v的雙向鏈表的起始節(jié)點(diǎn)，第三個(gè)入?yún)⑹且@取的結(jié)構(gòu)體類(lèi)型名稱(chēng)，第四個(gè)入?yún)⑹窃摻Y(jié)構(gòu)體中的雙向鏈表成員變量的名稱(chēng)。這個(gè)宏是個(gè)for循環(huán)條件，業(yè)務(wù)代碼寫(xiě)在宏后面的代碼塊{}內(nèi)。
源碼如下：
for循環(huán)的初始化語(yǔ)句item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member)表示獲取包含雙向鏈表第一個(gè)有效節(jié)點(diǎn)的結(jié)構(gòu)體，并保存到指針變量item中。條件測(cè)試語(yǔ)句&(item)->member != (list)表示當(dāng)雙向鏈表遍歷一圈到自身節(jié)點(diǎn)時(shí)，停止循環(huán)。循環(huán)更新語(yǔ)句item = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))中，使用(item)->member.pstNext遍歷到下一個(gè)鏈表節(jié)點(diǎn)，然后根據(jù)這個(gè)節(jié)點(diǎn)獲取對(duì)應(yīng)的下一個(gè)結(jié)構(gòu)體的指針變量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))
9.2 LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member)
該宏定義和LOS_DL_LIST_FOR_EACH_ENTRY的唯一區(qū)別就是多了一個(gè)入?yún)ext, 這個(gè)參數(shù)表示遍歷到的結(jié)構(gòu)體的下一個(gè)結(jié)構(gòu)體。該宏用于安全刪除，如果刪除遍歷到的item，不影響繼續(xù)遍歷。
源碼如下：
- #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))
9.3 LOS_DL_LIST_FOR_EACH_ENTRY_HOOK(item, list, type, member, hook)
該宏定義和LOS_DL_LIST_FOR_EACH_ENTRY的區(qū)別就是多了一個(gè)入?yún)ook，hook表示鉤子函數(shù)。在每次遍歷循環(huán)中，會(huì)調(diào)用該鉤子函數(shù)，實(shí)現(xiàn)用戶(hù)任務(wù)的定制。
源碼如下：
- #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)
小結(jié)
掌握鴻蒙輕內(nèi)核的雙向循環(huán)鏈表LOS_DL_LIST這一重要的數(shù)據(jù)結(jié)構(gòu)，會(huì)給進(jìn)一步學(xué)習(xí)、分析鴻蒙輕內(nèi)核源代碼打下了基礎(chǔ)，讓后續(xù)的學(xué)習(xí)更加容易。后續(xù)也會(huì)陸續(xù)推出更多的分享文章，敬請(qǐng)期待，也歡迎大家分享學(xué)習(xí)、使用鴻蒙輕內(nèi)核的心得，有任何問(wèn)題、建議，都可以留言給我們： https://gitee.com/openharmony/kernel_liteos_m/issues 。為了更容易找到鴻蒙輕內(nèi)核代碼倉(cāng)，建議訪問(wèn) https://gitee.com/openharmony/kernel_liteos_m ，關(guān)注Watch、點(diǎn)贊Star、并Fork到自己賬戶(hù)下，謝謝。
想了解更多內(nèi)容，請(qǐng)?jiān)L問(wèn)：
51CTO和華為官方合作共建的鴻蒙技術(shù)社區(qū)
