二、特殊的雙向循環鏈表

chyyuu.gitbooks.io

這種雙向循環鏈表在數據結構課程中不常見，我感覺是需要理解一下的。在操作系統中大量應用這種數據結構的原因是：不會因為每種特定數據結構的類型不一致，需要為每種特定數據結構類型定義針對這個數據結構的特定鏈表插入、刪除等各種操作。

來看一下應用：

正常的鏈表節點定義為：

typedef struct node { typename data; struct node* prev; struct node* next;} node;

這裡數據和指針在一起，可是操作系統希望有一個通用的結構，所以變成了這樣：

1.先是頭節點：

typedef struct { list_entry_t free_list;} free_area_t;

2.存放數據的節點：

struct node { atomic_t ref;// ... list_entry_t page_link;};

3.可以看到，把頭節點和數據節點連接起來用的是：list_entry_t，定義如下：

struct list_entry_t { struct list_entry_t *prev, *next;};

這樣就達到了目的。

具體操作如下：

1.初始化：

void list_init(list_entry_t *elm) { elm->prev = elm->next = elm;}list_init(&(free_area.free_list));

2.在節點後面插入一個節點（需要了解結構體的地址和結構體里內容的對應關係）：

可以參考

【不周山之讀薄 CSAPP】貳 機器指令與程序優化的6.2結構體部分和7緩衝區溢出部分介紹

//@listelm: list head to add after//@elm: new entry to be addedvoid list_add_after(list_entry_t* listelm, list_entry_t* elm) { list_add(elm, listelm, listelm->next);}void list_add(list_entry_t* elm, list_entry_t* prev, list_entry_t* next) { prev->next = next->prev = elm; elm->next = next; elm->prev = prev;}

3.在節點前面插入節點，與上述操作類似，略

4.刪除一個節點：

void list_del(list_entry_t *listelm) { _list_del(listelm->prev, listelm->next);}void _list_del(list_entry_t *prev, list_entry_t *next) { prev->next = next; next->prev = prev;}

5.非常重要的操作，訪問鏈表節點所在的宿主數據結構，這裡我基本照搬實驗指導書

雙向循環鏈表 · ucore_os_docs?

chyyuu.gitbooks.io

，因為我的水平不足以說明白。

通過上面的描述可知，list_entry_t通用雙向循環鏈表中僅保存了某特定數據結構中鏈表節點成員變數的地址，那麼如何通過這個鏈表節點成員變數訪問到它的所有者（即某特定數據結構的變數）呢？

Linux為此提供了針對數據結構XXX的le2XXX(le, member)的宏，其中le，即list entry的簡稱，是指向數據結構XXX中list_entry_t成員變數的指針，也就是存儲在雙向循環鏈表中的節點地址值， member則是XXX數據類型中包含的鏈表節點的成員變數。例如，我們要遍歷訪問空閑塊鏈表中所有節點所在的基於Page數據結構的變數，則可以採用如下編程方式（基於lab2/kern/mm/default_pmm.c）：

//free_area是空閑塊管理結構，free_area.free_list是空閑塊鏈表頭free_area_t free_area;list_entry_t * le = &free_area.free_list; //le是空閑塊鏈表頭指針while((le=list_next(le)) != &free_area.free_list) { //從第一個節點開始遍歷 struct Page *p = le2page(le, page_link); //獲取節點所在基於Page數據結構的變數 ……}

le2page宏（定義位於lab2/kern/mm/memlayout.h）的使用相當簡單：

// convert list entry to page#define le2page(le, member) o_struct((le), struct Page, member)

而相比之下，它的實現用到的to_struct宏和offsetof宏（定義位於lab2/libs/defs.h）則有一些難懂：

/* Return the offset of member relative to the beginning of a struct type */#define offsetof(type, member) ((size_t)(&((type *)0)->member))/* * * to_struct - get the struct from a ptr * @ptr: a struct pointer of member * @type: the type of the struct this is embedded in * @member: the name of the member within the struct * */#define to_struct(ptr, type, member) ((type *)((char *)(ptr) - offsetof(type, member)))

這裡採用了一個利用gcc編譯器技術的技巧，即先求得數據結構的成員變數在本宿主數據結構中的偏移量，然後根據成員變數的地址反過來得出屬主數據結構的變數的地址。

我們首先來看offsetof宏，size_t最終定義與CPU體系結構相關，本實驗都採用Intel X86-32 CPU，顧szie_t等價於 unsigned int。 ((type *)0)->member的設計含義是什麼？其實這是為了求得數據結構的成員變數在本宿主數據結構中的偏移量。為了達到這個目標，首先將0地址強制"轉換"為type數據結構（比如struct Page）的指針，再訪問到type數據結構中的member成員（比如page_link）的地址，即是type數據結構中member成員相對於數據結構變數的偏移量。在offsetof宏中，這個member成員的地址（即「&((type *)0)->member)」）實際上就是type數據結構中member成員相對於數據結構變數的偏移量。對於給定一個結構，offsetof(type,member)是一個常量，to_struct宏正是利用這個不變的偏移量來求得鏈表數據項的變數地址。接下來再分析一下to_struct宏，可以發現 to_struct宏中用到的ptr變數是鏈表節點的地址，把它減去offsetof宏所獲得的數據結構內偏移量，即就得到了包含鏈表節點的屬主數據結構的變數的地址。

這就是雙向循環鏈表的介紹。