1 /*
2 * Copyright (c) 2014-2019, NVIDIA CORPORATION. All rights reserved.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 *
16 */
17
18 #include "flang/ADT/hash.h"
19 #include "flang/Error/pgerror.h"
20 #include <stdlib.h>
21 #include <string.h>
22
23 #if UNIT_TESTING
24 #include <stdarg.h>
25 #include <stddef.h>
26 #include <setjmp.h>
27 #include "cmockery.h"
28 #endif /* UNIT_TESTING */
29
30 /** \file
31 * \brief Open addressing, quadratically probed hash tables.
32 *
33 * All keys are kept in a single array with 2^n entries. A key is first looked
34 * up at index hash(k) mod 2^k, then following a quadratic sequence of offsets.
35 * The quadratic probing has decent locality of reference for the first few
36 * probes.
37 *
38 * The search terminates when the key is found or a NULL is encountered. A
39 * special ERASED marker is used to avoid severing probe sequences when erasing
40 * keys.
41 */
42
43 #ifdef HOST_WIN
44 #define ERASED (hash_key_t) ~0ULL
45 #define LONG long long
46 #else
47 #define ERASED (hash_key_t) ~0UL
48 #define LONG long
49 #endif
50 #define ISKEY(k) ((k) != NULL && (k) != ERASED)
51
52 struct hashset_ {
53 hash_functions_t func;
54 hash_key_t *table;
55
56 /** Table size minus 1 is a bit mask. */
57 unsigned mask;
58
59 /** Number of ISKEY() entries in table. */
60 unsigned entries;
61
62 /** Number of ERASED entries in table. */
63 unsigned erased;
64 };
65
66 /** \brief A hashmap adds a table of data pointers after the hashset table. */
67 struct hashmap_ {
68 struct hashset_ set;
69 };
70
71 #define DTABLE(h) (((h)->table + 1) + (h)->mask)
72
73 /*
74 Quadrating probing sequence.
75
76 Given an initial hash value h, we probe at table indices
77
78 h, h+2, h+1+2, h+1+2+3, ... ( mod 2^n ), or
79
80 (i+1)i/2 ( mod 2^n ), for i = 0 .. 2^n.
81
82 This sequence visits the entire table without duplicates. Suppose two
83 indexes in the sequence are the same entry:
84
85 (i+1)i/2 = (j+1)j/2 ( mod 2^n )
86 ==> i^2 + i = j^2 + j ( mod 2^(n+1) )
87 ==> (i+j)(i-j) + i-j = 0 ( mod 2^(n+1) )
88 ==> (i+j+1)(i-j) = 0 ( mod 2^(n+1) )
89
90 Look at the difference of the factors on the left-hand side:
91
92 (i+j+1) - (i-j) = 2j + 1
93
94 This is an odd number, so one of the factors must be odd and thus coprime
95 with 2^(n+1). Therefore, 2^(n+1) must divide the other factor. The range of
96 the factors can be determined from the ranges of i and j:
97
98 1 <= i+j+1 <= 2^(n+1)-1, and
99 -(2^n-1) <= i-j <= 2^n-1.
100
101 The only way 2^(n+1) can divide one of the two factors is if 1 = j.
102
103 q.e.d.
104 */
105
106 /** \brief Search for key, return index that terminated the search. */
107 static unsigned
search(hashset_t h,hash_key_t key)108 search(hashset_t h, hash_key_t key)
109 {
110 unsigned p, s = 1;
111 hash_equality_t eq = h->func.equals;
112
113 assert(ISKEY(key), "Invalid key for hash", HKEY2INT(key), ERR_Fatal);
114
115 p = h->func.hash(key) & h->mask;
116 if (eq) {
117 /* General case where we have to call eq() to determine if keys are
118 * equivalent. */
119 while (h->table[p]) {
120 if (h->table[p] != ERASED && eq(key, h->table[p]))
121 break;
122 p = (p + s++) & h->mask;
123 }
124 } else {
125 /* Optimized case when eq is NULL and we simply test for pointer
126 * equality. */
127 while (h->table[p]) {
128 if (key == h->table[p])
129 break;
130 p = (p + s++) & h->mask;
131 }
132 }
133 return p;
134 }
135
136 /** \brief Find insertion point for key. */
137 static unsigned
insertion_point(hashset_t h,hash_key_t key)138 insertion_point(hashset_t h, hash_key_t key)
139 {
140 unsigned p, s = 1;
141
142 assert(ISKEY(key), "Invalid key for hash", HKEY2INT(key), ERR_Fatal);
143
144 p = h->func.hash(key) & h->mask;
145 while (ISKEY(h->table[p])) {
146 p = (p + s++) & h->mask;
147 }
148 return p;
149 }
150
151 /*
152 The number of NULL entries is kept above 1/8th of the whole table to avoid
153 too long probe sequences. The table is rehashed before the NULL entries drop
154 below that.
155
156 The ideal table size is the smallest power of two that keeps the load factor
157 below 2/3.
158 */
159
160 #define NEED_REHASH(h) ((h)->entries + (h)->erased >= (h)->mask - (h)->mask / 8)
161 #define MINSIZE 16
162
163 static unsigned
mask_for_entries(unsigned n)164 mask_for_entries(unsigned n)
165 {
166 unsigned m = (n + n / 2) | (MINSIZE - 1);
167
168 /* Arithmetic overflow happens after we have billions of entries. */
169 assert(m > n, "Hash table full", n, ERR_Fatal);
170
171 /* Round up to the next power of two minus one. */
172 m |= m >> 1;
173 m |= m >> 2;
174 m |= m >> 4;
175 m |= m >> 8;
176 m |= m >> 16;
177
178 return m;
179 }
180
181 /* Compute h->mask from h->entries and allocate table and dtable. */
182 static void
alloc_tables(hashset_t h,int with_dtable)183 alloc_tables(hashset_t h, int with_dtable)
184 {
185 h->mask = mask_for_entries(h->entries);
186
187 /* Allocate table + dtable in one calloc(). */
188 if (with_dtable)
189 h->table = (const void**) calloc(
190 1 + (size_t)h->mask, sizeof(hash_key_t) + sizeof(hash_data_t));
191 else
192 h->table = (const void**) calloc(1 + (size_t)h->mask, sizeof(hash_key_t));
193 }
194
195 /* Resize and rehash table to get rid of ERASED entries.
196
197 If not NULL, dtable points to a table of data entries that should be
198 rearranged the same way as h->table.
199 */
200 static void
rehash(hashset_t h,int with_dtable)201 rehash(hashset_t h, int with_dtable)
202 {
203 hash_key_t *old_table = h->table;
204 hash_data_t *old_dtable = DTABLE(h);
205 size_t n, old_size = 1 + (size_t)h->mask;
206 hash_data_t *new_dtable = NULL;
207
208 alloc_tables(h, with_dtable);
209 new_dtable = DTABLE(h);
210
211 /* There will be no ERASED markers after the rehash. */
212 h->erased = 0;
213
214 for (n = 0; n < old_size; n++) {
215 hash_key_t key = old_table[n];
216 if (ISKEY(key)) {
217 unsigned i = insertion_point(h, key);
218 h->table[i] = key;
219 if (with_dtable)
220 new_dtable[i] = old_dtable[n];
221 }
222 }
223
224 free((void*)old_table);
225 }
226
227 hashset_t
hashset_alloc(hash_functions_t f)228 hashset_alloc(hash_functions_t f)
229 {
230 hashset_t h = (hashset_t) calloc(1, sizeof(struct hashset_));
231 h->func = f;
232 alloc_tables(h, 0);
233 return h;
234 }
235
236 hashmap_t
hashmap_alloc(hash_functions_t f)237 hashmap_alloc(hash_functions_t f)
238 {
239 hashmap_t h = (hashmap_t) calloc(1, sizeof(struct hashmap_));
240 h->set.func = f;
241 alloc_tables(&h->set, 1);
242 return h;
243 }
244
245 void
hashset_free(hashset_t h)246 hashset_free(hashset_t h)
247 {
248 free((void*)h->table);
249 memset(h, 0, sizeof(*h));
250 free((void*)h);
251 }
252
253 void
hashmap_free(hashmap_t h)254 hashmap_free(hashmap_t h)
255 {
256 free((void*)h->set.table);
257 memset(h, 0, sizeof(*h));
258 free((void*)h);
259 }
260
261 void
hashset_clear(hashset_t h)262 hashset_clear(hashset_t h)
263 {
264 free((void*)h->table);
265 h->entries = h->erased = 0;
266 alloc_tables(h, 0);
267 }
268
269 void
hashmap_clear(hashmap_t h)270 hashmap_clear(hashmap_t h)
271 {
272 free((void*)h->set.table);
273 h->set.entries = h->set.erased = 0;
274 alloc_tables(&h->set, 1);
275 }
276
277 unsigned
hashset_size(hashset_t h)278 hashset_size(hashset_t h)
279 {
280 return h->entries;
281 }
282
283 unsigned
hashmap_size(hashmap_t h)284 hashmap_size(hashmap_t h)
285 {
286 return h->set.entries;
287 }
288
289 hash_key_t
hashset_lookup(hashset_t h,hash_key_t key)290 hashset_lookup(hashset_t h, hash_key_t key)
291 {
292 return h->table[search(h, key)];
293 }
294
295 hash_key_t
hashmap_lookup(hashmap_t h,hash_key_t key,hash_data_t * data)296 hashmap_lookup(hashmap_t h, hash_key_t key, hash_data_t *data)
297 {
298 unsigned i = search(&h->set, key);
299 hash_key_t k = h->set.table[i];
300 if (data && k)
301 *data = DTABLE(&h->set)[i];
302 return k;
303 }
304
305 void
hashset_insert(hashset_t h,hash_key_t key)306 hashset_insert(hashset_t h, hash_key_t key)
307 {
308 unsigned i;
309
310 #if DEBUG
311 assert(hashset_lookup(h, key) == NULL, "Duplicate hash key", 0, ERR_Fatal);
312 #endif
313
314 if (NEED_REHASH(h))
315 rehash(h, 0);
316
317 i = insertion_point(h, key);
318 if (h->table[i] == ERASED)
319 h->erased--;
320 h->table[i] = key;
321 h->entries++;
322 }
323
324 void
hashmap_insert(hashmap_t h,hash_key_t key,hash_data_t data)325 hashmap_insert(hashmap_t h, hash_key_t key, hash_data_t data)
326 {
327 unsigned i;
328
329 #if DEBUG
330 assert(hashmap_lookup(h, key, NULL) == NULL, "Duplicate hash key", 0, ERR_Fatal);
331 #endif
332
333 if (NEED_REHASH(&h->set))
334 rehash(&h->set, 1);
335
336 i = insertion_point(&h->set, key);
337 if (h->set.table[i] == ERASED)
338 h->set.erased--;
339 h->set.table[i] = key;
340 DTABLE(&h->set)[i] = data;
341 h->set.entries++;
342 }
343
344 hash_key_t
hashset_replace(hashset_t h,hash_key_t key)345 hashset_replace(hashset_t h, hash_key_t key)
346 {
347 unsigned i = search(h, key);
348 hash_key_t old = h->table[i];
349
350 if (ISKEY(old)) {
351 h->table[i] = key;
352 return old;
353 }
354
355 hashset_insert(h, key);
356 return NULL;
357 }
358
359 hash_key_t
hashmap_replace(hashmap_t h,hash_key_t key,hash_data_t * data)360 hashmap_replace(hashmap_t h, hash_key_t key, hash_data_t *data)
361 {
362 unsigned i = search(&h->set, key);
363 hash_key_t old = h->set.table[i];
364
365 if (ISKEY(old)) {
366 hash_data_t old_data = DTABLE(&h->set)[i];
367 h->set.table[i] = key;
368 DTABLE(&h->set)[i] = *data;
369 *data = old_data;
370 return old;
371 }
372
373 hashmap_insert(h, key, *data);
374 return NULL;
375 }
376
377 /* We never rehash while erasing elements. The rehash() at insertion can also
378 * shrink the table. */
379 hash_key_t
hashset_erase(hashset_t h,hash_key_t key)380 hashset_erase(hashset_t h, hash_key_t key)
381 {
382 unsigned i = search(h, key);
383 hash_key_t old = h->table[i];
384
385 if (!old)
386 return NULL;
387
388 h->table[i] = ERASED;
389 h->erased++;
390 h->entries--;
391 return old;
392 }
393
394 hash_key_t
hashmap_erase(hashmap_t h,hash_key_t key,hash_data_t * data)395 hashmap_erase(hashmap_t h, hash_key_t key, hash_data_t *data)
396 {
397 unsigned i = search(&h->set, key);
398 hash_key_t old = h->set.table[i];
399
400 if (!old)
401 return NULL;
402
403 h->set.table[i] = ERASED;
404 h->set.erased++;
405 h->set.entries--;
406 if (data)
407 *data = DTABLE(&h->set)[i];
408 return old;
409 }
410
411 void
hashset_iterate(hashset_t h,void (* f)(hash_key_t,void * context),void * context)412 hashset_iterate(hashset_t h, void (*f)(hash_key_t, void *context),
413 void *context)
414 {
415 size_t n, size = 1 + (size_t)h->mask;
416
417 for (n = 0; n < size; n++) {
418 hash_key_t key = h->table[n];
419 if (ISKEY(key))
420 f(key, context);
421 }
422 }
423
424
425 typedef struct {
426 hash_key_t table;
427 hash_data_t dtable;
428 } sortmap_t;
429
430 static int
string_cmp(sortmap_t * a,sortmap_t * b)431 string_cmp(sortmap_t* a, sortmap_t* b)
432 {
433 return strcmp((const char *)(a->table), (const char *)(b->table));
434 }
435
436 void
hashmap_sort(hashmap_t h,void (* f)(hash_key_t,hash_data_t,void * context),void * context)437 hashmap_sort(hashmap_t h, void (*f)(hash_key_t, hash_data_t, void *context),
438 void *context)
439 {
440 typedef int (*compare_func_t)(const void*, const void*);
441 size_t n,i, size = 1 + (size_t)h->set.mask;
442 size_t count = 0;
443 hash_data_t *dtable = DTABLE(&h->set);
444 sortmap_t *mysortmap;
445
446 for (n = 0; n < size; n++) {
447 hash_key_t key = h->set.table[n];
448 if (ISKEY(key))
449 count++;
450 }
451
452 mysortmap = (sortmap_t*) malloc(count * sizeof(sortmap_t));
453
454 i = 0;
455 for (n = 0; n < size; n++) {
456 hash_key_t key = h->set.table[n];
457 if (ISKEY(key)) {
458 mysortmap[i].table =(hash_key_t*)h->set.table[n];
459 mysortmap[i].dtable = dtable[n];
460 i++;
461 }
462 }
463
464 qsort(mysortmap, count, sizeof(sortmap_t), (compare_func_t)string_cmp);
465 for (n = 0; n < count; n++) {
466 f(mysortmap[n].table, mysortmap[n].dtable, context);
467 }
468
469 free(mysortmap);
470 }
471
472 void
hashmap_iterate(hashmap_t h,void (* f)(hash_key_t,hash_data_t,void * context),void * context)473 hashmap_iterate(hashmap_t h, void (*f)(hash_key_t, hash_data_t, void *context),
474 void *context)
475 {
476 size_t n, size = 1 + (size_t)h->set.mask;
477 hash_data_t *dtable = DTABLE(&h->set);
478
479 for (n = 0; n < size; n++) {
480 hash_key_t key = h->set.table[n];
481 if (ISKEY(key))
482 f(key, dtable[n], context);
483 }
484 }
485
486 /* String hashing */
487 static hash_value_t
string_hash(hash_key_t key)488 string_hash(hash_key_t key)
489 {
490 const unsigned char *p = (const unsigned char *)key;
491 hash_accu_t hacc = HASH_ACCU_INIT;
492 for (; *p; p++)
493 HASH_ACCU_ADD(hacc, *p);
494 HASH_ACCU_FINISH(hacc);
495 return HASH_ACCU_VALUE(hacc);
496 }
497
498 static int
string_equals(hash_key_t a,hash_key_t b)499 string_equals(hash_key_t a, hash_key_t b)
500 {
501 return strcmp((const char *)a, (const char *)b) == 0;
502 }
503
504 const hash_functions_t hash_functions_strings = {string_hash, string_equals};
505
506 /* Direct hashing. */
507 static hash_value_t
direct_hash(hash_key_t key)508 direct_hash(hash_key_t key)
509 {
510 unsigned LONG k = (unsigned LONG)key;
511 hash_accu_t hacc = HASH_ACCU_INIT;
512 HASH_ACCU_ADD(hacc, k);
513 /* On an LP64 system, this ignores the high 8 bits of k. That's OK if k
514 * represents a pointer, since current 64-bit systems don't use the high
515 * bits of addresses. A shift by 32 would be undefined when long is a
516 * 32-bit type. */
517 HASH_ACCU_ADD(hacc, k >> 24);
518 HASH_ACCU_FINISH(hacc);
519 return HASH_ACCU_VALUE(hacc);
520 }
521
522 const hash_functions_t hash_functions_direct = {direct_hash, NULL};
523
524 /* Everything below is only for testing the implementation. */
525 #if UNIT_TESTING
526
527 #include <stdio.h>
528
529 static void
table_size(void ** state)530 table_size(void **state)
531 {
532 assert_int_equal(mask_for_entries(0), 15);
533 assert_int_equal(mask_for_entries(1), 15);
534 assert_int_equal(mask_for_entries(10), 15);
535 assert_int_equal(mask_for_entries(11), 31);
536 assert_int_equal(mask_for_entries(20), 31);
537 assert_int_equal(mask_for_entries(21), 31);
538 assert_int_equal(mask_for_entries(22), 63);
539 assert_int_equal(mask_for_entries(0x80000000), 0xffffffff);
540 assert_int_equal(mask_for_entries(0xa0000000), 0xffffffff);
541 /* 0xb0000000 will overflow and assert, but expect_assert_failure()
542 * segfaults... */
543 }
544
545 static void
hash_funcs(void ** state)546 hash_funcs(void **state)
547 {
548 assert_int_equal(string_hash(""), 0);
549 assert_int_equal(string_hash("a"), 0xca2e9442);
550 assert_int_equal(string_hash("A"), 0x820103f0);
551 assert_int_equal(string_hash("foo"), 0x238678dd);
552
553 assert_int_equal(direct_hash((hash_key_t)0), 0);
554 assert_int_equal(direct_hash((hash_key_t)1), 0x20e9c0b3);
555 assert_int_equal(direct_hash((hash_key_t)2), 0x41d38166);
556 }
557
558 static void
basic_direct(void ** state)559 basic_direct(void **state)
560 {
561 unsigned LONG i;
562 hashset_t h = hashset_alloc(hash_functions_direct);
563 assert_true(h != NULL);
564 assert_int_equal(hashset_size(h), 0);
565 assert_int_equal(h->mask, MINSIZE - 1);
566
567 assert_int_equal(hashset_lookup(h, (hash_key_t)1), 0);
568 assert_int_equal(hashset_lookup(h, (hash_key_t)2), 0);
569
570 hashset_insert(h, (hash_key_t)1);
571 assert_int_equal(hashset_lookup(h, (hash_key_t)1), 1);
572 assert_int_equal(hashset_lookup(h, (hash_key_t)2), 0);
573
574 assert_int_equal(hashset_replace(h, (hash_key_t)1), 1);
575 assert_int_equal(hashset_replace(h, (hash_key_t)2), 0);
576
577 for (i = 3; i <= 14; i++)
578 hashset_insert(h, (hash_key_t)i);
579
580 /* Table has 16 entries, 2 are NULL for exactly 7/8 load factor. */
581 assert_int_equal(hashset_size(h), 14);
582 assert_int_equal(h->mask, MINSIZE - 1);
583
584 /* Trigger a rehash when we add the 15th element. */
585 hashset_insert(h, (hash_key_t)15);
586 assert_int_equal(hashset_size(h), 15);
587 assert_int_equal(h->mask, 2 * MINSIZE - 1);
588
589 /* Remove odd entries. */
590 for (i = 1; i <= 15; i += 2)
591 assert_int_equal(hashset_erase(h, (hash_key_t)i), i);
592 assert_int_equal(hashset_size(h), 7);
593 assert_int_equal(h->mask, 2 * MINSIZE - 1);
594 assert_int_equal(h->erased, 8);
595
596 /* Remove everything. */
597 for (i = 1; i <= 15; i++)
598 assert_int_equal(hashset_erase(h, (hash_key_t)i), i % 2 ? 0 : i);
599
600 /* Set is empty, but hasn't rehashed yet. */
601 assert_int_equal(hashset_size(h), 0);
602 assert_int_equal(h->mask, 2 * MINSIZE - 1);
603 assert_int_equal(h->erased, 15);
604
605 for (i = 1; i <= 20; i++)
606 assert_int_equal(hashset_erase(h, (hash_key_t)i), 0);
607 assert_int_equal(hashset_size(h), 0);
608 assert_int_equal(h->mask, 2 * MINSIZE - 1);
609
610 /* Insert triggers a table shrink. Eventually. The exact timing depends on
611 * the hash function behavior. */
612 for (i = 1; i <= 10; i++)
613 hashset_insert(h, (hash_key_t)(100 + i));
614 assert_int_equal(h->mask, 2 * MINSIZE - 1);
615 for (i = 1; i <= 10; i++)
616 hashset_erase(h, (hash_key_t)(100 + i));
617 assert_int_equal(h->mask, 2 * MINSIZE - 1);
618 for (i = 1; i <= 10; i++)
619 hashset_insert(h, (hash_key_t)(200 + i));
620 assert_int_equal(h->mask, 2 * MINSIZE - 1);
621 for (i = 1; i <= 10; i++)
622 hashset_erase(h, (hash_key_t)(200 + i));
623 assert_int_equal(h->mask, 2 * MINSIZE - 1);
624 for (i = 1; i <= 10; i++)
625 hashset_insert(h, (hash_key_t)(300 + i));
626 assert_int_equal(h->mask, 2 * MINSIZE - 1);
627 for (i = 1; i <= 10; i++)
628 hashset_erase(h, (hash_key_t)(300 + i));
629 assert_int_equal(h->mask, 2 * MINSIZE - 1);
630 for (i = 1; i <= 10; i++)
631 hashset_insert(h, (hash_key_t)(400 + i));
632 assert_int_equal(h->erased, 0);
633 assert_int_equal(h->mask, MINSIZE - 1);
634
635 hashset_free(h);
636 }
637
638 static void
free_iterator(hash_key_t key,void * context)639 free_iterator(hash_key_t key, void *context)
640 {
641 ++*(unsigned *)context;
642 free((void *)key);
643 }
644
645 static void
basic_string(void ** state)646 basic_string(void **state)
647 {
648 unsigned i;
649 hashset_t h = hashset_alloc(hash_functions_strings);
650 const char *strs[] = {"foo", "bar", "baz", "quux"};
651 char buf[20];
652
653 for (i = 0; i != 4; i++)
654 hashset_insert(h, (hash_key_t)strs[i]);
655
656 strcpy(buf, "foo");
657 assert_int_equal(hashset_lookup(h, buf), strs[0]);
658 strcpy(buf, "fooo");
659 assert_int_not_equal(hashset_lookup(h, buf), strs[0]);
660
661 for (i = 0; i < 1000; i++) {
662 char *x = malloc(10);
663 sprintf(x, "x%d", i);
664 hashset_insert(h, x);
665 }
666
667 for (i = 0; i != 4; i++)
668 hashset_erase(h, (hash_key_t)strs[i]);
669
670 i = 0;
671 assert_int_equal(hashset_size(h), 1000);
672 hashset_iterate(h, free_iterator, &i);
673 assert_int_equal(i, 1000);
674
675 hashset_free(h);
676 }
677
678 static hash_value_t
worst_hash_ever(hash_key_t key)679 worst_hash_ever(hash_key_t key)
680 {
681 return 42;
682 }
683
684 static const hash_functions_t hash_functions_worst = {worst_hash_ever, NULL};
685
686 static void
worst_case(void ** state)687 worst_case(void **state)
688 {
689 unsigned LONG i;
690 hashset_t h = hashset_alloc(hash_functions_worst);
691
692 for (i = 1; i <= 14; i++)
693 hashset_insert(h, (hash_key_t)i);
694
695 /* Table has 16 entries, 2 are NULL for exactly 7/8 load factor. */
696 assert_int_equal(hashset_size(h), 14);
697 assert_int_equal(h->mask, MINSIZE - 1);
698
699 /* The bad hash function stresses the probing sequence to find the NULLS.
700 * The insert and the lookup can both loop infinitely if their probing
701 * sequence doesn't completely cover the table. */
702 for (i = 15; i <= 1000; i++)
703 hashset_insert(h, (hash_key_t)i);
704
705 for (i = 1; i <= 2000; i += 100)
706 assert_int_equal(hashset_lookup(h, (hash_key_t)i), i <= 1000 ? i : 0);
707
708 hashset_free(h);
709 }
710
711 static void
basic_map(void ** state)712 basic_map(void **state)
713 {
714 hashmap_t h = hashmap_alloc(hash_functions_direct);
715 hash_data_t datum;
716 const char *s1 = "foo", *s2 = "bar";
717 unsigned LONG i;
718
719 assert_int_equal(hashmap_size(h), 0);
720
721 /* Lookup nonexistent data with NULL data pointer. */
722 assert_int_equal(hashmap_lookup(h, (hash_key_t)1, NULL), 0);
723
724 /* Lookup nonexistent data with non-NULL data pointer. */
725 datum = &h;
726 assert_int_equal(hashmap_lookup(h, (hash_key_t)1, &datum), 0);
727 assert_int_equal(datum, &h);
728
729 hashmap_insert(h, (hash_key_t)1, (hash_data_t)s1);
730 hashmap_insert(h, (hash_key_t)2, (hash_data_t)s2);
731
732 /* We support lookup with NULL data pointer. */
733 assert_int_equal(hashmap_lookup(h, (hash_key_t)1, NULL), 1);
734
735 datum = (hash_data_t)s2;
736 assert_int_equal(hashmap_lookup(h, (hash_key_t)1, &datum), 1);
737 assert_int_equal(datum, s1);
738
739 /* Replace where no previous key existed. */
740 datum = (hash_data_t)s2;
741 assert_int_equal(hashmap_replace(h, (hash_key_t)3, &datum), 0);
742 assert_int_equal(datum, s2);
743
744 /* Replace previous key. Should return previous data. */
745 datum = (hash_data_t)s1;
746 assert_int_equal(hashmap_replace(h, (hash_key_t)3, &datum), 3);
747 assert_int_equal(datum, s2);
748
749 /* Force rehash. Verify that data entries are copied correctly. */
750 for (i = 1; i < 100; i++) {
751 datum = (hash_data_t)(i % 7);
752 hashmap_replace(h, (hash_key_t)i, &datum);
753 }
754 for (i = 1; i < 100; i++) {
755 assert_int_equal(hashmap_lookup(h, (hash_key_t)i, &datum), i);
756 assert_int_equal(datum, i % 7);
757 }
758
759 hashmap_free(h);
760 }
761
762 int
main()763 main()
764 {
765 const UnitTest tests[] = {
766 unit_test(table_size), unit_test(hash_funcs), unit_test(basic_direct),
767 unit_test(basic_string), unit_test(worst_case), unit_test(basic_map),
768 };
769 return run_tests(tests);
770 }
771
772 #endif /* UNIT_TESTING */
773