]>
Commit | Line | Data |
---|---|---|
9b0a0ba9 OZ |
1 | /* |
2 | * BIRD Library -- Hash Tests | |
3 | * | |
4 | * (c) 2015 CZ.NIC z.s.p.o. | |
5 | * | |
6 | * Can be freely distributed and used under the terms of the GNU GPL. | |
7 | */ | |
8 | ||
9 | #undef LOCAL_DEBUG | |
10 | ||
11 | #include "test/birdtest.h" | |
12 | ||
13 | #include "lib/hash.h" | |
14 | ||
15 | struct test_node { | |
16 | struct test_node *next; /* Hash chain */ | |
17 | u32 key; | |
18 | }; | |
19 | ||
20 | #define TEST_KEY(n) n->key | |
21 | #define TEST_NEXT(n) n->next | |
22 | #define TEST_EQ(n1,n2) n1 == n2 | |
23 | #define TEST_FN(n) (n) ^ u32_hash((n)) | |
24 | #define TEST_ORDER 13 | |
25 | #define TEST_PARAMS /TEST_ORDER, *2, 2, 2, TEST_ORDER, 20 | |
26 | #define TEST_REHASH test_rehash | |
27 | ||
28 | HASH_DEFINE_REHASH_FN(TEST, struct test_node); | |
29 | ||
30 | HASH(struct test_node) hash; | |
31 | struct pool *my_pool; | |
32 | ||
33 | #define MAX_NUM (1 << TEST_ORDER) | |
34 | ||
35 | struct test_node nodes[MAX_NUM]; | |
36 | ||
37 | static void | |
38 | print_rate_of_fulfilment(void) | |
39 | { | |
40 | int i; | |
41 | int num_stacked_items = 0; | |
42 | ||
43 | for (i = 0; i < MAX_NUM; i++) | |
44 | if (!hash.data[i]) | |
45 | num_stacked_items++; | |
46 | ||
47 | double percent_stacked_items = ((double)num_stacked_items/(double)MAX_NUM)*100.; | |
48 | bt_debug("%d (%.2f %%) chained of %d hashes \n", num_stacked_items, percent_stacked_items, MAX_NUM); | |
49 | } | |
50 | ||
51 | #ifdef LOCAL_DEBUG | |
52 | static void | |
53 | dump_nodes(void) | |
54 | { | |
55 | int i; | |
56 | for (i = 0; i < MAX_NUM; i++) | |
57 | bt_debug("nodes[%3d] is at address %14p has .key %3d, .next %14p \n", i, &nodes[i], nodes[i].key, nodes[i].next); | |
58 | } | |
59 | #endif | |
60 | ||
61 | static void | |
62 | init_hash_(uint order) | |
63 | { | |
64 | resource_init(); | |
65 | my_pool = rp_new(&root_pool, "Test pool"); | |
66 | ||
67 | HASH_INIT(hash, my_pool, order); | |
68 | ||
69 | int i; | |
70 | for (i = 0; i < MAX_NUM; i++) | |
71 | { | |
72 | nodes[i].key = i; | |
73 | nodes[i].next = NULL; | |
74 | } | |
75 | ||
76 | bt_debug("MAX_NUM %d \n", MAX_NUM); | |
77 | } | |
78 | ||
79 | static void | |
80 | init_hash(void) | |
81 | { | |
82 | init_hash_(TEST_ORDER); | |
83 | } | |
84 | ||
85 | static void | |
86 | validate_filled_hash(void) | |
87 | { | |
88 | int i; | |
89 | struct test_node *node; | |
90 | for (i = 0; i < MAX_NUM; i++) | |
91 | { | |
92 | node = HASH_FIND(hash, TEST, nodes[i].key); | |
93 | bt_assert_msg(node->key == nodes[i].key, "Hash should be filled, to find (%p) the node[%d] (%p) with .key = %u, .next %p", node, i, &nodes[i], nodes[i].key, nodes[i].next); | |
94 | } | |
95 | ||
96 | print_rate_of_fulfilment(); | |
97 | } | |
98 | ||
99 | static void | |
100 | validate_empty_hash(void) | |
101 | { | |
102 | int i; | |
103 | struct test_node *node; | |
104 | for (i = 0; i < MAX_NUM; i++) | |
105 | { | |
106 | node = HASH_FIND(hash, TEST, nodes[i].key); | |
107 | bt_assert_msg(node == NULL, "Hash should be empty, to find (%p) the node[%d] (%p) with .key %u, .next %p", node, i, &nodes[i], nodes[i].key, nodes[i].next); | |
108 | } | |
109 | } | |
110 | ||
111 | static void | |
112 | fill_hash(void) | |
113 | { | |
114 | int i; | |
115 | struct test_node *node; | |
116 | ||
117 | for (i = 0; i < MAX_NUM; i++) | |
118 | { | |
119 | nodes[i].key = i; | |
120 | node = &nodes[i]; | |
121 | HASH_INSERT(hash, TEST, node); | |
122 | } | |
123 | } | |
124 | ||
125 | static int | |
126 | t_insert_find(void) | |
127 | { | |
128 | init_hash(); | |
129 | fill_hash(); | |
130 | validate_filled_hash(); | |
131 | ||
5e3cd0e5 | 132 | return 1; |
9b0a0ba9 OZ |
133 | } |
134 | ||
135 | static int | |
136 | t_insert_find_random(void) | |
137 | { | |
138 | init_hash(); | |
139 | ||
140 | int i; | |
141 | struct test_node *node; | |
142 | for (i = 0; i < MAX_NUM; i++) | |
143 | { | |
144 | nodes[i].key = bt_random(); | |
145 | node = &nodes[i]; | |
146 | HASH_INSERT(hash, TEST, node); | |
147 | } | |
148 | ||
149 | validate_filled_hash(); | |
150 | ||
5e3cd0e5 | 151 | return 1; |
9b0a0ba9 OZ |
152 | } |
153 | ||
154 | static int | |
155 | t_insert2_find(void) | |
156 | { | |
157 | init_hash_(1); | |
158 | ||
159 | int i; | |
160 | struct test_node *node; | |
161 | for (i = 0; i < MAX_NUM; i++) | |
162 | { | |
163 | nodes[i].key = i; | |
164 | node = &nodes[i]; | |
165 | HASH_INSERT2(hash, TEST, my_pool, node); | |
166 | } | |
167 | bt_assert_msg(hash.order != 1, "The hash should auto-resize from order 2^1. The order of the hash is 2^%u.", hash.order); | |
168 | ||
169 | validate_filled_hash(); | |
170 | ||
5e3cd0e5 | 171 | return 1; |
9b0a0ba9 OZ |
172 | } |
173 | ||
174 | static int | |
175 | t_walk(void) | |
176 | { | |
177 | init_hash(); | |
178 | fill_hash(); | |
179 | ||
180 | uint i; | |
181 | uint check[MAX_NUM]; | |
182 | for (i = 0; i < MAX_NUM; i++) | |
183 | check[i] = 0; | |
184 | ||
185 | HASH_WALK(hash, next, n) | |
186 | { | |
187 | check[n->key]++; | |
188 | } | |
189 | HASH_WALK_END; | |
190 | ||
191 | for (i = 0; i < MAX_NUM; i++) | |
192 | bt_assert(check[i] == 1); | |
193 | ||
5e3cd0e5 | 194 | return 1; |
9b0a0ba9 OZ |
195 | } |
196 | ||
197 | static int | |
198 | t_walk_delsafe_delete(void) | |
199 | { | |
200 | init_hash(); | |
201 | fill_hash(); | |
202 | ||
203 | HASH_WALK_DELSAFE(hash, next, n) | |
204 | { | |
205 | HASH_DELETE(hash, TEST, n->key); | |
206 | } | |
207 | HASH_WALK_DELSAFE_END; | |
208 | ||
209 | validate_empty_hash(); | |
210 | ||
5e3cd0e5 | 211 | return 1; |
9b0a0ba9 OZ |
212 | } |
213 | ||
214 | static int | |
215 | t_walk_delsafe_remove(void) | |
216 | { | |
217 | init_hash(); | |
218 | fill_hash(); | |
219 | ||
220 | HASH_WALK_DELSAFE(hash, next, n) | |
221 | { | |
222 | HASH_REMOVE(hash, TEST, n); | |
223 | } | |
224 | HASH_WALK_DELSAFE_END; | |
225 | ||
226 | validate_empty_hash(); | |
227 | ||
5e3cd0e5 | 228 | return 1; |
9b0a0ba9 OZ |
229 | } |
230 | ||
231 | static int | |
232 | t_walk_delsafe_delete2(void) | |
233 | { | |
234 | init_hash(); | |
235 | fill_hash(); | |
236 | ||
237 | HASH_WALK_DELSAFE(hash, next, n) | |
238 | { | |
239 | HASH_DELETE2(hash, TEST, my_pool, n->key); | |
240 | } | |
241 | HASH_WALK_DELSAFE_END; | |
242 | ||
243 | validate_empty_hash(); | |
244 | ||
5e3cd0e5 | 245 | return 1; |
9b0a0ba9 OZ |
246 | } |
247 | ||
248 | static int | |
249 | t_walk_delsafe_remove2(void) | |
250 | { | |
251 | init_hash(); | |
252 | fill_hash(); | |
253 | ||
254 | HASH_WALK_DELSAFE(hash, next, n) | |
255 | { | |
256 | HASH_REMOVE2(hash, TEST, my_pool, n); | |
257 | } | |
258 | HASH_WALK_DELSAFE_END; | |
259 | ||
260 | validate_empty_hash(); | |
261 | ||
5e3cd0e5 | 262 | return 1; |
9b0a0ba9 OZ |
263 | } |
264 | ||
265 | static int | |
266 | t_walk_filter(void) | |
267 | { | |
268 | init_hash(); | |
269 | fill_hash(); | |
270 | ||
271 | uint i; | |
272 | uint check[MAX_NUM]; | |
273 | for (i = 0; i < MAX_NUM; i++) | |
274 | check[i] = 0; | |
275 | ||
276 | HASH_WALK_FILTER(hash, next, n, m) | |
277 | { | |
278 | bt_assert(n == *m); | |
279 | check[n->key]++; | |
280 | } | |
281 | HASH_WALK_FILTER_END; | |
282 | ||
283 | for (i = 0; i < MAX_NUM; i++) | |
284 | bt_assert(check[i] == 1); | |
285 | ||
5e3cd0e5 | 286 | return 1; |
9b0a0ba9 OZ |
287 | } |
288 | ||
289 | int | |
290 | main(int argc, char *argv[]) | |
291 | { | |
292 | bt_init(argc, argv); | |
293 | ||
294 | bt_test_suite(t_insert_find, "HASH_INSERT and HASH_FIND"); | |
295 | bt_test_suite(t_insert_find_random, "HASH_INSERT pseudo-random keys and HASH_FIND"); | |
296 | bt_test_suite(t_insert2_find, "HASH_INSERT2 and HASH_FIND. HASH_INSERT2 is HASH_INSERT and a smart auto-resize function"); | |
297 | bt_test_suite(t_walk, "HASH_WALK"); | |
298 | bt_test_suite(t_walk_delsafe_delete, "HASH_WALK_DELSAFE and HASH_DELETE"); | |
299 | bt_test_suite(t_walk_delsafe_delete2, "HASH_WALK_DELSAFE and HASH_DELETE2. HASH_DELETE2 is HASH_DELETE and smart auto-resize function"); | |
300 | bt_test_suite(t_walk_delsafe_remove, "HASH_WALK_DELSAFE and HASH_REMOVE"); | |
301 | bt_test_suite(t_walk_delsafe_remove2, "HASH_WALK_DELSAFE and HASH_REMOVE2. HASH_REMOVE2 is HASH_REMOVE and smart auto-resize function"); | |
302 | bt_test_suite(t_walk_filter, "HASH_WALK_FILTER"); | |
303 | ||
304 | return bt_exit_value(); | |
305 | } |