Linux内核hash链表结构解析

linux 内核里有两种链表类型，双向循环链表和哈希链表，双向循环链表比较常见，不区分头结点和数据结点，而哈希链表区分头结点(hlist_head)和数据结点(hlist_node)。与哈希链表有关的两个数据结构如下：

1
2
3
4
5
6
7


struct hlist_head { 
    struct hlist_node *first;  //指向每一个hash桶的第一个结点的指针
}; 
struct hlist_node { 
    struct hlist_node *next;   //指向下一个结点的指针
    struct hlist_node **pprev; //指向上一个结点的next指针的指针
};

这个结构形如：

list_head-and-hlist_node

其中 hash_table 为散列表（数组），其中的元素类型为struct hlist_head。以hlist_head为链表头的链表，其中的节点hash值是相同的（也叫冲突）。first指针指向链表中的节点①，然后节点①的pprev指针指向hlist_head中的first，节点①的next指针指向节点②。以此类推。

prev 类型是二级指针，将头节点巧妙的变成了一个 dummy node，不需要对头节点做特殊处理，这也是 Linus 所提倡的。¹

 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
29
30
31
32
33
34
35
36
37
38
39
40


static inline void __hlist_del(struct hlist_node *n)
{
	struct hlist_node *next = n->next;
	struct hlist_node **pprev = n->pprev;

	WRITE_ONCE(*pprev, next);
	if (next)
		next->pprev = pprev;
}

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;
}

/* 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;
}

static inline void hlist_add_behind(struct hlist_node *n,
				    struct hlist_node *prev)
{
	n->next = prev->next;
	prev->next = n;
	n->pprev = &prev->next;

	if (n->next)
		n->next->pprev  = &n->next;
}

https://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions ↩︎

Contents