[轉]深入理解linux內核list_head

http://blog.chinaunix.net/uid-27122224-id-3277511.html
深入理解linux內核list_head的實現 2012-07-17 17:37:01

分類： LINUX

前言：在linux源代碼中有個頭文件為list.h。很多linux下的源代碼都會使用這個頭文件，它里面定義

了一個結構,以及定義了和其相關的一組函數，這個結構是這樣的：

點擊(此處)折疊或打開

1.struct list_head{

1.  struct list_head *next, *prev; 

3.};

那么這個頭文件又是有什么樣的作用呢，這篇文章就是用來解釋它的作用，雖然這是linux下的源代碼，但對

于學習C語言的人來說，這是算法和平臺沒有什么關系。

一、雙向鏈表

學習計算機的人都會開一門課程《數據結構》，里面都會有講解雙向鏈表的內容。

什么是雙向鏈表，它看起來是這樣的：

點擊(此處)折疊或打開

1.struct dlist

2.{

1.  int no; 

2.  void* data; 

3.  struct dlist *prev, *next; 

6.};
他的圖形結構圖：

現在有幾個結構體，它們是：

表示人的：

點擊(此處)折疊或打開

1.struct person

2.{

1.  int age; 

2.  int weight; 

5.};

表示動物的：

點擊(此處)折疊或打開

1.struct animal

2.{

1.  int age; 

2.  int weight; 

5.};

如果有一組filename變量和filedata變量，把它們存起來，我們會怎么做，當然就用數組了，但我們想使

用雙向鏈表，讓它們鏈接起來，那該怎么做，唯一可以做的就是給每個結構加如兩個成員，如下：

表示人的：

點擊(此處)折疊或打開

1.struct person

2.{

1.  int age; 

2.  int weight; 

3.  struct person *next, *prev; 

6.};
表示動物的：

點擊(此處)折疊或打開

1.struct animal

2.{

1.  int age; 

2.  int weight; 

3.  struct animal *next, *prev; 

6.};

現在有一個人的一個鏈表的鏈頭指針person_head （循環雙向鏈表）和動物的鏈表的鏈頭指針

ainimal_head ，我們要獲得特定年齡和特定體重的人或動物（假設不考慮重疊），那么代碼看起來可能是這樣：

點擊(此處)折疊或打開

1.struct person * get_percent(int age, int weight)

2.{

3.…....

1.  struct person *p; 

2.  for(p = person_head->next; p != person_head; p=p->next) 

3.  { 

4.        if(p->age == age && p->weight == weight) 

5.              return p; 

6.  } 

10.…...

11.}

那同理,要獲得一個特定年齡和重量的動物的函數get_animal(int age, int weight)的代碼也是和上面

的類似。

我們再回過頭來看這兩個結構，它們的指向前和指向后的指針其實都差不多，那把它們綜合起來吧，所以看起

來如下面：

點擊(此處)折疊或打開

1.struct list_head{

1.  struct list_head *next, *prev; 

3.};
表示人的：

點擊(此處)折疊或打開

1.struct person{

1.  int age; 

2.  int weight;

3.  struct list_head list; 

5.};
動物的：

點擊(此處)折疊或打開

1.struct animal

2.{

1.  int age; 

2.  int weight; 

3.  struct list_head list; 

6.};

可能又會有些人會問了，struct list_head都不是struct persion和struct animal類型，怎么可以

做鏈表的指針呢？其實，無論是什么樣的指針，它的大小都是一樣的，32位的系統中，指針的大小都是32位

（即4個字節），只是不同類型的指針在解釋的時候不一樣而已，那么這個struct list_head又是怎么去

做這些結構的鏈表指針呢，那么就請看下一節吧：）。

二、struct list_head結構的操作

首先，讓我們來看下和struct list_head有關的兩個宏，它們定義在list.h文件中。

點擊(此處)折疊或打開

1.#define LIST_HEAD_INIT(name) { &(name), &(name) }

2.#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

3.#define INIT_LIST_HEAD(ptr) do { ?

1.  (ptr)->next = (ptr); (ptr)->prev = (ptr); \ 

5.} while (0)
這兩個宏是用了定義雙向鏈表的頭節點的，定義一個雙向鏈表的頭節點，我們可以這樣：

點擊(此處)折疊或打開

1.struct list_head head;

2.LIST_HEAD_INIT(head);
又或者直接這樣：

點擊(此處)折疊或打開

1.LIST_HEAD(head);

這樣，我們就定義并初始化了一個頭節點。

點擊(此處)折疊或打開

1.#define LIST_HEAD_INIT(name) { &(name), &(name) }

就是用head的地址初始化其兩個成員next和prev ，使其都指向自己。

我們再看下和其相關的幾個函數，這些函數都作為內聯函數也都定義list.h中，這里要說明一下linux源碼

的一個風格，在下面的這些函數中以下劃線開始的函數是給內部調用的函數，而以符開始的函數就是對外使用

的函數，這些函數一般都是調用以下劃線開始的函數，或是說是對下劃線開始的函數的封裝。

2.1 增加節點的函數

點擊(此處)折疊或打開

1.static inline void __list_add();

2.static inline void list_add();

3.static inline void list_add_tail();
其實看源代碼是最好的講解了，這里我再簡單的講一下。

點擊(此處)折疊或打開

1./**

1. • __list_add - Insert a new entry between two known consecutive entries.
2. • @new:
3. • @prev:
4. • @next:
6. • This is only for internal list manipulation where we know the prev/next
7. • entries
8. */

10.static inline void __list_add(struct list_head * new,

1.         struct list_head * prev, struct list_head * next) 

12.{

1.   next->prev = new; 

2.   new->next = next; 

3.   new->prev = prev; 

4.   prev->next = new; 

17.}

18.//這個函數在prev和next間插入一個節點new。

20./**

1. • list_add - add a new entry
2. • @new: new entry to be added
3. • @head: list head to add it after
5. • Insert a new entry after the specified head.
6. • This is good for implementing stacks.
7. */

點擊(此處)折疊或打開

1.static inline void list_add(struct list_head new, struct list_head head)

2.{

1.   __list_add(new, head, head->next); 

4.}

5.//這個函數在head節點后面插入new節點。

7./**

1. • list_add_tail - add a new entry
2. • @new: new entry to be added
3. • @head: list head to add it before
5. • Insert a new entry before the specified head.
6. • This is useful for implementing queues.
7. */

15.static inline void list_add_tail(struct list_head new, struct list_head head)

16.{

1.   __list_add(new, head->prev, head);

   18.}
   這個函數和上面的那個函數相反，它在head節點的前面插入new節點。

2.2 從鏈表中刪除節點的函數

點擊(此處)折疊或打開

1./**

1. • __list_del -
2. • @prev:
3. • @next:
5. • Delete a list entry by making the prev/next entries point to each other.
7. • This is only for internal list manipulation where we know the prev/next
8. • entries
9. */

11.static inline void __list_del(struct list_head * prev,

1.         struct list_head * next) 

13.{

1.   next->prev = prev; 

2.   prev->next = next; 

16.}

18./**

1. • list_del - deletes entry from list.
2. • @entry: the element to delete from the list.
3. • • Note: list_empty on entry does not return true after this, the entry is in
4. • an undefined state.
5. */

24.static inline void list_del(struct list_head *entry)

25.{

1.  __list_del(entry->prev, entry->next); 

27.}

29./**

1. • list_del_init - deletes entry from list and reinitialize it.
2. • @entry: the element to delete from the list.
3. */

33.static inline void list_del_init(struct list_head *entry)

34.{

1.  __list_del(entry->prev, entry->next); 

2.   INIT_LIST_HEAD(entry); 

37.}

這里簡單說一下，list_del(struct list_head *entry)是從鏈表中刪除entry節點。

list_del_init(struct list_head *entry) 不但從鏈表中刪除節點，還把這個節點的向前向后指針都指

向自己，即初始化。

那么，我們怎么判斷這個鏈表是不是空的呢！上面我說了，這里的雙向鏈表都是有一個頭節點，而我們上面看到，定義一個頭節點時我們就初始化了，即它的prev和next指針都指向自己。所以這個函數是這樣的。

點擊(此處)折疊或打開

1./**

1. • list_empty - tests whether a list is empty
2. • @head: the list to test.
3. */

5.static inline int list_empty(struct list_head *head)

6.{

1.  return head->next == head; 

8.}

講了這幾個函數后，這又到了關鍵了，下面講解的一個宏的定義就是對第一節中，我們所要說的為什么在一個

結構中加入struct list_head變量就把這個結構變成了雙向鏈表呢，這其中的關鍵就是怎么通過這個

struct list_head變量來獲取整個結構的變量，下面這個宏就為你解開答案：

點擊(此處)折疊或打開

1./**

1. • list_entry - get the struct for this entry
2. • @ptr: the &struct list_head pointer.
3. • @type: the type of the struct this is embedded in.
4. • @member: the name of the list_struct within the struct.
5. */

7.#define list_entry(ptr, type, member) ?

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

乍一看下，不知道這個宏在說什么，沒關系，我舉個例子來為你一一解答 ：）

首先，我們還是用上面的結構：

點擊(此處)折疊或打開

1.struct person

2.{

1.  int age; 

2.  int weight; 

3.  struct list_head list; 

6.};

我們一看到這樣的結構就應該知道它定義了一個雙向鏈表，下面來看下。

我們有一個指針：

struct list_head *pos;

現在有這個指針，我們怎么去獲得這個指針所在的結構的變量（即是struct person變量，其實是struct

person指針）呢？看下面這樣使用：

點擊(此處)折疊或打開

1.struct person *one = list_entry(pos, struct person, list);
不明白是吧，展開一下 list_entry結構如下：

點擊(此處)折疊或打開

1.((struct person )((char )(pos) - (unsigned long)(&((struct person *)0)->list)))

我慢慢的分解，首先分成兩部分(char )(pos)減去(unsigned long)(&((struct person )0)-

list)然后轉 成(struct person *)類型的指針。

(char )(pos)：是將pos由struct list_head轉 成char* ，這個好理解。

(unsigned long)(&((struct person )0)->list)：先看最里面的(struct person )0)，它是把0

地址轉 成struct person指針，然后(struct person *)0)->list就是指向list變量，之后是

&((struct person *)0)->list是取這個變量的地址，最后是(unsigned long)(&((struct person

*)0)->list)把這個變量的地址值變成一個整形數！

這么復雜啊，其實說白了，這個(unsigned long)(&((struct person *)0)->list)的意思就是取list

變量在struct person結構中的偏移量。

用個圖形來說(unsigned long)(&((struct person *)0)->list，如下：

而(unsigned long)(&((struct person *)0)->list就是獲取這個offset的值。

((char )(pos) - (unsigned long)(&((struct person )0)->list))

就是將pos指針往前移動offset位置，即是本來pos是struct list_head類型，它即是list。即是把

pos指針往struct person結構的頭地址位置移動過去，如上圖的pos和虛箭頭。

當pos移到struct person結構頭后就轉 成(struct person *)指針，這樣就可以得到struct person

*變量了。

所以我們再回到前面的句子

點擊(此處)折疊或打開

1.struct person *one = list_entry(pos, struct person, list);

2.//就是由pos得到pos所在的結構的指針，動物就可以這樣：

3.struct animal *one = list_entry(pos, struct animal, list);
下面我們再來看下和struct list_head相關的最后一個宏。
2.3 list_head 的遍歷的宏

點擊(此處)折疊或打開

1./**

1. • list_for_each - iterate over a list
2. • @pos: the &struct list_head to use as a loop counter.
3. • @head: the head for your list.
4. */

6.#define list_for_each(pos, head) ?

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

9./**

1. • list_for_each_safe - iterate over a list safe against removal of list entry
2. • @pos: the &struct list_head to use as a loop counter.
3. • @n: another &struct list_head to use as temporary storage
4. • @head: the head for your list.
5. */

15.#define list_for_each_safe(pos, n, head) ?

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

2.        pos = n, n = pos->next)

list_for_each(pos, head)是遍歷整個head鏈表中的每個元素，每個元素都用pos指向。

list_for_each_safe(pos, n, head)是用于刪除鏈表head中的元素，不是上面有刪除鏈表元素的函數了

嗎，為什么這里又要定義一個這樣的宏呢。看下這個宏后面有個safe字，就是說用這個宏來刪除是安全的，

直接用前面的那些刪除函數是不安全的。這個怎么說呢，我們看下下面這個圖，有三個元素a ，b ，c。

點擊(此處)折疊或打開

1.list_for_each(pos, myhead)

2.{

1.  if (pos == b) 

3.   ｛ 

5.        list_del_init(pos); 

6.        //break; 

7.  } 

9.  。。。 

13.}
上面的算法是不安全的，因為當我們刪除b后，如下圖這樣：

上刪除pos即b后，list_for_each要移到下一個元素，還需要用pos來取得下一個元素，但pos的指向已

經改變，如果不直接退出而是在繼續操作的話，就會出錯了。

而 list_for_each_safe就不一樣了，如果上面的代碼改成這樣：

點擊(此處)折疊或打開

1.struct list_head pos, n;

2.list_for_each_safe(pos, n, myhead)

3.{

1.  if (pos == b) 

3.   ｛ 

5.        list_del_init(pos); 

6.        //break; 

7.  } 

9.  。。。 

14.}

這里我們使用了n作為一個臨時的指針，當pos被刪除后，還可以用n來獲得下一個元素的位置。

說了那么多關于list_head的東西，下面應該總結一下，總結一下第一節想要解決的問題.

三、 總例

我用一個程序來說明在struct person中增加了struct list_head變量后怎么來操作這樣的雙向鏈表。

點擊(此處)折疊或打開

1.#include <stdio.h>

2.#include "list.h"

4.struct person

5.{

1.  int age; 

3.  int weight; 

4.  struct list_head list; 

10.};

12.int main(int argc, char* argv[])

13.{

1.  struct person *tmp; 

2.  struct list_head *pos, *n; 

3.  int age_i, weight_j; 

5.  // 定義并初始化一個鏈表頭 

6.  struct person person_head; 

7.  INIT_LIST_HEAD(&person_head.list); 

9.  for(age_i = 10, weight_j = 35; age_i < 40; age_i += 5, weight_j += 5) 

10.  { 

11.        tmp =(struct person*)malloc(sizeof(struct person)); 

12.        tmp->age = age_i; 

13.        tmp->weight = weight_j; 

15.        // 把這個節點鏈接到鏈表后面 

16.        // 這里因為每次的節點都是加在person_head的后面，所以先加進來的節點就在鏈表里的最 

30.后面

2.        // 打印的時候看到的順序就是先加進來的就在最后面打印 

3.        list_add(&(tmp->list), &(person_head.list)); 

5.  } 

7.  // 下面把這個鏈表中各個節點的值打印出來 

8.  printf("\n"); 

9.  printf("=========== print the list ===============\n"); 

10.  list_for_each(pos, &person_head.list) 

11.  { 

12.        // 這里我們用list_entry來取得pos所在的結構的指針 

13.        tmp = list_entry(pos, struct person, list); 

14.        printf("age:%d, weight: %d \n", tmp->age, tmp->weight); 

15.  } 

16.  printf("\n"); 

18.  // 下面刪除一個節點中，age為20的節點 

19.  printf("========== print list after delete a node which age is 20 

50.==========\n");

1.  list_for_each_safe(pos, n, &person_head.list) 

2.  { 

4.    tmp = list_entry(pos, struct person, list); 

5.          if(tmp->age == 20) 

6.          { 

7.                list_del_init(pos); 

8.                free(tmp); 

9.          } 

11.   } 

13.   list_for_each(pos, &person_head.list) 

14.   { 

15.          tmp = list_entry(pos, struct person, list); 

16.          printf("age:%d, weight: %d \n", tmp->age, tmp->weight); 

17.   } 

19.   // 釋放資源 

20.   list_for_each_safe(pos, n, &person_head.list) 

21.   { 

22.          tmp = list_entry(pos, struct person, list); 

23.          list_del_init(pos); 

24.          free(tmp); 

25.   } 

27.   return 0; 

78.}