【数据结构】list.h 常用函数实现详解

---

一、概述

list.h文件里面实现了一个带头结点的循环双向链表，也实现了哈希表。不过在平时编程中，大多是使用其中的循环双向链表。 本文主要介绍这个循环双向链表的常用函数是怎样实现的。list.h文件位于Linux内核源码目录的include/linux/list.h，不同的内核版本，list.h文件会有些许不同，但总会有下面这些常用函数，这些函数也是本文分析重点

• INIT_LIST_HEAD：链表头结点初始化；
• list_add：链表头部插入条目；
• list_add_tail：链表尾部插入条目；
• list_del：删除条目
• list_for_each：遍历条目
• list_for_each_safe：遍历条目，防删除列表条目
• list_entry：获取结构体指针
• list_empty：判断链表是否为空

二、基础函数

这小节主要看 初始化函数 和 判断空链表函数 的实现。

介绍链表，一定需要先认识它的结点结构体，list.h的循环双链表结点结构体只包含了两个指针：next指针指向下一个结点；prev指向前一个结点。它没有像其他链表结点那样也包含了数据部分，那它是怎样存储数据并查找数据的呢？这个在后面讲解。结点结构体代码如下：

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

✨2.1 INIT_LIST_HEAD

链表头结点初始化函数实际上是一个宏，其代码实现如下：

#define INIT_LIST_HEAD(ptr) do { \
	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
1
2
3

就是将头结点的next指针 和prev指针 都指向自己。

---

✨2.2 list_empty

这是判断空链表函数，空链表返回真，非空链表返回假。从上面的图可知，当头结点的next指向自己，就是空链表：

/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}
1
2
3
4
5
6
7
8

三、添加结点的函数

添加结点主要介绍三个函数：__list_add、list_add、list_add_tail

✨3.1 __list_add

__list_add 是添加结点的基础函数，是一个静态内联函数。是list.h内部操作函数，一般不直接调用。
函数参数：
新结点指针；
上个结点指针；
下个结点指针；

代码如下：

/*
 * 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_node,
		struct list_head *prev,
		struct list_head *next)
{
	next->prev = new_node;
	new_node->next = next;
	new_node->prev = prev;
	prev->next = new_node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

分析：代码是先把新结点与next连接，再把新结点与prev连接，其操作如下图：

---

✨3.2 list_add

list_add 是在链表头部插入结点，它调用了__list_add去实现的；

函数参数：
new_node：新结点指针
head：头结点指针

代码实现如下：

/**
 * 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_node, struct list_head *head)
{
	__list_add(new_node, head, head->next);
}
1
2
3
4
5
6
7
8
9
10
11
12

分析：在头部插入新结点就相当于在头结点和第一个结点之间插入，链表不为空的情况下，head->next指向第一个结点，操作如下图：

如果是空链表，head->next指向head，相当于调用 __list_add(new_node, head, head);，操作如下图：

---

✨3.3 list_add_tail

list_add_tail 是在链表尾部插入结点，也是它调用了__list_add去实现的；

函数参数：
new_node：新结点指针
head：头结点指针

代码实现如下：

/**
 * 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_node, struct list_head *head)
{
	__list_add(new_node, head->prev, head);
}
1
2
3
4
5
6
7
8
9
10
11
12

分析：在尾部插入新结点就相当于在头结点和最后结点之间插入，链表不为空的情况下，head->prev指向第一个结点，操作如下图：

---

四、删除结点的函数

删除结点主要介绍两个函数：__list_del、list_del

✨4.1 __list_del

__list_del 是删除结点的基础函数，是list.h内部操作函数，一般不直接调用。

函数参数：
prev：要删除的结点的上一个结点指针
next：要删除的结点的下一个结点指针

代码实现如下：

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}
1
2
3
4
5
6
7
8
9
10
11
12

---

✨4.2 list_del

list_del可以删除指定的结点，其参数是一个有效的结点指针。调用了__list_del(entry->prev, entry->next);，把当前结点的上个结点和下个结点作为参数传给 __list_del，删除了自己。

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty on entry does not return true after this, the entry is
 * in an undefined state.
 */
static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	//entry->next = (struct list_head *)LIST_POISON1;
	//entry->prev = (struct list_head *)LIST_POISON2;
}
1
2
3
4
5
6
7
8
9
10
11
12

五、获取结构体指针、遍历链表

这小节介绍怎list.h的链表怎样通过struct list_head *获取到其所在结构体的指针。仔细看前面的代码可以观察到，无论是初始化、添加、删除结点都只操作了结点的prev和next指针。那怎么存储和获取数据呢？这小节就给出答案。

list.h 要求定义数据结构体时，必须包含struct list_head定义的成员，添加或删除结点时，把结构体的struct list_head成员的指针添加到链表或从链表删除；这样就可以把各个结点联系起来并存储了。但是从链表获取结点，也只是获取到struct list_head的指针，list.h 提供一个list_entry函数可以通过struct list_head、结构体类型、成员名称 来获取到结构体的指针，通过结构体指针就可以获取数据了。

✨5.1 list_entry

list_entry可以通过struct list_head、结构体类型、成员名称 来获取到结构体的指针。

函数参数：
ptr：struct list_head*指针，指向链表某个结点
type：包含了struct list_head成员的结构体类型
member：struct list_head成员的名称

#ifndef offsetof
#define offsetof(type, f) ((size_t) \
		((char *)&((type *)0)->f - (char *)(type *)0))
#endif

#ifndef container_of
#define container_of(ptr, type, member) ({ \
		const typeof( ((type *)0)->member ) *__mptr = (ptr);\
		(type *)( (char *)__mptr - offsetof(type,member) );})
#endif

/**
 * 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) \
	container_of(ptr, type, member)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

分析：
1、先看 offsetof 这个宏是干什么的？
它的输入参数是一个结构体类型type 和 成员名称f，最后会获取到成员f在整个结构体类型type的偏移量，单位是字节。

2、再看看 container_of 宏的作用
它的输入参数是：struct list_head*的指针ptr、所在的结构体类型type、struct list_head成员名称member，先用typeof获取member的类型并定义该类型的指针 __mptr，然后将 ptr 赋值给 __mptr，最后用 __mptr 减去 （member 成员在该结构体的偏移量），得到了结构体的开始地址，并用(type *)做类型转换。

3、最后看 list_entry
它直接调用 container_of 宏，通过地址ptr、类型type、成员名称member，获取到type*结构体指针。

也就是说，我们调用时需要传入struct list_head*指针、包含了struct list_head成员的结构体类型、struct list_head成员名称，就可以获取到 struct list_head*指针 所在的结构体的地址。

此外，有些较新版本的内核代码，支持获取首结点、尾结点，其代码实现如下，ptr只需要传入头结点指针即可：

#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)
	
#define list_last_entry(ptr, type, member) \
	list_entry((ptr)->prev, type, member)
1
2
3
4
5

---

✨5.2 list_for_each

知道了怎样通过struct list_head*指针来获取结构体数据后，就可以来遍历链表了。这里先介绍list_for_each，但平时更多地使用list_for_each_safe。

list_for_each函数参数：
pos：用于遍历的指针，会依次指向链表的各个结点
head：链表头结点

#ifndef ARCH_HAS_PREFETCH
static inline void prefetch(const void *x) {;}
#endif

/**
 * 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; prefetch(pos->next), pos != (head); \
			pos = pos->next)
1
2
3
4
5
6
7
8
9
10
11
12

分析：这个宏展开后，是一个for循环，pos会依次指向链表的各个结点。实际使用时，通过pos去获取数据。

---

✨5.3 list_for_each_safe

list_for_each_safe是更常使用的，它可以避免在使用过程误删了结点。

函数参数：
pos：用于遍历的指针，会依次指向链表的各个结点；
n：用作临时存储的变量，在该for循环外无作用；
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.
 */
#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; pos != (head); \
			pos = n, n = pos->next)
1
2
3
4
5
6
7
8
9

分析：这个函数比list_for_each安全，每次循环前，会先把下个指针保存起来，避免pos被误删后找不到下个指针。

---

✨5.4 list_for_each_entry

list_for_each_entry 可以遍历给定类型的列表；

函数参数：
pos：要用作循环计数器的结构体类型指针
head：链表头结点指针
member：结构中 struct list_head 的成员名称

/**
 * list_for_each_entry	-	iterate over list of given type
 * @pos:	the type * to use as a loop counter.
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
 */
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_entry((head)->next, typeof(*pos), member);	\
			prefetch(pos->member.next), &pos->member != (head); 	\
			pos = list_entry(pos->member.next, typeof(*pos), member))
1
2
3
4
5
6
7
8
9
10

---

总结

本文介绍了 list.h 的函数实现，对想知道如何使用 list.h 有一定帮助。只要将上面的实现代码都复制起来，放到一个my_list.h的头文件，就可以得到一个简约版本的list.h，并且可以使用到上面所有函数。

// my_list.h

#ifndef _LINUX_LIST_H
#define _LINUX_LIST_H

struct list_head {
	struct list_head *next, *prev;
};


#define INIT_LIST_HEAD(ptr) do { \
	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}

/*
 * 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_node,
		struct list_head *prev,
		struct list_head *next)
{
	next->prev = new_node;
	new_node->next = next;
	new_node->prev = prev;
	prev->next = new_node;
}

/**
 * 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_node, struct list_head *head)
{
	__list_add(new_node, 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_node, struct list_head *head)
{
	__list_add(new_node, head->prev, head);
}

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty on entry does not return true after this, the entry is
 * in an undefined state.
 */
static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	//entry->next = (struct list_head *)LIST_POISON1;
	//entry->prev = (struct list_head *)LIST_POISON2;
}

#ifndef offsetof
#define offsetof(type, f) ((size_t) \
		((char *)&((type *)0)->f - (char *)(type *)0))
#endif

#ifndef container_of
#define container_of(ptr, type, member) ({ \
		const typeof( ((type *)0)->member ) *__mptr = (ptr);\
		(type *)( (char *)__mptr - offsetof(type,member) );})
#endif

/**
 * 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) \
	container_of(ptr, type, member)

#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)
	
#define list_last_entry(ptr, type, member) \
	list_entry((ptr)->prev, type, member)

#ifndef ARCH_HAS_PREFETCH
static inline void prefetch(const void *x) {;}
#endif

/**
 * 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; prefetch(pos->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)
			
/**
 * list_for_each_entry	-	iterate over list of given type
 * @pos:	the type * to use as a loop counter.
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
 */
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_entry((head)->next, typeof(*pos), member);	\
			prefetch(pos->member.next), &pos->member != (head); 	\
			pos = list_entry(pos->member.next, typeof(*pos), member))


#endif //_LINUX_LIST_H
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

如果文章有帮助的话，点赞