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;
};
对比于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) );})
先假设有一群学生按照班级分类在排队
struct class{
int num;
struct hlist_head head;
}
struct student{
char* name;
int age;
int class;
struct hlist_node classmates;
};
已知一个指向某位同学的指针S，获取下一个学生节点可以使用container_of
container_of(S->classmates.next, struct student, classmates)
2. 相关方法
- 初始化
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;
}
- 添加节点
/**
* 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);
}
- 删除节点
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;
}
- 遍历节点
#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))
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;
}
输出结果：
class1:
s4 -> s1 ->
class2:
s3 -> s2 ->
class1:
s1 ->
class2:
s4 -> s3 -> s2 ->