![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hash_test.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / lib|
Return to hash_test.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / lib |
1.1 misho 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:
132: return 1;
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:
151: return 1;
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:
171: return 1;
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:
194: return 1;
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:
211: return 1;
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:
228: return 1;
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:
245: return 1;
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:
262: return 1;
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:
286: return 1;
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: }