zephyr---双向链表dlist

先来看看结点的数据结构：
struct _dnode
{
     union
    {
         struct _dnode *head;  /* 链表头指针 (sys_dlist_t) */
         struct _dnode *next;  /* 下一节点指针(sys_dnode_t) */
    };
     union
    {
         struct _dnode *tail;  /* 链表尾指针 (sys_dlist_t) */
         struct _dnode *prev;  /* 上一节点指针 (sys_dnode_t) */
    };
};

typedef  struct _dnode sys_dlist_t;  //表示链表，使用*head和*tail
typedef  struct _dnode sys_dnode_t;  //表示节点，使用*next和*prev
学过数据结构的都知道，链表本身就是用节点来表示的，这里只是使用共用体区分开来。

SYS_DLIST_FOR_EACH_CONTAINER(__dl, __cn, __n)
/**
 * @brief 提供在一容器下的链表迭代原语
 * Note: 非安全循环，因此_cn不可或缺
 *
 * 用户必须自行添加大括号:
 *
 *     SYS_DLIST_FOR_EACH_CONTAINER(l, c, n) {
 *         <user code>
 *     }
 *
 * @param __dl  sys_dlist_t类型指针，指向将要迭代的链表
 * @param __cn  依次指向链表每个条目的指针
 * @param __n  容器中的sys_dnode_t类型成员名称
 */
#define SYS_DLIST_FOR_EACH_CONTAINER(__dl, __cn, __n)           \
     for (__cn = SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n); __cn; \
         __cn = SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n))
此宏用于非安全遍历，所谓非安全遍历，就是不需要删除操作的遍历。要进行删除操作，就得使用下面这个宏了。

SYS_DLIST_FOR_EACH_CONTAINER_SAFE(__dl, __cn, __cns, __n)
/**
 * @brief 提供在一容器下的链表安全迭代原语
 * Note: __cn可用于删除，不会打断循环
 *
 * 用户必须自行添加大括号:
 *
 *     SYS_DLIST_FOR_EACH_CONTAINER_SAFE(l, c, cn, n) {
 *         <user code>
 *     }
 *
 * @param __dl  sys_dlist_t类型指针，指向将要迭代的链表
 * @param __cn  依次指向链表每个条目的指针
 * @param __cns  用于安全循环的指针
 * @param __n  sys_dnode_tsys_node_t在容器结构体中的类型名称
 */
#define SYS_DLIST_FOR_EACH_CONTAINER_SAFE(__dl, __cn, __cns, __n)   \
     for (__cn = SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n), \
         __cns = SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n); __cn; \
         __cn = __cns,                      \
         __cns = SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n))
此宏用于安全遍历，也就是需要进行删除操作时，再使用此方法遍历。_cn可被删除。

sys_dlist_append(sys_dlist_t *list, sys_dnode_t *node)
将node节点追加到 list链表尾部。

sys_dlist_prepend(sys_dlist_t *list, sys_dnode_t *node)
将node节点插入到list链表头部。

sys_dlist_insert_after(sys_dlist_t *list,
sys_dnode_t *insert_point, 
sys_dnode_t *node)
将node节点插入到list链表的insert_point节点后面。

sys_dlist_insert_before(sys_dlist_t *list, 
sys_dnode_t *insert_point, 
sys_dnode_t *node)
将node节点插入到list链表的insert_point节点前面。

sys_dlist_insert_at(sys_dlist_t *list, 
sys_dnode_t *node,
int (*cond)(sys_dnode_t *, void *), 
void *data)
将node节点插入到list链表内，至于插入到哪个位置，由cond()函数决定。在运行时每个节点和data参数都会传递给cond()函数进行判断，如果cond()返回1，则插入到当前判断节点的前面。
如果链表为空，则node作为头节点添加，不经过conf()判断。
这函数写的，很新颖啊！不研究在什么情况下使用了，改天碰到再说。

sys_dlist_remove(sys_dnode_t *node)
删除节点node，这函数写的，怎么看着都不合逻辑，都不需要指定是哪个链表了。不过想想，的确也不需要指定链表。

研究完了，写个例子吧。多年经验，不写个例子，还真就没办法掌握，顶多也就是自认为掌握而已。为了省事，直接把上次的slist例子改为dlist版的吧。

#include <zephyr.h>
#include <misc/printk.h>
#include <misc/dlist.h>
 
static sys_dlist_t list;
struct container_node
{
    sys_dnode_t node;
    int id;
};
 
void PrintList(sys_dlist_t *list) //依次打印所有节点
{
    struct container_node *container;
    printk("print list node:\n");
    //注意，下面的参数node是container_node结构体中的字段名
    SYS_DLIST_FOR_EACH_CONTAINER(list, container, node)
    {
        printk("node%d   ", container->id);
    }
    printk("\n\n");
}
 
void main(void)
{
    struct container_node node1, node2, node3, node4, node5;
    node1.id = 1;
    node2.id = 2;
    node3.id = 3;
    node4.id = 4;
    node5.id = 5;
    sys_dlist_init(&list);
    //将5个节点加入链表
    sys_dlist_append(&list, &node1.node);
    sys_dlist_append(&list, &node2.node);
    sys_dlist_append(&list, &node3.node);
    sys_dlist_append(&list, &node4.node);
    sys_dlist_append(&list, &node5.node);
    PrintList(&list);
 
    printk("move node3 to head\n");
    sys_dlist_remove(&node3.node);//删除节点3
    sys_dlist_prepend(&list, &node3.node);//将节点3变为头节点
    PrintList(&list);
 
    printk("switch node4 and node2\n");
    sys_dlist_remove(&node4.node);//删除节点4
    sys_dlist_insert_after(&list, &node1.node, &node4.node);//将节点4加到节点1后面
    PrintList(&list);
}

运行结果如下图所示：

结果和slist的一模一样。两者的代码间的最大区别就是结点删除操作，大家可以做下对比。slist的是find and remove。而dlist的是直接remove。了解数据结构中单链表和双链表的区别，相信对这种区别的原因会有体会。

最后来个总结吧。个人观点，slist应该用在只对头尾进行操作的链表，比如作为栈和队列的基础数据结构就很合适。而如果要对链表中段进行操作，当然dlist会快很多。当然需要的内存也会大一些。