linux内核数据结构之链表
1、前言
最近写代码需用到链表结构，正好公共库有关于链表的。第一眼看时，觉得有点新鲜，和我之前见到的链表结构不一样，只有前驱和后继指针，而没有数据域。后来看代码注释发现该代码来自linux内核，在linux源代码下include/Lish.h下。这个链表具备通用性，使用非常方便。只需要在结构定义一个链表结构就可以使用。
2、链表介绍
链表是非常基本的数据结构，根据链个数分为单链表、双链表，根据是否循环分为单向链表和循环链表。通常定义定义链表结构如下：
typedef
struct
node { ElemType data;
//数据域
struct
node *
next;
//指针域
}node,
*list;
链表中包含数据域和指针域。链表通常包含一个头结点，不存放数据，方便链表操作。单向循环链表结构如下图所示：
双向循环链表结构如下图所示：
这样带数据域的链表降低了链表的通用性，不容易扩展。linux内核定义的链表结构不带数据域，只需要两个指针完成链表的操作。具备非常高的扩展性，通用性。链表结构定义如下所示：
struct
list_head {
struct
list_head *next, *
prev; };
链表结构如下所示：
需要用链表结构时，只需要在结构体中定义一个链表类型的数据即可。例如定义一个app_info链表，
1
typedef
struct
application_info
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;
定义一个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）初始化链表头结点
#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) { list
->next =
list; list
->prev =
list; }
LIST_HEAD宏创建一个链表头结点，并用LIST_HEAD_INIT宏对头结点进行赋值，使得头结点的前驱和后继指向自己。
INIT_LIST_HEAD函数对链表进行初始化，使得前驱和后继指针指针指向头结点。
（2）插入节点
1
static
inline
void
__list_add(
struct
list_head *
new
,
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
11
static
inline
void
list_add(
struct
list_head *
new
,
struct
list_head *
head)
12
{
13
__list_add(
new
, head, head->
next);
14
}
15
16
static
inline
void
list_add_tail(
struct
list_head *
new
,
struct
list_head *
head)
17
{
18
__list_add(
new
, head->
prev, head);
19
}
插入节点分为从链表头部插入list_add和链表尾部插入list_add_tail，通过调用__list_add函数进行实现，head->next指向之一个节点，head->prev指向尾部节点。
（3）删除节点
1
static
inline
void
__list_del(
struct
list_head * prev,
struct
list_head *
next)
2
{
3
next->prev =
prev;
4
prev->next =
next;
5
}
6
7
static
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
}
从链表中删除一个节点，需要改变该节点前驱节点的后继结点和后继结点的前驱节点。最后设置该节点的前驱节点和后继结点指向 LIST_POSITION1和LIST_POSITION2两个特殊值，这样设置是为了保证不在链表中的节点项不可访问，对LIST_POSITION1和LIST_POSITION2的访问都将引起页故障
/*
* These are non-NULL pointers that will result in page faults * under normal circumstances, used to verify that nobody uses * non-initialized list entries.
*/
#define
LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define
LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
（4）移动节点
1
/*
*
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
*/
6
static
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
*/
17
static
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
}
move将一个节点移动到头部或者尾部。
（5）判断链表
1
/*
*
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
*/
6
static
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
*/
16
static
inline
int
list_empty(
const
struct
list_head *
head)
17
{
18
return
head->next ==
head;
19
}
list_is_last函数判断节点是否为末尾节点，list_empty判断链表是否为空。
（6）遍历链表
1
/*
*
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)
宏list_entity获取链表的结构，包括数据域。list_first_entry获取链表第一个节点，包括数据源。list_for_each宏对链表节点进行遍历。
4、测试例子
编写一个简单使用链表的程序，从而掌握链表的使用。
自定义个类似的list结构如下所示：mylist.h
1
# define POISON_POINTER_DELTA
0
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
//
链表结构
14
struct
list_head
15
{
16
struct
list_head *
prev;
17
struct
list_head *
next;
18
};
19
20
static
inline
void
init_list_head(
struct
list_head *
list)
21
{
22
list->prev =
list;
23
list->next =
list;
24
}
25
26
static
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
//
从头部添加
36
static
inline
void
list_add(
struct
list_head *
new
,
struct
list_head *
head)
37
{
38
__list_add(
new
, head, head->
next);
39
}
40
//
从尾部添加
41
static
inline
void
list_add_tail(
struct
list_head *
new
,
struct
list_head *
head)
42
{
43
__list_add(
new
, head->
prev, head);
44
}
45
46
static
inline
void
__list_del(
struct
list_head *prev,
struct
list_head *
next)
47
{
48
prev->next =
next;
49
next->prev =
prev;
50
}
51
52
static
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
59
static
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
65
static
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)
mylist.c如下所示：
1
/*
*@brief 练习使用linux内核链表，功能包括：
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链表结构
12
typedef
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
21
app_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
}
35
static
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
49
void
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
62
int
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
}
测试结果如下所示：
参考网址：
https://www.ibm.com/developerworks/cn/linux/kernel/l-chain/
冷静思考，勇敢面对，把握未来！
分类:
Linux内核学习
