LiteOS：盘点那些重要的数据结构_飞道的博客

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

2021-02-25 17:18 377人阅读评论(0)

摘要：本文会给读者介绍下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 。

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

转载：https://blog.csdn.net/devcloud/article/details/113988221

查看评论

飞道的博客

飞道的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章