| 1 | /* Copyright (C) 2010-2020 The RetroArch team |
| 2 | * |
| 3 | * --------------------------------------------------------------------------------------- |
| 4 | * The following license statement only applies to this file (rhmap.h). |
| 5 | * --------------------------------------------------------------------------------------- |
| 6 | * |
| 7 | * Permission is hereby granted, free of charge, |
| 8 | * to any person obtaining a copy of this software and associated documentation files (the "Software"), |
| 9 | * to deal in the Software without restriction, including without limitation the rights to |
| 10 | * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, |
| 11 | * and to permit persons to whom the Software is furnished to do so, subject to the following conditions: |
| 12 | * |
| 13 | * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. |
| 14 | * |
| 15 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, |
| 16 | * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| 17 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. |
| 18 | * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
| 19 | * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
| 20 | * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| 21 | */ |
| 22 | |
| 23 | #ifndef __LIBRETRO_SDK_ARRAY_RHMAP_H__ |
| 24 | #define __LIBRETRO_SDK_ARRAY_RHMAP_H__ |
| 25 | |
| 26 | /* |
| 27 | * This file implements a hash map with 32-bit keys. |
| 28 | * Based on the implementation from the public domain Bitwise project |
| 29 | * by Per Vognsen - https://github.com/pervognsen/bitwise |
| 30 | * |
| 31 | * It's a super simple type safe hash map for C with no need |
| 32 | * to predeclare any type or anything. |
| 33 | * Will always allocate memory for twice the amount of max elements |
| 34 | * so larger structs should be stored as pointers or indices to an array. |
| 35 | * Can be used in C++ with POD types (without any constructor/destructor). |
| 36 | * |
| 37 | * Be careful not to supply modifying statements to the macro arguments. |
| 38 | * Something like RHMAP_FIT(map, i++); would have unintended results. |
| 39 | * |
| 40 | * Sample usage: |
| 41 | * |
| 42 | * -- Set 2 elements with string keys and mytype_t values: |
| 43 | * mytype_t* map = NULL; |
| 44 | * RHMAP_SET_STR(map, "foo", foo_element); |
| 45 | * RHMAP_SET_STR(map, "bar", bar_element); |
| 46 | * -- now RHMAP_LEN(map) == 2, RHMAP_GET_STR(map, "foo") == foo_element |
| 47 | * |
| 48 | * -- Check if keys exist: |
| 49 | * bool has_foo = RHMAP_HAS_STR(map, "foo"); |
| 50 | * bool has_baz = RHMAP_HAS_STR(map, "baz"); |
| 51 | * -- now has_foo == true, has_baz == false |
| 52 | * |
| 53 | * -- Removing a key: |
| 54 | * bool removed = RHMAP_DEL_STR(map, "bar"); |
| 55 | * bool removed_again = RHMAP_DEL_STR(map, "bar"); |
| 56 | * -- now RHMAP_LEN(map) == 1, removed == true, removed_again == false |
| 57 | * |
| 58 | * -- Add/modify via pointer: |
| 59 | * mytype_t* p_elem = RHMAP_PTR_STR(map, "qux"); |
| 60 | * p_elem->a = 123; |
| 61 | * -- New keys initially have memory uninitialized |
| 62 | * -- Pointers can get invalidated when a key is added/removed |
| 63 | * |
| 64 | * -- Looking up the index for a given key: |
| 65 | * ptrdiff_t idx_foo = RHMAP_IDX_STR(map, "foo"); |
| 66 | * ptrdiff_t idx_invalid = RHMAP_IDX_STR(map, "invalid"); |
| 67 | * -- now idx_foo >= 0, idx_invalid == -1, map[idx_foo] == foo_element |
| 68 | * -- Indices can change when a key is added/removed |
| 69 | * |
| 70 | * -- Clear all elements (keep memory allocated): |
| 71 | * RHMAP_CLEAR(map); |
| 72 | * -- now RHMAP_LEN(map) == 0, RHMAP_CAP(map) == 16 |
| 73 | * |
| 74 | * -- Reserve memory for at least N elements: |
| 75 | * RHMAP_FIT(map, 30); |
| 76 | * -- now RHMAP_LEN(map) == 0, RHMAP_CAP(map) == 64 |
| 77 | * |
| 78 | * -- Add elements with custom hash keys: |
| 79 | * RHMAP_SET(map, my_uint32_hash(key1), some_element); |
| 80 | * RHMAP_SET(map, my_uint32_hash(key2), other_element); |
| 81 | * -- now RHMAP_LEN(map) == 2, _GET/_HAS/_DEL/_PTR/_IDX also exist |
| 82 | * |
| 83 | * -- Iterate elements (random order, order can change on insert): |
| 84 | * for (size_t i = 0, cap = RHMAP_CAP(map); i != cap, i++) |
| 85 | * if (RHMAP_KEY(map, i)) |
| 86 | * ------ here map[i] is the value of key RHMAP_KEY(map, i) |
| 87 | * |
| 88 | * -- Set a custom null value (is zeroed by default): |
| 89 | * RHMAP_SETNULLVAL(map, map_null); |
| 90 | * -- now RHMAP_GET_STR(map, "invalid") == map_null |
| 91 | * |
| 92 | * -- Free allocated memory: |
| 93 | * RHMAP_FREE(map); |
| 94 | * -- now map == NULL, RHMAP_LEN(map) == 0, RHMAP_CAP(map) == 0 |
| 95 | * |
| 96 | * -- To handle running out of memory: |
| 97 | * bool ran_out_of_memory = !RHMAP_TRYFIT(map, 1000); |
| 98 | * -- before setting an element (with SET, PTR or NULLVAL). |
| 99 | * -- When out of memory, map will stay unmodified. |
| 100 | * |
| 101 | */ |
| 102 | |
| 103 | #include <stdlib.h> /* for malloc, realloc */ |
| 104 | #include <string.h> /* for memcpy, memset */ |
| 105 | #include <stddef.h> /* for ptrdiff_t, size_t */ |
| 106 | #include <stdint.h> /* for uint32_t */ |
| 107 | |
| 108 | #define RHMAP_LEN(b) ((b) ? RHMAP__HDR(b)->len : 0) |
| 109 | #define RHMAP_MAX(b) ((b) ? RHMAP__HDR(b)->maxlen : 0) |
| 110 | #define RHMAP_CAP(b) ((b) ? RHMAP__HDR(b)->maxlen + 1 : 0) |
| 111 | #define RHMAP_KEY(b, idx) (RHMAP__HDR(b)->keys[idx]) |
| 112 | #define RHMAP_KEY_STR(b, idx) (RHMAP__HDR(b)->key_strs[idx]) |
| 113 | #define RHMAP_SETNULLVAL(b, val) (RHMAP__FIT1(b), b[-1] = (val)) |
| 114 | #define RHMAP_CLEAR(b) ((b) ? (memset(RHMAP__HDR(b)->keys, 0, RHMAP_CAP(b) * sizeof(uint32_t)), RHMAP__HDR(b)->len = 0) : 0) |
| 115 | #define RHMAP_FREE(b) ((b) ? (rhmap__free(RHMAP__HDR(b)), (b) = NULL) : 0) |
| 116 | #define RHMAP_FIT(b, n) ((!(n) || ((b) && (size_t)(n) * 2 <= RHMAP_MAX(b))) ? 0 : RHMAP__GROW(b, n)) |
| 117 | #define RHMAP_TRYFIT(b, n) (RHMAP_FIT((b), (n)), (!(n) || ((b) && (size_t)(n) * 2 <= RHMAP_MAX(b)))) |
| 118 | |
| 119 | #define RHMAP_SET(b, key, val) RHMAP_SET_FULL(b, key, NULL, val) |
| 120 | #define RHMAP_GET(b, key) RHMAP_GET_FULL(b, key, NULL) |
| 121 | #define RHMAP_HAS(b, key) RHMAP_HAS_FULL(b, key, NULL) |
| 122 | #define RHMAP_DEL(b, key) RHMAP_DEL_FULL(b, key, NULL) |
| 123 | #define RHMAP_PTR(b, key) RHMAP_PTR_FULL(b, key, NULL) |
| 124 | #define RHMAP_IDX(b, key) RHMAP_IDX_FULL(b, key, NULL) |
| 125 | |
| 126 | #ifdef __GNUC__ |
| 127 | #define RHMAP__UNUSED __attribute__((__unused__)) |
| 128 | #else |
| 129 | #define RHMAP__UNUSED |
| 130 | #endif |
| 131 | |
| 132 | #if defined(_MSC_VER) |
| 133 | #pragma warning(push) |
| 134 | #pragma warning(disable:4505) //unreferenced local function has been removed |
| 135 | #endif |
| 136 | |
| 137 | #define RHMAP_SET_FULL(b, key, str, val) (RHMAP__FIT1(b), b[rhmap__idx(RHMAP__HDR(b), (key), (str), 1, 0)] = (val)) |
| 138 | #define RHMAP_GET_FULL(b, key, str) (RHMAP__FIT1(b), b[rhmap__idx(RHMAP__HDR(b), (key), (str), 0, 0)]) |
| 139 | #define RHMAP_HAS_FULL(b, key, str) ((b) ? rhmap__idx(RHMAP__HDR(b), (key), (str), 0, 0) != -1 : 0) |
| 140 | #define RHMAP_DEL_FULL(b, key, str) ((b) ? rhmap__idx(RHMAP__HDR(b), (key), (str), 0, sizeof(*(b))) != -1 : 0) |
| 141 | #define RHMAP_PTR_FULL(b, key, str) (RHMAP__FIT1(b), &b[rhmap__idx(RHMAP__HDR(b), (key), (str), 1, 0)]) |
| 142 | #define RHMAP_IDX_FULL(b, key, str) ((b) ? rhmap__idx(RHMAP__HDR(b), (key), (str), 0, 0) : -1) |
| 143 | |
| 144 | #define RHMAP_SET_STR(b, string_key, val) RHMAP_SET_FULL(b, rhmap_hash_string(string_key), string_key, val) |
| 145 | #define RHMAP_GET_STR(b, string_key) RHMAP_GET_FULL(b, rhmap_hash_string(string_key), string_key) |
| 146 | #define RHMAP_HAS_STR(b, string_key) RHMAP_HAS_FULL(b, rhmap_hash_string(string_key), string_key) |
| 147 | #define RHMAP_DEL_STR(b, string_key) RHMAP_DEL_FULL(b, rhmap_hash_string(string_key), string_key) |
| 148 | #define RHMAP_PTR_STR(b, string_key) RHMAP_PTR_FULL(b, rhmap_hash_string(string_key), string_key) |
| 149 | #define RHMAP_IDX_STR(b, string_key) RHMAP_IDX_FULL(b, rhmap_hash_string(string_key), string_key) |
| 150 | |
| 151 | RHMAP__UNUSED static uint32_t rhmap_hash_string(const char* str) |
| 152 | { |
| 153 | unsigned char c; |
| 154 | uint32_t hash = (uint32_t)0x811c9dc5; |
| 155 | while ((c = (unsigned char)*(str++)) != '\0') |
| 156 | hash = ((hash * (uint32_t)0x01000193) ^ (uint32_t)c); |
| 157 | return (hash ? hash : 1); |
| 158 | } |
| 159 | |
| 160 | struct rhmap__hdr { size_t len, maxlen; uint32_t *keys; char** key_strs; }; |
| 161 | #define RHMAP__HDR(b) (((struct rhmap__hdr *)&(b)[-1])-1) |
| 162 | #define RHMAP__GROW(b, n) (*(void**)(&(b)) = rhmap__grow((void*)(b), sizeof(*(b)), (size_t)(n))) |
| 163 | #define RHMAP__FIT1(b) ((b) && RHMAP_LEN(b) * 2 <= RHMAP_MAX(b) ? 0 : RHMAP__GROW(b, 0)) |
| 164 | |
| 165 | RHMAP__UNUSED static void* rhmap__grow(void* old_ptr, size_t elem_size, size_t reserve) |
| 166 | { |
| 167 | struct rhmap__hdr *old_hdr = (old_ptr ? ((struct rhmap__hdr *)((char*)old_ptr-elem_size))-1 : NULL); |
| 168 | struct rhmap__hdr *new_hdr; |
| 169 | char *new_vals; |
| 170 | size_t new_max = (old_ptr ? old_hdr->maxlen * 2 + 1 : 15); |
| 171 | for (; new_max / 2 <= reserve; new_max = new_max * 2 + 1) |
| 172 | if (new_max == (size_t)-1) |
| 173 | return old_ptr; /* overflow */ |
| 174 | |
| 175 | new_hdr = (struct rhmap__hdr *)malloc(sizeof(struct rhmap__hdr) + (new_max + 2) * elem_size); |
| 176 | if (!new_hdr) |
| 177 | return old_ptr; /* out of memory */ |
| 178 | |
| 179 | new_hdr->maxlen = new_max; |
| 180 | new_hdr->keys = (uint32_t *)calloc(new_max + 1, sizeof(uint32_t)); |
| 181 | if (!new_hdr->keys) |
| 182 | { |
| 183 | /* out of memory */ |
| 184 | free(new_hdr); |
| 185 | return old_ptr; |
| 186 | } |
| 187 | new_hdr->key_strs = (char**)calloc(new_max + 1, sizeof(char*)); |
| 188 | if (!new_hdr->key_strs) |
| 189 | { |
| 190 | /* out of memory */ |
| 191 | free(new_hdr->keys); |
| 192 | free(new_hdr); |
| 193 | return old_ptr; |
| 194 | } |
| 195 | |
| 196 | new_vals = ((char*)(new_hdr + 1)) + elem_size; |
| 197 | if (old_ptr) |
| 198 | { |
| 199 | size_t i; |
| 200 | char* old_vals = ((char*)(old_hdr + 1)) + elem_size; |
| 201 | for (i = 0; i <= old_hdr->maxlen; i++) |
| 202 | { |
| 203 | uint32_t key, j; |
| 204 | if (!old_hdr->keys[i]) |
| 205 | continue; |
| 206 | for (key = old_hdr->keys[i], j = key;; j++) |
| 207 | { |
| 208 | if (!new_hdr->keys[j &= new_hdr->maxlen]) |
| 209 | { |
| 210 | new_hdr->keys[j] = key; |
| 211 | new_hdr->key_strs[j] = old_hdr->key_strs[i]; |
| 212 | memcpy(new_vals + j * elem_size, old_vals + i * elem_size, elem_size); |
| 213 | break; |
| 214 | } |
| 215 | } |
| 216 | } |
| 217 | memcpy(new_vals - elem_size, old_vals - elem_size, elem_size); |
| 218 | new_hdr->len = old_hdr->len; |
| 219 | free(old_hdr->keys); |
| 220 | free(old_hdr->key_strs); |
| 221 | free(old_hdr); |
| 222 | } |
| 223 | else |
| 224 | { |
| 225 | memset(new_vals - elem_size, 0, elem_size); |
| 226 | new_hdr->len = 0; |
| 227 | } |
| 228 | return new_vals; |
| 229 | } |
| 230 | |
| 231 | RHMAP__UNUSED static ptrdiff_t rhmap__idx(struct rhmap__hdr* hdr, uint32_t key, const char * str, int add, size_t del) |
| 232 | { |
| 233 | uint32_t i; |
| 234 | |
| 235 | if (!key) |
| 236 | return (ptrdiff_t)-1; |
| 237 | |
| 238 | for (i = key;; i++) |
| 239 | { |
| 240 | if (hdr->keys[i &= hdr->maxlen] == key && (!hdr->key_strs[i] || !str || !strcmp(hdr->key_strs[i], str))) |
| 241 | { |
| 242 | if (del) |
| 243 | { |
| 244 | hdr->len--; |
| 245 | hdr->keys[i] = 0; |
| 246 | free(hdr->key_strs[i]); |
| 247 | hdr->key_strs[i] = NULL; |
| 248 | while ((key = hdr->keys[i = (i + 1) & hdr->maxlen]) != 0) |
| 249 | { |
| 250 | if ((key = (uint32_t)rhmap__idx(hdr, key, hdr->key_strs[i], 1, 0)) == i) continue; |
| 251 | hdr->len--; |
| 252 | hdr->keys[i] = 0; |
| 253 | free(hdr->key_strs[i]); |
| 254 | hdr->key_strs[i] = NULL; |
| 255 | memcpy(((char*)(hdr + 1)) + (key + 1) * del, |
| 256 | ((char*)(hdr + 1)) + (i + 1) * del, del); |
| 257 | } |
| 258 | } |
| 259 | return (ptrdiff_t)i; |
| 260 | } |
| 261 | if (!hdr->keys[i]) |
| 262 | { |
| 263 | if (add) { hdr->len++; hdr->keys[i] = key; if (str) hdr->key_strs[i] = strdup(str); return (ptrdiff_t)i; } |
| 264 | return (ptrdiff_t)-1; |
| 265 | } |
| 266 | } |
| 267 | } |
| 268 | |
| 269 | RHMAP__UNUSED static void rhmap__free(struct rhmap__hdr* hdr) |
| 270 | { |
| 271 | size_t i; |
| 272 | for (i=0;i<hdr->maxlen+1;i++) |
| 273 | { |
| 274 | free(hdr->key_strs[i]); |
| 275 | } |
| 276 | free(hdr->key_strs); |
| 277 | free(hdr->keys); |
| 278 | free(hdr); |
| 279 | } |
| 280 | |
| 281 | #if defined(_MSC_VER) |
| 282 | #pragma warning(pop) |
| 283 | #endif |
| 284 | |
| 285 | #endif |