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 | 1392 | static inline HashMapIter hashmap_iter(const HashMap *map) | |
| 39 | { | ||
| 40 | 1392 | return (HashMapIter){.map = map}; | |
| 41 | } | ||
| 42 | |||
| 43 | 20117 | static inline bool hashmap_next(HashMapIter *iter) | |
| 44 | { | ||
| 45 | 20117 | const HashMap *map = iter->map; | |
| 46 |
2/2✓ Branch 2 → 3 taken 19886 times.
✓ Branch 2 → 8 taken 231 times.
|
20117 | if (unlikely(!map->entries)) { |
| 47 | return false; | ||
| 48 | } | ||
| 49 | |||
| 50 |
2/2✓ Branch 7 → 4 taken 40224 times.
✓ Branch 7 → 8 taken 1159 times.
|
41383 | for (size_t i = iter->idx, n = map->mask + 1; i < n; i++) { |
| 51 | 40224 | const HashMapEntry *e = map->entries + i; | |
| 52 |
2/2✓ Branch 4 → 5 taken 18727 times.
✓ Branch 4 → 6 taken 21497 times.
|
40224 | if (e->key) { |
| 53 | 18727 | iter->entry = e; | |
| 54 | 18727 | iter->idx = i + 1; | |
| 55 | 18727 | return true; | |
| 56 | } | ||
| 57 | } | ||
| 58 | return false; | ||
| 59 | } | ||
| 60 | |||
| 61 | HashMap hashmap_new(size_t capacity, HashMapFlags flags) WARN_UNUSED_RESULT; | ||
| 62 | void *hashmap_insert(HashMap *map, char *key, void *value) NONNULL_ARGS_AND_RETURN; | ||
| 63 | void *hashmap_insert_or_replace(HashMap *map, char *key, void *value) NONNULL_ARGS WARN_UNUSED_RESULT; | ||
| 64 | void *hashmap_remove(HashMap *map, const char *key) NONNULL_ARGS WARN_UNUSED_RESULT; | ||
| 65 | void hashmap_clear(HashMap *map, FreeFunction free_value) NONNULL_ARG(1); | ||
| 66 | void hashmap_free(HashMap *map, FreeFunction free_value) NONNULL_ARG(1); | ||
| 67 | HashMapEntry *hashmap_find(const HashMap *map, const char *key) NONNULL_ARGS WARN_UNUSED_RESULT; | ||
| 68 | |||
| 69 | NONNULL_ARGS WARN_UNUSED_RESULT | ||
| 70 | 30827 | static inline void *hashmap_get(const HashMap *map, const char *key) | |
| 71 | { | ||
| 72 | 30827 | HashMapEntry *entry = hashmap_find(map, key); | |
| 73 |
2/2✓ Branch 3 → 4 taken 11341 times.
✓ Branch 3 → 5 taken 19486 times.
|
30827 | return entry ? entry->value : NULL; |
| 74 | } | ||
| 75 | |||
| 76 | NONNULL_ARGS_AND_RETURN WARN_UNUSED_RESULT | ||
| 77 | 1630 | static inline void *hashmap_xget(const HashMap *map, const char *key) | |
| 78 | { | ||
| 79 | 1630 | void *val = hashmap_get(map, key); | |
| 80 | 1630 | BUG_ON(!val); | |
| 81 | 1630 | return val; | |
| 82 | } | ||
| 83 | |||
| 84 | #endif | ||
| 85 |