src/util/hashset.c
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include <errno.h> | ||
| 2 | #include <stdlib.h> | ||
| 3 | #include <string.h> | ||
| 4 | #include "hashset.h" | ||
| 5 | #include "bit.h" | ||
| 6 | #include "debug.h" | ||
| 7 | #include "hash.h" | ||
| 8 | #include "xmalloc.h" | ||
| 9 | |||
| 10 | 156 | static void alloc_table(HashSet *set, size_t size) | |
| 11 | { | ||
| 12 | 156 | BUG_ON(size < 8); | |
| 13 | 156 | BUG_ON(!IS_POWER_OF_2(size)); | |
| 14 | 156 | set->table_size = size; | |
| 15 | 156 | set->table = xcalloc(size, sizeof(set->table[0])); | |
| 16 | 156 | set->grow_at = size - (size / 4); // 75% load factor (size * 0.75) | |
| 17 | 156 | } | |
| 18 | |||
| 19 | 141 | HashSet hashset_new(size_t size, bool icase) | |
| 20 | { | ||
| 21 | 141 | size = MAX(size, 8); | |
| 22 | |||
| 23 | // Accommodate the 75% load factor in the table size, to allow filling | ||
| 24 | // the set to the requested size without needing to rehash() | ||
| 25 | 141 | size += size / 3; | |
| 26 | |||
| 27 | // Round up the allocation to the next power of 2, to allow using | ||
| 28 | // simple bitwise ops (instead of modulo) in get_slot() | ||
| 29 | 141 | size = next_pow2(size); | |
| 30 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 141 times.
|
141 | FATAL_ERROR_ON(size == 0, EOVERFLOW); |
| 31 | |||
| 32 | 141 | HashSet set; | |
| 33 | 141 | alloc_table(&set, size); | |
| 34 | 141 | set.nr_entries = 0; | |
| 35 | 141 | set.icase = icase; | |
| 36 | 141 | return set; | |
| 37 | } | ||
| 38 | |||
| 39 | 142 | void hashset_free(HashSet *set) | |
| 40 | { | ||
| 41 |
2/2✓ Branch 7 → 3 taken 10352 times.
✓ Branch 7 → 8 taken 142 times.
|
10494 | for (size_t i = 0, n = set->table_size; i < n; i++) { |
| 42 | 10352 | HashSetEntry *h = set->table[i]; | |
| 43 |
2/2✓ Branch 5 → 4 taken 4796 times.
✓ Branch 5 → 6 taken 10352 times.
|
15148 | while (h) { |
| 44 | 4796 | HashSetEntry *next = h->next; | |
| 45 | 4796 | free(h); | |
| 46 | 4796 | h = next; | |
| 47 | } | ||
| 48 | } | ||
| 49 | |||
| 50 | 142 | free(set->table); | |
| 51 | 142 | } | |
| 52 | |||
| 53 | 14440 | static size_t get_slot(const HashSet *set, StringView str) | |
| 54 | { | ||
| 55 |
2/2✓ Branch 2 → 3 taken 2792 times.
✓ Branch 2 → 4 taken 11648 times.
|
14440 | size_t hash = set->icase ? fnv_1a_hash_icase(str) : fnv_1a_hash(str); |
| 56 | 14440 | return hash & (set->table_size - 1); | |
| 57 | } | ||
| 58 | |||
| 59 | 8441 | HashSetEntry *hashset_get(const HashSet *set, StringView str) | |
| 60 | { | ||
| 61 |
2/2✓ Branch 2 → 3 taken 1398 times.
✓ Branch 2 → 9 taken 7043 times.
|
8441 | if (set->icase) { |
| 62 | 1398 | size_t slot = get_slot(set, str); | |
| 63 |
2/2✓ Branch 8 → 5 taken 375 times.
✓ Branch 8 → 15 taken 1394 times.
|
1769 | for (HashSetEntry *h = set->table[slot]; h; h = h->next) { |
| 64 |
2/2✓ Branch 6 → 7 taken 371 times.
✓ Branch 6 → 15 taken 4 times.
|
375 | if (strview_equal_icase(str, string_view(h->str, h->str_len))) { |
| 65 | return h; | ||
| 66 | } | ||
| 67 | } | ||
| 68 | } else { | ||
| 69 | 7043 | size_t slot = get_slot(set, str); | |
| 70 |
2/2✓ Branch 14 → 11 taken 5093 times.
✓ Branch 14 → 15 taken 3504 times.
|
8597 | for (HashSetEntry *h = set->table[slot]; h; h = h->next) { |
| 71 |
2/2✓ Branch 12 → 13 taken 1554 times.
✓ Branch 12 → 15 taken 3539 times.
|
5093 | if (strview_equal(str, string_view(h->str, h->str_len))) { |
| 72 | return h; | ||
| 73 | } | ||
| 74 | } | ||
| 75 | } | ||
| 76 | |||
| 77 | return NULL; | ||
| 78 | } | ||
| 79 | |||
| 80 | 15 | static void rehash(HashSet *set, size_t newsize) | |
| 81 | { | ||
| 82 | 15 | size_t oldsize = set->table_size; | |
| 83 | 15 | HashSetEntry **oldtable = set->table; | |
| 84 | 15 | alloc_table(set, newsize); | |
| 85 | |||
| 86 |
2/2✓ Branch 9 → 4 taken 1584 times.
✓ Branch 9 → 10 taken 15 times.
|
1614 | for (size_t i = 0; i < oldsize; i++) { |
| 87 | 1584 | HashSetEntry *e = oldtable[i]; | |
| 88 |
2/2✓ Branch 7 → 5 taken 1203 times.
✓ Branch 7 → 8 taken 1584 times.
|
2787 | while (e) { |
| 89 | 1203 | HashSetEntry *next = e->next; | |
| 90 | 1203 | const size_t slot = get_slot(set, string_view(e->str, e->str_len)); | |
| 91 | 1203 | e->next = set->table[slot]; | |
| 92 | 1203 | set->table[slot] = e; | |
| 93 | 1203 | e = next; | |
| 94 | } | ||
| 95 | } | ||
| 96 | |||
| 97 | 15 | free(oldtable); | |
| 98 | 15 | } | |
| 99 | |||
| 100 | 7272 | HashSetEntry *hashset_insert(HashSet *set, StringView str) | |
| 101 | { | ||
| 102 | 7272 | HashSetEntry *h = hashset_get(set, str); | |
| 103 |
2/2✓ Branch 3 → 4 taken 4796 times.
✓ Branch 3 → 11 taken 2476 times.
|
7272 | if (h) { |
| 104 | return h; | ||
| 105 | } | ||
| 106 | |||
| 107 | 4796 | const size_t slot = get_slot(set, str); | |
| 108 | 4796 | h = xmalloc(xadd3(sizeof(*h), str.length, 1)); | |
| 109 | 4796 | h->next = set->table[slot]; | |
| 110 | 4796 | h->str_len = str.length; | |
| 111 | 4796 | memcpy(h->str, str.data, str.length); | |
| 112 | 4796 | h->str[str.length] = '\0'; | |
| 113 | 4796 | set->table[slot] = h; | |
| 114 | |||
| 115 |
2/2✓ Branch 7 → 8 taken 15 times.
✓ Branch 7 → 11 taken 4781 times.
|
4796 | if (++set->nr_entries > set->grow_at) { |
| 116 | 15 | size_t new_size = set->table_size << 1; | |
| 117 |
1/2✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 15 times.
|
15 | FATAL_ERROR_ON(new_size == 0, EOVERFLOW); |
| 118 | 15 | rehash(set, new_size); | |
| 119 | } | ||
| 120 | |||
| 121 | return h; | ||
| 122 | } | ||
| 123 |