共计 7665 个字符，预计需要花费 20 分钟才能阅读完成。
摘要：双向链表 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)点击关注，第一工夫理解华为云陈腐技术~
