環狀雙向鏈結串列 (Doubly Linked List)
Linux核心維護了許多重要的資料結構，大部份的資料結構是由鏈結串列所組成。有鑑於此，從
有關於此串列的程式與相關資訊都存放在
在list.h中，定義一個list_head的結構，此結構包含了兩個指標用以指向後一個節點與前一個節點：
struct list_head {
struct list_head *next, *prev;
};
當有一資料結構須要使用串列時，只須在該資料結構中加入一個型別為list_head的欄位。如下例，藉由list_head將所有的結點串接起來：
struct num {
int number;
//加入下面欄位
struct list_head list;
};
在使用list_head時須注意到串列的起始必須由一個獨立的list_head開始，如上圖所示。其原因是因為核心所提供的串列處理函數均假設一個串列的起始是由一個獨立的list_head開始，在後面的程式碼分析中可以觀察出此結果。
下面的表格是用以操作串列的相關函式：
LIST_HEAD(name)
串列的初始化巨集，使用此巨集後會得到一個名稱為name的串列。
INIT_LIST_HEAD(ptr)
將ptr所指的串列初始化。
list_add(struct list_head *new, struct list_head *head)
此函式會將新結點(new)串到head之後。
list_add_tail(struct list_head *new, struct list_head *head)
此函式則是將新結點(new)插到head之前。
list_del(struct list_head *entry)
將entry從其所屬串列中移出。
list_del_init(struct list_head *entry)
此函式除了將entry從其所屬串列中移出，還會將移出的entry從新初始化。
list_empty(struct list_head *head)
檢查此串列是不是空的。pos
list_splice(struct list_head *list, struct list_head *head)
將兩串列串接在一起。此函式會將list所指的串列接到head之後。
poslist_entry(ptr, type, member)
取出ptr所指的結點。此函式會回傳一結點指標，此結點包含ptr所指到的list_head。
list_for_each(pos, head)
走訪head所指到的串列，pos則會指向每一次走訪的結點。
list_for_each_prev(pos, head)
與上一個函式相同，不過走訪順序是相反的。
list_for_each_safe(pos, n, head)pos
下面的程式碼示範了串列的使用：
struct num {
struct list_head node;
int number;
};
int main()
{
LIST_HEAD(head);
struct num *tmp;
struct list_head *iterator;
int i;
for (i=0 ; i<5 ; i++) {
tmp = malloc(sizeof(struct num));
tmp->number = i;
list_add(&tmp->node, &head);
}pos
list_for_each(iterator, &head) {
printf("%dn", list_entry(iterator, struct num, node)->number);
}
}
下圖為執行後輸出的結果：
程式碼分析
待續 ...
留言列表
