src/util/hashmap.h
| 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 | 1370 | static inline HashMapIter hashmap_iter(const HashMap *map) | |
| 47 | { | ||
| 48 | 1370 | return (HashMapIter){.map = map}; | |
| 49 | } | ||
| 50 | |||
| 51 | 19788 | static inline bool hashmap_next(HashMapIter *iter) | |
| 52 | { | ||
| 53 | 19788 | const HashMap *map = iter->map; | |
| 54 |
2/2✓ Branch 2 → 3 taken 19561 times.
✓ Branch 2 → 8 taken 227 times.
|
19788 | if (unlikely(!map->entries)) { |
| 55 | return false; | ||
| 56 | } | ||
| 57 | |||
| 58 |
2/2✓ Branch 7 → 4 taken 39672 times.
✓ Branch 7 → 8 taken 1141 times.
|
40813 | for (size_t i = iter->idx, n = map->mask + 1; i < n; i++) { |
| 59 | 39672 | const HashMapEntry *e = map->entries + i; | |
| 60 |
2/2✓ Branch 4 → 5 taken 18420 times.
✓ Branch 4 → 6 taken 21252 times.
|
39672 | if (e->key) { |
| 61 | 18420 | iter->entry = e; | |
| 62 | 18420 | iter->idx = i + 1; | |
| 63 | 18420 | 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 | 30550 | static inline void *hashmap_get(const HashMap *map, const char *key) | |
| 79 | { | ||
| 80 | 30550 | HashMapEntry *entry = hashmap_find(map, key); | |
| 81 |
2/2✓ Branch 3 → 4 taken 11155 times.
✓ Branch 3 → 5 taken 19395 times.
|
30550 | 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 |