C語(yǔ)言的那些小秘密之鏈表(四)
大多數(shù)的讀者在學(xué)習(xí)編程語(yǔ)言的時(shí)候都不喜歡那些枯燥的文字描述,包括我自己在開始學(xué)習(xí)編程的時(shí)候也是這樣,對(duì)于代碼的熱情遠(yuǎn)遠(yuǎn)高于文字,所以我在我寫東西的時(shí)候也不喜歡用枯燥的文字描述來(lái)向讀者講解,更喜歡用代碼加上適當(dāng)?shù)奈淖置枋龅姆绞竭M(jìn)行講解,因?yàn)橛行〇|西可能用枯燥的文字描述半天還不如實(shí)實(shí)在在的給讀者呈現(xiàn)出一段簡(jiǎn)單的代碼,讓讀者理解得更加的透徹些。但是并不是說(shuō)文字描述就沒用,文字描述也很重要,只是絕大部分讀者都更加的希望直接達(dá)到最終的效果,都想跳過(guò)那些中間的步驟。接下來(lái)我們接著上一篇博客《C語(yǔ)言的那些小秘密之鏈表(三)》的內(nèi)容繼續(xù)講解linux內(nèi)核雙向循環(huán)鏈表。[cpp] view plaincopystatic inline int list_empty(const struct list_head *head)
本文引用地址:http://m.butianyuan.cn/article/273506.htm{
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()函數(shù)和list_empty_careful()函數(shù)都是用來(lái)檢測(cè)鏈表是否為空的。但是稍有區(qū)別的就是第一個(gè)鏈表使用的檢測(cè)方法是判斷表頭的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)是否為其本身,如果是則返回為true,否則返回false。第二個(gè)函數(shù)使用的檢測(cè)方法是判斷表頭的前一個(gè)結(jié)點(diǎn)和后一個(gè)結(jié)點(diǎn)是否為其本身,如果同時(shí)滿足則返回false,否則返回值為true。說(shuō)多了可能讀者就會(huì)沒耐心了,那么接下來(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()檢測(cè),鏈表為空n");
else
printf("使用list_empty()檢測(cè),鏈表非空n");
if(list_empty_careful(&stu_list))
printf("使用list_empty_careful()檢測(cè),鏈表為空n");
else
printf("使用list_empty_careful()檢測(cè),鏈表非空n");
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
使用list_empty()檢測(cè),鏈表非空
使用list_empty_careful()檢測(cè),鏈表非空
看看代碼就知道如何使用了,接下來(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è)地方我覺得最好的方法就是使用圖示來(lái)進(jìn)行講解,直觀易懂,如果用文字描述半天還不如讀者看一眼圖。
將一個(gè)鏈表插入到另外一個(gè)鏈表中。不作鏈表是否為空的檢查,由調(diào)用者默認(rèn)保證。因?yàn)槊總€(gè)鏈表只有一個(gè)頭節(jié)點(diǎn),將空鏈表插入到另外一個(gè)鏈表中是沒有意義的。但被插入的鏈表可以是空的。
[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所指向的頭結(jié)點(diǎn),因?yàn)閮蓚€(gè)鏈表有兩個(gè)頭結(jié)點(diǎn),所以我們必須要去掉其中一個(gè)頭結(jié)點(diǎn)。只要list非空鏈,head無(wú)任何限制,該函數(shù)就能實(shí)現(xiàn)鏈表的合并。
[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);
}
}
以上函數(shù)的功能是將一個(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;
}
運(yùn)行結(jié)果為:
[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
有了直觀的代碼和運(yùn)行結(jié)果,理解起來(lái)也更加的容易了。
有了上面的這些操作,但是我們還一直沒有講到我們最終所關(guān)心的宿主結(jié)構(gòu),那么接下來(lái)我們一起來(lái)看看我們?cè)撊绾稳〕鏊拗鹘Y(jié)構(gòu)的指針呢?這也是我認(rèn)為linux內(nèi)核雙向循環(huán)鏈表實(shí)現(xiàn)最為巧妙的地方了。
[cpp] view plaincopy#define list_entry(ptr, type, member)
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
看看上面的代碼,發(fā)現(xiàn)一個(gè)很熟悉的身影(unsigned long)(&((type *)0)->member)),這個(gè)我在前一篇博客《C語(yǔ)言的那些小秘密之字節(jié)對(duì)齊》中已經(jīng)講解過(guò)了,多以在此就不再做過(guò)多的講解,如果有不明白的讀者可以回過(guò)去看看講解再回過(guò)來(lái)閱讀。通過(guò)(unsigned long)(&((type *)0)->member))我們得出了成員變量member的偏移量,而ptr為指向member的指針,因?yàn)橹羔橆愋筒煌脑?,所以我們?cè)俅我冗M(jìn)行(char*)的轉(zhuǎn)換之后再進(jìn)行計(jì)算。所以我們用ptr減去member的偏移量就得到了宿主結(jié)構(gòu)體的指針,這就是一個(gè)非常巧妙的地方,這也就使得linux內(nèi)核雙向循環(huán)鏈表能夠區(qū)別于傳統(tǒng)鏈表的關(guān)鍵所在。可能看到這兒的時(shí)候讀者已經(jīng)感覺非常的枯燥了,但是別放棄,堅(jiān)持看完,因?yàn)殡m然這樣的講解枯燥了點(diǎn),但是非常有用。所以堅(jiān)持堅(jiā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為頭節(jié)點(diǎn),遍歷過(guò)程中首先從(head)->next開始,當(dāng)pos==head時(shí)退出,故head節(jié)點(diǎn)并沒有訪問,這和鏈表的結(jié)構(gòu)設(shè)計(jì)有關(guān),通常頭節(jié)點(diǎn)都不含有其它有效信息,因此可以把頭節(jié)點(diǎn)作為雙向鏈表遍歷一遍的檢測(cè)標(biāo)志來(lái)使用。在list_for_each宏中讀者可能發(fā)現(xiàn)一個(gè)比較陌生的面孔,我們?cè)诖司筒粚refetch展開了講解了,有興趣的讀者可以自己查看下它的實(shí)現(xiàn),其功能是預(yù)取內(nèi)存的內(nèi)容,也就是程序告訴CPU哪些內(nèi)容可能馬上用到,CPU預(yù)先其取出內(nèi)存操作數(shù),然后將其送入高速緩存,用于優(yōu)化,是的執(zhí)行速度更快。接下來(lái)的__list_for_each()宏和list_for_each_prev()宏就不在此做一一的講解了,和list_for_each()宏類似。 就是遍歷的方向有所改變或者不使用預(yù)取。
通過(guò)上面的講解和前面那么多的代碼,相信讀者這個(gè)時(shí)候?qū)τ趌ist_for_each()已經(jīng)不再感到陌生了。上面的但三個(gè)遍歷鏈表的宏都類似,繼續(xù)往下看。
[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è)節(jié)點(diǎn)的地址,避免了因?yàn)閜os節(jié)點(diǎn)被釋放而造成的斷鏈,這也就體現(xiàn)出了safe。也就是說(shuō)你可以遍歷完當(dāng)前節(jié)點(diǎn)后將其刪除,同時(shí)可以接著訪問下一個(gè)節(jié)點(diǎn),遍歷完畢后就只剩下一個(gè)頭節(jié)點(diǎn)。當(dāng)然這有一個(gè)最為典型的應(yīng)用,那就是我們?cè)诙噙M(jìn)程編程時(shí)候,多個(gè)進(jìn)程等待在同一個(gè)等待隊(duì)列上,若事件發(fā)生時(shí)喚醒所有進(jìn)程,則可以喚醒后將其依次從等待隊(duì)列中刪除。
[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)刪除結(jié)點(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)刪除結(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é)果為:
[html] view plaincopyroot@ubuntu:/home/paixu/dlist_node# ./a
通過(guò)list_for_each_safe()遍歷使用list_del(pos)刪除結(jié)點(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)刪除結(jié)點(diǎn)后
讀者可以結(jié)合運(yùn)行結(jié)果再去閱讀上面的文字描述部分。
如果只提供對(duì)list_head結(jié)構(gòu)的遍歷操作是遠(yuǎn)遠(yuǎn)不夠的,我們希望實(shí)現(xiàn)的是對(duì)宿主結(jié)構(gòu)的遍歷,即在遍歷時(shí)直接獲得當(dāng)前鏈表節(jié)點(diǎn)所在的宿主結(jié)構(gòu)項(xiàng),而不是每次要同時(shí)調(diào)用list_for_each()和list_entry()。為此Linux特地提供了list_for_each_entry()宏來(lái)實(shí)現(xiàn)
[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è)參數(shù)為傳入的遍歷指針,指向宿主數(shù)據(jù)結(jié)構(gòu),第二個(gè)參數(shù)為鏈表頭,為list_head結(jié)構(gòu),第三個(gè)參數(shù)為list_head結(jié)構(gòu)在宿主結(jié)構(gòu)中的成員名。有時(shí)候做過(guò)多的講解反而沒有看看代碼的效果好,我們還是用段代碼來(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;
}
運(yùn)行結(jié)果為:
[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
如果讀者一開始對(duì)于文字描述感到陌生的話,那么就再次結(jié)合代碼去閱讀。
接下來(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類似,只是其中略有差別,list_prepare_entry()中含有prefetch(),它的作用在上面已經(jīng)講解,有什么疑惑可以返回去閱讀下,在此不再做過(guò)多的講解;list_for_each_entry_continue()和list_for_each_entry()的區(qū)別主要是list_for_each_entry_continue()可以不從鏈表頭開始遍歷,而是從已知的某個(gè)pos結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開始遍歷。在某些時(shí)候如果不是從頭結(jié)點(diǎn)開始遍歷,那么為了保證pos的初始值有效,必須使用list_prepare_entry()。其含義就是如果pos非空,那么pos的值就為其本身,如果pos為空,那么就從鏈表頭強(qiáng)制擴(kuò)展一個(gè)虛pos指針,讀者自己分析list_prepare_entry()的實(shí)現(xiàn)就明白了。list_for_each_entry_safe()要求調(diào)用者另外提供一個(gè)與pos同類型的指針n,在for循環(huán)中暫存pos下一個(gè)節(jié)點(diǎn)的宿主結(jié)構(gòu)體的地址,避免因pos節(jié)點(diǎn)被釋放而造成的斷鏈。
到此我們linux內(nèi)核雙向循環(huán)鏈表的旅程就結(jié)束了,下一篇我們將開始一個(gè)新的旅程。由于本人水平有限,博客中的不妥或錯(cuò)誤之處在所難免,殷切希望讀者批評(píng)指正。同時(shí)也歡迎讀者共同探討相關(guān)的內(nèi)容,如果樂意交流的話請(qǐng)留下你寶貴的意見。
c語(yǔ)言相關(guān)文章:c語(yǔ)言教程
評(píng)論