| 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 "macros.h" | ||
| 7 | |||
| 8 | typedef void (*FreeFunction)(void *ptr); | ||
| 9 | |||
| 10 | typedef struct { | ||
| 11 | char *key; | ||
| 12 | void *value; | ||
| 13 | size_t hash; | ||
| 14 | } HashMapEntry; | ||
| 15 | |||
| 16 | typedef struct { | ||
| 17 | HashMapEntry *entries; | ||
| 18 | size_t mask; // Length of entries (which is always a power of 2) minus 1 | ||
| 19 | size_t count; // Number of active entries | ||
| 20 | size_t tombstones; // Number of tombstones | ||
| 21 | } HashMap; | ||
| 22 | |||
| 23 | typedef struct { | ||
| 24 | const HashMap *map; | ||
| 25 | HashMapEntry *entry; | ||
| 26 | size_t idx; | ||
| 27 | } HashMapIter; | ||
| 28 | |||
| 29 | #define HASHMAP_INIT { \ | ||
| 30 | .entries = NULL, \ | ||
| 31 | .mask = 0, \ | ||
| 32 | .count = 0, \ | ||
| 33 | .tombstones = 0 \ | ||
| 34 | } | ||
| 35 | |||
| 36 | 1234 | static inline HashMapIter hashmap_iter(const HashMap *map) | |
| 37 | { | ||
| 38 | 1234 | return (HashMapIter){.map = map}; | |
| 39 | } | ||
| 40 | |||
| 41 | 17555 | static inline bool hashmap_next(HashMapIter *iter) | |
| 42 | { | ||
| 43 | 17555 | const HashMap *map = iter->map; | |
| 44 |
2/2✓ Branch 0 taken 17352 times.
✓ Branch 1 taken 203 times.
|
17555 | if (unlikely(!map->entries)) { |
| 45 | return false; | ||
| 46 | } | ||
| 47 | |||
| 48 |
2/2✓ Branch 0 taken 47040 times.
✓ Branch 1 taken 1031 times.
|
48071 | for (size_t i = iter->idx, n = map->mask + 1; i < n; i++) { |
| 49 | 47040 | HashMapEntry *e = map->entries + i; | |
| 50 |
2/2✓ Branch 0 taken 16321 times.
✓ Branch 1 taken 30719 times.
|
47040 | if (e->key) { |
| 51 | 16321 | iter->entry = e; | |
| 52 | 16321 | iter->idx = i + 1; | |
| 53 | 16321 | return true; | |
| 54 | } | ||
| 55 | } | ||
| 56 | return false; | ||
| 57 | } | ||
| 58 | |||
| 59 | void hashmap_init(HashMap *map, size_t capacity) NONNULL_ARGS; | ||
| 60 | void *hashmap_insert(HashMap *map, char *key, void *value) NONNULL_ARGS_AND_RETURN; | ||
| 61 | void *hashmap_insert_or_replace(HashMap *map, char *key, void *value) NONNULL_ARGS; | ||
| 62 | void *hashmap_remove(HashMap *map, const char *key) NONNULL_ARGS; | ||
| 63 | void hashmap_clear(HashMap *map, FreeFunction free_value) NONNULL_ARG(1); | ||
| 64 | void hashmap_free(HashMap *map, FreeFunction free_value) NONNULL_ARG(1); | ||
| 65 | HashMapEntry *hashmap_find(const HashMap *map, const char *key) NONNULL_ARGS WARN_UNUSED_RESULT; | ||
| 66 | |||
| 67 | 29735 | static inline void *hashmap_get(const HashMap *map, const char *key) | |
| 68 | { | ||
| 69 | 29735 | HashMapEntry *e = hashmap_find(map, key); | |
| 70 |
2/2✓ Branch 0 taken 10766 times.
✓ Branch 1 taken 18969 times.
|
29735 | return e ? e->value : NULL; |
| 71 | } | ||
| 72 | |||
| 73 | #endif | ||
| 74 |