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

　　大多數的讀者在學(xué)習編程語(yǔ)言的時(shí)候都不喜歡那些枯燥的文字描述，包括我自己在開(kāi)始學(xué)習編程的時(shí)候也是這樣，對于代碼的熱情遠遠高于文字，所以我在我寫(xiě)東西的時(shí)候也不喜歡用枯燥的文字描述來(lái)向讀者講解，更喜歡用代碼加上適當的文字描述的方式進(jìn)行講解，因為有些東西可能用枯燥的文字描述半天還不如實(shí)實(shí)在在的給讀者呈現出一段簡(jiǎn)單的代碼，讓讀者理解得更加的透徹些。但是并不是說(shuō)文字描述就沒(méi)用，文字描述也很重要，只是絕大部分讀者都更加的希望直接達到最終的效果，都想跳過(guò)那些中間的步驟。接下來(lái)我們接著(zhù)上一篇博客《C語(yǔ)言的那些小秘密之鏈表(三)》的內容繼續講解linux內核雙向循環(huán)鏈表。[cpp] view plaincopystatic inline int list_empty(const struct list_head *head)

　　{

　　return head->next == head;

　　}

　　static inline int list_empty_careful(const struct list_head *head)

　　{

　　struct list_head *next = head->next;

　　return (next == head) && (next == head->prev);

　　}

　　list_empty()函數和list_empty_careful()函數都是用來(lái)檢測鏈表是否為空的。但是稍有區別的就是第一個(gè)鏈表使用的檢測方法是判斷表頭的結點(diǎn)的下一個(gè)結點(diǎn)是否為其本身，如果是則返回為true，否則返回false。第二個(gè)函數使用的檢測方法是判斷表頭的前一個(gè)結點(diǎn)和后一個(gè)結點(diǎn)是否為其本身，如果同時(shí)滿(mǎn)足則返回false，否則返回值為true。說(shuō)多了可能讀者就會(huì )沒(méi)耐心了，那么接下來(lái)我來(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);

　　}

　　if(list_empty(&stu_list))

　　printf("使用list_empty()檢測，鏈表為空n");

　　else

　　printf("使用list_empty()檢測，鏈表非空n");

　　if(list_empty_careful(&stu_list))

　　printf("使用list_empty_careful()檢測，鏈表為空n");

　　else

　　printf("使用list_empty_careful()檢測，鏈表非空n");

　　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

　　使用list_empty()檢測，鏈表非空

　　使用list_empty_careful()檢測，鏈表非空

　　看看代碼就知道如何使用了，接下來(lái)看看鏈表的合成。

　　[html] view plaincopystatic inline void __list_splice(struct list_head *list,

　　struct list_head *head)

　　{

　　struct list_head *first = list->next;

　　struct list_head *last = list->prev;

　　struct list_head *at = head->next;

　　first->prev = head;

　　head->next = first;

　　last->next = at;

　　at->prev = last;

　　}

　　這個(gè)地方我覺(jué)得最好的方法就是使用圖示來(lái)進(jìn)行講解，直觀(guān)易懂，如果用文字描述半天還不如讀者看一眼圖。

　　將一個(gè)鏈表插入到另外一個(gè)鏈表中。不作鏈表是否為空的檢查，由調用者默認保證。因為每個(gè)鏈表只有一個(gè)頭節點(diǎn)，將空鏈表插入到另外一個(gè)鏈表中是沒(méi)有意義的。但被插入的鏈表可以是空的。

　　[cpp] view plaincopystatic inline void list_splice(struct list_head *list, struct list_head *head)

　　{

　　if (!list_empty(list))

　　__list_splice(list, head);

　　}

　　在這種情況下會(huì )丟棄list所指向的頭結點(diǎn)，因為兩個(gè)鏈表有兩個(gè)頭結點(diǎn)，所以我們必須要去掉其中一個(gè)頭結點(diǎn)。只要list非空鏈，head無(wú)任何限制，該函數就能實(shí)現鏈表的合并。

　　[cpp] view plaincopystatic inline void list_splice_init(struct list_head *list,

　　struct list_head *head)

　　{

　　if (!list_empty(list)) {

　　__list_splice(list, head);

　　INIT_LIST_HEAD(list);

　　}

　　}

　　以上函數的功能是將一個(gè)鏈表list的有效信息合并到另外一個(gè)鏈表head后，重新初始化被去掉的空的鏈表頭。這樣的描述可能不是太好理解，接下來(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,*pstu2;

　　stu *tmp_stu;

　　struct list_head stu_list,stu_list2;

　　struct list_head *pos;

　　int i = 0;

　　INIT_LIST_HEAD(&stu_list);

　　INIT_LIST_HEAD(&stu_list2);

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

　　pstu2 = malloc(sizeof(stu)*3);

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

　　{

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

　　sprintf(pstu2[i].name,"Stu%d",i+4);

　　pstu[i].num = i+1;

　　pstu2[i].num = i+4;

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

　　list_add( &(pstu2[i].list), &stu_list2);

　　}

　　printf("stu_list 鏈表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);

　　}

　　printf("stu_list2 鏈表n");

　　list_for_each(pos,&stu_list2)

　　{

　　tmp_stu = list_entry(pos, stu, list);

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

　　}

　　printf("stu_list鏈表和stu_list2 鏈表合并以后n");

　　list_splice(&stu_list2,&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

　　stu_list 鏈表

　　student num: 3 student name: Stu3

　　student num: 2 student name: Stu2

　　student num: 1 student name: Stu1

　　stu_list2 鏈表

　　student num: 6 student name: Stu6

　　student num: 5 student name: Stu5

　　student num: 4 student name: Stu4

　　stu_list鏈表和stu_list2 鏈表合并以后

　　student num: 6 student name: Stu6

　　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

　　有了直觀(guān)的代碼和運行結果，理解起來(lái)也更加的容易了。

　　有了上面的這些操作，但是我們還一直沒(méi)有講到我們最終所關(guān)心的宿主結構，那么接下來(lái)我們一起來(lái)看看我們該如何取出宿主結構的指針呢?這也是我認為linux內核雙向循環(huán)鏈表實(shí)現最為巧妙的地方了。

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

　　((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

　　看看上面的代碼，發(fā)現一個(gè)很熟悉的身影(unsigned long)(&((type *)0)->member))，這個(gè)我在前一篇博客《C語(yǔ)言的那些小秘密之字節對齊》中已經(jīng)講解過(guò)了，多以在此就不再做過(guò)多的講解，如果有不明白的讀者可以回過(guò)去看看講解再回過(guò)來(lái)閱讀。通過(guò)(unsigned long)(&((type *)0)->member))我們得出了成員變量member的偏移量，而ptr為指向member的指針，因為指針類(lèi)型不同的原因，所以我們再次要先進(jìn)行(char*)的轉換之后再進(jìn)行計算。所以我們用ptr減去member的偏移量就得到了宿主結構體的指針，這就是一個(gè)非常巧妙的地方，這也就使得linux內核雙向循環(huán)鏈表能夠區別于傳統鏈表的關(guān)鍵所在?？赡芸吹竭@兒的時(shí)候讀者已經(jīng)感覺(jué)非常的枯燥了，但是別放棄，堅持看完，因為雖然這樣的講解枯燥了點(diǎn)，但是非常有用。所以堅持堅持吧!

　　[cpp] view plaincopy#define list_for_each(pos, head)

　　for (pos = (head)->next; prefetch(pos->next), pos != (head);

　　pos = pos->next)

　　#define __list_for_each(pos, head)

　　for (pos = (head)->next; pos != (head); pos = pos->next)

　　#define list_for_each_prev(pos, head)

　　for (pos = (head)->prev; prefetch(pos->prev), pos != (head);

　　pos = pos->prev)

　　遍歷是雙循環(huán)鏈表的基本操作，head為頭節點(diǎn)，遍歷過(guò)程中首先從(head)->next開(kāi)始，當pos==head時(shí)退出，故head節點(diǎn)并沒(méi)有訪(fǎng)問(wèn)，這和鏈表的結構設計有關(guān)，通常頭節點(diǎn)都不含有其它有效信息，因此可以把頭節點(diǎn)作為雙向鏈表遍歷一遍的檢測標志來(lái)使用。在list_for_each宏中讀者可能發(fā)現一個(gè)比較陌生的面孔，我們在此就不將prefetch展開(kāi)了講解了，有興趣的讀者可以自己查看下它的實(shí)現，其功能是預取內存的內容，也就是程序告訴CPU哪些內容可能馬上用到，CPU預先其取出內存操作數，然后將其送入高速緩存，用于優(yōu)化，是的執行速度更快。接下來(lái)的__list_for_each()宏和list_for_each_prev()宏就不在此做一一的講解了，和list_for_each()宏類(lèi)似。 就是遍歷的方向有所改變或者不使用預取。

　　通過(guò)上面的講解和前面那么多的代碼，相信讀者這個(gè)時(shí)候對于list_for_each()已經(jīng)不再感到陌生了。上面的但三個(gè)遍歷鏈表的宏都類(lèi)似，繼續往下看。

　　[cpp] view plaincopy#define list_for_each_safe(pos, n, head)

　　for (pos = (head)->next, n = pos->next; pos != (head);

　　pos = n, n = pos->next)

　　以上list_for_each_safe()宏也同樣是用于遍歷的，不同的是里邊多出了一個(gè)n暫存pos下一個(gè)節點(diǎn)的地址，避免了因為pos節點(diǎn)被釋放而造成的斷鏈，這也就體現出了safe。也就是說(shuō)你可以遍歷完當前節點(diǎn)后將其刪除，同時(shí)可以接著(zhù)訪(fǎng)問(wèn)下一個(gè)節點(diǎn)，遍歷完畢后就只剩下一個(gè)頭節點(diǎn)。當然這有一個(gè)最為典型的應用，那就是我們在多進(jìn)程編程時(shí)候，多個(gè)進(jìn)程等待在同一個(gè)等待隊列上，若事件發(fā)生時(shí)喚醒所有進(jì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,*n;

　　int i = 0;

　　INIT_LIST_HEAD(&stu_list);

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

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

　　{

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

　　pstu[i].num = i+1;

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

　　}

　　printf("通過(guò)list_for_each_safe()遍歷使用list_del(pos)刪除結點(diǎn)前n");

　　list_for_each_safe(pos, n, &stu_list)

　　{

　　tmp_stu = list_entry(pos, stu, list);

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

　　list_del(pos);

　　}

　　printf("通過(guò)list_for_each()遍歷使用list_del(pos)刪除結點(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;

　　}

　　運行結果為：

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

　　通過(guò)list_for_each_safe()遍歷使用list_del(pos)刪除結點(diǎn)前

　　student num: 3 student name: Stu3

　　student num: 2 student name: Stu2

　　student num: 1 student name: Stu1

　　通過(guò)list_for_each()遍歷使用list_del(pos)刪除結點(diǎn)后

　　讀者可以結合運行結果再去閱讀上面的文字描述部分。

　　如果只提供對list_head結構的遍歷操作是遠遠不夠的，我們希望實(shí)現的是對宿主結構的遍歷，即在遍歷時(shí)直接獲得當前鏈表節點(diǎn)所在的宿主結構項，而不是每次要同時(shí)調用list_for_each()和list_entry()。為此Linux特地提供了list_for_each_entry()宏來(lái)實(shí)現

　　[cpp] view plaincopy#define list_for_each_entry(pos, head, member)

　　for (pos = list_entry((head)->next, typeof(*pos), member);

　　prefetch(pos->member.next), &pos->member != (head);

　　pos = list_entry(pos->member.next, typeof(*pos), member))

　　第一個(gè)參數為傳入的遍歷指針，指向宿主數據結構，第二個(gè)參數為鏈表頭，為list_head結構，第三個(gè)參數為list_head結構在宿主結構中的成員名。有時(shí)候做過(guò)多的講解反而沒(méi)有看看代碼的效果好，我們還是用段代碼來(lái)說(shuō)明下吧。

　　[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,*n;

　　int i = 0;

　　INIT_LIST_HEAD(&stu_list);

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

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

　　{

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

　　pstu[i].num = i+1;

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

　　}

　　list_for_each_entry(tmp_stu, &stu_list, 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: 3 student name: Stu3

　　student num: 2 student name: Stu2

　　student num: 1 student name: Stu1

　　如果讀者一開(kāi)始對于文字描述感到陌生的話(huà)，那么就再次結合代碼去閱讀。

　　接下來(lái)再來(lái)看看最后幾個(gè)。

　　[html] view plaincopy#define list_for_each_entry_reverse(pos, head, member)

　　for (pos = list_entry((head)->prev, typeof(*pos), member);

　　prefetch(pos->member.prev), &pos->member != (head);

　　pos = list_entry(pos->member.prev, typeof(*pos), member))

　　#define list_prepare_entry(pos, head, member)

　　((pos) ? : list_entry(head, typeof(*pos), member))

　　#define list_for_each_entry_continue(pos, head, member)

　　for (pos = list_entry(pos->member.next, typeof(*pos), member);

　　prefetch(pos->member.next), &pos->member != (head);

　　pos = list_entry(pos->member.next, typeof(*pos), member))

　　#define list_for_each_entry_safe(pos, n, head, member)

　　for (pos = list_entry((head)->next, typeof(*pos), member),

　　n = list_entry(pos->member.next, typeof(*pos), member);

　　&pos->member != (head);

　　pos = n, n = list_entry(n->member.next, typeof(*n), member))

　　以上幾個(gè)與list_for_each_entry類(lèi)似，只是其中略有差別，list_prepare_entry()中含有prefetch()，它的作用在上面已經(jīng)講解，有什么疑惑可以返回去閱讀下，在此不再做過(guò)多的講解;list_for_each_entry_continue()和list_for_each_entry()的區別主要是list_for_each_entry_continue()可以不從鏈表頭開(kāi)始遍歷，而是從已知的某個(gè)pos結點(diǎn)的下一個(gè)結點(diǎn)開(kāi)始遍歷。在某些時(shí)候如果不是從頭結點(diǎn)開(kāi)始遍歷，那么為了保證pos的初始值有效，必須使用list_prepare_entry()。其含義就是如果pos非空，那么pos的值就為其本身，如果pos為空，那么就從鏈表頭強制擴展一個(gè)虛pos指針，讀者自己分析list_prepare_entry()的實(shí)現就明白了。list_for_each_entry_safe()要求調用者另外提供一個(gè)與pos同類(lèi)型的指針n，在for循環(huán)中暫存pos下一個(gè)節點(diǎn)的宿主結構體的地址，避免因pos節點(diǎn)被釋放而造成的斷鏈。

　　到此我們linux內核雙向循環(huán)鏈表的旅程就結束了，下一篇我們將開(kāi)始一個(gè)新的旅程。由于本人水平有限，博客中的不妥或錯誤之處在所難免，殷切希望讀者批評指正。同時(shí)也歡迎讀者共同探討相關(guān)的內容，如果樂(lè )意交流的話(huà)請留下你寶貴的意見(jiàn)。