这两个数据结构在内核中随处可见,不得不拿出来单独讲讲.
这两个数据结构都是为了方便内核开发者在使用到类似数据结构的时候不必自行开发(虽然不难),因此它们需要做到足够的"通用性",也就是说,今天可以用它们做一个存放进程的链表,明天同样可以做一个封装定时器的链表.两个数据结构的对外API封装了针对它们的基本操作,也是最常见的操作,比如遍历,查找等等.
一般的,如果我们需要写一个链表,会这么写:
struct node
{
struct node *next;
data_t data;
}
其中的data假设是链表中元素存放的数据.然后针对这个链表写一些相关操作的API.
假设下一个需求,链表存放的元素变了,那么我们还需要定义一个新的数据结构,写一些相关操作的API.
但是,其实我们需要做的事情都是类似:遍历一个链表,按照某个条件定位到其中的一个元素,等等.有没有办法将操作比较特定数据的操作交给使用者,而封装出一套满足基本链表操作的API呢?
C++里面的做法是STL,使用的是范型技术,在运行时才直到容器所要存放的数据元素的类型.而通过C++中的重载,函数对象等技术可以平滑的实现操作不同数据元素.
C中没有这些技术,用STL的方式恐怕是走不通了.
于是,内核采用了另一种方法解决这个问题.
内核中实现的链表数据结构是这样的:
struct list_head {
struct list_head *next, *prev;
};
可见,这个链表中只有分别指向前一个和后一个元素的指针,而没有特定的类型.也就是说,这个数据类型关注的仅仅是链表本身的东西,与具体的数据无关.
当需要使用链表的时候,可以这样来:
struct node
{
struct list_head link;
data_t data;
}
那么,如何根据这个link定位到所需要管理的数据呢?
内核中定义了这么一个宏:
#define container_of(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
这个宏的作用是容器类型type中有一个名为member的list_head元素,要根据这个元素的指针(ptr)得到存放它的type类型的对象的地址.
一步一步看这个宏:
1) &
((type *)0)->member)
从C的角度出发, 假设结构体node中有一个成员data, 那么对于一个指向结构体node的指针p来说,p->data与p的地址相差为data这个域在结构体node中的偏移量.
于是,&
(p->member)就是type类型的指针p中的成员member的地址,而这个地址是p的地址+member成员在这个结构体中的偏移,
当这个p变成了0之后,自然就得出了member成员在结构体type中的偏移量.
所以,
&((type *)0)->member)获得了结构体type中成员member的偏移量.
2)
(char *)(ptr)-(unsigned long)(&((type *)0)->member))
这里ptr是list_head的指针,也就是member成员的指针,因此两者相减得到了存放member的type结构体的指针.
3)((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
最后在前面加上一个类型转换,将前面得到的指针转换成type类型.
这就是内核中根据list_head指针得到容纳它的容器地址的魔法.
理解了这个,理解内核中的链表操作也就不再难.
接着看hlist,首先看看内核中的定义:
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
这个数据结构与一般的hash-list数据结构定义有以下的区别:
1) 首先,hash的头节点仅存放一个指针,也就是first指针,指向的是list的头结点,没有tail指针也就是指向list尾节点的指针,这样的考虑是为了节省空间--尤其在hash bucket很大的情况下可以节省一半的指针空间.
2) list的节点有两个指针,但是需要注意的是pprev是指针的指针,它指向的是前一个节点的next指针(见下图).
现在疑问来了:为什么pprev不是prev也就是一个指针,用于简单的指向list的前一个指针呢?这样即使对于first而言,它可以将prev指针指向list的尾结点.
主要是基于以下几个考虑:
1) hash-list中的list一般元素不多(如果太多了一般是设计出现了问题),即使遍历也不需要太大的代价,同时需要得到尾结点的需求也不多.
2) 如果对于一般节点而言,prev指向的是前一个指针,而对于first也就是hash的第一个元素而言prev指向的是list的尾结点,那么在删除一个元素的时候还需要判断该节点是不是first节点进行处理.而在hlist提供的删除节点的API中,并没有带上hlist_head这个参数,因此做这个判断存在难度.
3) 以上两点说明了为什么不使用prev,现在来说明为什么需要的是pprev,也就是一个指向指针的指针来保存前一个节点的next指针--因为这样做即使在删除的节点是first节点时也可以通过*pprev = next;直接修改指针的指向.来看删除一个节点和修改list头结点的两个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指向的是前一个节点的next指针,而当该节点是first节点时指向自己,因此两种情况下不论该节点是一般的节点还是头结点都可以通过这个操作删除掉所需删除的节点
if (next)
next->pprev = pprev;
}
参考资料:
1)http://blog.chinaunix.net/u/12592/showart.php?id=451619
我对里面的示意图做了一下修改,主要是将list头结点的pprev指针指向hash的first指针地址.这样看上去更明白一些.
2)http://linux.chinaunix.net/bbs/viewthread.php?tid=1032772