Linux内核哈希链表结构（linux内核链表实现）

Linux内核哈希链表结构（linux内核链表实现）

Linux内核哈希链表结构

哈希链表（Hash List）是指在对需要存储的数据进行hash时，如果产生了冲突，就使用链表的方式将产生冲突的数据进行存储。通常情况下，哈希表中元素的使用顺序是：数据存储-->数据获取-->数据删除。

我们使用哈希表的目的是为了快速获取表中的数据，关注的是其效率。哈希链表中，节点的插入操作都是插在链表头的位置，因为这样插入非常快！而且，一般不使用循环链表，因为哈希链表中的链表中存储的元素不会太多(如果太多证明hash函数有问题)，遍历一遍不会花费太多时间，而且也不怎么需要直接获取尾节点。

哈希链表结构

Linux内核链表使用struct hlist_head数据结构来描述哈希表，使用struct hlist_node数据结构来描述链表结构。代码位于include/linux/types.h文件中。

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

pprev二级指针存在的意义是因为效率。向链表中添加节点时可以直接添加到头部，但是当删除节点时，不但要记录即将删除节点的前一个节点，还需要判断删除的节点是否是头结点。如果使用pprev指针，那么在删除节点时直接使用*(del_node->pprev) = del_node->next即可。

哈希链表初始化

哈希链表初始化分为初始化hlist_head的节点和初始化hlist_node节点。

/* * 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) static inline void INIT_HLIST_NODE(struct hlist_node *h) { h->next = NULL; h->pprev = NULL; }

添加节点

添加节点函数有三个，分别是添加到指定哈希链表头上hlist_add_head()、添加到指定节点前面hlist_add_before()、添加到指定节点后面hlist_add_behind()。

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

删除节点

删除节点函数有两个，分别是删除节点hlist_del()、删除节点并初始化已删除的节点hlist_del_init()。

static inline void hlist_del(struct hlist_node *n) { __hlist_del(n); n->next = LIST_POISON1; n->pprev = LIST_POISON2; } 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_del_init(struct hlist_node *n) { if (!hlist_unhashed(n)) { __hlist_del(n); INIT_HLIST_NODE(n); } }

移动节点

将哈希链表从一个移动到另外一个。

/* * Move a list from one list head to another. Fixup the pprev * reference of the first entry if it exists. */ static inline void hlist_move_list(struct hlist_head *old, struct hlist_head *new) { new->first = old->first; if (new->first) new->first->pprev = &new->first; old->first = NULL; }

遍历哈希链表

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

这个宏只是遍历一个一个节点的当前位置，那么如何获取节点本身的数据结构呢？这里还需要使用hlist_entry()宏。

#define hlist_entry(ptr, type, member) container_of(ptr,type,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 offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

其中offsetof()宏是通过把0地址转换为type类型的指针，然后去获取该结构体中member成员的指针，也就是获取了member在type结构体中的偏移量。最后用指针ptr减去offset，就得到type结构体的真实地址了。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。