前沿

先来直观的比较下普通链表和哈希链表:

普通链表

普通链表的表头和节点相同

1
2
3
struct list_head {  
struct list_head *next, *prev;
};

详情请参考内核数据结构之链表

哈希链表

哈希链表头

1
2
3
struct hlist_head {  
struct hlist_node *first;
};

哈希链表节点

1
2
3
struct hlist_node {  
struct hlist_node *next, **pprev;
};

设计原理

Linux链表设计者认为双指针表头双循环链表对于HASH表来说过于浪费,因而另行设计了一套用于HASH表的hlist数据结构,即单指针表头双循环链表。hlist表头仅有一个指向首节点的指针,而没有指向尾节点的指针,这样在海量的HASH表中存储的表头就能减少一半的空间消耗。

这里还需要注意:struct hlist_node **pprev,也就是说pprev是指向前一个节点(也可以是表头)中next指针的指针。

Q: 为什么不使用struct hlist_node *prev,即让prev指向前一个节点呢?
A: 因为这时候表头(hlist_head)和节点(hlist_node)的数据结构不同。如果使用struct hlist_node *prev,只适用于前一个为节点的情况,而不适用于前一个为表头的情况。如果每次操作都要考虑指针类型转换,会是一件麻烦的事情。所以,我们需要一种统一的操作,而不用考虑前一个元素是节点还是表头。
struct hlist_node **pprev,pprev指向前一个元素的next指针,不用管前一个元素是节点还是表头。当我们需要操作前一个元素(节点或表头),可以统一使用*(node->pprev)来访问和修改前一元素的next(或first)指针。

原理图如下:

常用操作

(1) 初始化

1
2
3
4
5
6
7
8
/*
* Double linked lists with a single pointer list head.
* Mostly useful for hash tables where the two pointer list head is too wasteful.
* You lose the ability to access the tail in O(1).
*/
#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD (name) struct hlist_head name = { .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

(2) 插入

1
2
3
4
5
6
7
8
/* next must be != NULL */  
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;
}

(3) 删除

1
2
3
4
5
6
7
8
static inline void __hlist_del(struct hlist_node *n)  
{
struct hlist_node *next = n->next;
struct hlist_node **prev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
}

(4) 遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *) 0)->MEMBER)  

/*
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*/
#define container_of(ptr, type, member) ({ \
const typeof(((type *) 0)->member) * __mptr = (ptr); \
(type *) ((char *) __mptr - offsetof(type, member)); })

#define hlist_entry(ptr, type, member) container_of(ptr, type, member)

#define hlist_for_each(pos, head) \
for (pos = (head)->first; pos; pos = pos->next)

/**
* hlist_for_each_entry - iterate over list of given type
* @tpos: the type * to use as a loop cursor.
* @pos: the &struct hlist_node to use a loop cursor.
* @head: the head for your list.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry(tpos, pos, head, member) \
for (pos = (head)->first; \
pos && ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = pos->next)

参考资料:

  1. 哈希链表及其变种

  2. Linux内核链表