explorer

万丈高楼平地起,勿在浮沙筑高台

0%

[What]linux -> list

kernel version arch
v5.4.x lts arm32

罗列内核已经提供的双向链表数据结构的使用方式。

linux 在 include/linux/list.h 中提供了 双向环形链表双向链表 的操作函数, 此代码可以移植到其他应用环境中,方便使用。

  • 在内核编程环境中,需要 #include 来包含该头文件

需要注意的是:

  1. linux是通过 将此链表嵌入在其他数据结构中, 从而将很多不同的数据结构链接起来!. (而不是链表中包含数据).
  2. 函数中的参数 head 代表的即为链表头!
  3. typeof 是GCC扩展的关键字, 所以不能在编译选项中添加 -std=c99 ,而是使用 -std=gnu99 .
    • 为了兼容所有编译器,我在github中移植了通用版本。

使用双向环形链表

双向环形链表概览

内核提供了以下宏供操作:

  • LIST_HEAD(name) : 定义并初始化一个名称为 name 的双向环形链表。
    • 默认链表的 next 和 prev 指向自己
  • list_entry(ptr, type, member) : 通过链表节点地址 ptr , 来反推处包含它的 type 类型数据的起始地址, member 就是该链表节点在 type 中定义的名称
  • list_first_entry(ptr, type, member): 反推节点 ptr 的下一个节点被包含的 type 类型数据的起始地址, 当 ptr为头指针时, 返回的就是第一个对象.
  • list_last_entry(ptr, type, member): 反推节点 ptr 的上一个节点被包含的 type 类型数据的起始地址, 当 ptr 为头指针时, 返回的就是最后一个对象.
  • list_first_entry_or_null(ptr, type, member): 反推节点 ptr 的下一个节点被包含的 type 类型数据的起始地址, 如果没有则返回 NULL
  • list_next_entry(pos, member): 得到与 pos 相连的下一个数据结构的地址
  • list_prev_entry(pos, member): 得到与 pos 相连的上一个数据结构的地址
  • list_for_each(pos, head) : 向下遍历 poshead 节点, 此宏为一个for语句
  • list_for_each_prev(pos, head) : 向上遍历 poshead 节点, 此宏为一个for语句
  • list_for_each_safe(pos, n, head) : 向下遍历 poshead 节点, 此宏为一个for语句
    • 当遍历到一个节点,然后需要删除它式,需要使用此宏
  • list_for_each_prev_safe(pos, n, head) : 向上遍历 poshead 节点, 此宏为一个for语句
  • list_for_each_entry(pos, head, member): 通过节点, 向下数据结构遍历
  • list_for_each_entry_reverse(pos, head, member): 通过节点,向上数据结构遍历
  • list_prepare_entry(pos, head, member) : 准备一个节点作为起始遍历,用于 list_for_each_entry_continue
  • list_for_each_entry_continue(pos, head, member): 通过数据结构,向下遍历数据结构
  • list_for_each_entry_continue_reverse(pos, head, member): 通过数据结构,向上遍历数据结构
  • list_for_each_entry_from(pos, head, member): 向下寻找与head匹配的数据结构 pos
  • list_for_each_entry_from_reverse(pos, head, member): 向上寻找与head匹配的数据结构 pos
  • list_safe_reset_next(pos, n, member): 得到与 pos 相连的下一个数据结构地址, 并将地址复制给 n.

内核提供了以下函数供操作:

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/**
* @brief 初始化链表
*/
static inline void INIT_LIST_HEAD(struct list_head *list);
/**
* @brief 在节点 prev,next 之间插入新节点 new
*/
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next);

/**
* @brief 在节点 head 后插入节点 new (以head 为参考)
* @note 这个过程就和入栈是一样的
*/
static inline void list_add(struct list_head *new, struct list_head *head);

/**
* @brief 在节点 head 前插入节点 new (以head 为参考)
* @note 这个过程就和插入一个数据到队列尾一样
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head);

/**
* @brief 删除 prev 和 next 之间的节点
*/
static inline void __list_del(struct list_head *prev, struct list_head *next);
/**
* @brief 删除 entry 节点,并将此节点的 prev 设置为 NULL
* @note 将 prev 设置为 NULL 是为了在某些场景下判断
*/
static inline void __list_del_clearprev(struct list_head *entry);
/**
* @brief 删除 entry 节点
* @note 这种情况下,其实 entry 节点还是指向了它之前前后位置,要是无意操作到便会出幺蛾子
*/
static inline void __list_del_entry(struct list_head *entry);
/**
* @brief 删除 entry 节点,并将此节点的 next 和 prev 指向会引起 Pagefault 的内存地址
* @note 这样以后,当有代码有意或无意操作该节点时,内核便会以 oops 来提示用户
*/
static inline void list_del(struct list_head *entry);
/**
* @brief 删除节点 entry,将此节点的 next 和 prev 指向自己
* @brief 这种情况下就是安全的
*/
static inline void list_del_init(struct list_head *entry);
/**
* @brief 节点 new 替换节点 old
* @brief 替换后,节点 old 依然指向原来的位置,这依然是不安全的
*/
static inline void list_replace(struct list_head *old, struct list_head *new);
/**
* @brief 节点 new 替换节点 old,并将 Old 的前后指向到自己
* @brief 这种情况下就是安全的
*/
static inline void list_replace_init(struct list_head *old, struct list_head *new);
/**
* @brief 交换两个节点的位置
*/
static inline void list_swap(struct list_head *entry1,
struct list_head *entry2)
/**
* @brief 将节点 list 移出当前链表, 并插入到另一个链表的 head 节点后
*/
static inline void list_move(struct list_head *list, struct list_head *head);
/**
* @brief 将节点 list 移出当前链表, 并插入到另一个链表的 head 节点前
*/
static inline void list_move_tail(struct list_head *list, struct list_head *head);
/**
* @brief 将 first 和 last 之间(包括 first 和 last) 的所有节点移动到 head 之前
* @note 这个操作必须是在同一个链表中
*/
static inline void list_bulk_move_tail(struct list_head *head,
struct list_head *first,
struct list_head *last);
/**
* @brief 判断 list 节点是否是该链表的第一个节点
*/
static inline int list_is_first(const struct list_head *list,
const struct list_head *head)
/**
* @brief 判断 list 节点是否是该链表的最后一个节点
*/
static inline int list_is_last(struct list_head *list, struct list_head *head);
/**
* @brief 判断当前链表是否是空链表
*/
static inline int list_empty(struct list_head *head);
/**
* @brief 以安全的方式判断当前链表是否是空链表
*/
static inline int list_empty_careful(const struct list_head *head);
/**
* @brief 将 head 开头的链表的节点从右边移动到左边
*/
static inline int list_rotate_left(struct list_head *head);
/**
* @brief 将 list 作为链表头
*/
static inline void list_rotate_to_front(struct list_head *list,
struct list_head *head);
/**
* @brief 判断一个链表是否只有一个元素
*/
static inline int list_is_singular(struct list_head *head);
/**
* @brief 将链表从 head 节点处切断(不包括 head), 一直到 entry(包括), 并拼接到 list节点处
* @note list 节点需要为空,否则 list 之前的链接会被丢失
*/
static inline int list_cut_position(struct list_head *list,
struct list_head *head,
struct list_head *entry);
/**
* @brief 将链表从 head 节点处切断(不包括 head), 一直到 entry(不包括), 并拼接到 list节点处
* @note list 节点需要为空,否则 list 之前的链接会被丢失
*/
static inline void list_cut_before(struct list_head *list,
struct list_head *head,
struct list_head *entry);

/**
* @brief 在 head 及其 next 之间插入链表 list,不包括 list 本身
*/
static inline int list_splice(struct list_head *list, struct list_head *head);
/**
* @brief 在 head 及其 next 之间插入链表 list,不包括 list 本身
* @note list 会被设置为指向自身,这是比较安全的
*/
static inline int list_splice_init(struct list_head *list, struct list_head *head);
/**
* @brief 在 head 及其 prev 之间插入链表 list,不包括 list 本身
*/
static inline int list_splice_tail(struct list_head *list, struct list_head *head);
/**
* @brief 在 head 及其 prev 之间插入链表 list,不包括 list 本身
* @note list 会被设置为指向自身,这是比较安全的
*/
static inline int list_splice_tail_init(struct list_head *list, struct list_head *head);

示例

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
#include 
#include
#include

#include "list.h"

LIST_HEAD(head);

typedef struct
{
int val;
struct list_head node;
}obj;


static void print_list(const struct list_head *head)
{
obj *pobj;
list_for_each_entry(pobj, head, node)
{
printf("%d,", pobj->val);
}
printf("\n");
}
static void clear_list(const struct list_head *head)
{
struct list_head *node, *next;
obj *pobj;
list_for_each_safe(node, next, head)
{
pobj = list_entry(node, obj, node);
list_del(node);
free(pobj);
}
}
/**
* @note 因为 list_add 是以栈的形式插入的数据,所以从 0~4 插入数据后,
* 遍历输出的是 4~0 的倒序
*/
static void test_list_add(void)
{
printf("%s\n", __func__);

for(int i = 0; i < 5; i++)
{
obj *pobj = malloc(sizeof(obj));
assert(pobj);

pobj->val = i;
list_add(&pobj->node, &head);
}

print_list(&head);
clear_list(&head);
}
/**
* @note 因为 list_add 是以队列的形式插入的数据,所以从 0~4 插入数据后,
* 遍历输出的是 0~4 的正序
*/
static void test_list_add_tail(void)
{
printf("%s\n", __func__);

for(int i = 0; i < 5; i++)
{
obj *pobj = malloc(sizeof(obj));
assert(pobj);

pobj->val = i;
list_add_tail(&pobj->node, &head);
}

print_list(&head);
clear_list(&head);
}
/**
* @note 删除索引 3 处的节点后,遍历输出便是 0,1,2,4
*/
static void test_list_del(void)
{
printf("%s\n", __func__);
obj *tmp = NULL;

for(int i = 0; i < 5; i++)
{
obj *pobj = malloc(sizeof(obj));
assert(pobj);

pobj->val = i;
list_add_tail(&pobj->node, &head);

if(i == 3)
{
tmp = pobj;
}
}
list_del(&tmp->node);
free(tmp);

print_list(&head);
clear_list(&head);
}
/**
* @note 替换索引 3 处的节点后,遍历输出便是 0,1,2,5, 4
*/
static void test_list_replace(void)
{
printf("%s\n", __func__);

obj *tmp = NULL;
for(int i = 0; i < 5; i++)
{
obj *pobj = malloc(sizeof(obj));
assert(pobj);

pobj->val = i;
list_add_tail(&pobj->node, &head);
if(i == 3)
{
tmp = pobj;
}
}
obj *pobj = malloc(sizeof(obj));
pobj->val = 5;
list_replace_init(&tmp->node, &pobj->node);
free(tmp);


print_list(&head);
clear_list(&head);
}
/**
* @note 交换索引 3,4 处的节点后,遍历输出便是 0,1,2,4, 3
*/
static void test_list_swap(void)
{
printf("%s\n", __func__);

obj *tmp = NULL;
obj *pobj = NULL;
for(int i = 0; i < 5; i++)
{
pobj = malloc(sizeof(obj));
assert(pobj);

pobj->val = i;
list_add_tail(&pobj->node, &head);
if(i == 3)
{
tmp = pobj;
}
}

list_swap(&tmp->node, &pobj->node);


print_list(&head);
clear_list(&head);
}
/**
* @note 将链表 0,1,2,3,4 中的 3 移动到另一个链表头,
* 那么另一个链表就是 3,5,6,7,8,9
*/
static void test_list_move(void)
{
printf("%s\n", __func__);

obj *tmp = NULL;
obj *pobj = NULL;
for(int i = 0; i < 5; i++)
{
pobj = malloc(sizeof(obj));
assert(pobj);

pobj->val = i;
list_add_tail(&pobj->node, &head);
if(i == 3)
{
tmp = pobj;
}
}

LIST_HEAD(new_head);
for(int i = 5; i < 10; i++)
{
pobj = malloc(sizeof(obj));
assert(pobj);

pobj->val = i;
list_add_tail(&pobj->node, &new_head);
}

list_move(&tmp->node, &new_head);


print_list(&head);
clear_list(&head);
print_list(&new_head);
clear_list(&new_head);
}
/**
* @note 将链表 0,1,2,3,4 中的 0,1,2 移动到尾部,
* 那么链表就是 3,4,0,1,2
*/
static void test_list_bulk_move_tail(void)
{
printf("%s\n", __func__);

obj *tmp = NULL, *tmp2 = NULL;
obj *pobj = NULL;
for(int i = 0; i < 5; i++)
{
pobj = malloc(sizeof(obj));
assert(pobj);

pobj->val = i;
list_add_tail(&pobj->node, &head);
if(i == 0)
{
tmp = pobj;
}
else if(i == 2)
{
tmp2 = pobj;
}
}

list_bulk_move_tail(&head, &tmp->node, &tmp2->node);


print_list(&head);
clear_list(&head);
}
/**
* @note 将链表 0,1,2,3,4 第一个节点移动到左边,
* 那么链表就是 1,2,3,4,0
*/
static void test_list_rotate_left(void)
{
printf("%s\n", __func__);

obj *pobj = NULL;
for(int i = 0; i < 5; i++)
{
pobj = malloc(sizeof(obj));
assert(pobj);

pobj->val = i;
list_add_tail(&pobj->node, &head);
}

list_rotate_left(&head);


print_list(&head);
clear_list(&head);
}
/**
* @note 将链表 0,1,2,3,4 中的 2,3 移动到另外一个空链表
*/
static void test_list_cut_position(void)
{
printf("%s\n", __func__);

obj *tmp = NULL, *tmp2 = NULL;
obj *pobj = NULL;
for(int i = 0; i < 5; i++)
{
pobj = malloc(sizeof(obj));
assert(pobj);

pobj->val = i;
list_add_tail(&pobj->node, &head);
if(i == 1)
{
tmp = pobj;
}
else if(i == 3)
{
tmp2 = pobj;
}
}

LIST_HEAD(new_head);
list_cut_position(&new_head, &tmp->node, &tmp2->node);

print_list(&head);
clear_list(&head);

print_list(&new_head);
clear_list(&new_head);
}
/**
* @note 将链表 5,6,7,8,9 拼接到链表 0,1,2,3,4
* 那么新链表就是 0~9
*/
static void test_list_splice_init(void)
{
printf("%s\n", __func__);

obj *pobj = NULL;
for(int i = 0; i < 5; i++)
{
pobj = malloc(sizeof(obj));
assert(pobj);

pobj->val = i;
list_add_tail(&pobj->node, &head);
}

LIST_HEAD(new_head);
for(int i = 5; i < 10; i++)
{
pobj = malloc(sizeof(obj));
assert(pobj);

pobj->val = i;
list_add_tail(&pobj->node, &new_head);
}

list_splice_init(&head, &new_head);


print_list(&head);
clear_list(&head);
print_list(&new_head);
clear_list(&new_head);
}
int main(int argc, char *argv[])
{
test_list_add();
test_list_add_tail();
test_list_del();
test_list_replace();
test_list_swap();
test_list_move();
test_list_bulk_move_tail();
test_list_rotate_left();
test_list_cut_position();
test_list_splice_init();

return 0;
}

哈希链表

哈希表概览

内核中使用哈希算法是以链表的方式防止哈希冲突。

这里前驱结点使用二级指针原因如下:
首先,链式哈希表使用数组来存放哈希表的表头,表头为了节省内存空间,使用一个指向下一节点的指针即可。
但是对于链表的节点而言,为了方便插入和删除操作,则需要使用双向链表。

但如果仅仅使用内核前面提供的双向链表,当操作前驱节点时,前驱节点无法指向头节点(因为表头类型不一样),但这样就增加了代码的复杂度。

二级指针的特点在于:二级指针指向的对象也是一个指针,所以它是固定的类型无关的。

那么使用二级指针就可以避免前面处理表头的麻烦了。

以普通双向链表的方式处理 hlist 的示例如此链接。

  • pprev 妙就妙在:它指向其前驱节点 next 指针的地址处,所以可以使用 *(n->pprev) = n 指向下一个节点
    • 即使这个前驱节点是表头也依然可以这么用

内核提供了以下宏供操作:

  • HLIST_HEAD(name) : 定义一个名称为 name 的链表,并指向空
  • HLIST_HEAD_INIT / INIT_HLIST_HEAD(ptr) : 初始化头节点
  • hlist_entry(ptr, type, member):根据 ptr 得到 entry
  • hlist_for_each(pos, head) : 遍历链表
  • hlist_for_each_safe(pos, n, head) :在遍历的同时需要删除链表时,需要使用此宏
  • hlist_entry_safe(ptr, type, member):当 ptr 不为空时返回对应的 entry
  • hlist_for_each_entry(pos, head, member):从 head 开始遍历 entry
  • hlist_for_each_entry_continue(pos, member) : 继续遍历,不包含当前 pos
  • hlist_for_each_entry_from(pos, member):继续遍历,包含当前 pos
  • hlist_for_each_entry_safe(pos, n, head, member): 当要删除该 pos 时,应该使用此宏

内核提供了如下函数供操作:

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
/**
* @brief 初始化一个节点
* @note : 将节点前后驱指针置空
*/
static inline void INIT_HLIST_NODE(struct hlist_node *h);
/**
* @brief 该节点未被挂入 hash ,返回 true
* @note 如果其前驱节点为空,则可以证明该节点没有被挂入链表
*/
static inline int hlist_unhashed(const struct hlist_node *h);
/**
* @brief 如果该链表为空则返回 true
* @note 如果表头指向的第一个节点都会空,则证明该链表没有挂入任何节点
*/
static inline int hlist_empty(const struct hlist_head *h);
/**
* @brief 删除一个节点
*/
static inline void __hlist_del(struct hlist_node *n);
/**
* @brief 删除一个节点,并将此节点指向 LIST_POISON
* @note 如果有代码操作此节点,内核便会输出 oops
*/
static inline void hlist_del(struct hlist_node *n);
/**
* @brief 删除一个节点,并将此节点指向置空
* @note 如果有代码操作此节点,内核便会输出 oops
*/
static inline void hlist_del_init(struct hlist_node *n);
/**
* @brief 将节点 n 插入到链表头
*/
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h);
/**
* @brief 将节点 n 插入到节点 next 之前
*/
static inline void hlist_add_before(struct hlist_node *n,
struct hlist_node *next);
/**
* @brief 将节点 n 插入到节点 prev 之后
*/
static inline void hlist_add_behind(struct hlist_node *n,
struct hlist_node *prev);
/**
* @brief 将节点 n 的前驱结点指向自己
* @note 这相当于将当前节点及及其后的节点与链表脱离了
*/
static inline void hlist_add_fake(struct hlist_node *n);
static inline bool hlist_fake(struct hlist_node *h);
/**
* @brief 当链表 h 上只有一个节点 n 时,返回 true
*/
static inline bool
hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h);
/**
* @brief 将链表 old 上的节点移动到 new 链表上去
* @note old 链表的表头指向空
*/
static inline void hlist_move_list(struct hlist_head *old,
struct hlist_head *new);

示例

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include 
#include
#include
#include

#include "list.h"

typedef struct
{
uint32_t number;
char *name;
uint8_t age;
struct hlist_node node;
}student_t;

#define HASH_TABLE_SIZE (4)

typedef struct
{
student_t student;
struct hlist_head head;
}hash_element_t;

struct
{
hash_element_t buf[HASH_TABLE_SIZE];
}hash_table;

static student_t bruce =
{
.number = 10102,
.name = "Bruce",
.age = 16,
};
static student_t tom =
{
.number = 10103,
.name = "Tom",
.age = 18,
};
static student_t may =
{
.number = 10205,
.name = "May",
.age = 20,
};
static student_t jim =
{
.number = 10303,
.name = "Jim",
.age = 27,
};
static student_t tony =
{
.number = 10503,
.name = "tony",
.age = 25,
};


static void hash_init(void)
{
for(uint32_t i = 0; i < HASH_TABLE_SIZE; ++i)
{
INIT_HLIST_HEAD(&hash_table.buf[i].head);
}
}

static uint32_t hash_val_get(uint32_t key)
{
return (key % HASH_TABLE_SIZE);
}
static void hash_save(student_t *student, uint32_t index)
{
student_t *obj;
bool have_obj = false;

hlist_for_each_entry(obj, &hash_table.buf[index].head, node)
{
if(obj->number == student->number)
{
student->node = obj->node;
*obj = *student;
printf("modify student [%s]\n", student->name);
have_obj = true;
break;
}
}
if(have_obj == false)
{
printf("insert student [%s]\n", student->name);

obj = (student_t *)malloc(sizeof(student_t));
assert(obj != NULL);
*obj = *student;
hlist_add_head(&obj->node, &hash_table.buf[index].head);
}
}
static void hash_insert(student_t *student)
{
uint32_t index = hash_val_get(student->number);
printf("insert index = %d\n", index);

hash_save(student, index);
}
static bool hash_rm(uint32_t key)
{
bool ret = false;
int32_t index = hash_val_get(key);
printf("rm index = %d\n", index);
if(index != -1)
{
student_t *obj;
struct hlist_node *n;
hlist_for_each_entry_safe(obj, n, &hash_table.buf[index].head, node)
{
hlist_del(&obj->node);
free(obj);
ret = true;
}
}
if(ret == false)
{
printf("can not find !\n");
}

return ret;
}
static void hash_modify(student_t *student)
{
hash_insert(student);
}
static bool hash_find(student_t *student, uint32_t key)
{
bool ret = false;
int32_t index = hash_val_get(key);
printf("find index = %d\n", index);
if(index != -1)
{
student_t *obj;
hlist_for_each_entry(obj, &hash_table.buf[index].head, node)
{
if(obj->number == key)
{
*student = *obj;
ret = true;
break;
}
}
}
if(ret == false)
{
printf("can not find !\n");
}

return ret;
}

static void print_student(const student_t *student)
{
printf("Hi, my name is [%s], and my number is [%d], and I'm [%d]\n",
student->name,
student->number,
student->age);
}
static void print_hash(void)
{
for(uint8_t i = 0; i < HASH_TABLE_SIZE; i++)
{
student_t *obj;
printf("list [%d]:", i);
hlist_for_each_entry(obj, &hash_table.buf[i].head, node)
{
printf("%s, ", obj->name);
}
printf("\n");
}
printf("\n");
}
int main(int argc, char *argv[])
{
hash_init();

hash_insert(&bruce);
print_hash();

hash_insert(&tom);
print_hash();

hash_insert(&may);
print_hash();

hash_insert(&jim);
print_hash();

hash_insert(&tony);
print_hash();

hash_rm(may.number);
print_hash();

bruce.age = 50;
hash_modify(&bruce);
print_hash();

hash_insert(&tony);
print_hash();

jim.age = 50;
hash_modify(&jim);
print_hash();

student_t student;

if(hash_find(&student, bruce.number) == true)
print_student(&student);

if(hash_find(&student, tom.number) == true)
print_student(&student);

if(hash_find(&student, may.number) == true)
print_student(&student);

if(hash_find(&student, jim.number) == true)
print_student(&student);

if(hash_find(&student, tony.number) == true)
print_student(&student);

return 0;
}
Last Updated 2020-08-20 四 17:38.
Render by hexo-renderer-org with Emacs 26.3 (Org mode 9.3.7)