Linux 链表 list_head_init_list_head

参考文章

list_head

内核关于链表的代码定义在：include/linux/list.h
list_head 结构体，它分别有一个next指针和prev指针 都是struct list_head 类型。

struct list_head {
    struct list_head *next, *prev;
};
1
2
3

内核链表的设计思想：既然链表不能包含万事万物，那么就让万事万物来包含链表。
一个链表节点包含数据域：person.age，链表域：list。

//用自定义类型的struct 包含list_head，即用万物包含链表。
struct person 
{
     struct list_head list;
     int age;
};
1
2
3
4
5
6

定义一个head

定义一个head结构体，head 通常不会用来存储数据。
它的作用就是方便找到其它节点，牵着头节点就可以找到这条链表中的任何一个节点。

struct person person_head;		
INIT_LIST_HEAD(&head.list)	
1
2

//第一步：根据自己的数据类型定义一个person_head结构体
//第二步：对head 做初始化，所谓的初始化就是让person_head中的list头指针和尾指针都指向自己

INIT_LIST_HEAD 的原型如下
内核中有两种方法可以初始化一个链表头节点：INIT_LIST_HEAD、LIST_HEAD
它们的不同点在于INIT_LIST_HEAD 需要自己定义一个list_head，而LIST_HEAD只需要传入一个变量名。

INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list->prev = list;
}


#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)
1
2
3
4
5
6
7
8
9
10

添加一个新节点

向一条链表添加一个新的节点，我们首先要了解链表的结构。如图，是一条完整的链表：

它拥有head 头节点和，list_head1~list_headn 个数据节点。注意：头不存放数据，只是为了能找到其它节点；list_head1-n 可以存放数据。

头插法：
添加新节点有头插法和尾插法，我们先来看一下头插法，对应内核中的函数是list_add：

static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

首先，我们假设现在有一个已经初始化号的头节点，它的prev 和next 分别指向自己。

要安插一个new节点，调用list_add->__list_add
next->prev = new; //next在list_add 中传入的是head->next，此时的head->next 指向的是head（head->next = head）
//那么这里的next 就是head，得出结论 head->prev = new head 的前一个指向的是new。
new->next = next; //new 的后一个指向的是 head。
new->prev = prev; //new 的前一个指向的是 head。
prev->next = new; //head 的后一个指向的是 new。

得到的结果就是两个结构体的next、prev 互相指。

添加 第二个节点new2，假设上一步添加的节点为new1
next->prev = new; //在list_add 传入参数head->next 此时已经指向了new1，这里的next 就是new1
//那么就是new1->prev =new2，new1的prev 指向了new2
new->next = next; //new2->next 指向new1
new->prev = prev; //new2->prev 指向head
prev->next = new; //head->next 指向new2

最终结果就是如下图：
（头插法：新插入的节点永远会再上一个插入的前面，例如new2在new1的前面）

以此类推再插入一个新的节点，new3 又会再new2 的前面。
最后插入的节点它的prev 永远指向head，head的prev 永远指向第一个节点。next 刚好与prev 相反。
后面添加的节点会向左边new4、new5 … 依次增长。

尾插法：

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

尾插法对应内核函数list_add_tail，它也是调用的__list_add。
添加节点过程：添加第一个节点时，最终的结果是new1 和 head的 prev 和next互相指。添加第二个节点时这里把new 看成new2，head->prev 指向的是new1 所以看成new1，head还是head 依次代入到 __list_add 函数里面。以此类推添加其它节点。
__list_add(new, head->prev, head);
得到的结果如图，和头插法相反 新节点会像右不断的增长。

遍历链表

构建好一个完整的链表后，我们需要通过遍历链表来查找节点，访问其中的数据域。
遍历链表使用函数：list_for_each

//include/linux/list.h
#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)
1
2
3

pos 是一个指针，目的是偏移，指向某个节点；head 就是链表头，与上一步的head 相同。
list_for_each 是一个宏，它本身的内容其实就是一个for 循环：
① pos = (head)->next，pos 偏移到链表的头节点或尾节点 （原因是头插 和 尾插的不同）。
② pos != (head)，判断pos 指向的节点是不是head，是的话就说明一整个链表遍历完了，退出for 循环。
③ pos = pos->next，pos 再次偏移向下一个节点。如果①中 pos 是头节点，那么就会不断的向后（右，参考尾插法图）偏移，如果是尾节点那么就不断的向前（右，参考头插法图）偏移。每偏移一次都会判断一下②，直到遍历完所有的节点回到head。

再for 循环中可以访问节点的数据域，如下：

list_for_each(pos, head){
	strcut person* person1 = container_of(pos,struct person,list)
	printk("age = %d\n", person1->age)
}
1
2
3
4

因为 list_head 中并没有数据域，所以我们要获取包含这个list 的person 结构体。这就会用到container_of 或 offsetof 宏，它可以通过list 的地址获取到包含这个list 的结构体，person 也可以替换成其它类型。
container_of 和offsetof参考
我们后面把包含list 成员的结构体称为容器结构体 ，例如person。
内核又对container_of 宏做了封装，换了个名字 list_entry。用这两个宏的效果是一样的。

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
1
2

list_for_each_entry
在上面我们遍历链表，然后用list_entry 获取到容器结构体，再访问容器结构体中的内容，这样的步骤太麻烦。所以内核为我们想到了解决方法：宏list_for_each_entry。
list_next_entry 就是在list_entry 上再做出扩展。可以把pos 偏移到下一个list，然后返回list 所在的容器结构体。
list_for_each_entry 遍历整个链表所有的list，然后找到它所在的容器，在for循环里就可以直接访问容器结构体了。
注意： list_for_each_entry 传入的参数pos 是容器类型的指针，而不是 struct list_head* 。

#define list_next_entry(pos, member) \
	list_entry((pos)->member.next, typeof(*(pos)), member)

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

删除节点

对于删除链表节点，内核定义了函数list_del。

static inline void __list_del(struct list_head *prev, struct list_head *next)
{
    next->prev = prev;
    prev->next = next;
}

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 *entry)
{
	__list_del_entry(entry);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

首先判断entry 是否有效，如果entry == NULL 则无效。
接着调用到了__list_del， 是关于指针的操作。可以想象一个节点n，它的前一个节点是n-1，后一个节点是n+1，把n 带入到代码中的entry：
__list_del(entry->prev, entry->next); entry->prev 就是n-1，entry->next 是n+1。
next->prev = prev; n+1 的前一个是本来是n，现在改成n-1。
prev->next = next; n-1 的后一个本来是n，现在改成了n+1。 如此n 就在n-1 和n+1 中间删除了，链表中也就没有了n节点。
如果一条链表中只有两个节点：head 和 n。他们两个的关系是next 和perv 都指向对方，删除n 后又变成了head 自己指自己。
最后将entry 的next、prev 指向LIST_POISON1 和 LIST_POISON2，这个是内核设置的一个区域。

使用list_del 可以从链表中删除一个节点，但是如果你想在遍历链表时删除一个节点，那么删除它后必须执行break 跳出for 循环，否则就会发生段错误，如图：

为什么会这样，我们来看list_for_each_entry 的实现，假设我们遍历找到了节点(pos)->member ，删除之后for 循环还会继续利用(pos)->member.next 来找到下一个节点，但是此时它指向LIST_POISON1，所以这样时不对的。

#define list_next_entry(pos, member) \
	list_entry((pos)->member.next, typeof(*(pos)), member)

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

为了应付这个问题，内核开发者又想出了新的宏list_for_each_entry_safe，它与list_for_each_entry 的区别就是它提供了一个新的指针n，在遍历的时候提前把pos 的下一个节点n获取到了，所以即使pos 被删除也没关系，因为它用的是n 来寻找下一个。

#define list_for_each_entry_safe(pos, n, head, member)			\
	for (pos = list_first_entry(head, typeof(*pos), member),	\
		n = list_next_entry(pos, member);			\
	     &pos->member != (head); 					\
	     pos = n, n = list_next_entry(n, member))
1
2
3
4
5

替换节点

使用一个单独的节点替换链表中的某一个节点，可以用 list_replace：

static inline void list_replace(struct list_head *old,
				struct list_head *new)
{
	new->next = old->next;
	new->next->prev = new;
	new->prev = old->prev;
	new->prev->next = new;
}
1
2
3
4
5
6
7
8

由于list_replace没有将old的前驱和后继断开，所以内核又提供了：list_replace_init

static inline void list_replace_init(struct list_head *old,
					struct list_head *new)
{
	list_replace(old, new);
	INIT_LIST_HEAD(old);
}
1
2
3
4
5
6

移动节点

内核链表还提供给我们：list_move
list_move就是删除list指针所处的容器结构节点，然后将其重新以头插法添加到另一个头结点中去，head可以是该链表自身，也可以是其他链表的头指针。

static inline void list_move(struct list_head *list, struct list_head *head)
{
	__list_del_entry(list);
	list_add(list, head);
}
1
2
3
4
5

既然有头插法的list_move，那么也同样有尾插法的list_move_tail：

static inline void list_move_tail(struct list_head *list,
				  struct list_head *head)
{
	__list_del_entry(list);
	list_add_tail(list, head);
}
1
2
3
4
5
6

判断链表是否空

如果head->next == head 的话，那么这是个空链表

static inline int list_empty(const struct list_head *head)
{
	return READ_ONCE(head->next) == head;
}
1
2
3
4