dte test coverage

Directory: ./
File: src/util/hashset.c
Date: 2024-12-21 16:03:22
Exec Total Coverage
Lines: 66 66 100.0%
Functions: 7 7 100.0%
Branches: 22 24 91.7%
Line Branch Exec Source
1 #include <errno.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include "hashset.h"
5 #include "debug.h"
6 #include "hash.h"
7 #include "xmalloc.h"
8 #include "xstring.h"
9
10 136 static void alloc_table(HashSet *set, size_t size)
11 {
12 136 BUG_ON(size < 8);
13 136 BUG_ON(!IS_POWER_OF_2(size));
14 136 set->table_size = size;
15 136 set->table = xnew0(HashSetEntry*, size);
16 136 set->grow_at = size - (size / 4); // 75% load factor (size * 0.75)
17 136 }
18
19 125 void hashset_init(HashSet *set, size_t size, bool icase)
20 {
21 125 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 125 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 125 size = round_size_to_next_power_of_2(size);
30
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 125 times.
 125 if (unlikely(size == 0)) {
31 − fatal_error(__func__, EOVERFLOW);
32 }
33
34 125 alloc_table(set, size);
35 125 set->nr_entries = 0;
36
37
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 104 times.
 125 if (icase) {
38 21 set->hash = fnv_1a_hash_icase;
39 21 set->equal = mem_equal_icase;
40 } else {
41 104 set->hash = fnv_1a_hash;
42 104 set->equal = mem_equal;
43 }
44 125 }
45
46 125 void hashset_free(HashSet *set)
47 {
48
2/2
✓ Branch 0 taken 9072 times.
✓ Branch 1 taken 125 times.
 9197 for (size_t i = 0, n = set->table_size; i < n; i++) {
49 9072 HashSetEntry *h = set->table[i];
50
2/2
✓ Branch 0 taken 4199 times.
✓ Branch 1 taken 9072 times.
 13271 while (h) {
51 4199 HashSetEntry *next = h->next;
52 4199 free(h);
53 4199 h = next;
54 }
55 }
56 125 free(set->table);
57 125 }
58
59 9742 static size_t get_slot(const HashSet *set, const char *str, size_t str_len)
60 {
61 9742 const size_t hash = set->hash(str, str_len);
62 9742 return hash & (set->table_size - 1);
63 }
64
65 4872 HashSetEntry *hashset_get(const HashSet *set, const char *str, size_t str_len)
66 {
67 4872 const size_t slot = get_slot(set, str, str_len);
68 4872 HashSetEntry *h = set->table[slot];
69
2/2
✓ Branch 0 taken 1837 times.
✓ Branch 1 taken 4299 times.
 6136 while (h) {
70
4/4
✓ Branch 0 taken 745 times.
✓ Branch 1 taken 1092 times.
✓ Branch 2 taken 172 times.
✓ Branch 3 taken 573 times.
 1837 if (str_len == h->str_len && set->equal(str, h->str, str_len)) {
71 return h;
72 }
73 1264 h = h->next;
74 }
75 return NULL;
76 }
77
78 11 static void rehash(HashSet *set, size_t newsize)
79 {
80 11 size_t oldsize = set->table_size;
81 11 HashSetEntry **oldtable = set->table;
82 11 alloc_table(set, newsize);
83
2/2
✓ Branch 0 taken 880 times.
✓ Branch 1 taken 11 times.
 891 for (size_t i = 0; i < oldsize; i++) {
84 880 HashSetEntry *e = oldtable[i];
85
2/2
✓ Branch 0 taken 671 times.
✓ Branch 1 taken 880 times.
 1551 while (e) {
86 671 HashSetEntry *next = e->next;
87 671 const size_t slot = get_slot(set, e->str, e->str_len);
88 671 e->next = set->table[slot];
89 671 set->table[slot] = e;
90 671 e = next;
91 }
92 }
93 11 free(oldtable);
94 11 }
95
96 4736 HashSetEntry *hashset_insert(HashSet *set, const char *str, size_t str_len)
97 {
98 4736 HashSetEntry *h = hashset_get(set, str, str_len);
99
2/2
✓ Branch 0 taken 4199 times.
✓ Branch 1 taken 537 times.
 4736 if (h) {
100 return h;
101 }
102
103 4199 const size_t slot = get_slot(set, str, str_len);
104 4199 h = xmalloc(sizeof(*h) + str_len + 1);
105 4199 h->next = set->table[slot];
106 4199 h->str_len = str_len;
107 4199 memcpy(h->str, str, str_len);
108 4199 h->str[str_len] = '\0';
109 4199 set->table[slot] = h;
110
111
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 4188 times.
 4199 if (++set->nr_entries > set->grow_at) {
112 11 size_t new_size = set->table_size << 1;
113
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 11 times.
 11 if (unlikely(new_size == 0)) {
114 − fatal_error(__func__, EOVERFLOW);
115 }
116 11 rehash(set, new_size);
117 }
118
119 return h;
120 }
121