C語(yǔ)言的那些小秘密之鏈表（三）

　　在開始寫linux內(nèi)核雙向循環(huán)鏈表之前，我一直在想我要不要用長(zhǎng)篇大論的文字來(lái)描述linux內(nèi)核雙向循環(huán)鏈表呢?經(jīng)過(guò)認(rèn)真的思考之后，我否決了用枯燥的文字向讀者描述linux內(nèi)核雙向循環(huán)鏈表的想法，因?yàn)閷?duì)于編程語(yǔ)言來(lái)說(shuō)我相信大多數(shù)的讀者都應(yīng)該不喜歡面對(duì)枯燥的文字，更喜歡看到代碼，同時(shí)那也是讀者閱讀文字后想要實(shí)現(xiàn)的東西，所以我決定在這里采用代碼加上適當(dāng)?shù)奈淖置枋龅姆椒▉?lái)進(jìn)行講解，這就使得我不可能用一篇的篇幅來(lái)講解完，所以會(huì)寫兩篇文章來(lái)講解這個(gè)知識(shí)點(diǎn)。希望讀者能夠堅(jiān)持看完，學(xué)會(huì)以后在應(yīng)用程序中寫雙向循環(huán)鏈表時(shí)，不用再自己去編寫那些麻煩的操作函數(shù)，充分利用linux內(nèi)核里已經(jīng)提供的遍歷鏈表的操作函數(shù)。

　　特此說(shuō)明：我會(huì)把我在文章中編寫代碼時(shí)候用到的頭文件list.h上傳到我的空間，免積分下載，有需要的讀者可以自己去下載，當(dāng)然也可以自己上網(wǎng)下載或者從自己安裝的linux系統(tǒng)中得到。

　　懂了linux內(nèi)核里雙向循環(huán)鏈表的實(shí)現(xiàn)方式之后我們不得不驚嘆它的實(shí)現(xiàn)是如此的巧妙，為了讀者能夠順利的和我一起走完這次linux內(nèi)核雙向循環(huán)鏈表之旅，在此之前我特地為之寫了一篇《C語(yǔ)言的那些小秘密之字節(jié)對(duì)齊》的文章，如果你發(fā)現(xiàn)在本篇文章中有些地方不懂的時(shí)候，你可以回過(guò)去看看《C語(yǔ)言的那些小秘密之字節(jié)對(duì)齊》再來(lái)接著繼續(xù)往下繼續(xù)全文的閱讀。

　　由于我們?cè)趌inux內(nèi)核中有大量的數(shù)據(jù)結(jié)構(gòu)都需要用到雙向循環(huán)鏈表。若再采用以往那種傳統(tǒng)雙向循環(huán)鏈表的實(shí)現(xiàn)方式，我們不得不為這些數(shù)據(jù)結(jié)構(gòu)維護(hù)各自的鏈表，并且為每個(gè)鏈表都要設(shè)計(jì)插入、查找、刪除等操作函數(shù)。這是因?yàn)槲覀冊(cè)诔Ｒ?guī)鏈表中用來(lái)維持鏈表的next和prev指針都是指向?qū)?yīng)類型的對(duì)象，因此一種數(shù)據(jù)結(jié)構(gòu)的鏈表操作函數(shù)不能用于操作其它數(shù)據(jù)結(jié)構(gòu)的鏈表。為了解決這個(gè)問(wèn)題，在Linux內(nèi)核中采用了一種與類型無(wú)關(guān)的雙向循環(huán)鏈表實(shí)現(xiàn)方式，它的實(shí)現(xiàn)使得我們不用再為每個(gè)鏈表都要設(shè)計(jì)插入、查找、刪除等相關(guān)的操作函數(shù)。其實(shí)現(xiàn)方法就是將結(jié)構(gòu)體中的指針prev和next從具體的數(shù)據(jù)結(jié)構(gòu)中提取出來(lái)，構(gòu)成一種通用的雙向循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)list_head。如果需要構(gòu)造某類對(duì)象的特定鏈表，則只需要在其結(jié)構(gòu)體中定義一個(gè)類型為list_head類型的成員，通過(guò)這個(gè)定義的list_head類型的成員將這類對(duì)象連接起來(lái)，形成所需的雙向循環(huán)鏈表，進(jìn)而通過(guò)通用鏈表函數(shù)對(duì)其進(jìn)行操作。顯而易見是我們只需編寫通用鏈表函數(shù)，就可構(gòu)造和操作不同對(duì)象的鏈表，而無(wú)需為每個(gè)創(chuàng)建的雙向循環(huán)鏈表編寫專用函數(shù)，從而大大的實(shí)現(xiàn)了代碼的重用。

　　下面我們就真正的開始我們的linux內(nèi)核雙向循環(huán)鏈表之旅。讀者可以從網(wǎng)上下載一個(gè)linux內(nèi)核雙向循環(huán)鏈表的list.h的頭文件，值得注意的就是因?yàn)閮?nèi)核版本的不同可能下載的頭文件有些差異，但是這個(gè)并不影響我們對(duì)于它的講解。讀者可以先看完全文后再動(dòng)手也不遲，用list.h頭文件來(lái)實(shí)現(xiàn)我們的雙向循環(huán)鏈表。為了便于講解，我們就按照l(shuí)ist.h頭文件中代碼的先后順序進(jìn)行講解。

　　補(bǔ)充一點(diǎn)：(注：如果讀者看不懂下面這段代碼，可以繼續(xù)往下看，不會(huì)影響接下來(lái)的學(xué)習(xí)，在接下來(lái)的部分還會(huì)有講解，這部分代碼是我寫完全文后添加的，因?yàn)橐婚_始我使用的是#define list_entry(ptr, type, member) ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))而不是#define list_entry(ptr, type, member) container_of(ptr, type, member))

　　[cpp] view plaincopy#define container_of(ptr, type, member) ( {

　　const typeof( ((type *)0)->member ) *__mptr = (ptr);

　　(type *)( (char *)__mptr - offsetof(type,member) ); } )

　　通過(guò)typeof( ((type *)0)->member )得到member成員的類型，將指向member的指針ptr賦值給__mptr，__mptr指針的類型為member數(shù)據(jù)成員的類型。通過(guò)(char *)__mptr將__mptr強(qiáng)制轉(zhuǎn)換為char指針，之后再減去offsetof(type,member)，即可得到宿主結(jié)構(gòu)體的指針。如果有對(duì)offsetof(type,member)不懂的可以參考我之前寫的一篇《C語(yǔ)言的那些小秘密之字節(jié)對(duì)齊》。

　　首先看看list_head結(jié)構(gòu)的實(shí)現(xiàn)。

　　[html] view plaincopystruct list_head {

　　struct list_head *next, *prev;

　　};

　　在linux內(nèi)核雙向循環(huán)鏈表中我們用以上list_head類型定義一個(gè)變量，將其作為一個(gè)成員嵌入到宿主結(jié)構(gòu)內(nèi)。什么是宿主結(jié)構(gòu)體呢?就是我們創(chuàng)建的雙向循環(huán)鏈表的結(jié)構(gòu)體?？梢詫㈡湵斫Y(jié)構(gòu)放在宿主結(jié)構(gòu)內(nèi)的任何地方，當(dāng)然也可以為鏈表結(jié)構(gòu)取任何名字，從而我們就可以用list_head中的成員和相對(duì)應(yīng)的處理函數(shù)來(lái)對(duì)鏈表進(jìn)行遍歷操作，如果想得到宿主結(jié)構(gòu)的指針，使用我們可以使用list_entry計(jì)算出來(lái)，先別急著想知道list_entry什么，我們會(huì)在下面講解，接著往下看。

　　在宿主結(jié)構(gòu)體中定義了list_head之后接下來(lái)當(dāng)然是要對(duì)我們定義的頭結(jié)點(diǎn)進(jìn)行初始化工作，初始化的實(shí)現(xiàn)方法可以有以下兩種方式。

　　[html] view plaincopy#define LIST_HEAD_INIT(name) { &(name), &(name) }

　　#define LIST_HEAD(name)

　　struct list_head name = LIST_HEAD_INIT(name)

　　#define INIT_LIST_HEAD(ptr) do {

　　(ptr)->next = (ptr); (ptr)->prev = (ptr);

　　} while (0)

　　分析上面的代碼可知，我們?cè)诖a中使用list_head定義了一個(gè)頭結(jié)點(diǎn)之后，就要對(duì)定義的頭結(jié)點(diǎn)進(jìn)行初始化工作，可以使用INIT_LIST_HEAD(ptr)宏進(jìn)行初始化，或者我們無(wú)需自己定義直接使用LIST_HEAD(name)宏即可完成定義和初始化的工作。頭結(jié)點(diǎn)的初始化工作完成了之后接下來(lái)的工作當(dāng)然是要添加節(jié)點(diǎn)了。

　　[html] view plaincopystatic inline void __list_add(struct list_head *new,

　　struct list_head *prev,

　　struct list_head *next)

　　{

　　next->prev = new;

　　new->next = next;

　　new->prev = prev;

　　prev->next = new;

　　}

　　__list_add()的功能是在兩個(gè)非空結(jié)點(diǎn)中插入一個(gè)結(jié)點(diǎn)，值得注意的是new、prev、next均不能為空值。當(dāng)然prev可以等于next，此時(shí)表示在只含頭節(jié)點(diǎn)的鏈表中插入新節(jié)點(diǎn)。知道了__list_add()函數(shù)的實(shí)現(xiàn)我們接下來(lái)當(dāng)然也要看看list_add()和list_add_tail()的實(shí)現(xiàn)。

　　[html] view plaincopystatic inline void list_add(struct list_head *new, struct list_head *head)

　　{

　　__list_add(new, head, head->next);

　　}

　　static inline void list_add_tail(struct list_head *new, struct list_head *head)

　　{

　　__list_add(new, head->prev, head);

　　}

　　看了上面的實(shí)現(xiàn)方式我們知道他們都是調(diào)用底層的__list_add()來(lái)實(shí)現(xiàn)的?？纯丛赺_list_add()函數(shù)里面?zhèn)鬟f不同的參數(shù)我們就能實(shí)現(xiàn)不同的添加節(jié)點(diǎn)的方法。__list_add()函數(shù)前面的雙劃線通常表示這是一個(gè)底層函數(shù)，供其他的模塊調(diào)用。

　　第一個(gè)list_add()傳遞的參數(shù)實(shí)現(xiàn)的是在head和head->next兩指針?biāo)赶虻慕Y(jié)點(diǎn)之間插入new所指向的結(jié)點(diǎn)。即就是在head指針的后面插入一個(gè)new所指向的結(jié)點(diǎn)。Head并非一定為頭結(jié)點(diǎn)。如果我們的鏈表只含有一個(gè)頭節(jié)點(diǎn)時(shí)，上面的__list_add(new, head, head->next)仍然成立。

　　第二個(gè)list_add_tail()其功能是在結(jié)點(diǎn)指針head所指向結(jié)點(diǎn)的前面插入new所指向的結(jié)點(diǎn)。當(dāng)如果head指向的是頭結(jié)點(diǎn)，那么就相當(dāng)于在尾結(jié)點(diǎn)后面增加一個(gè)new所指向的結(jié)點(diǎn)。在這個(gè)函數(shù)里值得注意的是head->prev不能為空，如果head為頭結(jié)點(diǎn)，那么head->prev要指向一個(gè)數(shù)值，一般為指向尾結(jié)點(diǎn)，構(gòu)成循環(huán)鏈表。

　　說(shuō)到這兒可能有的讀者已經(jīng)迫不及待的想看看代碼了，那我們就用linux內(nèi)核里的list.h在應(yīng)用層來(lái)寫出我們的代碼。

　　[html] view plaincopy#include

　　#include

　　#include "list.h"

　　typedef struct _stu

　　{

　　char name[20];

　　int num;

　　struct list_head list;

　　}stu;

　　int main()

　　{

　　stu *pstu;

　　stu *tmp_stu;

　　struct list_head stu_list;

　　struct list_head *pos;

　　int i = 0;

　　INIT_LIST_HEAD(&stu_list);

　　pstu = malloc(sizeof(stu)*5);

　　for(i=0;i<5;i++)

　　{

　　sprintf(pstu[i].name,"Stu%d",i+1);

　　pstu[i].num = i+1;

　　list_add( &(pstu[i].list), &stu_list);

　　}

　　list_for_each(pos,&stu_list)

　　{

　　tmp_stu = list_entry(pos, stu, list);

　　printf("student num: %dtstudent name: %sn",tmp_stu->num,tmp_stu->name);

　　}

　　free(pstu);

　　return 0;

　　}

　　運(yùn)行結(jié)果為：

　　[html] view plaincopyroot@ubuntu:/home/paixu/dlist_node# ./a

　　student num: 5 student name: Stu5

　　student num: 4 student name: Stu4

　　student num: 3 student name: Stu3

　　student num: 2 student name: Stu2

　　student num: 1 student name: Stu1

　　看看上面的代碼，我們做的基本工作都有那些呢?

　　1、定義了一個(gè)宿主結(jié)構(gòu)體stu，并且在宿主結(jié)構(gòu)體中我們定義了一個(gè)struct list_head 類型的list變量;

　　2、定義一個(gè)頭結(jié)點(diǎn)并且對(duì)其進(jìn)行初始化工作;

　　3、對(duì)定義的一個(gè)宿主結(jié)構(gòu)體變量申請(qǐng)內(nèi)存空間;

　　4、對(duì)申請(qǐng)的宿主結(jié)構(gòu)體變量初始化和添加到以stu_list為頭結(jié)點(diǎn)的鏈表中。

　　在上面值得注意的就是list_for_each()和list_entry()，我們會(huì)在接下來(lái)的部分講解，讀者在這兒只需要知道它們兩個(gè)在此合在一起的作用就是打印出宿主結(jié)構(gòu)stu中每個(gè)數(shù)據(jù)。sprintf()的使用就不在這里講解了，很簡(jiǎn)單，相信讀者猜都可以猜出它的功能。讀者如果一開始對(duì)上面的文字描述部分有什么疑惑或者不解的現(xiàn)在看了代碼的實(shí)現(xiàn)應(yīng)該都懂了，list_add_tail()的使用和list_add()類似，讀者可以自己修改代碼實(shí)現(xiàn)。如果一開始對(duì)于list_add()不太理解的讀者，現(xiàn)在對(duì)于list_add()的理解現(xiàn)在可以參考運(yùn)行結(jié)果和上面的文字描述部分。

　　我們接著往下看。

　　[html] view plaincopystatic inline void __list_del(struct list_head * prev, struct list_head * next)

　　{

　　next->prev = prev;

　　prev->next = next;

　　}

　　在prev和next指針?biāo)赶虻慕Y(jié)點(diǎn)之間，兩者互相所指。其實(shí)也就是prev為待刪除的結(jié)點(diǎn)的前面一個(gè)結(jié)點(diǎn)，next為待刪除的結(jié)點(diǎn)的后面一個(gè)結(jié)點(diǎn)。

　　[html] view plaincopystatic inline void list_del(struct list_head *entry)

　　{

　　__list_del(entry->prev, entry->next);

　　entry->next = LIST_POISON1;

　　entry->prev = LIST_POISON2;

　　}

　　刪除entry所指的結(jié)點(diǎn)，同時(shí)將entry所指向的結(jié)點(diǎn)指針域封死。在這里值得注意的是LIST_POISON1、LIST_POISON2。它們?cè)趌ist.h中的宏定義如下：

　　#define LIST_POISON1 ((void *) 0x00100100)

　　#define LIST_POISON2 ((void *) 0x00200200)

　　對(duì)LIST_POISON1、LIST_POISON2的說(shuō)明，Linux 內(nèi)核中有這么一句話：These are non-NULL pointers that will result in page faults under normal circumstances，used to verify that nobody uses non-initialized list entries。也就是說(shuō)它們并不是空指針，但是訪問(wèn)這樣的指針在正常情況下是會(huì)導(dǎo)致出錯(cuò)的。其實(shí)按照我們一般的思路都是把entry->next 和entry->prev 賦值為NULL，使得不可以通過(guò)該節(jié)點(diǎn)進(jìn)行訪問(wèn)。但是在這里使用了一種特殊的方法。注意：我在linux環(huán)境下以上宏的值不用修改是不會(huì)出錯(cuò)的，但是在vc下就會(huì)出錯(cuò)，不允許使用那兩個(gè)值，所以要修改為NULL。

　　[html] view plaincopystatic inline void list_del_init(struct list_head *entry)

　　{

　　__list_del(entry->prev, entry->next);

　　INIT_LIST_HEAD(entry);

　　}

　　以上函數(shù)的功能為刪除entry所指向的結(jié)點(diǎn)，同時(shí)調(diào)用LIST_INIT_HEAD()把被刪除結(jié)點(diǎn)為作為鏈表頭構(gòu)建一個(gè)新的空雙循環(huán)鏈表。

　　[html] view plaincopy#include

　　#include

　　#include "list.h"

　　typedef struct _stu

　　{

　　char name[20];

　　int num;

　　struct list_head list;

　　}stu;

　　int main()

　　{

　　stu *pstu;

　　stu *tmp_stu;

　　struct list_head stu_list;

　　struct list_head *pos;

　　int i = 0;

　　INIT_LIST_HEAD(&stu_list);

　　pstu = malloc(sizeof(stu)*5);

　　for(i=0;i<5;i++)

　　{

　　sprintf(pstu[i].name,"Stu%d",i+1);

　　pstu[i].num = i+1;

　　list_add( &(pstu[i].list), &stu_list);

　　}

　　list_del(&(pstu[3].list));

　　printf("使用list_del()刪除pstu[3]n");

　　list_for_each(pos,&stu_list)

　　{

　　tmp_stu = list_entry(pos, stu, list);

　　printf("student num: %dtstudent name: %sn",tmp_stu->num,tmp_stu->name);

　　}

　　list_del_init(&(pstu[2].list));

　　printf("使用list_del_init()刪除pstu[2]n");

　　list_for_each(pos,&stu_list)

　　{

　　tmp_stu = list_entry(pos, stu, list);

　　printf("student num: %dtstudent name: %sn",tmp_stu->num,tmp_stu->name);

　　}

　　free(pstu);

　　return 0;

　　}

　　運(yùn)行結(jié)果為：

　　[cpp] view plaincopyroot@ubuntu:/home/paixu/dlist_node# ./a

　　使用list_del()刪除pstu[3]

　　student num: 5 student name: Stu5

　　student num: 3 student name: Stu3

　　student num: 2 student name: Stu2

　　student num: 1 student name: Stu1

　　使用list_del_init()刪除pstu[2]

　　student num: 5 student name: Stu5

　　student num: 2 student name: Stu2

　　student num: 1 student name: Stu1

　　看了代碼的使用之后我們?cè)偃ダ斫庵暗闹v解就要輕松多了。讀者可以結(jié)合上面相應(yīng)的文字描述再分析下代碼，以加深印象。接著往下看，堅(jiān)持看完本篇博客的最后兩個(gè)函數(shù)。

　　[html] view plaincopystatic inline void list_move(struct list_head *list, struct list_head *head)

　　{

　　__list_del(list->prev, list->next);

　　list_add(list, head);

　　}

　　static inline void list_move_tail(struct list_head *list,

　　struct list_head *head)

　　{

　　__list_del(list->prev, list->next);

　　list_add_tail(list, head);

　　}

　　看看上面兩個(gè)函數(shù)list_move()和list_move_tail()，第一個(gè)list_move()函數(shù)的功能是把list移至head和head->next兩個(gè)指針?biāo)赶虻慕Y(jié)點(diǎn)之間。而第二個(gè)list_move_tail()函數(shù)的功能是把list移至head和head->prev兩個(gè)指針?biāo)赶虻慕Y(jié)點(diǎn)之間。如果讀者覺(jué)得這樣說(shuō)不是太具體的話，那么我們來(lái)看看下面的代碼。

　　[cpp] view plaincopy#include

　　#include

　　#include "list.h"

　　typedef struct _stu

　　{

　　char name[20];

　　int num;

　　struct list_head list;

　　}stu;

　　int main()

　　{

　　stu *pstu;

　　stu *tmp_stu;

　　struct list_head stu_list;

　　struct list_head *pos;

　　int i = 0;

　　INIT_LIST_HEAD(&stu_list);

　　pstu = malloc(sizeof(stu)*5);

　　for(i=0;i<5;i++)

　　{

　　sprintf(pstu[i].name,"Stu%d",i+1);

　　pstu[i].num = i+1;

　　list_add( &(pstu[i].list), &stu_list);

　　}

　　list_move(&(pstu[3].list),&stu_list);

　　printf("把pstu[3]移至head和head->next兩個(gè)指針?biāo)赶虻慕Y(jié)點(diǎn)之間n");

　　list_for_each(pos,&stu_list)

　　{

　　tmp_stu = list_entry(pos, stu, list);

　　printf("student num: %dtstudent name: %sn",tmp_stu->num,tmp_stu->name);

　　}

　　list_move_tail(&(pstu[2].list),&stu_list);

　　printf("把pstu[2]移至head和head->prev兩個(gè)指針?biāo)赶虻慕Y(jié)點(diǎn)之間n");

　　list_for_each(pos,&stu_list)

　　{

　　tmp_stu = list_entry(pos, stu, list);

　　printf("student num: %dtstudent name: %sn",tmp_stu->num,tmp_stu->name);

　　}

　　free(pstu);

　　return 0;

　　}

　　運(yùn)行結(jié)果為：

　　[cpp] view plaincopyroot@ubuntu:/home/paixu/dlist_node# ./a

　　把pstu[3]移至head和head->next兩個(gè)指針?biāo)赶虻慕Y(jié)點(diǎn)之間

　　student num: 4 student name: Stu4

　　student num: 5 student name: Stu5

　　student num: 3 student name: Stu3

　　student num: 2 student name: Stu2

　　student num: 1 student name: Stu1

　　把pstu[2]移至head和head->prev兩個(gè)指針?biāo)赶虻慕Y(jié)點(diǎn)之間

　　student num: 4 student name: Stu4

　　student num: 5 student name: Stu5

　　student num: 2 student name: Stu2

　　student num: 1 student name: Stu1

　　student num: 3 student name: Stu3

　　在此之前先說(shuō)一個(gè)注意點(diǎn)，以免部分讀者以為結(jié)果有誤，pstu[]中的下標(biāo)是從0開始的，所以pstu[3]對(duì)應(yīng)的是stu4。

　　這篇先講到這里，余下的我們?cè)谙旅嬉黄禖語(yǔ)言的那些小秘密之鏈表(四)》中繼續(xù)講。由于本人水平有限，博客中的不妥或錯(cuò)誤之處在所難免，殷切希望讀者批評(píng)指正。同時(shí)也歡迎讀者共同探討相關(guān)的內(nèi)容，如果樂(lè)意交流的話請(qǐng)留下你寶貴的意見。