LiteOS内核源码分析系列一 盘点那些重要的数据结构 (1)

举报
zhushy 发表于 2021/02/22 14:46:24 2021/02/22
【摘要】 在学习Huawei LiteOS源代码的时候,常常会遇到一些数据结构的使用。如果没有掌握这它们的用法,阅读LiteOS源代码的时候会很费解、很吃力。本文会给读者介绍下LiteOS源码中常用的几个数据结构,包括: 双向循环链表LOS_DL_LIST,优先级队列Priority Queue,排序链表SortLinkList等。在讲解时,会结合相关的绘图,培养数据结构的平面想象能力,帮助更好的学习和理解

LiteOS内核源码分析系列一 盘点那些重要的数据结构 -- DL

在学习Huawei LiteOS源代码的时候,常常会遇到一些数据结构的使用。如果没有掌握这它们的用法,阅读LiteOS源代码的时候会很费解、很吃力。本文会给读者介绍下LiteOS源码中常用的几个数据结构,包括: 双向循环链表LOS_DL_LIST,优先级队列Priority Queue,排序链表SortLinkList等。在讲解时,会结合相关的绘图,培养数据结构的平面想象能力,帮助更好的学习和理解这些数据结构用法。

本文中所涉及的LiteOS源码,均可以在LiteOS开源站点https://gitee.com/LiteOS/LiteOS 获取。

我们首先来看看使用最多的双向循环链表Doubly Linked List

1、LOS_DL_LIST 双向循环链表

双向链表LOS_DL_LIST核心的代码都在kernel\include\los_list.h头文件中,包含LOS_DL_LIST结构体定义、一些inline内联函数LOS_ListXXX,还有一些双向链表相关的宏定义LOS_DL_LIST_XXXX

双向链表源代码、示例程序代码、开发文档如下:

1.1 LOS_DL_LIST 双向链表结构体

双向链表结构体LOS_DL_LIST定义如下。看得出来,双向链表的结构非常简单、通用、抽象,只包含前驱、后继两个节点,负责承上启下的双向链表作用。双向链表不包任何业务数据信息,业务数据信息维护在业务的结构体中。双向链表作为业务结构体的成员使用,使用示例稍后会有讲述。

typedef struct LOS_DL_LIST {
    struct LOS_DL_LIST *pstPrev; /** 当前节点的指向前驱节点的指针 */
    struct LOS_DL_LIST *pstNext; /** 当前节点的指向后继节点的指针  */
} LOS_DL_LIST;

从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点,这种数据结构形式使得双向链表在查找、插入、删除等操作,对于非常方便。由于双向链表的环状结构,任何一个节点的地位都是平等的。从业务上,可以创建一个节点作为Head头节点,业务结构体的链表节点从HEAD节点开始挂载。从head节点的依次遍历下一个节点,最后一个不等于Head节点的节点称之为Tail尾节点。这个Tail节点也是Head节点的前驱。从Head向前查找,可以更快的找到Tail节点。

我们看看LiteOS内核代码中如何使用双向链表结构体的。下面是互斥锁结构体LosMuxCB定义,其中包含双向链表LOS_DL_LIST muxList;成员变量:

typedef struct {
    LOS_DL_LIST muxList; /** 互斥锁的双向链表*/
    LosTaskCB *owner; /** 当前持有锁的任务TCB */
    UINT16 muxCount; /** 持有互斥锁的次数 */
    UINT8 muxStat; /** 互斥锁状态OS_MUX_UNUSED, OS_MUX_USED */
    UINT32 muxId; /** 互斥锁handler ID*/
} LosMuxCB;

双向循环链表可以把各个互斥锁链接起来,链表和其他业务成员关系如下图所示:

LOS_DL_LIST.png

LiteOS的双向链表为用户提供下面初始化双向列表,增加、删除链表节点,判断节点是否为空,获取链表节点,获取链表所在的结构体,遍历双向链表,遍历包含双向链表的结构体等功能。我们一一来详细的学习、分析下代码。

1.2 LOS_DL_LIST 双向链表初始化


1.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)方法,把这个节点链接为环状的双向链表。初始化链表的时候,只有一个链表节点,这个节点的前序和后继节点都是自身。

链表节点初始化为链表,如图所示:

LOS_ListInit.png


源码如下:

LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListInit(LOS_DL_LIST *list)
{
    list->pstNext = list;
    list->pstPrev = list;
}

另外,还提供了一个宏LOS_DL_LIST_HEAD,直接定义一个双向链表节点并以该节点初始化为双向链表。

#define LOS_DL_LIST_HEAD(list) LOS_DL_LIST list = { &(list), &(list) }

1.2.2 LOS_ListEmpty(LOS_DL_LIST *list)

该接口用于判断链表是否为空。如果双向链表的前驱/后继节点均为自身,只有一个链表HEAD头节点,没有挂载业务结构体的链表节点,称该链表为空链表。

源码如下:

LITE_OS_SEC_ALW_INLINE STATIC INLINE BOOL LOS_ListEmpty(LOS_DL_LIST *list)
{
    return (BOOL)(list->pstNext == list);
}

1.3 LOS_DL_LIST 双向链表节点操作

LiteOS双向链表提供三种链表节点插入方法,指定链表节点后面插入LOS_ListAdd、尾部插入LOS_ListTailInsert、头部插入LOS_ListHeadInsert。在头部插入的节点,从头部开始遍历时第一个遍历到,从尾部插入的节点,最后一个遍历到。


1.3.1 LOS_ListAdd(LOS_DL_LIST *list, LOS_DL_LIST *node)

这个API接口往链表节点*list所在的双向链表中插入一个链表节点*node,插入位置在链表节点*list的后面。如图所示,完成插入后,*node的后继节点是list->pstNext*node的前序节点是*listlist->pstNext的前序节点是*node*list的后续是*node节点。

图示:

LOS_ListAdd.png


源码如下:

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;
}

1.3.2 LOS_ListTailInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)

这个API接口往链表节点*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);
}

1.3.3 LOS_ListHeadInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)

这个API接口和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);
}

LiteOS双向链表提供两种链表节点的删除方法,指定节点删除LOS_ListDelete、删除并初始化为一个新链表LOS_ListDelInit


1.3.4 LOS_ListDelete(LOS_DL_LIST *node)

这个API接口将链表节点*node从所在的双向链表中删除。节点删除后,可能需要调用Free()函数释放节点所占用的内存。如图所示,*node节点后继节点的前序改为*node的前序,*node节点前序节点的后续改为*node的后续,并把*node节点的前序、后续节点设置为null

图示:

LOS_ListDelete.png


源码如下:

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;
}

1.3.5 LOS_ListDelInit(LOS_DL_LIST *list)

这个API接口将链表节点*list从所在的双向链表中删除, 并把删除后的节点重新初始化为一个新的双向链表。

*list节点后继节点的前序改为*list的前序,*list节点前序节点的后续改为*list的后续。和LOS_ListDelete()方法不同的是,并不并把*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);
}

LiteOS双向链表还提供获取链表节点、获取包含链表的结构体地址的操作。

1.3.6 LOS_DL_LIST_LAST(object)

这个宏定义获取链表的前驱节点。

源码如下:

#define LOS_DL_LIST_LAST(object) ((object)->pstPrev)

1.3.7 LOS_DL_LIST_FIRST(object)

这个宏定义获取链表的后继节点。

源码如下:

#define LOS_DL_LIST_FIRST(object) ((object)->pstNext)

1.3.8 LOS_OFF_SET_OF(type, member)

这个宏定义根据结构体类型名称type和其中的成员变量名称member,获取member成员变量相对于结构体type的内存地址偏移量。在应用场景上,业务结构体包含双向链表作为成员,当知道双向链表成员变量的内存地址时,和这个偏移量,可以进一步获取业务结构体的内存地址。

源码如下:

#define LOS_OFF_SET_OF(type, member) ((UINTPTR)&((type *)0)->member)

1.3.9 LOS_DL_LIST_ENTRY(item, type, member)

根据业务结构体类型名称type、其中的双向链表成员变量名称member,和双向链表的内存指针变量item,使用该宏定义LOS_DL_LIST_ENTRY可以获取业务结构体的内存地址。

我们以实际例子演示下这个宏LOS_DL_LIST_ENTRY是如何使用的。互斥锁的control block结构体LosMuxCB在上文已经展示过其代码,有个双向链表的成员变量LOS_DL_LIST muxList。在创建互斥锁的方法LOS_MuxCreate()中,⑴ 处代码从空闲互斥锁链表中获取一个空闲的双向链表节点指针地址LOS_DL_LIST *unusedMux,把这个作为第一个参数,结构体名称LosMuxCB及其成员变量muxList,分别作为第二、第三个参数,使用宏LOS_DL_LIST_ENTRY可以计算出结构体的指针变量地址LosMuxCB *muxCreated,见⑵处代码。

LITE_OS_SEC_TEXT UINT32 LOS_MuxCreate(UINT32 *muxHandle)
{
    ......
    LosMuxCB *muxCreated = NULL;
    LOS_DL_LIST *unusedMux = NULL;
    ......
⑴  unusedMux = LOS_DL_LIST_FIRST(&g_unusedMuxList);
    LOS_ListDelete(unusedMux);
⑵  muxCreated = LOS_DL_LIST_ENTRY(unusedMux, LosMuxCB, muxList);
    ......
}

从这个例子上,就比较容易理解,这个宏定义可以用于什么样的场景,读者们可以阅读查看更多使用这个宏的例子,加强理解。

源码如下:

源码实现上,基于双向链表节点的内存地址,和双向链表成员变量在结构体中的地址偏移量,可以计算出结构体的内存地址。

#define LOS_DL_LIST_ENTRY(item, type, member) \
    ((type *)(VOID *)((CHAR *)(item) - LOS_OFF_SET_OF(type, member)))

1.4 LOS_DL_LIST 双向循环链表遍历

LiteOS双向循环链表提供两种遍历双向链表的方法,LOS_DL_LIST_FOR_EACHLOS_DL_LIST_FOR_EACH_SAFE

1.4.1 LOS_DL_LIST_FOR_EACH(item, list)

该宏定义LOS_DL_LIST_FOR_EACH遍历双向链表,接口的第一个入参表示的是双向链表节点的指针变量,在遍历过程中依次指向下一个链表节点。第二个入参是要遍历的双向链表的起始节点。这个宏是个循环条件部分,用户的业务代码写在宏后面的代码块{}内。

我们以实际例子来演示这个宏LOS_DL_LIST_FOR_EACH是如何使用的。在kernel\base\sched\sched_sq\los_priqueue.c文件中,UINT32 OsPriQueueSize(UINT32 priority)函数的片段如下:

&g_priQueueList[priority]是我们要遍历的双向链表,curNode指向遍历过程中的链表节点,见⑴处代码代码。完整代码请访问我们的开源站点。

UINT32 OsPriQueueSize(UINT32 priority)
{
    UINT32 itemCnt = 0;
    LOS_DL_LIST *curNode = NULL;
    ......
⑴  LOS_DL_LIST_FOR_EACH(curNode, &g_priQueueList[priority]) {
    ......
        task = OS_TCB_FROM_PENDLIST(curNode);
    ......
    }
    return itemCnt;
}

源码如下:

#define LOS_DL_LIST_FOR_EACH(item, list) \
    for (item = (list)->pstNext;         \
         (item) != (list);               \
         item = (item)->pstNext)

1.4.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)

1.5 LOS_DL_LIST 遍历包含双向链表的结构体

LiteOS双向链表提供三个宏定义来遍历包含双向链表成员的结构体,LOS_DL_LIST_FOR_EACH_ENTRYLOS_DL_LIST_FOR_EACH_ENTRY_SAFELOS_DL_LIST_FOR_EACH_ENTRY_HOOK

1.5.1 LOS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member)

该宏定义LOS_DL_LIST_FOR_EACH_ENTRY遍历双向链表,接口的第一个入参表示的是包含双向链表成员的结构体的指针变量,第二个入参是要遍历的双向链表的起始节点,第三个入参是要获取的结构体名称,第四个入参是在该结构体中的双向链表的成员变量名称。

我们以实际例子来演示这个宏LOS_DL_LIST_FOR_EACH_ENTRY是如何使用的。在kernel\base\sched\sched_sq\los_priqueue.c文件中,LosTaskCB *OsGetTopTask(VOID)函数的片段如下。结构体LosTaskCB包含双向链表成员变量pendList,&g_priQueueList[priority] 是对应任务优先级prioritypendList的双向链表。会依次遍历这个双向链表&g_priQueueList[priority],根据遍历到的链表节点,依次获取任务结构体LosTaskCB的指针变量newTask,如⑴处代码所示。

LITE_OS_SEC_TEXT_MINOR LosTaskCB *OsGetTopTask(VOID)
{
    UINT32 priority;
    UINT32 bitmap;
    LosTaskCB *newTask = NULL;
    ......
⑴  LOS_DL_LIST_FOR_EACH_ENTRY(newTask, &g_priQueueList[priority], LosTaskCB, pendList) {
        ......
        OsPriQueueDequeue(&newTask->pendList);
        ......
    }
    ......
}

源码如下:

源码实现上,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))

1.5.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))

1.5.3 LOS_DL_LIST_FOR_EACH_ENTRY_HOOK(item, list, type, member, hook)

该宏定义和LOS_DL_LIST_FOR_EACH_ENTRY的区别就是多了个入参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)

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。