1 /* stb_ds.h - v0.4 - public domain data structures - Sean Barrett 2019
2
3 This is a single-header-file library that provides easy-to-use
4 dynamic arrays and hash tables for C (also works in C++).
5
6 For a gentle introduction:
7 http://nothings.org/stb_ds
8
9 To use this library, do this in *one* C or C++ file:
10 #define STB_DS_IMPLEMENTATION
11 #include "stb_ds.h"
12
13 TABLE OF CONTENTS
14
15 Table of Contents
16 Compile-time options
17 License
18 Documentation
19 Notes
20 Notes - Dynamic arrays
21 Notes - Hash maps
22 Credits
23
24 COMPILE-TIME OPTIONS
25
26 #define STBDS_NO_SHORT_NAMES
27
28 This flag needs to be set globally.
29
30 By default stb_ds exposes shorter function names that are not qualified
31 with the "stbds_" prefix. If these names conflict with the names in your
32 code, define this flag.
33
34 #define STBDS_SIPHASH_2_4
35
36 This flag only needs to be set in the file containing #define STB_DS_IMPLEMENTATION.
37
38 By default stb_ds.h hashes using a weaker variant of SipHash and a custom hash for
39 4- and 8-byte keys. On 64-bit platforms, you can define the above flag to force
40 stb_ds.h to use specification-compliant SipHash-2-4 for all keys. Doing so makes
41 hash table insertion about 20% slower on 4- and 8-byte keys, 5% slower on
42 64-byte keys, and 10% slower on 256-byte keys on my test computer.
43
44 LICENSE
45
46 Placed in the public domain and also MIT licensed.
47 See end of file for detailed license information.
48
49 DOCUMENTATION
50
51 Dynamic Arrays
52
53 Non-function interface:
54
55 Declare an empty dynamic array of type T
56 T* foo = NULL;
57
58 Access the i'th item of a dynamic array 'foo' of type T, T* foo:
59 foo[i]
60
61 Functions (actually macros)
62
63 arrfree:
64 void arrfree(T*);
65 Frees the array.
66
67 arrlen:
68 ptrdiff_t arrlen(T*);
69 Returns the number of elements in the array.
70
71 arrlenu:
72 size_t arrlenu(T*);
73 Returns the number of elements in the array as an unsigned type.
74
75 arrpop:
76 T arrpop(T* a)
77 Removes the final element of the array and returns it.
78
79 arrput:
80 T arrput(T* a, T b);
81 Appends the item b to the end of array a. Returns b.
82
83 arrins:
84 T arrins(T* a, int p, T b);
85 Inserts the item b into the middle of array a, into a[p],
86 moving the rest of the array over. Returns b.
87
88 arrinsn:
89 void arrins(T* a, int p, int n);
90 Inserts n uninitialized items into array a starting at a[p],
91 moving the rest of the array over.
92
93 arrdel:
94 void arrdel(T* a, int p);
95 Deletes the element at a[p], moving the rest of the array over.
96
97 arrdeln:
98 void arrdel(T* a, int p, int n);
99 Deletes n elements starting at a[p], moving the rest of the array over.
100
101 arrdelswap:
102 void arrdelswap(T* a, int p);
103 Deletes the element at a[p], replacing it with the element from
104 the end of the array. O(1) performance.
105
106 arrsetlen:
107 void arrsetlen(T* a, int n);
108 Changes the length of the array to n. Allocates uninitialized
109 slots at the end if necessary.
110
111 arrsetcap:
112 size_t arrsetcap(T* a, int n);
113 Sets the length of allocated storage to at least n. It will not
114 change the length of the array.
115
116 arrcap:
117 size_t arrcap(T* a);
118 Returns the number of total elements the array can contain without
119 needing to be reallocated.
120
121 Hash maps & String hash maps
122
123 Given T is a structure type: struct { TK key; TV value; }. Note that some
124 functions do not require TV value and can have other fields. For string
125 hash maps, TK must be 'char *'.
126
127 Special interface:
128
129 stbds_rand_seed:
130 void stbds_rand_seed(size_t seed);
131 For security against adversarially chosen data, you should seed the
132 library with a strong random number. Or at least seed it with time().
133
134 stbds_hash_string:
135 size_t stbds_hash_string(char *str, size_t seed);
136 Returns a hash value for a string.
137
138 stbds_hash_bytes:
139 size_t stbds_hash_bytes(void *p, size_t len, size_t seed);
140 These functions hash an arbitrary number of bytes. The function
141 uses a custom hash for 4- and 8-byte data, and a weakened version
142 of SipHash for everything else. On 64-bit platforms you can get
143 specification-compliant SipHash-2-4 on all data by defining
144 STBDS_SIPHASH_2_4, at a significant cost in speed.
145
146 Non-function interface:
147
148 Declare an empty hash map of type T
149 T* foo = NULL;
150
151 Access the i'th entry in a hash table T* foo:
152 foo[i]
153
154 Function interface (actually macros):
155
156 hmfree
157 shfree
158 void hmfree(T*);
159 void shfree(T*);
160 Frees the hashmap and sets the pointer to NULL.
161
162 hmlen
163 shlen
164 ptrdiff_t hmlen(T*)
165 ptrdiff_t shlen(T*)
166 Returns the number of elements in the hashmap.
167
168 hmlenu
169 shlenu
170 size_t hmlenu(T*)
171 size_t shlenu(T*)
172 Returns the number of elements in the hashmap.
173
174 hmgeti
175 shgeti
176 ptrdiff_t hmgeti(T*, TK key)
177 ptrdiff_t shgeti(T*, char* key)
178 Returns the index in the hashmap which has the key 'key', or -1
179 if the key is not present.
180
181 hmget
182 shget
183 TV hmget(T*, TK key)
184 TV shget(T*, char* key)
185 Returns the value corresponding to 'key' in the hashmap.
186 The structure must have a 'value' field
187
188 hmgets
189 shgets
190 T hmgets(T*, TK key)
191 T shgets(T*, char* key)
192 Returns the structure corresponding to 'key' in the hashmap.
193
194 hmdefault
195 shdefault
196 TV hmdefault(T*, TV value)
197 TV shdefault(T*, TV value)
198 Sets the default value for the hashmap, the value which will be
199 returned by hmget/shget if the key is not present.
200
201 hmdefaults
202 shdefaults
203 TV hmdefaults(T*, T item)
204 TV shdefaults(T*, T item)
205 Sets the default struct for the hashmap, the contents which will be
206 returned by hmgets/shgets if the key is not present.
207
208 hmput
209 shput
210 TV hmput(T*, TK key, TV value)
211 TV shput(T*, char* key, TV value)
212 Inserts a <key,value> pair into the hashmap. If the key is already
213 present in the hashmap, updates its value.
214
215 hmputs
216 shputs
217 T hmputs(T*, T item)
218 T shputs(T*, T item)
219 Inserts a struct with T.key and T.value into the hashmap. If the struct is already
220 present in the hashmap, updates it.
221
222 hmdel
223 shdel
224 int hmdel(T*, TK key)
225 int shdel(T*, char* key)
226 If 'key' is in the hashmap, deletes its entry and returns 1.
227 Otherwise returns 0.
228
229 Function interface (actually macros) for strings only:
230
231 sh_new_strdup
232 void sh_new_strdup(T*);
233 Overwrites the existing pointer with a newly allocated
234 string hashmap which will automatically allocate and free
235 each string key using malloc/free
236
237 sh_new_arena
238 void sh_new_arena(T*);
239 Overwrites the existing pointer with a newly allocated
240 string hashmap which will automatically allocate each string
241 key to a string arena. Every string key ever used by this
242 hash table remains in the arena until the arena is freed.
243 Additionally, any key which is deleted and reinserted will
244 be allocated multiple times in the string arena.
245
246 NOTES
247
248 * These data structures are realloc'd when they grow, and the macro "functions"
249 write to the provided pointer. This means: (a) the pointer must be an lvalue,
250 and (b) the pointer to the data structure is not stable, and you must maintain
251 it the same as you would a realloc'd pointer. For example, if you pass a pointer
252 to a dynamic array to a function which updates it, the function must return
253 back the new pointer to the caller. This is the price of trying to do this in C.
254
255 * You iterate over the contents of a dynamic array and a hashmap in exactly
256 the same way, using arrlen/hmlen/shlen:
257
258 for (i=0; i < arrlen(foo); ++i)
259 ... foo[i] ...
260
261 * All operations except arrins/arrdel are O(1) amortized, but individual
262 operations can be slow, so these data structures may not be suitable
263 for real time use. Dynamic arrays double in capacity as needed, so
264 elements are copied an average of once. Hash tables double/halve
265 their size as needed, with appropriate hysteresis to maintain O(1)
266 performance.
267
268 NOTES - DYNAMIC ARRAY
269
270 * If you know how long a dynamic array is going to be in advance, you can avoid
271 extra memory allocations by using arrsetlen to allocate it to that length in
272 advance and use foo[n] while filling it out, or arrsetcap to allocate the memory
273 for that length and use arrput/arrpush as normal.
274
275 * Unlike some other versions of the dynamic array, this version should
276 be safe to use with strict-aliasing optimizations.
277
278 NOTES - HASH MAP
279
280 * For compilers other than GCC and clang (e.g. Visual Studio), for hmput/hmget/hmdel
281 and variants, the key must be an lvalue (so the macro can take the address of it).
282 Extensions are used that eliminate this requirement if you're using C99 and later
283 in GCC or clang, or if you're using C++ in GCC.
284
285 * To test for presence of a key in a hashmap, just do 'hmgeti(foo,key) >= 0'.
286
287 * The iteration order of your data in the hashmap is determined solely by the
288 order of insertions and deletions. In particular, if you never delete, new
289 keys are always added at the end of the array. This will be consistent
290 across all platforms and versions of the library. However, you should not
291 attempt to serialize the internal hash table, as the hash is not consistent
292 between different platforms, and may change with future versions of the library.
293
294 * Use sh_new_arena() for string hashmaps that you never delete from. Initialize
295 with NULL if you're managing the memory for your strings, or your strings are
296 never freed (at least until the hashmap is freed). Otherwise, use sh_new_strdup().
297 @TODO: make an arena variant that garbage collects the strings with a trivial
298 copy collector into a new arena whenever the table shrinks / rebuilds. Since
299 current arena recommendation is to only use arena if it never deletes, then
300 this can just replace current arena implementation.
301
302 * If adversarial input is a serious concern and you're on a 64-bit platform,
303 enable STBDS_SIPHASH_2_4 (see the 'Compile-time options' section), and pass
304 a strong random number to stbds_rand_seed.
305
306 * The default value for the hash table is stored in foo[-1], so if you
307 use code like 'hmget(T,k)->value = 5' you can overwrite the value
308 stored by hmdefault if 'k' is not present.
309
310 CREDITS
311
312 Sean Barrett -- library, idea for dynamic array API/implementation
313 Per Vognsen -- idea for hash table API/implementation
314 Rafael Sachetto -- arrpop()
315 */
316
317 #ifdef STBDS_UNIT_TESTS
318 #define _CRT_SECURE_NO_WARNINGS
319 #endif
320
321 #ifndef INCLUDE_STB_DS_H
322 #define INCLUDE_STB_DS_H
323
324 #include <stdlib.h>
325 #include <stddef.h>
326 #include <string.h>
327
328 #ifndef STBDS_NO_SHORT_NAMES
329 #define arrlen stbds_arrlen
330 #define arrlenu stbds_arrlenu
331 #define arrput stbds_arrput
332 #define arrpush stbds_arrput
333 #define arrpop stbds_arrpop
334 #define arrfree stbds_arrfree
335 #define arraddn stbds_arraddn
336 #define arrsetlen stbds_arrsetlen
337 #define arrlast stbds_arrlast
338 #define arrins stbds_arrins
339 #define arrinsn stbds_arrinsn
340 #define arrdel stbds_arrdel
341 #define arrdeln stbds_arrdeln
342 #define arrdelswap stbds_arrdelswap
343 #define arrcap stbds_arrcap
344 #define arrsetcap stbds_arrsetcap
345
346 #define hmput stbds_hmput
347 #define hmputs stbds_hmputs
348 #define hmget stbds_hmget
349 #define hmgets stbds_hmgets
350 #define hmgetp stbds_hmgetp
351 #define hmgeti stbds_hmgeti
352 #define hmdel stbds_hmdel
353 #define hmlen stbds_hmlen
354 #define hmlenu stbds_hmlenu
355 #define hmfree stbds_hmfree
356 #define hmdefault stbds_hmdefault
357 #define hmdefaults stbds_hmdefaults
358
359 #define shput stbds_shput
360 #define shputs stbds_shputs
361 #define shget stbds_shget
362 #define shgets stbds_shgets
363 #define shgetp stbds_shgetp
364 #define shgeti stbds_shgeti
365 #define shdel stbds_shdel
366 #define shlen stbds_shlen
367 #define shlenu stbds_shlenu
368 #define shfree stbds_shfree
369 #define shdefault stbds_shdefault
370 #define shdefaults stbds_shdefaults
371 #define sh_new_arena stbds_sh_new_arena
372 #define sh_new_strdup stbds_sh_new_strdup
373
374 #define stralloc stbds_stralloc
375 #define strreset stbds_strreset
376 #endif
377 #ifdef __cplusplus
378 extern "C" {
379 #endif
380
381 // for security against attackers, seed the library with a random number, at least time() but stronger is better
382 extern void stbds_rand_seed(size_t seed);
383
384 // these are the hash functions used internally if you want to test them or use them for other purposes
385 extern size_t stbds_hash_bytes(void *p, size_t len, size_t seed);
386 extern size_t stbds_hash_string(char *str, size_t seed);
387
388 // this is a simple string arena allocator, initialize with e.g. 'stbds_string_arena my_arena={0}'.
389 typedef struct stbds_string_arena stbds_string_arena;
390 extern char * stbds_stralloc(stbds_string_arena *a, char *str);
391 extern void stbds_strreset(stbds_string_arena *a);
392
393 // have to #define STBDS_UNIT_TESTS to call this
394 extern void stbds_unit_tests(void);
395
396 ///////////////
397 //
398 // Everything below here is implementation details
399 //
400
401 extern void * stbds_arrgrowf(void *a, size_t elemsize, size_t addlen, size_t min_cap);
402 extern void stbds_hmfree_func(void *p, size_t elemsize, size_t keyoff);
403 extern void * stbds_hmget_key(void *a, size_t elemsize, void *key, size_t keysize, int mode);
404 extern void * stbds_hmput_default(void *a, size_t elemsize);
405 extern void * stbds_hmput_key(void *a, size_t elemsize, void *key, size_t keysize, int mode);
406 extern void * stbds_hmdel_key(void *a, size_t elemsize, void *key, size_t keysize, size_t keyoffset, int mode);
407 extern void * stbds_shmode_func(size_t elemsize, int mode);
408
409 #ifdef __cplusplus
410 }
411 #endif
412
413 #if defined(__GNUC__) || defined(__clang__)
414 #define STBDS_HAS_TYPEOF
415 #ifdef __cplusplus
416 //#define STBDS_HAS_LITERAL_ARRAY // this is currently broken for clang
417 #endif
418 #endif
419
420 #if !defined(__cplusplus)
421 #if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L
422 #define STBDS_HAS_LITERAL_ARRAY
423 #endif
424 #endif
425
426 // this macro takes the address of the argument, but on gcc/clang can accept rvalues
427 #if defined(STBDS_HAS_LITERAL_ARRAY) && defined(STBDS_HAS_TYPEOF)
428 #if __clang__
429 #define STBDS_ADDRESSOF(typevar, value) ((__typeof__(typevar)[1]){value}) // literal array decays to pointer to value
430 #else
431 #define STBDS_ADDRESSOF(typevar, value) ((typeof(typevar)[1]){value}) // literal array decays to pointer to value
432 #endif
433 #else
434 #define STBDS_ADDRESSOF(typevar, value) &(value)
435 #endif
436
437 #define STBDS_OFFSETOF(var,field) ((char *) &(var)->field - (char *) (var))
438
439 #define stbds_header(t) ((stbds_array_header *) (t) - 1)
440 #define stbds_temp(t) stbds_header(t)->temp
441
442 #define stbds_arrsetcap(a,n) (stbds_arrgrow(a,0,n))
443 #define stbds_arrsetlen(a,n) ((stbds_arrcap(a) < n ? stbds_arrsetcap(a,n),0 : 0), (a) ? stbds_header(a)->length = (n) : 0)
444 #define stbds_arrcap(a) ((a) ? stbds_header(a)->capacity : 0)
445 #define stbds_arrlen(a) ((a) ? (ptrdiff_t) stbds_header(a)->length : 0)
446 #define stbds_arrlenu(a) ((a) ? stbds_header(a)->length : 0)
447 #define stbds_arrput(a,v) (stbds_arrmaybegrow(a,1), (a)[stbds_header(a)->length++] = (v))
448 #define stbds_arrpush stbds_arrput // synonym
449 #define stbds_arrpop(a) (stbds_header(a)->length--, (a)[stbds_header(a)->length])
450 #define stbds_arraddn(a,n) (stbds_arrmaybegrow(a,n), stbds_header(a)->length += (n))
451 #define stbds_arrlast(a) ((a)[stbds_header(a)->length-1])
452 #define stbds_arrfree(a) ((void) ((a) ? realloc(stbds_header(a),0) : 0), (a)=NULL)
453 #define stbds_arrdel(a,i) stbds_arrdeln(a,i,1)
454 #define stbds_arrdeln(a,i,n) (memmove(&(a)[i], &(a)[(i)+(n)], sizeof *(a) * (stbds_header(a)->length-(n)-(i))), stbds_header(a)->length -= (n))
455 #define stbds_arrdelswap(a,i) ((a)[i] = stbds_arrlast(a), stbds_header(a)->length -= 1)
456 #define stbds_arrinsn(a,i,n) (stbds_arraddn((a),(n)), memmove(&(a)[(i)+(n)], &(a)[i], sizeof *(a) * (stbds_header(a)->length-(n)-(i))))
457 #define stbds_arrins(a,i,v) (stbds_arrinsn((a),(i),1), (a)[i]=(v))
458
459 #define stbds_arrmaybegrow(a,n) ((!(a) || stbds_header(a)->length + (n) > stbds_header(a)->capacity) \
460 ? (stbds_arrgrow(a,n,0),0) : 0)
461
462 #define stbds_arrgrow(a,b,c) ((a) = stbds_arrgrowf_wrapper((a), sizeof *(a), (b), (c)))
463
464 #define stbds_hmput(t, k, v) \
465 ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), (void*) STBDS_ADDRESSOF((t)->key, (k)), sizeof (t)->key, 0), \
466 (t)[stbds_temp((t)-1)].key = (k), \
467 (t)[stbds_temp((t)-1)].value = (v))
468
469 #define stbds_hmputs(t, s) \
470 ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), &(s).key, sizeof (s).key, STBDS_HM_BINARY), \
471 (t)[stbds_temp((t)-1)] = (s))
472
473 #define stbds_hmgeti(t,k) \
474 ((t) = stbds_hmget_key_wrapper((t), sizeof *(t), (void*) STBDS_ADDRESSOF((t)->key, (k)), sizeof (t)->key, STBDS_HM_BINARY), \
475 stbds_temp((t)-1))
476
477 #define stbds_hmgetp(t, k) \
478 ((void) stbds_hmgeti(t,k), &(t)[stbds_temp((t)-1)])
479
480 #define stbds_hmdel(t,k) \
481 (((t) = stbds_hmdel_key_wrapper((t),sizeof *(t), (void*) STBDS_ADDRESSOF((t)->key, (k)), sizeof (t)->key, STBDS_OFFSETOF((t),key), STBDS_HM_BINARY)),(t)?stbds_temp((t)-1):0)
482
483 #define stbds_hmdefault(t, v) \
484 ((t) = stbds_hmput_default_wrapper((t), sizeof *(t)), (t)[-1].value = (v))
485
486 #define stbds_hmdefaults(t, s) \
487 ((t) = stbds_hmput_default_wrapper((t), sizeof *(t)), (t)[-1] = (s))
488
489 #define stbds_hmfree(p) \
490 ((void) ((p) != NULL ? stbds_hmfree_func((p)-1,sizeof*(p),STBDS_OFFSETOF((p),key)),0 : 0),(p)=NULL)
491
492 #define stbds_hmgets(t, k) (*stbds_hmgetp(t,k))
493 #define stbds_hmget(t, k) (stbds_hmgetp(t,k)->value)
494 #define stbds_hmlen(t) (stbds_arrlen((t)-1)-1)
495 #define stbds_hmlenu(t) (stbds_arrlenu((t)-1)-1)
496
497 #define stbds_shput(t, k, v) \
498 ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), (void*) (k), sizeof (t)->key, STBDS_HM_STRING), \
499 (t)[stbds_temp(t-1)].value = (v))
500
501 #define stbds_shputs(t, s) \
502 ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), (void*) (s).key, sizeof (s).key, STBDS_HM_STRING), \
503 (t)[stbds_temp(t-1)] = (s))
504
505 #define stbds_shgeti(t,k) \
506 ((t) = stbds_hmget_key_wrapper((t), sizeof *(t), (void*) (k), sizeof (t)->key, STBDS_HM_STRING), \
507 stbds_temp(t))
508
509 #define stbds_shgetp(t, k) \
510 ((void) stbds_shgeti(t,k), &(t)[stbds_temp(t-1)])
511
512 #define stbds_shdel(t,k) \
513 (((t) = stbds_hmdel_key_wrapper((t),sizeof *(t), (void*) (k), sizeof (t)->key, STBDS_OFFSETOF((t),key), STBDS_HM_STRING)),(t)?stbds_temp((t)-1):0)
514
515 #define stbds_sh_new_arena(t) \
516 ((t) = stbds_shmode_func_wrapper(t, sizeof *(t), STBDS_SH_ARENA))
517 #define stbds_sh_new_strdup(t) \
518 ((t) = stbds_shmode_func_wrapper(t, sizeof *(t), STBDS_SH_STRDUP))
519
520 #define stbds_shdefault(t, v) stbds_hmdefault(t,v)
521 #define stbds_shdefaults(t, s) stbds_hmdefaults(t,s)
522
523 #define stbds_shfree stbds_hmfree
524 #define stbds_shlenu stbds_hmlenu
525
526 #define stbds_shgets(t, k) (*stbds_shgetp(t,k))
527 #define stbds_shget(t, k) (stbds_shgetp(t,k)->value)
528 #define stbds_shlen stbds_hmlen
529
530 typedef struct
531 {
532 size_t length;
533 size_t capacity;
534 void * hash_table;
535 ptrdiff_t temp;
536 } stbds_array_header;
537
538 typedef struct stbds_string_block
539 {
540 struct stbds_string_block *next;
541 char storage[8];
542 } stbds_string_block;
543
544 struct stbds_string_arena
545 {
546 stbds_string_block *storage;
547 size_t remaining;
548 unsigned char block;
549 unsigned char mode; // this isn't used by the string arena itself
550 };
551
552 enum
553 {
554 STBDS_HM_BINARY,
555 STBDS_HM_STRING,
556 };
557
558 enum
559 {
560 STBDS_SH_NONE,
561 STBDS_SH_STRDUP,
562 STBDS_SH_ARENA
563 };
564
565 #ifdef __cplusplus
566 // in C we use implicit assignment from these void*-returning functions to T*.
567 // in C++ these templates make the same code work
stbds_arrgrowf_wrapper(T * a,size_t elemsize,size_t addlen,size_t min_cap)568 template<class T> static T * stbds_arrgrowf_wrapper(T *a, size_t elemsize, size_t addlen, size_t min_cap) {
569 return (T*)stbds_arrgrowf((void *)a, elemsize, addlen, min_cap);
570 }
stbds_hmget_key_wrapper(T * a,size_t elemsize,void * key,size_t keysize,int mode)571 template<class T> static T * stbds_hmget_key_wrapper(T *a, size_t elemsize, void *key, size_t keysize, int mode) {
572 return (T*)stbds_hmget_key((void*)a, elemsize, key, keysize, mode);
573 }
stbds_hmput_default_wrapper(T * a,size_t elemsize)574 template<class T> static T * stbds_hmput_default_wrapper(T *a, size_t elemsize) {
575 return (T*)stbds_hmput_default((void *)a, elemsize);
576 }
stbds_hmput_key_wrapper(T * a,size_t elemsize,void * key,size_t keysize,int mode)577 template<class T> static T * stbds_hmput_key_wrapper(T *a, size_t elemsize, void *key, size_t keysize, int mode) {
578 return (T*)stbds_hmput_key((void*)a, elemsize, key, keysize, mode);
579 }
stbds_hmdel_key_wrapper(T * a,size_t elemsize,void * key,size_t keysize,size_t keyoffset,int mode)580 template<class T> static T * stbds_hmdel_key_wrapper(T *a, size_t elemsize, void *key, size_t keysize, size_t keyoffset, int mode){
581 return (T*)stbds_hmdel_key((void*)a, elemsize, key, keysize, keyoffset, mode);
582 }
stbds_shmode_func_wrapper(T *,size_t elemsize,int mode)583 template<class T> static T * stbds_shmode_func_wrapper(T *, size_t elemsize, int mode) {
584 return (T*)stbds_shmode_func(elemsize, mode);
585 }
586 #else
587 #define stbds_arrgrowf_wrapper stbds_arrgrowf
588 #define stbds_hmget_key_wrapper stbds_hmget_key
589 #define stbds_hmput_default_wrapper stbds_hmput_default
590 #define stbds_hmput_key_wrapper stbds_hmput_key
591 #define stbds_hmdel_key_wrapper stbds_hmdel_key
592 #define stbds_shmode_func_wrapper(t,e,m) stbds_shmode_func(e,m)
593 #endif
594
595 #endif // INCLUDE_STB_DS_H
596
597
598 //////////////////////////////////////////////////////////////////////////////
599 //
600 // IMPLEMENTATION
601 //
602
603 #ifdef STB_DS_IMPLEMENTATION
604 #include <assert.h>
605 #include <string.h>
606
607 #ifndef STBDS_ASSERT
608 #define STBDS_ASSERT_WAS_UNDEFINED
609 #define STBDS_ASSERT(x) ((void) 0)
610 #endif
611
612 #ifdef STBDS_STATISTICS
613 #define STBDS_STATS(x) x
614 size_t stbds_array_grow;
615 size_t stbds_hash_grow;
616 size_t stbds_hash_shrink;
617 size_t stbds_hash_rebuild;
618 size_t stbds_hash_probes;
619 size_t stbds_hash_alloc;
620 size_t stbds_rehash_probes;
621 size_t stbds_rehash_items;
622 #else
623 #define STBDS_STATS(x)
624 #endif
625
626 //
627 // stbds_arr implementation
628 //
629
stbds_arrgrowf(void * a,size_t elemsize,size_t addlen,size_t min_cap)630 void *stbds_arrgrowf(void *a, size_t elemsize, size_t addlen, size_t min_cap)
631 {
632 void *b;
633 size_t min_len = stbds_arrlen(a) + addlen;
634
635 // compute the minimum capacity needed
636 if (min_len > min_cap)
637 min_cap = min_len;
638
639 if (min_cap <= stbds_arrcap(a))
640 return a;
641
642 // increase needed capacity to guarantee O(1) amortized
643 if (min_cap < 2 * stbds_arrcap(a))
644 min_cap = 2 * stbds_arrcap(a);
645 else if (min_cap < 4)
646 min_cap = 4;
647
648 b = realloc((a) ? stbds_header(a) : 0, elemsize * min_cap + sizeof(stbds_array_header));
649 b = (char *) b + sizeof(stbds_array_header);
650 if (a == NULL) {
651 stbds_header(b)->length = 0;
652 stbds_header(b)->hash_table = 0;
653 } else {
654 STBDS_STATS(++stbds_array_grow);
655 }
656 stbds_header(b)->capacity = min_cap;
657 return b;
658 }
659
660 //
661 // stbds_hm hash table implementation
662 //
663
664 #ifdef STBDS_INTERNAL_SMALL_BUCKET
665 #define STBDS_BUCKET_LENGTH 4
666 #else
667 #define STBDS_BUCKET_LENGTH 8
668 #endif
669
670 #define STBDS_BUCKET_SHIFT (STBDS_BUCKET_LENGTH == 8 ? 3 : 2)
671 #define STBDS_BUCKET_MASK (STBDS_BUCKET_LENGTH-1)
672 #define STBDS_CACHE_LINE_SIZE 64
673
674 #define STBDS_ALIGN_FWD(n,a) (((n) + (a) - 1) & ~((a)-1))
675
676 typedef struct
677 {
678 size_t hash [STBDS_BUCKET_LENGTH];
679 ptrdiff_t index[STBDS_BUCKET_LENGTH];
680 } stbds_hash_bucket; // in 32-bit, this is one 64-byte cache line; in 64-bit, each array is one 64-byte cache line
681
682 typedef struct
683 {
684 size_t slot_count;
685 size_t used_count;
686 size_t used_count_threshold;
687 size_t used_count_shrink_threshold;
688 size_t tombstone_count;
689 size_t tombstone_count_threshold;
690 size_t seed;
691 size_t slot_count_log2;
692 stbds_string_arena string;
693 stbds_hash_bucket *storage; // not a separate allocation, just 64-byte aligned storage after this struct
694 } stbds_hash_index;
695
696 #define STBDS_INDEX_EMPTY -1
697 #define STBDS_INDEX_DELETED -2
698 #define STBDS_INDEX_IN_USE(x) ((x) >= 0)
699
700 #define STBDS_HASH_EMPTY 0
701 #define STBDS_HASH_DELETED 1
702
703 static size_t stbds_hash_seed=0x31415926;
704
stbds_rand_seed(size_t seed)705 void stbds_rand_seed(size_t seed)
706 {
707 stbds_hash_seed = seed;
708 }
709
710 #define stbds_load_32_or_64(var, temp, v32, v64_hi, v64_lo) \
711 temp = v64_lo ^ v32, temp <<= 16, temp <<= 16, temp >>= 16, temp >>= 16, /* discard if 32-bit */ \
712 var = v64_hi, var <<= 16, var <<= 16, /* discard if 32-bit */ \
713 var ^= temp ^ v32
714
715 #define STBDS_SIZE_T_BITS ((sizeof (size_t)) * 8)
716
stbds_probe_position(size_t hash,size_t slot_count,size_t slot_log2)717 static size_t stbds_probe_position(size_t hash, size_t slot_count, size_t slot_log2)
718 {
719 size_t pos;
720 pos = hash & (slot_count-1);
721 #ifdef STBDS_INTERNAL_BUCKET_START
722 pos &= ~STBDS_BUCKET_MASK;
723 #endif
724 return pos;
725 }
726
stbds_log2(size_t slot_count)727 static size_t stbds_log2(size_t slot_count)
728 {
729 size_t n=0;
730 while (slot_count > 1) {
731 slot_count >>= 1;
732 ++n;
733 }
734 return n;
735 }
736
stbds_make_hash_index(size_t slot_count,stbds_hash_index * ot)737 static stbds_hash_index *stbds_make_hash_index(size_t slot_count, stbds_hash_index *ot)
738 {
739 stbds_hash_index *t;
740 t = (stbds_hash_index *) realloc(0,(slot_count >> STBDS_BUCKET_SHIFT) * sizeof(stbds_hash_bucket) + sizeof(stbds_hash_index) + STBDS_CACHE_LINE_SIZE-1);
741 t->storage = (stbds_hash_bucket *) STBDS_ALIGN_FWD((size_t) (t+1), STBDS_CACHE_LINE_SIZE);
742 t->slot_count = slot_count;
743 t->slot_count_log2 = stbds_log2(slot_count);
744 t->tombstone_count = 0;
745 t->used_count = 0;
746
747 #if 0 // A1
748 t->used_count_threshold = slot_count*12/16; // if 12/16th of table is occupied, grow
749 t->tombstone_count_threshold = slot_count* 2/16; // if tombstones are 2/16th of table, rebuild
750 t->used_count_shrink_threshold = slot_count* 4/16; // if table is only 4/16th full, shrink
751 #elif 1 // A2
752 //t->used_count_threshold = slot_count*12/16; // if 12/16th of table is occupied, grow
753 //t->tombstone_count_threshold = slot_count* 3/16; // if tombstones are 3/16th of table, rebuild
754 //t->used_count_shrink_threshold = slot_count* 4/16; // if table is only 4/16th full, shrink
755
756 // compute without overflowing
757 t->used_count_threshold = slot_count - (slot_count>>2);
758 t->tombstone_count_threshold = (slot_count>>3) + (slot_count>>4);
759 t->used_count_shrink_threshold = slot_count >> 2;
760
761 #elif 0 // B1
762 t->used_count_threshold = slot_count*13/16; // if 13/16th of table is occupied, grow
763 t->tombstone_count_threshold = slot_count* 2/16; // if tombstones are 2/16th of table, rebuild
764 t->used_count_shrink_threshold = slot_count* 5/16; // if table is only 5/16th full, shrink
765 #else // C1
766 t->used_count_threshold = slot_count*14/16; // if 14/16th of table is occupied, grow
767 t->tombstone_count_threshold = slot_count* 2/16; // if tombstones are 2/16th of table, rebuild
768 t->used_count_shrink_threshold = slot_count* 6/16; // if table is only 6/16th full, shrink
769 #endif
770 // Following statistics were measured on a Core i7-6700 @ 4.00Ghz, compiled with clang 7.0.1 -O2
771 // Note that the larger tables have high variance as they were run fewer times
772 // A1 A2 B1 C1
773 // 0.10ms : 0.10ms : 0.10ms : 0.11ms : 2,000 inserts creating 2K table
774 // 0.96ms : 0.95ms : 0.97ms : 1.04ms : 20,000 inserts creating 20K table
775 // 14.48ms : 14.46ms : 10.63ms : 11.00ms : 200,000 inserts creating 200K table
776 // 195.74ms : 196.35ms : 203.69ms : 214.92ms : 2,000,000 inserts creating 2M table
777 // 2193.88ms : 2209.22ms : 2285.54ms : 2437.17ms : 20,000,000 inserts creating 20M table
778 // 65.27ms : 53.77ms : 65.33ms : 65.47ms : 500,000 inserts & deletes in 2K table
779 // 72.78ms : 62.45ms : 71.95ms : 72.85ms : 500,000 inserts & deletes in 20K table
780 // 89.47ms : 77.72ms : 96.49ms : 96.75ms : 500,000 inserts & deletes in 200K table
781 // 97.58ms : 98.14ms : 97.18ms : 97.53ms : 500,000 inserts & deletes in 2M table
782 // 118.61ms : 119.62ms : 120.16ms : 118.86ms : 500,000 inserts & deletes in 20M table
783 // 192.11ms : 194.39ms : 196.38ms : 195.73ms : 500,000 inserts & deletes in 200M table
784
785 if (slot_count <= STBDS_BUCKET_LENGTH)
786 t->used_count_shrink_threshold = 0;
787 // to avoid infinite loop, we need to guarantee that at least one slot is empty and will terminate probes
788 STBDS_ASSERT(t->used_count_threshold + t->tombstone_count_threshold < t->slot_count);
789 STBDS_STATS(++stbds_hash_alloc);
790 if (ot) {
791 t->string = ot->string;
792 // reuse old seed so we can reuse old hashes so below "copy out old data" doesn't do any hashing
793 t->seed = ot->seed;
794 } else {
795 size_t a,b,temp;
796 memset(&t->string, 0, sizeof(t->string));
797 t->seed = stbds_hash_seed;
798 // LCG
799 // in 32-bit, a = 2147001325 b = 715136305
800 // in 64-bit, a = 2862933555777941757 b = 3037000493
801 stbds_load_32_or_64(a,temp, 2147001325, 0x27bb2ee6, 0x87b0b0fd);
802 stbds_load_32_or_64(b,temp, 715136305, 0, 0xb504f32d);
803 stbds_hash_seed = stbds_hash_seed * a + b;
804 }
805
806 {
807 size_t i,j;
808 for (i=0; i < slot_count >> STBDS_BUCKET_SHIFT; ++i) {
809 stbds_hash_bucket *b = &t->storage[i];
810 for (j=0; j < STBDS_BUCKET_LENGTH; ++j)
811 b->hash[j] = STBDS_HASH_EMPTY;
812 for (j=0; j < STBDS_BUCKET_LENGTH; ++j)
813 b->index[j] = STBDS_INDEX_EMPTY;
814 }
815 }
816
817 // copy out the old data, if any
818 if (ot) {
819 size_t i,j;
820 t->used_count = ot->used_count;
821 for (i=0; i < ot->slot_count >> STBDS_BUCKET_SHIFT; ++i) {
822 stbds_hash_bucket *ob = &ot->storage[i];
823 for (j=0; j < STBDS_BUCKET_LENGTH; ++j) {
824 if (STBDS_INDEX_IN_USE(ob->index[j])) {
825 size_t hash = ob->hash[j];
826 size_t pos = stbds_probe_position(hash, t->slot_count, t->slot_count_log2);
827 size_t step = STBDS_BUCKET_LENGTH;
828 STBDS_STATS(++stbds_rehash_items);
829 for (;;) {
830 size_t limit,z;
831 stbds_hash_bucket *bucket;
832 bucket = &t->storage[pos >> STBDS_BUCKET_SHIFT];
833 STBDS_STATS(++stbds_rehash_probes);
834
835 for (z=pos & STBDS_BUCKET_MASK; z < STBDS_BUCKET_LENGTH; ++z) {
836 if (bucket->hash[z] == 0) {
837 bucket->hash[z] = hash;
838 bucket->index[z] = ob->index[j];
839 goto done;
840 }
841 }
842
843 limit = pos & STBDS_BUCKET_MASK;
844 for (z = 0; z < limit; ++z) {
845 if (bucket->hash[z] == 0) {
846 bucket->hash[z] = hash;
847 bucket->index[z] = ob->index[j];
848 goto done;
849 }
850 }
851
852 pos += step; // quadratic probing
853 step += STBDS_BUCKET_LENGTH;
854 pos &= (t->slot_count-1);
855 }
856 }
857 done:
858 ;
859 }
860 }
861 }
862
863 return t;
864 }
865
866 #define STBDS_ROTATE_LEFT(val, n) (((val) << (n)) | ((val) >> (STBDS_SIZE_T_BITS - (n))))
867 #define STBDS_ROTATE_RIGHT(val, n) (((val) >> (n)) | ((val) << (STBDS_SIZE_T_BITS - (n))))
868
stbds_hash_string(char * str,size_t seed)869 size_t stbds_hash_string(char *str, size_t seed)
870 {
871 size_t hash = seed;
872 while (*str)
873 hash = STBDS_ROTATE_LEFT(hash, 9) + (unsigned char) *str++;
874
875 // Thomas Wang 64-to-32 bit mix function, hopefully also works in 32 bits
876 hash ^= seed;
877 hash = (~hash) + (hash << 18);
878 hash ^= hash ^ STBDS_ROTATE_RIGHT(hash,31);
879 hash = hash * 21;
880 hash ^= hash ^ STBDS_ROTATE_RIGHT(hash,11);
881 hash += (hash << 6);
882 hash ^= STBDS_ROTATE_RIGHT(hash,22);
883 return hash+seed;
884 }
885
886 #ifdef STBDS_SIPHASH_2_4
887 #define STBDS_SIPHASH_C_ROUNDS 2
888 #define STBDS_SIPHASH_D_ROUNDS 4
889 typedef int STBDS_SIPHASH_2_4_can_only_be_used_in_64_bit_builds[sizeof(size_t) == 8 ? 1 : -1];
890 #endif
891
892 #ifndef STBDS_SIPHASH_C_ROUNDS
893 #define STBDS_SIPHASH_C_ROUNDS 1
894 #endif
895 #ifndef STBDS_SIPHASH_D_ROUNDS
896 #define STBDS_SIPHASH_D_ROUNDS 1
897 #endif
898
stbds_siphash_bytes(void * p,size_t len,size_t seed)899 static size_t stbds_siphash_bytes(void *p, size_t len, size_t seed)
900 {
901 unsigned char *d = (unsigned char *) p;
902 size_t i,j;
903 size_t v0,v1,v2,v3, data;
904
905 // hash that works on 32- or 64-bit registers without knowing which we have
906 // (computes different results on 32-bit and 64-bit platform)
907 // derived from siphash, but on 32-bit platforms very different as it uses 4 32-bit state not 4 64-bit
908 v0 = ((((size_t) 0x736f6d65 << 16) << 16) + 0x70736575) ^ seed;
909 v1 = ((((size_t) 0x646f7261 << 16) << 16) + 0x6e646f6d) ^ ~seed;
910 v2 = ((((size_t) 0x6c796765 << 16) << 16) + 0x6e657261) ^ seed;
911 v3 = ((((size_t) 0x74656462 << 16) << 16) + 0x79746573) ^ ~seed;
912
913 #ifdef STBDS_TEST_SIPHASH_2_4
914 // hardcoded with key material in the siphash test vectors
915 v0 ^= 0x0706050403020100ull ^ seed;
916 v1 ^= 0x0f0e0d0c0b0a0908ull ^ ~seed;
917 v2 ^= 0x0706050403020100ull ^ seed;
918 v3 ^= 0x0f0e0d0c0b0a0908ull ^ ~seed;
919 #endif
920
921 #define STBDS_SIPROUND() \
922 do { \
923 v0 += v1; v1 = STBDS_ROTATE_LEFT(v1, 13); v1 ^= v0; v0 = STBDS_ROTATE_LEFT(v0,STBDS_SIZE_T_BITS/2); \
924 v2 += v3; v3 = STBDS_ROTATE_LEFT(v3, 16); v3 ^= v2; \
925 v2 += v1; v1 = STBDS_ROTATE_LEFT(v1, 17); v1 ^= v2; v2 = STBDS_ROTATE_LEFT(v2,STBDS_SIZE_T_BITS/2); \
926 v0 += v3; v3 = STBDS_ROTATE_LEFT(v3, 21); v3 ^= v0; \
927 } while (0)
928
929 for (i=0; i+sizeof(size_t) <= len; i += sizeof(size_t), d += sizeof(size_t)) {
930 data = d[0] | (d[1] << 8) | (d[2] << 16) | (d[3] << 24);
931 data |= (size_t) (d[4] | (d[5] << 8) | (d[6] << 16) | (d[7] << 24)) << 16 << 16; // discarded if size_t == 4
932
933 v3 ^= data;
934 for (j=0; j < STBDS_SIPHASH_C_ROUNDS; ++j)
935 STBDS_SIPROUND();
936 v0 ^= data;
937 }
938 data = len << (STBDS_SIZE_T_BITS-8);
939 switch (len - i) {
940 case 7: data |= ((size_t) d[6] << 24) << 24;
941 case 6: data |= ((size_t) d[5] << 20) << 20;
942 case 5: data |= ((size_t) d[4] << 16) << 16;
943 case 4: data |= (d[3] << 24);
944 case 3: data |= (d[2] << 16);
945 case 2: data |= (d[1] << 8);
946 case 1: data |= d[0];
947 case 0: break;
948 }
949 v3 ^= data;
950 for (j=0; j < STBDS_SIPHASH_C_ROUNDS; ++j)
951 STBDS_SIPROUND();
952 v0 ^= data;
953 v2 ^= 0xff;
954 for (j=0; j < STBDS_SIPHASH_D_ROUNDS; ++j)
955 STBDS_SIPROUND();
956 #ifdef STBDS_SIPHASH_2_4
957 return v0^v1^v2^v3;
958 #else
959 return v1^v2^v3; // slightly stronger since v0^v3 in above cancels out final round operation? I tweeted at the authors of SipHash about this but they didn't reply
960 #endif
961 }
962
stbds_hash_bytes(void * p,size_t len,size_t seed)963 size_t stbds_hash_bytes(void *p, size_t len, size_t seed)
964 {
965 #ifdef STBDS_SIPHASH_2_4
966 return stbds_siphash_bytes(p,len,seed);
967 #else
968 unsigned char *d = (unsigned char *) p;
969
970 if (len == 4) {
971 unsigned int hash = d[0] | (d[1] << 8) | (d[2] << 16) | (d[3] << 24);
972 #if 0
973 // HASH32-A Bob Jenkin's hash function w/o large constants
974 hash ^= seed;
975 hash -= (hash<<6);
976 hash ^= (hash>>17);
977 hash -= (hash<<9);
978 hash ^= seed;
979 hash ^= (hash<<4);
980 hash -= (hash<<3);
981 hash ^= (hash<<10);
982 hash ^= (hash>>15);
983 #elif 1
984 // HASH32-BB Bob Jenkin's presumably-accidental version of Thomas Wang hash with rotates turned into shifts.
985 // Note that converting these back to rotates makes it run a lot slower, presumably due to collisions, so I'm
986 // not really sure what's going on.
987 hash ^= seed;
988 hash = (hash ^ 61) ^ (hash >> 16);
989 hash = hash + (hash << 3);
990 hash = hash ^ (hash >> 4);
991 hash = hash * 0x27d4eb2d;
992 hash ^= seed;
993 hash = hash ^ (hash >> 15);
994 #else // HASH32-C - Murmur3
995 hash ^= seed;
996 hash *= 0xcc9e2d51;
997 hash = (hash << 17) | (hash >> 15);
998 hash *= 0x1b873593;
999 hash ^= seed;
1000 hash = (hash << 19) | (hash >> 13);
1001 hash = hash*5 + 0xe6546b64;
1002 hash ^= hash >> 16;
1003 hash *= 0x85ebca6b;
1004 hash ^= seed;
1005 hash ^= hash >> 13;
1006 hash *= 0xc2b2ae35;
1007 hash ^= hash >> 16;
1008 #endif
1009 // Following statistics were measured on a Core i7-6700 @ 4.00Ghz, compiled with clang 7.0.1 -O2
1010 // Note that the larger tables have high variance as they were run fewer times
1011 // HASH32-A // HASH32-BB // HASH32-C
1012 // 0.10ms // 0.10ms // 0.10ms : 2,000 inserts creating 2K table
1013 // 0.96ms // 0.95ms // 0.99ms : 20,000 inserts creating 20K table
1014 // 14.69ms // 14.43ms // 14.97ms : 200,000 inserts creating 200K table
1015 // 199.99ms // 195.36ms // 202.05ms : 2,000,000 inserts creating 2M table
1016 // 2234.84ms // 2187.74ms // 2240.38ms : 20,000,000 inserts creating 20M table
1017 // 55.68ms // 53.72ms // 57.31ms : 500,000 inserts & deletes in 2K table
1018 // 63.43ms // 61.99ms // 65.73ms : 500,000 inserts & deletes in 20K table
1019 // 80.04ms // 77.96ms // 81.83ms : 500,000 inserts & deletes in 200K table
1020 // 100.42ms // 97.40ms // 102.39ms : 500,000 inserts & deletes in 2M table
1021 // 119.71ms // 120.59ms // 121.63ms : 500,000 inserts & deletes in 20M table
1022 // 185.28ms // 195.15ms // 187.74ms : 500,000 inserts & deletes in 200M table
1023 // 15.58ms // 14.79ms // 15.52ms : 200,000 inserts creating 200K table with varying key spacing
1024
1025 return (((size_t) hash << 16 << 16) | hash) ^ seed;
1026 } else if (len == 8 && sizeof(size_t) == 8) {
1027 size_t hash = d[0] | (d[1] << 8) | (d[2] << 16) | (d[3] << 24);
1028 hash |= (size_t) (d[4] | (d[5] << 8) | (d[6] << 16) | (d[7] << 24)) << 16 << 16; // avoid warning if size_t == 4
1029 hash ^= seed;
1030 hash = (~hash) + (hash << 21);
1031 hash ^= STBDS_ROTATE_RIGHT(hash,24);
1032 hash *= 265;
1033 hash ^= STBDS_ROTATE_RIGHT(hash,14);
1034 hash ^= seed;
1035 hash *= 21;
1036 hash ^= STBDS_ROTATE_RIGHT(hash,28);
1037 hash += (hash << 31);
1038 hash = (~hash) + (hash << 18);
1039 return hash;
1040 } else {
1041 return stbds_siphash_bytes(p,len,seed);
1042 }
1043 #endif
1044 }
1045
stbds_is_key_equal(void * a,size_t elemsize,void * key,size_t keysize,int mode,size_t i)1046 static int stbds_is_key_equal(void *a, size_t elemsize, void *key, size_t keysize, int mode, size_t i)
1047 {
1048 if (mode >= STBDS_HM_STRING)
1049 return 0==strcmp((char *) key, * (char **) ((char *) a + elemsize*i));
1050 else
1051 return 0==memcmp(key, (char *) a + elemsize*i, keysize);
1052 }
1053
1054 #define STBDS_HASH_TO_ARR(x,elemsize) ((char*) (x) - (elemsize))
1055 #define STBDS_ARR_TO_HASH(x,elemsize) ((char*) (x) + (elemsize))
1056 #define STBDS_FREE(x) realloc(x,0)
1057
1058 #define stbds_hash_table(a) ((stbds_hash_index *) stbds_header(a)->hash_table)
1059
stbds_hmfree_func(void * a,size_t elemsize,size_t keyoff)1060 void stbds_hmfree_func(void *a, size_t elemsize, size_t keyoff)
1061 {
1062 if (a == NULL) return;
1063 if (stbds_hash_table(a) != NULL) {
1064 if (stbds_hash_table(a)->string.mode == STBDS_SH_STRDUP) {
1065 size_t i;
1066 // skip 0th element, which is default
1067 for (i=1; i < stbds_header(a)->length; ++i)
1068 STBDS_FREE(*(char**) ((char *) a + elemsize*i));
1069 }
1070 stbds_strreset(&stbds_hash_table(a)->string);
1071 }
1072 STBDS_FREE(stbds_header(a)->hash_table);
1073 STBDS_FREE(stbds_header(a));
1074 }
1075
stbds_hm_find_slot(void * a,size_t elemsize,void * key,size_t keysize,int mode)1076 static ptrdiff_t stbds_hm_find_slot(void *a, size_t elemsize, void *key, size_t keysize, int mode)
1077 {
1078 void *raw_a = STBDS_HASH_TO_ARR(a,elemsize);
1079 stbds_hash_index *table = stbds_hash_table(raw_a);
1080 size_t hash = mode >= STBDS_HM_STRING ? stbds_hash_string((char*)key,table->seed) : stbds_hash_bytes(key, keysize,table->seed);
1081 size_t step = STBDS_BUCKET_LENGTH;
1082 size_t limit,i;
1083 size_t pos;
1084 stbds_hash_bucket *bucket;
1085
1086 if (hash < 2) hash += 2; // stored hash values are forbidden from being 0, so we can detect empty slots
1087
1088 pos = stbds_probe_position(hash, table->slot_count, table->slot_count_log2);
1089
1090 for (;;) {
1091 STBDS_STATS(++stbds_hash_probes);
1092 bucket = &table->storage[pos >> STBDS_BUCKET_SHIFT];
1093
1094 // start searching from pos to end of bucket, this should help performance on small hash tables that fit in cache
1095 for (i=pos & STBDS_BUCKET_MASK; i < STBDS_BUCKET_LENGTH; ++i) {
1096 if (bucket->hash[i] == hash) {
1097 if (stbds_is_key_equal(a, elemsize, key, keysize, mode, bucket->index[i])) {
1098 return (pos & ~STBDS_BUCKET_MASK)+i;
1099 }
1100 } else if (bucket->hash[i] == STBDS_HASH_EMPTY) {
1101 return -1;
1102 }
1103 }
1104
1105 // search from beginning of bucket to pos
1106 limit = pos & STBDS_BUCKET_MASK;
1107 for (i = 0; i < limit; ++i) {
1108 if (bucket->hash[i] == hash) {
1109 if (stbds_is_key_equal(a, elemsize, key, keysize, mode, bucket->index[i])) {
1110 return (pos & ~STBDS_BUCKET_MASK)+i;
1111 }
1112 } else if (bucket->hash[i] == STBDS_HASH_EMPTY) {
1113 return -1;
1114 }
1115 }
1116
1117 // quadratic probing
1118 pos += step;
1119 step += STBDS_BUCKET_LENGTH;
1120 pos &= (table->slot_count-1);
1121 }
1122 /* NOTREACHED */
1123 return -1;
1124 }
1125
stbds_hmget_key(void * a,size_t elemsize,void * key,size_t keysize,int mode)1126 void * stbds_hmget_key(void *a, size_t elemsize, void *key, size_t keysize, int mode)
1127 {
1128 if (a == NULL) {
1129 // make it non-empty so we can return a temp
1130 a = stbds_arrgrowf(0, elemsize, 0, 1);
1131 stbds_header(a)->length += 1;
1132 memset(a, 0, elemsize);
1133 stbds_temp(a) = STBDS_INDEX_EMPTY;
1134 // adjust a to point after the default element
1135 return STBDS_ARR_TO_HASH(a,elemsize);
1136 } else {
1137 stbds_hash_index *table;
1138 void *raw_a = STBDS_HASH_TO_ARR(a,elemsize);
1139 // adjust a to point to the default element
1140 table = (stbds_hash_index *) stbds_header(raw_a)->hash_table;
1141 if (table == 0) {
1142 stbds_temp(raw_a) = -1;
1143 } else {
1144 ptrdiff_t slot = stbds_hm_find_slot(a, elemsize, key, keysize, mode);
1145 if (slot < 0) {
1146 stbds_temp(raw_a) = STBDS_INDEX_EMPTY;
1147 } else {
1148 stbds_hash_bucket *b = &table->storage[slot >> STBDS_BUCKET_SHIFT];
1149 stbds_temp(raw_a) = b->index[slot & STBDS_BUCKET_MASK];
1150 }
1151 }
1152 return a;
1153 }
1154 }
1155
stbds_hmput_default(void * a,size_t elemsize)1156 void * stbds_hmput_default(void *a, size_t elemsize)
1157 {
1158 // three cases:
1159 // a is NULL <- allocate
1160 // a has a hash table but no entries, because of shmode <- grow
1161 // a has entries <- do nothing
1162 if (a == NULL || stbds_header(STBDS_HASH_TO_ARR(a,elemsize))->length == 0) {
1163 a = stbds_arrgrowf(a ? STBDS_HASH_TO_ARR(a,elemsize) : NULL, elemsize, 0, 1);
1164 stbds_header(a)->length += 1;
1165 memset(a, 0, elemsize);
1166 a=STBDS_ARR_TO_HASH(a,elemsize);
1167 }
1168 return a;
1169 }
1170
1171 static char *stbds_strdup(char *str);
1172
stbds_hmput_key(void * a,size_t elemsize,void * key,size_t keysize,int mode)1173 void *stbds_hmput_key(void *a, size_t elemsize, void *key, size_t keysize, int mode)
1174 {
1175 void *raw_a;
1176 stbds_hash_index *table;
1177
1178 if (a == NULL) {
1179 a = stbds_arrgrowf(0, elemsize, 0, 1);
1180 memset(a, 0, elemsize);
1181 stbds_header(a)->length += 1;
1182 // adjust a to point AFTER the default element
1183 a = STBDS_ARR_TO_HASH(a,elemsize);
1184 }
1185
1186 // adjust a to point to the default element
1187 raw_a = a;
1188 a = STBDS_HASH_TO_ARR(a,elemsize);
1189
1190 table = (stbds_hash_index *) stbds_header(a)->hash_table;
1191
1192 if (table == NULL || table->used_count >= table->used_count_threshold) {
1193 stbds_hash_index *nt;
1194 size_t slot_count;
1195
1196 slot_count = (table == NULL) ? STBDS_BUCKET_LENGTH : table->slot_count*2;
1197 nt = stbds_make_hash_index(slot_count, table);
1198 if (table) {
1199 STBDS_FREE(table);
1200 }
1201 stbds_header(a)->hash_table = table = nt;
1202 STBDS_STATS(++stbds_hash_grow);
1203 }
1204
1205 // we iterate hash table explicitly because we want to track if we saw a tombstone
1206 {
1207 size_t hash = mode >= STBDS_HM_STRING ? stbds_hash_string((char*)key,table->seed) : stbds_hash_bytes(key, keysize,table->seed);
1208 size_t step = STBDS_BUCKET_LENGTH;
1209 size_t limit,i;
1210 size_t pos;
1211 ptrdiff_t tombstone = -1;
1212 stbds_hash_bucket *bucket;
1213
1214 // stored hash values are forbidden from being 0, so we can detect empty slots to early out quickly
1215 if (hash < 2) hash += 2;
1216
1217 pos = stbds_probe_position(hash, table->slot_count, table->slot_count_log2);
1218
1219 for (;;) {
1220 STBDS_STATS(++stbds_hash_probes);
1221 bucket = &table->storage[pos >> STBDS_BUCKET_SHIFT];
1222
1223 // start searching from pos to end of bucket
1224 for (i=pos & STBDS_BUCKET_MASK; i < STBDS_BUCKET_LENGTH; ++i) {
1225 if (bucket->hash[i] == hash) {
1226 if (stbds_is_key_equal(raw_a, elemsize, key, keysize, mode, bucket->index[i])) {
1227 stbds_temp(a) = bucket->index[i];
1228 return STBDS_ARR_TO_HASH(a,elemsize);
1229 }
1230 } else if (bucket->hash[i] == 0) {
1231 pos = (pos & ~STBDS_BUCKET_MASK) + i;
1232 goto found_empty_slot;
1233 } else if (tombstone < 0) {
1234 if (bucket->index[i] == STBDS_INDEX_DELETED)
1235 tombstone = (ptrdiff_t) ((pos & ~STBDS_BUCKET_MASK) + i);
1236 }
1237 }
1238
1239 // search from beginning of bucket to pos
1240 limit = pos & STBDS_BUCKET_MASK;
1241 for (i = 0; i < limit; ++i) {
1242 if (bucket->hash[i] == hash) {
1243 if (stbds_is_key_equal(raw_a, elemsize, key, keysize, mode, bucket->index[i])) {
1244 stbds_temp(a) = bucket->index[i];
1245 return STBDS_ARR_TO_HASH(a,elemsize);
1246 }
1247 } else if (bucket->hash[i] == 0) {
1248 pos = (pos & ~STBDS_BUCKET_MASK) + i;
1249 goto found_empty_slot;
1250 } else if (tombstone < 0) {
1251 if (bucket->index[i] == STBDS_INDEX_DELETED)
1252 tombstone = (ptrdiff_t) ((pos & ~STBDS_BUCKET_MASK) + i);
1253 }
1254 }
1255
1256 // quadratic probing
1257 pos += step;
1258 step += STBDS_BUCKET_LENGTH;
1259 pos &= (table->slot_count-1);
1260 }
1261 found_empty_slot:
1262 if (tombstone >= 0) {
1263 pos = tombstone;
1264 --table->tombstone_count;
1265 }
1266 ++table->used_count;
1267
1268 {
1269 ptrdiff_t i = (ptrdiff_t) stbds_arrlen(a);
1270 // we want to do stbds_arraddn(1), but we can't use the macros since we don't have something of the right type
1271 if ((size_t) i+1 > stbds_arrcap(a))
1272 *(void **) &a = stbds_arrgrowf(a, elemsize, 1, 0);
1273 raw_a = STBDS_ARR_TO_HASH(a,elemsize);
1274
1275 STBDS_ASSERT((size_t) i+1 <= stbds_arrcap(a));
1276 stbds_header(a)->length = i+1;
1277 bucket = &table->storage[pos >> STBDS_BUCKET_SHIFT];
1278 bucket->hash[pos & STBDS_BUCKET_MASK] = hash;
1279 bucket->index[pos & STBDS_BUCKET_MASK] = i-1;
1280 stbds_temp(a) = i-1;
1281
1282 switch (table->string.mode) {
1283 case STBDS_SH_STRDUP: *(char **) ((char *) a + elemsize*i) = stbds_strdup((char*) key); break;
1284 case STBDS_SH_ARENA: *(char **) ((char *) a + elemsize*i) = stbds_stralloc(&table->string, (char*)key); break;
1285 default: *(char **) ((char *) a + elemsize*i) = (char *) key; break;
1286 }
1287 }
1288 return STBDS_ARR_TO_HASH(a,elemsize);
1289 }
1290 }
1291
stbds_shmode_func(size_t elemsize,int mode)1292 void * stbds_shmode_func(size_t elemsize, int mode)
1293 {
1294 void *a = stbds_arrgrowf(0, elemsize, 0, 1);
1295 stbds_hash_index *h;
1296 memset(a, 0, elemsize);
1297 stbds_header(a)->length = 1;
1298 stbds_header(a)->hash_table = h = (stbds_hash_index *) stbds_make_hash_index(STBDS_BUCKET_LENGTH, NULL);
1299 h->string.mode = mode;
1300 return STBDS_ARR_TO_HASH(a,elemsize);
1301 }
1302
stbds_hmdel_key(void * a,size_t elemsize,void * key,size_t keysize,size_t keyoffset,int mode)1303 void * stbds_hmdel_key(void *a, size_t elemsize, void *key, size_t keysize, size_t keyoffset, int mode)
1304 {
1305 if (a == NULL) {
1306 return 0;
1307 } else {
1308 stbds_hash_index *table;
1309 void *raw_a = STBDS_HASH_TO_ARR(a,elemsize);
1310 table = (stbds_hash_index *) stbds_header(raw_a)->hash_table;
1311 stbds_temp(raw_a) = 0;
1312 if (table == 0) {
1313 return a;
1314 } else {
1315 ptrdiff_t slot;
1316 slot = stbds_hm_find_slot(a, elemsize, key, keysize, mode);
1317 if (slot < 0)
1318 return a;
1319 else {
1320 stbds_hash_bucket *b = &table->storage[slot >> STBDS_BUCKET_SHIFT];
1321 int i = slot & STBDS_BUCKET_MASK;
1322 ptrdiff_t old_index = b->index[i];
1323 ptrdiff_t final_index = (ptrdiff_t) stbds_arrlen(raw_a)-1-1; // minus one for the raw_a vs a, and minus one for 'last'
1324 STBDS_ASSERT(slot < (ptrdiff_t) table->slot_count);
1325 --table->used_count;
1326 ++table->tombstone_count;
1327 stbds_temp(raw_a) = 1;
1328 STBDS_ASSERT(table->used_count >= 0);
1329 //STBDS_ASSERT(table->tombstone_count < table->slot_count/4);
1330 b->hash[i] = STBDS_HASH_DELETED;
1331 b->index[i] = STBDS_INDEX_DELETED;
1332
1333 if (mode == STBDS_HM_STRING && table->string.mode == STBDS_SH_STRDUP)
1334 STBDS_FREE(*(char**) ((char *) a+elemsize*old_index));
1335
1336 // if indices are the same, memcpy is a no-op, but back-pointer-fixup will fail, so skip
1337 if (old_index != final_index) {
1338 // swap delete
1339 memmove((char*) a + elemsize*old_index, (char*) a + elemsize*final_index, elemsize);
1340
1341 // now find the slot for the last element
1342 if (mode == STBDS_HM_STRING)
1343 slot = stbds_hm_find_slot(a, elemsize, *(char**) ((char *) a+elemsize*old_index + keyoffset), keysize, mode);
1344 else
1345 slot = stbds_hm_find_slot(a, elemsize, (char* ) a+elemsize*old_index + keyoffset, keysize, mode);
1346 STBDS_ASSERT(slot >= 0);
1347 b = &table->storage[slot >> STBDS_BUCKET_SHIFT];
1348 i = slot & STBDS_BUCKET_MASK;
1349 STBDS_ASSERT(b->index[i] == final_index);
1350 b->index[i] = old_index;
1351 }
1352 stbds_header(raw_a)->length -= 1;
1353
1354 if (table->used_count < table->used_count_shrink_threshold && table->slot_count > STBDS_BUCKET_LENGTH) {
1355 stbds_header(raw_a)->hash_table = stbds_make_hash_index(table->slot_count>>1, table);
1356 STBDS_FREE(table);
1357 STBDS_STATS(++stbds_hash_shrink);
1358 } else if (table->tombstone_count > table->tombstone_count_threshold) {
1359 stbds_header(raw_a)->hash_table = stbds_make_hash_index(table->slot_count , table);
1360 STBDS_FREE(table);
1361 STBDS_STATS(++stbds_hash_rebuild);
1362 }
1363
1364 return a;
1365 }
1366 }
1367 }
1368 /* NOTREACHED */
1369 return 0;
1370 }
1371
stbds_strdup(char * str)1372 static char *stbds_strdup(char *str)
1373 {
1374 // to keep replaceable allocator simple, we don't want to use strdup.
1375 // rolling our own also avoids problem of strdup vs _strdup
1376 size_t len = strlen(str)+1;
1377 char *p = (char*) realloc(0, len);
1378 memmove(p, str, len);
1379 return p;
1380 }
1381
1382 #ifndef STBDS_STRING_ARENA_BLOCKSIZE_MIN
1383 #define STBDS_STRING_ARENA_BLOCKSIZE_MIN 512
1384 #endif
1385 #ifndef STBDS_STRING_ARENA_BLOCKSIZE_MAX
1386 #define STBDS_STRING_ARENA_BLOCKSIZE_MAX 1<<20
1387 #endif
1388
stbds_stralloc(stbds_string_arena * a,char * str)1389 char *stbds_stralloc(stbds_string_arena *a, char *str)
1390 {
1391 char *p;
1392 size_t len = strlen(str)+1;
1393 if (len > a->remaining) {
1394 // compute the next blocksize
1395 size_t blocksize = a->block;
1396
1397 // size is 512, 512, 1024, 1024, 2048, 2048, 4096, 4096, etc., so that
1398 // there are log(SIZE) allocations to free when we destroy the table
1399 blocksize = (size_t) (STBDS_STRING_ARENA_BLOCKSIZE_MIN) << (blocksize>>1);
1400
1401 // if size is under 1M, advance to next blocktype
1402 if (blocksize < (size_t)(STBDS_STRING_ARENA_BLOCKSIZE_MAX))
1403 ++a->block;
1404
1405 if (len > blocksize) {
1406 // if string is larger than blocksize, then just allocate the full size.
1407 // note that we still advance string_block so block size will continue
1408 // increasing, so e.g. if somebody only calls this with 1000-long strings,
1409 // eventually the arena will start doubling and handling those as well
1410 stbds_string_block *sb = (stbds_string_block *) realloc(0, sizeof(*sb)-8 + len);
1411 memmove(sb->storage, str, len);
1412 if (a->storage) {
1413 // insert it after the first element, so that we don't waste the space there
1414 sb->next = a->storage->next;
1415 a->storage->next = sb;
1416 } else {
1417 sb->next = 0;
1418 a->storage = sb;
1419 a->remaining = 0; // this is redundant, but good for clarity
1420 }
1421 return sb->storage;
1422 } else {
1423 stbds_string_block *sb = (stbds_string_block *) realloc(0, sizeof(*sb)-8 + blocksize);
1424 sb->next = a->storage;
1425 a->storage = sb;
1426 a->remaining = blocksize;
1427 }
1428 }
1429
1430 STBDS_ASSERT(len <= a->remaining);
1431 p = a->storage->storage + a->remaining - len;
1432 a->remaining -= len;
1433 memmove(p, str, len);
1434 return p;
1435 }
1436
stbds_strreset(stbds_string_arena * a)1437 void stbds_strreset(stbds_string_arena *a)
1438 {
1439 stbds_string_block *x,*y;
1440 x = a->storage;
1441 while (x) {
1442 y = x->next;
1443 realloc(x,0);
1444 x = y;
1445 }
1446 memset(a, 0, sizeof(*a));
1447 }
1448
1449 #endif
1450
1451 //////////////////////////////////////////////////////////////////////////////
1452 //
1453 // UNIT TESTS
1454 //
1455
1456 #ifdef STBDS_UNIT_TESTS
1457 #include <stdio.h>
1458 #ifdef STBDS_ASSERT_WAS_UNDEFINED
1459 #undef STBDS_ASSERT
1460 #endif
1461 #ifndef STBDS_ASSERT
1462 #define STBDS_ASSERT assert
1463 #include <assert.h>
1464 #endif
1465
1466 typedef struct { int key,b,c,d; } stbds_struct;
1467
1468 static char buffer[256];
strkey(int n)1469 char *strkey(int n)
1470 {
1471 #if defined(_WIN32) && defined(__STDC_WANT_SECURE_LIB__)
1472 sprintf_s(buffer, sizeof(buffer), "test_%d", n);
1473 #else
1474 sprintf(buffer, "test_%d", n);
1475 #endif
1476 return buffer;
1477 }
1478
stbds_unit_tests(void)1479 void stbds_unit_tests(void)
1480 {
1481 #if defined(_MSC_VER) && _MSC_VER <= 1200 && defined(__cplusplus)
1482 // VC6 C++ doesn't like the template<> trick on unnamed structures, so do nothing!
1483 STBDS_ASSERT(0);
1484 #else
1485 const int testsize = 100000;
1486 int *arr=NULL;
1487 struct { int key; int value; } *intmap = NULL;
1488 struct { char *key; int value; } *strmap = NULL;
1489 struct { stbds_struct key; int value; } *map = NULL;
1490 stbds_struct *map2 = NULL;
1491 stbds_string_arena sa = { 0 };
1492
1493 int i,j;
1494
1495 for (i=0; i < 20000; i += 50) {
1496 for (j=0; j < i; ++j)
1497 arrpush(arr,j);
1498 arrfree(arr);
1499 }
1500
1501 for (i=0; i < 4; ++i) {
1502 arrpush(arr,1); arrpush(arr,2); arrpush(arr,3); arrpush(arr,4);
1503 arrdel(arr,i);
1504 arrfree(arr);
1505 arrpush(arr,1); arrpush(arr,2); arrpush(arr,3); arrpush(arr,4);
1506 arrdelswap(arr,i);
1507 arrfree(arr);
1508 }
1509
1510 for (i=0; i < 5; ++i) {
1511 arrpush(arr,1); arrpush(arr,2); arrpush(arr,3); arrpush(arr,4);
1512 stbds_arrins(arr,i,5);
1513 STBDS_ASSERT(arr[i] == 5);
1514 if (i < 4)
1515 STBDS_ASSERT(arr[4] == 4);
1516 arrfree(arr);
1517 }
1518
1519 hmdefault(intmap, -1);
1520 i=1; STBDS_ASSERT(hmget(intmap, i) == -1);
1521 for (i=0; i < testsize; i+=2)
1522 hmput(intmap, i, i*5);
1523 for (i=0; i < testsize; i+=1)
1524 if (i & 1) STBDS_ASSERT(hmget(intmap, i) == -1 );
1525 else STBDS_ASSERT(hmget(intmap, i) == i*5);
1526 for (i=0; i < testsize; i+=2)
1527 hmput(intmap, i, i*3);
1528 for (i=0; i < testsize; i+=1)
1529 if (i & 1) STBDS_ASSERT(hmget(intmap, i) == -1 );
1530 else STBDS_ASSERT(hmget(intmap, i) == i*3);
1531 for (i=2; i < testsize; i+=4)
1532 hmdel(intmap, i); // delete half the entries
1533 for (i=0; i < testsize; i+=1)
1534 if (i & 3) STBDS_ASSERT(hmget(intmap, i) == -1 );
1535 else STBDS_ASSERT(hmget(intmap, i) == i*3);
1536 for (i=0; i < testsize; i+=1)
1537 hmdel(intmap, i); // delete the rest of the entries
1538 for (i=0; i < testsize; i+=1)
1539 STBDS_ASSERT(hmget(intmap, i) == -1 );
1540 hmfree(intmap);
1541 for (i=0; i < testsize; i+=2)
1542 hmput(intmap, i, i*3);
1543 hmfree(intmap);
1544
1545 #if defined(__clang__) || defined(__GNUC__)
1546 #ifndef __cplusplus
1547 intmap = NULL;
1548 hmput(intmap, 15, 7);
1549 hmput(intmap, 11, 3);
1550 hmput(intmap, 9, 5);
1551 STBDS_ASSERT(hmget(intmap, 9) == 5);
1552 STBDS_ASSERT(hmget(intmap, 11) == 3);
1553 STBDS_ASSERT(hmget(intmap, 15) == 7);
1554 #endif
1555 #endif
1556
1557 for (i=0; i < testsize; ++i)
1558 stralloc(&sa, strkey(i));
1559 strreset(&sa);
1560
1561 for (j=0; j < 2; ++j) {
1562 if (j == 0)
1563 sh_new_strdup(strmap);
1564 else
1565 sh_new_arena(strmap);
1566 shdefault(strmap, -1);
1567 for (i=0; i < testsize; i+=2)
1568 shput(strmap, strkey(i), i*3);
1569 for (i=0; i < testsize; i+=1)
1570 if (i & 1) STBDS_ASSERT(shget(strmap, strkey(i)) == -1 );
1571 else STBDS_ASSERT(shget(strmap, strkey(i)) == i*3);
1572 for (i=2; i < testsize; i+=4)
1573 shdel(strmap, strkey(i)); // delete half the entries
1574 for (i=0; i < testsize; i+=1)
1575 if (i & 3) STBDS_ASSERT(shget(strmap, strkey(i)) == -1 );
1576 else STBDS_ASSERT(shget(strmap, strkey(i)) == i*3);
1577 for (i=0; i < testsize; i+=1)
1578 shdel(strmap, strkey(i)); // delete the rest of the entries
1579 for (i=0; i < testsize; i+=1)
1580 STBDS_ASSERT(shget(strmap, strkey(i)) == -1 );
1581 shfree(strmap);
1582 }
1583
1584 {
1585 struct { char *key; char value; } *hash = NULL;
1586 char name[4] = "jen";
1587 shput(hash, "bob" , 'h');
1588 shput(hash, "sally" , 'e');
1589 shput(hash, "fred" , 'l');
1590 shput(hash, "jen" , 'x');
1591 shput(hash, "doug" , 'o');
1592
1593 shput(hash, name , 'l');
1594 shfree(hash);
1595 }
1596
1597 for (i=0; i < testsize; i += 2) {
1598 stbds_struct s = { i,i*2,i*3,i*4 };
1599 hmput(map, s, i*5);
1600 }
1601
1602 for (i=0; i < testsize; i += 1) {
1603 stbds_struct s = { i,i*2,i*3 ,i*4 };
1604 stbds_struct t = { i,i*2,i*3+1,i*4 };
1605 if (i & 1) STBDS_ASSERT(hmget(map, s) == 0);
1606 else STBDS_ASSERT(hmget(map, s) == i*5);
1607 STBDS_ASSERT(hmget(map, t) == 0);
1608 }
1609
1610 for (i=0; i < testsize; i += 2) {
1611 stbds_struct s = { i,i*2,i*3,i*4 };
1612 hmputs(map2, s);
1613 }
1614 hmfree(map);
1615
1616 for (i=0; i < testsize; i += 1) {
1617 stbds_struct s = { i,i*2,i*3,i*4 };
1618 stbds_struct t = { i,i*2,i*3+1,i*4 };
1619 if (i & 1) STBDS_ASSERT(hmgets(map2, s.key).d == 0);
1620 else STBDS_ASSERT(hmgets(map2, s.key).d == i*4);
1621 STBDS_ASSERT(hmget(map, t) == 0);
1622 }
1623 hmfree(map2);
1624 #endif
1625 }
1626 #endif
1627
1628
1629 /*
1630 ------------------------------------------------------------------------------
1631 This software is available under 2 licenses -- choose whichever you prefer.
1632 ------------------------------------------------------------------------------
1633 ALTERNATIVE A - MIT License
1634 Copyright (c) 2019 Sean Barrett
1635 Permission is hereby granted, free of charge, to any person obtaining a copy of
1636 this software and associated documentation files (the "Software"), to deal in
1637 the Software without restriction, including without limitation the rights to
1638 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
1639 of the Software, and to permit persons to whom the Software is furnished to do
1640 so, subject to the following conditions:
1641 The above copyright notice and this permission notice shall be included in all
1642 copies or substantial portions of the Software.
1643 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1644 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1645 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1646 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
1647 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
1648 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
1649 SOFTWARE.
1650 ------------------------------------------------------------------------------
1651 ALTERNATIVE B - Public Domain (www.unlicense.org)
1652 This is free and unencumbered software released into the public domain.
1653 Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
1654 software, either in source code form or as a compiled binary, for any purpose,
1655 commercial or non-commercial, and by any means.
1656 In jurisdictions that recognize copyright laws, the author or authors of this
1657 software dedicate any and all copyright interest in the software to the public
1658 domain. We make this dedication for the benefit of the public at large and to
1659 the detriment of our heirs and successors. We intend this dedication to be an
1660 overt act of relinquishment in perpetuity of all present and future rights to
1661 this software under copyright law.
1662 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1663 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1664 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1665 AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
1666 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
1667 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1668 ------------------------------------------------------------------------------
1669 */
1670