​​摘要：双向链表 Doubly Linked List 是鸿蒙轻内核最重要的数据结构之一，在各个模块有着非常广泛的使用。

本文分享自华为云社区《鸿蒙轻内核M核源码分析系列二 数据结构-双向循环链表》，原文作者：zhushy 。

在学习 OpenHarmony 鸿蒙轻内核源代码的时候，常常会遇到一些数据结构的使用。如果没有掌握它们的用法，会导致阅读源代码时很费解、很吃力。本文会给读者介绍源码中重要的数据结构，双向循环链表 Doubly Linked List。在讲解时，会结合数据结构相关绘图，培养读者们的数据结构的平面想象能力，帮助更好的学习和理解这些数据结构的用法。

本文中所涉及的源码，以 OpenHarmonyLiteOS-M 内核为例，均可以在开源站点https://gitee.com/openharmony/kernel_liteos_m 获取。

1、双向循环链表

双向链表 LOS_DL_LIST 的源代码在 utils\los_list.h 双向链表头文件中，包含 LOS_DL_LIST 结构体定义、inline 内联函数 LOS_ListXXX，还有相关的函数宏定义 LOS_DL_LIST_XXXX。双向链表头文件可以网页访问 utils/los_list.h，也可以检出到本地阅读。

1.1 双向链表结构体

双向链表节点结构体 LOS_DL_LIST 定义如下。其结构非常简单、通用、抽象，只包含前驱、后继两个节点，负责承上启下的双向链表作用。双向链表不包含任何业务数据信息，一般不会单独使用。通常，双向链表节点和业务数据信息作为结构体成员，一起组成业务结构体来使用，使用示例稍后会有讲述。

typedef struct LOS_DL_LIST {    struct LOS_DL_LIST *pstPrev; /** 指向当前链表节点的前驱节点的指针 */    struct LOS_DL_LIST *pstNext; /** 指向当前链表节点的后继节点的指针 */} LOS_DL_LIST;

​从双向链表中的任意一个节点开始，都可以很方便地访问它的前驱节点和后继节点，这种环状数据结构形式使得双向链表在查找、插入、删除等操作上非常方便。业务场景使用双向链表时，可以定义一个 LOS_DL_LIST 类型的全局变量作为双向循环链表 Head 头结点，业务结构体的链表成员节点依次挂载在头结点上。还有些业务结构体的双向链表节点作为 Head 头节点，依次挂载其他业务结构体的链表成员节点。从 Head 节点可以依次遍历下一个节点，Head 节点的前驱节点就是 Tail 尾节点。

下面通过鸿蒙轻内核代码中互斥锁结构体 LosMuxCB 定义，来了解如何使用双向链表结构体：

typedef struct {    UINT8 muxStat;       /**< 互斥锁状态  */    UINT16 muxCount;     /**< 互斥锁当前被持有的次数 */    UINT32 muxID;        /**< 互斥锁编号ID */    LOS_DL_LIST muxList; /**< 互斥锁的双向链表 */    LosTaskCB *owner;    /**< 当前持有锁的任务TCB */    UINT16 priority;     /**< 持有互斥锁的任务优先级 */} LosMuxCB;

​互斥锁结构体中包括双向链表 LOS_DL_LIST muxList 成员变量和其他包含互斥锁业务信息的成员变量，这里通过双向链表把各个互斥锁链接起来，挂载在头结点 LOS_DL_LIST g_unusedMuxList；通过其他业务成员变量承载业务数据，链表和其他业务成员关系如下图所示：

2、初始化双向链表

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;}

2.2 LOS_DL_LIST_HEAD(LOS_DL_LIST list)

除了 LOS_ListInit()，还提供了一个相同功能的函数式宏 LOS_DL_LIST_HEAD，通过直接定义一个双向链表节点，实现将该节点初始化为双向链表。区别于 LOS_ListInit()，在调用函数式宏前，不需要动态申请内存空间。

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

3、判断空链表

3.1 LOS_ListEmpty(LOS_DL_LIST *list)

该内联函数用于判断链表是否为空。如果双向链表的前驱/后继节点均为自身，只有一个链节点，没有挂载业务结构体的链表节点，称该链表为空链表。

源码如下：

LITE_OS_SEC_ALW_INLINE STATIC_INLINE BOOL LOS_ListEmpty(LOS_DL_LIST *node){    return (BOOL)(node->pstNext == node);}

4、插入双向链表节点

双向链表提供三种链表节点插入方法，在指定链表节点后面插入 LOS_ListAdd、尾部插入 LOS_ListTailInsert、头部插入 LOS_ListHeadInsert。在头部插入的节点，从头部开始遍历时第一个遍历到，从尾部插入的节点，最后一个遍历到。

4.1 LOS_ListAdd(LOS_DL_LIST *list, LOS_DL_LIST*node)

该内联函数往链表节点*list 所在的双向链表中插入一个链表节点*node，插入位置在链表节点*list

的后面。如图所示，在插入过程中，会将*node 的后继节点设置为 list->pstNext，*node 的前驱节点为*list，并将 list->pstNext 的前驱节点从*list 修改为*node，*list 的后继节点从 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)

该内联函数往链表节点*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);}

4.3 LOS_ListHeadInsert(LOS_DL_LIST *list,LOS_DL_LIST *node)

该内联函数和 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);}

5、删除双向链表节点

双向链表提供两种链表节点的删除方法，删除指定节点 LOS_ListDelete()、删除并初始化为一个新链表 LOS_ListDelInit()。

5.1 LOS_ListDelete(LOS_DL_LIST *node)

该内联函数将链表节点*node 从所在的双向链表中删除。节点删除后，可能需要主动释放节点所占用的内存。如图所示，删除节点过程中，会将*node 的后继节点的前驱改为*node 的前驱节点，*node 的前驱节点的后继改为*node 的后继节点，并把*node 节点的前驱、后继节点设置为 null，这样*node 节点就脱离了该双向链表。

图示：

​源码如下：

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)

该内联函数将链表节点*list 从所在的双向链表中删除, 并把删除后的节点重新初始化为一个新的双向链表。

和 LOS_ListDelete()类似，该函数也会将*list 的后继节点的前驱改为*list 的前驱，*list 的前驱节点的后继改为*list 的后继，但不同的是，因为要重新初始化为新双向链表，所以这个函数并不会把*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);}

6、获取双向链表节点

双向链表还提供获取链表节点、获取包含链表的结构体地址的操作。

6.1 LOS_DL_LIST_LAST(object)

获取指定链表节点的前驱节点。

源码如下：

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

6.2 LOS_DL_LIST_FIRST(object)

获取指定链表节点的后继节点。

源码如下：

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

7、遍历双向循环链表节点

双向循环链表提供两种遍历双向链表的方法，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 遍历双向链表，将每次循环获取的链表节点保存在第一个入参中，第二个入参是要遍历的双向链表的起始节点。这个宏是个 for 循环条件，在每次循环中，获取下一个链表节点保存到入参 item。业务代码写在宏后面的代码块{}内。

源码如下：

#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 文件中，UINT32OsPriqueueSize(UINT32 priority)函数的片段如下：

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]是要循环遍历的双向链表，curPQNode 指向遍历过程中的链表节点。

7.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)

8、获取链表节点所在结构体

8.1 LOS_OFF_SET_OF(type, member)

根据结构体类型名称 type 和其中的成员变量名称 member，获取 member 成员变量相对于结构体 type 的内存地址偏移量。在链表的应用场景上，业务结构体包含双向链表作为成员，当知道双向链表成员变量的内存地址和相对于业务结构体的偏移时，就可以进一步获取业务结构体的内存地址，具体见下面 LOS_DL_LIST_ENTRY 的宏实现。

源码如下：

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

8.2 LOS_DL_LIST_ENTRY(item, type, member)

函数宏中的三个参数分别为：业务结构体类型名称 type，作为结构体成员的双向链表成员变量名称 member，作为结构体成员的双向链表节点指针 item。通过调用该宏函数 LOS_DL_LIST_ENTRY 即可以获取双向链表节点所在的业务结构体的内存地址。

源码如下：

基于双向链表节点的内存地址，和双向链表成员变量在结构体中的地址偏移量，可以计算出结构体的内存地址。

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

9、遍历包含双向链表的结构体

双向链表提供三个宏定义来遍历包含双向链表成员的结构体，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 通过遍历双向链表，在每次循环中获取包含该双向链表成员的结构体变量并保存在第一个入参中。第二个入参是要遍历的双向链表的起始节点，第三个入参是要获取的结构体类型名称，第四个入参是该结构体中的双向链表成员变量的名称。这个宏是个 for 循环条件，业务代码写在宏后面的代码块{}内。

源码如下：

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))

9.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))

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

该宏定义和 LOS_DL_LIST_FOR_EACH_ENTRY 的区别就是多了一个入参 hook，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)

小结

掌握鸿蒙轻内核的双向循环链表 LOS_DL_LIST 这一重要的数据结构，会给进一步学习、分析鸿蒙轻内核源代码打下了基础，让后续的学习更加容易。

点击关注，第一时间了解华为云新鲜技术~