Linked List in C:wl_list 的实现

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

Singly Linked List
Singly Linked List

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

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

Doubly Linked List
Doubly Linked List

普通实现

1
2
3
4
5
6
/* 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

使用方法大概是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 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 内核的链表实现。

实现是这样的:

1
2
3
4
5
6
struct wl_list {
/** Previous list element */
struct wl_list *prev;
/** Next list element */
struct wl_list *next;
};

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

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

1
2
3
4
5
6
7
8
9
10
11
12
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 的实现,别无二致:

1
2
3
4
5
6
7
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 方法可以帮助我们做到。用法如下:

1
2
3
4
5
6
7
8
9
10
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:元素结构中链表成员的名字

如果链表长度是 nwl_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 的地址了。具体定义如下:

1
2
3
4
#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))