Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / lib / hash_test.c @ 6b3f1a54

History | View | Annotate | Download (5.54 KB)

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
}