dte test coverage


Directory: ./
File: src/util/hashmap.h
Date: 2025-07-10 06:26:10
Exec Total Coverage
Lines: 18 18 100.0%
Functions: 4 4 100.0%
Branches: 8 8 100.0%

Line Branch Exec Source
1 #ifndef UTIL_HASHMAP_H
2 #define UTIL_HASHMAP_H
3
4 #include <stdbool.h>
5 #include <stddef.h>
6 #include "container.h"
7 #include "debug.h"
8 #include "macros.h"
9
10 typedef enum {
11 HMAP_NO_FLAGS = 0, // For self-documentation purposes only
12 HMAP_BORROWED_KEYS = 1 << 0, // Never call free(3) on HashMapEntry::key
13 } HashMapFlags;
14
15 typedef struct {
16 char *key;
17 void *value;
18 size_t hash;
19 } HashMapEntry;
20
21 // A container type for mapping between string keys and pointer values,
22 // using hashing for primary lookups and quadratic probing for collision
23 // resolution.
24 typedef struct {
25 HashMapEntry *entries;
26 size_t mask; // Length of entries (which is always a power of 2) minus 1
27 size_t count; // Number of active entries
28 size_t tombstones; // Number of tombstones
29 HashMapFlags flags;
30 } HashMap;
31
32 typedef struct {
33 const HashMap *map;
34 const HashMapEntry *entry;
35 size_t idx;
36 } HashMapIter;
37
38 #define HASHMAP_INIT(f) { \
39 .entries = NULL, \
40 .mask = 0, \
41 .count = 0, \
42 .tombstones = 0, \
43 .flags = f, \
44 }
45
46 1364 static inline HashMapIter hashmap_iter(const HashMap *map)
47 {
48 1364 return (HashMapIter){.map = map};
49 }
50
51 19552 static inline bool hashmap_next(HashMapIter *iter)
52 {
53 19552 const HashMap *map = iter->map;
54
2/2
✓ Branch 0 (2→3) taken 19320 times.
✓ Branch 1 (2→8) taken 232 times.
19552 if (unlikely(!map->entries)) {
55 return false;
56 }
57
58
2/2
✓ Branch 0 (7→4) taken 39144 times.
✓ Branch 1 (7→8) taken 1130 times.
40274 for (size_t i = iter->idx, n = map->mask + 1; i < n; i++) {
59 39144 const HashMapEntry *e = map->entries + i;
60
2/2
✓ Branch 0 (4→5) taken 18190 times.
✓ Branch 1 (4→6) taken 20954 times.
39144 if (e->key) {
61 18190 iter->entry = e;
62 18190 iter->idx = i + 1;
63 18190 return true;
64 }
65 }
66 return false;
67 }
68
69 void hashmap_init(HashMap *map, size_t capacity, HashMapFlags flags) NONNULL_ARGS;
70 void *hashmap_insert(HashMap *map, char *key, void *value) NONNULL_ARGS_AND_RETURN;
71 void *hashmap_insert_or_replace(HashMap *map, char *key, void *value) NONNULL_ARGS WARN_UNUSED_RESULT;
72 void *hashmap_remove(HashMap *map, const char *key) NONNULL_ARGS WARN_UNUSED_RESULT;
73 void hashmap_clear(HashMap *map, FreeFunction free_value) NONNULL_ARG(1);
74 void hashmap_free(HashMap *map, FreeFunction free_value) NONNULL_ARG(1);
75 HashMapEntry *hashmap_find(const HashMap *map, const char *key) NONNULL_ARGS WARN_UNUSED_RESULT;
76
77 NONNULL_ARGS WARN_UNUSED_RESULT
78 30416 static inline void *hashmap_get(const HashMap *map, const char *key)
79 {
80 30416 HashMapEntry *entry = hashmap_find(map, key);
81
2/2
✓ Branch 0 (3→4) taken 11098 times.
✓ Branch 1 (3→5) taken 19318 times.
30416 return entry ? entry->value : NULL;
82 }
83
84 NONNULL_ARGS_AND_RETURN WARN_UNUSED_RESULT
85 1580 static inline void *hashmap_xget(const HashMap *map, const char *key)
86 {
87 1580 void *val = hashmap_get(map, key);
88 1580 BUG_ON(!val);
89 1580 return val;
90 }
91
92 #endif
93