链表概述

链表作为一种基本的数据结构，得益于其简单的结构、优良的性能（双向链表的插入和删除复杂度都是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);
}
复制代码

Linux内核基础数据结构-双链表

Linux内核基础数据结构-双链表

链表概述

设计思想

使用方式

具体实例