[数据结构与算法]liteOS中双向循环链表的一些设计思想

1. 问题提出

看liteOS的源码，发现这些伙计们的水平还是高的。对于一个双向链表，一般我们的写法都是：

typedef struct Node {
	int data;
	struct Node *prev;
	struct Node *next;
} NODE

但是这就诞生了一个问题，节点Node中的数据类型是int时我们定义了一个链表类型NODE0，如果是float data又定义了一种链表类型NODE1，或者有多个业务变量时我们又定义了NODE2，这时候如果我们想写一个链表遍历函数，希望能够对所有的链表适用，怎么办呢？使用C++也许容易解决这个问题，模板嘛；但是C语言怎么办呢？

2. 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;

让我们简单看一个插入节点函数，这很容易理解，不做解释了。

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

当需要定义业务结构体时，则需要把上面定义的双向链表结构体作为成员变量，举个例子，下面是互斥锁结构体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;

新的问题就来了，虽然遍历、插入双向链表很容易了，但是我们在使用的时候肯定是对业务结构体进行遍历的啊，如何从链表遍历过渡到业务结构体的遍历呢？
问题的关键是计算出在一个业务结构体中，链表节点的地址相对于业务结构体起始地址的偏移，得到该偏移，我们就可以得到业务结构体指针，从而完成遍历。
业务结构体类型名称type、其中的双向链表成员变量名称member，下面这个宏定义就巧妙实现了求解链表节点地址在一个业务结构体中的地址偏移；(type *)0->member这一骚操作，很好，很喜欢。

#define LOS_OFF_SET_OF(type, member) ((UINTPTR)&((type *)0)->member)

下面这个宏定义更进一步，求出了业务结构体的实际内存地址，其中item是双向链表的实际内存地址。

#define LOS_DL_LIST_ENTRY(item, type, member) \
    ((type *)(VOID *)((CHAR *)(item) - LOS_OFF_SET_OF(type, member)))

再进一步，让我们开始愉快地遍历业务结构体吧，下面宏定义中，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))

到此，liteOS通过实现上述的宏定义/函数，实现了一套链表函数适用于所有的业务结构体，在C语言中写出了C++的风采，值得参考。

3. 参考

1. liteOS源码：https://gitee.com/LiteOS/LiteOS/blob/master/kernel/include/los_list.h
2. LiteOS内核源码分析系列一 盘点那些重要的数据结构 （1）：https://bbs.huaweicloud.com/blogs/244926