描述
在linux內核中封裝了一個通用的雙向鏈表庫，這個通用的鏈表庫有很好的擴展性和封裝性，它給我們提供了一個固定的指針域結構體，我們在使用的時候，只需要在我們定義的數據域結構體中包含這個指針域結構體就可以了，具體的實現、鏈接并不需要我們關心，只要調用提供給我們的相關接口就可以完成了。
傳統的鏈表結構
|
1
2
3
4
5
6
|
struct node{ int key; int val; node* prev; node* next; } |
linux 內核通用鏈表庫結構
提供給我們的指針域結構體：
|
1
2
3
|
struct list_head { struct list_head *next, *prev;}; |
我們只需要包含它就可以：
|
1
2
3
4
5
|
struct node{ int val; int key; struct list_head* head;} |
可以看到通過這個 list_head 結構就把我們的數據層跟驅動層分開了，而內核提供的各種操作方法接口也只關心 list_head 這個結構，也就是具體鏈接的時候也只鏈接這個list_head 結構，并不關心你數據層定義了什么類型.
一些接口宏定義
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
//初始化頭指針#define list_head_init(name) { &(name), &(name) }#define list_head(name) \ struct list_head name = list_head_init(name)//遍歷鏈表#define __list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next)//獲取節點首地址(不是list_head地址，是數據層節點首地址)#define list_entry(ptr, type, member) \ container_of(ptr, type, member)//container_of在linux內核中是一個常用的宏，用于從包含在某個//結構中的指針獲得結構本身的指針，通俗地講就是通過結構體變//量中某個成員的首地址進而獲得整個結構體變量的首地址#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );})#define offsetof(s,m) (size_t)&(((s *)0)->m) |
使用方式
|
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
|
typedef struct node{ int val; int key; struct list_head* list;}node;//初始化頭指針list_head(head);//創建節點node* a = malloc(sizeof(node));node* b = malloc(sizeof(node));//插入鏈表 方式一list_add(&a->list,&head);list_add(&b->list,&head);//插入鏈表 方式二list_add_tail(&a->list,&head);list_add_tail(&b->list,&head);//遍歷鏈表 struct list_head* p;struct node* n;__list_for_each(p,head){ //返回list_head地址，然后再通過list_head地址反推 //節點結構體首地址. n = list_entry(pos,struct node,list);} |
list_add 接口，先入后出原則，有點類似于棧
list_add-先入后出模式
list_add_tail 接口，先入先出原則，有點類似于fifo
list_add-先入先出模式
我們的鏈表節點，實際在內存中的展示形態
節點描述
可以看到最終的形態是，通過指向每個結構體里面的 list_head 類型指針，然后把它們串聯起來的
list_entry 接口，通過結構體變量某個成員的地址，反推結構體首地址，就像 __list_for_each 接口只返回 list_head 地址，所以我們要通過這個成員地址在去獲取它本身的結構體首地址，底層實現方法 container_of 宏
反推結構體首地址
舉個例子
這個例子包括簡單的增、刪、遍歷
|
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
|
#include <linux/kernel.h> #include <linux/module.h> #include <linux/init.h> #include <linux/slab.h> #include <linux/list.h> module_license("gpl"); module_author("david xie"); module_description("list module"); module_alias("list module"); struct student //代表一個實際節點的結構 { char name[100]; int num; struct list_head list; //內核鏈表里的節點結構 }; struct student *pstudent; struct student *tmp_student; struct list_head student_list; struct list_head *pos; int mylist_init(void) { int i = 0; //初始化一個鏈表，其實就是把student_list的prev和next指向自身 init_list_head(&student_list); pstudent = kmalloc(sizeof(struct student)*5,gfp_kernel);//向內核申請5個student結構空間 memset(pstudent,0,sizeof(struct student)*5); //清空，這兩個函數可以由kzalloc單獨做到 for(i=0;i<5;i++) { //為結構體屬性賦值 sprintf(pstudent[i].name,"student%d",i+1); pstudent[i].num = i+1; //加入鏈表節點，list_add的話是在表頭插入，list_add_tail是在表尾插入 list_add( &(pstudent[i].list), &student_list);//參數1是要插入的節點地址，參數2是鏈表頭地址 } list_for_each(pos,&student_list) //list_for_each用來遍歷鏈表，這是個宏定義 //pos在上面有定義 { //list_entry用來提取出內核鏈表節點對應的實際結構節點，即根據struct list_head來提取struct student //第三個參數list就是student結構定義里的屬性list //list_entry的原理有點復雜，也是linux內核的一個經典實現，這個在上面那篇鏈接文章里也有講解 tmp_student = list_entry(pos,struct student,list); //打印一些信息，以備驗證結果 printk("<0>student %d name: %s/n",tmp_student->num,tmp_student->name); } return 0; } void mylist_exit(void) { int i ; /* 實驗：將for換成list_for_each來遍歷刪除結點，觀察要發生的現象，并考慮解決辦法 */ for(i=0;i<5;i++) { //額，刪除節點，只要傳個內核鏈表節點就行了 list_del(&(pstudent[i].list)); } //釋放空間 kfree(pstudent); } module_init(mylist_init); module_exit(mylist_exit); |
結束
linux 內核提供的這個通用鏈表庫里面還有很多其他的接口，這里沒有詳細的一一舉例，有興趣的可以自己去看看，在源碼包 include/linux/list.h 文件里面，不過通過閱讀一些源代碼確實對我們也有很大的提高，可以看看高手是如何去設計并實現，還可以學到一些技巧以及對代碼細節的掌握~~.
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://www.jianshu.com/p/1abba63d3f1c
