11.5. 鏈表

11.5.?鏈表

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

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

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

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

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

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

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

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