内核中常见的数据结构链表之分析及应用作为实现 Linux 内核代码的主体语言 C，它是朴素的、直接的，直接到你可以对硬件寄 存器的某一位进行操作，C 语言又是原始的，基本的，基本的就像构建大厦的一块块砖， 运用它，你可以随意地建造自己梦想中的大厦。但是，与其他语言不同，C 语言标准库中并没有对数据结构的支持函数，比如，没有对 链表、队、栈、树等数据结构操作的函数集合，但在 Linux 内核代码中，随处都可以觅见 这些数据结构的踪影。现实世界中数据的组织形式逃脱不出数据结构课程所涵盖的那些结构，相对于其他数据 结构而言，链表这种组织方式更常用和灵活，或者说，其他数据结构，都可以从链表衍生 而来。在 Linux 内核源代码树中，include/linux/list.h 文件中用 GNU C 语言实现了封装好的、易 用的双向链表函数集合，这种实现是高效和可移植的-否则，这些代码也进不了内核，同 时，这种实现又是巧妙和可见的，赏析这些代码，让我们领悟内核代码设计之美妙。1. 链表及衍生为什么链表是数据组织的根本形式？最简单的数组组织形式是数组，它在内存顺序存放，其存取效率无疑是高效的，但除非 你存放的数据是静态的，否则，增加和删除一个元素的代价是不可小估的。而链表，在建 立之初，无需知晓其节点是多少，在构建过程中，增加和删除一个节点与链表的长度无关， 主要开销为访问的顺序性和链表节点所占的空间。尽管链表可以分类为单链表、双链表和循环链表，但在此，以分析双链表为基点，从而 退化或者衍生出其他数据结构。在 C 语言中，一个基本的双向链表定义如下：struct my_list void *mydata; struct my_list *next; struct my_list *prev; ; 图 2. 1 双链表图 2.1 是一双链表，通过前趋（prev）和后继（next）两个指针字段，就可以从两个方向遍历双链表，这使得遍历链表的代价减少。如果打乱前驱、后继的依赖关系，就可以构成“ 二叉树“；如果再让首节点的前趋指向链表尾节点、尾节点的后继指向首节点（如图 1 中虚 线部分） ，就构成了循环链表；如果设计更多的指针字段，就可以构成各种复杂的树状数据 结构。如果减少一个指针域，就退化成单链表，如果只能对链表的首尾进行插入或删除操作， 就演变为队结构，如果只能对链表的头进行插入或删除操作，就退化为栈结构。 如此看来，双链表，是演化各种数据结构的基石。 2. 链表的实现抽象是软件设计中一项基本技术，如上所述，在众多数据结构中，选取双向链表作为基 本数据结构，这就是一种提取和抽象。 1）简约而又不简单的链表定义 于双向链表而言，内核中定义了如下简单结构：struct list_head struct list_head *next, *prev; ; 这个不含任何数据项的结构，注定了它的通用性和未来使用的灵活性，例如前面的例子就 可以按如下方式定义： struct my_list void *mydata; struct list_head list; ; 在此，进一步说明几点：list 字段，隐藏了链表的指针特性，但正是它，把我们要链接的数据组织成了链 表。 struct list_head 可以位于结构的任何位置可以给 struct list_head 起任何名字。在一个结构中可以有多个 list 简约而又不简单的 struct list_head，以此为基本对象，就衍生了对链表的插入、删除、 合并以及遍历等各种操作： 2）链表的声明和初始化宏 实际上， struct list_head 只定义了链表节点，并没有专门定义链表头，那么一个链表结 构是如何建立起来的？让我们来看看下面两个宏： #define LIST_HEAD_INIT(name) static inline void list_add();static inline void list_add_tail(); -/* Insert a new entry between two known consecutive entries. * This is only for internal list manipulation where we know* the prev/next entries already!*/ 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;prev-next = new; - /* list_add - add a new entry* new: new entry to be added* head: list head to add it after* Insert a new entry after the specified head.* This is good for implementing stacks.*/ static inline void list_add(struct list_head *new, struct list_head *head) _list_add(new, head, head-next); -/* list_add_tail - add a new entry* new: new entry to be added* head: list head to add it before* Insert a new entry before the specified head. * This is useful for implementing queues.*/ static inline void list_add_tail(struct list_head *new, struct list_head *head) _list_add(new, head-prev, head); -仔细体会其实现代码，看起来简单有效，但实际上也是一种抽象和封装的体现。首先 _list_add()函数做基本的操作，该函数仅仅是增加一个节点，至于这个节点加到何处，暂 不考虑。list_add（）调用_list_add()这个内部函数，在链表头增加一个节点，实际上实现 了栈在头部增加节点的操作，而 list_add_tail()在尾部增加一个节点，实际上实现了队的操 作。至于链表的删除、搬移和合并，读者自行分析，不再此一一讨论3. 遍历链表似走过千山万水遍历链表本是简单的，list.h 中就定义了如下的宏： -* list_for_each - iterate over a list* pos: the pos != (head); pos = pos-next)-这种遍历仅仅是找到一个个节点在链表中的偏移位置 pos，如图 2.2 所示。图 2.2 遍历链表问题在于，如何通过 pos 获得节点的地址，从而可以使用节点中的数据？ 于是 list.h 中定 义了晦涩难懂的 list_entry（）宏： - /* list_entry - get the struct for this entry* ptr: the struct list_head list; ; struct list_head *ptr; 则 list_entry(ptr, mylist, list)宏，就可以根据 ptr 的值，获取 mylist 的地址，也就是指向 mylist 的指针，这样，我们就可以存取 mylist-mydata 字段了。可为什么能够达到这样的效果？ list_entry(ptr, mylist, list) 展开以后为：(struct my_list *)(char *)(ptr) - (unsigned long)( struct list_head list; int from; ; int main(int argc, char *argv)struct kool_list *tmp; struct list_head *pos, *q; unsigned int i;struct kool_list mylist; INIT_LIST_HEAD( /*初始化链表头*/* 给 mylist 增加元素 */ for(i=5; i!=0; -i) tmp= (struct kool_list *)malloc(sizeof(struct kool_list); /* 或者调用 INIT_LIST_HEAD( */ printf(“enter to and from:“); scanf(“%d %d“, list_add( /*其参数要增加的元素和链表头*/ /* 也可以用 list_add_tail() 在表尾增加元素*/ printf(“n“); printf(“traversing the list using list_for_each()n“); list_for_each(pos, printf(“to= %d from= %dn“, tmp-to, tmp-from); printf(“n“); /* 因为这是循环链表，也可以以相反的顺序遍历它， *为此，需要用list_for_each_prev代替list_for_each， * 也可以调用 list_for_each_entry() 对给定类型的节点进行遍历。 */ printf(“traversing the list using list_for_each_entry()n“); list_for_each_entry(tmp, prin