dte test coverage

Directory: ./
File: src/util/hashset.c
Date: 2025-10-16 19:09:21
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 "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 4717 times.
✓ Branch 1 (5→6) taken 10336 times.
 15053 while (h) {
50 4717 HashSetEntry *next = h->next;
51 4717 free(h);
52 4717 h = next;
53 }
54 }
55 142 free(set->table);
56 142 }
57
58 12787 static size_t get_slot(const HashSet *set, const char *str, size_t str_len)
59 {
60 12787 const size_t hash = set->hash(str, str_len);
61 12787 return hash & (set->table_size - 1);
62 }
63
64 6867 HashSetEntry *hashset_get(const HashSet *set, const char *str, size_t str_len)
65 {
66 6867 const size_t slot = get_slot(set, str, str_len);
67 6867 HashSetEntry *h = set->table[slot];
68
2/2
✓ Branch 0 (8→4) taken 3707 times.
✓ Branch 1 (8→9) taken 4818 times.
 8525 while (h) {
69
4/4
✓ Branch 0 (4→5) taken 2229 times.
✓ Branch 1 (4→7) taken 1478 times.
✓ Branch 2 (6→7) taken 180 times.
✓ Branch 3 (6→9) taken 2049 times.
 3707 if (str_len == h->str_len && set->equal(str, h->str, str_len)) {
70 return h;
71 }
72 1658 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 6726 HashSetEntry *hashset_insert(HashSet *set, const char *str, size_t str_len)
96 {
97 6726 HashSetEntry *h = hashset_get(set, str, str_len);
98
2/2
✓ Branch 0 (3→4) taken 4717 times.
✓ Branch 1 (3→11) taken 2009 times.
 6726 if (h) {
99 return h;
100 }
101
102 4717 const size_t slot = get_slot(set, str, str_len);
103 4717 h = xmalloc(xadd3(sizeof(*h), str_len, 1));
104 4717 h->next = set->table[slot];
105 4717 h->str_len = str_len;
106 4717 memcpy(h->str, str, str_len);
107 4717 h->str[str_len] = '\0';
108 4717 set->table[slot] = h;
109
110
2/2
✓ Branch 0 (7→8) taken 15 times.
✓ Branch 1 (7→11) taken 4702 times.
 4717 if (++set->nr_entries > set->grow_at) {
111 15 size_t new_size = set->table_size << 1;
112
1/2
✗ Branch 0 (8→9) not taken.
✓ Branch 1 (8→10) taken 15 times.
 15 FATAL_ERROR_ON(new_size == 0, EOVERFLOW);
113 15 rehash(set, new_size);
114 }
115
116 return h;
117 }
118