Mercurial

comparison dowa/stb_ds.h @ 71:75de5903355c

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