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;
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
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);
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
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);
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
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;
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
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);
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
6 获取双向链表节点
双向链表还提供获取链表节点、获取包含链表的结构体地址的操作。
6.1 LOS_DL_LIST_LAST(object)
获取指定链表节点的前驱节点。
源码如下:
#define LOS_DL_LIST_LAST(object) ((object)->pstPrev)
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
6.2 LOS_DL_LIST_FIRST(object)
获取指定链表节点的后继节点。
源码如下:
#define LOS_DL_LIST_FIRST(object) ((object)->pstNext)
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
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)
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
我们以实例演示如何使用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;
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
其中⑴处代码,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)
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
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)
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
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)))
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
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))
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
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))
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
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)
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
小结
掌握鸿蒙轻内核的双向循环链表LOS_DL_LIST
这一重要的数据结构,会给进一步学习、分析鸿蒙轻内核源代码打下了基础,让后续的学习更加容易。
如果大家想更加深入的学习 OpenHarmony 开发的内容,不妨可以参考以下相关学习文档进行学习,助你快速提升自己:

- 搭建开发环境
- Windows 开发环境的搭建
- Ubuntu 开发环境搭建
- Linux 与 Windows 之间的文件共享
- ……

- 构建子系统
- 启动流程
- 子系统
- 分布式任务调度子系统
- 分布式通信子系统
- 驱动子系统
- ……



data-report-view="{"mod":"1585297308_001","spm":"1001.2101.3001.6548","dest":"https://blog.csdn.net/maniuT/article/details/139455447","extend1":"pc","ab":"new"}">>
评论记录:
回复评论: