Linux內(nèi)核中的循環(huán)鏈表結(jié)構(gòu)
注:文章中引用的代碼來源于LXR,所分析的內(nèi)核版本是v2.6.31。
linux內(nèi)核通過定義list_head以及對(duì)于list_head上的一組操作實(shí)現(xiàn)對(duì)不同類型的循環(huán)鏈表的同類操作,這種做法避免了對(duì)于不同數(shù)據(jù)類型的循環(huán)鏈表定義重復(fù)的操作函數(shù),使代碼得到了充分的使用,是一種十分有效的編程方法。
list_head的定義:
19struct list_head {
20struct list_head *next, *prev;
21};
接著我們來看任意一種數(shù)據(jù)結(jié)構(gòu)的循環(huán)鏈表(如圖1),鏈表的每個(gè)節(jié)點(diǎn)中加入了一個(gè)list_head類型的變量,節(jié)點(diǎn)的其他變量任意。(注意:每個(gè)指針?biāo)赶虻奈恢貌皇枪?jié)點(diǎn)數(shù)據(jù)的起始位置,而是list_head類型變量的開始地址。)
通過這樣一種實(shí)現(xiàn)方式建立的鏈表,節(jié)點(diǎn)都是通過list_head類型的變量相連接的,那么我們?nèi)绾斡蒷ist_head類型得指針得到中間某個(gè)節(jié)點(diǎn)類型的指針呢?我們來看這樣一個(gè)操作:list_entry(p,t,m),其中t是鏈表的節(jié)點(diǎn)類型,m是節(jié)點(diǎn)內(nèi)list_head類型的變量名,p是指向該變量的指針,該操作用于從list_head指針得到指向鏈表節(jié)點(diǎn)的指針。
334#define list_entry(ptr, type, member) \
335container_of(ptr, type, member)
650#define container_of(ptr, type, member) ({ \
651const typeof( ((type *)0)->member ) *__mptr = (ptr);\/*_mptr與ptr類型值都相同,是ptr的一個(gè)拷貝*/
652(type *)( (char *)__mptr - offsetof(type,member) );})/*地址減去偏移量(以字節(jié)為單位)即可*/
24#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) /*計(jì)算出變量在結(jié)構(gòu)中的偏移量(以字節(jié)為單位)*/
【編輯推薦】