恢宏宏的宏 循环双链表结构

linux 的内核源代码中, 有一个很重要的数据结构, 循环双链表. 在 $KERNEL_SOURCE_PATH/include/linux/list.h 中被完整实现.

按道理来讲, 循环双链表, 是一种很简单的数据结构. 不过这篇 post 的目的就在于说明, 良好的设计是多么重要.

其特点很鲜明, 就是将链表独立, 和数据分离开来.
好处是显而易见的, 构造链表更方便了, 而且更通用了. 不然, 也不会放到 linux 的内核源代码中, 作为最基本的数据结构嘛. 囧

任何想要被 linked 的数据, 只需要建立 struct 结构体, 然后在其中放入 struct list_head 就ok了.
也就是说, 数据中存放着链表. 是不是听着很奇怪? 一般来讲, 应该是链表中存放数据才对. 这一点也就是 linux 的此种实现方式的超级大优点了. 下面会具体分析之.

不过既然链表是存放在数据中的, 如何通过链表来访问数据呢? 也就是如何通过部分来访问整体呢? 使用 list_entry(pos, type, member) 就ok了.

下面来说说具体实现.
先就其使用方面, 对 list.h 进行一个结构剖析.

如果要查看内核源代码中的原始文件, 点击这里.
和我机器上的内核版本是一致的, 都是 2.6.27-9-generic.
这份原始代码是不能直接移植到其他项目中的, 因为其中包含了对多核心处理器的支持, gcc 编译器特有的命令 typeof(*pos) 等等, 所以, 只能在内核空间, 而非用户空间使用.

不过呢, 这份原始代码的可移植性很好, 很容易被移植到其他项目中, 简单的做些处理就ok了. 一份已经处理妥善的, 符合 ANSI-C 标准, 可以直接使用的代码点击这里下载.
如果无法下载, 点击这里查看.

ok, 剖析正文开始. 在文本编辑器上编辑好之后, 直接粘贴过来的. 囧
---------------------------------
list.h 接口剖析.

list.h 接口剖析, by jtuki:
---------------------------------
struct list_head;
最基本的链表结构体. 定义了前向指针 *prev, 后向指针 *next.

> 直接声明, 继而初始化一个 list_head 结构体.
LIST_HEAD(name);
效果等同于
do {
struct list_head name;
INIT_LIST_HEAD(&name);
} while(0);

> 链表初始化.
INIT_LIST_HEAD(ptr);
使用 #define 宏实现. 初始化一个 struct list_head 结构指针 ptr.

> 往链表中添加元素.
* @new: new entry to be added
* @head: list head to add it
static inline void list_add(struct list_head *new, struct list_head *head);
static inline void list_add_tail(struct list_head *new, struct list_head *head);
都利用了 __list_add(new, prev, next) 函数.

> 删除链表中某个 entry.
list_del(struct list_head *entry);
list_del_init(struct list_head *entry); /* 删除 entry 后立即将其初始化
       INIT_LIST_HEAD(entry); */

> 从某个链表中取出某个 entry, 然后移动到另外一个链表中.
* @list: the entry to move
* @head: the head that will precede our entry
static inline void list_move(struct list_head *list, struct list_head *head);
static inline void list_move_tail(struct list_head *list,
               struct list_head *head)

> 检测是否为空链表.
static inline int list_empty(struct list_head *head);

> 粘结两个链表.
* @list: the new list to add.
* @head: the place to add it in the first list.
static inline void list_splice(struct list_head *list, struct list_head *head);
static inline void list_splice_init(struct list_head *list,
                 struct list_head *head) /* 对变成了空链表的 list 做初始化,
                       INIT_LIST_HEAD(list); */

> 获得 struct list_head *ptr 的 ptr 所在的 struct 结构体指针.
struct type entry = list_entry(ptr, type, member);
/**
* list_entry - get the struct for this entry
* @ptr:    the &struct list_head pointer.
* @type:   the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
 ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

> 对链表进行遍历.
/**
* list_for_each    -   iterate over a list
* @pos:    the &struct list_head to use as a loop counter.
* @head:   the head for your list.
*/
list_for_each(pos, head) {...}
list_for_each_prev(pos, head) {...}

/**
* list_for_each_safe   -   iterate over a list safe against removal of list entry
* @pos:    the &struct list_head to use as a loop counter.
* @n:      another &struct list_head to use as temporary storage
* @head:   the head for your list.
*/
也就是譬如 pos 所在的结构体是通过 malloc 分配的, 那么这个 list_for_each_safe 就是要保证 ---
将 pos 所在的结构体释放掉后, 依然能够通过 n 找到 pos->next.
list_for_each_safe(pos, n, head) {...}

> 直接对结构体, 而非链表, 进行遍历.
list_for_each_entry(pos, head, member) {...}
注意: 这个函数我在源代码中用 #ifdef GCC_COMPILER 掩盖掉了. 因为其使用了 GCC 特有的 typeof(*pos)
运算符. 如果需要, 可以用可移植的方式将其重新写出, 但是我觉得似乎没有必要, list_for_each 就足够了.
接口越多, 容易引发的问题越多.

好了, 接口就是这么多. 是不是很简单? 我估计答案是「不是」. 囧
第一眼望去, 确实显得有些复杂, 不过多看几遍就ok了. 如果多看几遍还是觉得复杂, 那么估计就是我的表达问题了.
---------------------------------
list.h 实现分析

源代码中有一个部分可能难以理解. 就是 list_entry(ptr, type, member) 宏定义. 我看到这部分代码后, 先是一愣 --- 这是啥实现方式? 继而是摇头 --- F***, 简直是太巧妙了. 囧
不过其实仔细想想, 也挺简单, 只是很巧妙罢了, 就是通过计算偏移量, (unsigned long) & ((type *)0)->member, 或者是更加稳妥一些的 (unsigned long) ((char *)&(((type *)0)->member) - (char *)((type *)0)), 和一系列的强制指针类型转换来完成之.

/**

 * list_entry - get the struct for this entry
 * @ptr:    the &struct list_head pointer.
 * @type:   the type of the struct this is embedded in.
 * @member: the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \

    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

如果没法理解这段代码, 参考 C-FAQ 中的 Question 2.14, 以及这里的讲解, Linux Kernel Linked List Explained .

关于偏移量的问题, 在 ANSI-C 的 stddef.h 中有关于 offsetof(type, member) 的定义. 之所以要有针对结构体的 offsetof 定义, 是由于不同的编译器对于结构体的解释不同.
我这里写了一段代码, 来解释这一点 ---

#include <stdio.h>
#include <stdlib.h>

struct my_struct {
 unsigned int x;
 char y;
 struct my_struct *ptr;
};

int main()
{
 unsigned long offset_x, offset_y, offset_ptr;

 offset_x = (unsigned long)(& ((struct my_struct *)0)->x);
 offset_y = (unsigned long)(& ((struct my_struct *)0)->y);
 offset_ptr = (unsigned long)(& ((struct my_struct *)0)->ptr);
 printf("%lu, %lu, %lu\n", offset_x, offset_y, offset_ptr);

 offset_ptr = (unsigned long) (                             \
             (char *) & ((struct my_struct *)0)->ptr -   \
             (char *)((struct my_struct *)0));
 printf("%lu\n", offset_ptr);

 return 0;
}

运行一下, 就会发现在 gcc 平台下结果是:

0, 4, 8
8

而非 0 4 5, 其中的缘故就是因为 gcc 对结构体有所谓空洞的添加. 所以每个 char 类型也就分配了4个字节, 而非1个字节.
如果要强制1个字节怎么办?
使用结构体的位域技术就ok了, 不过这里就不阐述啦.

其次需要注意的是, list_for_each(pos, head) {...}, 以及list_for_each_safe(pos, n, head)的不同适用范围. 这一点很重要!

/**
 * list_for_each    -   iterate over a list
 * @pos:    the &struct list_head to use as a loop counter.
 * @head:   the head for your list.
 */

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

/**
 * list_for_each_safe   -   iterate over a list safe against removal of list entry
 * @pos:    the &struct list_head to use as a loop counter.
 * @n:      another &struct list_head to use as temporary storage
 * @head:   the head for your list.

 */
#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
        pos = n, n = pos->next)

注释里阐述的很清楚了, 就不赘述了.

- EOF -