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 |