|
在開始寫linux內核雙向循環鏈表之前，我一直在想我要不要用長篇大論的文字來描述linux內核雙向循環鏈表呢?經過認真的思考之后，我否決了用枯燥的文字向讀者描述linux內核雙向循環鏈表的想法，因為對于編程語言來說我相信大多數的讀者都應該不喜歡面對枯燥的文字，更喜歡看到代碼，同時那也是讀者閱讀文字后想要實現的東西，所以我決定在這里采用代碼加上適當的文字描述的方法來進行講解，這就使得我不可能用一篇的篇幅來講解完，所以會寫兩篇文章來講解這個知識點。希望讀者能夠堅持看完，學會以后在應用程序中寫雙向循環鏈表時，不用再自己去編寫那些麻煩的操作函數，充分利用linux內核里已經提供的遍歷鏈表的操作函數。 特此說明：我會把我在文章中編寫代碼時候用到的頭文件list.h上傳到我的空間，免積分下載，有需要的讀者可以自己去下載，當然也可以自己上網下載或者從自己安裝的linux系統中得到。 懂了linux內核里雙向循環鏈表的實現方式之后我們不得不驚嘆它的實現是如此的巧妙，為了讀者能夠順利的和我一起走完這次linux內核雙向循環鏈表之旅，在此之前我特地為之寫了一篇《C語言的那些小秘密之字節對齊》的文章，如果你發現在本篇文章中有些地方不懂的時候，你可以回過去看看《C語言的那些小秘密之字節對齊》再來接著繼續往下繼續全文的閱讀。 由于我們在linux內核中有大量的數據結構都需要用到雙向循環鏈表。若再采用以往那種傳統雙向循環鏈表的實現方式，我們不得不為這些數據結構維護各自的鏈表，并且為每個鏈表都要設計插入、查找、刪除等操作函數。這是因為我們在常規鏈表中用來維持鏈表的next和prev指針都是指向對應類型的對象，因此一種數據結構的鏈表操作函數不能用于操作其它數據結構的鏈表。為了解決這個問題，在Linux內核中采用了一種與類型無關的雙向循環鏈表實現方式，它的實現使得我們不用再為每個鏈表都要設計插入、查找、刪除等相關的操作函數。其實現方法就是將結構體中的指針prev和next從具體的數據結構中提取出來，構成一種通用的雙向循環鏈表數據結構list_head。如果需要構造某類對象的特定鏈表，則只需要在其結構體中定義一個類型為list_head類型的成員，通過這個定義的list_head類型的成員將這類對象連接起來，形成所需的雙向循環鏈表，進而通過通用鏈表函數對其進行操作。顯而易見是我們只需編寫通用鏈表函數，就可構造和操作不同對象的鏈表，而無需為每個創建的雙向循環鏈表編寫專用函數，從而大大的實現了代碼的重用。 下面我們就真正的開始我們的linux內核雙向循環鏈表之旅。讀者可以從網上下載一個linux內核雙向循環鏈表的list.h的頭文件，值得注意的就是因為內核版本的不同可能下載的頭文件有些差異，但是這個并不影響我們對于它的講解。讀者可以先看完全文后再動手也不遲，用list.h頭文件來實現我們的雙向循環鏈表。為了便于講解，我們就按照list.h頭文件中代碼的先后順序進行講解。 補充一點：(注：如果讀者看不懂下面這段代碼，可以繼續往下看，不會影響接下來的學習，在接下來的部分還會有講解，這部分代碼是我寫完全文后添加的，因為一開始我使用的是#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數據成員的類型。通過(char *)__mptr將__mptr強制轉換為char指針，之后再減去offsetof(type,member)，即可得到宿主結構體的指針。如果有對offsetof(type,member)不懂的可以參考我之前寫的一篇《C語言的那些小秘密之字節對齊》。 首先看看list_head結構的實現。 [html] view plaincopystruct list_head { struct list_head *next, *prev; }; 在linux內核雙向循環鏈表中我們用以上list_head類型定義一個變量，將其作為一個成員嵌入到宿主結構內。什么是宿主結構體呢?就是我們創建的雙向循環鏈表的結構體。可以將鏈表結構放在宿主結構內的任何地方，當然也可以為鏈表結構取任何名字，從而我們就可以用list_head中的成員和相對應的處理函數來對鏈表進行遍歷操作，如果想得到宿主結構的指針，使用我們可以使用list_entry計算出來，先別急著想知道list_entry什么，我們會在下面講解，接著往下看。 在宿主結構體中定義了list_head之后接下來當然是要對我們定義的頭結點進行初始化工作，初始化的實現方法可以有以下兩種方式。 [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定義了一個頭結點之后，就要對定義的頭結點進行初始化工作，可以使用INIT_LIST_HEAD(ptr)宏進行初始化，或者我們無需自己定義直接使用LIST_HEAD(name)宏即可完成定義和初始化的工作。頭結點的初始化工作完成了之后接下來的工作當然是要添加節點了。 [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()的功能是在兩個非空結點中插入一個結點，值得注意的是new、prev、next均不能為空值。當然prev可以等于next，此時表示在只含頭節點的鏈表中插入新節點。知道了__list_add()函數的實現我們接下來當然也要看看list_add()和list_add_tail()的實現。 [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); } 看了上面的實現方式我們知道他們都是調用底層的__list_add()來實現的。看看在__list_add()函數里面傳遞不同的參數我們就能實現不同的添加節點的方法。__list_add()函數前面的雙劃線通常表示這是一個底層函數，供其他的模塊調用。 第一個list_add()傳遞的參數實現的是在head和head->next兩指針所指向的結點之間插入new所指向的結點。即就是在head指針的后面插入一個new所指向的結點。Head并非一定為頭結點。如果我們的鏈表只含有一個頭節點時，上面的__list_add(new, head, head->next)仍然成立。 第二個list_add_tail()其功能是在結點指針head所指向結點的前面插入new所指向的結點。當如果head指向的是頭結點，那么就相當于在尾結點后面增加一個new所指向的結點。在這個函數里值得注意的是head->prev不能為空，如果head為頭結點，那么head->prev要指向一個數值，一般為指向尾結點，構成循環鏈表。 說到這兒可能有的讀者已經迫不及待的想看看代碼了，那我們就用linux內核里的list.h在應用層來寫出我們的代碼。 [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;inum,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、定義了一個宿主結構體stu，并且在宿主結構體中我們定義了一個struct list_head 類型的list變量; 2、定義一個頭結點并且對其進行初始化工作; 3、對定義的一個宿主結構體變量申請內存空間; 4、對申請的宿主結構體變量初始化和添加到以stu_list為頭結點的鏈表中。 在上面值得注意的就是list_for_each()和list_entry()，我們會在接下來的部分講解，讀者在這兒只需要知道它們兩個在此合在一起的作用就是打印出宿主結構stu中每個數據。sprintf()的使用就不在這里講解了，很簡單，相信讀者猜都可以猜出它的功能。讀者如果一開始對上面的文字描述部分有什么疑惑或者不解的現在看了代碼的實現應該都懂了，list_add_tail()的使用和list_add()類似，讀者可以自己修改代碼實現。如果一開始對于list_add()不太理解的讀者，現在對于list_add()的理解現在可以參考運行結果和上面的文字描述部分。 我們接著往下看。 [html] view plaincopystatic inline void __list_del(struct list_head * prev, struct list_head * next) { next->prev = prev; prev->next = next; } 在prev和next指針所指向的結點之間，兩者互相所指。其實也就是prev為待刪除的結點的前面一個結點，next為待刪除的結點的后面一個結點。 [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所指的結點，同時將entry所指向的結點指針域封死。在這里值得注意的是LIST_POISON1、LIST_POISON2。它們在list.h中的宏定義如下： #define LIST_POISON1 ((void *) 0x00100100) #define LIST_POISON2 ((void *) 0x00200200) 對LIST_POISON1、LIST_POISON2的說明，Linux 內核中有這么一句話：These are non-NULL pointers that will result in page faults under normal circumstances，used to verify that nobody uses non-initialized list entries。也就是說它們并不是空指針，但是訪問這樣的指針在正常情況下是會導致出錯的。其實按照我們一般的思路都是把entry->next 和entry->prev 賦值為NULL，使得不可以通過該節點進行訪問。但是在這里使用了一種特殊的方法。注意：我在linux環境下以上宏的值不用修改是不會出錯的，但是在vc下就會出錯，不允許使用那兩個值，所以要修改為NULL。 [html] view plaincopystatic inline void list_del_init(struct list_head *entry) { __list_del(entry->prev, entry->next); INIT_LIST_HEAD(entry); } 以上函數的功能為刪除entry所指向的結點，同時調用LIST_INIT_HEAD()把被刪除結點為作為鏈表頭構建一個新的空雙循環鏈表。 [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;inum,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: %d\tstudent name: %s\n",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 看了代碼的使用之后我們再去理解之前的講解就要輕松多了。讀者可以結合上面相應的文字描述再分析下代碼，以加深印象。接著往下看，堅持看完本篇博客的最后兩個函數。 [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); } 看看上面兩個函數list_move()和list_move_tail()，第一個list_move()函數的功能是把list移至head和head->next兩個指針所指向的結點之間。而第二個list_move_tail()函數的功能是把list移至head和head->prev兩個指針所指向的結點之間。如果讀者覺得這樣說不是太具體的話，那么我們來看看下面的代碼。 [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;inext兩個指針所指向的結點之間\n"); list_for_each(pos,&stu_list) { tmp_stu = list_entry(pos, stu, list); printf("student num: %d\tstudent name: %s\n",tmp_stu->num,tmp_stu->name); } list_move_tail(&(pstu[2].list),&stu_list); printf("把pstu[2]移至head和head->prev兩個指針所指向的結點之間\n"); list_for_each(pos,&stu_list) { tmp_stu = list_entry(pos, stu, list); printf("student num: %d\tstudent name: %s\n",tmp_stu->num,tmp_stu->name); } free(pstu); return 0; } 運行結果為： [cpp] view plaincopyroot@ubuntu:/home/paixu/dlist_node# ./a 把pstu[3]移至head和head->next兩個指針所指向的結點之間 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兩個指針所指向的結點之間 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 在此之前先說一個注意點，以免部分讀者以為結果有誤，pstu[]中的下標是從0開始的，所以pstu[3]對應的是stu4。 這篇先講到這里，余下的我們在下面一篇《C語言的那些小秘密之鏈表(四)》中繼續講。由于本人水平有限，博客中的不妥或錯誤之處在所難免，殷切希望讀者批評指正。同時也歡迎讀者共同探討相關的內容，如果樂意交流的話請留下你寶貴的意見。 |
