Commit | Line | Data |
---|---|---|
3719602c PC |
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 |