LiteOS双向链表使用详解

llb90 发表于 2020/03/06 16:44:49 2020/03/06
【摘要】 官方开放文档中关于双向链表的介绍比较简单,并没有告诉大家到底怎么在自己的数据结构中使用链表。其实也比较简单,时间紧的朋友可以直接看第二部分。一、双向链表简介双向链表是指含有往前和往后两个方向的链表,即每个结点中除存放下一个节点指针外,还增加一个指向其前一个节点的指针。其头指针head是唯一确定的。从双向链表的任意一个节点开始,都可以很方便的访问它的前驱和后继节点。如下图所示:LiteOS双向...

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

一、双向链表简介

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

image.png


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))) \

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

image.png


示例代码如下:

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);
}



【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。