list链表与hlist哈希链表

rayter

在include/Linux/list.h中有list链表与hlist哈希链表结构的定义，下面都列出它们的定义，可以对比一下：
struct list_head {
     struct list_head *next, *prev;
};
struct hlist_head {
     struct hlist_node *first;
};
struct hlist_node {
     struct hlist_node *next, **pprev;
};

双头（next，prev）的双链表对于Hash表来说“过于浪费”，因而另行设计了一套Hash表专用的hlist数据结构——单指针表头双循环链表，hlist的表头仅有一个指向首节点的指针，而没有指向尾节点的指针，这样在可能是海量的Hash表中存储的表头就能减少一半的空间消耗。
pprev因为hlist不是一个完整的循环链表而不得不使用。在list中，表头和节点是同一个数据结构，直接用prev没问题；在hlist中，表头没有prev，也没有next，只有一个first。为了能统一地修改表头的first指针，即表头的first指针必须修改指向新插入的节点，hlist就设计了pprev。hlist节点的pprev不再是指向前一个节点的指针，而是指向前一个节点（可能是表头）中的next（对于表头则是first）指针（struct list_head **pprev），从而在表头插入的操作可以通过一致的“*(node->pprev)”访问和修改前节点的next（或first）指针。
下面是hlist中常用的几个宏：
#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
下面只列出hlist_add_before操作函数，其他hlist链表操作函数操作方法类似。这个函数中的参数next不能为空。它在next前面加入了n节点。函数的实现与list中对应函数类似。
static inline void hlist_add_before(struct hlist_node *n,
                       struct hlist_node *next)
{
     n->pprev = next->pprev;
     n->next = next;
     next->pprev = &n->next;
     *(n->pprev) = n;
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/13229/showart_327790.html