linux內核數(shù)據(jù)結構之鏈表
1、前言
最近寫代碼需用到鏈表結構，正好公共庫有關于鏈表的。第一眼看時，覺得有點新鮮，和我之前見到的鏈表結構不一樣，只有前驅和后繼指針，而沒有數(shù)據(jù)域。后來看代碼注釋發(fā)現(xiàn)該代碼來自linux內核，在linux源代碼下include/Lish.h下。這個鏈表具備通用性，使用非常方便。只需要在結構定義一個鏈表結構就可以使用。
2、鏈表介紹
鏈表是非常基本的數(shù)據(jù)結構，根據(jù)鏈個數(shù)分為單鏈表、雙鏈表，根據(jù)是否循環(huán)分為單向鏈表和循環(huán)鏈表。通常定義定義鏈表結構如下：
typedef
struct
node { ElemType data;
//數(shù)據(jù)域
struct
node *
next;
//指針域
}node,
*list;
鏈表中包含數(shù)據(jù)域和指針域。鏈表通常包含一個頭結點，不存放數(shù)據(jù)，方便鏈表操作。單向循環(huán)鏈表結構如下圖所示：
雙向循環(huán)鏈表結構如下圖所示：
這樣帶數(shù)據(jù)域的鏈表降低了鏈表的通用性，不容易擴展。linux內核定義的鏈表結構不帶數(shù)據(jù)域，只需要兩個指針完成鏈表的操作。具備非常高的擴展性，通用性。鏈表結構定義如下所示：
struct
list_head {
struct
list_head *next, *
prev; };
鏈表結構如下所示：
需要用鏈表結構時，只需要在結構體中定義一個鏈表類型的數(shù)據(jù)即可。例如定義一個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;
//
鏈表節(jié)點
7
}app_info;
定義一個app_info鏈表，app_info app_info_list;通過app_info_head進行鏈表操作。根據(jù)C語言指針操作，通過container_of和offsetof，可以根據(jù)app_info_head的地址找出app_info的起始地址，即一個完整ap_info結構的起始地址。可以參考： http://www.cnblogs.com/Anker/p/3472271.html 。
3、linux內核鏈表實現(xiàn)
內核實現(xiàn)的是雙向循環(huán)鏈表，提供了鏈表操作的基本功能。
（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宏創(chuàng)建一個鏈表頭結點，并用LIST_HEAD_INIT宏對頭結點進行賦值，使得頭結點的前驅和后繼指向自己。
INIT_LIST_HEAD函數(shù)對鏈表進行初始化，使得前驅和后繼指針指針指向頭結點。
（2）插入節(jié)點
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
}
插入節(jié)點分為從鏈表頭部插入list_add和鏈表尾部插入list_add_tail，通過調用__list_add函數(shù)進行實現(xiàn)，head->next指向之一個節(jié)點，head->prev指向尾部節(jié)點。
（3）刪除節(jié)點
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
}
從鏈表中刪除一個節(jié)點，需要改變該節(jié)點前驅節(jié)點的后繼結點和后繼結點的前驅節(jié)點。最后設置該節(jié)點的前驅節(jié)點和后繼結點指向 LIST_POSITION1和LIST_POSITION2兩個特殊值，這樣設置是為了保證不在鏈表中的節(jié)點項不可訪問，對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）移動節(jié)點
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將一個節(jié)點移動到頭部或者尾部。
（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函數(shù)判斷節(jié)點是否為末尾節(jié)點，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獲取鏈表的結構，包括數(shù)據(jù)域。list_first_entry獲取鏈表第一個節(jié)點，包括數(shù)據(jù)源。list_for_each宏對鏈表節(jié)點進行遍歷。
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
//
根據(jù)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
* 定義鏈表結構，創(chuàng)建鏈表、插入節(jié)點、刪除節(jié)點、移動節(jié)點、遍歷節(jié)點
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;
//
鏈表節(jié)點
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
//
創(chuàng)建一個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
//
將第一個節(jié)點移到末尾
86
printf(
"
Move first node to tail:\n
"
);
87
list_move_tail(head->
next, head);
88
for_each_app(head);
89
//
刪除最后一個節(jié)點
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/
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
