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