Linked List in C：wl_list 的实现

链表是用来储存数据的线形结构。每个元素之间用指针来指向彼此，实现链接。

这篇文章主要是想分享一下今天看到的一种别于普通思路的实现：wl_list。

链表一般分三种结构：单向、双向、环形。这里以双向链表为例来介绍这种实现。

普通实现

/* Node of a doubly linked list */
struct Node { 
    int data; 
    struct Node* next; // Pointer to next node in DLL 
    struct Node* prev; // Pointer to previous node in DLL 
};

这种实现的思路是定义一种结构 Node，内含：

数据 data
指向上一个 Node 的指针 prev
指向下一个 Node 的指针 next

使用方法大概是这样的：

/* Start with the empty list */
struct Node* head = NULL;

// Insert 6.  So linked list becomes 6->NULL 
append(&head, 6); 

// Insert 7 at the beginning. So linked list becomes 7->6->NULL 
push(&head, 7); 

// Insert 1 at the beginning. So linked list becomes 1->7->6->NULL 
push(&head, 1); 

// Insert 4 at the end. So linked list becomes 1->7->6->4->NULL 
append(&head, 4); 

// Insert 8, after 7. So linked list becomes 1->7->8->6->4->NULL 
insertAfter(head->next, 8);

printList(head);

具体方法的视线可以参考这里。

另一种思路：`wl_list`

这是 C 内建的一个库。同时也是 Linux 内核的链表实现。

实现是这样的：

struct wl_list {
    /** Previous list element */
    struct wl_list *prev;
    /** Next list element */
    struct wl_list *next;
};

数据结构 wl_list 只包含了两个指针，分别指向上一个和下一个 wl_list。而这就是全部了。（如果链表是空的话，指针指向表的头部。）

你可能第一眼看到会疑惑在哪里存储数据。事实上，这种实现也只是把指针们单独抽出来作为一个数据结构，我们可以定义自己的数据结构，其中包含想存储的数据，以及这个 wl_list：

struct wl_list head; // list head

struct data {
    int value;
    struct wl_list link;
};
struct data e1, e2, e3;

wl_list_init(&head);
wl_list_insert(&head, &e1.link);   // e1 is the first element
wl_list_insert(&head, &e2.link);   // e2 is now the first element
wl_list_insert(&e2.link, &e3.link);    // insert e3 after e2

小窥一下 wl_list_insert 的实现，别无二致：

void wl_list_insert(struct wl_list *list, struct wl_list *elm)
{
	elm->prev = list;
	elm->next = list->next;
	list->next = elm;
	elm->next->prev = elm;
}

那如果要遍历链表呢。wl_list_for_each 方法可以帮助我们做到。用法如下：

struct element {
    int data;
    struct wl_list link;
};
struct wl_list head;
// Assume head now "contains" many messages
struct element pos;
wl_list_for_each(&pos, &head, link) {
    do_something_with_element(&pos);
}

该方法的三个参数分别是：

pos：将会被赋值成每个元素的值的指针

head：需要遍历的链表头

member：元素结构中链表成员的名字

如果链表长度是 n，wl_list_for_each 就会执行内部的 do_something_with_element n 次，每一次 pos 都会依次指向相应的元素。

额外问题

看起来好像就那么回事，但是问题来了，head 是链表的头，link 也没包含实际元素的信息，wl_list_for_each 是怎么知道要给 pos 赋什么值的呢？

很简单，假设 element 的内存结构如下：

link 离数据结构起始位置的偏移量（offset）是 x 字节。wl_list_for_each 既然有 link 成员的地址，直接将这个地址减去 x 就能得到 data 的地址了。具体定义如下：

#define wl_list_for_each(pos, head, member)				\
	for (pos = wl_container_of((head)->next, pos, member);	\
	     &pos->member != (head);					\
	     pos = wl_container_of(pos->member.next, pos, member))

wl_container_of 接受三个参数：指向被包含的成员（wl_list）的指针、包含这个指针的样本、样本中该指针的名字。它返回一个首个含有该指针的容器。它的定义如下：

1
2
3

#define wl_container_of(ptr, sample, member)				\
	(__typeof__(sample))((char *)(ptr) -				\
			     offsetof(__typeof__(*sample), member))

普通实现

另一种思路：wl_list

额外问题

另一种思路：`wl_list`