歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux綜合 >> Linux內核

詳解Linux內核之雙向循環鏈表

1、雙循環鏈表傳統實現:

    在傳統的雙循環鏈表實現中,如果創建某種數據結構的雙循環鏈表,通常采用的辦法是在這個數據結構的類型定義中加入兩個(指向該類型對象的)指針next和prev。例如:

    QUOTE:

     typedef struct foo {

struct foo *prev;

struct foo *next;

} foo_t;


    這裡給出了對應的節點結構、空的雙循環鏈表和非空的雙循環鏈表示意圖。

    2、Linux內核中雙循環鏈表實現

    在linux內核中,有大量的數據結構需要用到雙循環鏈表,例如進程、文件、模塊、頁面等。若采用雙循環鏈表的傳統實現方式,需要為這些數據結構維護各自的鏈表,並且為每個鏈表都要設計插入、刪除等操作函數。因為用來維持鏈表的next和prev指針指向對應類型的對象,因此一種數據結構的鏈表操作函數不能用於操作其它數據結構的鏈表。

    在Linux源代碼樹的include/linux/list.h文件中,采用了一種類型無關的雙循環鏈表實現方式。其思想是將指針prev和next從具體的數據結構中提取出來構成一種通用的"雙鏈表"數據結構list_head。如果需要構造某類對象的特定鏈表,則在其結構(被稱為宿主數據結構)中定義一個類型為list_head類型的成員,通過這個成員將這類對象連接起來,形成所需鏈表,並通過通用鏈表函數對其進行操作。其優點是只需編寫通用鏈表函數,即可構造和操作不同對象的鏈表,而無需為每類對象的每種列表編寫專用函數,實現了代碼的重用。

    list_head結構

    QUOTE:

     -----------struct list_head{}及初始化宏---------

struct list_head

{

struct list_head *next, *prev;

};


    當用此類型定義一個獨立的變量時,其為頭結點;

    當其為某個結構體的一個成員時,其為普通結點。

    盡管形式一樣,但表達的意義不同,是否應該定義為兩個類型list_head和list_node???無法分開,空鏈表時指向了自己

    list_head成員作為"連接件",把宿主數據結構鏈接起來。如下圖所示:

    在Linux內核中的雙循環鏈表實現方式下:

    1. list_head類型的變量作為一個成員嵌入到宿主數據結構內;

    2. 可以將鏈表結構放在宿主結構內的任何地方;

    3. 可以為鏈表結構取任何名字;

    4. 宿主結構可以有多個鏈表結構;

    5. 用list_head中的成員和相對應的處理函數來對鏈表進行遍歷;

    6. 如果想得到宿主結構的指針,使用list_entry可以算出來。

    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 的每個雙循環鏈表都有一個鏈表頭,鏈表頭也是一個節點,只不過它不嵌入到宿主數據結構中,即不能利用鏈表頭定位到對應的宿主結構,但可以由之獲得虛擬的宿主結構指針。

    LIST_HEAD()宏可以同時完成定義鏈表頭,並初始化這個雙循環鏈表為空。

    靜態定義一個list_head 類型變量,該變量一定為頭節點。name為struct list_head{}類型的一個變量,&(name)為該結構體變量的地址。用name結構體變量的始地址將該結構體變量進行初始化。

    QUOTE:

 #define INIT_LIST_HEAD(ptr) do { \

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

} while (0)


    動態初始化一個已經存在的list_head對象,ptr為一個結構體的指針,這樣可以初始化堆棧以及全局區定義的list_head對象。ptr使用時候,當用括號,(ptr),避免ptr為表達式時宏擴展帶來的異常問題。此宏很少用於動態初始化內嵌的list對象,主要是鏈表合並或者刪除後重新初始化頭部。若是在堆中申請了這個鏈表頭,調用INIT_LIST_HEAD()宏初始化鏈表節點,將next和prev指針都指向其自身,我們就構造了一個空的雙循環鏈表。

    2.6內核中內聯函數版本如下:

    QUOTE:

     static inline void INIT_LIST_HEAD(struct list_head *list)

{

list->next = list;

list->prev = list;

}


    此時的參數有明確的類型信息struct list_head,同時可以看出其為指針,list無須象宏中那樣(),即使參數為表達式,其也是求值後再作為參數傳入的。內聯函數有嚴格的參數類型檢查,同時不會出現宏函數擴展帶來的異常問題,但是運行效率和空間效率與宏函數一致

Copyright © Linux教程網 All Rights Reserved