map_defs.h (6445B)
1 #pragma once 2 3 #include <stdbool.h> 4 #include <stdint.h> 5 #include <stdio.h> 6 7 #include "nvim/api/private/defs.h" 8 #include "nvim/assert_defs.h" 9 #include "nvim/highlight_defs.h" 10 #include "nvim/types_defs.h" 11 12 #if defined(__NetBSD__) 13 # undef uint64_t 14 # define uint64_t uint64_t 15 #endif 16 17 typedef const char *cstr_t; 18 typedef void *ptr_t; 19 20 // when used as a key, String doesn't need to be NUL terminated, 21 // and can also contain embedded NUL:s as part of the data. 22 static inline uint32_t hash_String(String s) 23 { 24 uint32_t h = 0; 25 for (size_t i = 0; i < s.size; i++) { 26 h = (h << 5) - h + (uint8_t)s.data[i]; 27 } 28 return h; 29 } 30 31 static inline bool equal_String(String a, String b) 32 { 33 if (a.size != b.size) { 34 return false; 35 } 36 37 return (a.size == 0) || (memcmp(a.data, b.data, a.size) == 0); 38 } 39 40 #define Set(type) Set_##type 41 #define Map(T, U) Map_##T##_##U 42 #define PMap(T) Map(T, ptr_t) 43 44 static const int value_init_int = 0; 45 static const ptr_t value_init_ptr_t = NULL; 46 static const ssize_t value_init_ssize_t = -1; 47 static const uint32_t value_init_uint32_t = 0; 48 static const uint64_t value_init_uint64_t = 0; 49 static const int64_t value_init_int64_t = 0; 50 static const String value_init_String = STRING_INIT; 51 static const ColorItem value_init_ColorItem = COLOR_ITEM_INITIALIZER; 52 53 // layer 0: type non-specific code 54 55 typedef struct { 56 uint32_t n_buckets; 57 uint32_t size; 58 uint32_t n_occupied; 59 uint32_t upper_bound; 60 uint32_t n_keys; // this is almost always "size", but keys[] could contain ded items.. 61 uint32_t keys_capacity; 62 uint32_t *hash; 63 } MapHash; 64 65 #define MAPHASH_INIT { 0, 0, 0, 0, 0, 0, NULL } 66 #define SET_INIT { MAPHASH_INIT, NULL } 67 #define MAP_INIT { SET_INIT, NULL } 68 69 #define MH_TOMBSTONE UINT32_MAX 70 71 #define mh_is_empty(h, i) ((h)->hash[i] == 0) 72 #define mh_is_del(h, i) ((h)->hash[i] == MH_TOMBSTONE) 73 #define mh_is_either(h, i) ((uint32_t)((h)->hash[i] + 1U) <= 1U) 74 75 typedef enum { 76 kMHExisting = 0, 77 kMHNewKeyDidFit, 78 kMHNewKeyRealloc, 79 } MHPutStatus; 80 81 void mh_clear(MapHash *h); 82 void mh_realloc(MapHash *h, uint32_t n_min_buckets); 83 84 // layer 1: key type specific defs 85 // This is all need for sets. 86 87 #define MH_DECLS(T, K, K_query) \ 88 typedef struct { \ 89 MapHash h; \ 90 K *keys; \ 91 } Set(T); \ 92 \ 93 uint32_t mh_find_bucket_##T(Set(T) *set, K_query key, bool put); \ 94 uint32_t mh_get_##T(Set(T) *set, K_query key); \ 95 void mh_rehash_##T(Set(T) *set); \ 96 uint32_t mh_put_##T(Set(T) *set, K_query key, MHPutStatus *new); \ 97 98 #define KEY_DECLS(T) \ 99 MH_DECLS(T, T, T) \ 100 uint32_t mh_delete_##T(Set(T) *set, T *key); \ 101 static inline bool set_put_##T(Set(T) *set, T key, T **key_alloc) { \ 102 MHPutStatus status; \ 103 uint32_t k = mh_put_##T(set, key, &status); \ 104 if (key_alloc) { \ 105 *key_alloc = &set->keys[k]; \ 106 } \ 107 return status != kMHExisting; \ 108 } \ 109 static inline T set_del_##T(Set(T) *set, T key) \ 110 { \ 111 mh_delete_##T(set, &key); \ 112 return key; \ 113 } \ 114 static inline bool set_has_##T(Set(T) *set, T key) { \ 115 return mh_get_##T(set, key) != MH_TOMBSTONE; \ 116 } \ 117 118 // layer 2: key+value specific defs 119 // now we finally get Maps 120 121 #define MAP_DECLS(T, U) \ 122 typedef struct { \ 123 Set(T) set; \ 124 U *values; \ 125 } Map(T, U); \ 126 static inline U map_get_##T##_##U(Map(T, U) *map, T key) \ 127 { \ 128 uint32_t k = mh_get_##T(&map->set, key); \ 129 return k == MH_TOMBSTONE ? value_init_##U : map->values[k]; \ 130 } \ 131 U *map_ref_##T##_##U(Map(T, U) *map, T key, T **key_alloc); \ 132 U *map_put_ref_##T##_##U(Map(T, U) *map, T key, T **key_alloc, bool *new_item); \ 133 static inline void map_put_##T##_##U(Map(T, U) *map, T key, U value) \ 134 { \ 135 U *val = map_put_ref_##T##_##U(map, key, NULL, NULL); \ 136 *val = value; \ 137 } \ 138 U map_del_##T##_##U(Map(T, U) *map, T key, T *key_alloc); \ 139 140 // NOTE: Keys AND values must be allocated! Map and Set does not make a copy. 141 142 #define quasiquote(x, y) x##y 143 144 MH_DECLS(glyph, char, String) 145 KEY_DECLS(int) 146 KEY_DECLS(cstr_t) 147 KEY_DECLS(ptr_t) 148 KEY_DECLS(uint64_t) 149 KEY_DECLS(int64_t) 150 KEY_DECLS(uint32_t) 151 KEY_DECLS(String) 152 KEY_DECLS(HlEntry) 153 KEY_DECLS(ColorKey) 154 155 MAP_DECLS(int, int) 156 MAP_DECLS(int, ptr_t) 157 MAP_DECLS(cstr_t, ptr_t) 158 MAP_DECLS(cstr_t, int) 159 MAP_DECLS(ptr_t, ptr_t) 160 MAP_DECLS(uint32_t, ptr_t) 161 MAP_DECLS(uint64_t, ptr_t) 162 MAP_DECLS(uint64_t, ssize_t) 163 MAP_DECLS(uint64_t, uint64_t) 164 MAP_DECLS(uint64_t, int) 165 MAP_DECLS(int64_t, int64_t) 166 MAP_DECLS(int64_t, ptr_t) 167 MAP_DECLS(uint32_t, uint32_t) 168 MAP_DECLS(String, int) 169 MAP_DECLS(int, String) 170 MAP_DECLS(ColorKey, ColorItem) 171 172 #define set_has(T, set, key) set_has_##T(set, key) 173 #define set_put(T, set, key) set_put_##T(set, key, NULL) 174 #define set_put_ref(T, set, key, key_alloc) set_put_##T(set, key, key_alloc) 175 #define set_put_idx(T, set, key, status) mh_put_##T(set, key, status) 176 #define set_del(T, set, key) set_del_##T(set, key) 177 #define set_size(set) ((set)->h.size) 178 #define set_clear(T, set) mh_clear(&(set)->h) 179 #define set_destroy(T, set) \ 180 do { \ 181 xfree((set)->keys); \ 182 xfree((set)->h.hash); \ 183 *(set) = (Set(T)) SET_INIT; \ 184 } while (0) 185 186 #define map_get(T, U) map_get_##T##_##U 187 #define map_has(T, map, key) set_has(T, &(map)->set, key) 188 #define map_put(T, U) map_put_##T##_##U 189 #define map_ref(T, U) map_ref_##T##_##U 190 #define map_put_ref(T, U) map_put_ref_##T##_##U 191 #define map_del(T, U) map_del_##T##_##U 192 #define map_size(map) set_size(&(map)->set) 193 #define map_clear(T, map) set_clear(T, &(map)->set) 194 #define map_destroy(T, map) \ 195 do { \ 196 set_destroy(T, &(map)->set); \ 197 XFREE_CLEAR((map)->values); \ 198 } while (0) 199 200 #define pmap_get(T) map_get(T, ptr_t) 201 #define pmap_put(T) map_put(T, ptr_t) 202 #define pmap_ref(T) map_ref(T, ptr_t) 203 #define pmap_put_ref(T) map_put_ref(T, ptr_t) 204 /// @see pmap_del2 205 #define pmap_del(T) map_del(T, ptr_t) 206 207 #define set_foreach(set, key, block) \ 208 { \ 209 uint32_t __i; \ 210 for (__i = 0; __i < (set)->h.n_keys; __i++) { \ 211 (key) = (set)->keys[__i]; \ 212 block; \ 213 } \ 214 } 215 216 #define map_foreach_key(map, key, block) set_foreach(&(map)->set, key, block) 217 218 #define map_foreach(map, key, value, code) \ 219 { \ 220 uint32_t __i; \ 221 for (__i = 0; __i < (map)->set.h.n_keys; __i++) { \ 222 (key) = (map)->set.keys[__i]; \ 223 (value) = (map)->values[__i]; \ 224 code; \ 225 } \ 226 } 227 228 #define map_foreach_value(map, value, code) \ 229 { \ 230 uint32_t __i; \ 231 for (__i = 0; __i < (map)->set.h.n_keys; __i++) { \ 232 (value) = (map)->values[__i]; \ 233 code; \ 234 } \ 235 } 236 237 void pmap_del2(PMap(cstr_t) *map, const char *key);