描述
在linux內核中封裝了一個通用的雙向鏈表庫，這個通用的鏈表庫有很好的擴展性和封裝性，它給我們提供了一個固定的指針域結構體，我們在使用的時候，只需要在我們定義的數(shù)據(jù)域結構體中包含這個指針域結構體就可以了，具體的實現(xiàn)、鏈接并不需要我們關心，只要調用提供給我們的相關接口就可以完成了。
傳統(tǒng)的鏈表結構
|
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 結構就把我們的數(shù)據(jù)層跟驅動層分開了，而內核提供的各種操作方法接口也只關心 list_head 這個結構，也就是具體鏈接的時候也只鏈接這個list_head 結構，并不關心你數(shù)據(jù)層定義了什么類型.
一些接口宏定義
|
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)//獲取節(jié)點首地址(不是list_head地址，是數(shù)據(jù)層節(jié)點首地址)#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);//創(chuàng)建節(jié)點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地址反推 //節(jié)點結構體首地址. n = list_entry(pos,struct node,list);} |
list_add 接口，先入后出原則，有點類似于棧
list_add-先入后出模式
list_add_tail 接口，先入先出原則，有點類似于fifo
list_add-先入先出模式
我們的鏈表節(jié)點，實際在內存中的展示形態(tài)
節(jié)點描述
可以看到最終的形態(tài)是，通過指向每個結構體里面的 list_head 類型指針，然后把它們串聯(lián)起來的
list_entry 接口，通過結構體變量某個成員的地址，反推結構體首地址，就像 __list_for_each 接口只返回 list_head 地址，所以我們要通過這個成員地址在去獲取它本身的結構體首地址，底層實現(xiàn)方法 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 //代表一個實際節(jié)點的結構 { char name[100]; int num; struct list_head list; //內核鏈表里的節(jié)點結構 }; 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); //清空，這兩個函數(shù)可以由kzalloc單獨做到 for(i=0;i<5;i++) { //為結構體屬性賦值 sprintf(pstudent[i].name,"student%d",i+1); pstudent[i].num = i+1; //加入鏈表節(jié)點，list_add的話是在表頭插入，list_add_tail是在表尾插入 list_add( &(pstudent[i].list), &student_list);//參數(shù)1是要插入的節(jié)點地址，參數(shù)2是鏈表頭地址 } list_for_each(pos,&student_list) //list_for_each用來遍歷鏈表，這是個宏定義 //pos在上面有定義 { //list_entry用來提取出內核鏈表節(jié)點對應的實際結構節(jié)點，即根據(jù)struct list_head來提取struct student //第三個參數(shù)list就是student結構定義里的屬性list //list_entry的原理有點復雜，也是linux內核的一個經典實現(xiàn)，這個在上面那篇鏈接文章里也有講解 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來遍歷刪除結點，觀察要發(fā)生的現(xiàn)象，并考慮解決辦法 */ for(i=0;i<5;i++) { //額，刪除節(jié)點，只要傳個內核鏈表節(jié)點就行了 list_del(&(pstudent[i].list)); } //釋放空間 kfree(pstudent); } module_init(mylist_init); module_exit(mylist_exit); |
結束
linux 內核提供的這個通用鏈表庫里面還有很多其他的接口，這里沒有詳細的一一舉例，有興趣的可以自己去看看，在源碼包 include/linux/list.h 文件里面，不過通過閱讀一些源代碼確實對我們也有很大的提高，可以看看高手是如何去設計并實現(xiàn)，還可以學到一些技巧以及對代碼細節(jié)的掌握~~.
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://www.jianshu.com/p/1abba63d3f1c
