队列2-双向链表

???? [Github Pages] ????

果然晚了一步，基于双向链表的消息队列模块还没有完全完工，不过已经有一个雏形了，那么本篇文章主要就介绍下双向链表的细节实现以及我基于双向链表搭建的一个消息队列框架，虽说代码还未完全完工，不过不妨，还是可以介绍下的。

为什么要用链表

在嵌入式开发实际编程当中，会经常有数据管理之类的需求，比如一个视频设备，在采集视频帧的时候需要一个buffer队列来进行视频帧的缓存管理，这个时候就需要用到一些队列管理类的数据结构。再比如说，设备的管理也需要用到双向链表（linux内核的设备驱动管理）。

那么本文介绍的双向链表是一个通用的双向链表，它可以很方便的嵌入到任何一个自定义的结构体类型里面，使用极为方便。至于为什么在某些情况下要使用链表代替数组等结构，原因有以下几个：

• 数组：数组当然可以实现数据管理这个需求，常见的方式使用数组来管理一个具有固定序列的数据列表，比如说一个有固定数量的设备，数量序号从0~3，在这种情况下，不需要做队列循环的操作，在创建一个设备的时候只需要将相应的设备按照标号放入到对应的数组位置当中即可。这种方式可以快速的定位数据所在的位置，而不需要从头到尾去顺序查询。但是数组不适合动态插入动态删除这个操作需求，需要大量的数据搬运。
• 链表：有些没有固定数量，处于不断地更新变化的数据，比如一个需要异步执行并且不可丢失的命令序列、一个需要进行实时加载与卸载的驱动，无序且数量未知，这个时候就需要链表结构来协助完成数据的管理。链表不需要过度关注数据的顺序，还可以方便快捷地在任意一个地方插入删除一个元素，并且不会影响到其它的元素。但是普通的链表不支持随机访问，只能够遍历，而消息队列这种东西很适合需要动态插入删除而不用随机访问的数据构造。
• 哈希表：哈希表融合了数组与链表的优点，既可以快速查询到指定元素，又可以十分灵活的添加或者删除相关的元素。不过哈希表不在本文的讨论范围之内，暂且略过不表。

链表以极强的灵活性而被内核作为广泛使用的数据结构，通常用于各种驱动列表的管理，还有各种拓扑结构上也使用到了链表：比如V4L2驱动框架。链表相较于数组更适合用于这些管理的原因有：

1. 链表适合于做队列循环，链表做一次队列循环只需要对两个元素进行操作，而数组需要对所有的元素进行操作。
2. 链表可以即时即刻，在任意一个位置新建、插入、删除元素而不至于影响到其它的元素，而数组想在一个地方插入一个元素，假设元素个数为n，在第m个位置插入元素，则至少需要挪动n-m+1个元素，并且数组的空间拓展相较于链表更加繁琐一点。
3. 链表的存储空间拓展比较灵活，随用随分配，而数组通常情况下得提前定好长度，这样极有可能会造成空间的浪费或者空间不足。不过可以通过另外一种方式实现变长数组，有一种不完全类型可以实现变长的数组，这个变长的数组叫做柔性数组，使用结构体可以实现，但即使是变长的，也是增加空间容易，减少空间困难，不如链表。

链表

单向链表

• 原型

struct simplex
{
    int value;
    struct simplex *next;
};

• 结构图

双向链表

• 原型

struct dlist
{
    struct dlist *next;
    struct dlist *prev;
};

• 结构图

根据上面的两种简单链表结构可看出，单向循环链表的遍历顺序是单一的，从链表的某一个成员开始，如果要匹配的成员已知在链表遍历方向的反方向，整个遍历过程就会显得十分繁琐，不够灵活。而双向链表可以在任意一个位置双向遍历，比单项链表显得更加灵活。

可以看到它们都有一定的缺点，单向链表缺点是无法从任意一个位置随意的往前往后访问，而双向链表也有一个缺点，就是每次都得自行定义并实现一个特定类型的结构体，这个属于两种类型链表的共同缺点了，下面介绍下一个比较通用的嵌入式双向链表结构。

list_head 结构体

在linux内核当中，一个随处可见的结构体就是 list_head 结构体，其原型是：

struct list_head {
    struct list_head *next, *prev;
};

此结构体在linux内核中被大量的引用，几乎所有内核当中需要构成链表结构的地方都用到了这个结构体。例如内核的设备驱动管理就广泛使用到了这个结构体。该结构体相关的代码可以在 include/linux/list.h 内核文件当中看到。

• 一个问题
  Q：为什么linux内核里面不使用类似上一节里面的「双向链表」所描述的链表结构？
  A：因为内核里面的结构体众多，每个结构体的类型都不一样，如果在每个结构体里面都实现一个特定的双向链表，每个结构体都需要单独实现特定的链表管理方法，这样会在内核里面增加大量繁琐、冗余的代码。

• 解决方法
  实现一个 list_head 双向链表元结构体，然后在每一个需要进行队列管理的结构体里面嵌入这个 list_head 元结构体，使用统一的接口来对众多的结构体链表进行管理。

• 如何使用list_head结构体

1. 在需要管理的结构体里面嵌入类似struct list_head list的代码。
2. 使用linux提供的统一的接口进行链表增删、遍历操作。

至于如何使用这里就不再贴代码了，基本功而已，主要看下它的实现，如何做到通用、即插即用这一特性。

实现方法

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

这个宏就是链表头的初始化，此时 name 的结构就是一个内部前后指针均指向自己的形式，这是一个空的带头链表的头部，所谓带头链表就是它有一个头，有的链表是没头的，这个头不参与实际的数据存储，只是作为一个头而已，它起的是统领功能。

__list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

上面的尖端代码实现了一个节点的添加，图形化描述：

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
#define container_of(ptr, type, member) ({          \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

这段代码就比较核心了，它描述了如何从 list_head 结构体成员找到父结构体，也就是我们自定义的结构体类型，因为总归我们还是要访问到自己的结构体，不然这个东西就不只是鸡肋，而是根本就不能用了，把上面例程代码段中的 list_entry(mod, struct test_list, test); 展开就得到：

{
    const typeof( ((struct test_list *)0)->test ) *__mptr = (mod);
    (struct test_list *)( (char *)__mptr - ((size_t) &((struct test_list *)0)->test));
}

/* test_list结构体原型 */
struct test_list
{
    unsigned char *name;
    struct list_head test;
    int value;
};

/* mod 变量定义*/
struct list_head *mod;

拆解一下代码步骤可得：

1. ((struct test_list *)0)：将0转换为struct test_list类型的指针。
2. typeof( ((struct test_list *)0)->test )：获取test_list结构体内的test成员的类型，也就是list_head类型。
3. typeof( ((struct test_list *)0)->test ) *__mptr = (mod)：定义一个struct list_head类型的指针，名为__mptr，指向mod所指向的内存（mod为整个链表中的某一个list_head节点）。
4. ((size_t) &((struct test_list *)0)->test：获取test_list结构体头到test成员的字节长度。
5. (char *)__mptr - ((size_t) &((struct test_list *)0)->test)：list_head节点地址减去test_list结构体头到test成员的字节长度（也就是该list_head节点的父结构体test_list的地址）。
6. (struct test_list *)( (char *)__mptr - ((size_t) &((struct test_list *)0)->test))：强制转换为struct test_list类型的指针返还给调用者。

有图就十分的形象啦，上面的图揭示了一个嵌入式 list_head 结构体到父结构体的寻找过程。搞明白之后就可以自己实现一个平平凡凡的类似功能的宏：

#define mlist_entry(list_head, type, member_name) \
            (type *)((unsigned int)list_head - (unsigned int)(&(((type*)(0))->member_name)))

内核当中还有很多的链表操作方法，例如 list_move_tail （链表元素的移动），还有链表的遍历（前向遍历、后向遍历）等等，这些不在赘述，可以去内核的 list.h 文件里面看看，自己造一个也未尝不可，很简单的，有了上面的知识，其它的理解起来就轻而易举了。

工具的使用

那么知道了一个通用的双向链表是怎么实现的，就可以用它来做一些事情了，这里我就提出一个自己的需求，一个消息队列模块：

1. 可以方便的填入、使用、还回消息。
2. 可以传递的消息类型有整形、字符串类型以及它们的混合。
3. 可以随时随地地创建、使用、销毁一个完整的消息队列模块，使用模块化的编程实现。

下面只是泛泛的说一下大概的实现思路，看不懂是我的问题，我觉得还是要结合代码来看比较好，所以这个就相当于我介绍自己的代码理解思路吧。

首先定义一下一个基础消息的结构体类型：

/* You can push one fifo element with initilize one [list_fifo_buf].
* @id: this is reserved until now.
* @data1: the first data you want push.
* @data2: the second ...
* @pdata: if you have one extra data, push it into here.
* @pdata_len: how much length is you @pdata, Unit(char).
* @malloc_by_self: if the extra data is malloc by yourself(malloc_by_self == 1),
* then I think you can hold your datas memory until you don't need it, or
* I will malloc one mermory region to store you datas, and you don't
* need care about you datas life cycle.
*/
struct list_fifo_buf {
    unsigned int id;
    unsigned int data1;
    unsigned int data2;
    void *pdata;
    unsigned int pdata_len; /* Unit: char. */
    bool malloc_by_self;
};

由于编辑器问题，用中文注释太麻烦，虽然我的英文不咋地，但是为了方便就用英文注释了。讲人话就是我这个玩意儿它有这么几个元素：

1. fifo 数据的 id，用于标识这个消息是哪一个，整个 fifo 当中是唯一的。
2. 两个整形数据就不多说了，就是用来放自己的数据的，这是个简单的类型，比如可以放置自己的枚举类型消息元素等。
3. pdata 就是在需求没有得到完全满足的时候的扩展选项，用于存放自定义的消息，可以是任意类型的，当然我就不负责告诉你这究竟是什么类型的，自己约定好就行，是不是很强大。
4. 以及自定义消息的长度。
5. 如果你不想自己分配那个自定义消息类型的存储空间的话，那就把这个 malloc_by_self 保持默认的 0 就好，内部会帮你去使用 malloc 分配以保证整个的过程中它的内存不会被瞎释放，在你还回的时候我会根据这个标志位来判定是否需要 free，如果是本人管理的话在还回的时候需要自行去释放这块内存。

用户可以接触到的 API 设计，与上次的环形缓冲区设计一脉相承，没时间解释了：

/* The fifo elemention, users can do fifo operations with this structure.
* @push_fifo: push one element into fifo list.
* @pull_fifo: get one element from fifo list.
* @release_fifo: If you have used the @fifo_list_buf, then give it back.
* @wait_release_all_fifos: Wait if used is not empty.
* @reset_fifo: Invalid all valid fifo elements. NNNNNNNNotice: you responsible for this invoke.
* @revert_fifo: revert one fifo list.
* @merge_fifo: merge two fifo list, move @type_head list into &type_body list.
*/
struct list_fifo {
    int (*push_fifo)(struct list_fifo *fifo, struct list_fifo_buf *buf);
    int (*pull_fifo)(struct list_fifo *fifo, struct list_fifo_buf *buf);
    int (*release_fifo)(struct list_fifo *fifo, struct list_fifo_buf *buf);
    int (*wait_release_all_fifos)(struct list_fifo *fifo);
    int (*reset_fifo)(struct list_fifo *fifo, bool all_list);
    int (*revert_fifo)(struct list_fifo *fifo, enum fifo_type type);
    int (*merge_fifo)(struct list_fifo *fifo,
         enum fifo_type type_head, enum fifo_type type_body);

    void (*get_fifo_attr)(struct list_fifo *fifo, struct list_fifo_attr *attr);

    /* Used by list_fifo internal, do not touch it. */
    void *private;
};

代码内部的实现就是要填充好 push_fifo, pull_fifo 等等的具体实现，里面值得说下的东西并不多，随便想想就想得到，觉得有必要描述下的是消息的 id 怎么分配，我这里用了一个比较笨的方法。

我用了一个位图类型的结构存储某个 id 是否已经被分配了，一个 bit 代表一个 id 坑位，每次进来消息的时候都会便利下这个 id 列表，看起来效率较低哈，就先这样吧，消息数量不多的情况下很实用。它的定义是 unsigned char bitBufIdMap[(MAX_PRESET_NUM+7)/8];，在填入消息的时候使用下面的代码分配 id，不用判断是否能够分配得到，肯定能够分配得到的：

int iSizeofMapElem = sizeof(fifo_elem->bitBufIdMap[0])*8;
for (i = 0; i < sizeof(fifo_elem->bitBufIdMap)*iSizeofMapElem); i++) {
    if (!(fifo_elem->bitBufIdMap[i/iSizeofMapElem] & 1 << (i%iSizeofMapElem))) {
        buf_push->list_buf.id = i;
    }
}

在归还消息的时候要清理一下 id，这个就很方便了：

int iSizeofMapElem = sizeof(fifo_elem->bitBufIdMap[0])*8;
fifo_elem->bitBufIdMap[buf_cur->list_buf.id/iSizeofMapElem]
    &= ~(1 << (buf_cur->list_buf.id%iSizeofMapElem));

其它的真没啥好说的，浏览下代码就好。其实这个玩意儿不仅仅可以传递消息类型，因为其具有顺序性，也就是先进先出，所以也可以传递一些多媒体数据的结构体头部信息，直接把它填充到 pdata 那个域里面就可以，当然也可以使用环形缓冲区来实现，见仁见智啦，具体情况具体分析看适合采用哪个类型的模块。

End

下周就过年溜回家了，肯定不会更新数据结构这个玩意儿啦，会写下别的东西。准备收年终奖回家过年啦。

????????????????????

Github 代码链接：链接 。或者点击阅读原文可以直接转到 Github

---

想做的事情就去做吧