Linux内核源码中最常见的数据结构之【hlist_head】

1. 定义

在上一篇中，我们详细介绍了list_head，反响很好，我们接下来继续更新hlist_head，hlist_head也是内核源码中使用的非常多的一种数据结构，其定义如下。

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};
1
2
3
4
5
6
7

对比于list_head，hlist_head定义中还伴随一个hlist_node，且pprev采用的是指针的指针类型，它有什么用呢？

hlist实际上是用于hash table即哈希表的hash bucket的实现，相当于用拉链法解决哈希碰撞问题。其设计上采用的非循环双向链表的形式，以hlist_head为表头，hlist_node为链表中的节点。

在hlist_node中，next成员指向下一个hlist_node节点，而pprev则指向前一个hlist_node的next指针

如何访问相邻元素呢，还是要用到上一篇所讲解的container_of，不了解的赶紧去看一看吧

#ifndef offsetof
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif

/**
 * 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) );})
1
2
3
4
5
6
7
8
9
10
11
12
13
14

先假设有一群学生按照班级分类在排队

struct class{
    int num;
	struct hlist_head head;
}

struct student{
    char* name;
    int age;
    int class;
   	struct hlist_node classmates;
};
1
2
3
4
5
6
7
8
9
10
11

已知一个指向某位同学的指针S，获取下一个学生节点可以使用container_of

container_of(S->classmates.next, struct student, classmates)
1

2. 相关方法

1. 初始化hlist_head和hlist_node

#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
	h->next = NULL;
	h->pprev = NULL;
}
1
2
3
4
5
6
7
8

2. 添加节点

/**
 * hlist_add_head - add a new entry at the beginning of the hlist
 * @n: new entry to be added
 * @h: hlist head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
	struct hlist_node *first = h->first;
    //WRITE_ONECE赋值操作，把first值赋给n->next，下方同理
	WRITE_ONCE(n->next, first);
	if (first)
		WRITE_ONCE(first->pprev, &n->next);
	WRITE_ONCE(h->first, n);
	WRITE_ONCE(n->pprev, &h->first);
}

/**
 * hlist_add_before - add a new entry before the one specified
 * @n: new entry to be added
 * @next: hlist node to add it before, which must be non-NULL
 */
static inline void hlist_add_before(struct hlist_node *n,
				    struct hlist_node *next)
{
	WRITE_ONCE(n->pprev, next->pprev);
	WRITE_ONCE(n->next, next);
	WRITE_ONCE(next->pprev, &n->next);
	WRITE_ONCE(*(n->pprev), n);
}

/**
 * hlist_add_behind - add a new entry after the one specified
 * @n: new entry to be added
 * @prev: hlist node to add it after, which must be non-NULL
 */
static inline void hlist_add_behind(struct hlist_node *n,
				    struct hlist_node *prev)
{
	WRITE_ONCE(n->next, prev->next);
	WRITE_ONCE(prev->next, n);
	WRITE_ONCE(n->pprev, &prev->next);

	if (n->next)
		WRITE_ONCE(n->next->pprev, &n->next);
}
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
41
42
43
44
45
46
47
48

3. 删除节点

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)
		WRITE_ONCE(next->pprev, pprev);
}

/**
 * hlist_del - Delete the specified hlist_node from its list
 * @n: Node to delete.
 *
 * Note that this function leaves the node in hashed state.  Use
 * hlist_del_init() or similar instead to unhash @n.
 */
static inline void hlist_del(struct hlist_node *n)
{
	__hlist_del(n);
	n->next = LIST_POISON1;
	n->pprev = LIST_POISON2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4. 遍历节点

#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)

#define hlist_for_each_safe(pos, n, head) \
	for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
	     pos = n)

#define hlist_entry_safe(ptr, type, member) \
	({ typeof(ptr) ____ptr = (ptr); \
	   ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
	})

/**
 * hlist_for_each_entry	- iterate over list of given type
 * @pos:	the type * to use as a loop cursor.
 * @head:	the head for your list.
 * @member:	the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry(pos, head, member)				\
	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
	     pos;							\
	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3. 使用案例

struct hlist_head{
    struct hlist_node *first;
};

struct hlist_node{
    struct hlist_node *next, **pprev;
};

struct class{
    int num;
    struct hlist_head students;
};

struct student{
    char* name;
    int age;
    int class;
    struct hlist_node classmates;
};

void __add_to_class(struct class **classes, struct student *s){
    if(s->class == 1)
    {
        hlist_add_head(&s->classmates, &classes[0]->students);
    }
    else if(s->class == 2)
    {
        hlist_add_head(&s->classmates, &classes[1]->students);
    }
    else printf("error, wrong class num");
}

int main(void)
{
    //所有班级
    struct class *all_classes[2];
    //班级1
    struct class class1 = {1};
    INIT_HLIST_HEAD(&class1.students);
    all_classes[0] = &class1;
    //班级2
    struct class class2 = {2};
    INIT_HLIST_HEAD(&class2.students);
    all_classes[1] = &class2;

    //所有学生
    struct student s1 = {"s1", 10, 1};
    INIT_HLIST_NODE(&s1.classmates);
    struct student s2 = {"s2", 9, 2};
    INIT_HLIST_NODE(&s2.classmates);
    struct student s3 = {"s3", 11, 2};
    INIT_HLIST_NODE(&s3.classmates);
    struct student s4 = {"s4", 10, 1};
    INIT_HLIST_NODE(&s4.classmates);

    //将s1加入到班级1中
    __add_to_class(all_classes, &s1);
    //将s2加入到班级2中
    __add_to_class(all_classes, &s2);
    //将s3加入到班级2中
    __add_to_class(all_classes, &s3);
    //将s4加入到班级1中
    __add_to_class(all_classes, &s4);


    struct student *cursor;
    printf("class1: \n");
    hlist_for_each_entry(cursor, &all_classes[0]->students, classmates){
        printf("%s -> ", cursor->name);
    }
    printf("\n");

    printf("class2: \n");
    hlist_for_each_entry(cursor, &all_classes[1]->students, classmates){
        printf("%s -> ", cursor->name);
    }
    printf("\n");

    //s4离开班级1，加入班级2
    hlist_del(&s4.classmates);
    s4.class = 2;
    __add_to_class(all_classes, &s4);

    printf("class1: \n");
    hlist_for_each_entry(cursor, &all_classes[0]->students, classmates){
        printf("%s -> ", cursor->name);
    }
    printf("\n");

    printf("class2: \n");
    hlist_for_each_entry(cursor, &all_classes[1]->students, classmates){
        printf("%s -> ", cursor->name);
    }
    printf("\n");

    return 0;
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

输出结果：

class1: 
s4 -> s1 -> 
class2:
s3 -> s2 ->
class1:
s1 ->
class2:
s4 -> s3 -> s2 ->
1
2
3
4
5
6
7
8