操作系統內核, 如同其他程序, 常常需要維護數據結構的列表. 有時, Linux 內核已經同時有幾個列表實現. 為減少復制代碼的數量, 內核開發者已經創建了一個標准環形的, 雙鏈表; 鼓勵需要操作列表的人使用這個設施.
當使用鏈表接口時, 你應當一直記住列表函數不做加鎖. 如果你的驅動可能試圖對同一個列表並發操作, 你有責任實現一個加鎖方案. 可選項( 破壞的列表結構, 數據丟失, 內核崩潰) 肯定是難以診斷的.
為使用列表機制, 你的驅動必須包含文件 <linux/list.h>. 這個文件定義了一個簡單的類型 list_head 結構:
struct list_head { struct list_head *next, *prev; };
真實代碼中使用的鏈表幾乎是不變地由幾個結構類型組成, 每一個描述一個鏈表中的入口項. 為在你的代碼中使用 Linux 列表, 你只需要嵌入一個 list_head 在構成這個鏈表的結構裡面. 假設, 如果你的驅動維護一個列表, 它的聲明可能看起來象這樣:
struct todo_struct
{
struct list_head list;
int priority;
};
列表的頭常常是一個獨立的 list_head 結構. 圖鏈表頭數據結構顯示了這個簡單的 struct list_head 是如何用來維護一個數據結構的列表的.
圖 11.1. 鏈表頭數據結構
鏈表頭數據結構
鏈表頭必須在使用前用 INIT_LIST_HEAD 宏來初始化. 一個"要做的事情"的鏈表頭可能聲明並且初始化用:
struct list_head todo_list;
INIT_LIST_HEAD(&todo_list);
<para>可選地, 鏈表可在編譯時初始化:</para>
LIST_HEAD(todo_list);
幾個使用鏈表的函數定義在 <linux/list.h>:
list_add(struct list_head *new, struct list_head *head);
在緊接著鏈表 head 後面增加新入口項 -- 正常地在鏈表的開頭. 因此, 它可用來構建堆棧. 但是, 注意, head 不需要是鏈表名義上的頭; 如果你傳遞一個 list_head 結構, 它在鏈表某處的中間, 新的項緊靠在它後面. 因為 Linux 鏈表是環形的, 鏈表的頭通常和任何其他的項沒有區別.
list_add_tail(struct list_head *new, struct list_head *head);
剛好在給定鏈表頭前面增加一個新入口項 -- 在鏈表的尾部, 換句話說. list_add_tail 能夠, 因此, 用來構建先入先出隊列.
list_del(struct list_head *entry);
list_del_init(struct list_head *entry);
給定的項從隊列中去除. 如果入口項可能注冊在另外的鏈表中, 你應當使用 list_del_init, 它重新初始化這個鏈表指針.
list_move(struct list_head *entry, struct list_head *head);
list_move_tail(struct list_head *entry, struct list_head *head);
給定的入口項從它當前的鏈表裡去除並且增加到 head 的開始. 為安放入口項在新鏈表的末尾, 使用 list_move_tail 代替.
list_empty(struct list_head *head);
如果給定鏈表是空, 返回一個非零值.
list_splice(struct list_head *list, struct list_head *head);
將 list 緊接在 head 之後來連接 2 個鏈表.
list_head 結構對於實現一個相似結構的鏈表是好的, 但是調用程序常常感興趣更大的結構, 它組成鏈表作為一個整體. 一個宏定義, list_entry, 映射一個 list_head 結構指針到一個指向包含它的結構的指針. 它如下被調用:
list_entry(struct list_head *ptr, type_of_struct, field_name);
這裡 ptr 是一個指向使用的 struct list_head 的指針, type_of_struct 是包含 ptr 的結構的類型, field_name 是結構中列表成員的名子. 在我們之前的 todo_struct 結構中, 鏈表成員稱為簡單列表. 因此, 我們應當轉變一個列表入口項為它的包含結構, 使用這樣一行:
struct todo_struct *todo_ptr = list_entry(listptr, struct todo_struct, list);
list_entry 宏定義使用了一些習慣的東西但是不難用.
鏈表的遍歷是容易的: 只要跟隨 prev 和 next 指針. 作為一個例子, 假設我們想保持 todo_struct 項的列表已降序的優先級順序排列. 一個函數來添加新項應當看來如此:
void todo_add_entry(struct todo_struct *new)
{
struct list_head *ptr;
struct todo_struct *entry;
for (ptr = todo_list.next; ptr != &todo_list; ptr = ptr->next)
{
entry = list_entry(ptr, struct todo_struct, list);
if (entry->priority < new->priority) {
list_add_tail(&new->list, ptr);
return;
}
}
list_add_tail(&new->list, &todo_struct)
}
但是, 作為一個通用的規則, 最好使用一個預定義的宏來創建循環, 它遍歷鏈表. 前一個循環, 例如, 可這樣編碼:
void todo_add_entry(struct todo_struct *new)
{
struct list_head *ptr;
struct todo_struct *entry;
list_for_each(ptr, &todo_list)
{
entry = list_entry(ptr, struct todo_struct, list);
if (entry->priority < new->priority) {
list_add_tail(&new->list, ptr);
return;
}
}
list_add_tail(&new->list, &todo_struct)
}
使用提供的宏幫助避免簡單的編程錯誤; 宏的開發者也已做了些努力來保證它們進行正常. 存在幾個變體:
list_for_each(struct list_head *cursor, struct list_head *list)
這個宏創建一個 for 循環, 執行一次, cursor 指向鏈表中的每個連續的入口項. 小心改變列表在遍歷它時.
list_for_each_prev(struct list_head *cursor, struct list_head *list)
這個版本後向遍歷鏈表.
list_for_each_safe(struct list_head *cursor, struct list_head *next, struct list_head *list)
如果你的循環可能刪除列表中的項, 使用這個版本. 它簡單的存儲列表 next 中下一個項, 在循環的開始, 因此如果 cursor 指向的入口項被刪除, 它不會被搞亂.
list_for_each_entry(type *cursor, struct list_head *list, member)
list_for_each_entry_safe(type *cursor, type *next, struct list_head *list, member)
這些宏定義減輕了對一個包含給定結構類型的列表的處理. 這裡, cursor 是一個指向包含數據類型的指針, member 是包含結構中 list_head 結構的名子. 有了這些宏, 沒有必要安放 list_entry 調用在循環裡了.
如果你查看 <linux/list.h> 裡面, 你看到有一些附加的聲明. hlist 類型是一個有一個單獨的, 單指針列表頭類型的雙向鏈表; 它常用作創建哈希表和類型結構. 還有宏用來遍歷 2 種列表類型, 打算作使用 讀取-拷貝-更新 機制(在第 5 章的"讀取-拷貝-更新"一節中描述 ). 這些原語在設備驅動中不可能有用; 看頭文件如果你願意知道更多信息關於它們是如何工作的。
