内核数据结构--哈希链表 linux内核及编程

Linux内核中，除了有通用了双向链表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; }

在Linux内核的 hlist_node 结构中不使用通常的 prev 指针，而使用二级指针 pprev，是因为对每一个哈希表的表项来说，它并不组成循环的链表，这样就不能方便地用统一的形式操作。在双向链表中，表头和节点是同一个数据结构，直接用 prev 没有问题。而在 hlist 中，表头没有 prev，也没有 next，只有一个 first。为了能统一地修改表头的 first 指针，即表头的 first 指针必须能够被引用修改，hlist 就设计了 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_del(struct hlist_node *n){ struct hlist_node *next = n->next; struct hlist_node **pprev = n->pprev; *pprev = next; if (next) next->pprev = pprev; }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; }#define hlist_entry(ptr, type, member) container_of(ptr,type,member) #define hlist_for_each(pos, head) \ for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \ pos = pos->next)

【内核数据结构--哈希链表】