作者在 2011-04-28 10:20:22 发布以下内容
10 hlist扩展
精益求精的Linux链表设计者（因为list.h没有署名，所以很可能就是Linus Torvalds）认为
双头（next、prev）的双链表对于HASH表来说"过于浪费"，因而另行设计了一套用于HASH表
应用的hlist数据结构--单指针表头双循环链表，从上图可以看出，hlist的表头仅有一个指
向首节点的指针，而没有指向尾节点的指针，这样在可能是海量的HASH表中存储的表头就能
减少一半的空间消耗。
struct hlist_head
{
struct hlist_node *first;
};
struct hlist_node
{
struct hlist_node *next, **pprev;
};
{
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指针(见下图).
现在疑问来了:为什么hlist要使用pprev这样的指向前一个节点的next指针的设计呢？
+--------+ -------
| | ( hlist )
| | -------
+--------+
| | +---+----+ +---+----+ +---+----+
| +---+--->| | | +--+---->| | | +-+--->| | | |
| | | +-+-+-+--+ +-+-+--+-+ +-+-+----+
+--------+ | | | | |
| | | | | | | |
| +---+------+ +----------+ +--------+
| |
+--------+
-----------
( 散列表 )
-----------
主要是基于以下几个考虑:
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;
}
{
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;
}