map.c (5240B)
1 // map.c: Hash maps and sets 2 // 3 // parts of the implementation derived from khash.h as part of klib (MIT license) 4 // 5 // NOTE: Callers must manage memory (allocate) for keys and values. 6 // Map and Set does not make its own copy of the key or value. 7 8 #include <stdbool.h> 9 #include <string.h> 10 11 #include "auto/config.h" 12 #include "nvim/map_defs.h" 13 #include "nvim/memory.h" 14 15 #define equal_simple(x, y) ((x) == (y)) 16 17 #define hash_uint64_t(key) (uint32_t)((key) >> 33^(key)^(key) << 11) 18 #define equal_uint64_t equal_simple 19 #define hash_uint32_t(x) (x) 20 #define equal_uint32_t equal_simple 21 #define hash_int(x) hash_uint32_t((uint32_t)(x)) 22 #define equal_int equal_simple 23 #define hash_int64_t(key) hash_uint64_t((uint64_t)key) 24 #define equal_int64_t equal_simple 25 26 #if defined(ARCH_64) 27 # define hash_ptr_t(key) hash_uint64_t((uint64_t)(key)) 28 # define equal_ptr_t(a, b) equal_uint64_t((uint64_t)(a), (uint64_t)(b)) 29 #elif defined(ARCH_32) 30 # define hash_ptr_t(key) hash_uint32_t((uint32_t)(key)) 31 # define equal_ptr_t(a, b) equal_uint32_t((uint32_t)(a), (uint32_t)(b)) 32 #endif 33 34 static inline uint32_t hash_cstr_t(const char *s) 35 { 36 uint32_t h = 0; 37 for (size_t i = 0; s[i]; i++) { 38 h = (h << 5) - h + (uint8_t)s[i]; 39 } 40 return h; 41 } 42 43 #define equal_cstr_t strequal 44 45 static inline uint32_t hash_HlEntry(HlEntry ae) 46 { 47 const uint8_t *data = (const uint8_t *)&ae; 48 uint32_t h = 0; 49 for (size_t i = 0; i < sizeof(ae); i++) { 50 h = (h << 5) - h + data[i]; 51 } 52 return h; 53 } 54 55 static inline bool equal_HlEntry(HlEntry ae1, HlEntry ae2) 56 { 57 return memcmp(&ae1, &ae2, sizeof(ae1)) == 0; 58 } 59 60 static inline uint32_t hash_ColorKey(ColorKey ae) 61 { 62 const uint8_t *data = (const uint8_t *)&ae; 63 uint32_t h = 0; 64 for (size_t i = 0; i < sizeof(ae); i++) { 65 h = (h << 5) - h + data[i]; 66 } 67 return h; 68 } 69 70 static inline bool equal_ColorKey(ColorKey ae1, ColorKey ae2) 71 { 72 return memcmp(&ae1, &ae2, sizeof(ae1)) == 0; 73 } 74 75 // TODO(bfredl): this could be _less_ for the h->hash part as this is now small (4 bytes per value) 76 #define UPPER_FILL 0.77 77 78 #define roundup32(x) (--(x), (x) |= (x)>>1, (x) |= (x)>>2, (x) |= (x)>>4, (x) |= (x)>>8, \ 79 (x) |= (x)>>16, ++(x)) 80 81 // h->hash must either be NULL or an already valid pointer 82 void mh_realloc(MapHash *h, uint32_t n_min_buckets) 83 { 84 xfree(h->hash); 85 uint32_t n_buckets = n_min_buckets < 16 ? 16 : n_min_buckets; 86 roundup32(n_buckets); 87 // sets all buckets to EMPTY 88 h->hash = xcalloc(n_buckets, sizeof *h->hash); 89 h->n_occupied = h->size = 0; 90 h->n_buckets = n_buckets; 91 h->upper_bound = (uint32_t)(h->n_buckets * UPPER_FILL + 0.5); 92 } 93 94 void mh_clear(MapHash *h) 95 { 96 if (h->hash) { 97 memset(h->hash, 0, h->n_buckets * sizeof(*h->hash)); 98 h->size = h->n_occupied = 0; 99 h->n_keys = 0; 100 } 101 } 102 103 #define KEY_NAME(x) x##int 104 #include "nvim/map_key_impl.c.h" 105 #define VAL_NAME(x) quasiquote(x, int) 106 #include "nvim/map_value_impl.c.h" 107 #undef VAL_NAME 108 #define VAL_NAME(x) quasiquote(x, ptr_t) 109 #include "nvim/map_value_impl.c.h" 110 #undef VAL_NAME 111 #define VAL_NAME(x) quasiquote(x, String) 112 #include "nvim/map_value_impl.c.h" 113 #undef VAL_NAME 114 #undef KEY_NAME 115 116 #define KEY_NAME(x) x##ptr_t 117 #include "nvim/map_key_impl.c.h" 118 #define VAL_NAME(x) quasiquote(x, ptr_t) 119 #include "nvim/map_value_impl.c.h" 120 #undef VAL_NAME 121 #undef KEY_NAME 122 123 #define KEY_NAME(x) x##cstr_t 124 #include "nvim/map_key_impl.c.h" 125 #define VAL_NAME(x) quasiquote(x, ptr_t) 126 #include "nvim/map_value_impl.c.h" 127 #undef VAL_NAME 128 #define VAL_NAME(x) quasiquote(x, int) 129 #include "nvim/map_value_impl.c.h" 130 #undef VAL_NAME 131 #undef KEY_NAME 132 133 #define KEY_NAME(x) x##String 134 #include "nvim/map_key_impl.c.h" 135 #define VAL_NAME(x) quasiquote(x, int) 136 #include "nvim/map_value_impl.c.h" 137 #undef VAL_NAME 138 #undef KEY_NAME 139 140 #define KEY_NAME(x) x##uint32_t 141 #include "nvim/map_key_impl.c.h" 142 #define VAL_NAME(x) quasiquote(x, ptr_t) 143 #include "nvim/map_value_impl.c.h" 144 #undef VAL_NAME 145 #define VAL_NAME(x) quasiquote(x, uint32_t) 146 #include "nvim/map_value_impl.c.h" 147 #undef VAL_NAME 148 #undef KEY_NAME 149 150 #define KEY_NAME(x) x##uint64_t 151 #include "nvim/map_key_impl.c.h" 152 #define VAL_NAME(x) quasiquote(x, ptr_t) 153 #include "nvim/map_value_impl.c.h" 154 #undef VAL_NAME 155 #define VAL_NAME(x) quasiquote(x, ssize_t) 156 #include "nvim/map_value_impl.c.h" 157 #undef VAL_NAME 158 #define VAL_NAME(x) quasiquote(x, uint64_t) 159 #include "nvim/map_value_impl.c.h" 160 #undef VAL_NAME 161 #define VAL_NAME(x) quasiquote(x, int) 162 #include "nvim/map_value_impl.c.h" 163 #undef VAL_NAME 164 #undef KEY_NAME 165 166 #define KEY_NAME(x) x##int64_t 167 #include "nvim/map_key_impl.c.h" 168 #define VAL_NAME(x) quasiquote(x, ptr_t) 169 #include "nvim/map_value_impl.c.h" 170 #undef VAL_NAME 171 #define VAL_NAME(x) quasiquote(x, int64_t) 172 #include "nvim/map_value_impl.c.h" 173 #undef VAL_NAME 174 #undef KEY_NAME 175 176 #define KEY_NAME(x) x##HlEntry 177 #include "nvim/map_key_impl.c.h" 178 #undef KEY_NAME 179 180 #define KEY_NAME(x) x##ColorKey 181 #include "nvim/map_key_impl.c.h" 182 #define VAL_NAME(x) quasiquote(x, ColorItem) 183 #include "nvim/map_value_impl.c.h" 184 #undef VAL_NAME 185 #undef KEY_NAME 186 187 /// Deletes a key:value pair from a string:pointer map, and frees the 188 /// storage of both key and value. 189 /// 190 void pmap_del2(PMap(cstr_t) *map, const char *key) 191 { 192 cstr_t key_alloc = NULL; 193 ptr_t val = pmap_del(cstr_t)(map, key, &key_alloc); 194 xfree((void *)key_alloc); 195 xfree(val); 196 }