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