鸿蒙内核源码分析：双向循环链表

作者| 深入研究鸿蒙，鸿蒙内核爱好者

出品 | CSDN（ID：CSDNnews）

为什么鸿蒙内核源码分析系列开头提到了LOS_DL_LIST？

因为它在鸿蒙LOS内核中无处不在，可以说在整个内核中占有巨大的比重。 它基本上像胶水一样将所有结构粘在一起。 毫不夸张的说，理解LOS_DL_LIST及相关函数，是阅读理解鸿蒙内核的关键。 前后指针如同人的左右手一样灵活，指挥着系统的精准运转。 对内核源码分析得越深入，越能体会到内核开发者对LOS_DL_LIST超凡的把控能力。 作者仿佛看到了无数只手来回连接，拉出无数个双向循环链表，将指针的魔力发挥到了极致。 这可能就是编程的艺术！

向鸿蒙内核的开发者致敬，鸿蒙内核的源代码可以作为大学操作系统和数据结构两门课程的教学项目。

/** * @ingroup los_list * Structure of a node in a doubly linked list. */
typedef struct LOS_DL_LIST {  struct LOS_DL_LIST *pstPrev; /**< Current node's pointer to the previous node */  struct LOS_DL_LIST *pstNext; /**< Current node's pointer to the next node */} LOS_DL_LIST;
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListInit(LOS_DL_LIST *list){  list->pstNext = list;  list->pstPrev = list;}

真的无处不在吗？ A: 是的，看看使用它的源代码，到处都是。

基本概念

双向链表是指包含前向和后向的链表，即每个节点除了存储下一个节点指针外，还添加一个指向其前一个节点的指针。 它的头指针头是唯一确定的。

从双向链表中的任意一个节点开始，可以很容易地访问到它的前驱节点和后继节点。 这种数据结构使得双向链表的查找更加方便，特别是对于大数据量的遍历。 由于双向链表的对称性，可以轻松完成插入、删除等各种操作，但需要注意前后方向的操作。

功能接口

Huawei LiteOS系统中的双向链表模块为用户提供了如下接口。

功能分类

接口名称

描述

初始化链表

LOS_ListInit

初始化链表。

增加节点

LOS_ListAdd

向链表中添加一个新节点。

在链表的末尾插入一个节点

LOS_ListTailInsert

在双向链表的末尾插入节点。

删除节点

LOS_List删除

从链表中删除指定的节点。

检查双向链表是否为空

LOS_ListEmpty

检查链表是否为空。

删除节点并初始化链表

LOS_ListDelInit

从链表中删除指定节点，并用该节点初始化链表。

将链表插入链表

LOS_ListAddList

将两个循环链表合并为一个大的循环链表

从末尾插入节点

LOS_ListTailInsert

(LOS_DL_LIST *列表, LOS_DL_LIST *节点)

从头部插入节点

LOS_ListHeadInsert

(LOS_DL_LIST *列表, LOS_DL_LIST *节点)

从链表末尾插入

LOS_ListTailInsertList

(LOS_DL_LIST *oldList, LOS_DL_LIST *newList)

从头部插入链表

LOS_ListTailInsertList

(LOS_DL_LIST *oldList, LOS_DL_LIST *newList)

鸿蒙采用双向循环链表实现structure数据结构之间的关联，支持单节点头尾插入。 更精妙的是，链表支持插入另一个链表比特币核心源码，将两个循环链表组合成一个大循环链表。 巧妙简单，详见代码

//双向链表初始化LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListInit(LOS_DL_LIST *list){  list->pstNext = list; // 前后指针都指向自己  list->pstPrev = list;}
//链表判空，检查前后指针是否指向自己LITE_OS_SEC_ALW_INLINE STATIC INLINE BOOL LOS_ListEmpty(LOS_DL_LIST *list){  return (BOOL)(list->pstNext == list);}//从链表中删除节点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;}//指针互换，具体向双向循环链表中插入节点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;}// 两个循环链表合成一个大循环列表LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListAddList(LOS_DL_LIST *oldList, LOS_DL_LIST *newList){// 先用临时指针记录头尾位置  LOS_DL_LIST *oldListHead = oldList->pstNext;  LOS_DL_LIST *oldListTail = oldList;  LOS_DL_LIST *newListHead = newList;  LOS_DL_LIST *newListTail = newList->pstPrev;  // 前后指针完成切换  oldListTail->pstNext = newListHead;  newListHead->pstPrev = oldListTail;  oldListHead->pstPrev = newListTail;  newListTail->pstNext = oldListHead;}// 这里与其说插入不如说合并，同样支持从头或尾部合并
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListTailInsertList(LOS_DL_LIST *oldList, LOS_DL_LIST *newList){  LOS_ListAddList(oldList->pstPrev, newList);}
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListHeadInsertList(LOS_DL_LIST *oldList, LOS_DL_LIST *newList){  LOS_ListAddList(oldList, newList);}

阅读鸿蒙内核源码时，要实时带上LOS_DL_LIST，了解代码之间的关系，想象一下运行时的场景，才能体会到内核代码的简洁之美。

具体使用场景

我们来看看它的一个使用场景，感受一下设计者的奇妙用心，上传代码。

typedef struct ProcessCB {    CHAR                 processName[OS_PCB_NAME_LEN]; /**< Process name */    UINT32               processID;                    /**< process ID = leader thread ID */    UINT16               processStatus;                /**< [15:4] process Status; [3:0] The number of threads currently                                                            running in the process */    LOS_DL_LIST          pendList;                     /**< Block list to which the process belongs */    LOS_DL_LIST          childrenList;                 /**< my children process list */    LOS_DL_LIST          exitChildList;                /**< my exit children process list */    LOS_DL_LIST          siblingList;                  /**< linkage in my parent's children list */    ProcessGroup         *group;                       /**< Process group to which a process belongs */    LOS_DL_LIST          subordinateGroupList;         /**< linkage in my group list */    UINT32               threadGroupID;                /**< Which thread group , is the main thread ID of the process */    UINT32               threadScheduleMap;            /**< The scheduling bitmap table for the thread group of the                                                            process */    LOS_DL_LIST          threadSiblingList;            /**< List of threads under this process */    LOS_DL_LIST          threadPriQueueList[OS_PRIORITY_QUEUE_NUM]; /**< The process's thread group schedules the    LOS_DL_LIST          waitList;     /**< The process holds the waitLits to support } LosProcessCB;

这是 LosProcessCB（进程控制块）。 因为结构很复杂，其他定义省略，只留下LOS_DL_LIST。 大家可以根据内核源码阅读。 LosProcessCB包含七个双向循环链表，进程组的队列是一个数组。比特币核心源码，其中还包含 32 个就绪队列的双向循环链表。 这些链表承载着一个进程在其生命周期中的运行过程逻辑、进程与线程的关系逻辑、线程的运行过程逻辑等等。是的，描述进程从出生到死亡，必须要有这么复杂的数据结构的过程。

任务队列涉及的相关代码

以上就是任务队列的dequeue和enqueue操作，后面就是LOS_DL_LIST的增删过程。

#define OS_PROCESS_PRI_QUEUE_SIZE(processCB) OsPriQueueProcessSize(g_priQueueList, (processCB)->priority) #define OS_TASK_PRI_QUEUE_ENQUEUE(processCB, taskCB) \    OsPriQueueEnqueue((processCB)->threadPriQueueList, &((processCB)->threadScheduleMap), \                      &((taskCB)->pendList), (taskCB)->priority)#define OS_TASK_PRI_QUEUE_ENQUEUE_HEAD(processCB, taskCB) \    OsPriQueueEnqueueHead((processCB)->threadPriQueueList, &((processCB)->threadScheduleMap), \                      &((taskCB)->pendList), (taskCB)->priority) #define OS_TASK_PRI_QUEUE_DEQUEUE(processCB, taskCB) \    OsPriQueueDequeue((processCB)->threadPriQueueList, &((processCB)->threadScheduleMap), &((taskCB)->pendList))  #define OS_TASK_SCHED_QUEUE_ENQUEUE(taskCB, status) OsTaskSchedQueueEnqueue(taskCB, status)#define OS_TASK_SCHED_QUEUE_DEQUEUE(taskCB, status) OsTaskSchedQueueDequeue(taskCB, status) #define OS_PROCESS_PRI_QUEUE_ENQUEUE(processCB) \    OsPriQueueEnqueue(g_priQueueList, &g_priQueueBitmap, &((processCB)->pendList), (processCB)->priority)#define OS_PROCESS_PRI_QUEUE_ENQUEUE_HEAD(processCB) \    OsPriQueueEnqueueHead(g_priQueueList, &g_priQueueBitmap, &((processCB)->pendList), (processCB)->priority)#define OS_PROCESS_PRI_QUEUE_DEQUEUE(processCB) OsPriQueueProcessDequeue(&((processCB)->pendList)) #define OS_TASK_PRI_QUEUE_SIZE(processCB, taskCB) OsPriQueueSize((processCB)->threadPriQueueList, (taskCB)->priority)#define OS_TASK_GET_NEW(processCB) LOS_DL_LIST_ENTRY(OsPriQueueTop((processCB)->threadPriQueueList,     \                                                                    &((processCB)->threadScheduleMap)), \                                                     LosTaskCB, pendList)

内联函数内联

鸿蒙内核使用了大量的内联函数。 内联函数有什么好处？ 不懂的自行查看，这里不普及基础知识。 源码中只有los_list.h是.h文件，没有.c文件！ 这些最常被调用的内联函数节省了普通函数需要出栈和入栈的时间和空间，效率极高。

/* Define OS code data sections *//* The indicator function is inline */#ifndef LITE_OS_SEC_ALW_INLINE#define LITE_OS_SEC_ALW_INLINE  /* __attribute__((always_inline)) */#endif 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;}LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListTailInsert(LOS_DL_LIST *list, LOS_DL_LIST *node){    LOS_ListAdd(list->pstPrev, node);}