詳解Linux內(nèi)核之雙向循環(huán)鏈表

1、詳解Linux內(nèi)核之雙向循環(huán)鏈表1、雙循環(huán)鏈表傳統(tǒng)實(shí)現(xiàn)：    在傳統(tǒng)的雙循環(huán)鏈表實(shí)現(xiàn)中，如果創(chuàng)建某種數(shù)據(jù)結(jié)構(gòu)的雙循環(huán)鏈表，通常采用的辦法是在這個(gè)數(shù)據(jù)結(jié)構(gòu)的類型定義中加入兩個(gè)（指向該類型對象的）指針next和prev。例如：    QUOTE:     typedef struct foo struct foo *prev;struct foo *next; foo_t;    這里給出了對應(yīng)的節(jié)點(diǎn)結(jié)構(gòu)、空的雙循環(huán)鏈表和非空的雙循環(huán)鏈表示意圖。  

2、;  2、Linux內(nèi)核中雙循環(huán)鏈表實(shí)現(xiàn)    在linux內(nèi)核中，有大量的數(shù)據(jù)結(jié)構(gòu)需要用到雙循環(huán)鏈表，例如進(jìn)程、文件、模塊、頁面等。若采用雙循環(huán)鏈表的傳統(tǒng)實(shí)現(xiàn)方式，需要為這些數(shù)據(jù)結(jié)構(gòu)維護(hù)各自的鏈表，并且為每個(gè)鏈表都要設(shè)計(jì)插入、刪除等操作函數(shù)。因?yàn)橛脕砭S持鏈表的next和prev指針指向?qū)?yīng)類型的對象，因此一種數(shù)據(jù)結(jié)構(gòu)的鏈表操作函數(shù)不能用于操作其它數(shù)據(jù)結(jié)構(gòu)的鏈表。    在Linux源代碼樹的include/linux/list.h文件中，采用了一種類型無關(guān)的雙循環(huán)鏈表實(shí)現(xiàn)方式。其思想是將指針prev和next從具體的數(shù)據(jù)結(jié)

3、構(gòu)中提取出來構(gòu)成一種通用的"雙鏈表"數(shù)據(jù)結(jié)構(gòu)list_head。如果需要構(gòu)造某類對象的特定鏈表，則在其結(jié)構(gòu)（被稱為宿主數(shù)據(jù)結(jié)構(gòu)）中定義一個(gè)類型為list_head類型的成員，通過這個(gè)成員將這類對象連接起來，形成所需鏈表，并通過通用鏈表函數(shù)對其進(jìn)行操作。其優(yōu)點(diǎn)是只需編寫通用鏈表函數(shù)，即可構(gòu)造和操作不同對象的鏈表，而無需為每類對象的每種列表編寫專用函數(shù)，實(shí)現(xiàn)了代碼的重用。    list_head結(jié)構(gòu)    QUOTE:     -struct list_head及初始化宏-st

4、ruct list_headstruct list_head *next, *prev;    當(dāng)用此類型定義一個(gè)獨(dú)立的變量時(shí)，其為頭結(jié)點(diǎn)；    當(dāng)其為某個(gè)結(jié)構(gòu)體的一個(gè)成員時(shí)，其為普通結(jié)點(diǎn)。    盡管形式一樣，但表達(dá)的意義不同，是否應(yīng)該定義為兩個(gè)類型list_head和list_node？無法分開，空鏈表時(shí)指向了自己    list_head成員作為"連接件"，把宿主數(shù)據(jù)結(jié)構(gòu)鏈接起來。如下圖所示：    在Linux內(nèi)核中

5、的雙循環(huán)鏈表實(shí)現(xiàn)方式下：    1. list_head類型的變量作為一個(gè)成員嵌入到宿主數(shù)據(jù)結(jié)構(gòu)內(nèi)；    2. 可以將鏈表結(jié)構(gòu)放在宿主結(jié)構(gòu)內(nèi)的任何地方；    3. 可以為鏈表結(jié)構(gòu)取任何名字；    4. 宿主結(jié)構(gòu)可以有多個(gè)鏈表結(jié)構(gòu)；    5. 用list_head中的成員和相對應(yīng)的處理函數(shù)來對鏈表進(jìn)行遍歷；    6. 如果想得到宿主結(jié)構(gòu)的指針，使用list_entry可以算出來。  

6、60; 3、定義和初始化    QUOTE:     -LIST_HEAD_INIT()-LIST_HEAD()-INIT_LIST_HEAD()-#define LIST_HEAD_INIT(name) &(name), &(name) #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)    需要注意的是，Linux 的每個(gè)雙循環(huán)鏈表都有一個(gè)鏈表頭，鏈表頭也是一個(gè)節(jié)點(diǎn)，只不過它不嵌入到宿主數(shù)

7、據(jù)結(jié)構(gòu)中，即不能利用鏈表頭定位到對應(yīng)的宿主結(jié)構(gòu)，但可以由之獲得虛擬的宿主結(jié)構(gòu)指針。    LIST_HEAD()宏可以同時(shí)完成定義鏈表頭，并初始化這個(gè)雙循環(huán)鏈表為空。    靜態(tài)定義一個(gè)list_head 類型變量，該變量一定為頭節(jié)點(diǎn)。name為struct list_head類型的一個(gè)變量，&(name)為該結(jié)構(gòu)體變量的地址。用name結(jié)構(gòu)體變量的始地址將該結(jié)構(gòu)體變量進(jìn)行初始化。    QUOTE: #define INIT_LIST_HEAD(ptr) do (ptr)->ne

8、xt = (ptr); (ptr)->prev = (ptr); while (0)    動態(tài)初始化一個(gè)已經(jīng)存在的list_head對象，ptr為一個(gè)結(jié)構(gòu)體的指針，這樣可以初始化堆棧以及全局區(qū)定義的list_head對象。ptr使用時(shí)候，當(dāng)用括號，(ptr)，避免ptr為表達(dá)式時(shí)宏擴(kuò)展帶來的異常問題。此宏很少用于動態(tài)初始化內(nèi)嵌的list對象，主要是鏈表合并或者刪除后重新初始化頭部。若是在堆中申請了這個(gè)鏈表頭，調(diào)用INIT_LIST_HEAD()宏初始化鏈表節(jié)點(diǎn)，將next和prev指針都指向其自身，我們就構(gòu)造了一個(gè)空的雙循環(huán)鏈表。    2.6內(nèi)核中內(nèi)聯(lián)函數(shù)版本如下：    QUOTE:     static inline void INIT_LIST_HEAD(struct list_head *list)list->next = list;list->prev = list;  &#