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