[转]深入理解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{
3.};
那么這個頭文件又是有什么樣的作用呢，這篇文章就是用來解釋它的作用，雖然這是linux下的源代碼，但對
于學習C語言的人來說，這是算法和平臺沒有什么關系。
一、雙向鏈表
學習計算機的人都會開一門課程《數據結構》，里面都會有講解雙向鏈表的內容。
什么是雙向鏈表，它看起來是這樣的：
點擊(此處)折疊或打開
1.struct dlist
2.{
6.};
他的圖形結構圖：
現在有幾個結構體，它們是：
表示人的：
點擊(此處)折疊或打開
1.struct person
2.{
5.};
表示動物的：
點擊(此處)折疊或打開
1.struct animal
2.{
5.};
如果有一組filename變量和filedata變量，把它們存起來，我們會怎么做，當然就用數組了，但我們想使
用雙向鏈表，讓它們鏈接起來，那該怎么做，唯一可以做的就是給每個結構加如兩個成員，如下：
表示人的：
點擊(此處)折疊或打開
1.struct person
2.{
6.};
表示動物的：
點擊(此處)折疊或打開
1.struct animal
2.{
6.};
現在有一個人的一個鏈表的鏈頭指針person_head （循環雙向鏈表）和動物的鏈表的鏈頭指針
ainimal_head ，我們要獲得特定年齡和特定體重的人或動物（假設不考慮重疊），那么代碼看起來可能是這樣：
點擊(此處)折疊或打開
1.struct person * get_percent(int age, int weight)
2.{
3.…....
10.…...
11.}
那同理,要獲得一個特定年齡和重量的動物的函數get_animal(int age, int weight)的代碼也是和上面
的類似。
我們再回過頭來看這兩個結構，它們的指向前和指向后的指針其實都差不多，那把它們綜合起來吧，所以看起
來如下面：
點擊(此處)折疊或打開
1.struct list_head{
3.};
表示人的：
點擊(此處)折疊或打開
1.struct person{
5.};
動物的：
點擊(此處)折疊或打開
1.struct animal
2.{
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 { ?
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./**
- __list_add - Insert a new entry between two known consecutive entries.
- @new:
- @prev:
- @next:
- This is only for internal list manipulation where we know the prev/next
- entries
10.static inline void __list_add(struct list_head * new,
12.{
17.}
18.//這個函數在prev和next間插入一個節點new。
20./**
- list_add - add a new entry
- @new: new entry to be added
- @head: list head to add it after
- Insert a new entry after the specified head.
- This is good for implementing stacks.
點擊(此處)折疊或打開
1.static inline void list_add(struct list_head new, struct list_head head)
2.{
4.}
5.//這個函數在head節點后面插入new節點。
7./**
- list_add_tail - add a new entry
- @new: new entry to be added
- @head: list head to add it before
- Insert a new entry before the specified head.
- This is useful for implementing queues.
15.static inline void list_add_tail(struct list_head new, struct list_head head)
16.{
這個函數和上面的那個函數相反，它在head節點的前面插入new節點。
2.2 從鏈表中刪除節點的函數
點擊(此處)折疊或打開
1./**
- __list_del -
- @prev:
- @next:
- Delete a list entry by making the prev/next entries point to each other.
- This is only for internal list manipulation where we know the prev/next
- entries
11.static inline void __list_del(struct list_head * prev,
13.{
16.}
18./**
- list_del - deletes entry from list.
- @entry: the element to delete from the list.
- Note: list_empty on entry does not return true after this, the entry is in
- an undefined state.
24.static inline void list_del(struct list_head *entry)
25.{
27.}
29./**
- list_del_init - deletes entry from list and reinitialize it.
- @entry: the element to delete from the list.
33.static inline void list_del_init(struct list_head *entry)
34.{
37.}
這里簡單說一下，list_del(struct list_head *entry)是從鏈表中刪除entry節點。
list_del_init(struct list_head *entry) 不但從鏈表中刪除節點，還把這個節點的向前向后指針都指
向自己，即初始化。
那么，我們怎么判斷這個鏈表是不是空的呢！上面我說了，這里的雙向鏈表都是有一個頭節點，而我們上面看到，定義一個頭節點時我們就初始化了，即它的prev和next指針都指向自己。所以這個函數是這樣的。
點擊(此處)折疊或打開
1./**
- list_empty - tests whether a list is empty
- @head: the list to test.
5.static inline int list_empty(struct list_head *head)
6.{
8.}
講了這幾個函數后，這又到了關鍵了，下面講解的一個宏的定義就是對第一節中，我們所要說的為什么在一個
結構中加入struct list_head變量就把這個結構變成了雙向鏈表呢，這其中的關鍵就是怎么通過這個
struct list_head變量來獲取整個結構的變量，下面這個宏就為你解開答案：
點擊(此處)折疊或打開
1./**
- list_entry - get the struct for this entry
- @ptr: the &struct list_head pointer.
- @type: the type of the struct this is embedded in.
- @member: the name of the list_struct within the struct.
7.#define list_entry(ptr, type, member) ?
乍一看下，不知道這個宏在說什么，沒關系，我舉個例子來為你一一解答 ：）
首先，我們還是用上面的結構：
點擊(此處)折疊或打開
1.struct person
2.{
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./**
- list_for_each - iterate over a list
- @pos: the &struct list_head to use as a loop counter.
- @head: the head for your list.
6.#define list_for_each(pos, head) ?
9./**
- list_for_each_safe - iterate over a list safe against removal of list entry
- @pos: the &struct list_head to use as a loop counter.
- @n: another &struct list_head to use as temporary storage
- @head: the head for your list.
15.#define list_for_each_safe(pos, n, head) ?
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.{
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.{
14.}
這里我們使用了n作為一個臨時的指針，當pos被刪除后，還可以用n來獲得下一個元素的位置。
說了那么多關于list_head的東西，下面應該總結一下，總結一下第一節想要解決的問題.
三、 總例
我用一個程序來說明在struct person中增加了struct list_head變量后怎么來操作這樣的雙向鏈表。
點擊(此處)折疊或打開
1.#include <stdio.h>
2.#include "list.h"
4.struct person
5.{
10.};
12.int main(int argc, char* argv[])
13.{
30.后面
50.==========\n");
78.}
轉載于:https://www.cnblogs.com/fastwave2004/p/4940166.html
總結
以上是生活随笔為你收集整理的[转]深入理解linux内核list_head的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： eclipse实现代码块折叠-类似于VS
- 下一篇： JavaSE基础知识（5）—面向对象（O