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 | #include "xstring.h" | ||
10 | |||
11 | 156 | static void alloc_table(HashSet *set, size_t size) | |
12 | { | ||
13 | 156 | BUG_ON(size < 8); | |
14 | 156 | BUG_ON(!IS_POWER_OF_2(size)); | |
15 | 156 | set->table_size = size; | |
16 | 156 | set->table = xcalloc(size, sizeof(set->table[0])); | |
17 | 156 | set->grow_at = size - (size / 4); // 75% load factor (size * 0.75) | |
18 | 156 | } | |
19 | |||
20 | 141 | void hashset_init(HashSet *set, size_t size, bool icase) | |
21 | { | ||
22 | 141 | size = MAX(size, 8); | |
23 | |||
24 | // Accommodate the 75% load factor in the table size, to allow filling | ||
25 | // the set to the requested size without needing to rehash() | ||
26 | 141 | size += size / 3; | |
27 | |||
28 | // Round up the allocation to the next power of 2, to allow using | ||
29 | // simple bitwise ops (instead of modulo) in get_slot() | ||
30 | 141 | size = next_pow2(size); | |
31 |
1/2✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 141 times.
|
141 | FATAL_ERROR_ON(size == 0, EOVERFLOW); |
32 | |||
33 | 141 | alloc_table(set, size); | |
34 | 141 | set->nr_entries = 0; | |
35 | |||
36 |
2/2✓ Branch 0 (5→6) taken 21 times.
✓ Branch 1 (5→7) taken 120 times.
|
141 | if (icase) { |
37 | 21 | set->hash = fnv_1a_hash_icase; | |
38 | 21 | set->equal = mem_equal_icase; | |
39 | } else { | ||
40 | 120 | set->hash = fnv_1a_hash; | |
41 | 120 | set->equal = mem_equal; | |
42 | } | ||
43 | 141 | } | |
44 | |||
45 | 142 | void hashset_free(HashSet *set) | |
46 | { | ||
47 |
2/2✓ Branch 0 (7→3) taken 10336 times.
✓ Branch 1 (7→8) taken 142 times.
|
10478 | for (size_t i = 0, n = set->table_size; i < n; i++) { |
48 | 10336 | HashSetEntry *h = set->table[i]; | |
49 |
2/2✓ Branch 0 (5→4) taken 4706 times.
✓ Branch 1 (5→6) taken 10336 times.
|
15042 | while (h) { |
50 | 4706 | HashSetEntry *next = h->next; | |
51 | 4706 | free(h); | |
52 | 4706 | h = next; | |
53 | } | ||
54 | } | ||
55 | 142 | free(set->table); | |
56 | 142 | } | |
57 | |||
58 | 12763 | static size_t get_slot(const HashSet *set, const char *str, size_t str_len) | |
59 | { | ||
60 | 12763 | const size_t hash = set->hash(str, str_len); | |
61 | 12763 | return hash & (set->table_size - 1); | |
62 | } | ||
63 | |||
64 | 6854 | HashSetEntry *hashset_get(const HashSet *set, const char *str, size_t str_len) | |
65 | { | ||
66 | 6854 | const size_t slot = get_slot(set, str, str_len); | |
67 | 6854 | HashSetEntry *h = set->table[slot]; | |
68 |
2/2✓ Branch 0 (8→4) taken 3672 times.
✓ Branch 1 (8→9) taken 4807 times.
|
8479 | while (h) { |
69 |
4/4✓ Branch 0 (4→5) taken 2228 times.
✓ Branch 1 (4→7) taken 1444 times.
✓ Branch 2 (6→7) taken 181 times.
✓ Branch 3 (6→9) taken 2047 times.
|
3672 | if (str_len == h->str_len && set->equal(str, h->str, str_len)) { |
70 | return h; | ||
71 | } | ||
72 | 1625 | h = h->next; | |
73 | } | ||
74 | return NULL; | ||
75 | } | ||
76 | |||
77 | 15 | static void rehash(HashSet *set, size_t newsize) | |
78 | { | ||
79 | 15 | size_t oldsize = set->table_size; | |
80 | 15 | HashSetEntry **oldtable = set->table; | |
81 | 15 | alloc_table(set, newsize); | |
82 |
2/2✓ Branch 0 (9→4) taken 1584 times.
✓ Branch 1 (9→10) taken 15 times.
|
1599 | for (size_t i = 0; i < oldsize; i++) { |
83 | 1584 | HashSetEntry *e = oldtable[i]; | |
84 |
2/2✓ Branch 0 (7→5) taken 1203 times.
✓ Branch 1 (7→8) taken 1584 times.
|
2787 | while (e) { |
85 | 1203 | HashSetEntry *next = e->next; | |
86 | 1203 | const size_t slot = get_slot(set, e->str, e->str_len); | |
87 | 1203 | e->next = set->table[slot]; | |
88 | 1203 | set->table[slot] = e; | |
89 | 1203 | e = next; | |
90 | } | ||
91 | } | ||
92 | 15 | free(oldtable); | |
93 | 15 | } | |
94 | |||
95 | 6713 | HashSetEntry *hashset_insert(HashSet *set, const char *str, size_t str_len) | |
96 | { | ||
97 | 6713 | HashSetEntry *h = hashset_get(set, str, str_len); | |
98 |
2/2✓ Branch 0 (3→4) taken 4706 times.
✓ Branch 1 (3→10) taken 2007 times.
|
6713 | if (h) { |
99 | return h; | ||
100 | } | ||
101 | |||
102 | 4706 | const size_t slot = get_slot(set, str, str_len); | |
103 | 4706 | h = xmalloc(sizeof(*h) + str_len + 1); | |
104 | 4706 | h->next = set->table[slot]; | |
105 | 4706 | h->str_len = str_len; | |
106 | 4706 | memcpy(h->str, str, str_len); | |
107 | 4706 | h->str[str_len] = '\0'; | |
108 | 4706 | set->table[slot] = h; | |
109 | |||
110 |
2/2✓ Branch 0 (6→7) taken 15 times.
✓ Branch 1 (6→10) taken 4691 times.
|
4706 | if (++set->nr_entries > set->grow_at) { |
111 | 15 | size_t new_size = set->table_size << 1; | |
112 |
1/2✗ Branch 0 (7→8) not taken.
✓ Branch 1 (7→9) taken 15 times.
|
15 | FATAL_ERROR_ON(new_size == 0, EOVERFLOW); |
113 | 15 | rehash(set, new_size); | |
114 | } | ||
115 | |||
116 | return h; | ||
117 | } | ||
118 |