11.5. 鏈表

11.5.?鏈表

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

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

為使用列表機制, 你的驅(qū)動必須包含文件 <linux/list.h>. 這個文件定義了一個簡單的類型 list_head 結(jié)構(gòu):

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

真實代碼中使用的鏈表幾乎是不變地由幾個結(jié)構(gòu)類型組成, 每一個描述一個鏈表中的入口項. 為在你的代碼中使用 Linux 列表, 你只需要嵌入一個 list_head 在構(gòu)成這個鏈表的結(jié)構(gòu)里面. 假設(shè), 如果你的驅(qū)動維護一個列表, 它的聲明可能看起來象這樣:

struct todo_struct
{
        struct list_head list;
        int priority; /* driver specific */
        /* ... add other driver-specific fields */
};

列表的頭常常是一個獨立的 list_head 結(jié)構(gòu). 圖鏈表頭數(shù)據(jù)結(jié)構(gòu)顯示了這個簡單的 struct list_head 是如何用來維護一個數(shù)據(jù)結(jié)構(gòu)的列表的.

圖?11.1.?鏈表頭數(shù)據(jù)結(jié)構(gòu)