LiteOS双向链表使用详解

官方开放文档中关于双向链表的介绍比较简单，并没有告诉大家到底怎么在自己的数据结构中使用链表。其实也比较简单，时间紧的朋友可以直接看第二部分。

一、双向链表简介

双向链表是指含有往前和往后两个方向的链表，即每个结点中除存放下一个节点指针外，还增加一个指向其前一个节点的指针。其头指针head是唯一确定的。从双向链表的任意一个节点开始，都可以很方便的访问它的前驱和后继节点。如下图所示：

LiteOS双向链接跟linux的内核链接原理一样。LiteOS定义了双向链表基本数据结构，并提供了相关的函数和宏定义来操作链表，用户可以添加、删除节点，遍历节点等。

LiteOS双向链表数据结构定义如下，包含了两个指针，分别指向前驱和后继节点。这是个最基本的数据结构，仅包含有双向链表。

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;

LiteOS双向链表操作函数：

VOID LOS_ListInit(LOS_DL_LIST *pstList) #define LOS_DL_LIST_FIRST(pstObject) ((pstObject)->pstNext) VOID LOS_ListAdd(LOS_DL_LIST *pstList, LOS_DL_LIST *pstNode) VOID LOS_ListTailInsert(LOS_DL_LIST *pstList, LOS_DL_LIST *pstNode) VOID LOS_ListDelete(LOS_DL_LIST *pstNode) BOOL LOS_ListEmpty(LOS_DL_LIST *pstNode) //return (BOOL)(pstNode->pstNext == pstNode); //取得链表所在结构体地址,即根据链表节点的地址获取用户结构体地址. //item: 链表节点地址.用户结构体中定义的链表成员的地址 //type: 用户结构体名称 //member:链表在用户结构体中的成员名称 #define LOS_DL_LIST_ENTRY(item, type, member) \     ((type *)((char *)item - LOS_OFF_SET_OF(type, member))) \ //遍历用户结构体 for循环 //item:用户结构体指针。需用户在外定义好。 //list: 链表首地址 //type: 用户结构体名称 //member: 链表在用户结构体中的成员名称 #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))    //遍历用户结构体,可删除节点  for循环 //item:用户结构体指针。需用户在外定义好。 //next: 用户结构体指针,指向item的下一个节点. 需用户在外定义该变量。 //list: 链表首地址 //type: 用户结构体名称 //member: 链表在用户结构体中的成员名称         #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))     //遍历双向链表,不可有删除节点.仅遍历链表节点(不包括用户结构体内容) //item: 链表指针, 需用户定义好该变量 //list: 链表头 #define LOS_DL_LIST_FOR_EACH(item, list)   \     for ((item) = (list)->pstNext; \         (item) != (list); \         (item) = (item)->pstNext)         //安全遍历双向链表,可删除节点.仅遍历链表节点(不包括用户结构体内容) //item: 链表指针, 需用户定义好该变量 //next: 链表指针, 指向item下一个节点.需用户定义好该变量 //list: 链表头 #define LOS_DL_LIST_FOR_EACH_SAFE(item, next, list) \     for (item = (list)->pstNext, next = item->pstNext; item != (list); \         item = next, next = item->pstNext)    // 定义一个双向链表节点并初始化,可用于初始化一个链表头.变量名为list #define LOS_DL_LIST_HEAD(list) \             LOS_DL_LIST list = { &(list), &(list) }

二、链表的使用

LiteOS 内核定义的双向链表跟Linux内核链表思想一致，它仅仅包含了两个指针类型的变量。

用户使用双向链表时，要将双向链表加入自己的数据结构中。即定义一个结构体，成员包括用户需要用到的数据类型，最后，在结构体中加入内核双向链表数据类型，使之成为结构体的成员。

如代码所示，定义用户结构体，包含双向链表成员：

typedef struct {     UINT16          member1;  //用户数据              UINT16          member2;  //用户数据据                         LOS_DL_LIST     mList;    //双向链表    } User_Data_t;

基本原理是：利用双向链表，将用户结构体中定义好的链表成员变量都链接起来；链表节点在用户结构体中的偏移地址是固定的，根据链表节点的地址，减去偏移地址，就能得到用户结构体变量的起始地址了。LiteOS中根据链表地址获取用户节点地址的宏定义是：

//取得链表所在结构体地址,即根据链表节点的地址获取用户结构体地址. //item: 链表节点地址.用户结构体中定义的链表成员的地址 //type: 用户结构体名称 //member:链表在用户结构体中的成员名称 #define LOS_DL_LIST_ENTRY(item, type, member) \     ((type *)((char *)item - LOS_OFF_SET_OF(type, member))) \

如下图所示，利用链表将用户节点中的链表成员链接起来

示例代码如下：

User_Data_t  data1,data2,data3; //定义用户变量 LOS_DL_LIST  gHeader;   //定义链表头 data1.member1 = 1;data2.member1 = 2;data3.member1 = 3;//初始化用户数据 LOS_ListInit(&gHeader);  //初始化链表 LOS_ListTailInsert(&gHeader,&data1.mList);//将data1添加到链表尾部 LOS_ListTailInsert(&gHeader,&data2.mList);//将data2添加到链表尾部,即data1之后 LOS_ListTailInsert(&gHeader,&data3.mList);//将data3添加到链表尾部,即data2之后 //从链表中取数据  LOS_DL_LIST *node; User_Data_t  *pData; node = LOS_DL_LIST_FIRST(&gHeader); //获取链表第一个节点.node指向data1.mList //根据node取得data1的地址 pData = LOS_DL_LIST_ENTRY(node,User_Data_t,mList); printf("data1.member1 is %d!\r\n",pData->member1); //遍历链表 LOS_DL_LIST_FOR_EACH_ENTRY(pData,&gHeader,User_Data_t,mList) {     printf("data member1 is %d!\r\n",pData->member1); }

软件开发

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。