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