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