更多内容请访问：Harmonyos.51cto.com，与华为官方共同打造的鸿蒙技术社区学习OpenHarmony鸿蒙时点亮内核源码代码中，我们经常会遇到一些数据结构的使用。如果不掌握它们的用法，会使阅读源码变得非常吃力和吃力。本文将为读者介绍源码中的重要数据结构——双向链表。讲解时会结合数据结构相关的图解，培养读者对数据结构的平面想象能力，帮助读者更好地学习和理解这些数据结构的用法。1、双向链表LOS_DL_LIST的源码在utils\los_list.h双向链表头文件中，包含了LOS_DL_LIST结构体的定义，内联函数LOS_ListXXX，以及相关的函数宏定义LOS_DL_LIST_XXXX。双向链表的头文件可以在网页utils/los_list.h中找到，也可以在本地查看阅读。1.1双向链表结构双向链表节点结构LOS_DL_LIST定义如下。它的结构非常简单、笼统和抽象。它只包含前驱和后继两个节点，负责连接前后的双向链表的作用。双向链表不包含任何业务数据信息，一般不单独使用。通常使用双向链表节点和业务数据信息作为结构成员，共同构成一个业务结构。稍后将描述使用示例。typedefstructLOS_DL_LIST{structLOS_DL_LIST*pstPrev;/**指向当前链表节点的前驱节点*/structLOS_DL_LIST*pstNext;/**指向当前链表节点的后继节点*/}LOS_DL_LIST;从中的任意节点开始双向链表，可以轻松访问其前驱节点和后继节点。这种环形数据结构形式使得双向链表在查找、插入、删除等操作中非常方便。当业务场景使用双向链表时，可以定义一个LOS_DL_LIST类型的全局变量作为双向循环链表的头节点，业务结构的链表成员节点依次挂载在头节点上。另外，将部分业务结构的双向链表节点作为Head节点，依次挂载其他业务结构的链表成员节点。从Head节点开始，可以依次遍历下一个节点，Head节点的前驱节点就是Tail尾节点。下面我们通过鸿蒙轻内核代码中互斥锁结构LosMuxCB的定义来了解如何使用双向链表结构：typedefstruct{UINT8muxStat;/**pstNext=list;list->pstPrev=list;}2.2LOS_DL_LIST_HEAD(LOS_DL_LISTlist)除了LOS_ListInit()之外，它还提供了一个功能宏LOS_DL_LIST_HEAD，通过直接定义一个双向链表节点，将节点初始化为双向链表，功能相同。与LOS_ListInit()不同的是，在调用功能宏之前不需要动态申请内存空间。#defineLOS_DL_LIST_HEAD(list)LOS_DL_LISTlist={&(list),&(list)}3空链表的判断3.1LOS_ListEmpty(LOS_DL_LIST*list)该内联函数用于判断链表是否为空。如果双向链表的前驱/后继节点都是自己，只有一个链节点，没有挂载业务结构的链表节点，则该链表称为空链表。源码如下：LITE_OS_SEC_ALW_INLINESTATIC_INLINEBOOLLOS_ListEmpty(LOS_DL_LIST*node){return(BOOL)(node->pstNext==node);}4插入双向链表节点双向链表提供了三种插入链表节点的方式，在指定链表节点后插入LOS_ListAdd，尾部插入LOS_ListTailInsert，头部插入LOS_ListHeadInsert。从头部开始遍历时先遍历头部插入的节点，最后遍历尾部插入的节点。4.1LOS_ListAdd(LOS_DL_LIST*list,LOS_DL_LIST*node)该内联函数在链表节点*list所在的双向链表中插入一个链表节点*node，插入位置在链表节点*list的后面。如图所示，在插入过程中，*node的后继节点会被设置为list->pstNext，*node的前驱节点为*list，list->pstNext的前驱节点由*listto*node，*list的后继节点从list->pstNext变为*node。说明：源码如下：LITE_OS_SEC_ALW_INLINESTATICINLINEVOIDLOS_ListAdd(LOS_DL_LIST*list,LOS_DL_LIST*node){node->pstNext=list->pstNext;node->pstPrev=list;list->pstNext->pstPrev=node;list->pstNext=node;}4.2LOS_ListTailInsert(LOS_DL_LIST*list,LOS_DL_LIST*node)该内联函数将一个链表节点*node插入到链表节点*list所在的双向链表中。插入位置在链表节点*list前面，后面是list->pstPrev节点。源码如下：LITE_OS_SEC_ALW_INLINESTATICINLINEVOIDLOS_ListTailInsert(LOS_DL_LIST*list,LOS_DL_LIST*node){LOS_ListAdd(list->pstPrev,node);}4.3LOS_ListHeadInsert(LOS_DL_LIST*list,LOS_DL_LIST*node)该内联函数实现了与LOS_ListAdd().在链表节点*list所在的双向链表中插入一个链表节点*node，插入位置在链表节点*list的后面。源码如下：LITE_OS_SEC_ALW_INLINESTATICINLINEVOIDLOS_ListHeadInsert(LOS_DL_LIST*list,LOS_DL_LIST*node){LOS_ListAdd(list,node);}5删除双向链表节点双向链表提供了两种删除链表节点的方式，删除指定节点LOS_ListDelete(),删除并初始化为一个新的链表LOS_ListDelInit()。5.1LOS_ListDelete(LOS_DL_LIST*node)该内联函数从双向链表中删除链表节点*node。一个节点被删除后，可能需要主动释放该节点占用的内存。如图所示，在删除一个节点的过程中，*node的后继节点的前驱会变成*node的前驱节点，*node的前驱节点的后继会变成*node的后继节点，而*node节点，后继节点设置为null，使*node节点从双向链表中分离出来。说明：源码如下：LITE_OS_SEC_ALW_INLINESTATICINLINEVOIDLOS_ListDelete(LOS_DL_LIST*node){node->pstNext->pstPrev=node->pstPrev;node->pstPrev->pstNext=node->pstNext;node->pstNext=NULL;node->pstPrev=NULL;}5.2LOS_ListDelInit(LOS_DL_LIST*list)该内联函数从双向链表中删除链表节点*list，并将删除的节点重新初始化为一个新的双向链表。与LOS_ListDelete()类似，该函数也会将*list的后继节点的前驱变为*list的前驱，将*list的前驱节点的后继变为*list的后继，不同的是它需要重新初始化为一个新的双向链表，所以该函数并没有将*list的前后节点设置为null，而是将删除的节点重新初始化为一个新的以*list为头节点的双向链表。源代码如下：提供获取链表节点和包含链表的结构体地址的操作。6.1LOS_DL_LIST_LAST(object)获取指定链表节点的前驱节点。源码如下：#defineLOS_DL_LIST_LAST(object)((object)->pstPrev)6.2LOS_DL_LIST_FIRST(object)获取指定链表节点的后继节点。源码如下：#defineLOS_DL_LIST_FIRST(object)((object)->pstNext)7遍历双向循环链表节点双向循环链表提供了两种遍历双向链表的方法，LOS_DL_LIST_FOR_EACH和LOS_DL_LIST_FOR_EACH_SAFE。7.1LOS_DL_LIST_FOR_EACH(item,list)该宏定义了LOS_DL_LIST_FOR_EACH遍历双向链表，将每次循环得到的链表节点保存在第一个入参中，第二个入参为待测双向链表的起始节点遍历。这个宏是一个for循环条件。在每次循环中，获取下一个链表节点并保存到输入参数项中。业务代码写在宏后面的代码块{}中。源码如下：#defineLOS_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(UINT32priority)函数的片段如下：++itemCnt;}returnitemCnt;}其中，(⑴)处的代码，g_losPriorityQueueList[priority]是一个待遍历的双向链表，curPQNode指向遍历过程中的链表节点。7.2LOS_DL_LIST_FOR_EACH_SAFE(item,next,list)宏定义LOS_DL_LIST_FOR_EACH_SAFE与LOS_DL_LIST_FOR_EACH的唯一区别在于多了一个入参next，表示遍历的双向链表节点的下一个节点。此宏用于安全删除。如果遍历的item被删除，不影响继续遍历。源码如下：#defineLOS_DL_LIST_FOR_EACH_SAFE(item,next,list)\for((item)=(list)->pstNext,(next)=(item)->pstNext;(item)!=(list);\(item)=(next),(next)=(item)->pstNext)8获取链表节点所在结构体8.1LOS_OFF_SET_OF(type,member)根据结构体类型名type和成员变量名member，获取成员变量相对于该结构类型的内存地址偏移量。在链表的应用场景中，业务结构中包含一个双向链表作为成员。当已知双向链表成员变量的内存地址和相对于业务结构的偏移量时，可以进一步得到业务结构的内存地址。LOS_DL_LIST_ENTRY的详细宏实现见下文。源码如下：#defineLOS_OFF_SET_OF(type,member)((UINTPTR)&((type*)0)->member)8.2LOS_DL_LIST_ENTRY(item,type,member)函数宏中的三个参数分别是：业务结构类型名类型，作为结构体成员的双向链表的成员变量名，作为结构体成员的双向链表的节点指针项。通过调用这个宏函数LOS_DL_LIST_ENTRY，可以得到双向链表节点所在业务结构的内存地址。源码如下：根据双向链表节点的内存地址和双向链表成员变量在结构体中的地址偏移，可以计算出结构体的内存地址。#defineLOS_DL_LIST_ENTRY(item,type,member)\((type*)(VOID*)((CHAR*)(item)-LOS_OFF_SET_OF(type,member)))9遍历包含双向链表的结构双向链表提供了三个macros定义为遍历包含双向链表成员的结构，LOS_DL_LIST_FOR_EACH_ENTRY，LOS_DL_LIST_FOR_EACH_ENTRY_SAFE和LOS_DL_LIST_FOR_EACH_ENTRY_HOOK。9.1LOS_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)->member!=(list)意思是当双向链表遍历一个圈到自己的节点时，循环停止。在循环update语句item=LOS_DL_LIST_ENTRY((item)->member.pstNext,type,member))中，使用(item)->member.pstNext遍历到下一个链表节点，然后根据获取对应的next结构指向该节点的指针变量item，直到遍历完成。#defineLOS_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.2LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item,next,list,type,member)这个宏定义和LOS_DL_LIST_FOR_EACH_ENTRY的唯一区别是多了一个入参next，表示要访问的结构体被遍历的下一个结构体。此宏用于安全删除。如果删除遍历的item，不影响遍历。源码如下：#defineLOS_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.3LOS_DL_LIST_FOR_EACH_ENTRY_HOOK(item,list,type,member,hook)这个宏定义和LOS_DL_LIST_FOR_EACH_ENTRY的区别在于多了一个入参hook，即钩子函数。在每个遍历周期中，都会调用钩子函数，实现用户任务的定制。源码如下：#defineLOS_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)总结掌握鸿蒙LightKernel的双向循环链表LOS_DL_LIST的重要数据结构，有助于大家进一步学习分析为鸿蒙LightKernel源码打下基础，让后续学习更轻松。后续会陆续推出更多分享文章，敬请期待。也欢迎大家分享学习和使用鸿蒙LightKernel的心得。如果您有任何问题或建议，可以给我们留言：https://gitee.com/openharmony/kernel_liteos_m/issues。为了更方便的找到鸿蒙轻内核代码仓库，推荐访问https://gitee.com/openharmony/kernel_liteos_m，关注Watch，点赞，Fork到自己的账号，谢谢。更多信息请访问：Harmonyos.51cto.com，与华为官方合作打造的鸿蒙技术社区
