摘要：双向链表Doubly Linked List是鸿蒙轻内核最重要的数据结构之一，在各个模块有着十分宽泛的应用。
本文分享自华为云社区《鸿蒙轻内核M核源码剖析系列二 数据结构-双向循环链表》，原文作者：zhushy 。
在学习OpenHarmony鸿蒙轻内核源代码的时候，经常会遇到一些数据结构的应用。如果没有把握它们的用法，会导致浏览源代码时很费解、很吃力。本文会给读者介绍源码中重要的数据结构，双向循环链表Doubly Linked List。在解说时，会联合数据结构相干绘图，造就读者们的数据结构的立体设想能力，帮忙更好的学习和了解这些数据结构的用法。
本文中所波及的源码，以OpenHarmony LiteOS-M内核为例，均能够在开源站点https://gitee.com/openharmony... 获取。
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)点击关注，第一工夫理解华为云陈腐技术~