## 11.5.?鏈表 操作系統內核, 如同其他程序, 常常需要維護數據結構的列表. 有時, 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; /* driver specific */ /* ... add other driver-specific fields */ }; ~~~ 列表的頭常常是一個獨立的 list_head 結構. 圖[鏈表頭數據結構](# "圖?11.1.?鏈表頭數據結構")顯示了這個簡單的 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 章的"讀取-拷貝-更新"一節中描述 ). 這些原語在設備驅動中不可能有用; 看頭文件如果你愿意知道更多信息關于它們是如何工作的.