hlist原本是定义在内核list.h里面的结构体，主要用在解决哈希表冲突时使用链接(chaining)方法时候用到的结构体。结构体定义简单、相关的接口也比较丰富，可以直接拿到用户层使用。最常见的一种使用场景如下图：
htable是hash数组，每个数组元素是一个hlist_head结构体。当多个结点的hash key值相同时，直接添加在对应的结点链表里就可以了。下面介绍相关数据结构和操作接口使用。
链表头和结点的结构体定义：
复制代码
1
2
3
4
5
6
7
8
9/* 链表头 */ struct hlist_head { struct hlist_node *first; }; /* 链表结点，具体的数据结构体只需要包含这个结构体就可以了 */ struct hlist_node { struct hlist_node *next, **pprev; };
链表头和结点使用前需要初始化：
复制代码
1
2
3
4
5
6
7
8
9
10
11//hlist_head 初始化 #define HLIST_HEAD_INIT { .first = NULL } //静态初始化 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) //动态初始化 //hlist_node 初始化 static inline void INIT_HLIST_NODE(struct hlist_node *h) { h->next = NULL; h->pprev = NULL; }
常用接口包括添加、删除和修改：
复制代码
1
2//添加结点至链表首部 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)；
复制代码
1
2//删除前有判断 static inline void hlist_del_init(struct hlist_node *n)；
复制代码
1
2//判断链表头是否为空，是的话返回1 static inline int hlist_empty(const struct hlist_head *h)；
复制代码
1
2
3
4
5//遍历结点 hlist_for_each(pos, head) //遍历结点过程中有删除结点操作使用这个接口 hlist_for_each_safe(pos, n, head)
复制代码
1
2
3
4//遍历获取结点里的数据 hlist_for_each_entry(tpos, pos, head, member)
复制代码
1//遍历结点过程中有删除结点操作使用这个接口
复制代码
1hlist_for_each_entry_safe(tpos, pos, n, head, member)
假设结点结构体定义如下;
复制代码
1
2
3
4
5//结点结构体 struct hdata_node { unsigned int data; struct hlist_node list; };
下面是一个小李子，采用除法散列法计算hash值，结点定义如上，包含添加、删除和查询操作。
复制代码
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115/* * Description : linux应用层编程之哈希链表hlist的使用 * Date ：20180713 * Author ：fuyuande * Mail : mrsonko@126.com * */ #include <stddef.h> #include <stdio.h> #include <string.h> #include <unistd.h> #include <stdlib.h> #include "hlistdemo.h" #define log(fmt, arg...) printf(""fmt,##arg) #define MAX_ADDR 256 void main(int argc, char **argv){ struct hlist_head htable[MAX_ADDR]; //hash数组 struct hdata_node *hnode = NULL; struct hlist_node *hlist = NULL, *n = NULL; int i = 0, quit = 1, opt = 0, key; unsigned int data; /* hlist_head 动态初始化 */ for(i = 0; i < MAX_ADDR; i++) //hash数组动态初始化 INIT_HLIST_HEAD(&htable[i]); log("*********************nn" "input options:n" "1: insertn" //插入 "2: serachn" //查询 "3: deleten" //删除 "0: quitn" "n*********************n"); while(quit != 0){ log("ninput options:"); scanf("%d", &opt); switch(opt){ //插入 case 1: //分配结点 hnode = calloc(1, sizeof(struct hdata_node)); if(!hnode){ log("insert fail n"); break; } //hlist_node 结点初始化 INIT_HLIST_NODE(&hnode->list); log("ninput data:"); scanf("%d", &hnode->data); key = hnode->data % MAX_ADDR; //添加到链表首部 hlist_add_head(&hnode->list, &htable[key]); break; //查询 case 2: log("ninput data:"); scanf("%d", &data); key = data % MAX_ADDR; if(hlist_empty(&htable[key])) log("data not exist n"); else{ //遍历对应的槽位，匹配值就打印 hlist_for_each_entry(hnode, hlist, &htable[key], list){ if(hnode->data == data) log("find data : %u n", hnode->data); } } break; //删除 case 3: log("ninput data:"); scanf("%d", &data); key = data % MAX_ADDR; if(hlist_empty(&htable[key])) log("data not exist ，delete fail n"); else{ //遍历对应的槽，匹配值就删除 hlist_for_each_entry_safe(hnode, hlist, n, &htable[key], list){ if(hnode->data == data){ hlist_del(&hnode->list); break; } } } log("delete failn"); break; case 0: quit = 0; break; default: log("unrecognized option!"); break; } } //退出程序前释放资源 for(i=0; i < MAX_ADDR; i++){ //遍历每一个槽，有结点就删除 hlist_for_each_entry_safe(hnode, hlist, n, &htable[i], list){ hlist_del(&hnode->list); log("delete %u n", hnode->data); free(hnode); hnode = NULL; } } log("exitn"); }
代码放在：git@github.com:FuYuanDe/hlist_demo.git
git clone之后直接make运行。
またね！
最后
以上就是洁净学姐最近收集整理的关于Linux环境编程 哈希链表结构 hlist 介绍与用例的全部内容，更多相关Linux环境编程内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复