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

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

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

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

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

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

　　補充一點(diǎn)：(注：如果讀者看不懂下面這段代碼，可以繼續往下看，不會(huì )影響接下來(lái)的學(xué)習，在接下來(lái)的部分還會(huì )有講解，這部分代碼是我寫(xiě)完全文后添加的，因為一開(kāi)始我使用的是#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成員的類(lèi)型，將指向member的指針ptr賦值給__mptr，__mptr指針的類(lèi)型為member數據成員的類(lèi)型。通過(guò)(char *)__mptr將__mptr強制轉換為char指針，之后再減去offsetof(type,member)，即可得到宿主結構體的指針。如果有對offsetof(type,member)不懂的可以參考我之前寫(xiě)的一篇《C語(yǔ)言的那些小秘密之字節對齊》。

　　首先看看list_head結構的實(shí)現。

　　[html] view plaincopystruct list_head {

　　struct list_head *next, *prev;

　　};

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

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

　　[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)

　　分析上面的代碼可知，我們在代碼中使用list_head定義了一個(gè)頭結點(diǎn)之后，就要對定義的頭結點(diǎn)進(jìn)行初始化工作，可以使用INIT_LIST_HEAD(ptr)宏進(jìn)行初始化，或者我們無(wú)需自己定義直接使用LIST_HEAD(name)宏即可完成定義和初始化的工作。頭結點(diǎn)的初始化工作完成了之后接下來(lái)的工作當然是要添加節點(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è)非空結點(diǎn)中插入一個(gè)結點(diǎn)，值得注意的是new、prev、next均不能為空值。當然prev可以等于next，此時(shí)表示在只含頭節點(diǎn)的鏈表中插入新節點(diǎn)。知道了__list_add()函數的實(shí)現我們接下來(lái)當然也要看看list_add()和list_add_tail()的實(shí)現。

　　[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í)現方式我們知道他們都是調用底層的__list_add()來(lái)實(shí)現的?？纯丛赺_list_add()函數里面傳遞不同的參數我們就能實(shí)現不同的添加節點(diǎn)的方法。__list_add()函數前面的雙劃線(xiàn)通常表示這是一個(gè)底層函數，供其他的模塊調用。

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

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

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

　　[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;

　　}

　　運行結果為：

　　[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è)宿主結構體stu，并且在宿主結構體中我們定義了一個(gè)struct list_head 類(lèi)型的list變量;

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

　　3、對定義的一個(gè)宿主結構體變量申請內存空間;

　　4、對申請的宿主結構體變量初始化和添加到以stu_list為頭結點(diǎn)的鏈表中。

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

　　我們接著(zhù)往下看。

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

　　{

　　next->prev = prev;

　　prev->next = next;

　　}

　　在prev和next指針所指向的結點(diǎn)之間，兩者互相所指。其實(shí)也就是prev為待刪除的結點(diǎn)的前面一個(gè)結點(diǎn)，next為待刪除的結點(diǎn)的后面一個(gè)結點(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所指的結點(diǎn)，同時(shí)將entry所指向的結點(diǎn)指針域封死。在這里值得注意的是LIST_POISON1、LIST_POISON2。它們在list.h中的宏定義如下：

　　#define LIST_POISON1 ((void *) 0x00100100)

　　#define LIST_POISON2 ((void *) 0x00200200)

　　對LIST_POISON1、LIST_POISON2的說(shuō)明，Linux 內核中有這么一句話(huà)：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ō)它們并不是空指針，但是訪(fǎng)問(wèn)這樣的指針在正常情況下是會(huì )導致出錯的。其實(shí)按照我們一般的思路都是把entry->next 和entry->prev 賦值為NULL，使得不可以通過(guò)該節點(diǎn)進(jìn)行訪(fǎng)問(wèn)。但是在這里使用了一種特殊的方法。注意：我在linux環(huán)境下以上宏的值不用修改是不會(huì )出錯的，但是在vc下就會(huì )出錯，不允許使用那兩個(gè)值，所以要修改為NULL。

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

　　{

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

　　INIT_LIST_HEAD(entry);

　　}

　　以上函數的功能為刪除entry所指向的結點(diǎn)，同時(shí)調用LIST_INIT_HEAD()把被刪除結點(diǎn)為作為鏈表頭構建一個(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;

　　}

　　運行結果為：

　　[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

　　看了代碼的使用之后我們再去理解之前的講解就要輕松多了。讀者可以結合上面相應的文字描述再分析下代碼，以加深印象。接著(zhù)往下看，堅持看完本篇博客的最后兩個(gè)函數。

　　[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è)函數list_move()和list_move_tail()，第一個(gè)list_move()函數的功能是把list移至head和head->next兩個(gè)指針所指向的結點(diǎn)之間。而第二個(gè)list_move_tail()函數的功能是把list移至head和head->prev兩個(gè)指針所指向的結點(diǎn)之間。如果讀者覺(jué)得這樣說(shuō)不是太具體的話(huà)，那么我們來(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è)指針所指向的結點(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è)指針所指向的結點(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;

　　}

　　運行結果為：

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

　　把pstu[3]移至head和head->next兩個(gè)指針所指向的結點(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è)指針所指向的結點(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)，以免部分讀者以為結果有誤，pstu[]中的下標是從0開(kāi)始的，所以pstu[3]對應的是stu4。

　　這篇先講到這里，余下的我們在下面一篇《C語(yǔ)言的那些小秘密之鏈表(四)》中繼續講。由于本人水平有限，博客中的不妥或錯誤之處在所難免，殷切希望讀者批評指正。同時(shí)也歡迎讀者共同探討相關(guān)的內容，如果樂(lè )意交流的話(huà)請留下你寶貴的意見(jiàn)。