C語言的那些小秘密之鏈表（三）

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

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

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

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

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

　　補充一點：(注：如果讀者看不懂下面這段代碼，可以繼續(xù)往下看，不會影響接下來的學(xué)習(xí)，在接下來的部分還會有講解，這部分代碼是我寫完全文后添加的，因為一開始我使用的是#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) ); } )

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

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

　　[html] view plaincopystruct list_head {

　　struct list_head *next, *prev;

　　};

　　在linux內(nèi)核雙向循環(huán)鏈表中我們用以上list_head類型定義一個變量，將其作為一個成員嵌入到宿主結(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中的成員和相對應(yīng)的處理函數(shù)來對鏈表進行遍歷操作，如果想得到宿主結(jié)構(gòu)的指針，使用我們可以使用list_entry計算出來，先別急著想知道list_entry什么，我們會在下面講解，接著往下看。

　　在宿主結(jié)構(gòu)體中定義了list_head之后接下來當(dāng)然是要對我們定義的頭結(jié)點進行初始化工作，初始化的實現(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)

　　分析上面的代碼可知，我們在代碼中使用list_head定義了一個頭結(jié)點之后，就要對定義的頭結(jié)點進行初始化工作，可以使用INIT_LIST_HEAD(ptr)宏進行初始化，或者我們無需自己定義直接使用LIST_HEAD(name)宏即可完成定義和初始化的工作。頭結(jié)點的初始化工作完成了之后接下來的工作當(dāng)然是要添加節(jié)點了。

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

　　}

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

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

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

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

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

　　}

　　運行結(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、定義了一個宿主結(jié)構(gòu)體stu，并且在宿主結(jié)構(gòu)體中我們定義了一個struct list_head 類型的list變量;

　　2、定義一個頭結(jié)點并且對其進行初始化工作;

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

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

　　在上面值得注意的就是list_for_each()和list_entry()，我們會在接下來的部分講解，讀者在這兒只需要知道它們兩個在此合在一起的作用就是打印出宿主結(jié)構(gòu)stu中每個數(shù)據(jù)。sprintf()的使用就不在這里講解了，很簡單，相信讀者猜都可以猜出它的功能。讀者如果一開始對上面的文字描述部分有什么疑惑或者不解的現(xiàn)在看了代碼的實現(xiàn)應(yīng)該都懂了，list_add_tail()的使用和list_add()類似，讀者可以自己修改代碼實現(xiàn)。如果一開始對于list_add()不太理解的讀者，現(xiàn)在對于list_add()的理解現(xià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é)點之間，兩者互相所指。其實也就是prev為待刪除的結(jié)點的前面一個結(jié)點，next為待刪除的結(jié)點的后面一個結(jié)點。

　　[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é)點，同時將entry所指向的結(jié)點指針域封死。在這里值得注意的是LIST_POISON1、LIST_POISON2。它們在list.h中的宏定義如下：

　　#define LIST_POISON1 ((void *) 0x00100100)

　　#define LIST_POISON2 ((void *) 0x00200200)

　　對LIST_POISON1、LIST_POISON2的說明，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。也就是說它們并不是空指針，但是訪問這樣的指針在正常情況下是會導(dǎo)致出錯的。其實按照我們一般的思路都是把entry->next 和entry->prev 賦值為NULL，使得不可以通過該節(jié)點進行訪問。但是在這里使用了一種特殊的方法。注意：我在linux環(huán)境下以上宏的值不用修改是不會出錯的，但是在vc下就會出錯，不允許使用那兩個值，所以要修改為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ào)用LIST_INIT_HEAD()把被刪除結(jié)點為作為鏈表頭構(gòu)建一個新的空雙循環(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;

　　}

　　運行結(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

　　看了代碼的使用之后我們再去理解之前的講解就要輕松多了。讀者可以結(jié)合上面相應(yīng)的文字描述再分析下代碼，以加深印象。接著往下看，堅持看完本篇博客的最后兩個函數(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);

　　}

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

　　[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兩個指針?biāo)赶虻慕Y(jié)點之間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兩個指針?biāo)赶虻慕Y(jié)點之間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;

　　}

　　運行結(jié)果為：

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

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

　　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兩個指針?biāo)赶虻慕Y(jié)點之間

　　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

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

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