| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #ifndef UTIL_INTMAP_H | ||
| 2 | #define UTIL_INTMAP_H | ||
| 3 | |||
| 4 | #include <stdbool.h> | ||
| 5 | #include <stddef.h> | ||
| 6 | #include <stdint.h> | ||
| 7 | #include "macros.h" | ||
| 8 | |||
| 9 | extern const char tombstone[16]; | ||
| 10 | |||
| 11 | typedef void (*FreeFunction)(void *ptr); | ||
| 12 | |||
| 13 | typedef struct { | ||
| 14 | uint32_t key; | ||
| 15 | void *value; | ||
| 16 | } IntMapEntry; | ||
| 17 | |||
| 18 | // This is much like the HashMap type from hashmap.h, but for uint32_t keys | ||
| 19 | // and with some of the internal details (different hash function, different | ||
| 20 | // tombstone handling, not storing hash values in entries, etc.) tweaked | ||
| 21 | // accordingly. | ||
| 22 | typedef struct { | ||
| 23 | IntMapEntry *entries; | ||
| 24 | size_t mask; // Length of entries (which is always a power of 2) minus 1 | ||
| 25 | size_t count; // Number of active entries | ||
| 26 | size_t tombstones; // Number of tombstones | ||
| 27 | } IntMap; | ||
| 28 | |||
| 29 | typedef struct { | ||
| 30 | const IntMap *map; | ||
| 31 | IntMapEntry *entry; | ||
| 32 | size_t idx; | ||
| 33 | } IntMapIter; | ||
| 34 | |||
| 35 | #define INTMAP_INIT { \ | ||
| 36 | .entries = NULL, \ | ||
| 37 | .mask = 0, \ | ||
| 38 | .count = 0, \ | ||
| 39 | .tombstones = 0 \ | ||
| 40 | } | ||
| 41 | |||
| 42 | 33 | static inline IntMapIter intmap_iter(const IntMap *map) | |
| 43 | { | ||
| 44 | 33 | return (IntMapIter){.map = map}; | |
| 45 | } | ||
| 46 | |||
| 47 | 1696 | static inline bool intmap_next(IntMapIter *iter) | |
| 48 | { | ||
| 49 | 1696 | const IntMap *map = iter->map; | |
| 50 |
1/2✓ Branch 0 (2→3) taken 1696 times.
✗ Branch 1 (2→9) not taken.
|
1696 | if (unlikely(!map->entries)) { |
| 51 | return false; | ||
| 52 | } | ||
| 53 | |||
| 54 |
2/2✓ Branch 0 (8→4) taken 4368 times.
✓ Branch 1 (8→9) taken 33 times.
|
4401 | for (size_t i = iter->idx, n = map->mask + 1; i < n; i++) { |
| 55 | 4368 | IntMapEntry *e = map->entries + i; | |
| 56 |
4/4✓ Branch 0 (4→5) taken 1667 times.
✓ Branch 1 (4→7) taken 2701 times.
✓ Branch 2 (5→6) taken 1663 times.
✓ Branch 3 (5→7) taken 4 times.
|
4368 | if (e->value && e->value != tombstone) { |
| 57 | 1663 | iter->entry = e; | |
| 58 | 1663 | iter->idx = i + 1; | |
| 59 | 1663 | return true; | |
| 60 | } | ||
| 61 | } | ||
| 62 | return false; | ||
| 63 | } | ||
| 64 | |||
| 65 | void intmap_init(IntMap *map, size_t capacity) NONNULL_ARGS; | ||
| 66 | void *intmap_insert_or_replace(IntMap *map, uint32_t key, void *value) NONNULL_ARGS; | ||
| 67 | void *intmap_remove(IntMap *map, uint32_t key) NONNULL_ARGS; | ||
| 68 | void intmap_free(IntMap *map, FreeFunction free_value) NONNULL_ARG(1); | ||
| 69 | IntMapEntry *intmap_find(const IntMap *map, uint32_t key) NONNULL_ARGS WARN_UNUSED_RESULT; | ||
| 70 | |||
| 71 | 13 | static inline void *intmap_get(const IntMap *map, uint32_t key) | |
| 72 | { | ||
| 73 | 13 | IntMapEntry *e = intmap_find(map, key); | |
| 74 |
2/2✓ Branch 0 (3→4) taken 9 times.
✓ Branch 1 (3→5) taken 4 times.
|
13 | return e ? e->value : NULL; |
| 75 | } | ||
| 76 | |||
| 77 | #endif | ||
| 78 |