新聞中心

EEPW首頁(yè) > 嵌入式系統(tǒng) > 牛人業(yè)話 > C語(yǔ)言的那些小秘密之鏈表(三)

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

作者: 時(shí)間:2015-04-21 來源:網(wǎng)絡(luò) 收藏

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

本文引用地址:http://m.butianyuan.cn/article/272927.htm

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

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

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

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

  補(bǔ)充一點(diǎn):(注:如果讀者看不懂下面這段代碼,可以繼續(xù)往下看,不會(huì)影響接下來的學(xué)習(xí),在接下來的部分還會(huì)有講解,這部分代碼是我寫完全文后添加的,因?yàn)橐婚_始我使用的是#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強(qiáng)制轉(zhuǎn)換為char指針,之后再減去offsetof(type,member),即可得到宿主結(jié)構(gòu)體的指針。如果有對(duì)offsetof(type,member)不懂的可以參考我之前寫的一篇《的那些小秘密之字節(jié)對(duì)齊》。

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

  [html] view plaincopystruct list_head {

  struct list_head *next, *prev;

  };

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

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

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

  }

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

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

  第二個(gè)list_add_tail()其功能是在結(jié)點(diǎn)指針head所指向結(jié)點(diǎn)的前面插入new所指向的結(jié)點(diǎn)。當(dāng)如果head指向的是頭結(jié)點(diǎn),那么就相當(dāng)于在尾結(jié)點(diǎn)后面增加一個(gè)new所指向的結(jié)點(diǎn)。在這個(gè)函數(shù)里值得注意的是head->prev不能為空,如果head為頭結(jié)點(diǎn),那么head->prev要指向一個(gè)數(shù)值,一般為指向尾結(jié)點(diǎn),構(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;

  }

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

  看看上面的代碼,我們做的基本工作都有那些呢?

  1、定義了一個(gè)宿主結(jié)構(gòu)體stu,并且在宿主結(jié)構(gòu)體中我們定義了一個(gè)struct list_head 類型的list變量;

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

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

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

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

  #define LIST_POISON1 ((void *) 0x00100100)

  #define LIST_POISON2 ((void *) 0x00200200)

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

  }

  運(yùn)行結(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

  看了代碼的使用之后我們?cè)偃ダ斫庵暗闹v解就要輕松多了。讀者可以結(jié)合上面相應(yīng)的文字描述再分析下代碼,以加深印象。接著往下看,堅(jiān)持看完本篇博客的最后兩個(gè)函數(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);

  }

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

  [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è)指針?biāo)赶虻慕Y(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);

  }

  list_move_tail(&(pstu[2].list),&stu_list);

  printf("把pstu[2]移至head和head->prev兩個(gè)指針?biāo)赶虻慕Y(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é)果為:

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

  把pstu[3]移至head和head->next兩個(gè)指針?biāo)赶虻慕Y(jié)點(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è)指針?biāo)赶虻慕Y(jié)點(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

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

  這篇先講到這里,余下的我們?cè)谙旅嬉黄禖語(yǔ)言的那些小秘密之鏈表(四)》中繼續(xù)講。由于本人水平有限,博客中的不妥或錯(cuò)誤之處在所難免,殷切希望讀者批評(píng)指正。同時(shí)也歡迎讀者共同探討相關(guān)的內(nèi)容,如果樂意交流的話請(qǐng)留下你寶貴的意見。

c語(yǔ)言相關(guān)文章:c語(yǔ)言教程


linux相關(guān)文章:linux教程




關(guān)鍵詞: C語(yǔ)言 鏈表

評(píng)論


相關(guān)推薦

技術(shù)專區(qū)

關(guān)閉