双向链表是刚毕业就基于linux的实现了解过，后面因为内核的实现没办法直接搬出来用，所以自己应用开发的时候借鉴linux的实现重写了一份，这样方便自己粘贴到任意代码上。

时间长了，关于双向链表的实现很容易印象不深刻，这时候别人突然一问，让我写一个双向链表出来，我能给出思路，但是没办法完美写出来。

举个例子，我们每个人都学过关雎，里面一句"窈窕淑女，君子好逑"可谓人尽皆知，但突然某一天，有人让你背诵关雎，你会不会发懵呢？

本文基于linux内核的实现做一下分析，然后将自己的实现粘贴进来，主要目的是做一个复习。如有有喜欢我的实现的，放心拿去用好啦。

结构体

在内核中list.h实现了双向链表，其结构如下


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

初始化

doubly linked list的创建就是将自己指向自己。所以有如下宏


#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
        struct list_head name = LIST_HEAD_INIT(name)

这样传入list_head结构体就可以初始化一个doubly linked list。
内核还提供了一个函数实现INIT_LIST_HEAD来实现初始化


static inline void INIT_LIST_HEAD(struct list_head *list)
{
        WRITE_ONCE(list->next, list);
        list->prev = list;
}

插入

对于链表的插入需要区分头插还是尾插。那么add有两个实现 list_add和list_add_tail。内核将其头插和尾插抽象成形参传递了，如下


static inline void __list_add(struct list_head *new,
                              struct list_head *prev,
                              struct list_head *next)

这里如果是头插，那么组成关系如下

head ---> new ---> head->next

如果是尾插，那么组成关系如下

head->prev ---> new ---> head

所以__list_add的实现只需要关心位于new的prev和next的位置，那么list_add和list_add_tail只是不同的封装而已，考一下大家，下面哪个是list_add，哪个是list_add_tail。


__list_add(new, head, head->next); // 1
__list_add(new, head->prev, head); // 2

关于__list_add的实现就是

将待插入的new的prev指向prev
将待插入的new的next指向next
将原next的prev设置为new
将原prev的next设置为new

值得注意的是，针对prev->next使用了WRITE_ONCE，这样使得prev->next会保证赋值的有效性。所以我们看内核实现如下


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

内核关于list_add和list_add_tail的实现如下


static inline void list_add(struct list_head *new, struct list_head *head)
{
        __list_add(new, head, head->next);
}
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
        __list_add(new, head->prev, head);
}

删除

对于删除节点而言，我们只需要知道被删除节点即可。然后如下

将待删除的节点的prev的next设置为待删除节点的next。修复待删除节点的prev的next
将待删除的节点的next的prev设置为待删除节点的prev。修复待删除节点的next的prev

对于内核而言，其实现也做了抽象。我们知道待删除节点假设是entry，那么__list_del提供两个参数，一个是prev，一个是next。这样对于删除而言就是简单的如下

将prev的next设置为next
将next的prev设置为prev

那么内核实现如下


static inline void __list_del(struct list_head * prev, struct list_head * next)
{
        next->prev = prev;
        WRITE_ONCE(prev->next, next);
}

当内核实现了__list_del,那么关于删除函数__list_del_entry就是简单的将形参entry拆分成entry->prev和entry->next。如下


static inline void __list_del_entry(struct list_head *entry)
{
        __list_del(entry->prev, entry->next);
}

基于上面，为了满足调试需求，内核故意对被删除的节点设置了固定的值，这样使用crash等工具就能很方便的判断问题了。如下


static inline void list_del(struct list_head *entry)
{
        __list_del_entry(entry);
        entry->next = LIST_POISON1;
        entry->prev = LIST_POISON2;
}
define LIST_POISON1  ((void *) 0x100 + POISON_POINTER_DELTA)
#define LIST_POISON2  ((void *) 0x122 + POISON_POINTER_DELTA)
CONFIG_ILLEGAL_POINTER_VALUE=0xdead000000000000

我们组合一下上面值可以得到如下


0xdead000000000100
0xdead000000000122

我们经常使用crash的同学可以看到如下信息


  list = {
    next = 0xdead000000000100, 
    prev = 0xdead000000000122
  }

替换

替换函数的主要思路为

将new的next设置为old的next
将new的next的prev设置为new自己
将new的prev设置为old的prev
将new的prev的next设置为new自己

也就是说先针对new自身的next，设置为old的next，同时修复原old的next的prev改变成new自己。
然后再针对new自身的prev，设置为old的prev，同时修复原old的prev的next设置为自己

所以替换的实现如下


static inline void list_replace(struct list_head *old,
                                struct list_head *new)
{
        new->next = old->next;
        new->next->prev = new;
        new->prev = old->prev;
        new->prev->next = new;
}

交换

交换的目标是对entry1和entry2的内容在链表进行交换。那么思路应该如下

拿到entry2的prev
将entry2删掉
将entry2替换到entry1的位置上
将entry1添加到entry2的prev后面

根据上面的分析，以及以上章节的代码展示，可以默写步骤如下

获取entry2->prev
list_del(entry2)
list_replace(entry1, entry2)
list_add(entry1, entry2->prev)

但是上面可能在一种情况下出bug，那就是当entry2->prev就是entry1的时候，此时对entry2->prev的头插，就是对entry1的头插，但是list_replace已经修改了entry1的值变成实际entry2的实际值，所以entry2->prev已经不是属于这个doubly link list中了，所以我们更新为entry2。代码如下


static inline void list_swap(struct list_head *entry1,
                             struct list_head *entry2)
{
        struct list_head *pos = entry2->prev;

        list_del(entry2);
        list_replace(entry1, entry2);
        if (pos == entry1)
                pos = entry2;
        list_add(entry1, pos);
}

上面如果理解不太清楚，下面我画图解释如下。最开始链表如下

---> entry1(pos) ---> entry2 ---->

当删除entry2时，如下

---> entry1(pos) ---->

当替换entry1的之后如下

---> entry2 ---->

此时我们需要完成步骤4，但是此时entry1也就是pos不在这个双向链表中了。所以我们需要强制修改pos为entry2如下

---> entry2(pos) ---->

然后调用list_add，结果如下

---> entry2(pos) ----> entry1 ---->

很明显，如果entry1不是entry2的prev，那么就无需关心此问题

移动

移动非常好理解，就是将某个元素删除后，然后通过__list_add添加，因为__list_add有两个实现，所以move有两个版本也就是list_move和list_move_tail。其实现如下


static inline void list_move(struct list_head *list, struct list_head *head)
{
        __list_del_entry(list);
        list_add(list, head);
}
static inline void list_move_tail(struct list_head *list,
                                  struct list_head *head)
{
        __list_del_entry(list);
        list_add_tail(list, head);
}

拼接

关于拼接，__list_splice也做了抽象，这样便于理解，所以有三个形参如下


static inline void __list_splice(const struct list_head *list,
                                 struct list_head *prev,
                                 struct list_head *next)

这里list是待拼接的链表，而prev和next是需要拼接的位置的prev和next。
对于拼接而言，其步骤如下

将待拼接的next的prev设置为prev
将prev的next设置为待拼接的next
将待拼接的prev的next设置为next
将next的prev设置为待拼接的prev

上面需要进一步解释，这里我们因为待拼接的list是整个list，所以我们知道如下

待拼接的next是待拼接的第一个元素
待拼接的prev是待拼接的最后一个元素
待拼接的next的prev是第一个元素的prev，也就是原head
待拼接的prev的next是最后一个元素的next，也是原head

经过这样进一步的解释，再对照内核如下代码


static inline void __list_splice(const struct list_head *list,
                                 struct list_head *prev,
                                 struct list_head *next)
{
        struct list_head *first = list->next;
        struct list_head *last = list->prev;

        first->prev = prev;
        prev->next = first;

        last->next = next;
        next->prev = last;
}

我们可以清楚的知道了拼接的实现

entry

内核提供了list_entry实现，其实就是container_of。关于container_of这里不重复了，可以查阅文章《内核C语言结构体定位成员》

遍历

对于双向循环链表的遍历，可以分为根据next遍历，还是根据prev遍历，所以有两个变体，如下


#define list_for_each(pos, head) \
        for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_prev(pos, head) \
        for (pos = (head)->prev; pos != (head); pos = pos->prev)

安全遍历

根据遍历的代码，可以看到是通过for循环，从head处一直找next/prev，直到pos再次等于head的时候停止遍历。但是这里实际上是不安全的。也是很多代码导致崩溃的原因，本人遇到未使用安全遍历导致遍历崩溃的问题已经数十次有余了。

其原因是这个list的当前值，会在for语句里面可能被删除，例如在list_for_each的里面，会调用list_del(pos)把当前pos删掉。针对这种情况，需要引入一个临时遍历n，它保存了pos->next的值。这样安全的意思就是在遍历的过程中，可以放心的删除pos。其代码实现如下


#define list_for_each_prev_safe(pos, n, head) \
        for (pos = (head)->prev, n = pos->prev; \
             pos != (head); \
             pos = n, n = pos->prev)

遍历entry

我们直到container_of的作用是获取list的上层结构体，而遍历的作用是从头遍历list所有成员。
那么遍历entry的含义就是两者的结合版本，通过list_for_each遍历所有list，然后通过entry获取上层结构体，其代码如下


#define list_for_each_entry(pos, head, member)                          \
        for (pos = list_first_entry(head, typeof(*pos), member);        \
             !list_entry_is_head(pos, head, member);                    \
             pos = list_next_entry(pos, member))

可以看到这里的pos不再是list某个成员，而是所带list的上层结构体entry了。

安全遍历entry

遍历entry也有安全函数版本，如果在循环内部需要删除pos，那么请使用安全版本，其代码如下


#define list_for_each_entry_safe(pos, n, head, member)                  \
        for (pos = list_first_entry(head, typeof(*pos), member),        \
                n = list_next_entry(pos, member);                       \
             !list_entry_is_head(pos, head, member);                    \
             pos = n, n = list_next_entry(n, member))

自己的实现

上面把内核的实现捋了一遍，我又翻箱倒柜找到了自己当时list.h的实现。这里也简单分析一下。

自己的list实现思路是参考了内核，但没内核写的高级，纯粹按照个人思路完成。本人多个工程都用此list.h文件，目前没什么问题。最后贴上list.h的个人版本所有代码

结构体

结构体和内核一致


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

初始化

和内核一致，但是不考虑变量的原子性


static inline void list_inithead(struct list_head *item)
{
    item->prev = item;
    item->next = item;
}

list_add

添加的两个版本没有内核的抽象，我的思路如下首先默认情况如下

list<---> A

此时添加item，首先先把item的prev和next接到list和A中间

list<---item--->A


    item->prev = list;
    item->next = list->next;

此时A的prev是断开的，list的next也是断开的，修复doubly link list关系

list<--->item<--->A


    list->next->prev = item;
    list->next = item;

故代码如下


static inline void list_add(struct list_head *item, struct list_head *list)
{
    item->prev = list;
    item->next = list->next;
    list->next->prev = item;
    list->next = item;
}

list_addtail

tail的版本是添加到list之前，假设默认情况如下

A<--->list

此时添加item，首先先把item的prev和next接到list和A中间

A<---item--->list


    item->next = list;
    item->prev = list->prev;

此时A是list->prev，其next是断开的，list的prev也是断开的，修复一下

A<--->item<--->list


    list->prev->next = item;
    list->prev = item;

故代码如下


static inline void list_addtail(struct list_head *item, struct list_head *list)
{
    item->next = list;
    item->prev = list->prev;
    list->prev->next = item;
    list->prev = item;
}

list_del

首先默认情况如下

list<--->item<--->B

我们幻想一个删除后的结果如下

list<---?--->B

所以在item角度修复其item->prev->next和item->next->prev

list<--->B


    item->prev->next = item->next;
    item->next->prev = item->prev;

个人的实现没有内核的标记，所有直接置空即可，故整体代码如下


static inline void list_del(struct list_head *item)
{
    item->prev->next = item->next;
    item->next->prev = item->prev;
    item->prev = item->next = NULL;
}

list_validate

在解决《glibc的chunk破坏问题》问题的时候，我特地实现了validate函数，此函数判断doubly link list的每个成员是否正常，其思路是

判断每个成员的next的prev是不是自己
判断每个成员的prev的next是不是自己


static inline void list_validate(const struct list_head *list)
{
   struct list_head *node;
   assert(list_is_linked(list));
   assert(list->next->prev == list && list->prev->next == list);
   for (node = list->next; node != list; node = node->next)
      assert(node->next->prev == node && node->prev->next == node);
}

list_splice

拼接的思路上文已经叙述清楚了，这里绘图示意即可。假设默认两个list如下

tail(A)<--->src<--->A dst<--->B

第一步，将src拆开，将A的prev挂到dst，将tail的next挂到B上。为了简化，假设tail就是A。

dst<---A(tail)--->B


   src->next->prev = dst;
   src->prev->next = dst->next;

第二步，将B的prev设置为tail(A)

dst<---A(tail)<--->B


   dst->next->prev = src->prev;

第三步，将dst的next设置为A

dst<--->A(tail)<--->B


dst->next = src->next;

此时拼接完成，故整体代码如下


static inline void list_splice(struct list_head *src, struct list_head *dst)
{
   if (list_is_empty(src))
      return;

   src->next->prev = dst;
   src->prev->next = dst->next;
   dst->next->prev = src->prev;
   dst->next = src->next;
}

list_splicetail

拼接尾的思路完全一致，不同的是拼接到head前面。假设默认两个list如下

tail(A)<--->src<--->A tail(B)<--->dst<--->B

第一步，将src拆开，将tail(A)的next挂到dst，将A的prev挂到tail(B)上。

tail(B)<---tail(A)--->dst


   src->prev->next = dst;
   src->next->prev = dst->prev;

第二步，将tail(B)的next设置为A

tail(B)<--->tail(A)--->dst


   dst->prev->next = src->next;

第三步，将dst的prev设置为tail(A)

tail(B)<--->tail(A)--->dst


dst->prev = src->prev;

值得注意的是，如果此链表只要一个元素A/B，那么tail(A)就是A，tail(B)就是B，如果是多个元素，你也可以理解tail(A)是src的最后一个元素，tail(B)是dest的最后一个元素。

entry及其衍生

关于list_entry的宏定义，可以直接从内核抄，只不过我们需要替换成标准的offsetof实现，如下


#define list_entry(__item, __type, __field)   \
    ((__type *)(((char *)(__item)) - offsetof(__type, __field)))

在此之上list_for_each和list_for_each_entry的实现可以无缝复制粘贴
当然，其safe实现也可以无缝粘贴。

代码


#ifndef _LIST_H_
#define _LIST_H_

#include <stdbool.h>
#include <stddef.h>
#include <assert.h>

#define list_assert(cond, msg)  assert(cond && msg)

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

static inline void list_inithead(struct list_head *item)
{
    item->prev = item;
    item->next = item;
}

static inline void list_add(struct list_head *item, struct list_head *list)
{
    item->prev = list;
    item->next = list->next;
    list->next->prev = item;
    list->next = item;
}

static inline void list_addtail(struct list_head *item, struct list_head *list)
{
    item->next = list;
    item->prev = list->prev;
    list->prev->next = item;
    list->prev = item;
}

static inline bool list_is_empty(const struct list_head *list)
{
   return list->next == list;
}

static inline void list_replace(struct list_head *from, struct list_head *to)
{
    if (list_is_empty(from)) {
        list_inithead(to);
    } else {
        to->prev = from->prev;
        to->next = from->next;
        from->next->prev = to;
        from->prev->next = to;
    }
}

static inline void list_del(struct list_head *item)
{
    item->prev->next = item->next;
    item->next->prev = item->prev;
    item->prev = item->next = NULL;
}

static inline void list_delinit(struct list_head *item)
{
    item->prev->next = item->next;
    item->next->prev = item->prev;
    item->next = item;
    item->prev = item;
}

static inline bool list_is_linked(const struct list_head *list)
{
   assert((list->prev != NULL) == (list->next != NULL));

   return list->next != NULL;
}
static inline bool list_is_singular(const struct list_head *list)
{
   return list_is_linked(list) && !list_is_empty(list) && list->next->next == list;
}

static inline unsigned list_length(const struct list_head *list)
{
   struct list_head *node;
   unsigned length = 0;
   for (node = list->next; node != list; node = node->next)
      length++;
   return length;
}

static inline void list_splice(struct list_head *src, struct list_head *dst)
{
   if (list_is_empty(src))
      return;

   src->next->prev = dst;
   src->prev->next = dst->next;
   dst->next->prev = src->prev;
   dst->next = src->next;
}

static inline void list_splicetail(struct list_head *src, struct list_head *dst)
{
   if (list_is_empty(src))
      return;

   src->prev->next = dst;
   src->next->prev = dst->prev;
   dst->prev->next = src->next;
   dst->prev = src->prev;
}

static inline void list_validate(const struct list_head *list)
{
   struct list_head *node;
   assert(list_is_linked(list));
   assert(list->next->prev == list && list->prev->next == list);
   for (node = list->next; node != list; node = node->next)
      assert(node->next->prev == node && node->prev->next == node);
}

static inline void list_move_to(struct list_head *item, struct list_head *loc) {
   list_del(item);
   list_add(item, loc);
}

#define list_entry(__item, __type, __field)   \
    ((__type *)(((char *)(__item)) - offsetof(__type, __field)))

#define list_container_of(ptr, sample, member)                          \
    (void *)((char *)(ptr)                                              \
             - ((char *)&(sample)->member - (char *)(sample)))

#define list_first_entry(ptr, type, member) \
        list_entry((ptr)->next, type, member)

#define list_last_entry(ptr, type, member) \
        list_entry((ptr)->prev, type, member)

#define LIST_FOR_EACH_ENTRY(pos, head, member)                          \
   for (pos = NULL, pos = list_container_of((head)->next, pos, member); \
        &pos->member != (head);                                         \
        pos = list_container_of(pos->member.next, pos, member))

#define LIST_FOR_EACH_ENTRY_SAFE(pos, storage, head, member)    \
   for (pos = NULL, pos = list_container_of((head)->next, pos, member), \
        storage = list_container_of(pos->member.next, pos, member);     \
        &pos->member != (head);                                         \
        pos = storage, storage = list_container_of(storage->member.next, storage, member))

#define LIST_FOR_EACH_ENTRY_SAFE_REV(pos, storage, head, member)        \
   for (pos = NULL, pos = list_container_of((head)->prev, pos, member), \
        storage = list_container_of(pos->member.prev, pos, member);             \
        &pos->member != (head);                                         \
        pos = storage, storage = list_container_of(storage->member.prev, storage, member))

#define LIST_FOR_EACH_ENTRY_FROM(pos, start, head, member)              \
   for (pos = NULL, pos = list_container_of((start), pos, member);              \
        &pos->member != (head);                                         \
        pos = list_container_of(pos->member.next, pos, member))

#define LIST_FOR_EACH_ENTRY_FROM_REV(pos, start, head, member)          \
   for (pos = NULL, pos = list_container_of((start), pos, member);              \
        &pos->member != (head);                                         \
        pos = list_container_of(pos->member.prev, pos, member))
#define list_for_each_entry(type, pos, head, member)                    \
   for (type *pos = list_entry((head)->next, type, member),        \
             *__next = list_entry(pos->member.next, type, member); \
        &pos->member != (head);                                         \
        pos = list_entry(pos->member.next, type, member),          \
        list_assert(pos == __next, "use _safe iterator"),               \
        __next = list_entry(__next->member.next, type, member))

#define list_for_each_entry_safe(type, pos, head, member)               \
   for (type *pos = list_entry((head)->next, type, member),        \
             *__next = list_entry(pos->member.next, type, member); \
        &pos->member != (head);                                         \
        pos = __next,                                                   \
        __next = list_entry(__next->member.next, type, member))

#define list_for_each_entry_rev(type, pos, head, member)                \
   for (type *pos = list_entry((head)->prev, type, member),        \
             *__prev = list_entry(pos->member.prev, type, member); \
        &pos->member != (head);                                         \
        pos = list_entry(pos->member.prev, type, member),          \
        list_assert(pos == __prev, "use _safe iterator"),               \
        __prev = list_entry(__prev->member.prev, type, member))

#define list_for_each_entry_safe_rev(type, pos, head, member)           \
   for (type *pos = list_entry((head)->prev, type, member),        \
             *__prev = list_entry(pos->member.prev, type, member); \
        &pos->member != (head);                                         \
        pos = __prev,                                                   \
        __prev = list_entry(__prev->member.prev, type, member))

#define list_for_each_entry_from(type, pos, start, head, member)        \
   for (type *pos = list_entry((start), type, member);             \
        &pos->member != (head);                                         \
        pos = list_entry(pos->member.next, type, member))

#define list_for_each_entry_from_safe(type, pos, start, head, member)   \
   for (type *pos = list_entry((start), type, member),             \
             *__next = list_entry(pos->member.next, type, member); \
        &pos->member != (head);                                         \
        pos = __next,                                                   \
        __next = list_entry(__next->member.next, type, member))

#define list_for_each_entry_from_rev(type, pos, start, head, member)    \
   for (type *pos = list_entry((start), type, member);             \
        &pos->member != (head);                                         \
        pos = list_entry(pos->member.prev, type, member))
#endif

上述代码和内核一样，声明成list.h就可搬到代码使用了。

总结

本文重新分析了内核list的实现，并找到了原来自己写的list.h。可以发现，对于不同的list实现，思路并不是一样的。

我在分析内核的实现的时候，还得停下来想一会儿，才能清楚。但是分析自己原来写的东西的时候，一下就知道当时自己为什么这么写，很快就给出了图示。

所以人的思维还是有一定定式的，如果是内核的实现方式方式，我并不一定能想到并写出来。而自己的实现又没有常常去复习。所以这才是我现场写不出来一个双向循环链表的根本原因吧，自省之~

目录

结构体

初始化

插入

删除

替换

交换

移动

拼接