dte test coverage

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 50.0% high: ≥ 85.0%
Coverage Exec / Excl / Total
Lines: 100.0% 67 / 0 / 67
Functions: 100.0% 7 / 0 / 7
Branches: 91.7% 22 / 4 / 28
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 #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 HashSet hashset_new(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 2 → 3 not taken.
✓ Branch 2 → 4 taken 141 times.
 141 FATAL_ERROR_ON(size == 0, EOVERFLOW);
32
33 141 HashSet set;
34 141 alloc_table(&set, size);
35 141 set.nr_entries = 0;
36
37
2/2
✓ Branch 5 → 6 taken 21 times.
✓ Branch 5 → 7 taken 120 times.
 141 if (icase) {
38 21 set.hash = fnv_1a_hash_icase;
39 21 set.equal = mem_equal_icase;
40 } else {
41 120 set.hash = fnv_1a_hash;
42 120 set.equal = mem_equal;
43 }
44
45 141 return set;
46 }
47
48 142 void hashset_free(HashSet *set)
49 {
50
2/2
✓ Branch 7 → 3 taken 10336 times.
✓ Branch 7 → 8 taken 142 times.
 10478 for (size_t i = 0, n = set->table_size; i < n; i++) {
51 10336 HashSetEntry *h = set->table[i];
52
2/2
✓ Branch 5 → 4 taken 4783 times.
✓ Branch 5 → 6 taken 10336 times.
 15119 while (h) {
53 4783 HashSetEntry *next = h->next;
54 4783 free(h);
55 4783 h = next;
56 }
57 }
58 142 free(set->table);
59 142 }
60
61 14414 static size_t get_slot(const HashSet *set, const char *str, size_t str_len)
62 {
63 14414 const size_t hash = set->hash(str, str_len);
64 14414 return hash & (set->table_size - 1);
65 }
66
67 8428 HashSetEntry *hashset_get(const HashSet *set, const char *str, size_t str_len)
68 {
69 8428 const size_t slot = get_slot(set, str, str_len);
70 8428 HashSetEntry *h = set->table[slot];
71
2/2
✓ Branch 8 → 4 taken 5446 times.
✓ Branch 8 → 9 taken 4885 times.
 10331 while (h) {
72
4/4
✓ Branch 4 → 5 taken 3719 times.
✓ Branch 4 → 7 taken 1727 times.
✓ Branch 6 → 7 taken 176 times.
✓ Branch 6 → 9 taken 3543 times.
 5446 if (str_len == h->str_len && set->equal(str, h->str, str_len)) {
73 return h;
74 }
75 1903 h = h->next;
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
2/2
✓ Branch 9 → 4 taken 1584 times.
✓ Branch 9 → 10 taken 15 times.
 1614 for (size_t i = 0; i < oldsize; i++) {
86 1584 HashSetEntry *e = oldtable[i];
87
2/2
✓ Branch 7 → 5 taken 1203 times.
✓ Branch 7 → 8 taken 1584 times.
 2787 while (e) {
88 1203 HashSetEntry *next = e->next;
89 1203 const size_t slot = get_slot(set, e->str, e->str_len);
90 1203 e->next = set->table[slot];
91 1203 set->table[slot] = e;
92 1203 e = next;
93 }
94 }
95 15 free(oldtable);
96 15 }
97
98 7259 HashSetEntry *hashset_insert(HashSet *set, const char *str, size_t str_len)
99 {
100 7259 HashSetEntry *h = hashset_get(set, str, str_len);
101
2/2
✓ Branch 3 → 4 taken 4783 times.
✓ Branch 3 → 11 taken 2476 times.
 7259 if (h) {
102 return h;
103 }
104
105 4783 const size_t slot = get_slot(set, str, str_len);
106 4783 h = xmalloc(xadd3(sizeof(*h), str_len, 1));
107 4783 h->next = set->table[slot];
108 4783 h->str_len = str_len;
109 4783 memcpy(h->str, str, str_len);
110 4783 h->str[str_len] = '\0';
111 4783 set->table[slot] = h;
112
113
2/2
✓ Branch 7 → 8 taken 15 times.
✓ Branch 7 → 11 taken 4768 times.
 4783 if (++set->nr_entries > set->grow_at) {
114 15 size_t new_size = set->table_size << 1;
115
1/2
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 15 times.
 15 FATAL_ERROR_ON(new_size == 0, EOVERFLOW);
116 15 rehash(set, new_size);
117 }
118
119 return h;
120 }
121