deps/libretro-common/include/array/rhmap.h

   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