双向循环链表：鸿蒙轻内核中数据的“驿站”

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

华为云开发者联盟

4630人浏览 · 2021-05-08 14:35:02

华为云开发者联盟 · 2021-05-08 14:35:02 发布

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

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

本文中所涉及的源码，以OpenHarmony LiteOS-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文件中，UINT32 OsPriqueueSize(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)

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