dte test coverage

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