摘要：本文会给读者介绍下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)办法，把这个节点链接为环状的双向链表。初始化链表的时候，只有一个链表节点，这个节点的前序和后继节点都是本身。
链表节点初始化为链表，如图所示：
源码如下：
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节点。
图示：
源码如下：
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。
图示：
源码如下：
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)函数
`ret = OsSortLinkInit(&g_percpu[index].taskSortLink);`kernelbaselos_swtmr.c : UINT32 OsSwtmrInit(VOID)函数
`ret = OsSortLinkInit(&g_percpu[cpuid].swtmrSortLink);`
咱们看下排序链表初始化函数的源代码，⑴处代码计算须要申请多少个双向链表的内存大小，对于单链表的排序链表，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到本人账户下，如下图，谢谢。
本文分享自华为云社区《LiteOS内核源码剖析系列一 盘点那些重要的数据结构 》，原文作者：zhushy 。
点击关注，第一工夫理解华为云陈腐技术~