3
* test_hash.c - test suite for nih/hash.c
5
* Copyright © 2009 Scott James Remnant <scott@netsplit.com>.
6
* Copyright © 2009 Canonical Ltd.
8
* This program is free software; you can redistribute it and/or modify
9
* it under the terms of the GNU General Public License version 2, as
10
* published by the Free Software Foundation.
12
* This program is distributed in the hope that it will be useful,
13
* but WITHOUT ANY WARRANTY; without even the implied warranty of
14
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15
* GNU General Public License for more details.
17
* You should have received a copy of the GNU General Public License along
18
* with this program; if not, write to the Free Software Foundation, Inc.,
19
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24
#include <nih/macros.h>
25
#include <nih/alloc.h>
30
typedef struct hash_entry {
36
new_entry (void *parent,
41
entry = nih_new (parent, HashEntry);
43
nih_list_init (&entry->list);
46
return (NihList *)entry;
50
my_key_function (NihList *entry)
56
my_hash_function (const void *key)
58
static uint32_t hash = 0;
64
my_cmp_function (const void *key1,
77
TEST_FUNCTION ("nih_hash_new");
79
/* Check that we can create a small hash table; a small prime number
80
* should be selected for the actual size, and that number of empty
81
* bins should be allocated as a child of the hash table.
83
TEST_FEATURE ("with zero size");
85
hash = nih_hash_new (NULL, 0,
90
if (test_alloc_failed) {
91
TEST_EQ_P (hash, NULL);
95
TEST_ALLOC_SIZE (hash, sizeof(NihHash));
96
TEST_EQ_P (hash->key_function, my_key_function);
97
TEST_EQ_P (hash->hash_function, my_hash_function);
98
TEST_EQ_P (hash->cmp_function, my_cmp_function);
100
TEST_EQ (hash->size, 17);
101
TEST_NE_P (hash->bins, NULL);
102
TEST_ALLOC_PARENT (hash->bins, hash);
104
for (i = 0; i < hash->size; i++)
105
TEST_LIST_EMPTY (&hash->bins[i]);
111
/* Check again with a medium size, which should pick a medium prime
114
TEST_FEATURE ("with medium size");
116
hash = nih_hash_new (NULL, 600,
121
if (test_alloc_failed) {
122
TEST_EQ_P (hash, NULL);
126
TEST_EQ (hash->size, 331);
127
TEST_NE_P (hash->bins, NULL);
128
TEST_ALLOC_PARENT (hash->bins, hash);
130
for (i = 0; i < hash->size; i++)
131
TEST_LIST_EMPTY (&hash->bins[i]);
137
/* Check with a much larger size, which should pick the largest prime
140
TEST_FEATURE ("with large size");
142
hash = nih_hash_new (NULL, 40000000,
147
if (test_alloc_failed) {
148
TEST_EQ_P (hash, NULL);
152
TEST_EQ (hash->size, 10250323);
153
TEST_NE_P (hash->bins, NULL);
154
TEST_ALLOC_PARENT (hash->bins, hash);
156
for (i = 0; i < hash->size; i++)
157
TEST_LIST_EMPTY (&hash->bins[i]);
164
test_string_new (void)
169
/* Check that we can create a small hash table; a small prime number
170
* should be selected for the actual size, and that number of empty
171
* bins should be allocated as a child of the hash table.
173
TEST_FUNCTION ("nih_hash_string_new");
175
hash = nih_hash_string_new (NULL, 0);
177
if (test_alloc_failed) {
178
TEST_EQ_P (hash, NULL);
182
TEST_ALLOC_SIZE (hash, sizeof(NihHash));
183
TEST_EQ_P (hash->key_function,
184
(NihKeyFunction)nih_hash_string_key);
185
TEST_EQ_P (hash->hash_function,
186
(NihHashFunction)nih_hash_string_hash);
187
TEST_EQ_P (hash->cmp_function,
188
(NihCmpFunction)nih_hash_string_cmp);
190
TEST_EQ (hash->size, 17);
191
TEST_NE_P (hash->bins, NULL);
192
TEST_ALLOC_PARENT (hash->bins, hash);
194
for (i = 0; i < hash->size; i++)
195
TEST_LIST_EMPTY (&hash->bins[i]);
205
NihList *entry1, *entry2, *entry3, *entry4, *ptr;
207
TEST_FUNCTION ("nih_hash_add");
208
hash = nih_hash_string_new (NULL, 0);
209
entry1 = new_entry (hash, "entry 1");
210
entry2 = new_entry (hash, "entry 2");
211
entry3 = new_entry (hash, "entry 1");
212
entry4 = new_entry (hash, "entry 4");
214
/* Check that we can add an entry to an empty hash table; it should
215
* be returned and turn up in the appropriate bin.
217
TEST_FEATURE ("with empty hash");
218
ptr = nih_hash_add (hash, entry1);
220
TEST_EQ_P (ptr, entry1);
222
TEST_EQ_P (hash->bins[15].next, entry1);
223
TEST_EQ_P (entry1->next, &hash->bins[15]);
224
TEST_EQ_P (hash->bins[15].prev, entry1);
225
TEST_EQ_P (entry1->prev, &hash->bins[15]);
228
/* Check that we can add an entry to a populated hash table. */
229
TEST_FEATURE ("with non-empty hash");
230
nih_hash_add (hash, entry2);
232
TEST_EQ_P (hash->bins[14].next, entry2);
233
TEST_EQ_P (entry2->next, &hash->bins[14]);
234
TEST_EQ_P (hash->bins[14].prev, entry2);
235
TEST_EQ_P (entry2->prev, &hash->bins[14]);
238
/* Check that we can add an entry with a duplicate key, and it is
239
* added to the end of the same bin as the previous entry with that
242
TEST_FEATURE ("with duplicate key");
243
nih_hash_add (hash, entry3);
245
TEST_EQ_P (hash->bins[15].next, entry1);
246
TEST_EQ_P (entry1->next, entry3);
247
TEST_EQ_P (entry3->next, &hash->bins[15]);
248
TEST_EQ_P (hash->bins[15].prev, entry3);
249
TEST_EQ_P (entry3->prev, entry1);
250
TEST_EQ_P (entry1->prev, &hash->bins[15]);
253
/* Check that nih_hash_add can rip an entry out of an existing list
254
* and place it in the hash table.
256
TEST_FEATURE ("with entry already in a list");
257
ptr = nih_list_new (NULL);
258
nih_list_add (ptr, entry4);
259
nih_hash_add (hash, entry4);
261
TEST_EQ_P (ptr->next, ptr);
262
TEST_EQ_P (ptr->prev, ptr);
264
TEST_EQ_P (hash->bins[3].next, entry4);
265
TEST_EQ_P (entry4->next, &hash->bins[3]);
266
TEST_EQ_P (hash->bins[3].prev, entry4);
267
TEST_EQ_P (entry4->prev, &hash->bins[3]);
274
test_add_unique (void)
277
NihList *entry1, *entry2, *entry3, *entry4, *ptr;
279
TEST_FUNCTION ("nih_hash_add_unique");
280
hash = nih_hash_string_new (NULL, 0);
281
entry1 = new_entry (hash, "entry 1");
282
entry2 = new_entry (hash, "entry 2");
283
entry3 = new_entry (hash, "entry 1");
284
entry4 = new_entry (hash, "entry 4");
286
/* Check that we can add an entry to an empty hash table; it should
287
* be returned and turn up in the appropriate bin.
289
TEST_FEATURE ("with empty hash");
290
ptr = nih_hash_add_unique (hash, entry1);
292
TEST_EQ_P (ptr, entry1);
294
TEST_EQ_P (hash->bins[15].next, entry1);
295
TEST_EQ_P (entry1->next, &hash->bins[15]);
296
TEST_EQ_P (hash->bins[15].prev, entry1);
297
TEST_EQ_P (entry1->prev, &hash->bins[15]);
300
/* Check that we can add an entry to a populated hash table. */
301
TEST_FEATURE ("with non-empty hash");
302
nih_hash_add_unique (hash, entry2);
304
TEST_EQ_P (hash->bins[14].next, entry2);
305
TEST_EQ_P (entry2->next, &hash->bins[14]);
306
TEST_EQ_P (hash->bins[14].prev, entry2);
307
TEST_EQ_P (entry2->prev, &hash->bins[14]);
310
/* Check that we get NULL if we try and add an entry with a
311
* duplicate key, and that the hash table is not altered.
313
TEST_FEATURE ("with duplicate key");
314
ptr = nih_hash_add_unique (hash, entry3);
316
TEST_EQ_P (ptr, NULL);
318
TEST_EQ_P (hash->bins[15].next, entry1);
319
TEST_EQ_P (entry1->next, &hash->bins[15]);
320
TEST_EQ_P (hash->bins[15].prev, entry1);
321
TEST_EQ_P (entry1->prev, &hash->bins[15]);
324
/* Check that nih_hash_add can rip an entry out of an existing list
325
* and place it in the hash table.
327
TEST_FEATURE ("with entry already in a list");
328
ptr = nih_list_new (NULL);
329
nih_list_add (ptr, entry4);
330
nih_hash_add_unique (hash, entry4);
332
TEST_EQ_P (ptr->next, ptr);
333
TEST_EQ_P (ptr->prev, ptr);
335
TEST_EQ_P (hash->bins[3].next, entry4);
336
TEST_EQ_P (entry4->next, &hash->bins[3]);
337
TEST_EQ_P (hash->bins[3].prev, entry4);
338
TEST_EQ_P (entry4->prev, &hash->bins[3]);
348
NihList *entry1, *entry2, *entry3, *entry4, *ptr;
350
TEST_FUNCTION ("nih_hash_replace");
351
hash = nih_hash_string_new (NULL, 0);
352
entry1 = new_entry (hash, "entry 1");
353
entry2 = new_entry (hash, "entry 2");
354
entry3 = new_entry (hash, "entry 1");
355
entry4 = new_entry (hash, "entry 4");
357
/* Check that we can add an entry to an empty hash table; NULL should
358
* be returned (nothing replaced) and the entry should turn up in the
361
TEST_FEATURE ("with empty hash");
362
ptr = nih_hash_replace (hash, entry1);
364
TEST_EQ_P (ptr, NULL);
366
TEST_EQ_P (hash->bins[15].next, entry1);
367
TEST_EQ_P (entry1->next, &hash->bins[15]);
368
TEST_EQ_P (hash->bins[15].prev, entry1);
369
TEST_EQ_P (entry1->prev, &hash->bins[15]);
372
/* Check that we can add an entry to a populated hash table. */
373
TEST_FEATURE ("with non-empty hash");
374
nih_hash_replace (hash, entry2);
376
TEST_EQ_P (hash->bins[14].next, entry2);
377
TEST_EQ_P (entry2->next, &hash->bins[14]);
378
TEST_EQ_P (hash->bins[14].prev, entry2);
379
TEST_EQ_P (entry2->prev, &hash->bins[14]);
382
/* Check that we can add an entry with a duplicate key, replacing
383
* the existing one in the hash. The replaced entry should be
384
* returned, and removed from the bin.
386
TEST_FEATURE ("with duplicate key");
387
ptr = nih_hash_replace (hash, entry3);
389
TEST_EQ_P (ptr, entry1);
391
TEST_EQ_P (entry1->next, entry1);
392
TEST_EQ_P (entry1->prev, entry1);
394
TEST_EQ_P (hash->bins[15].next, entry3);
395
TEST_EQ_P (entry3->next, &hash->bins[15]);
396
TEST_EQ_P (hash->bins[15].prev, entry3);
397
TEST_EQ_P (entry3->prev, &hash->bins[15]);
400
/* Check that nih_hash_add can rip an entry out of an existing list
401
* and place it in the hash table.
403
TEST_FEATURE ("with entry already in a list");
404
ptr = nih_list_new (NULL);
405
nih_list_add (ptr, entry4);
406
nih_hash_replace (hash, entry4);
408
TEST_EQ_P (ptr->next, ptr);
409
TEST_EQ_P (ptr->prev, ptr);
411
TEST_EQ_P (hash->bins[3].next, entry4);
412
TEST_EQ_P (entry4->next, &hash->bins[3]);
413
TEST_EQ_P (hash->bins[3].prev, entry4);
414
TEST_EQ_P (entry4->prev, &hash->bins[3]);
424
NihList *entry1, *entry2, *entry3, *ptr;
426
TEST_FUNCTION ("nih_hash_search");
427
hash = nih_hash_string_new (NULL, 0);
428
entry1 = nih_hash_add (hash, new_entry (hash, "entry 1"));
429
entry2 = nih_hash_add (hash, new_entry (hash, "entry 2"));
430
entry3 = nih_hash_add (hash, new_entry (hash, "entry 2"));
432
/* Check that we find the sole matching entry. */
433
ptr = nih_hash_search (hash, "entry 1", NULL);
435
TEST_EQ_P (ptr, entry1);
437
/* Searching again should find nothing */
438
ptr = nih_hash_search (hash, "entry 1", ptr);
440
TEST_EQ_P (ptr, NULL);
443
/* Check that where there's multiple matches, we find the first one. */
444
TEST_FEATURE ("with multiple matches");
445
ptr = nih_hash_search (hash, "entry 2", NULL);
447
TEST_EQ_P (ptr, entry2);
449
/* And that searching again finds the second one. */
450
ptr = nih_hash_search (hash, "entry 2", ptr);
452
TEST_EQ_P (ptr, entry3);
454
/* And again finds nothing. */
455
ptr = nih_hash_search (hash, "entry 2", ptr);
457
TEST_EQ_P (ptr, NULL);
460
/* Check that we get NULL if there are no matches. */
461
TEST_FEATURE ("with no matches");
462
ptr = nih_hash_search (hash, "entry 3", NULL);
464
TEST_EQ_P (ptr, NULL);
473
NihList *entry1, *entry2, *entry3, *ptr;
475
TEST_FUNCTION ("nih_hash_lookup");
476
hash = nih_hash_string_new (NULL, 0);
477
entry1 = nih_hash_add (hash, new_entry (hash, "entry 1"));
478
entry2 = nih_hash_add (hash, new_entry (hash, "entry 2"));
479
entry3 = new_entry (hash, "entry 3");
481
/* Check that we find a single matching entry. */
482
TEST_FEATURE ("with single match");
483
ptr = nih_hash_lookup (hash, "entry 1");
485
TEST_EQ_P (ptr, entry1);
488
/* Check that we find the first matching entry. */
489
TEST_FEATURE ("with multiple matches");
490
ptr = nih_hash_lookup (hash, "entry 2");
492
TEST_EQ_P (ptr, entry2);
495
/* Check that we get NULL when there are no matching entries. */
496
TEST_FEATURE ("with no matches");
497
ptr = nih_hash_lookup (hash, "entry 3");
499
TEST_EQ_P (ptr, NULL);
509
NihList *entry[4], *entry0, *entry1, *entry2, *entry3;
512
/* Check that NIH_HASH_FOREACH iterates the hash correctly in order,
513
* visiting each entry in each bin. Note that we stage the entries
514
* in the hash in the order we expect them to come out in, but add
515
* them in a different order for sanity.
517
TEST_FUNCTION ("NIH_HASH_FOREACH");
518
hash = nih_hash_string_new (NULL, 0);
519
entry0 = entry[2] = new_entry (hash, "entry 1");
520
entry1 = entry[1] = new_entry (hash, "entry 2");
521
entry2 = entry[3] = new_entry (hash, "entry 1");
522
entry3 = entry[0] = new_entry (hash, "entry 4");
524
nih_hash_add (hash, entry0);
525
nih_hash_add (hash, entry1);
526
nih_hash_add (hash, entry2);
527
nih_hash_add (hash, entry3);
530
NIH_HASH_FOREACH (hash, iter) {
532
TEST_FAILED ("wrong number of iterations, expected %d got %d",
535
if (iter != entry[i])
536
TEST_FAILED ("wrong list entry, expected %p got %p",
546
test_foreach_safe (void)
549
NihList *entry[4], *entry0, *entry1, *entry2, *entry3;
552
/* Check that NIH_HASH_FOREACH_SAFE iterates the hash correctly in
553
* order, visiting each entry in each bin; and that it's safe to
554
* remove the entries while doing so.
556
TEST_FUNCTION ("NIH_HASH_FOREACH_SAFE");
557
hash = nih_hash_string_new (NULL, 0);
558
entry0 = entry[2] = new_entry (hash, "entry 1");
559
entry1 = entry[1] = new_entry (hash, "entry 2");
560
entry2 = entry[3] = new_entry (hash, "entry 1");
561
entry3 = entry[0] = new_entry (hash, "entry 4");
563
nih_hash_add (hash, entry0);
564
nih_hash_add (hash, entry1);
565
nih_hash_add (hash, entry2);
566
nih_hash_add (hash, entry3);
569
NIH_HASH_FOREACH_SAFE (hash, iter) {
571
TEST_FAILED ("wrong number of iterations, expected %d got %d",
574
if (iter != entry[i])
575
TEST_FAILED ("wrong list entry, expected %p got %p",
578
nih_list_remove (entry[i]);
588
test_string_key (void)
594
/* Check that the string key function returns a pointer to the
595
* key in our test structure.
597
TEST_FUNCTION ("nih_hash_string_key");
598
entry = new_entry (NULL, "my entry");
600
key = nih_hash_string_key (entry);
602
TEST_EQ_P (key, ((HashEntry *)entry)->key);
603
TEST_EQ_STR (key, "my entry");
621
test_foreach_safe ();
added
removed
nih/tests/test_hash.c
