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_EACHLOS_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_SAFELOS_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_ENTRYLOS_DL_LIST_FOR_EACH_ENTRY_SAFELOS_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的区别就是多了一个入参hookhook表示钩子函数。在每次遍历循环中,会调用该钩子函数,实现用户任务的定制。

源码如下:

#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 开发的内容,不妨可以参考以下相关学习文档进行学习,助你快速提升自己:

OpenHarmony 开发环境搭建:https://qr18.cn/CgxrRy

《OpenHarmony源码解析》:https://qr18.cn/CgxrRy

系统架构分析:https://qr18.cn/CgxrRy

OpenHarmony 设备开发学习手册:https://qr18.cn/CgxrRy

在这里插入图片描述

OpenHarmony面试题(内含参考答案):https://qr18.cn/CgxrRy

data-report-view="{"mod":"1585297308_001","spm":"1001.2101.3001.6548","dest":"https://blog.csdn.net/maniuT/article/details/139455447","extend1":"pc","ab":"new"}">>
注:本文转载自blog.csdn.net的沧海一笑-dj的文章"https://blog.csdn.net/dengjin20104042056/article/details/97962008"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接

评论记录:

未查询到任何数据!