dte test coverage

Directory: ./
File: src/util/hashset.c
Date: 2025-05-08 15:05:54
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 144 static void alloc_table(HashSet *set, size_t size)
12 {
13 144 BUG_ON(size < 8);
14 144 BUG_ON(!IS_POWER_OF_2(size));
15 144 set->table_size = size;
16 144 set->table = xcalloc(size, sizeof(set->table[0]));
17 144 set->grow_at = size - (size / 4); // 75% load factor (size * 0.75)
18 144 }
19
20 131 void hashset_init(HashSet *set, size_t size, bool icase)
21 {
22 131 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 131 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 131 size = next_pow2(size);
31
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 131 times.
 131 if (unlikely(size == 0)) {
32 − fatal_error(__func__, EOVERFLOW);
33 }
34
35 131 alloc_table(set, size);
36 131 set->nr_entries = 0;
37
38
2/2
✓ Branch 0 (6→7) taken 21 times.
✓ Branch 1 (6→8) taken 110 times.
 131 if (icase) {
39 21 set->hash = fnv_1a_hash_icase;
40 21 set->equal = mem_equal_icase;
41 } else {
42 110 set->hash = fnv_1a_hash;
43 110 set->equal = mem_equal;
44 }
45 131 }
46
47 131 void hashset_free(HashSet *set)
48 {
49
2/2
✓ Branch 0 (7→3) taken 9824 times.
✓ Branch 1 (7→8) taken 131 times.
 9955 for (size_t i = 0, n = set->table_size; i < n; i++) {
50 9824 HashSetEntry *h = set->table[i];
51
2/2
✓ Branch 0 (5→4) taken 4454 times.
✓ Branch 1 (5→6) taken 9824 times.
 14278 while (h) {
52 4454 HashSetEntry *next = h->next;
53 4454 free(h);
54 4454 h = next;
55 }
56 }
57 131 free(set->table);
58 131 }
59
60 12094 static size_t get_slot(const HashSet *set, const char *str, size_t str_len)
61 {
62 12094 const size_t hash = set->hash(str, str_len);
63 12094 return hash & (set->table_size - 1);
64 }
65
66 6535 HashSetEntry *hashset_get(const HashSet *set, const char *str, size_t str_len)
67 {
68 6535 const size_t slot = get_slot(set, str, str_len);
69 6535 HashSetEntry *h = set->table[slot];
70
2/2
✓ Branch 0 (8→4) taken 3518 times.
✓ Branch 1 (8→9) taken 4555 times.
 8073 while (h) {
71
4/4
✓ Branch 0 (4→5) taken 2157 times.
✓ Branch 1 (4→7) taken 1361 times.
✓ Branch 2 (6→7) taken 177 times.
✓ Branch 3 (6→9) taken 1980 times.
 3518 if (str_len == h->str_len && set->equal(str, h->str, str_len)) {
72 return h;
73 }
74 1538 h = h->next;
75 }
76 return NULL;
77 }
78
79 13 static void rehash(HashSet *set, size_t newsize)
80 {
81 13 size_t oldsize = set->table_size;
82 13 HashSetEntry **oldtable = set->table;
83 13 alloc_table(set, newsize);
84
2/2
✓ Branch 0 (9→4) taken 1456 times.
✓ Branch 1 (9→10) taken 13 times.
 1469 for (size_t i = 0; i < oldsize; i++) {
85 1456 HashSetEntry *e = oldtable[i];
86
2/2
✓ Branch 0 (7→5) taken 1105 times.
✓ Branch 1 (7→8) taken 1456 times.
 2561 while (e) {
87 1105 HashSetEntry *next = e->next;
88 1105 const size_t slot = get_slot(set, e->str, e->str_len);
89 1105 e->next = set->table[slot];
90 1105 set->table[slot] = e;
91 1105 e = next;
92 }
93 }
94 13 free(oldtable);
95 13 }
96
97 6394 HashSetEntry *hashset_insert(HashSet *set, const char *str, size_t str_len)
98 {
99 6394 HashSetEntry *h = hashset_get(set, str, str_len);
100
2/2
✓ Branch 0 (3→4) taken 4454 times.
✓ Branch 1 (3→10) taken 1940 times.
 6394 if (h) {
101 return h;
102 }
103
104 4454 const size_t slot = get_slot(set, str, str_len);
105 4454 h = xmalloc(sizeof(*h) + str_len + 1);
106 4454 h->next = set->table[slot];
107 4454 h->str_len = str_len;
108 4454 memcpy(h->str, str, str_len);
109 4454 h->str[str_len] = '\0';
110 4454 set->table[slot] = h;
111
112
2/2
✓ Branch 0 (6→7) taken 13 times.
✓ Branch 1 (6→10) taken 4441 times.
 4454 if (++set->nr_entries > set->grow_at) {
113 13 size_t new_size = set->table_size << 1;
114
1/2
✗ Branch 0 (7→8) not taken.
✓ Branch 1 (7→9) taken 13 times.
 13 if (unlikely(new_size == 0)) {
115 − fatal_error(__func__, EOVERFLOW);
116 }
117 13 rehash(set, new_size);
118 }
119
120 return h;
121 }
122