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