這兩個(gè)數(shù)據(jù)結(jié)構(gòu)在內(nèi)核中隨處可見,不得不拿出來(lái)單獨(dú)講講.
這兩個(gè)數(shù)據(jù)結(jié)構(gòu)都是為了方便內(nèi)核開發(fā)者在使用到類似數(shù)據(jù)結(jié)構(gòu)的時(shí)候不必自行開發(fā)(雖然不難),因此它們需要做到足夠的"通用性",也就是說(shuō),今天可以用它們做一個(gè)存放進(jìn)程的鏈表,明天同樣可以做一個(gè)封裝定時(shí)器的鏈表.兩個(gè)數(shù)據(jù)結(jié)構(gòu)的對(duì)外API封裝了針對(duì)它們的基本操作,也是最常見的操作,比如遍歷,查找等等.
一般的,如果我們需要寫一個(gè)鏈表,會(huì)這么寫:
struct node
{
struct node *next;
data_t data;
}
其中的data假設(shè)是鏈表中元素存放的數(shù)據(jù).然后針對(duì)這個(gè)鏈表寫一些相關(guān)操作的API.
假設(shè)下一個(gè)需求,鏈表存放的元素變了,那么我們還需要定義一個(gè)新的數(shù)據(jù)結(jié)構(gòu),寫一些相關(guān)操作的API.
但是,其實(shí)我們需要做的事情都是類似:遍歷一個(gè)鏈表,按照某個(gè)條件定位到其中的一個(gè)元素,等等.有沒有辦法將操作比較特定數(shù)據(jù)的操作交給使用者,而封裝出一套滿足基本鏈表操作的API呢?
C++里面的做法是STL,使用的是范型技術(shù),在運(yùn)行時(shí)才直到容器所要存放的數(shù)據(jù)元素的類型.而通過(guò)C++中的重載,函數(shù)對(duì)象等技術(shù)可以平滑的實(shí)現(xiàn)操作不同數(shù)據(jù)元素.
C中沒有這些技術(shù),用STL的方式恐怕是走不通了.
于是,內(nèi)核采用了另一種方法解決這個(gè)問題.
內(nèi)核中實(shí)現(xiàn)的鏈表數(shù)據(jù)結(jié)構(gòu)是這樣的:
struct list_head {
struct list_head *next, *prev;
};
可見,這個(gè)鏈表中只有分別指向前一個(gè)和后一個(gè)元素的指針,而沒有特定的類型.也就是說(shuō),這個(gè)數(shù)據(jù)類型關(guān)注的僅僅是鏈表本身的東西,與具體的數(shù)據(jù)無(wú)關(guān).
當(dāng)需要使用鏈表的時(shí)候,可以這樣來(lái):
struct node
{
struct list_head link;
data_t data;
}
那么,如何根據(jù)這個(gè)link定位到所需要管理的數(shù)據(jù)呢?
內(nèi)核中定義了這么一個(gè)宏:
#define container_of(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
這個(gè)宏的作用是容器類型type中有一個(gè)名為member的list_head元素,要根據(jù)這個(gè)元素的指針(ptr)得到存放它的type類型的對(duì)象的地址.
一步一步看這個(gè)宏:
1) &
((type *)0)->member)
從C的角度出發(fā), 假設(shè)結(jié)構(gòu)體node中有一個(gè)成員data, 那么對(duì)于一個(gè)指向結(jié)構(gòu)體node的指針p來(lái)說(shuō),p->data與p的地址相差為data這個(gè)域在結(jié)構(gòu)體node中的偏移量.
于是,&
(p->member)就是type類型的指針p中的成員member的地址,而這個(gè)地址是p的地址+member成員在這個(gè)結(jié)構(gòu)體中的偏移,
當(dāng)這個(gè)p變成了0之后,自然就得出了member成員在結(jié)構(gòu)體type中的偏移量.
所以,
&((type *)0)->member)獲得了結(jié)構(gòu)體type中成員member的偏移量.
2)
(char *)(ptr)-(unsigned long)(&((type *)0)->member))
這里ptr是list_head的指針,也就是member成員的指針,因此兩者相減得到了存放member的type結(jié)構(gòu)體的指針.
3)((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
最后在前面加上一個(gè)類型轉(zhuǎn)換,將前面得到的指針轉(zhuǎn)換成type類型.
這就是內(nèi)核中根據(jù)list_head指針得到容納它的容器地址的魔法.
理解了這個(gè),理解內(nèi)核中的鏈表操作也就不再難.
接著看hlist,首先看看內(nèi)核中的定義:
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
這個(gè)數(shù)據(jù)結(jié)構(gòu)與一般的hash-list數(shù)據(jù)結(jié)構(gòu)定義有以下的區(qū)別:
1) 首先,hash的頭節(jié)點(diǎn)僅存放一個(gè)指針,也就是first指針,指向的是list的頭結(jié)點(diǎn),沒有tail指針也就是指向list尾節(jié)點(diǎn)的指針,這樣的考慮是為了節(jié)省空間--尤其在hash bucket很大的情況下可以節(jié)省一半的指針空間.
2) list的節(jié)點(diǎn)有兩個(gè)指針,但是需要注意的是pprev是指針的指針,它指向的是前一個(gè)節(jié)點(diǎn)的next指針(見下圖).
現(xiàn)在疑問來(lái)了:為什么pprev不是prev也就是一個(gè)指針,用于簡(jiǎn)單的指向list的前一個(gè)指針呢?這樣即使對(duì)于first而言,它可以將prev指針指向list的尾結(jié)點(diǎn).
主要是基于以下幾個(gè)考慮:
1) hash-list中的list一般元素不多(如果太多了一般是設(shè)計(jì)出現(xiàn)了問題),即使遍歷也不需要太大的代價(jià),同時(shí)需要得到尾結(jié)點(diǎn)的需求也不多.
2) 如果對(duì)于一般節(jié)點(diǎn)而言,prev指向的是前一個(gè)指針,而對(duì)于first也就是hash的第一個(gè)元素而言prev指向的是list的尾結(jié)點(diǎn),那么在刪除一個(gè)元素的時(shí)候還需要判斷該節(jié)點(diǎn)是不是first節(jié)點(diǎn)進(jìn)行處理.而在hlist提供的刪除節(jié)點(diǎn)的API中,并沒有帶上hlist_head這個(gè)參數(shù),因此做這個(gè)判斷存在難度.
3) 以上兩點(diǎn)說(shuō)明了為什么不使用prev,現(xiàn)在來(lái)說(shuō)明為什么需要的是pprev,也就是一個(gè)指向指針的指針來(lái)保存前一個(gè)節(jié)點(diǎn)的next指針--因?yàn)檫@樣做即使在刪除的節(jié)點(diǎn)是first節(jié)點(diǎn)時(shí)也可以通過(guò)*pprev = next;直接修改指針的指向.來(lái)看刪除一個(gè)節(jié)點(diǎn)和修改list頭結(jié)點(diǎn)的兩個(gè)API:
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
struct hlist_node *first = h->first;
n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
n->pprev = &h->first; //此時(shí)n是hash的first指針,因此它的pprev指向的是hash的first指針的地址
}
static inline void __hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next;
struct hlist_node **pprev = n->pprev;
*pprev = next; // pprev指向的是前一個(gè)節(jié)點(diǎn)的next指針,而當(dāng)該節(jié)點(diǎn)是first節(jié)點(diǎn)時(shí)指向自己,因此兩種情況下不論該節(jié)點(diǎn)是一般的節(jié)點(diǎn)還是頭結(jié)點(diǎn)都可以通過(guò)這個(gè)操作刪除掉所需刪除的節(jié)點(diǎn)
if (next)
next->pprev = pprev;
}
參考資料:
1)http://blog.chinaunix.net/u/12592/showart.php?id=451619
我對(duì)里面的示意圖做了一下修改,主要是將list頭結(jié)點(diǎn)的pprev指針指向hash的first指針地址.這樣看上去更明白一些.
2)http://linux.chinaunix.net/bbs/viewthread.php?tid=1032772