我是靠谱客的博主 动人帆布鞋,这篇文章主要介绍Linux内核数据结构hlist_head,现在分享给大家,希望可以做个参考。

参考自:https://blog.csdn.net/zhanglei4214/article/details/6767288

一、hlist结构简介

hlist_head 和 hlist_node 是位于linux内核中的数据结构,其设计初衷主要是为了减少Hash表的内存消耗。

复制代码
1
2
3
4
5
6
7
struct hlist_head { struct hlist_node *first; }; struct hlist_node { struct hlist_node *next, **pprev; };

其内存结构如下:

 

 

hlist_head 结构体仅仅有一个first指针.

hlist_node 结构体有两个指针,next 和 ppre。其中next指针指向下一个hlist_node,如果该节点为最后一个一个节点,那么next指向NULL。

这样设计的原因在于:通常我们在使用Hash表是为实现快速查找,那么Hash表通常会维护一张相对较大的数组,否则的会带来较大的冲突,而一张较大的数组必然会带来较大的内存消耗。我们知道通常一个Hash表中每一个dentry(每一个具体数元素)会使用两个指针,有其中一个指向尾节点,而我们知道在Hash表中的list通常是非常短(如果过长,说明冲突过多),那么显然这个指向尾节点的指向我们就不那么的必要,Hash表中的每一个denry只用保存一个指针。这样的设计显然会造成链表中节点数据结构不一致,如果hlist_node采用的next和pre指针,那么对于第一个节点和其他节点操作必然会使不一致。hlist_node巧妙地将pprev指向上一个节点的next指针的地址,由于hlist_head和hlist_node指向的下一个节点的指针类型相同,这样就解决了通用性。

二、常用接口

(1)hlist_head 和 hlist_node初始化

复制代码
1
2
3
4
5
6
7
8
#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; }

(2)添加节点

复制代码
1
2
3
4
5
6
7
8
9
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; }

(3)删除节点

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static inline void __hlist_del(struct hlist_node *n) { struct hlist_node *next = n->next; struct hlist_node **pprev = n->pprev; *pprev = next; if (next) next->pprev = pprev; } static inline void hlist_del(struct hlist_node *n) { __hlist_del(n); n->next = LIST_POISON1; n->pprev = LIST_POISON2; }

(4)遍历节点

复制代码
1
2
3
4
#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))

 

转载于:https://www.cnblogs.com/bspp1314/p/9457013.html

最后

以上就是动人帆布鞋最近收集整理的关于Linux内核数据结构hlist_head的全部内容,更多相关Linux内核数据结构hlist_head内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(90)

评论列表共有 0 条评论

立即
投稿
返回
顶部