LiteOS：盘点那些重要的数据结构

关注

发布于: 2021 年 02 月 23 日

摘要：本文会给读者介绍下 LiteOS 源码中常用的几个数据结构，包括: 双向循环链表 LOS_DL_LIST，优先级队列 Priority Queue，排序链表 SortLinkList 等。

在学习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核心的代码都在kernelincludelos_list.h头文件中，包含LOS_DL_LIST结构体定义、一些inline内联函数LOS_ListXXX，还有一些双向链表相关的宏定义LOS_DL_LIST_XXXX。

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

kernelincludelos_list.h 双向链表头文件网页获取源码 https://gitee.com/LiteOS/Lite...。
demoskernelapilos_api_list.c 双向链表 Demo 程序网页获取源码 https://gitee.com/LiteOS/Lite...。
开发指南双向链表文档在线文档https://gitee.com/LiteOS/Lite...

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;

复制代码

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

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的前序节点是*list。list->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_EACH和LOS_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是如何使用的。在kernelbaseschedsched_sqlos_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_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)

复制代码

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

LiteOS双向链表提供三个宏定义来遍历包含双向链表成员的结构体，LOS_DL_LIST_FOR_EACH_ENTRY、LOS_DL_LIST_FOR_EACH_ENTRY_SAFE和LOS_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是如何使用的。在kernelbaseschedsched_sqlos_priqueue.c文件中，LosTaskCB *OsGetTopTask(VOID)函数的片段如下。结构体LosTaskCB包含双向链表成员变量pendList,&g_priQueueList[priority] 是对应任务优先级priority的pendList的双向链表。会依次遍历这个双向链表&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.2LOS_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.3LOS_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)

复制代码

2、Priority Queue 优先级队列

在任务调度模块，就绪队列是个重要的数据结构，就绪队列需要支持初始化，出入队列，从队列获取最高优先级任务等操作。LiteOS调度模块支持单一就绪队列（Single Ready Queue）和多就绪队列（Multiple Ready Queue），我们这里主要讲述一下单一就绪队列。

优先级队列Priority Queue接口主要内部使用，用户业务开发时不涉及，不对外提供接口。优先级队列其实就是个双向循环链表数组，提供更加方便的接口支持任务基于优先级进行调度。

优先级队列核心的代码都在kernelbaseincludelos_priqueue_pri.h头文件和kernelbaseschedsched_sqlos_priqueue.c实现文件中。

我们来看看优先级队列支持的操作。

2.1 Priority Queue 优先级队列变量定义

LiteOS支持 32 个优先级，取值范围 0-31，优先级数值越小优先级越大。优先级队列在kernelbaseschedsched_sqlos_priqueue.c文件中定义的几个变量如下，

其中⑴表示优先级为 0 的位，⑵处表示优先级队列的双向链表数组，后文会初始化为数组的长度为 32，⑶表示优先级位图，标志哪些优先级就绪队列里有挂载的任务。

示意图如下：

优先级位图g_priQueueBitmap的 bit 位和优先级的关系是 bits=31-priority，g_priQueueList[priority]优先级数组内容为双向链表，挂载各个优先级的处于就绪状态的任务。

源码如下：

 #define OS_PRIORITY_QUEUE_NUM 32⑴ #define PRIQUEUE_PRIOR0_BIT   0x80000000U⑵ LITE_OS_SEC_BSS LOS_DL_LIST *g_priQueueList = NULL;⑶ STATIC LITE_OS_SEC_BSS UINT32 g_priQueueBitmap;

复制代码

下面我们来学习下优先级队列支持的那些操作。

2.2 Priority Queue 优先级队列接口

2.2.1 OsPriQueueInit(VOID)初始化

优先级队列初始化在系统初始化的时候调用：main.c:main(void)k-->kernelinitlos_init.c:OsMain(VOID)-->kernelbaselos_task.c:OsTaskInit(VOID)-->OsPriQueueInit()。

从下面的代码可以看出，⑴处申请长度为 32 的双向链表数值申请常驻内存，运行期间不会调用Free()接口释放。⑴处代码为数组的每一个双向链表元素都初始化为双向循环链表。

源码如下：

UINT32 OsPriQueueInit(VOID){    UINT32 priority;    /* 系统常驻内存，运行期间不会Free释放 */⑴  g_priQueueList = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, (OS_PRIORITY_QUEUE_NUM * sizeof(LOS_DL_LIST)));    if (g_priQueueList == NULL) {        return LOS_NOK;    }    for (priority = 0; priority < OS_PRIORITY_QUEUE_NUM; ++priority) {⑵      LOS_ListInit(&g_priQueueList[priority]);    }    return LOS_OK;}

复制代码

2.2.2 OsPriQueueEnqueueHead()插入就绪队列头部

OsPriQueueEnqueueHead()从就绪队列的头部进行插入，插入得晚，但在同等优先级的任务中，会第一个调度。一起看下代码，⑴处先判断指定优先级priority的就绪队列是否为空，如果为空，则在⑵处更新优先级位图。⑶处把就绪状态的任务插入就绪队列的头部，以便优先调度。

源码如下：

VOID OsPriQueueEnqueueHead(LOS_DL_LIST *priqueueItem, UINT32 priority){    LOS_ASSERT(priqueueItem->pstNext == NULL);⑴  if (LOS_ListEmpty(&g_priQueueList[priority])) {⑵      g_priQueueBitmap |= PRIQUEUE_PRIOR0_BIT >> priority;    }⑶  LOS_ListHeadInsert(&g_priQueueList[priority], priqueueItem);}

复制代码

2.2.3 OsPriQueueEnqueue()插入就绪队列尾部

和OsPriQueueEnqueueHead()的区别是，把就绪状态的任务插入就绪队列的尾部，同等优先级的任务中，后插入的后调度。

2.2.4 OsPriQueueDequeue()就绪队列中删除

在任务被删除、进入suspend状态，优先级调整等场景时，都需要调用接口OsPriQueueEnqueue()把任务从优先级队列中删除。

我们来看下代码，⑴把任务从优先级就绪队列中删除。⑵获取删除的任务TCB信息，用来获取任务的优先级。刚从优先级队列中删除了一个任务，⑶处代码判断优先级队列是否为空，

如果为空，则需要执行⑷处代码，把优先级位图中对应的优先级bit位置为 0。

源码如下：

VOID OsPriQueueDequeue(LOS_DL_LIST *priqueueItem){    LosTaskCB *runTask = NULL;⑴  LOS_ListDelete(priqueueItem);⑵  runTask = LOS_DL_LIST_ENTRY(priqueueItem, LosTaskCB, pendList);⑶  if (LOS_ListEmpty(&g_priQueueList[runTask->priority])) {⑷      g_priQueueBitmap &= ~(PRIQUEUE_PRIOR0_BIT >> runTask->priority);    }}

复制代码

2.2.5 LOS_DL_LIST *OsPriQueueTop(VOID)获取就绪的优先级最高的链表节点

这个接口可以获取优先级就绪队列中优先级最高的链表节点。⑴处判断优先级位图g_priQueueBitmap是否为 0，如果为 0，说明没有任何就绪状态的任务，返回 NULL。 ⑵处计算g_priQueueBitmap二进制时开头的 0 的数目，这个数目对应于

任务的优先级priority，然后⑶处从&g_priQueueList[priority]优先级队列链表中获取第一个链表节点。

源码如下：

LOS_DL_LIST *OsPriQueueTop(VOID){    UINT32 priority;⑴  if (g_priQueueBitmap != 0) {⑵      priority = CLZ(g_priQueueBitmap);⑶      return LOS_DL_LIST_FIRST(&g_priQueueList[priority]);    }    return NULL;}

复制代码

2.2.6 UINT32 OsPriQueueSize(UINT32 priority)获取指定优先级的就绪任务的数量

这个接口可以获取指定优先级的就绪队列中任务的数量。⑴、⑶处代码表示，在SMP多核模式下，根据获取的当前 CPU 编号的cpuId，判断任务是否属于当前 CPU 核，如果不属于，则不计数。⑵处代码使用for循环遍历指定优先级就绪队列中的链表节点，对遍历到新节点则执行⑷处代码，对计数进行进行加 1 操作。

源码如下：

 UINT32 OsPriQueueSize(UINT32 priority)    {        UINT32 itemCnt = 0;        LOS_DL_LIST *curNode = NULL;    #ifdef LOSCFG_KERNEL_SMP        LosTaskCB *task = NULL;⑴      UINT32 cpuId = ArchCurrCpuid();    #endif        LOS_ASSERT(ArchIntLocked());        LOS_ASSERT(LOS_SpinHeld(&g_taskSpin));⑵      LOS_DL_LIST_FOR_EACH(curNode, &g_priQueueList[priority]) {    #ifdef LOSCFG_KERNEL_SMP            task = OS_TCB_FROM_PENDLIST(curNode);⑶          if (!(task->cpuAffiMask & (1U << cpuId))) {                continue;            }    #endif⑷          ++itemCnt;        }        return itemCnt;    }

复制代码

2.2.7 LosTaskCB *OsGetTopTask(VOID)获取就绪的优先级最高的任务

这个接口或者就绪任务队列中优先级最高的任务。一起看下代码，⑴、⑷处对SMP多核做特殊处理，如果是多核，只获取指定在当前 CPU 核运行的优先级最高的任务。⑵处获取g_priQueueBitmap优先级位图的值，赋值给UINT32 bitmap;。不直接操作优先级位图的原因是什么呢？在SMP多核时，在高优先级任务就绪队列里没有找到指定在当前 CPU 核运行的任务，需要执行⑹处的代码，清零临时优先级位图的 bit 位，去低一级的优先级就绪队列里去查找。只能改动临时优先级位图，不能改变g_priQueueBitmap。⑶处代码对优先级最高的就绪队列进行遍历，如果遍历到则执行⑸处代码从优先级就绪队列里出队，函数返回对应的LosTaskCB *newTask。

源码如下：

 {        UINT32 priority;        UINT32 bitmap;        LosTaskCB *newTask = NULL;    #ifdef LOSCFG_KERNEL_SMP⑴      UINT32 cpuid = ArchCurrCpuid();    #endif⑵      bitmap = g_priQueueBitmap;        while (bitmap) {            priority = CLZ(bitmap);⑶          LOS_DL_LIST_FOR_EACH_ENTRY(newTask, &g_priQueueList[priority], LosTaskCB, pendList) {    #ifdef LOSCFG_KERNEL_SMP⑷              if (newTask->cpuAffiMask & (1U << cpuid)) {    #endif⑸                  OsPriQueueDequeue(&newTask->pendList);                    goto OUT;    #ifdef LOSCFG_KERNEL_SMP                }    #endif            }⑹          bitmap &= ~(1U << (OS_PRIORITY_QUEUE_NUM - priority - 1));        }    OUT:        return newTask;    }

复制代码

3、SortLinkList 排序链表

SortLinkList是LiteOS另外一个比较重要的数据结构，它在LOS_DL_LIST双向链表结构体的基础上，增加了RollNum滚动数，用于涉及时间到期、超时的业务场景。在阻塞任务是否到期，定时器是否超时场景下，非常依赖SortLinkList排序链表这个数据结构。LiteOS排序链表支持单一链表LOSCFG_BASE_CORE_USE_SINGLE_LIST和多链表LOSCFG_BASE_CORE_USE_MULTI_LIST，可以通过LiteOS的menuconfig工具更改Sortlink Option选项来配置使用单链表还是多链表，我们这里先讲述前者。

排序链表SortLinkList接口主要内部使用，用户业务开发时不涉及，不对外提供接口。SortLinkList排序链表的代码都在kernelbaseincludelos_sortlink_pri.h头文件和kernelbaselos_sortlink.c实现文件中。

3.1 SortLinkList 排序链表结构体定义

在kernelbaseincludelos_sortlink_pri.h文件中定义了两个结构体，如下述源码所示。

SortLinkAttribute结构体定义排序链表的头结点LOS_DL_LIST *sortLink，游标UINT16 cursor。SortLinkList结构体定义排序链表的业务节点，除了负责双向链接的成员变量LOS_DL_LIST *sortLink，还包括业务信息，UINT32 idxRollNum，即index索引和rollNum滚动数。在单链表的排序链表中，idxRollNum表示多长时间后会到期。

我们举个例子，看下面的示意图。排序链表中，有 3 个链表节点，分别在 25 ticks、35 ticks、50 ticks 后到期超时，已经按到期时间进行了先后排序。三个节点的idxRollNum分别等于 25 ticks、10

ticks、15 ticks。每个节点的idxRollNum保存的不是这个节点的超时时间，而是从链表head节点到该节点的所

有节点的idxRollNum的加和，才是该节点的超时时间。这样设计的好处就是，随着Tick时间推移，只需要更新第一个节点的超时时间就好，可以好好体会一下。

示意图如下：

源码如下：

typedef struct {    LOS_DL_LIST sortLinkNode;    UINT32 idxRollNum;} SortLinkList;
typedef struct {    LOS_DL_LIST *sortLink;    UINT16 cursor;    UINT16 reserved;} SortLinkAttribute;

复制代码

下面我们来学习下排序链表支持的那些操作。

3.2 SortLinkList 排序链表接口

在继续之前我们先看下kernelbaseincludelos_sortlink_pri.h文件中的一些单链表配置LOSCFG_BASE_CORE_USE_SINGLE_LIST下的宏定义，包含滚动数最大值等，对滚动数进行加、减、减少 1 等操作。

源码如下：

#define OS_TSK_SORTLINK_LOGLEN  0U#define OS_TSK_SORTLINK_LEN     1U#define OS_TSK_MAX_ROLLNUM      0xFFFFFFFEU#define OS_TSK_LOW_BITS_MASK    0xFFFFFFFFU#define SORTLINK_CURSOR_UPDATE(CURSOR)#define SORTLINK_LISTOBJ_GET(LISTOBJ, SORTLINK)  (LISTOBJ = SORTLINK->sortLink)#define ROLLNUM_SUB(NUM1, NUM2)         NUM1 = (ROLLNUM(NUM1) - ROLLNUM(NUM2))#define ROLLNUM_ADD(NUM1, NUM2)         NUM1 = (ROLLNUM(NUM1) + ROLLNUM(NUM2))#define ROLLNUM_DEC(NUM)                NUM = ((NUM) - 1)#define ROLLNUM(NUM)                    (NUM)#define SET_SORTLIST_VALUE(sortList, value) (((SortLinkList *)(sortList))->idxRollNum = (value))

复制代码

3.2.1 UINT32 OsSortLinkInit() 排序链表初始化

在系统启动软件初始化，初始化任务、初始化定时器时，会分别初始化任务的排序链表和定时器的排序链表。

kernelbaselos_task.c : UINT32 OsTaskInit(VOID)函数
kernelbaselos_swtmr.c : UINT32 OsSwtmrInit(VOID)函数

我们看下排序链表初始化函数的源代码，⑴处代码计算需要申请多少个双向链表的内存大小，对于单链表的排序链表，OS_TSK_SORTLINK_LOGLEN为 0，为一个双向链表申请内存大小即可。然后申请内存，初始化申请的内存区域为 0 等，⑵处把申请的双向链表节点赋值给sortLinkHeader的链表节点，作为排序链表的头节点，然后调用LOS_ListInit()函数初始化为双向循环链表。

源码如下：

LITE_OS_SEC_TEXT_INIT UINT32 OsSortLinkInit(SortLinkAttribute *sortLinkHeader){    UINT32 size;    LOS_DL_LIST *listObject = NULL;
⑴  size = sizeof(LOS_DL_LIST) << OS_TSK_SORTLINK_LOGLEN;    listObject = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, size); /* system resident resource */    if (listObject == NULL) {        return LOS_NOK;    }
    (VOID)memset_s(listObject, size, 0, size);⑵  sortLinkHeader->sortLink = listObject;    LOS_ListInit(listObject);    return LOS_OK;}

复制代码

3.2.2 VOID OsAdd2SortLink() 排序链表插入

在任务等待互斥锁、信号量等资源阻塞时，定时器启动时，这些需要等待指定时间的任务、定时器等，都会加入对应的排序链表。

我们一起看下代码，包含 2 个参数，第一个参数sortLinkHeader用于指定排序链表的头结点，第二个参数sortList是待插入的链表节点，此时该节点的滚动数等于对应阻塞任务或定时器的超时时间。

⑴处代码处理滚动数超大的场景，如果滚动数大于OS_TSK_MAX_ROLLNUM，则设置滚动数等于OS_TSK_MAX_ROLLNUM。⑵处代码，如果排序链表为空，则把链表节点尾部插入。如果排序链表不为空，则执行⑶处代码，获取排序链表上的下一个节点SortLinkList *listSorted。⑷、⑸ 处代码，如果待插入节点的滚动数大于排序链表的下一个节点的滚动数，则把待插入节点的滚动数减去下一个节点的滚动数，并继续执行⑹处代码，继续与下下一个节点进行比较。否则，如果待插入节点的滚动数小于排序链表的下一个节点的滚动数，则把下一个节点的滚动数减去待插入节点的滚动数，然后跳出循环，继续执行⑺处代码，完成待插入节点的插入。插入过程，可以结合上文的示意图进行理解。

源码如下：

LITE_OS_SEC_TEXT VOID OsAdd2SortLink(const SortLinkAttribute *sortLinkHeader, SortLinkList *sortList){    SortLinkList *listSorted = NULL;    LOS_DL_LIST *listObject = NULL;⑴  if (sortList->idxRollNum > OS_TSK_MAX_ROLLNUM) {        SET_SORTLIST_VALUE(sortList, OS_TSK_MAX_ROLLNUM);    }    listObject = sortLinkHeader->sortLink;⑵  if (listObject->pstNext == listObject) {        LOS_ListTailInsert(listObject, &sortList->sortLinkNode);    } else {⑶      listSorted = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode);        do {⑷          if (ROLLNUM(listSorted->idxRollNum) <= ROLLNUM(sortList->idxRollNum)) {                ROLLNUM_SUB(sortList->idxRollNum, listSorted->idxRollNum);            } else {⑸              ROLLNUM_SUB(listSorted->idxRollNum, sortList->idxRollNum);                break;            }
⑹         listSorted = LOS_DL_LIST_ENTRY(listSorted->sortLinkNode.pstNext, SortLinkList, sortLinkNode);        } while (&listSorted->sortLinkNode != listObject);
⑺      LOS_ListTailInsert(&listSorted->sortLinkNode, &sortList->sortLinkNode);    }}

复制代码

3.2.3 VOID OsDeleteSortLink() 排序链表删除

当任务恢复、删除，定时器停止的时候，会从对应的排序链表中删除。

我们一起阅读下删除函数的源代码，包含 2 个参数，第一个参数sortLinkHeader用于指定排序链表的头结点，第二个参数sortList是待删除的链表节点。

⑴处是获取排序链表的头结点listObject，⑵处代码检查要删除的节点是否在排序链表里，否则输出错误信息和回溯栈信息。⑶处代码判断是否排序链表里只有一个业务节点，如果只有一个节点，直接执行⑸处代码删除该节点即可。如果排序链表里有多个业务节点，则执行⑷处代码获取待删除节点的下一个节点nextSortList，把删除节点的滚动数加到下一个节点的滚动数里，然后执行⑸处代码执行删除操作。

源码如下：

LITE_OS_SEC_TEXT VOID OsDeleteSortLink(const SortLinkAttribute *sortLinkHeader, SortLinkList *sortList){    LOS_DL_LIST *listObject = NULL;    SortLinkList *nextSortList = NULL;
⑴  listObject = sortLinkHeader->sortLink;
⑵  OsCheckSortLink(listObject, &sortList->sortLinkNode);
⑶  if (listObject != sortList->sortLinkNode.pstNext) {⑷      nextSortList = LOS_DL_LIST_ENTRY(sortList->sortLinkNode.pstNext, SortLinkList, sortLinkNode);        ROLLNUM_ADD(nextSortList->idxRollNum, sortList->idxRollNum);    }⑸  LOS_ListDelete(&sortList->sortLinkNode);}

复制代码

3.2.4 UINT32 OsSortLinkGetNextExpireTime() 获取下一个超时到期时间

在Tickless特性，会使用此方法获取下一个超时到期时间。

我们一起阅读下源代码，包含 1 个参数，sortLinkHeader用于指定排序链表的头结点。

⑴处是获取排序链表的头结点listObject，⑵处代码判断排序链表是否为空，如果排序链表为空，则返回OS_INVALID_VALUE。如果链表不为空，⑶处代码获取排序链表的第一个业务节点，然后获取其滚动数，即过期时间，进行返回。

源码如下：

LITE_OS_SEC_TEXT UINT32 OsSortLinkGetNextExpireTime(const SortLinkAttribute *sortLinkHeader){    UINT32 expireTime = OS_INVALID_VALUE;    LOS_DL_LIST *listObject = NULL;    SortLinkList *listSorted = NULL;
⑴  listObject = sortLinkHeader->sortLink;⑵  if (!LOS_ListEmpty(listObject)) {⑶      listSorted = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode);        expireTime = listSorted->idxRollNum;    }    return expireTime;}

复制代码

3.2.5 OsSortLinkGetTargetExpireTime() 获取指定节点的超时时间

定时器获取剩余超时时间函数LOS_SwtmrTimeGet()会调用函数OsSortLinkGetTargetExpireTime() 获取指定节点的超时时间。

我们一起看下代码，包含 2 个参数，第一个参数sortLinkHeader用于指定排序链表的头结点，第二个参数targetSortList是待获取超时时间的目标链表节点。

⑴处代码获取目标节点的滚动数。⑵处代码获取排序链表的头结点listObject，⑶处代码获取排序链表上的下一个节点SortLinkList *listSorted。⑷处循环代码，当下一个节点不为目标链表节点的时候，依次循环，并执行⑸处代码把循环遍历的各个节点的滚动数相加，最终的计算结果即为目标节点的超时时间。

源码如下：

LITE_OS_SEC_TEXT_MINOR UINT32 OsSortLinkGetTargetExpireTime(const SortLinkAttribute *sortLinkHeader,                                                            const SortLinkList *targetSortList){    SortLinkList *listSorted = NULL;    LOS_DL_LIST *listObject = NULL;⑴  UINT32 rollNum = targetSortList->idxRollNum;
⑵  listObject = sortLinkHeader->sortLink;⑶  listSorted = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode);
⑷  while (listSorted != targetSortList) {⑸      rollNum += listSorted->idxRollNum;        listSorted = LOS_DL_LIST_ENTRY((listSorted->sortLinkNode).pstNext, SortLinkList, sortLinkNode);    }
    return rollNum;}

复制代码

3.2.6 VOID OsSortLinkUpdateExpireTime() 更新超时时间

在Tickless特性，会使用此方法更新超时时间。Tickless休眠sleep时，需要把休眠的ticks数目从排序链表里减去。调用此方法的函数会保障减去的ticks数小于节点的滚动数。

我们一起阅读下源代码，包含 2 个参数，第一个参数sleepTicks是休眠的ticks数，第二个参数sortLinkHeader用于指定排序链表的头结点。

⑴处获取排序链表的头结点listObject，⑵处代码获取下一个链表节点sortList，这个也是排序链表的第一个业务节点，然后把该节点的滚动数减去sleepTicks - 1完成超时时间更新。

源码如下：

LITE_OS_SEC_TEXT VOID OsSortLinkUpdateExpireTime(UINT32 sleepTicks, SortLinkAttribute *sortLinkHeader){    SortLinkList *sortList = NULL;    LOS_DL_LIST *listObject = NULL;
    if (sleepTicks == 0) {        return;    }
⑴  listObject = sortLinkHeader->sortLink;⑵  sortList = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode);    ROLLNUM_SUB(sortList->idxRollNum, sleepTicks - 1);}

复制代码

3.3 SortLinkList 排序链表和 Tick 时间关系

任务、定时器加入排序链表后，随时时间推移，一个tick一个tick的逝去，排序链表中的滚动数是如何更新的呢？

我们看看Tick中断的处理函数VOID OsTickHandler(VOID)，该函数在kernelbaselos_tick.c文件里。

当时间每走过一个tick，会调用该中断处理函数，代码片段中的⑴、⑵处的代码分别扫描任务和定时器，检查和更新时间。

LITE_OS_SEC_TEXT VOID OsTickHandler(VOID){    UINT32 intSave;
    TICK_LOCK(intSave);    g_tickCount[ArchCurrCpuid()]++;    TICK_UNLOCK(intSave);    ......⑴  OsTaskScan(); /* task timeout scan */
#if (LOSCFG_BASE_CORE_SWTMR == YES)⑵  OsSwtmrScan();#endif}

复制代码

我们以OsTaskScan()为例，快速了解下排序链表和tick时间的关系。函数在kernelbaselos_task.c文件中，函数代码片段如下：

⑴处代码获取任务排序链表的第一个节点，然后执行下一行代码把该节点的滚动数减去 1。⑵处代码循环遍历排序链表，如果滚动数为 0，即时间到期了，会调用LOS_ListDelete()函数从从排序链表中删除，然后执行⑶处代码，获取对应的taskCB，然后进一步进行业务处理。读者可以自行查看更多代码，后续的文章中也会对任务、定时器进行专题进行讲解。

LITE_OS_SEC_TEXT VOID OsTaskScan(VOID){    SortLinkList *sortList = NULL;    ......    LOS_DL_LIST *listObject = NULL;    SortLinkAttribute *taskSortLink = NULL;
    taskSortLink = &OsPercpuGet()->taskSortLink;    SORTLINK_CURSOR_UPDATE(taskSortLink->cursor);    SORTLINK_LISTOBJ_GET(listObject, taskSortLink);    ......⑴  sortList = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode);    ROLLNUM_DEC(sortList->idxRollNum);
⑵  while (ROLLNUM(sortList->idxRollNum) == 0) {        LOS_ListDelete(&sortList->sortLinkNode);⑶      taskCB = LOS_DL_LIST_ENTRY(sortList, LosTaskCB, sortList);         ......        sortList = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode);    }    ......}

复制代码

小结

掌握LiteOS内核的双向循环链表LOS_DL_LIST，优先级队列Priority Queue，排序链表SortLinkList等重要的数据结构，给进一步学习、分析LiteOS源代码打下了基础，让后续的学习更加容易。后续也会陆续推出更多的分享文章，敬请期待，也欢迎大家分享学习使用 LiteOS 的心得，有任何问题、建议，都可以留言给我们： https://gitee.com/LiteOS/Lite... 。为了更容易找到LiteOS代码仓，建议访问 https://gitee.com/LiteOS/LiteOS ，关注Watch、点赞Star、并Fork到自己账户下，如下图，谢谢。

LOS_STAR.png

本文分享自华为云社区《LiteOS 内核源码分析系列一盘点那些重要的数据结构》，原文作者：zhushy 。

点击关注，第一时间了解华为云新鲜技术~

发布于: 2021 年 02 月 23 日阅读数: 14

原文链接:【http://xie.infoq.cn/article/bb76fd3bc22f5ddcfe2ea7144】。文章转载请联系作者。

华为云开发者社区

关注

提供全面深入的云计算技术干货 2020.07.14 加入

华为云开发者社区，提供全面深入的云计算前景分析、丰富的技术干货、程序样例，分享华为云前沿资讯动态，方便开发者快速成长与发展，欢迎提问、互动，多方位了解云计算！传送门：https://bbs.huaweicloud.com/

发布

暂无评论

创作场景

LiteOS：盘点那些重要的数据结构

1、LOS_DL_LIST 双向循环链表

1.1 LOS_DL_LIST 双向链表结构体

1.2 LOS_DL_LIST 双向链表初始化

1.2.1 LOS_ListInit(LOS_DL_LIST *list)

1.2.2 LOS_ListEmpty(LOS_DL_LIST *list)

1.3 LOS_DL_LIST 双向链表节点操作

1.3.1 LOS_ListAdd(LOS_DL_LIST list, LOS_DL_LIST node)

1.3.2 LOS_ListTailInsert(LOS_DL_LIST list, LOS_DL_LIST node)

1.3.3 LOS_ListHeadInsert(LOS_DL_LIST list, LOS_DL_LIST node)

1.3.4 LOS_ListDelete(LOS_DL_LIST *node)

1.3.5 LOS_ListDelInit(LOS_DL_LIST *list)

1.3.6 LOS_DL_LIST_LAST(object)

1.3.7 LOS_DL_LIST_FIRST(object)

1.3.8 LOS_OFF_SET_OF(type, member)

1.3.9 LOS_DL_LIST_ENTRY(item, type, member)

1.4 LOS_DL_LIST 双向循环链表遍历

1.4.1 LOS_DL_LIST_FOR_EACH(item, list)

1.4.2 LOS_DL_LIST_FOR_EACH_SAFE(item, next, list)

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

1.5.1 LOS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member)

1.5.2LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member)

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

2、Priority Queue 优先级队列

2.1 Priority Queue 优先级队列变量定义

2.2 Priority Queue 优先级队列接口

2.2.1 OsPriQueueInit(VOID)初始化

2.2.2 OsPriQueueEnqueueHead()插入就绪队列头部

2.2.3 OsPriQueueEnqueue()插入就绪队列尾部

2.2.4 OsPriQueueDequeue()就绪队列中删除

2.2.5 LOS_DL_LIST *OsPriQueueTop(VOID)获取就绪的优先级最高的链表节点

2.2.6 UINT32 OsPriQueueSize(UINT32 priority)获取指定优先级的就绪任务的数量

2.2.7 LosTaskCB *OsGetTopTask(VOID)获取就绪的优先级最高的任务

3、SortLinkList 排序链表

3.1 SortLinkList 排序链表结构体定义

3.2 SortLinkList 排序链表接口

3.2.1 UINT32 OsSortLinkInit() 排序链表初始化

3.2.2 VOID OsAdd2SortLink() 排序链表插入

3.2.3 VOID OsDeleteSortLink() 排序链表删除

3.2.4 UINT32 OsSortLinkGetNextExpireTime() 获取下一个超时到期时间

3.2.5 OsSortLinkGetTargetExpireTime() 获取指定节点的超时时间

3.2.6 VOID OsSortLinkUpdateExpireTime() 更新超时时间

3.3 SortLinkList 排序链表和 Tick 时间关系

小结

华为云开发者社区

评论