释放双眼，带上耳机，听听看~！
linux内核数据结构之双向循环链表
1、前言
链表是一种常见的数据结构。它可以动态的进行存储分配的一种结构。用数组存放数据时，必须事先定义固定的数组长度（即元素个数）。如果有的班级有100人，而有的班级只有30人，若用同一个数组先后存放不同班级的学生数据，则必须定义长度为100的数组。如果事先难以确定一个班的最多人数，则必须把数组定得足够大，以便能存放任何班级的学生数据，显然这将会浪费内存。链表则没有这种缺点，它根据需要开辟内存单元。
链表有一个“头指针”变量，图中以head表示，它存放了一个地址，该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包含两个部分：用户需要用的数据、下一个结点的地址。这样，head结点指向第一元素，第一个元素指向第二个元素…直到最后一个元素
链表由指针域和数据域构成，指针域用来指向前后的元素，数据域用来存放元素数据
2、链表介绍
链表是非常基本的数据结构，根据链个数分为单链表、双链表，根据是否循环分为单向链表和循环链表。通常定义定义链表结构如下：
2
3
4
5
6
7
2{
3 ElemType data; //数据域
4 struct node *next; //指针域
5}node, *list;
6
7
链表中包含数据域和指针域。链表通常包含一个头结点，不存放数据，方便链表操作。单向循环链表结构如下图所示：
双向循环链表结构如下图所示：
这样带数据域的链表降低了链表的通用性，不容易扩展。linux内核定义的链表结构不带数据域，只需要两个指针完成链表的操作。将链表节点加入数据结构，具备非常高的扩展性，通用性。链表结构定义如下所示：
2
3
4
5
2 struct list_head *next, *prev;
3};
4
5
链表结构如下所示：
需要用链表结构时，只需要在结构体中定义一个链表类型的数据即可。例如定义一个app_info链表，
2
3
4
5
6
7
8
9
2{
3 uint32_t app_id;
4 uint32_t up_flow;
5 uint32_t down_flow;
6 struct list_head app_info_head; //链表节点
7}app_info;
8
9
定义一个app_info链表，app_info app_info_list;通过app_info_head进行链表操作。根据C语言指针操作，通过container_of和offsetof，可以根据app_info_head的地址找出app_info的起始地址，即一个完整ap_info结构的起始地址。可以参考：http://www.cnblogs.com/Anker/p/3472271.html。
3、linux内核链表实现
内核实现的是双向循环链表，提供了链表操作的基本功能。
（1）初始化链表头结点
2
3
4
5
6
7
8
9
10
11
12
2
3#define LIST_HEAD(name) \
4 struct list_head name = LIST_HEAD_INIT(name)
5
6static inline void INIT_LIST_HEAD(struct list_head *list)
7{
8 list->next = list;
9 list->prev = list;
10}
11
12
两种初始化链表头节点方式。LIST_HEAD_INIT和INIT_LIST_HEAD都是对链表进行初始化，都是使得前驱和后继指针指针指向头结点。
LIST_HEAD宏创建一个链表头结点，用LIST_HEAD_INIT宏对头结点进行赋值，使得头结点的前驱和后继指向自己。
INIT_LIST_HEAD函数对链表进行初始化，使得前驱和后继指针指针指向头结点。
（2）插入节点
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2 struct list_head *prev,
3 struct list_head *next)
4{
5 next->prev = new;
6 new->next = next;
7 new->prev = prev;
8 prev->next = new;
9}
10
11static inline void list_add(struct list_head *new, struct list_head *head)
12{
13 __list_add(new, head, head->next);
14}
15
16static inline void list_add_tail(struct list_head *new, struct list_head *head)
17{
18 __list_add(new, head->prev, head);
19}
20
21
插入节点分为从链表头部插入list_add和链表尾部插入list_add_tail，通过调用__list_add函数进行实现，head->next指向之一个节点，head->prev指向尾部节点。
（3）删除节点
2
3
4
5
6
7
8
9
10
11
12
13
14
2{
3 next->prev = prev;
4 prev->next = next;
5}
6
7static inline void list_del(struct list_head *entry)
8{
9 __list_del(entry->prev, entry->next);
10 entry->next = LIST_POISON1;
11 entry->prev = LIST_POISON2;
12}
13
14
从链表中删除一个节点，需要改变该节点前驱节点的后继结点和后继结点的前驱节点。最后设置该节点的前驱节点和后继结点指向
LIST_POSITION1和LIST_POSITION2两个特殊值，这样设置是为了保证不在链表中的节点项不可访问，对LIST_POSITION1和LIST_POSITION2的访问都将引起页故障
2
3
4
5
6
7
8
9
2 * These are non-NULL pointers that will result in page faults
3 * under normal circumstances, used to verify that nobody uses
4 * non-initialized list entries.
5 */
6#define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
7#define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
8
9
（4）移动节点
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2 * list_move - delete from one list and add as another's head
3 * @list: the entry to move
4 * @head: the head that will precede our entry
5 */
6static inline void list_move(struct list_head *list, struct list_head *head)
7{
8 __list_del(list->prev, list->next);
9 list_add(list, head);
10}
11
12/**
13 * list_move_tail - delete from one list and add as another's tail
14 * @list: the entry to move
15 * @head: the head that will follow our entry
16 */
17static inline void list_move_tail(struct list_head *list,
18 struct list_head *head)
19{
20 __list_del(list->prev, list->next);
21 list_add_tail(list, head);
22}
23
24
move将一个节点移动到头部或者尾部。
（5）判断链表
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2 * list_is_last - tests whether @list is the last entry in list @head
3 * @list: the entry to test
4 * @head: the head of the list
5 */
6static inline int list_is_last(const struct list_head *list,
7 const struct list_head *head)
8{
9 return list->next == head;
10}
11
12/**
13 * list_empty - tests whether a list is empty
14 * @head: the list to test.
15 */
16static inline int list_empty(const struct list_head *head)
17{
18 return head->next == head;
19}
20
21
list_is_last函数判断节点是否为末尾节点，list_empty判断链表是否为空。
（6）遍历链表
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
2 * list_entry - get the struct for this entry
3 * @ptr: the &struct list_head pointer.
4 * @type: the type of the struct this is embedded in.
5 * @member: the name of the list_struct within the struct.
6 */
7#define list_entry(ptr, type, member) \
8 container_of(ptr, type, member)
9
10/**
11 * list_first_entry - get the first element from a list
12 * @ptr: the list head to take the element from.
13 * @type: the type of the struct this is embedded in.
14 * @member: the name of the list_struct within the struct.
15 *
16 * Note, that list is expected to be not empty.
17 */
18#define list_first_entry(ptr, type, member) \
19 list_entry((ptr)->next, type, member)
20
21/**
22 * list_for_each - iterate over a list
23 * @pos: the &struct list_head to use as a loop cursor.
24 * @head: the head for your list.
25 */
26#define list_for_each(pos, head) \
27 for (pos = (head)->next; prefetch(pos->next), pos != (head); \
28 pos = pos->next)
29
30
list_entry获取链表的结构，包括数据域，由ptr这个节点地址得到它所在的type类型结构体的地。
list_first_entry获取链表第一个节点所在容器。
list_for_each宏对链表节点进行遍历，遍历head为链表头的整个链表，pos是个中间变量。
list_entry函数解析
list_entry函数其实是从一个结构的成员指针找到其容器的指针。即寻找容器
2
3
4
5
6
7
8
9
10
11
12
2 container_of(ptr, type, member)
3
4#define container_of(ptr, type, member) \
5({ \
6 const typeof( ((type *)0)->member ) *__mptr = (ptr);\
7 (type *)( (char *)__mptr - offsetof(type,member) ); \
8})
9
10#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
11
12
ptr是找容器的那个变量的指针，即链表的指针，把它减去自己在容器中的偏移量的值就应该 得到容器的指针。（容器就是包含自己的那个结构）。指针的加减要注意类型，用(char*)ptr是为了计算字节偏移。((type *)0)->member是一个小技巧。自己理解吧。前面的（type *）再转回容器的类型。
list_entry最终的定义如下
2
3
4
2 ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
3
4
ptr是指向list_head类型链表的指针，type为一个结构，而member为结构type中的一个域，类型为list_head，这个宏返回指向type结构的指针。**所以list_head是由ptr这个节点地址得到它所在的type类型结构体的地址。**在内核代码中大量引用了这个宏，因此，搞清楚这个宏的含义和用法非常重要。
list_for_each_entry
2
3
4
5
6
7
8
9
10
11
12
13
2 * list_for_each_entry - iterate over list of given type
3 * @pos: the type * to use as a loop cursor.
4 * @head: the head for your list.
5 * @member: the name of the list_struct within the struct.
6 */
7#define list_for_each_entry(pos, head, member) \
8 for (pos = list_entry((head)->next, typeof(*pos), member); \
9 prefetch(pos->member.next), &pos->member != (head); \
10 pos = list_entry(pos->member.next, typeof(*pos), member))
11
12
13
list_for_each_entry 是遍历head为链表头的链表容器
总结
list_entry获取链表的结构，包括数据域，由ptr这个节点地址得到它所在的type类型结构体的地。
list_first_entry获取链表第一个节点所在容器。
list_for_each宏对链表节点进行遍历，遍历head为链表头的整个链表，pos是个中间变量。
list_for_each_entry 是遍历head为链表头的链表容器
4、测试例子
编写一个简单使用链表的程序，从而掌握链表的使用。
自定义个类似的list结构如下所示：mylist.h
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
2
3#define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
4#define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
5
6//计算member在type中的位置
7#define offsetof(type, member) (size_t)(&((type*)0)->member)
8//根据member的地址获取type的起始地址
9#define container_of(ptr, type, member) ({ \
10 const typeof(((type *)0)->member)*__mptr = (ptr); \
11 (type *)((char *)__mptr - offsetof(type, member)); })
12
13//链表结构
14struct list_head
15{
16 struct list_head *prev;
17 struct list_head *next;
18};
19
20static inline void init_list_head(struct list_head *list)
21{
22 list->prev = list;
23 list->next = list;
24}
25
26static inline void __list_add(struct list_head *new,
27 struct list_head *prev, struct list_head *next)
28{
29 prev->next = new;
30 new->prev = prev;
31 new->next = next;
32 next->prev = new;
33}
34
35//从头部添加
36static inline void list_add(struct list_head *new , struct list_head *head)
37{
38 __list_add(new, head, head->next);
39}
40//从尾部添加
41static inline void list_add_tail(struct list_head *new, struct list_head *head)
42{
43 __list_add(new, head->prev, head);
44}
45
46static inline void __list_del(struct list_head *prev, struct list_head *next)
47{
48 prev->next = next;
49 next->prev = prev;
50}
51
52static inline void list_del(struct list_head *entry)
53{
54 __list_del(entry->prev, entry->next);
55 entry->next = LIST_POISON1;
56 entry->prev = LIST_POISON2;
57}
58
59static inline void list_move(struct list_head *list, struct list_head *head)
60{
61 __list_del(list->prev, list->next);
62 list_add(list, head);
63}
64
65static inline void list_move_tail(struct list_head *list,
66 struct list_head *head)
67{
68 __list_del(list->prev, list->next);
69 list_add_tail(list, head);
70}
71#define list_entry(ptr, type, member) \
72 container_of(ptr, type, member)
73
74#define list_first_entry(ptr, type, member) \
75 list_entry((ptr)->next, type, member)
76
77#define list_for_each(pos, head) \
78 for (pos = (head)->next; pos != (head); pos = pos->next)
79
80
mylist.c如下所示：
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
2 * 定义链表结构，创建链表、插入节点、删除节点、移动节点、遍历节点
3 *
4 *@auther Anker @date 2013-12-15
5 **/
6#include <stdio.h>
7#include <inttypes.h>
8#include <stdlib.h>
9#include <errno.h>
10#include "mylist.h"
11//定义app_info链表结构
12typedef struct application_info
13{
14 uint32_t app_id;
15 uint32_t up_flow;
16 uint32_t down_flow;
17 struct list_head app_info_node;//链表节点
18}app_info;
19
20
21app_info* get_app_info(uint32_t app_id, uint32_t up_flow, uint32_t down_flow)
22{
23 app_info *app = (app_info*)malloc(sizeof(app_info));
24 if (app == NULL)
25 {
26 fprintf(stderr, "Failed to malloc memory, errno:%u, reason:%s\n",
27 errno, strerror(errno));
28 return NULL;
29 }
30 app->app_id = app_id;
31 app->up_flow = up_flow;
32 app->down_flow = down_flow;
33 return app;
34}
35static void for_each_app(const struct list_head *head)
36{
37 struct list_head *pos;
38 app_info *app;
39 //遍历链表
40 list_for_each(pos, head)
41 {
42 app = list_entry(pos, app_info, app_info_node);
43 printf("ap_id: %u\tup_flow: %u\tdown_flow: %u\n",
44 app->app_id, app->up_flow, app->down_flow);
45
46 }
47}
48
49void destroy_app_list(struct list_head *head)
50{
51 struct list_head *pos = head->next;
52 struct list_head *tmp = NULL;
53 while (pos != head)
54 {
55 tmp = pos->next;
56 list_del(pos);
57 pos = tmp;
58 }
59}
60
61
62int main()
63{
64 //创建一个app_info
65 app_info * app_info_list = (app_info*)malloc(sizeof(app_info));
66 app_info *app;
67 if (app_info_list == NULL)
68 {
69 fprintf(stderr, "Failed to malloc memory, errno:%u, reason:%s\n",
70 errno, strerror(errno));
71 return -1;
72 }
73 //初始化链表头部
74 struct list_head *head = &app_info_list->app_info_node;
75 init_list_head(head);
76 //插入三个app_info
77 app = get_app_info(1001, 100, 200);
78 list_add_tail(&app->app_info_node, head);
79 app = get_app_info(1002, 80, 100);
80 list_add_tail(&app->app_info_node, head);
81 app = get_app_info(1003, 90, 120);
82 list_add_tail(&app->app_info_node, head);
83 printf("After insert three app_info: \n");
84 for_each_app(head);
85 //将第一个节点移到末尾
86 printf("Move first node to tail:\n");
87 list_move_tail(head->next, head);
88 for_each_app(head);
89 //删除最后一个节点
90 printf("Delete the last node:\n");
91 list_del(head->prev);
92 for_each_app(head);
93 destroy_app_list(head);
94 free(app_info_list);
95 return 0;
96}
97
98
测试结果如下所示：
