11.5. 鏈表

11.5.?鏈表

操作系統內核, 如同其他程序, 常常需要維護數據結構的列表. 有時, Linux 內核已經同時有幾個列表實現. 為減少復制代碼的數量, 內核開發(fā)者已經創(chuàng)建了一個標準環(huán)形的, 雙鏈表; 鼓勵需要操作列表的人使用這個設施.

當使用鏈表接口時, 你應當一直記住列表函數不做加鎖. 如果你的驅動可能試圖對同一個列表并發(fā)操作, 你有責任實現一個加鎖方案. 可選項( 破壞的列表結構, 數據丟失, 內核崩潰) 肯定是難以診斷的.

為使用列表機制, 你的驅動必須包含文件 <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 結構. 圖鏈表頭數據結構顯示了這個簡單的 struct list_head 是如何用來維護一個數據結構的列表的.

圖?11.1.?鏈表頭數據結構