本文轉(zhuǎn)載自Linux愛好者

　　原文出處：0xAX

　　譯文出處：伯樂在線

　　譯文鏈接：http://blog.jobbole.com/87687/

　　Linux 內(nèi)核提供一套雙向鏈表的實現(xiàn)，你可以在 include/linux/list.h 中找到。我們以雙向鏈表著手開始介紹 Linux 內(nèi)核中的數(shù)據(jù)結(jié)構(gòu) ，因為這個是在 Linux 內(nèi)核中使用最為廣泛的數(shù)據(jù)結(jié)構(gòu)，具體你可以 查看 這里。

　　首先讓我們看一下主要的結(jié)構(gòu)體：

　　struct list_head {

　　struct list_head *next, *prev;

　　};

　　你可以看到其與常見的結(jié)構(gòu)體實現(xiàn)有顯著不同，比如 glib 中所使用到的雙向鏈表實現(xiàn)。

　　struct GList {

　　gpointer data;

　　GList *next;

　　GList *prev;

　　};

　　通常來說，鏈表結(jié)構(gòu)體要包括一個指向數(shù)據(jù)的指針，不過 Linux 內(nèi)核的鏈表卻不包含此實現(xiàn)。那么首要的疑問：鏈表是用什么方式存儲數(shù)據(jù)的?。Linux 內(nèi)核所實現(xiàn)的是一種被稱為侵入式的鏈表（Intrusive list），這種鏈表并不在鏈表結(jié)構(gòu)中包含數(shù)據(jù)，而僅提供用于維護前向與后向訪問結(jié)構(gòu)的指針。這種實現(xiàn)方式使得鏈表數(shù)據(jù)結(jié)構(gòu)非常通用，因為它并不需要關(guān)注鏈表所維護的具體數(shù)據(jù)類型。

　　比如：

　　struct nmi_desc {

　　spinlock_t lock;

　　struct list_head head;

　　};

　　接下來讓我們看一些內(nèi)核使用 list_head 的具體例子。正如在前文所述的，Linux 內(nèi)核中諸多模塊都使用了 list_head。這里我們以內(nèi)核雜項字符設(shè)備驅(qū)動（miscellaneous character drivers）部分實現(xiàn)為例。驅(qū)動的 API 在 drivers/char/misc.c 中，其實現(xiàn)了簡單硬件外設(shè)以及虛擬設(shè)備的驅(qū)動，這個驅(qū)動共享主設(shè)備號（Major number）：

　　#define MISC_MAJOR 10

　　每個設(shè)備有自己的次設(shè)備號，具體可以看這個列子：

　　現(xiàn)在我們看看設(shè)備驅(qū)動是如何使用鏈表維護設(shè)備列表的，首先，我們看一下 miscdevice 的 struct 定義：

　　struct miscdevice

　　{

　　int minor;

　　const char *name;

　　const struct file_operations *fops;

　　struct list_head list;

　　struct device *parent;

　　struct device *this_device;

　　const char *nodename;

　　mode_t mode;

　　};

　　可以看到 miscdevice 的第四個成員 list ，這個就是用于維護已注冊設(shè)備鏈表的結(jié)構(gòu)。在源代碼文的首部，我們可以看到以下定義：

　　static LIST_HEAD(misc_list);

　　這個定義宏展開，可以看到是用于定義 list_head 類型變量：

　　#define LIST_HEAD(name)

　　struct list_head name = LIST_HEAD_INIT(name)

　　LIST_HEAD_INIT 這個宏用于對定義的變量進行雙向指針的初始化：

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

　　現(xiàn)在我看可以看一下函數(shù) misc_register 是如何進行設(shè)備注冊的。首先是用 INIT_LIST_HEAD 對 miscdevice->list 成員變量進行初始化：

　　INIT_LIST_HEAD(&misc->list);

　　這個操作與 LIST_HEAD_INIT 宏一致：

　　static inline void INIT_LIST_HEAD(struct list_head *list)

　　{

　　list->next = list;

　　list->prev = list;

　　}

　　接下來，在通過函數(shù) device_create 進行設(shè)備創(chuàng)建，同時將設(shè)備添加到 Misc 設(shè)備列表中：

　　list_add(&misc->list, &misc_list);

　　內(nèi)核的 list.h 文件提供向鏈表添加節(jié)點的 API，這里是添加操作的實現(xiàn)：

　　static inline void list_add(struct list_head *new, struct list_head *head)

　　{

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

　　}

　　函數(shù)實現(xiàn)很簡單，就是入?yún)⑥D(zhuǎn)換為三個參數(shù)后調(diào)用內(nèi)部 __list_add ：

new – new entry;

head – list head after which will be inserted new item;

head->next – next item after list head.

　　_list_add 函數(shù)的實現(xiàn)更加簡單：

　　static 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;

　　}

　　這里設(shè)置了新添加結(jié)點的 prev 與 next 指針，通過這些操作，就將先前使用 LIST_HEAD_INIT 所定義的 misc 鏈表的雙向指針與 miscdevice->list 結(jié)構(gòu)關(guān)聯(lián)起來。

　　這里還有一個問題，就是如何獲取鏈表中的數(shù)據(jù)，list_head 提供了一個特殊的宏用于獲取數(shù)據(jù)指針。

　　#define list_entry(ptr, type, member)

　　container_of(ptr, type, member)

　　這里有三個參數(shù)

ptr：list_head 結(jié)構(gòu)指針

type：數(shù)據(jù)對應(yīng)的 struct 類型

member：數(shù)據(jù)中 list_head 成員對應(yīng)的成員變量名

　　舉例如下：

　　const struct miscdevice *p = list_entry(v, struct miscdevice, list)

　　接下來我們就夠訪問 miscdevice 的各個成員，如 p->minor、p->name 等等，我們看一下 list_entry 的實現(xiàn)：

　　#define list_entry(ptr, type, member)

　　container_of(ptr, type, member)

　　其實現(xiàn)非常簡單，就是使用入?yún)⒄{(diào)用 container_of 宏，宏的實現(xiàn)如下：

　　#define container_of(ptr, type, member) ({

　　const typeof( ((type *)0)->member ) *__mptr = (ptr);

　　(type *)( (char *)__mptr - offsetof(type,member) );})

　　注意，宏使用了大括號表達式，對于大括號表達式，編譯器會展開所有表達式，同時使用最后一個表達式的結(jié)果進行返回。

　　舉個例子：

　　#include <stdio.h>

　　int main() {

　　int i = 0;

　　printf("i = %dn", ({++i; ++i;}));

　　return 0;

　　}

　　輸出結(jié)果為 2 。

　　另一個關(guān)鍵是 typeof 關(guān)鍵字，這個非常簡單，這個正如它的名字一樣，這個關(guān)鍵字返回的結(jié)果是變量的類型。當我第一次看到這個宏時，最讓我覺得奇怪的是表達式 ((type*)0) 中的 0 值，實際上，使用 0 值作為地址這個是成員變量取得 struct 內(nèi)相對偏移地址的巧妙實現(xiàn)，我們再來看個例子：

　　#include <stdio.h>

　　struct s {

　　int field1;

　　char field2;

　　char field3;

　　};

　　int main() {

　　printf("%pn", &((struct s*)0)->field3);

　　return 0;

　　}

　　輸出結(jié)果為 0x5 。

　　還有一個專門用于獲取結(jié)構(gòu)體中某個成員變量偏移的宏，其實現(xiàn)與前面提到的宏非常類似：

　　#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

　　這里對 container_of 宏做個綜述，container_of 宏通過 struct 中的 list_head 成員返回 struct 對應(yīng)數(shù)據(jù)的內(nèi)存地址。在宏的第一行定義了指向 list_head 成員的指針 __mptr ，并將 ptr 地址賦給 __mptr 。從技術(shù)實現(xiàn)的角度來看，實際并不需要這一行定義，但這個對于類型檢查而言非常有意義。這一行代碼確保結(jié)構(gòu)體（ type ）中存在 member 對應(yīng)的成員。第二行使用 offsetoff 宏計算出包含 member 的結(jié)構(gòu)體所對應(yīng)的內(nèi)存地址，就是這么簡單。

　　當然 list_add 與 list_entry 并非是 <linux/list.h> 中的全部函數(shù)，對于雙向鏈表 list_head ，內(nèi)核還提供了以下的接口：

list_add

list_add_tail

list_del

list_replace

list_move

list_is_last

list_empty

list_cut_position

list_splice

　　未了，需要說的是，內(nèi)核代碼中并不僅僅只有上述這些接口。