链表概述
链表作为一种基本的数据结构，得益于其简单的结构、优良的性能（双向链表的插入和删除复杂度都是O(1))，被广泛的应用于各种程序设计中。链表一般分为单向链表和双向链表。对于单向链表，其删除和插入的一般复杂度都是O(n)，所以，工程上一般很少使用，下面介绍的所有链表都是双向链表。
常见的双向链表数据结构定义如下：
struct list_node_xxx{ struct list_node_xxx *prev，*next； //具体的数据，比如一个char数组 char data[100]; };
- prev和next分别指向当前节点的前驱和后继节点。
- 每个节点中包含具体的数据。
设计思想
Linux内核同样支持双向链表，其设计十分的精巧，下面是它的定义：
struct list_head { struct list_head *next, *prev; };
首次看到内核链表的定义，第一种感觉就是惊艳，真的是太简洁了，之后，就有些疑问这样的结构如何实现链表功能呢？相信第一次看到这种链表定义的你同样会被惊艳到（:>
后来经过多年对于内核链表的使用经历，慢慢领会到了这种设计的精髓，简单说一下自己的感受吧，如有不妥之处，欢迎批评指正 （:>
- 这种设计完美的践行了Linux内核的设计哲学：机制和策略分离。
机制和策略分离，是Linux内核，乃至整个Linux社区共同遵守的设计哲学。机制用来提供具体的功能，而策略用来指定如何使用这项功能。机制是稳定的，而策略是千变万化的。就像原子是万物运行的基本机制一样，而纷繁复杂的世界就是原子的不同组合策略的表象。内核链表很好的诠释了机制与策略分离的设计哲学。struct list_head仅仅定义了链表这种机制所需的最小集合，具体到策略，也就是链表的具体使用者，可以组合这种链表机制来实现链表的相关功能。
- 数据与结构解耦，内核只需一个链表定义即可。
传统的链表定义，将数据和结构耦合到了一起，这种数据结构一般只会使用一种业务场景，业务场景改变之后，需要重新定义链表数据结构，相应的对于的链表的操作接口，也需要重新定义。对于简单的系统来说，这种链表的定义和使用方式一般是没有问题的。但是，对于复杂的系统，其会有各种各样的业务子系统，每个子系统有可能都会使用到链表这种数据结构。如果仍然遵照传统的链表使用模式，去分别定义链表，可想而知，对于链表的扩展和维护将是十分的困难的。
基于传统链表存在的“缺陷“，Linux内核设计者独辟蹊径，创造性的将”数据“和“结构”进行了解耦，从此，只需要定义一种链表结构，完成一套链表操作接口，就可以实现所有链表的统一管理。
- 统一链表操作接口，面向接口编程
面向对象编程中，有一条基本的设计原则：面向接口编程，而不是面向定义编程。虽然，内核的代码是完全使用C语言这种面向过程中的语言实现的，但是，面向对象编程是与语言无关的，根本意义上它是一种比较高阶的设计思想，对于大型复杂的系统，其都有重要的指导意义。好了，回归到Linux内核链表的设计，其很好的遵循了面向接口编程的原则。内核对于链表这种数据结构，进行了彻底的抽象，使其不与任何具体的数据相关，可以说，其是一个“纯粹”的链表，配合这种链表结构的接口，是全局统一的，任何业务子系统在使用链表这种结构时，面向的都是统一的操作接口。这种操作的便利性是十分重要的，联想一下扳手和螺母的关系就可以深刻的体会到这一点。
好了，上面就是关于内核链表的几点感悟，原理总是抽象的，只有亲身尝试使用，才能有深刻的体会，下面说一下内核链表的基本使用方式。
使用方式
Linux内核中关于链表的定义位置：/include/linux/list.h，里面定义了关于链表所有的操作接口。
链表结构
struct list_head { struct list_head *next, *prev; };
定义链表
struct list_node_xxx{ char data[10]; struct list_head list; ... ... }node_xxx;
- struct list_node_xxx：具体的链表定义。
- data：链表的具体数据。
- list：链表结构，数据与结构分离。
初始化
#define LIST_HEAD_INIT(name) { &(name), &(name) } #define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name) static inline void INIT_LIST_HEAD(struct list_head *list) { WRITE_ONCE(list->next, list); list->prev = list; }
链表定义了之后，需要初始化之后才能使用，LIST_HEAD_INIT宏和INIT_LIST_HEAD可以完成链表的初始化，比如初始化struct list_node_xxx结构中的链表。
struct list_node_xxx node_xxx; INIT_LIST_HEAD(&(node_xxx.list));
插入
链表的插入方式，分为头插和尾插。
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); }
这两个API都是调用__list_add函数实现的，双下划线开头表明这是一个内部使用函数。
static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { if (!__list_add_valid(new, prev, next)) return; next->prev = new; new->next = next; new->prev = prev; WRITE_ONCE(prev->next, new); }
删除
删除链表节点十分的高效、简单。
static inline void list_del(struct list_head *entry) { __list_del_entry(entry); entry->next = LIST_POISON1; entry->prev = LIST_POISON2; } 其中，\_\_list_del_entry用于删除链表节点，之后，两条语句用于将entry的next和prev指针置为无效的链表表项。 static inline void __list_del_entry(struct list_head *entry) { if (!__list_del_entry_valid(entry)) return; __list_del(entry->prev, entry->next); } static inline void __list_del(struct list_head * prev, struct list_head * next) { next->prev = prev; WRITE_ONCE(prev->next, next); }
- 链表空测试
测试链表为空。 static inline int list_empty(const struct list_head *head) { return READ_ONCE(head->next) == head; }
- 遍历链表
上文说了，Linux内核链表的设计哲学是：数据与结构分离。内核一般不会直接使用链表这种结构，而是会将其嵌入到具体的业务数据结构中，比如上面的struct list_node_xxx。那么，问题来了，到目前为止，我们涉及到的所有关于链表的接口参数都是struct list_head指针，而struct list_head一般嵌入到的了具体的业务数据结构中，问题就是我们该如何通过struct list_head访问到真正的业务数据结构呢？对于struct list_node_xxx就是如何通过 head访问到node_xxx呢？这里就是必须借助于list_entry这个工具宏。
/** * 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_head within the struct. */ #define list_entry(ptr, type, member) \ container_of(ptr, type, member) /** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */ #define container_of(ptr, type, member) ({ \ const typeof(((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
可以看到list_entry调用的是container_of这个宏，下面来看一下，container_of的工作原理。container_of包含三个入参：ptr，type，member，其与list_entry的三个参数完全相同。这三个参数可能比较抽象，下面通过一张图来分析一下，我们还是以struct list_node_xxx为例。
图中，标出了相对于struct list_node_xxx来说，ptr,type,member三个参数所指的含义，而“？”表示我们关心的目标业务数据结构的地址，本地来说就是node_xxx的地址。
- ptr:表示node_xxx结构中，list的地址
- type:表示struct list_node_xxx这个结构体类型
- member:表示struct list_head在struct list_node_xxx中的字段名
container_of宏分为两部分：
1. const typeof(((type *)0)->member ) *__mptr = (ptr); 2. (type *)( (char *)__mptr - offsetof(type,member) );
第一部分的作用是为获得__mptr指针。typeof是GNU/GCC的扩展关键字，可以通过变量名获得变量的类型。((type *)0)->member将0这个特殊的地址强制类型转换为type类型，这里就是struct list_node_xxx这个结构体，然后，获得这个结构体的中变量字段名，之后再通过typeof获取其数据类型，这里就是struct list_head。
第二部分的作用是通过__mptr和list相对于node_xxx的位置，来计算node_xxx的地址。这里的offsetof宏用到的一个技巧(TYPE *)0)->MEMBER中的0的作用同第一部分。
上面就是list_entry的实现原理，下面说一下常用的链表遍历函数。
/** * list_for_each_entry - iterate over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. */ #define list_for_each_entry(pos, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member); \ &pos->member != (head); \ pos = list_next_entry(pos, member)) /** * list_for_each_entry_reverse - iterate backwards over list of given type. * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. */ #define list_for_each_entry_reverse(pos, head, member) \ for (pos = list_last_entry(head, typeof(*pos), member); \ &pos->member != (head); \ pos = list_prev_entry(pos, member))
list_for_each_entry正向遍历整个链表，pos表示指向当前的链表数据项的指针，head表示链表头，member表示struct list_head在链表数据项中的字段名。
list_for_each_entry_reverse用于反向遍历整个链表。
具体实例
下面通过一个实例，来展示如何使用内核中的链表。
struct list_node_xxx { char data[100]; struct list_head list; }; //定义链表头 LIST_HEAD(node_head); //省略地址有效性检查 struct list_node_xxx *node_xxx_1 = kzalloc(sizeof(*node_xxx), GFP_KERNL); struct list_node_xxx *node_xxx_2 = kzalloc(sizeof(*node_xxx), GFP_KERNL); //添加链表表项 list_add(&(node_xxx_1), &node_head); list_add(&(node_xxx_2), &node_head); struct list_node_xxx *entry; //遍历链表 list_for_each_entry(entry, &node_head, list) { memcpy(entry->data, "hello, world.", strlen(hello,world."); } //删除链表 struct list_head *pos; list_for_each(pos, &node_head) { list_del(pos); }
