1 /* stb_lib.h - v1.00 - http://nothings.org/stb
2 no warranty is offered or implied; use this code at your own risk
3
4 ============================================================================
5 You MUST
6
7 #define STB_LIB_IMPLEMENTATION
8
9 in EXACTLY _one_ C or C++ file that includes this header, BEFORE the
10 include, like this:
11
12 #define STB_LIB_IMPLEMENTATION
13 #include "stblib_files.h"
14
15 All other files should just #include "stblib_files.h" without the #define.
16 ============================================================================
17
18 LICENSE
19
20 See end of file for license information.
21
22 CREDITS
23
24 Written by Sean Barrett.
25
26 Fixes:
27 Philipp Wiesemann Robert Nix
28 r-lyeh blackpawn
29 github:Mojofreem Ryan Whitworth
30 Vincent Isambart Mike Sartain
31 Eugene Opalev Tim Sjostrand
32 github:infatum Dave Butler
33 */
34
35 #ifndef STB_INCLUDE_STB_LIB_H
36
37 #include <stdarg.h>
38
39 #if defined(_WIN32) && !defined(__MINGW32__)
40 #ifndef _CRT_SECURE_NO_WARNINGS
41 #define _CRT_SECURE_NO_WARNINGS
42 #endif
43 #ifndef _CRT_NONSTDC_NO_DEPRECATE
44 #define _CRT_NONSTDC_NO_DEPRECATE
45 #endif
46 #ifndef _CRT_NON_CONFORMING_SWPRINTFS
47 #define _CRT_NON_CONFORMING_SWPRINTFS
48 #endif
49 #if !defined(_MSC_VER) || _MSC_VER > 1700
50 #include <intrin.h> // _BitScanReverse
51 #endif
52 #endif
53
54 #include <stdlib.h> // stdlib could have min/max
55 #include <stdio.h> // need FILE
56 #include <string.h> // stb_define_hash needs memcpy/memset
57 #include <time.h> // stb_dirtree
58
59 typedef unsigned char stb_uchar;
60 typedef unsigned char stb_uint8;
61 typedef unsigned int stb_uint;
62 typedef unsigned short stb_uint16;
63 typedef short stb_int16;
64 typedef signed char stb_int8;
65 #if defined(STB_USE_LONG_FOR_32_BIT_INT) || defined(STB_LONG32)
66 typedef unsigned long stb_uint32;
67 typedef long stb_int32;
68 #else
69 typedef unsigned int stb_uint32;
70 typedef int stb_int32;
71 #endif
72 typedef char stb__testsize2_16[sizeof(stb_uint16)==2 ? 1 : -1];
73 typedef char stb__testsize2_32[sizeof(stb_uint32)==4 ? 1 : -1];
74
75 #ifdef _MSC_VER
76 typedef unsigned __int64 stb_uint64;
77 typedef __int64 stb_int64;
78 #define STB_IMM_UINT64(literalui64) (literalui64##ui64)
79 #else
80 // ??
81 typedef unsigned long long stb_uint64;
82 typedef long long stb_int64;
83 #define STB_IMM_UINT64(literalui64) (literalui64##ULL)
84 #endif
85 typedef char stb__testsize2_64[sizeof(stb_uint64)==8 ? 1 : -1];
86
87 #ifdef __cplusplus
88 #define STB_EXTERN extern "C"
89 #else
90 #define STB_EXTERN extern
91 #endif
92
93 // check for well-known debug defines
94 #if defined(DEBUG) || defined(_DEBUG) || defined(DBG)
95 #ifndef NDEBUG
96 #define STB_DEBUG
97 #endif
98 #endif
99
100 #ifdef STB_DEBUG
101 #include <assert.h>
102 #endif
103 #endif // STB_INCLUDE_STB_LIB_H
104
105 #ifdef STB_LIB_IMPLEMENTATION
106 #include <assert.h>
107 #include <stdarg.h>
108 #include <stddef.h>
109 #include <ctype.h>
110 #include <math.h>
111 #ifndef _WIN32
112 #include <unistd.h>
113 #else
114 #include <io.h> // _mktemp
115 #include <direct.h> // _rmdir
116 #endif
117 #include <sys/types.h> // stat()/_stat()
118 #include <sys/stat.h> // stat()/_stat()
119 #endif
120
121 //////////////////////////////////////////////////////////////////////////////
122 //
123 // Miscellany
124 //
125
126 #ifdef _WIN32
127 #define stb_stricmp(a,b) stricmp(a,b)
128 #define stb_strnicmp(a,b,n) strnicmp(a,b,n)
129 #else
130 #define stb_stricmp(a,b) strcasecmp(a,b)
131 #define stb_strnicmp(a,b,n) strncasecmp(a,b,n)
132 #endif
133
134 #ifndef STB_INCLUDE_STB_LIB_H
135 STB_EXTERN void stb_fatal(char *fmt, ...);
136 STB_EXTERN void stb_swap(void *p, void *q, size_t sz);
137 STB_EXTERN double stb_linear_remap(double x, double x_min, double x_max,
138 double out_min, double out_max);
139
140 #define stb_arrcount(x) (sizeof(x)/sizeof((x)[0]))
141 #define stb_lerp(t,a,b) ( (a) + (t) * (float) ((b)-(a)) )
142 #define stb_unlerp(t,a,b) ( ((t) - (a)) / (float) ((b) - (a)) )
143
144 #endif
145
146
147 #ifdef STB_LIB_IMPLEMENTATION
stb_fatal(char * s,...)148 void stb_fatal(char *s, ...)
149 {
150 va_list a;
151 va_start(a,s);
152 fputs("Fatal error: ", stderr);
153 vfprintf(stderr, s, a);
154 va_end(a);
155 fputs("\n", stderr);
156 #ifdef STB_DEBUG
157 #ifdef _MSC_VER
158 #ifndef _WIN64
159 __asm int 3; // trap to debugger!
160 #else
161 __debugbreak();
162 #endif
163 #else
164 __builtin_trap();
165 #endif
166 #endif
167 exit(1);
168 }
169
170 typedef struct { char d[4]; } stb__4;
171 typedef struct { char d[8]; } stb__8;
172
173 // optimize the small cases, though you shouldn't be calling this for those!
stb_swap(void * p,void * q,size_t sz)174 void stb_swap(void *p, void *q, size_t sz)
175 {
176 char buffer[256];
177 if (p == q) return;
178 if (sz == 4) {
179 stb__4 temp = * ( stb__4 *) p;
180 * (stb__4 *) p = * ( stb__4 *) q;
181 * (stb__4 *) q = temp;
182 return;
183 } else if (sz == 8) {
184 stb__8 temp = * ( stb__8 *) p;
185 * (stb__8 *) p = * ( stb__8 *) q;
186 * (stb__8 *) q = temp;
187 return;
188 }
189
190 while (sz > sizeof(buffer)) {
191 stb_swap(p, q, sizeof(buffer));
192 p = (char *) p + sizeof(buffer);
193 q = (char *) q + sizeof(buffer);
194 sz -= sizeof(buffer);
195 }
196
197 memcpy(buffer, p , sz);
198 memcpy(p , q , sz);
199 memcpy(q , buffer, sz);
200 }
201
202 #ifdef stb_linear_remap
203 #undef stb_linear_remap
204 #endif
205
stb_linear_remap(double x,double x_min,double x_max,double out_min,double out_max)206 double stb_linear_remap(double x, double x_min, double x_max,
207 double out_min, double out_max)
208 {
209 return stb_lerp(stb_unlerp(x,x_min,x_max),out_min,out_max);
210 }
211
212 #define stb_linear_remap(t,a,b,c,d) stb_lerp(stb_unlerp(t,a,b),c,d)
213 #endif // STB_LIB_IMPLEMENTATION
214
215 #ifndef STB_INCLUDE_STB_LIB_H
216 // avoid unnecessary function call, but define function so its address can be taken
217 #ifndef stb_linear_remap
218 #define stb_linear_remap(t,a,b,c,d) stb_lerp(stb_unlerp(t,a,b),c,d)
219 #endif
220 #endif
221
222 //////////////////////////////////////////////////////////////////////////////
223 //
224 // cross-platform snprintf because they keep changing that,
225 // and with old compilers without vararg macros we can't write
226 // a macro wrapper to fix it up
227
228 #ifndef STB_INCLUDE_STB_LIB_H
229 STB_EXTERN int stb_snprintf(char *s, size_t n, const char *fmt, ...);
230 STB_EXTERN int stb_vsnprintf(char *s, size_t n, const char *fmt, va_list v);
231 STB_EXTERN char *stb_sprintf(const char *fmt, ...);
232 #endif
233
234 #ifdef STB_LIB_IMPLEMENTATION
235
stb_vsnprintf(char * s,size_t n,const char * fmt,va_list v)236 int stb_vsnprintf(char *s, size_t n, const char *fmt, va_list v)
237 {
238 int res;
239 #ifdef _WIN32
240 // Could use "_vsnprintf_s(s, n, _TRUNCATE, fmt, v)" ?
241 res = _vsnprintf(s,n,fmt,v);
242 #else
243 res = vsnprintf(s,n,fmt,v);
244 #endif
245 if (n) s[n-1] = 0;
246 // Unix returns length output would require, Windows returns negative when truncated.
247 return (res >= (int) n || res < 0) ? -1 : res;
248 }
249
stb_snprintf(char * s,size_t n,const char * fmt,...)250 int stb_snprintf(char *s, size_t n, const char *fmt, ...)
251 {
252 int res;
253 va_list v;
254 va_start(v,fmt);
255 res = stb_vsnprintf(s, n, fmt, v);
256 va_end(v);
257 return res;
258 }
259
stb_sprintf(const char * fmt,...)260 char *stb_sprintf(const char *fmt, ...)
261 {
262 static char buffer[1024];
263 va_list v;
264 va_start(v,fmt);
265 stb_vsnprintf(buffer,1024,fmt,v);
266 va_end(v);
267 return buffer;
268 }
269 #endif
270
271 //////////////////////////////////////////////////////////////////////////////
272 //
273 // Windows UTF8 filename handling
274 //
275 // Windows stupidly treats 8-bit filenames as some dopey code page,
276 // rather than utf-8. If we want to use utf8 filenames, we have to
277 // convert them to WCHAR explicitly and call WCHAR versions of the
278 // file functions. So, ok, we do.
279
280
281 #ifndef STB_INCLUDE_STB_LIB_H
282 #ifdef _WIN32
283 #define stb__fopen(x,y) _wfopen((const wchar_t *)stb__from_utf8(x), (const wchar_t *)stb__from_utf8_alt(y))
284 #define stb__windows(x,y) x
285 #else
286 #define stb__fopen(x,y) fopen(x,y)
287 #define stb__windows(x,y) y
288 #endif
289
290
291 typedef unsigned short stb__wchar;
292
293 STB_EXTERN stb__wchar * stb_from_utf8(stb__wchar *buffer, char *str, int n);
294 STB_EXTERN char * stb_to_utf8 (char *buffer, stb__wchar *str, int n);
295
296 STB_EXTERN stb__wchar *stb__from_utf8(char *str);
297 STB_EXTERN stb__wchar *stb__from_utf8_alt(char *str);
298 STB_EXTERN char *stb__to_utf8(stb__wchar *str);
299 #endif
300
301 #ifdef STB_LIB_IMPLEMENTATION
stb_from_utf8(stb__wchar * buffer,char * ostr,int n)302 stb__wchar * stb_from_utf8(stb__wchar *buffer, char *ostr, int n)
303 {
304 unsigned char *str = (unsigned char *) ostr;
305 stb_uint32 c;
306 int i=0;
307 --n;
308 while (*str) {
309 if (i >= n)
310 return NULL;
311 if (!(*str & 0x80))
312 buffer[i++] = *str++;
313 else if ((*str & 0xe0) == 0xc0) {
314 if (*str < 0xc2) return NULL;
315 c = (*str++ & 0x1f) << 6;
316 if ((*str & 0xc0) != 0x80) return NULL;
317 buffer[i++] = c + (*str++ & 0x3f);
318 } else if ((*str & 0xf0) == 0xe0) {
319 if (*str == 0xe0 && (str[1] < 0xa0 || str[1] > 0xbf)) return NULL;
320 if (*str == 0xed && str[1] > 0x9f) return NULL; // str[1] < 0x80 is checked below
321 c = (*str++ & 0x0f) << 12;
322 if ((*str & 0xc0) != 0x80) return NULL;
323 c += (*str++ & 0x3f) << 6;
324 if ((*str & 0xc0) != 0x80) return NULL;
325 buffer[i++] = c + (*str++ & 0x3f);
326 } else if ((*str & 0xf8) == 0xf0) {
327 if (*str > 0xf4) return NULL;
328 if (*str == 0xf0 && (str[1] < 0x90 || str[1] > 0xbf)) return NULL;
329 if (*str == 0xf4 && str[1] > 0x8f) return NULL; // str[1] < 0x80 is checked below
330 c = (*str++ & 0x07) << 18;
331 if ((*str & 0xc0) != 0x80) return NULL;
332 c += (*str++ & 0x3f) << 12;
333 if ((*str & 0xc0) != 0x80) return NULL;
334 c += (*str++ & 0x3f) << 6;
335 if ((*str & 0xc0) != 0x80) return NULL;
336 c += (*str++ & 0x3f);
337 // utf-8 encodings of values used in surrogate pairs are invalid
338 if ((c & 0xFFFFF800) == 0xD800) return NULL;
339 if (c >= 0x10000) {
340 c -= 0x10000;
341 if (i + 2 > n) return NULL;
342 buffer[i++] = 0xD800 | (0x3ff & (c >> 10));
343 buffer[i++] = 0xDC00 | (0x3ff & (c ));
344 }
345 } else
346 return NULL;
347 }
348 buffer[i] = 0;
349 return buffer;
350 }
351
stb_to_utf8(char * buffer,stb__wchar * str,int n)352 char * stb_to_utf8(char *buffer, stb__wchar *str, int n)
353 {
354 int i=0;
355 --n;
356 while (*str) {
357 if (*str < 0x80) {
358 if (i+1 > n) return NULL;
359 buffer[i++] = (char) *str++;
360 } else if (*str < 0x800) {
361 if (i+2 > n) return NULL;
362 buffer[i++] = 0xc0 + (*str >> 6);
363 buffer[i++] = 0x80 + (*str & 0x3f);
364 str += 1;
365 } else if (*str >= 0xd800 && *str < 0xdc00) {
366 stb_uint32 c;
367 if (i+4 > n) return NULL;
368 c = ((str[0] - 0xd800) << 10) + ((str[1]) - 0xdc00) + 0x10000;
369 buffer[i++] = 0xf0 + (c >> 18);
370 buffer[i++] = 0x80 + ((c >> 12) & 0x3f);
371 buffer[i++] = 0x80 + ((c >> 6) & 0x3f);
372 buffer[i++] = 0x80 + ((c ) & 0x3f);
373 str += 2;
374 } else if (*str >= 0xdc00 && *str < 0xe000) {
375 return NULL;
376 } else {
377 if (i+3 > n) return NULL;
378 buffer[i++] = 0xe0 + (*str >> 12);
379 buffer[i++] = 0x80 + ((*str >> 6) & 0x3f);
380 buffer[i++] = 0x80 + ((*str ) & 0x3f);
381 str += 1;
382 }
383 }
384 buffer[i] = 0;
385 return buffer;
386 }
387
stb__from_utf8(char * str)388 stb__wchar *stb__from_utf8(char *str)
389 {
390 static stb__wchar buffer[4096];
391 return stb_from_utf8(buffer, str, 4096);
392 }
393
stb__from_utf8_alt(char * str)394 stb__wchar *stb__from_utf8_alt(char *str)
395 {
396 static stb__wchar buffer[4096];
397 return stb_from_utf8(buffer, str, 4096);
398 }
399
stb__to_utf8(stb__wchar * str)400 char *stb__to_utf8(stb__wchar *str)
401 {
402 static char buffer[4096];
403 return stb_to_utf8(buffer, str, 4096);
404 }
405 #endif
406
407 //////////////////////////////////////////////////////////////////////////////
408 //
409 // qsort Compare Routines
410 // NOT THREAD SAFE
411
412 #ifndef STB_INCLUDE_STB_LIB_H
413 STB_EXTERN int (*stb_intcmp(int offset))(const void *a, const void *b);
414 STB_EXTERN int (*stb_qsort_strcmp(int offset))(const void *a, const void *b);
415 STB_EXTERN int (*stb_qsort_stricmp(int offset))(const void *a, const void *b);
416 STB_EXTERN int (*stb_floatcmp(int offset))(const void *a, const void *b);
417 STB_EXTERN int (*stb_doublecmp(int offset))(const void *a, const void *b);
418 STB_EXTERN int (*stb_ucharcmp(int offset))(const void *a, const void *b);
419 STB_EXTERN int (*stb_charcmp(int offset))(const void *a, const void *b);
420 #endif
421
422 #ifdef STB_LIB_IMPLEMENTATION
423 static int stb__intcmpoffset, stb__ucharcmpoffset, stb__strcmpoffset;
424 static int stb__floatcmpoffset, stb__doublecmpoffset, stb__charcmpoffset;
425
stb__intcmp(const void * a,const void * b)426 int stb__intcmp(const void *a, const void *b)
427 {
428 const int p = *(const int *) ((const char *) a + stb__intcmpoffset);
429 const int q = *(const int *) ((const char *) b + stb__intcmpoffset);
430 return p < q ? -1 : p > q;
431 }
432
stb__ucharcmp(const void * a,const void * b)433 int stb__ucharcmp(const void *a, const void *b)
434 {
435 const int p = *(const unsigned char *) ((const char *) a + stb__ucharcmpoffset);
436 const int q = *(const unsigned char *) ((const char *) b + stb__ucharcmpoffset);
437 return p < q ? -1 : p > q;
438 }
439
stb__charcmp(const void * a,const void * b)440 int stb__charcmp(const void *a, const void *b)
441 {
442 const int p = *(const char *) ((const char *) a + stb__ucharcmpoffset);
443 const int q = *(const char *) ((const char *) b + stb__ucharcmpoffset);
444 return p < q ? -1 : p > q;
445 }
446
stb__floatcmp(const void * a,const void * b)447 int stb__floatcmp(const void *a, const void *b)
448 {
449 const float p = *(const float *) ((const char *) a + stb__floatcmpoffset);
450 const float q = *(const float *) ((const char *) b + stb__floatcmpoffset);
451 return p < q ? -1 : p > q;
452 }
453
stb__doublecmp(const void * a,const void * b)454 int stb__doublecmp(const void *a, const void *b)
455 {
456 const double p = *(const double *) ((const char *) a + stb__doublecmpoffset);
457 const double q = *(const double *) ((const char *) b + stb__doublecmpoffset);
458 return p < q ? -1 : p > q;
459 }
460
stb__qsort_strcmp(const void * a,const void * b)461 int stb__qsort_strcmp(const void *a, const void *b)
462 {
463 const char *p = *(const char **) ((const char *) a + stb__strcmpoffset);
464 const char *q = *(const char **) ((const char *) b + stb__strcmpoffset);
465 return strcmp(p,q);
466 }
467
stb__qsort_stricmp(const void * a,const void * b)468 int stb__qsort_stricmp(const void *a, const void *b)
469 {
470 const char *p = *(const char **) ((const char *) a + stb__strcmpoffset);
471 const char *q = *(const char **) ((const char *) b + stb__strcmpoffset);
472 return stb_stricmp(p,q);
473 }
474
stb_intcmp(int offset)475 int (*stb_intcmp(int offset))(const void *, const void *)
476 {
477 stb__intcmpoffset = offset;
478 return &stb__intcmp;
479 }
480
stb_ucharcmp(int offset)481 int (*stb_ucharcmp(int offset))(const void *, const void *)
482 {
483 stb__ucharcmpoffset = offset;
484 return &stb__ucharcmp;
485 }
486
stb_charcmp(int offset)487 int (*stb_charcmp(int offset))(const void *, const void *)
488 {
489 stb__charcmpoffset = offset;
490 return &stb__ucharcmp;
491 }
492
stb_qsort_strcmp(int offset)493 int (*stb_qsort_strcmp(int offset))(const void *, const void *)
494 {
495 stb__strcmpoffset = offset;
496 return &stb__qsort_strcmp;
497 }
498
stb_qsort_stricmp(int offset)499 int (*stb_qsort_stricmp(int offset))(const void *, const void *)
500 {
501 stb__strcmpoffset = offset;
502 return &stb__qsort_stricmp;
503 }
504
stb_floatcmp(int offset)505 int (*stb_floatcmp(int offset))(const void *, const void *)
506 {
507 stb__floatcmpoffset = offset;
508 return &stb__floatcmp;
509 }
510
stb_doublecmp(int offset)511 int (*stb_doublecmp(int offset))(const void *, const void *)
512 {
513 stb__doublecmpoffset = offset;
514 return &stb__doublecmp;
515 }
516 #endif
517
518 //////////////////////////////////////////////////////////////////////////////
519 //
520 // String Processing
521 //
522
523 #ifndef STB_INCLUDE_STB_LIB_H
524 #define stb_prefixi(s,t) (0==stb_strnicmp((s),(t),strlen(t)))
525
526 enum stb_splitpath_flag
527 {
528 STB_PATH = 1,
529 STB_FILE = 2,
530 STB_EXT = 4,
531 STB_PATH_FILE = STB_PATH + STB_FILE,
532 STB_FILE_EXT = STB_FILE + STB_EXT,
533 STB_EXT_NO_PERIOD = 8,
534 };
535
536 STB_EXTERN char * stb_skipwhite(char *s);
537 STB_EXTERN char * stb_trimwhite(char *s);
538 STB_EXTERN char * stb_skipnewline(char *s);
539 STB_EXTERN char * stb_strncpy(char *s, char *t, int n);
540 STB_EXTERN char * stb_substr(char *t, int n);
541 STB_EXTERN char * stb_duplower(char *s);
542 STB_EXTERN void stb_tolower (char *s);
543 STB_EXTERN char * stb_strchr2 (char *s, char p1, char p2);
544 STB_EXTERN char * stb_strrchr2(char *s, char p1, char p2);
545 STB_EXTERN char * stb_strtok(char *output, char *src, char *delimit);
546 STB_EXTERN char * stb_strtok_keep(char *output, char *src, char *delimit);
547 STB_EXTERN char * stb_strtok_invert(char *output, char *src, char *allowed);
548 STB_EXTERN char * stb_dupreplace(char *s, char *find, char *replace);
549 STB_EXTERN void stb_replaceinplace(char *s, char *find, char *replace);
550 STB_EXTERN char * stb_splitpath(char *output, char *src, int flag);
551 STB_EXTERN char * stb_splitpathdup(char *src, int flag);
552 STB_EXTERN char * stb_replacedir(char *output, char *src, char *dir);
553 STB_EXTERN char * stb_replaceext(char *output, char *src, char *ext);
554 STB_EXTERN void stb_fixpath(char *path);
555 STB_EXTERN char * stb_shorten_path_readable(char *path, int max_len);
556 STB_EXTERN int stb_suffix (char *s, char *t);
557 STB_EXTERN int stb_suffixi(char *s, char *t);
558 STB_EXTERN int stb_prefix (char *s, char *t);
559 STB_EXTERN char * stb_strichr(char *s, char t);
560 STB_EXTERN char * stb_stristr(char *s, char *t);
561 STB_EXTERN int stb_prefix_count(char *s, char *t);
562 STB_EXTERN const char * stb_plural(int n); // "s" or ""
563 STB_EXTERN size_t stb_strscpy(char *d, const char *s, size_t n);
564
565 STB_EXTERN char **stb_tokens(char *src, char *delimit, int *count);
566 STB_EXTERN char **stb_tokens_nested(char *src, char *delimit, int *count, char *nest_in, char *nest_out);
567 STB_EXTERN char **stb_tokens_nested_empty(char *src, char *delimit, int *count, char *nest_in, char *nest_out);
568 STB_EXTERN char **stb_tokens_allowempty(char *src, char *delimit, int *count);
569 STB_EXTERN char **stb_tokens_stripwhite(char *src, char *delimit, int *count);
570 STB_EXTERN char **stb_tokens_withdelim(char *src, char *delimit, int *count);
571 STB_EXTERN char **stb_tokens_quoted(char *src, char *delimit, int *count);
572 // with 'quoted', allow delimiters to appear inside quotation marks, and don't
573 // strip whitespace inside them (and we delete the quotation marks unless they
574 // appear back to back, in which case they're considered escaped)
575 #endif // STB_INCLUDE_STB_LIB_H
576
577 #ifdef STB_LIB_IMPLEMENTATION
578 #include <ctype.h>
579
stb_strscpy(char * d,const char * s,size_t n)580 size_t stb_strscpy(char *d, const char *s, size_t n)
581 {
582 size_t len = strlen(s);
583 if (len >= n) {
584 if (n) d[0] = 0;
585 return 0;
586 }
587 strcpy(d,s);
588 return len + 1;
589 }
590
stb_plural(int n)591 const char *stb_plural(int n)
592 {
593 return n == 1 ? "" : "s";
594 }
595
stb_prefix(char * s,char * t)596 int stb_prefix(char *s, char *t)
597 {
598 while (*t)
599 if (*s++ != *t++)
600 return 0;
601 return 1;
602 }
603
stb_prefix_count(char * s,char * t)604 int stb_prefix_count(char *s, char *t)
605 {
606 int c=0;
607 while (*t) {
608 if (*s++ != *t++)
609 break;
610 ++c;
611 }
612 return c;
613 }
614
stb_suffix(char * s,char * t)615 int stb_suffix(char *s, char *t)
616 {
617 size_t n = strlen(s);
618 size_t m = strlen(t);
619 if (m <= n)
620 return 0 == strcmp(s+n-m, t);
621 else
622 return 0;
623 }
624
stb_suffixi(char * s,char * t)625 int stb_suffixi(char *s, char *t)
626 {
627 size_t n = strlen(s);
628 size_t m = strlen(t);
629 if (m <= n)
630 return 0 == stb_stricmp(s+n-m, t);
631 else
632 return 0;
633 }
634
635 // originally I was using this table so that I could create known sentinel
636 // values--e.g. change whitetable[0] to be true if I was scanning for whitespace,
637 // and false if I was scanning for nonwhite. I don't appear to be using that
638 // functionality anymore (I do for tokentable, though), so just replace it
639 // with isspace()
stb_skipwhite(char * s)640 char *stb_skipwhite(char *s)
641 {
642 while (isspace((unsigned char) *s)) ++s;
643 return s;
644 }
645
stb_skipnewline(char * s)646 char *stb_skipnewline(char *s)
647 {
648 if (s[0] == '\r' || s[0] == '\n') {
649 if (s[0]+s[1] == '\r' + '\n') ++s;
650 ++s;
651 }
652 return s;
653 }
654
stb_trimwhite(char * s)655 char *stb_trimwhite(char *s)
656 {
657 int i,n;
658 s = stb_skipwhite(s);
659 n = (int) strlen(s);
660 for (i=n-1; i >= 0; --i)
661 if (!isspace(s[i]))
662 break;
663 s[i+1] = 0;
664 return s;
665 }
666
stb_strncpy(char * s,char * t,int n)667 char *stb_strncpy(char *s, char *t, int n)
668 {
669 strncpy(s,t,n);
670 s[n-1] = 0;
671 return s;
672 }
673
stb_substr(char * t,int n)674 char *stb_substr(char *t, int n)
675 {
676 char *a;
677 int z = (int) strlen(t);
678 if (z < n) n = z;
679 a = (char *) malloc(n+1);
680 strncpy(a,t,n);
681 a[n] = 0;
682 return a;
683 }
684
stb_duplower(char * s)685 char *stb_duplower(char *s)
686 {
687 char *p = strdup(s), *q = p;
688 while (*q) {
689 *q = tolower(*q);
690 ++q;
691 }
692 return p;
693 }
694
stb_tolower(char * s)695 void stb_tolower(char *s)
696 {
697 while (*s) {
698 *s = tolower(*s);
699 ++s;
700 }
701 }
702
stb_strchr2(char * s,char x,char y)703 char *stb_strchr2(char *s, char x, char y)
704 {
705 for(; *s; ++s)
706 if (*s == x || *s == y)
707 return s;
708 return NULL;
709 }
710
stb_strrchr2(char * s,char x,char y)711 char *stb_strrchr2(char *s, char x, char y)
712 {
713 char *r = NULL;
714 for(; *s; ++s)
715 if (*s == x || *s == y)
716 r = s;
717 return r;
718 }
719
stb_strichr(char * s,char t)720 char *stb_strichr(char *s, char t)
721 {
722 if (tolower(t) == toupper(t))
723 return strchr(s,t);
724 return stb_strchr2(s, (char) tolower(t), (char) toupper(t));
725 }
726
stb_stristr(char * s,char * t)727 char *stb_stristr(char *s, char *t)
728 {
729 size_t n = strlen(t);
730 char *z;
731 if (n==0) return s;
732 while ((z = stb_strichr(s, *t)) != NULL) {
733 if (0==stb_strnicmp(z, t, n))
734 return z;
735 s = z+1;
736 }
737 return NULL;
738 }
739
stb_strtok_raw(char * output,char * src,char * delimit,int keep,int invert)740 static char *stb_strtok_raw(char *output, char *src, char *delimit, int keep, int invert)
741 {
742 if (invert) {
743 while (*src && strchr(delimit, *src) != NULL) {
744 *output++ = *src++;
745 }
746 } else {
747 while (*src && strchr(delimit, *src) == NULL) {
748 *output++ = *src++;
749 }
750 }
751 *output = 0;
752 if (keep)
753 return src;
754 else
755 return *src ? src+1 : src;
756 }
757
stb_strtok(char * output,char * src,char * delimit)758 char *stb_strtok(char *output, char *src, char *delimit)
759 {
760 return stb_strtok_raw(output, src, delimit, 0, 0);
761 }
762
stb_strtok_keep(char * output,char * src,char * delimit)763 char *stb_strtok_keep(char *output, char *src, char *delimit)
764 {
765 return stb_strtok_raw(output, src, delimit, 1, 0);
766 }
767
stb_strtok_invert(char * output,char * src,char * delimit)768 char *stb_strtok_invert(char *output, char *src, char *delimit)
769 {
770 return stb_strtok_raw(output, src, delimit, 1,1);
771 }
772
stb_tokens_raw(char * src_,char * delimit,int * count,int stripwhite,int allow_empty,char * start,char * end)773 static char **stb_tokens_raw(char *src_, char *delimit, int *count,
774 int stripwhite, int allow_empty, char *start, char *end)
775 {
776 int nested = 0;
777 unsigned char *src = (unsigned char *) src_;
778 static char stb_tokentable[256]; // rely on static initializion to 0
779 static char stable[256],etable[256];
780 char *out;
781 char **result;
782 int num=0;
783 unsigned char *s;
784
785 s = (unsigned char *) delimit; while (*s) stb_tokentable[*s++] = 1;
786 if (start) {
787 s = (unsigned char *) start; while (*s) stable[*s++] = 1;
788 s = (unsigned char *) end; if (s) while (*s) stable[*s++] = 1;
789 s = (unsigned char *) end; if (s) while (*s) etable[*s++] = 1;
790 }
791 stable[0] = 1;
792
793 // two passes through: the first time, counting how many
794 s = (unsigned char *) src;
795 while (*s) {
796 // state: just found delimiter
797 // skip further delimiters
798 if (!allow_empty) {
799 stb_tokentable[0] = 0;
800 while (stb_tokentable[*s])
801 ++s;
802 if (!*s) break;
803 }
804 ++num;
805 // skip further non-delimiters
806 stb_tokentable[0] = 1;
807 if (stripwhite == 2) { // quoted strings
808 while (!stb_tokentable[*s]) {
809 if (*s != '"')
810 ++s;
811 else {
812 ++s;
813 if (*s == '"')
814 ++s; // "" -> ", not start a string
815 else {
816 // begin a string
817 while (*s) {
818 if (s[0] == '"') {
819 if (s[1] == '"') s += 2; // "" -> "
820 else { ++s; break; } // terminating "
821 } else
822 ++s;
823 }
824 }
825 }
826 }
827 } else
828 while (nested || !stb_tokentable[*s]) {
829 if (stable[*s]) {
830 if (!*s) break;
831 if (end ? etable[*s] : nested)
832 --nested;
833 else
834 ++nested;
835 }
836 ++s;
837 }
838 if (allow_empty) {
839 if (*s) ++s;
840 }
841 }
842 // now num has the actual count... malloc our output structure
843 // need space for all the strings: strings won't be any longer than
844 // original input, since for every '\0' there's at least one delimiter
845 result = (char **) malloc(sizeof(*result) * (num+1) + (s-src+1));
846 if (result == NULL) return result;
847 out = (char *) (result + (num+1));
848 // second pass: copy out the data
849 s = (unsigned char *) src;
850 num = 0;
851 nested = 0;
852 while (*s) {
853 char *last_nonwhite;
854 // state: just found delimiter
855 // skip further delimiters
856 if (!allow_empty) {
857 stb_tokentable[0] = 0;
858 if (stripwhite)
859 while (stb_tokentable[*s] || isspace(*s))
860 ++s;
861 else
862 while (stb_tokentable[*s])
863 ++s;
864 } else if (stripwhite) {
865 while (isspace(*s)) ++s;
866 }
867 if (!*s) break;
868 // we're past any leading delimiters and whitespace
869 result[num] = out;
870 ++num;
871 // copy non-delimiters
872 stb_tokentable[0] = 1;
873 last_nonwhite = out-1;
874 if (stripwhite == 2) {
875 while (!stb_tokentable[*s]) {
876 if (*s != '"') {
877 if (!isspace(*s)) last_nonwhite = out;
878 *out++ = *s++;
879 } else {
880 ++s;
881 if (*s == '"') {
882 if (!isspace(*s)) last_nonwhite = out;
883 *out++ = *s++; // "" -> ", not start string
884 } else {
885 // begin a quoted string
886 while (*s) {
887 if (s[0] == '"') {
888 if (s[1] == '"') { *out++ = *s; s += 2; }
889 else { ++s; break; } // terminating "
890 } else
891 *out++ = *s++;
892 }
893 last_nonwhite = out-1; // all in quotes counts as non-white
894 }
895 }
896 }
897 } else {
898 while (nested || !stb_tokentable[*s]) {
899 if (!isspace(*s)) last_nonwhite = out;
900 if (stable[*s]) {
901 if (!*s) break;
902 if (end ? etable[*s] : nested)
903 --nested;
904 else
905 ++nested;
906 }
907 *out++ = *s++;
908 }
909 }
910
911 if (stripwhite) // rewind to last non-whitespace char
912 out = last_nonwhite+1;
913 *out++ = '\0';
914
915 if (*s) ++s; // skip delimiter
916 }
917 s = (unsigned char *) delimit; while (*s) stb_tokentable[*s++] = 0;
918 if (start) {
919 s = (unsigned char *) start; while (*s) stable[*s++] = 1;
920 s = (unsigned char *) end; if (s) while (*s) stable[*s++] = 1;
921 s = (unsigned char *) end; if (s) while (*s) etable[*s++] = 1;
922 }
923 if (count != NULL) *count = num;
924 result[num] = 0;
925 return result;
926 }
927
stb_tokens(char * src,char * delimit,int * count)928 char **stb_tokens(char *src, char *delimit, int *count)
929 {
930 return stb_tokens_raw(src,delimit,count,0,0,0,0);
931 }
932
stb_tokens_nested(char * src,char * delimit,int * count,char * nest_in,char * nest_out)933 char **stb_tokens_nested(char *src, char *delimit, int *count, char *nest_in, char *nest_out)
934 {
935 return stb_tokens_raw(src,delimit,count,0,0,nest_in,nest_out);
936 }
937
stb_tokens_nested_empty(char * src,char * delimit,int * count,char * nest_in,char * nest_out)938 char **stb_tokens_nested_empty(char *src, char *delimit, int *count, char *nest_in, char *nest_out)
939 {
940 return stb_tokens_raw(src,delimit,count,0,1,nest_in,nest_out);
941 }
942
stb_tokens_allowempty(char * src,char * delimit,int * count)943 char **stb_tokens_allowempty(char *src, char *delimit, int *count)
944 {
945 return stb_tokens_raw(src,delimit,count,0,1,0,0);
946 }
947
stb_tokens_stripwhite(char * src,char * delimit,int * count)948 char **stb_tokens_stripwhite(char *src, char *delimit, int *count)
949 {
950 return stb_tokens_raw(src,delimit,count,1,1,0,0);
951 }
952
stb_tokens_quoted(char * src,char * delimit,int * count)953 char **stb_tokens_quoted(char *src, char *delimit, int *count)
954 {
955 return stb_tokens_raw(src,delimit,count,2,1,0,0);
956 }
957
stb_dupreplace(char * src,char * find,char * replace)958 char *stb_dupreplace(char *src, char *find, char *replace)
959 {
960 size_t len_find = strlen(find);
961 size_t len_replace = strlen(replace);
962 int count = 0;
963
964 char *s,*p,*q;
965
966 s = strstr(src, find);
967 if (s == NULL) return strdup(src);
968 do {
969 ++count;
970 s = strstr(s + len_find, find);
971 } while (s != NULL);
972
973 p = (char *) malloc(strlen(src) + count * (len_replace - len_find) + 1);
974 if (p == NULL) return p;
975 q = p;
976 s = src;
977 for (;;) {
978 char *t = strstr(s, find);
979 if (t == NULL) {
980 strcpy(q,s);
981 assert(strlen(p) == strlen(src) + count*(len_replace-len_find));
982 return p;
983 }
984 memcpy(q, s, t-s);
985 q += t-s;
986 memcpy(q, replace, len_replace);
987 q += len_replace;
988 s = t + len_find;
989 }
990 }
991
stb_replaceinplace(char * src,char * find,char * replace)992 void stb_replaceinplace(char *src, char *find, char *replace)
993 {
994 size_t len_find = strlen(find);
995 size_t len_replace = strlen(replace);
996 int delta;
997
998 char *s,*p,*q;
999
1000 delta = len_replace - len_find;
1001 assert(delta <= 0);
1002 if (delta > 0) return;
1003
1004 p = strstr(src, find);
1005 if (p == NULL) return;
1006
1007 s = q = p;
1008 while (*s) {
1009 memcpy(q, replace, len_replace);
1010 p += len_find;
1011 q += len_replace;
1012 s = strstr(p, find);
1013 if (s == NULL) s = p + strlen(p);
1014 memmove(q, p, s-p);
1015 q += s-p;
1016 p = s;
1017 }
1018 *q = 0;
1019 }
1020
stb_fixpath(char * path)1021 void stb_fixpath(char *path)
1022 {
1023 for(; *path; ++path)
1024 if (*path == '\\')
1025 *path = '/';
1026 }
1027
stb__add_section(char * buffer,char * data,int curlen,int newlen)1028 void stb__add_section(char *buffer, char *data, int curlen, int newlen)
1029 {
1030 if (newlen < curlen) {
1031 int z1 = newlen >> 1, z2 = newlen-z1;
1032 memcpy(buffer, data, z1-1);
1033 buffer[z1-1] = '.';
1034 buffer[z1-0] = '.';
1035 memcpy(buffer+z1+1, data+curlen-z2+1, z2-1);
1036 } else
1037 memcpy(buffer, data, curlen);
1038 }
1039
stb_shorten_path_readable(char * path,int len)1040 char * stb_shorten_path_readable(char *path, int len)
1041 {
1042 static char buffer[1024];
1043 int n = strlen(path),n1,n2,r1,r2;
1044 char *s;
1045 if (n <= len) return path;
1046 if (len > 1024) return path;
1047 s = stb_strrchr2(path, '/', '\\');
1048 if (s) {
1049 n1 = s - path + 1;
1050 n2 = n - n1;
1051 ++s;
1052 } else {
1053 n1 = 0;
1054 n2 = n;
1055 s = path;
1056 }
1057 // now we need to reduce r1 and r2 so that they fit in len
1058 if (n1 < len>>1) {
1059 r1 = n1;
1060 r2 = len - r1;
1061 } else if (n2 < len >> 1) {
1062 r2 = n2;
1063 r1 = len - r2;
1064 } else {
1065 r1 = n1 * len / n;
1066 r2 = n2 * len / n;
1067 if (r1 < len>>2) r1 = len>>2, r2 = len-r1;
1068 if (r2 < len>>2) r2 = len>>2, r1 = len-r2;
1069 }
1070 assert(r1 <= n1 && r2 <= n2);
1071 if (n1)
1072 stb__add_section(buffer, path, n1, r1);
1073 stb__add_section(buffer+r1, s, n2, r2);
1074 buffer[len] = 0;
1075 return buffer;
1076 }
1077
stb__splitpath_raw(char * buffer,char * path,int flag)1078 static char *stb__splitpath_raw(char *buffer, char *path, int flag)
1079 {
1080 int len=0,x,y, n = (int) strlen(path), f1,f2;
1081 char *s = stb_strrchr2(path, '/', '\\');
1082 char *t = strrchr(path, '.');
1083 if (s && t && t < s) t = NULL;
1084 if (s) ++s;
1085
1086 if (flag == STB_EXT_NO_PERIOD)
1087 flag |= STB_EXT;
1088
1089 if (!(flag & (STB_PATH | STB_FILE | STB_EXT))) return NULL;
1090
1091 f1 = s == NULL ? 0 : s-path; // start of filename
1092 f2 = t == NULL ? n : t-path; // just past end of filename
1093
1094 if (flag & STB_PATH) {
1095 x = 0; if (f1 == 0 && flag == STB_PATH) len=2;
1096 } else if (flag & STB_FILE) {
1097 x = f1;
1098 } else {
1099 x = f2;
1100 if (flag & STB_EXT_NO_PERIOD)
1101 if (buffer[x] == '.')
1102 ++x;
1103 }
1104
1105 if (flag & STB_EXT)
1106 y = n;
1107 else if (flag & STB_FILE)
1108 y = f2;
1109 else
1110 y = f1;
1111
1112 if (buffer == NULL) {
1113 buffer = (char *) malloc(y-x + len + 1);
1114 if (!buffer) return NULL;
1115 }
1116
1117 if (len) { strcpy(buffer, "./"); return buffer; }
1118 strncpy(buffer, path+x, y-x);
1119 buffer[y-x] = 0;
1120 return buffer;
1121 }
1122
stb_splitpath(char * output,char * src,int flag)1123 char *stb_splitpath(char *output, char *src, int flag)
1124 {
1125 return stb__splitpath_raw(output, src, flag);
1126 }
1127
stb_splitpathdup(char * src,int flag)1128 char *stb_splitpathdup(char *src, int flag)
1129 {
1130 return stb__splitpath_raw(NULL, src, flag);
1131 }
1132
stb_replacedir(char * output,char * src,char * dir)1133 char *stb_replacedir(char *output, char *src, char *dir)
1134 {
1135 char buffer[4096];
1136 stb_splitpath(buffer, src, STB_FILE | STB_EXT);
1137 if (dir)
1138 sprintf(output, "%s/%s", dir, buffer);
1139 else
1140 strcpy(output, buffer);
1141 return output;
1142 }
1143
stb_replaceext(char * output,char * src,char * ext)1144 char *stb_replaceext(char *output, char *src, char *ext)
1145 {
1146 char buffer[4096];
1147 stb_splitpath(buffer, src, STB_PATH | STB_FILE);
1148 if (ext)
1149 sprintf(output, "%s.%s", buffer, ext[0] == '.' ? ext+1 : ext);
1150 else
1151 strcpy(output, buffer);
1152 return output;
1153 }
1154 #endif
1155
1156
1157 //////////////////////////////////////////////////////////////////////////////
1158 //
1159 // stb_arr
1160 //
1161 // An stb_arr is directly useable as a pointer (use the actual type in your
1162 // definition), but when it resizes, it returns a new pointer and you can't
1163 // use the old one, so you have to be careful to copy-in-out as necessary.
1164 //
1165 // Use a NULL pointer as a 0-length array.
1166 //
1167 // float *my_array = NULL, *temp;
1168 //
1169 // // add elements on the end one at a time
1170 // stb_arr_push(my_array, 0.0f);
1171 // stb_arr_push(my_array, 1.0f);
1172 // stb_arr_push(my_array, 2.0f);
1173 //
1174 // assert(my_array[1] == 2.0f);
1175 //
1176 // // add an uninitialized element at the end, then assign it
1177 // *stb_arr_add(my_array) = 3.0f;
1178 //
1179 // // add three uninitialized elements at the end
1180 // temp = stb_arr_addn(my_array,3);
1181 // temp[0] = 4.0f;
1182 // temp[1] = 5.0f;
1183 // temp[2] = 6.0f;
1184 //
1185 // assert(my_array[5] == 5.0f);
1186 //
1187 // // remove the last one
1188 // stb_arr_pop(my_array);
1189 //
1190 // assert(stb_arr_len(my_array) == 6);
1191
1192
1193 #ifndef STB_INCLUDE_STB_LIB_H
1194
1195 // simple functions written on top of other functions
1196 #define stb_arr_empty(a) ( stb_arr_len(a) == 0 )
1197 #define stb_arr_add(a) ( stb_arr_addn((a),1) )
1198 #define stb_arr_push(a,v) ( *stb_arr_add(a)=(v) )
1199
1200 typedef struct
1201 {
1202 int len, limit;
1203 unsigned int signature;
1204 unsigned int padding; // make it a multiple of 16 so preserve alignment mod 16
1205 } stb__arr;
1206
1207 #define stb_arr_signature 0x51bada7b // ends with 0123 in decimal
1208
1209 // access the header block stored before the data
1210 #define stb_arrhead(a) /*lint --e(826)*/ (((stb__arr *) (a)) - 1)
1211 #define stb_arrhead2(a) /*lint --e(826)*/ (((stb__arr *) (a)) - 1)
1212
1213 #ifdef STB_DEBUG
1214 #define stb_arr_check(a) assert(!a || stb_arrhead(a)->signature == stb_arr_signature)
1215 #define stb_arr_check2(a) assert(!a || stb_arrhead2(a)->signature == stb_arr_signature)
1216 #else
1217 #define stb_arr_check(a) ((void) 0)
1218 #define stb_arr_check2(a) ((void) 0)
1219 #endif
1220
1221 // ARRAY LENGTH
1222
1223 // get the array length; special case if pointer is NULL
1224 #define stb_arr_len(a) (a ? stb_arrhead(a)->len : 0)
1225 #define stb_arr_len2(a) ((stb__arr *) (a) ? stb_arrhead2(a)->len : 0)
1226 #define stb_arr_lastn(a) (stb_arr_len(a)-1)
1227
1228 // check whether a given index is valid -- tests 0 <= i < stb_arr_len(a)
1229 #define stb_arr_valid(a,i) (a ? (int) (i) < stb_arrhead(a)->len : 0)
1230
1231 // change the array length so is is exactly N entries long, creating
1232 // uninitialized entries as needed
1233 #define stb_arr_setlen(a,n) \
1234 (stb__arr_setlen((void **) &(a), sizeof(a[0]), (n)))
1235
1236 // change the array length so that N is a valid index (that is, so
1237 // it is at least N entries long), creating uninitialized entries as needed
1238 #define stb_arr_makevalid(a,n) \
1239 (stb_arr_len(a) < (n)+1 ? stb_arr_setlen(a,(n)+1),(a) : (a))
1240
1241 // remove the last element of the array, returning it
1242 #define stb_arr_pop(a) ((stb_arr_check(a), (a))[--stb_arrhead(a)->len])
1243
1244 // access the last element in the array
1245 #define stb_arr_last(a) ((stb_arr_check(a), (a))[stb_arr_len(a)-1])
1246
1247 // is iterator at end of list?
1248 #define stb_arr_end(a,i) ((i) >= &(a)[stb_arr_len(a)])
1249
1250 // (internal) change the allocated length of the array
1251 #define stb_arr__grow(a,n) (stb_arr_check(a), stb_arrhead(a)->len += (n))
1252
1253 // add N new uninitialized elements to the end of the array
1254 #define stb_arr__addn(a,n) /*lint --e(826)*/ \
1255 ((stb_arr_len(a)+(n) > stb_arrcurmax(a)) \
1256 ? (stb__arr_addlen((void **) &(a),sizeof(*a),(n)),0) \
1257 : ((stb_arr__grow(a,n), 0)))
1258
1259 // add N new uninitialized elements to the end of the array, and return
1260 // a pointer to the first new one
1261 #define stb_arr_addn(a,n) (stb_arr__addn((a),n),(a)+stb_arr_len(a)-(n))
1262
1263 // add N new uninitialized elements starting at index 'i'
1264 #define stb_arr_insertn(a,i,n) (stb__arr_insertn((void **) &(a), sizeof(*a), i, n))
1265
1266 // insert an element at i
1267 #define stb_arr_insert(a,i,v) (stb__arr_insertn((void **) &(a), sizeof(*a), i, 1), ((a)[i] = v))
1268
1269 // delete N elements from the middle starting at index 'i'
1270 #define stb_arr_deleten(a,i,n) (stb__arr_deleten((void **) &(a), sizeof(*a), i, n))
1271
1272 // delete the i'th element
1273 #define stb_arr_delete(a,i) stb_arr_deleten(a,i,1)
1274
1275 // delete the i'th element, swapping down from the end
1276 #define stb_arr_fastdelete(a,i) \
1277 (stb_swap(&a[i], &a[stb_arrhead(a)->len-1], sizeof(*a)), stb_arr_pop(a))
1278
1279
1280 // ARRAY STORAGE
1281
1282 // get the array maximum storage; special case if NULL
1283 #define stb_arrcurmax(a) (a ? stb_arrhead(a)->limit : 0)
1284 #define stb_arrcurmax2(a) (a ? stb_arrhead2(a)->limit : 0)
1285
1286 // set the maxlength of the array to n in anticipation of further growth
1287 #define stb_arr_setsize(a,n) (stb_arr_check(a), stb__arr_setsize((void **) &(a),sizeof((a)[0]),n))
1288
1289 // make sure maxlength is large enough for at least N new allocations
1290 #define stb_arr_atleast(a,n) (stb_arr_len(a)+(n) > stb_arrcurmax(a) \
1291 ? stb_arr_setsize((a), (n)) : 0)
1292
1293 // make a copy of a given array (copies contents via 'memcpy'!)
1294 #define stb_arr_copy(a) stb__arr_copy(a, sizeof((a)[0]))
1295
1296 // compute the storage needed to store all the elements of the array
1297 #define stb_arr_storage(a) (stb_arr_len(a) * sizeof((a)[0]))
1298
1299 #define stb_arr_for(v,arr) for((v)=(arr); (v) < (arr)+stb_arr_len(arr); ++(v))
1300
1301 // IMPLEMENTATION
1302
1303 STB_EXTERN void stb_arr_free_(void **p);
1304 STB_EXTERN void *stb__arr_copy_(void *p, int elem_size);
1305 STB_EXTERN void stb__arr_setsize_(void **p, int size, int limit);
1306 STB_EXTERN void stb__arr_setlen_(void **p, int size, int newlen);
1307 STB_EXTERN void stb__arr_addlen_(void **p, int size, int addlen);
1308 STB_EXTERN void stb__arr_deleten_(void **p, int size, int loc, int n);
1309 STB_EXTERN void stb__arr_insertn_(void **p, int size, int loc, int n);
1310
1311 #define stb_arr_free(p) stb_arr_free_((void **) &(p))
1312
1313 #ifndef STBLIB_MALLOC_WRAPPER // @Todo
1314 #define stb__arr_setsize stb__arr_setsize_
1315 #define stb__arr_setlen stb__arr_setlen_
1316 #define stb__arr_addlen stb__arr_addlen_
1317 #define stb__arr_deleten stb__arr_deleten_
1318 #define stb__arr_insertn stb__arr_insertn_
1319 #define stb__arr_copy stb__arr_copy_
1320 #else
1321 #define stb__arr_addlen(p,s,n) stb__arr_addlen_(p,s,n,__FILE__,__LINE__)
1322 #define stb__arr_setlen(p,s,n) stb__arr_setlen_(p,s,n,__FILE__,__LINE__)
1323 #define stb__arr_setsize(p,s,n) stb__arr_setsize_(p,s,n,__FILE__,__LINE__)
1324 #define stb__arr_deleten(p,s,i,n) stb__arr_deleten_(p,s,i,n,__FILE__,__LINE__)
1325 #define stb__arr_insertn(p,s,i,n) stb__arr_insertn_(p,s,i,n,__FILE__,__LINE__)
1326 #define stb__arr_copy(p,s) stb__arr_copy_(p,s,__FILE__,__LINE__)
1327 #endif
1328 #endif // STB_INCLUDE_STB_LIB_H
1329
1330 #ifdef STB_LIB_IMPLEMENTATION
stb_arr_malloc(void ** target,void * context)1331 void stb_arr_malloc(void **target, void *context)
1332 {
1333 stb__arr *q = (stb__arr *) malloc(sizeof(*q));
1334 q->len = q->limit = 0;
1335 q->signature = stb_arr_signature;
1336 *target = (void *) (q+1);
1337 }
1338
stb__arr_malloc(int size)1339 static void * stb__arr_malloc(int size)
1340 {
1341 return malloc(size);
1342 }
1343
stb__arr_copy_(void * p,int elem_size)1344 void * stb__arr_copy_(void *p, int elem_size)
1345 {
1346 stb__arr *q;
1347 if (p == NULL) return p;
1348 q = (stb__arr *) malloc(sizeof(*q) + elem_size * stb_arrhead2(p)->limit);
1349 stb_arr_check2(p);
1350 memcpy(q, stb_arrhead2(p), sizeof(*q) + elem_size * stb_arrhead2(p)->len);
1351 return q+1;
1352 }
1353
stb_arr_free_(void ** pp)1354 void stb_arr_free_(void **pp)
1355 {
1356 void *p = *pp;
1357 stb_arr_check2(p);
1358 if (p) {
1359 stb__arr *q = stb_arrhead2(p);
1360 free(q);
1361 }
1362 *pp = NULL;
1363 }
1364
stb__arrsize_(void ** pp,int size,int limit,int len)1365 static void stb__arrsize_(void **pp, int size, int limit, int len)
1366 {
1367 void *p = *pp;
1368 stb__arr *a;
1369 stb_arr_check2(p);
1370 if (p == NULL) {
1371 if (len == 0 && size == 0) return;
1372 a = (stb__arr *) stb__arr_malloc(sizeof(*a) + size*limit);
1373 a->limit = limit;
1374 a->len = len;
1375 a->signature = stb_arr_signature;
1376 } else {
1377 a = stb_arrhead2(p);
1378 a->len = len;
1379 if (a->limit < limit) {
1380 void *p;
1381 if (a->limit >= 4 && limit < a->limit * 2)
1382 limit = a->limit * 2;
1383 p = realloc(a, sizeof(*a) + limit*size);
1384 if (p) {
1385 a = (stb__arr *) p;
1386 a->limit = limit;
1387 } else {
1388 // throw an error!
1389 }
1390 }
1391 }
1392 a->len = a->len < a->limit ? a->len : a->limit;
1393 *pp = a+1;
1394 }
1395
stb__arr_setsize_(void ** pp,int size,int limit)1396 void stb__arr_setsize_(void **pp, int size, int limit)
1397 {
1398 void *p = *pp;
1399 stb_arr_check2(p);
1400 stb__arrsize_(pp, size, limit, stb_arr_len2(p));
1401 }
1402
stb__arr_setlen_(void ** pp,int size,int newlen)1403 void stb__arr_setlen_(void **pp, int size, int newlen)
1404 {
1405 void *p = *pp;
1406 stb_arr_check2(p);
1407 if (stb_arrcurmax2(p) < newlen || p == NULL) {
1408 stb__arrsize_(pp, size, newlen, newlen);
1409 } else {
1410 stb_arrhead2(p)->len = newlen;
1411 }
1412 }
1413
stb__arr_addlen_(void ** p,int size,int addlen)1414 void stb__arr_addlen_(void **p, int size, int addlen)
1415 {
1416 stb__arr_setlen_(p, size, stb_arr_len2(*p) + addlen);
1417 }
1418
stb__arr_insertn_(void ** pp,int size,int i,int n)1419 void stb__arr_insertn_(void **pp, int size, int i, int n)
1420 {
1421 void *p = *pp;
1422 if (n) {
1423 int z;
1424
1425 if (p == NULL) {
1426 stb__arr_addlen_(pp, size, n);
1427 return;
1428 }
1429
1430 z = stb_arr_len2(p);
1431 stb__arr_addlen_(&p, size, n);
1432 memmove((char *) p + (i+n)*size, (char *) p + i*size, size * (z-i));
1433 }
1434 *pp = p;
1435 }
1436
stb__arr_deleten_(void ** pp,int size,int i,int n)1437 void stb__arr_deleten_(void **pp, int size, int i, int n)
1438 {
1439 void *p = *pp;
1440 if (n) {
1441 memmove((char *) p + i*size, (char *) p + (i+n)*size, size * (stb_arr_len2(p)-(i+n)));
1442 stb_arrhead2(p)->len -= n;
1443 }
1444 *pp = p;
1445 }
1446 #endif
1447
1448 //////////////////////////////////////////////////////////////////////////////
1449 //
1450 // Hashing
1451 //
1452 // typical use for this is to make a power-of-two hash table.
1453 //
1454 // let N = size of table (2^n)
1455 // let H = stb_hash(str)
1456 // let S = stb_rehash(H) | 1
1457 //
1458 // then hash probe sequence P(i) for i=0..N-1
1459 // P(i) = (H + S*i) & (N-1)
1460 //
1461 // the idea is that H has 32 bits of hash information, but the
1462 // table has only, say, 2^20 entries so only uses 20 of the bits.
1463 // then by rehashing the original H we get 2^12 different probe
1464 // sequences for a given initial probe location. (So it's optimal
1465 // for 64K tables and its optimality decreases past that.)
1466 //
1467 // ok, so I've added something that generates _two separate_
1468 // 32-bit hashes simultaneously which should scale better to
1469 // very large tables.
1470
1471 #ifndef STB_INCLUDE_STB_LIB_H
1472 STB_EXTERN unsigned int stb_hash(char *str);
1473 STB_EXTERN unsigned int stb_hashptr(void *p);
1474 STB_EXTERN unsigned int stb_hashlen(char *str, int len);
1475 STB_EXTERN unsigned int stb_rehash_improved(unsigned int v);
1476 STB_EXTERN unsigned int stb_hash_fast(void *p, int len);
1477 STB_EXTERN unsigned int stb_hash2(char *str, unsigned int *hash2_ptr);
1478 STB_EXTERN unsigned int stb_hash_number(unsigned int hash);
1479
1480 #define stb_rehash(x) ((x) + ((x) >> 6) + ((x) >> 19))
1481 #endif // STB_INCLUDE_STB_LIB_H
1482
1483 #ifdef STB_LIB_IMPLEMENTATION
stb_hash(char * str)1484 unsigned int stb_hash(char *str)
1485 {
1486 unsigned int hash = 0;
1487 while (*str)
1488 hash = (hash << 7) + (hash >> 25) + *str++;
1489 return hash + (hash >> 16);
1490 }
1491
stb_hashlen(char * str,int len)1492 unsigned int stb_hashlen(char *str, int len)
1493 {
1494 unsigned int hash = 0;
1495 while (len-- > 0 && *str)
1496 hash = (hash << 7) + (hash >> 25) + *str++;
1497 return hash + (hash >> 16);
1498 }
1499
stb_hashptr(void * p)1500 unsigned int stb_hashptr(void *p)
1501 {
1502 unsigned int x = (unsigned int)(size_t) p;
1503
1504 // typically lacking in low bits and high bits
1505 x = stb_rehash(x);
1506 x += x << 16;
1507
1508 // pearson's shuffle
1509 x ^= x << 3;
1510 x += x >> 5;
1511 x ^= x << 2;
1512 x += x >> 15;
1513 x ^= x << 10;
1514 return stb_rehash(x);
1515 }
1516
stb_rehash_improved(unsigned int v)1517 unsigned int stb_rehash_improved(unsigned int v)
1518 {
1519 return stb_hashptr((void *)(size_t) v);
1520 }
1521
stb_hash2(char * str,unsigned int * hash2_ptr)1522 unsigned int stb_hash2(char *str, unsigned int *hash2_ptr)
1523 {
1524 unsigned int hash1 = 0x3141592c;
1525 unsigned int hash2 = 0x77f044ed;
1526 while (*str) {
1527 hash1 = (hash1 << 7) + (hash1 >> 25) + *str;
1528 hash2 = (hash2 << 11) + (hash2 >> 21) + *str;
1529 ++str;
1530 }
1531 *hash2_ptr = hash2 + (hash1 >> 16);
1532 return hash1 + (hash2 >> 16);
1533 }
1534
1535 // Paul Hsieh hash
1536 #define stb__get16_slow(p) ((p)[0] + ((p)[1] << 8))
1537 #if defined(_MSC_VER)
1538 #define stb__get16(p) (*((unsigned short *) (p)))
1539 #else
1540 #define stb__get16(p) stb__get16_slow(p)
1541 #endif
1542
stb_hash_fast(void * p,int len)1543 unsigned int stb_hash_fast(void *p, int len)
1544 {
1545 unsigned char *q = (unsigned char *) p;
1546 unsigned int hash = len;
1547
1548 if (len <= 0 || q == NULL) return 0;
1549
1550 /* Main loop */
1551 if (((int)(size_t) q & 1) == 0) {
1552 for (;len > 3; len -= 4) {
1553 unsigned int val;
1554 hash += stb__get16(q);
1555 val = (stb__get16(q+2) << 11);
1556 hash = (hash << 16) ^ hash ^ val;
1557 q += 4;
1558 hash += hash >> 11;
1559 }
1560 } else {
1561 for (;len > 3; len -= 4) {
1562 unsigned int val;
1563 hash += stb__get16_slow(q);
1564 val = (stb__get16_slow(q+2) << 11);
1565 hash = (hash << 16) ^ hash ^ val;
1566 q += 4;
1567 hash += hash >> 11;
1568 }
1569 }
1570
1571 /* Handle end cases */
1572 switch (len) {
1573 case 3: hash += stb__get16_slow(q);
1574 hash ^= hash << 16;
1575 hash ^= q[2] << 18;
1576 hash += hash >> 11;
1577 break;
1578 case 2: hash += stb__get16_slow(q);
1579 hash ^= hash << 11;
1580 hash += hash >> 17;
1581 break;
1582 case 1: hash += q[0];
1583 hash ^= hash << 10;
1584 hash += hash >> 1;
1585 break;
1586 case 0: break;
1587 }
1588
1589 /* Force "avalanching" of final 127 bits */
1590 hash ^= hash << 3;
1591 hash += hash >> 5;
1592 hash ^= hash << 4;
1593 hash += hash >> 17;
1594 hash ^= hash << 25;
1595 hash += hash >> 6;
1596
1597 return hash;
1598 }
1599
stb_hash_number(unsigned int hash)1600 unsigned int stb_hash_number(unsigned int hash)
1601 {
1602 hash ^= hash << 3;
1603 hash += hash >> 5;
1604 hash ^= hash << 4;
1605 hash += hash >> 17;
1606 hash ^= hash << 25;
1607 hash += hash >> 6;
1608 return hash;
1609 }
1610 #endif
1611
1612 //////////////////////////////////////////////////////////////////////////////
1613 //
1614 // Instantiated data structures
1615 //
1616 // This is an attempt to implement a templated data structure.
1617 //
1618 // Hash table: call stb_define_hash(TYPE,N,KEY,K1,K2,HASH,VALUE)
1619 // TYPE -- will define a structure type containing the hash table
1620 // N -- the name, will prefix functions named:
1621 // N create
1622 // N destroy
1623 // N get
1624 // N set, N add, N update,
1625 // N remove
1626 // KEY -- the type of the key. 'x == y' must be valid
1627 // K1,K2 -- keys never used by the app, used as flags in the hashtable
1628 // HASH -- a piece of code ending with 'return' that hashes key 'k'
1629 // VALUE -- the type of the value. 'x = y' must be valid
1630 //
1631 // Note that stb_define_hash_base can be used to define more sophisticated
1632 // hash tables, e.g. those that make copies of the key or use special
1633 // comparisons (e.g. strcmp).
1634
1635 #define STB_(prefix,name) stb__##prefix##name
1636 #define STB__(prefix,name) prefix##name
1637 #define STB__use(x) x
1638 #define STB__skip(x)
1639
1640 #define stb_declare_hash(PREFIX,TYPE,N,KEY,VALUE) \
1641 typedef struct stb__st_##TYPE TYPE;\
1642 PREFIX int STB__(N, init)(TYPE *h, int count);\
1643 PREFIX int STB__(N, memory_usage)(TYPE *h);\
1644 PREFIX TYPE * STB__(N, create)(void);\
1645 PREFIX TYPE * STB__(N, copy)(TYPE *h);\
1646 PREFIX void STB__(N, destroy)(TYPE *h);\
1647 PREFIX int STB__(N,get_flag)(TYPE *a, KEY k, VALUE *v);\
1648 PREFIX VALUE STB__(N,get)(TYPE *a, KEY k);\
1649 PREFIX int STB__(N, set)(TYPE *a, KEY k, VALUE v);\
1650 PREFIX int STB__(N, add)(TYPE *a, KEY k, VALUE v);\
1651 PREFIX int STB__(N, update)(TYPE*a,KEY k,VALUE v);\
1652 PREFIX int STB__(N, remove)(TYPE *a, KEY k, VALUE *v);
1653
1654 #define STB_nocopy(x) (x)
1655 #define STB_nodelete(x) 0
1656 #define STB_nofields
1657 #define STB_nonullvalue(x)
1658 #define STB_nullvalue(x) x
1659 #define STB_safecompare(x) x
1660 #define STB_nosafe(x)
1661 #define STB_noprefix
1662
1663 #ifdef __GNUC__
1664 #define STB__nogcc(x)
1665 #else
1666 #define STB__nogcc(x) x
1667 #endif
1668
1669 #define stb_define_hash_base(PREFIX,TYPE,FIELDS,N,NC,LOAD_FACTOR, \
1670 KEY,EMPTY,DEL,COPY,DISPOSE,SAFE, \
1671 VCOMPARE,CCOMPARE,HASH, \
1672 VALUE,HASVNULL,VNULL) \
1673 \
1674 typedef struct \
1675 { \
1676 KEY k; \
1677 VALUE v; \
1678 } STB_(N,_hashpair); \
1679 \
1680 STB__nogcc( typedef struct stb__st_##TYPE TYPE; ) \
1681 struct stb__st_##TYPE { \
1682 FIELDS \
1683 STB_(N,_hashpair) *table; \
1684 unsigned int mask; \
1685 int count, limit; \
1686 int deleted; \
1687 \
1688 int delete_threshhold; \
1689 int grow_threshhold; \
1690 int shrink_threshhold; \
1691 unsigned char alloced, has_empty, has_del; \
1692 VALUE ev; VALUE dv; \
1693 }; \
1694 \
1695 static unsigned int STB_(N, hash)(KEY k) \
1696 { \
1697 HASH \
1698 } \
1699 \
1700 PREFIX int STB__(N, init)(TYPE *h, int count) \
1701 { \
1702 int i; \
1703 if (count < 4) count = 4; \
1704 h->limit = count; \
1705 h->count = 0; \
1706 h->mask = count-1; \
1707 h->deleted = 0; \
1708 h->grow_threshhold = (int) (count * LOAD_FACTOR); \
1709 h->has_empty = h->has_del = 0; \
1710 h->alloced = 0; \
1711 if (count <= 64) \
1712 h->shrink_threshhold = 0; \
1713 else \
1714 h->shrink_threshhold = (int) (count * (LOAD_FACTOR/2.25)); \
1715 h->delete_threshhold = (int) (count * (1-LOAD_FACTOR)/2); \
1716 h->table = (STB_(N,_hashpair)*) malloc(sizeof(h->table[0]) * count); \
1717 if (h->table == NULL) return 0; \
1718 /* ideally this gets turned into a memset32 automatically */ \
1719 for (i=0; i < count; ++i) \
1720 h->table[i].k = EMPTY; \
1721 return 1; \
1722 } \
1723 \
1724 PREFIX int STB__(N, memory_usage)(TYPE *h) \
1725 { \
1726 return sizeof(*h) + h->limit * sizeof(h->table[0]); \
1727 } \
1728 \
1729 PREFIX TYPE * STB__(N, create)(void) \
1730 { \
1731 TYPE *h = (TYPE *) malloc(sizeof(*h)); \
1732 if (h) { \
1733 if (STB__(N, init)(h, 16)) \
1734 h->alloced = 1; \
1735 else { free(h); h=NULL; } \
1736 } \
1737 return h; \
1738 } \
1739 \
1740 PREFIX void STB__(N, destroy)(TYPE *a) \
1741 { \
1742 int i; \
1743 for (i=0; i < a->limit; ++i) \
1744 if (!CCOMPARE(a->table[i].k,EMPTY) && !CCOMPARE(a->table[i].k, DEL)) \
1745 DISPOSE(a->table[i].k); \
1746 free(a->table); \
1747 if (a->alloced) \
1748 free(a); \
1749 } \
1750 \
1751 static void STB_(N, rehash)(TYPE *a, int count); \
1752 \
1753 PREFIX int STB__(N,get_flag)(TYPE *a, KEY k, VALUE *v) \
1754 { \
1755 unsigned int h = STB_(N, hash)(k); \
1756 unsigned int n = h & a->mask, s; \
1757 if (CCOMPARE(k,EMPTY)){ if (a->has_empty) *v = a->ev; return a->has_empty;}\
1758 if (CCOMPARE(k,DEL)) { if (a->has_del ) *v = a->dv; return a->has_del; }\
1759 if (CCOMPARE(a->table[n].k,EMPTY)) return 0; \
1760 SAFE(if (!CCOMPARE(a->table[n].k,DEL))) \
1761 if (VCOMPARE(a->table[n].k,k)) { *v = a->table[n].v; return 1; } \
1762 s = stb_rehash(h) | 1; \
1763 for(;;) { \
1764 n = (n + s) & a->mask; \
1765 if (CCOMPARE(a->table[n].k,EMPTY)) return 0; \
1766 SAFE(if (CCOMPARE(a->table[n].k,DEL)) continue;) \
1767 if (VCOMPARE(a->table[n].k,k)) \
1768 { *v = a->table[n].v; return 1; } \
1769 } \
1770 } \
1771 \
1772 HASVNULL( \
1773 PREFIX VALUE STB__(N,get)(TYPE *a, KEY k) \
1774 { \
1775 VALUE v; \
1776 if (STB__(N,get_flag)(a,k,&v)) return v; \
1777 else return VNULL; \
1778 } \
1779 ) \
1780 \
1781 PREFIX int STB__(N,getkey)(TYPE *a, KEY k, KEY *kout) \
1782 { \
1783 unsigned int h = STB_(N, hash)(k); \
1784 unsigned int n = h & a->mask, s; \
1785 if (CCOMPARE(k,EMPTY)||CCOMPARE(k,DEL)) return 0; \
1786 if (CCOMPARE(a->table[n].k,EMPTY)) return 0; \
1787 SAFE(if (!CCOMPARE(a->table[n].k,DEL))) \
1788 if (VCOMPARE(a->table[n].k,k)) { *kout = a->table[n].k; return 1; } \
1789 s = stb_rehash(h) | 1; \
1790 for(;;) { \
1791 n = (n + s) & a->mask; \
1792 if (CCOMPARE(a->table[n].k,EMPTY)) return 0; \
1793 SAFE(if (CCOMPARE(a->table[n].k,DEL)) continue;) \
1794 if (VCOMPARE(a->table[n].k,k)) \
1795 { *kout = a->table[n].k; return 1; } \
1796 } \
1797 } \
1798 \
1799 static int STB_(N,addset)(TYPE *a, KEY k, VALUE v, \
1800 int allow_new, int allow_old, int copy) \
1801 { \
1802 unsigned int h = STB_(N, hash)(k); \
1803 unsigned int n = h & a->mask; \
1804 int b = -1; \
1805 if (CCOMPARE(k,EMPTY)) { \
1806 if (a->has_empty ? allow_old : allow_new) { \
1807 n=a->has_empty; a->ev = v; a->has_empty = 1; return !n; \
1808 } else return 0; \
1809 } \
1810 if (CCOMPARE(k,DEL)) { \
1811 if (a->has_del ? allow_old : allow_new) { \
1812 n=a->has_del; a->dv = v; a->has_del = 1; return !n; \
1813 } else return 0; \
1814 } \
1815 if (!CCOMPARE(a->table[n].k, EMPTY)) { \
1816 unsigned int s; \
1817 if (CCOMPARE(a->table[n].k, DEL)) \
1818 b = n; \
1819 else if (VCOMPARE(a->table[n].k,k)) { \
1820 if (allow_old) \
1821 a->table[n].v = v; \
1822 return !allow_new; \
1823 } \
1824 s = stb_rehash(h) | 1; \
1825 for(;;) { \
1826 n = (n + s) & a->mask; \
1827 if (CCOMPARE(a->table[n].k, EMPTY)) break; \
1828 if (CCOMPARE(a->table[n].k, DEL)) { \
1829 if (b < 0) b = n; \
1830 } else if (VCOMPARE(a->table[n].k,k)) { \
1831 if (allow_old) \
1832 a->table[n].v = v; \
1833 return !allow_new; \
1834 } \
1835 } \
1836 } \
1837 if (!allow_new) return 0; \
1838 if (b < 0) b = n; else --a->deleted; \
1839 a->table[b].k = copy ? COPY(k) : k; \
1840 a->table[b].v = v; \
1841 ++a->count; \
1842 if (a->count > a->grow_threshhold) \
1843 STB_(N,rehash)(a, a->limit*2); \
1844 return 1; \
1845 } \
1846 \
1847 PREFIX int STB__(N, set)(TYPE *a, KEY k, VALUE v){return STB_(N,addset)(a,k,v,1,1,1);}\
1848 PREFIX int STB__(N, add)(TYPE *a, KEY k, VALUE v){return STB_(N,addset)(a,k,v,1,0,1);}\
1849 PREFIX int STB__(N, update)(TYPE*a,KEY k,VALUE v){return STB_(N,addset)(a,k,v,0,1,1);}\
1850 \
1851 PREFIX int STB__(N, remove)(TYPE *a, KEY k, VALUE *v) \
1852 { \
1853 unsigned int h = STB_(N, hash)(k); \
1854 unsigned int n = h & a->mask, s; \
1855 if (CCOMPARE(k,EMPTY)) { if (a->has_empty) { if(v)*v = a->ev; a->has_empty=0; return 1; } return 0; } \
1856 if (CCOMPARE(k,DEL)) { if (a->has_del ) { if(v)*v = a->dv; a->has_del =0; return 1; } return 0; } \
1857 if (CCOMPARE(a->table[n].k,EMPTY)) return 0; \
1858 if (SAFE(CCOMPARE(a->table[n].k,DEL) || ) !VCOMPARE(a->table[n].k,k)) { \
1859 s = stb_rehash(h) | 1; \
1860 for(;;) { \
1861 n = (n + s) & a->mask; \
1862 if (CCOMPARE(a->table[n].k,EMPTY)) return 0; \
1863 SAFE(if (CCOMPARE(a->table[n].k, DEL)) continue;) \
1864 if (VCOMPARE(a->table[n].k,k)) break; \
1865 } \
1866 } \
1867 DISPOSE(a->table[n].k); \
1868 a->table[n].k = DEL; \
1869 --a->count; \
1870 ++a->deleted; \
1871 if (v != NULL) \
1872 *v = a->table[n].v; \
1873 if (a->count < a->shrink_threshhold) \
1874 STB_(N, rehash)(a, a->limit >> 1); \
1875 else if (a->deleted > a->delete_threshhold) \
1876 STB_(N, rehash)(a, a->limit); \
1877 return 1; \
1878 } \
1879 \
1880 PREFIX TYPE * STB__(NC, copy)(TYPE *a) \
1881 { \
1882 int i; \
1883 TYPE *h = (TYPE *) malloc(sizeof(*h)); \
1884 if (!h) return NULL; \
1885 if (!STB__(N, init)(h, a->limit)) { free(h); return NULL; } \
1886 h->count = a->count; \
1887 h->deleted = a->deleted; \
1888 h->alloced = 1; \
1889 h->ev = a->ev; h->dv = a->dv; \
1890 h->has_empty = a->has_empty; h->has_del = a->has_del; \
1891 memcpy(h->table, a->table, h->limit * sizeof(h->table[0])); \
1892 for (i=0; i < a->limit; ++i) \
1893 if (!CCOMPARE(h->table[i].k,EMPTY) && !CCOMPARE(h->table[i].k,DEL)) \
1894 h->table[i].k = COPY(h->table[i].k); \
1895 return h; \
1896 } \
1897 \
1898 static void STB_(N, rehash)(TYPE *a, int count) \
1899 { \
1900 int i; \
1901 TYPE b; \
1902 STB__(N, init)(&b, count); \
1903 for (i=0; i < a->limit; ++i) \
1904 if (!CCOMPARE(a->table[i].k,EMPTY) && !CCOMPARE(a->table[i].k,DEL)) \
1905 STB_(N,addset)(&b, a->table[i].k, a->table[i].v,1,1,0); \
1906 free(a->table); \
1907 a->table = b.table; \
1908 a->mask = b.mask; \
1909 a->count = b.count; \
1910 a->limit = b.limit; \
1911 a->deleted = b.deleted; \
1912 a->delete_threshhold = b.delete_threshhold; \
1913 a->grow_threshhold = b.grow_threshhold; \
1914 a->shrink_threshhold = b.shrink_threshhold; \
1915 }
1916
1917 #define STB_equal(a,b) ((a) == (b))
1918
1919 #define stb_define_hash(TYPE,N,KEY,EMPTY,DEL,HASH,VALUE) \
1920 stb_define_hash_base(STB_noprefix, TYPE,STB_nofields,N,NC,0.85f, \
1921 KEY,EMPTY,DEL,STB_nocopy,STB_nodelete,STB_nosafe, \
1922 STB_equal,STB_equal,HASH, \
1923 VALUE,STB_nonullvalue,0)
1924
1925 #define stb_define_hash_vnull(TYPE,N,KEY,EMPTY,DEL,HASH,VALUE,VNULL) \
1926 stb_define_hash_base(STB_noprefix, TYPE,STB_nofields,N,NC,0.85f, \
1927 KEY,EMPTY,DEL,STB_nocopy,STB_nodelete,STB_nosafe, \
1928 STB_equal,STB_equal,HASH, \
1929 VALUE,STB_nullvalue,VNULL)
1930
1931 //////////////////////////////////////////////////////////////////////////////
1932 //
1933 // stb_ptrmap
1934 //
1935 // An stb_ptrmap data structure is an O(1) hash table between pointers. One
1936 // application is to let you store "extra" data associated with pointers,
1937 // which is why it was originally called stb_extra.
1938
1939 #ifndef STB_INCLUDE_STB_LIB_H
1940 stb_declare_hash(STB_EXTERN, stb_ptrmap, stb_ptrmap_, void *, void *)
1941 stb_declare_hash(STB_EXTERN, stb_idict, stb_idict_, stb_int32, stb_int32)
1942
1943 STB_EXTERN void stb_ptrmap_delete(stb_ptrmap *e, void (*free_func)(void *));
1944 STB_EXTERN stb_ptrmap *stb_ptrmap_new(void);
1945
1946 STB_EXTERN stb_idict * stb_idict_new_size(unsigned int size);
1947 STB_EXTERN void stb_idict_remove_all(stb_idict *e);
1948 #endif // STB_INCLUDE_STB_LIB_H
1949
1950 #ifdef STB_LIB_IMPLEMENTATION
1951
1952 #define STB_EMPTY ((void *) 2)
1953 #define STB_EDEL ((void *) 6)
1954
1955 stb_define_hash_base(STB_noprefix,stb_ptrmap, STB_nofields, stb_ptrmap_,stb_ptrmap_,0.85f,
1956 void *,STB_EMPTY,STB_EDEL,STB_nocopy,STB_nodelete,STB_nosafe,
1957 STB_equal,STB_equal,return stb_hashptr(k);,
1958 void *,STB_nullvalue,NULL)
1959
stb_ptrmap_new(void)1960 stb_ptrmap *stb_ptrmap_new(void)
1961 {
1962 return stb_ptrmap_create();
1963 }
1964
stb_ptrmap_delete(stb_ptrmap * e,void (* free_func)(void *))1965 void stb_ptrmap_delete(stb_ptrmap *e, void (*free_func)(void *))
1966 {
1967 int i;
1968 if (free_func)
1969 for (i=0; i < e->limit; ++i)
1970 if (e->table[i].k != STB_EMPTY && e->table[i].k != STB_EDEL) {
1971 if (free_func == free)
1972 free(e->table[i].v); // allow STB_MALLOC_WRAPPER to operate
1973 else
1974 free_func(e->table[i].v);
1975 }
1976 stb_ptrmap_destroy(e);
1977 }
1978
1979 // extra fields needed for stua_dict
1980 #define STB_IEMPTY ((int) 1)
1981 #define STB_IDEL ((int) 3)
1982 stb_define_hash_base(STB_noprefix, stb_idict, STB_nofields, stb_idict_,stb_idict_,0.85f,
1983 stb_int32,STB_IEMPTY,STB_IDEL,STB_nocopy,STB_nodelete,STB_nosafe,
1984 STB_equal,STB_equal,
1985 return stb_rehash_improved(k);,stb_int32,STB_nonullvalue,0)
1986
stb_idict_new_size(unsigned int size)1987 stb_idict * stb_idict_new_size(unsigned int size)
1988 {
1989 stb_idict *e = (stb_idict *) malloc(sizeof(*e));
1990 if (e) {
1991 // round up to power of 2
1992 while ((size & (size-1)) != 0) // while more than 1 bit is set
1993 size += (size & ~(size-1)); // add the lowest set bit
1994 stb_idict_init(e, size);
1995 e->alloced = 1;
1996 }
1997 return e;
1998 }
1999
stb_idict_remove_all(stb_idict * e)2000 void stb_idict_remove_all(stb_idict *e)
2001 {
2002 int n;
2003 for (n=0; n < e->limit; ++n)
2004 e->table[n].k = STB_IEMPTY;
2005 e->has_empty = e->has_del = 0;
2006 }
2007 #endif
2008
2009 //////////////////////////////////////////////////////////////////////////////
2010 //
2011 // SDICT: Hash Table for Strings (symbol table)
2012 //
2013 // if "use_arena=1", then strings will be copied
2014 // into blocks and never freed until the sdict is freed;
2015 // otherwise they're malloc()ed and free()d on the fly.
2016 // (specify use_arena=1 if you never stb_sdict_remove)
2017
2018 #ifndef STB_INCLUDE_STB_LIB_H
2019 stb_declare_hash(STB_EXTERN, stb_sdict, stb_sdict_, char *, void *)
2020
2021 STB_EXTERN stb_sdict * stb_sdict_new(void);
2022 STB_EXTERN stb_sdict * stb_sdict_copy(stb_sdict*);
2023 STB_EXTERN void stb_sdict_delete(stb_sdict *);
2024 STB_EXTERN void * stb_sdict_change(stb_sdict *, char *str, void *p);
2025 STB_EXTERN int stb_sdict_count(stb_sdict *d);
2026
2027 STB_EXTERN int stb_sdict_internal_limit(stb_sdict *d);
2028 STB_EXTERN char * stb_sdict_internal_key(stb_sdict *d, int n);
2029 STB_EXTERN void * stb_sdict_internal_value(stb_sdict *d, int n);
2030
2031 #define stb_sdict_for(d,i,q,z) \
2032 for(i=0; i < stb_sdict_internal_limit(d) ? (q=stb_sdict_internal_key(d,i),z=stb_sdict_internal_value(d,i),1) : 0; ++i) \
2033 if (q==NULL||q==(void *) 1);else // reversed makes macro friendly
2034 #endif // STB_INCLUDE_STB_LIB_H
2035
2036 #ifdef STB_LIB_IMPLEMENTATION
2037
2038 // if in same translation unit, for speed, don't call accessors
2039 #undef stb_sdict_for
2040 #define stb_sdict_for(d,i,q,z) \
2041 for(i=0; i < (d)->limit ? (q=(d)->table[i].k,z=(d)->table[i].v,1) : 0; ++i) \
2042 if (q==NULL||q==(void *) 1);else // reversed makes macro friendly
2043
2044 //#define STB_DEL ((void *) 1)
2045 #define STB_SDEL ((char *) 1)
2046
2047 stb_define_hash_base(STB_noprefix, stb_sdict, STB_nofields, stb_sdict_,stb_sdictinternal_, 0.85f,
2048 char *, NULL, STB_SDEL, strdup, free,
2049 STB_safecompare, !strcmp, STB_equal, return stb_hash(k);,
2050 void *, STB_nullvalue, NULL)
2051
stb_sdict_count(stb_sdict * a)2052 int stb_sdict_count(stb_sdict *a)
2053 {
2054 return a->count;
2055 }
2056
stb_sdict_internal_limit(stb_sdict * a)2057 int stb_sdict_internal_limit(stb_sdict *a)
2058 {
2059 return a->limit;
2060 }
stb_sdict_internal_key(stb_sdict * a,int n)2061 char* stb_sdict_internal_key(stb_sdict *a, int n)
2062 {
2063 return a->table[n].k;
2064 }
stb_sdict_internal_value(stb_sdict * a,int n)2065 void* stb_sdict_internal_value(stb_sdict *a, int n)
2066 {
2067 return a->table[n].v;
2068 }
2069
stb_sdict_new(void)2070 stb_sdict * stb_sdict_new(void)
2071 {
2072 stb_sdict *d = stb_sdict_create();
2073 if (d == NULL) return NULL;
2074 return d;
2075 }
2076
stb_sdict_copy(stb_sdict * old)2077 stb_sdict* stb_sdict_copy(stb_sdict *old)
2078 {
2079 return stb_sdictinternal_copy(old);
2080 }
2081
stb_sdict_delete(stb_sdict * d)2082 void stb_sdict_delete(stb_sdict *d)
2083 {
2084 stb_sdict_destroy(d);
2085 }
2086
stb_sdict_change(stb_sdict * d,char * str,void * p)2087 void * stb_sdict_change(stb_sdict *d, char *str, void *p)
2088 {
2089 void *q = stb_sdict_get(d, str);
2090 stb_sdict_set(d, str, p);
2091 return q;
2092 }
2093 #endif
2094
2095 //////////////////////////////////////////////////////////////////////////////
2096 //
2097 // File Processing
2098 //
2099
2100 #ifndef STB_INCLUDE_STB_LIB_H
2101 #ifdef _MSC_VER
2102 #define stb_rename(x,y) _wrename((const wchar_t *)stb__from_utf8(x), (const wchar_t *)stb__from_utf8_alt(y))
2103 #define stb_mktemp _mktemp
2104 #else
2105 #define stb_mktemp mktemp
2106 #define stb_rename rename
2107 #endif
2108
2109 #define stb_filec (char *) stb_file
2110 #define stb_fileu (unsigned char *) stb_file
2111 STB_EXTERN void * stb_file(char *filename, size_t *length);
2112 STB_EXTERN size_t stb_filelen(FILE *f);
2113 STB_EXTERN int stb_filewrite(char *filename, void *data, size_t length);
2114 STB_EXTERN int stb_filewritestr(char *filename, char *data);
2115 STB_EXTERN char ** stb_stringfile(char *filename, int *len);
2116 STB_EXTERN char * stb_fgets(char *buffer, int buflen, FILE *f);
2117 STB_EXTERN char * stb_fgets_malloc(FILE *f);
2118 STB_EXTERN int stb_fexists(char *filename);
2119 STB_EXTERN int stb_fcmp(char *s1, char *s2);
2120 STB_EXTERN int stb_feq(char *s1, char *s2);
2121 STB_EXTERN time_t stb_ftimestamp(char *filename);
2122 STB_EXTERN int stb_fullpath(char *abs, int abs_size, char *rel);
2123
2124 STB_EXTERN int stb_copyfile(char *src, char *dest);
2125 STB_EXTERN int stb_fread(void *data, size_t len, size_t count, void *f);
2126 STB_EXTERN int stb_fwrite(void *data, size_t len, size_t count, void *f);
2127 #endif // STB_INCLUDE_STB_LIB_H
2128
2129 #ifdef STB_LIB_IMPLEMENTATION
2130 #if defined(_MSC_VER) || defined(__MINGW32__)
2131 #define stb__stat _stat
2132 #else
2133 #define stb__stat stat
2134 #endif
2135
stb_fexists(char * filename)2136 int stb_fexists(char *filename)
2137 {
2138 struct stb__stat buf;
2139 return stb__windows(
2140 _wstat((const wchar_t *)stb__from_utf8(filename), &buf),
2141 stat(filename,&buf)
2142 ) == 0;
2143 }
2144
stb_ftimestamp(char * filename)2145 time_t stb_ftimestamp(char *filename)
2146 {
2147 struct stb__stat buf;
2148 if (stb__windows(
2149 _wstat((const wchar_t *)stb__from_utf8(filename), &buf),
2150 stat(filename,&buf)
2151 ) == 0)
2152 {
2153 return buf.st_mtime;
2154 } else {
2155 return 0;
2156 }
2157 }
2158
stb_filelen(FILE * f)2159 size_t stb_filelen(FILE *f)
2160 {
2161 size_t len, pos;
2162 pos = ftell(f);
2163 fseek(f, 0, SEEK_END);
2164 len = ftell(f);
2165 fseek(f, pos, SEEK_SET);
2166 return len;
2167 }
2168
stb_file(char * filename,size_t * length)2169 void *stb_file(char *filename, size_t *length)
2170 {
2171 FILE *f = stb__fopen(filename, "rb");
2172 char *buffer;
2173 size_t len, len2;
2174 if (!f) return NULL;
2175 len = stb_filelen(f);
2176 buffer = (char *) malloc(len+2); // nul + extra
2177 len2 = fread(buffer, 1, len, f);
2178 if (len2 == len) {
2179 if (length) *length = len;
2180 buffer[len] = 0;
2181 } else {
2182 free(buffer);
2183 buffer = NULL;
2184 }
2185 fclose(f);
2186 return buffer;
2187 }
2188
stb_filewrite(char * filename,void * data,size_t length)2189 int stb_filewrite(char *filename, void *data, size_t length)
2190 {
2191 FILE *f = stb__fopen(filename, "wb");
2192 if (f) {
2193 unsigned char *data_ptr = (unsigned char *) data;
2194 size_t remaining = length;
2195 while (remaining > 0) {
2196 size_t len2 = remaining > 65536 ? 65536 : remaining;
2197 size_t len3 = fwrite(data_ptr, 1, len2, f);
2198 if (len2 != len3) {
2199 fprintf(stderr, "Failed while writing %s\n", filename);
2200 break;
2201 }
2202 remaining -= len2;
2203 data_ptr += len2;
2204 }
2205 fclose(f);
2206 }
2207 return f != NULL;
2208 }
2209
stb_filewritestr(char * filename,char * data)2210 int stb_filewritestr(char *filename, char *data)
2211 {
2212 return stb_filewrite(filename, data, strlen(data));
2213 }
2214
stb_stringfile(char * filename,int * plen)2215 char ** stb_stringfile(char *filename, int *plen)
2216 {
2217 FILE *f = stb__fopen(filename, "rb");
2218 char *buffer, **list=NULL, *s;
2219 size_t len, count, i;
2220
2221 if (!f) return NULL;
2222 len = stb_filelen(f);
2223 buffer = (char *) malloc(len+1);
2224 len = fread(buffer, 1, len, f);
2225 buffer[len] = 0;
2226 fclose(f);
2227
2228 // two passes through: first time count lines, second time set them
2229 for (i=0; i < 2; ++i) {
2230 s = buffer;
2231 if (i == 1)
2232 list[0] = s;
2233 count = 1;
2234 while (*s) {
2235 if (*s == '\n' || *s == '\r') {
2236 // detect if both cr & lf are together
2237 int crlf = (s[0] + s[1]) == ('\n' + '\r');
2238 if (i == 1) *s = 0;
2239 if (crlf) ++s;
2240 if (s[1]) { // it's not over yet
2241 if (i == 1) list[count] = s+1;
2242 ++count;
2243 }
2244 }
2245 ++s;
2246 }
2247 if (i == 0) {
2248 list = (char **) malloc(sizeof(*list) * (count+1) + len+1);
2249 if (!list) return NULL;
2250 list[count] = 0;
2251 // recopy the file so there's just a single allocation to free
2252 memcpy(&list[count+1], buffer, len+1);
2253 free(buffer);
2254 buffer = (char *) &list[count+1];
2255 if (plen) *plen = count;
2256 }
2257 }
2258 return list;
2259 }
2260
stb_fgets(char * buffer,int buflen,FILE * f)2261 char * stb_fgets(char *buffer, int buflen, FILE *f)
2262 {
2263 char *p;
2264 buffer[0] = 0;
2265 p = fgets(buffer, buflen, f);
2266 if (p) {
2267 int n = strlen(p)-1;
2268 if (n >= 0)
2269 if (p[n] == '\n')
2270 p[n] = 0;
2271 }
2272 return p;
2273 }
2274
stb_fgets_malloc(FILE * f)2275 char * stb_fgets_malloc(FILE *f)
2276 {
2277 // avoid reallocing for small strings
2278 char quick_buffer[800];
2279 quick_buffer[sizeof(quick_buffer)-2] = 0;
2280 if (!fgets(quick_buffer, sizeof(quick_buffer), f))
2281 return NULL;
2282
2283 if (quick_buffer[sizeof(quick_buffer)-2] == 0) {
2284 int n = strlen(quick_buffer);
2285 if (n > 0 && quick_buffer[n-1] == '\n')
2286 quick_buffer[n-1] = 0;
2287 return strdup(quick_buffer);
2288 } else {
2289 char *p;
2290 char *a = strdup(quick_buffer);
2291 int len = sizeof(quick_buffer)-1;
2292
2293 while (!feof(f)) {
2294 if (a[len-1] == '\n') break;
2295 a = (char *) realloc(a, len*2);
2296 p = &a[len];
2297 p[len-2] = 0;
2298 if (!fgets(p, len, f))
2299 break;
2300 if (p[len-2] == 0) {
2301 len += strlen(p);
2302 break;
2303 }
2304 len = len + (len-1);
2305 }
2306 if (a[len-1] == '\n')
2307 a[len-1] = 0;
2308 return a;
2309 }
2310 }
2311
stb_fullpath(char * abs,int abs_size,char * rel)2312 int stb_fullpath(char *abs, int abs_size, char *rel)
2313 {
2314 #ifdef _MSC_VER
2315 return _fullpath(abs, rel, abs_size) != NULL;
2316 #else
2317 if (rel[0] == '/' || rel[0] == '~') {
2318 if ((int) strlen(rel) >= abs_size)
2319 return 0;
2320 strcpy(abs,rel);
2321 return 1;
2322 } else {
2323 int n;
2324 getcwd(abs, abs_size);
2325 n = strlen(abs);
2326 if (n+(int) strlen(rel)+2 <= abs_size) {
2327 abs[n] = '/';
2328 strcpy(abs+n+1, rel);
2329 return 1;
2330 } else {
2331 return 0;
2332 }
2333 }
2334 #endif
2335 }
2336
stb_fcmp_core(FILE * f,FILE * g)2337 static int stb_fcmp_core(FILE *f, FILE *g)
2338 {
2339 char buf1[1024],buf2[1024];
2340 int n1,n2, res=0;
2341
2342 while (1) {
2343 n1 = fread(buf1, 1, sizeof(buf1), f);
2344 n2 = fread(buf2, 1, sizeof(buf2), g);
2345 res = memcmp(buf1,buf2,n1 < n2 ? n1 : n2);
2346 if (res)
2347 break;
2348 if (n1 != n2) {
2349 res = n1 < n2 ? -1 : 1;
2350 break;
2351 }
2352 if (n1 == 0)
2353 break;
2354 }
2355
2356 fclose(f);
2357 fclose(g);
2358 return res;
2359 }
2360
stb_fcmp(char * s1,char * s2)2361 int stb_fcmp(char *s1, char *s2)
2362 {
2363 FILE *f = stb__fopen(s1, "rb");
2364 FILE *g = stb__fopen(s2, "rb");
2365
2366 if (f == NULL || g == NULL) {
2367 if (f) fclose(f);
2368 if (g) {
2369 fclose(g);
2370 return 1;
2371 }
2372 return f != NULL;
2373 }
2374
2375 return stb_fcmp_core(f,g);
2376 }
2377
stb_feq(char * s1,char * s2)2378 int stb_feq(char *s1, char *s2)
2379 {
2380 FILE *f = stb__fopen(s1, "rb");
2381 FILE *g = stb__fopen(s2, "rb");
2382
2383 if (f == NULL || g == NULL) {
2384 if (f) fclose(f);
2385 if (g) fclose(g);
2386 return f == g;
2387 }
2388
2389 // feq is faster because it shortcuts if they're different length
2390 if (stb_filelen(f) != stb_filelen(g)) {
2391 fclose(f);
2392 fclose(g);
2393 return 0;
2394 }
2395
2396 return !stb_fcmp_core(f,g);
2397 }
2398
stb_copyfile(char * src,char * dest)2399 int stb_copyfile(char *src, char *dest)
2400 {
2401 char raw_buffer[1024];
2402 char *buffer;
2403 int buf_size = 65536;
2404
2405 FILE *f, *g;
2406
2407 // if file already exists at destination, do nothing
2408 if (stb_feq(src, dest)) return 1;
2409
2410 // open file
2411 f = stb__fopen(src, "rb");
2412 if (f == NULL) return 0;
2413
2414 // open file for writing
2415 g = stb__fopen(dest, "wb");
2416 if (g == NULL) {
2417 fclose(f);
2418 return 0;
2419 }
2420
2421 buffer = (char *) malloc(buf_size);
2422 if (buffer == NULL) {
2423 buffer = raw_buffer;
2424 buf_size = sizeof(raw_buffer);
2425 }
2426
2427 while (!feof(f)) {
2428 int n = fread(buffer, 1, buf_size, f);
2429 if (n != 0)
2430 fwrite(buffer, 1, n, g);
2431 }
2432
2433 fclose(f);
2434 if (buffer != raw_buffer)
2435 free(buffer);
2436
2437 fclose(g);
2438 return 1;
2439 }
2440
2441 #define stb_fgetc(f) ((unsigned char) fgetc(f))
2442
2443 #if 0
2444 // strip the trailing '/' or '\\' from a directory so we can refer to it
2445 // as a file for _stat()
2446 char *stb_strip_final_slash(char *t)
2447 {
2448 if (t[0]) {
2449 char *z = t + strlen(t) - 1;
2450 // *z is the last character
2451 if (*z == '\\' || *z == '/')
2452 if (z != t+2 || t[1] != ':') // but don't strip it if it's e.g. "c:/"
2453 *z = 0;
2454 if (*z == '\\')
2455 *z = '/'; // canonicalize to make sure it matches db
2456 }
2457 return t;
2458 }
2459
2460 char *stb_strip_final_slash_regardless(char *t)
2461 {
2462 if (t[0]) {
2463 char *z = t + strlen(t) - 1;
2464 // *z is the last character
2465 if (*z == '\\' || *z == '/')
2466 *z = 0;
2467 if (*z == '\\')
2468 *z = '/'; // canonicalize to make sure it matches db
2469 }
2470 return t;
2471 }
2472 #endif
2473 #endif
2474
2475 //////////////////////////////////////////////////////////////////////////////
2476 //
2477 // Portable directory reading
2478 //
2479
2480 #ifndef STB_INCLUDE_STB_LIB_H
2481 STB_EXTERN char **stb_readdir_files (char *dir);
2482 STB_EXTERN char **stb_readdir_files_mask(char *dir, char *wild);
2483 STB_EXTERN char **stb_readdir_subdirs(char *dir);
2484 STB_EXTERN char **stb_readdir_subdirs_mask(char *dir, char *wild);
2485 STB_EXTERN void stb_readdir_free (char **files);
2486 STB_EXTERN char **stb_readdir_recursive(char *dir, char *filespec);
2487 STB_EXTERN void stb_delete_directory_recursive(char *dir);
2488
2489 // forward declare for implementation
2490 STB_EXTERN int stb_wildmatchi(char *expr, char *candidate);
2491 #endif // STB_INCLUDE_STB_LIB_H
2492
2493
2494 #ifdef STB_LIB_IMPLEMENTATION
2495
2496 #ifdef _MSC_VER
2497 #include <io.h>
2498 #else
2499 #include <unistd.h>
2500 #include <dirent.h>
2501 #endif
2502
stb_readdir_free(char ** files)2503 void stb_readdir_free(char **files)
2504 {
2505 char **f2 = files;
2506 int i;
2507 for (i=0; i < stb_arr_len(f2); ++i)
2508 free(f2[i]);
2509 stb_arr_free(f2);
2510 }
2511
isdotdirname(char * name)2512 static int isdotdirname(char *name)
2513 {
2514 if (name[0] == '.')
2515 return (name[1] == '.') ? !name[2] : !name[1];
2516 return 0;
2517 }
2518
readdir_raw(char * dir,int return_subdirs,char * mask)2519 static char **readdir_raw(char *dir, int return_subdirs, char *mask)
2520 {
2521 char **results = NULL;
2522 char buffer[4096], with_slash[4096];
2523 size_t n;
2524
2525 #ifdef _MSC_VER
2526 stb__wchar *ws;
2527 struct _wfinddata_t data;
2528 #ifdef _WIN64
2529 const intptr_t none = -1;
2530 intptr_t z;
2531 #else
2532 const long none = -1;
2533 long z;
2534 #endif
2535 #else // !_MSC_VER
2536 const DIR *none = NULL;
2537 DIR *z;
2538 #endif
2539
2540 n = stb_strscpy(buffer,dir,sizeof(buffer));
2541 if (!n || n >= sizeof(buffer))
2542 return NULL;
2543 stb_fixpath(buffer);
2544 n--;
2545
2546 if (n > 0 && (buffer[n-1] != '/')) {
2547 buffer[n++] = '/';
2548 }
2549 buffer[n] = 0;
2550 if (!stb_strscpy(with_slash,buffer,sizeof(with_slash)))
2551 return NULL;
2552
2553 #ifdef _MSC_VER
2554 if (!stb_strscpy(buffer+n,"*.*",sizeof(buffer)-n))
2555 return NULL;
2556 ws = stb__from_utf8(buffer);
2557 z = _wfindfirst((const wchar_t *)ws, &data);
2558 #else
2559 z = opendir(dir);
2560 #endif
2561
2562 if (z != none) {
2563 int nonempty = 1;
2564 #ifndef _MSC_VER
2565 struct dirent *data = readdir(z);
2566 nonempty = (data != NULL);
2567 #endif
2568
2569 if (nonempty) {
2570
2571 do {
2572 int is_subdir;
2573 #ifdef _MSC_VER
2574 char *name = stb__to_utf8((stb__wchar *)data.name);
2575 if (name == NULL) {
2576 fprintf(stderr, "%s to convert '%S' to %s!\n", "Unable", data.name, "utf8");
2577 continue;
2578 }
2579 is_subdir = !!(data.attrib & _A_SUBDIR);
2580 #else
2581 char *name = data->d_name;
2582 if (!stb_strscpy(buffer+n,name,sizeof(buffer)-n))
2583 break;
2584 // Could follow DT_LNK, but would need to check for recursive links.
2585 is_subdir = !!(data->d_type & DT_DIR);
2586 #endif
2587
2588 if (is_subdir == return_subdirs) {
2589 if (!is_subdir || !isdotdirname(name)) {
2590 if (!mask || stb_wildmatchi(mask, name)) {
2591 char buffer[4096],*p=buffer;
2592 if ( stb_snprintf(buffer, sizeof(buffer), "%s%s", with_slash, name) < 0 )
2593 break;
2594 if (buffer[0] == '.' && buffer[1] == '/')
2595 p = buffer+2;
2596 stb_arr_push(results, strdup(p));
2597 }
2598 }
2599 }
2600 }
2601 #ifdef _MSC_VER
2602 while (0 == _wfindnext(z, &data));
2603 #else
2604 while ((data = readdir(z)) != NULL);
2605 #endif
2606 }
2607 #ifdef _MSC_VER
2608 _findclose(z);
2609 #else
2610 closedir(z);
2611 #endif
2612 }
2613 return results;
2614 }
2615
stb_readdir_files(char * dir)2616 char **stb_readdir_files (char *dir) { return readdir_raw(dir, 0, NULL); }
stb_readdir_subdirs(char * dir)2617 char **stb_readdir_subdirs(char *dir) { return readdir_raw(dir, 1, NULL); }
stb_readdir_files_mask(char * dir,char * wild)2618 char **stb_readdir_files_mask(char *dir, char *wild) { return readdir_raw(dir, 0, wild); }
stb_readdir_subdirs_mask(char * dir,char * wild)2619 char **stb_readdir_subdirs_mask(char *dir, char *wild) { return readdir_raw(dir, 1, wild); }
2620
2621 int stb__rec_max=0x7fffffff;
stb_readdir_rec(char ** sofar,char * dir,char * filespec)2622 static char **stb_readdir_rec(char **sofar, char *dir, char *filespec)
2623 {
2624 char **files;
2625 char ** dirs;
2626 char **p;
2627
2628 if (stb_arr_len(sofar) >= stb__rec_max) return sofar;
2629
2630 files = stb_readdir_files_mask(dir, filespec);
2631 stb_arr_for(p, files) {
2632 stb_arr_push(sofar, strdup(*p));
2633 if (stb_arr_len(sofar) >= stb__rec_max) break;
2634 }
2635 stb_readdir_free(files);
2636 if (stb_arr_len(sofar) >= stb__rec_max) return sofar;
2637
2638 dirs = stb_readdir_subdirs(dir);
2639 stb_arr_for(p, dirs)
2640 sofar = stb_readdir_rec(sofar, *p, filespec);
2641 stb_readdir_free(dirs);
2642 return sofar;
2643 }
2644
stb_readdir_recursive(char * dir,char * filespec)2645 char **stb_readdir_recursive(char *dir, char *filespec)
2646 {
2647 return stb_readdir_rec(NULL, dir, filespec);
2648 }
2649
stb_delete_directory_recursive(char * dir)2650 void stb_delete_directory_recursive(char *dir)
2651 {
2652 char **list = stb_readdir_subdirs(dir);
2653 int i;
2654 for (i=0; i < stb_arr_len(list); ++i)
2655 stb_delete_directory_recursive(list[i]);
2656 stb_arr_free(list);
2657 list = stb_readdir_files(dir);
2658 for (i=0; i < stb_arr_len(list); ++i)
2659 if (!remove(list[i])) {
2660 // on windows, try again after making it writeable; don't ALWAYS
2661 // do this first since that would be slow in the normal case
2662 #ifdef _MSC_VER
2663 _chmod(list[i], _S_IWRITE);
2664 remove(list[i]);
2665 #endif
2666 }
2667 stb_arr_free(list);
2668 stb__windows(_rmdir,rmdir)(dir);
2669 }
2670 #endif
2671
2672 //////////////////////////////////////////////////////////////////////////////
2673 //
2674 // Checksums: CRC-32, ADLER32, SHA-1
2675 //
2676 // CRC-32 and ADLER32 allow streaming blocks
2677 // SHA-1 requires either a complete buffer, max size 2^32 - 73
2678 // or it can checksum directly from a file, max 2^61
2679
2680 #ifndef STB_INCLUDE_STB_LIB_H
2681 #define STB_ADLER32_SEED 1
2682 #define STB_CRC32_SEED 0 // note that we logical NOT this in the code
2683
2684 STB_EXTERN stb_uint stb_adler32 (stb_uint adler32, stb_uchar *buffer, stb_uint buflen);
2685 STB_EXTERN stb_uint stb_crc32_block(stb_uint crc32 , stb_uchar *buffer, stb_uint buflen);
2686 STB_EXTERN stb_uint stb_crc32 ( stb_uchar *buffer, stb_uint buflen);
2687
2688 STB_EXTERN void stb_sha1( unsigned char output[20], stb_uchar *buffer, unsigned int len);
2689 STB_EXTERN int stb_sha1_file(unsigned char output[20], char *file);
2690 #endif // STB_INCLUDE_STB_LIB_H
2691
2692 #ifdef STB_LIB_IMPLEMENTATION
stb_crc32_block(stb_uint crc,unsigned char * buffer,stb_uint len)2693 stb_uint stb_crc32_block(stb_uint crc, unsigned char *buffer, stb_uint len)
2694 {
2695 static stb_uint crc_table[256];
2696 stb_uint i,j,s;
2697 crc = ~crc;
2698
2699 if (crc_table[1] == 0)
2700 for(i=0; i < 256; i++) {
2701 for (s=i, j=0; j < 8; ++j)
2702 s = (s >> 1) ^ (s & 1 ? 0xedb88320 : 0);
2703 crc_table[i] = s;
2704 }
2705 for (i=0; i < len; ++i)
2706 crc = (crc >> 8) ^ crc_table[buffer[i] ^ (crc & 0xff)];
2707 return ~crc;
2708 }
2709
stb_crc32(unsigned char * buffer,stb_uint len)2710 stb_uint stb_crc32(unsigned char *buffer, stb_uint len)
2711 {
2712 return stb_crc32_block(0, buffer, len);
2713 }
2714
stb_adler32(stb_uint adler32,stb_uchar * buffer,stb_uint buflen)2715 stb_uint stb_adler32(stb_uint adler32, stb_uchar *buffer, stb_uint buflen)
2716 {
2717 const unsigned long ADLER_MOD = 65521;
2718 unsigned long s1 = adler32 & 0xffff, s2 = adler32 >> 16;
2719 unsigned long blocklen, i;
2720
2721 blocklen = buflen % 5552;
2722 while (buflen) {
2723 for (i=0; i + 7 < blocklen; i += 8) {
2724 s1 += buffer[0], s2 += s1;
2725 s1 += buffer[1], s2 += s1;
2726 s1 += buffer[2], s2 += s1;
2727 s1 += buffer[3], s2 += s1;
2728 s1 += buffer[4], s2 += s1;
2729 s1 += buffer[5], s2 += s1;
2730 s1 += buffer[6], s2 += s1;
2731 s1 += buffer[7], s2 += s1;
2732
2733 buffer += 8;
2734 }
2735
2736 for (; i < blocklen; ++i)
2737 s1 += *buffer++, s2 += s1;
2738
2739 s1 %= ADLER_MOD, s2 %= ADLER_MOD;
2740 buflen -= blocklen;
2741 blocklen = 5552;
2742 }
2743 return (s2 << 16) + s1;
2744 }
2745
2746 #define stb__big32(c) (((c)[0]<<24) + (c)[1]*65536 + (c)[2]*256 + (c)[3])
stb__sha1(stb_uchar * chunk,stb_uint h[5])2747 static void stb__sha1(stb_uchar *chunk, stb_uint h[5])
2748 {
2749 int i;
2750 stb_uint a,b,c,d,e;
2751 stb_uint w[80];
2752
2753 for (i=0; i < 16; ++i)
2754 w[i] = stb__big32(&chunk[i*4]);
2755 for (i=16; i < 80; ++i) {
2756 stb_uint t;
2757 t = w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16];
2758 w[i] = (t + t) | (t >> 31);
2759 }
2760
2761 a = h[0];
2762 b = h[1];
2763 c = h[2];
2764 d = h[3];
2765 e = h[4];
2766
2767 #define STB__SHA1(k,f) \
2768 { \
2769 stb_uint temp = (a << 5) + (a >> 27) + (f) + e + (k) + w[i]; \
2770 e = d; \
2771 d = c; \
2772 c = (b << 30) + (b >> 2); \
2773 b = a; \
2774 a = temp; \
2775 }
2776
2777 i=0;
2778 for (; i < 20; ++i) STB__SHA1(0x5a827999, d ^ (b & (c ^ d)) );
2779 for (; i < 40; ++i) STB__SHA1(0x6ed9eba1, b ^ c ^ d );
2780 for (; i < 60; ++i) STB__SHA1(0x8f1bbcdc, (b & c) + (d & (b ^ c)) );
2781 for (; i < 80; ++i) STB__SHA1(0xca62c1d6, b ^ c ^ d );
2782
2783 #undef STB__SHA1
2784
2785 h[0] += a;
2786 h[1] += b;
2787 h[2] += c;
2788 h[3] += d;
2789 h[4] += e;
2790 }
2791
stb_sha1(stb_uchar output[20],stb_uchar * buffer,stb_uint len)2792 void stb_sha1(stb_uchar output[20], stb_uchar *buffer, stb_uint len)
2793 {
2794 unsigned char final_block[128];
2795 stb_uint end_start, final_len, j;
2796 int i;
2797
2798 stb_uint h[5];
2799
2800 h[0] = 0x67452301;
2801 h[1] = 0xefcdab89;
2802 h[2] = 0x98badcfe;
2803 h[3] = 0x10325476;
2804 h[4] = 0xc3d2e1f0;
2805
2806 // we need to write padding to the last one or two
2807 // blocks, so build those first into 'final_block'
2808
2809 // we have to write one special byte, plus the 8-byte length
2810
2811 // compute the block where the data runs out
2812 end_start = len & ~63;
2813
2814 // compute the earliest we can encode the length
2815 if (((len+9) & ~63) == end_start) {
2816 // it all fits in one block, so fill a second-to-last block
2817 end_start -= 64;
2818 }
2819
2820 final_len = end_start + 128;
2821
2822 // now we need to copy the data in
2823 assert(end_start + 128 >= len+9);
2824 assert(end_start < len || len < 64-9);
2825
2826 j = 0;
2827 if (end_start > len)
2828 j = (stb_uint) - (int) end_start;
2829
2830 for (; end_start + j < len; ++j)
2831 final_block[j] = buffer[end_start + j];
2832 final_block[j++] = 0x80;
2833 while (j < 128-5) // 5 byte length, so write 4 extra padding bytes
2834 final_block[j++] = 0;
2835 // big-endian size
2836 final_block[j++] = len >> 29;
2837 final_block[j++] = len >> 21;
2838 final_block[j++] = len >> 13;
2839 final_block[j++] = len >> 5;
2840 final_block[j++] = len << 3;
2841 assert(j == 128 && end_start + j == final_len);
2842
2843 for (j=0; j < final_len; j += 64) { // 512-bit chunks
2844 if (j+64 >= end_start+64)
2845 stb__sha1(&final_block[j - end_start], h);
2846 else
2847 stb__sha1(&buffer[j], h);
2848 }
2849
2850 for (i=0; i < 5; ++i) {
2851 output[i*4 + 0] = h[i] >> 24;
2852 output[i*4 + 1] = h[i] >> 16;
2853 output[i*4 + 2] = h[i] >> 8;
2854 output[i*4 + 3] = h[i] >> 0;
2855 }
2856 }
2857
stb_sha1_file(stb_uchar output[20],char * file)2858 int stb_sha1_file(stb_uchar output[20], char *file)
2859 {
2860 int i;
2861 stb_uint64 length=0;
2862 unsigned char buffer[128];
2863
2864 FILE *f = stb__fopen(file, "rb");
2865 stb_uint h[5];
2866
2867 if (f == NULL) return 0; // file not found
2868
2869 h[0] = 0x67452301;
2870 h[1] = 0xefcdab89;
2871 h[2] = 0x98badcfe;
2872 h[3] = 0x10325476;
2873 h[4] = 0xc3d2e1f0;
2874
2875 for(;;) {
2876 int n = fread(buffer, 1, 64, f);
2877 if (n == 64) {
2878 stb__sha1(buffer, h);
2879 length += n;
2880 } else {
2881 int block = 64;
2882
2883 length += n;
2884
2885 buffer[n++] = 0x80;
2886
2887 // if there isn't enough room for the length, double the block
2888 if (n + 8 > 64)
2889 block = 128;
2890
2891 // pad to end
2892 memset(buffer+n, 0, block-8-n);
2893
2894 i = block - 8;
2895 buffer[i++] = (stb_uchar) (length >> 53);
2896 buffer[i++] = (stb_uchar) (length >> 45);
2897 buffer[i++] = (stb_uchar) (length >> 37);
2898 buffer[i++] = (stb_uchar) (length >> 29);
2899 buffer[i++] = (stb_uchar) (length >> 21);
2900 buffer[i++] = (stb_uchar) (length >> 13);
2901 buffer[i++] = (stb_uchar) (length >> 5);
2902 buffer[i++] = (stb_uchar) (length << 3);
2903 assert(i == block);
2904 stb__sha1(buffer, h);
2905 if (block == 128)
2906 stb__sha1(buffer+64, h);
2907 else
2908 assert(block == 64);
2909 break;
2910 }
2911 }
2912 fclose(f);
2913
2914 for (i=0; i < 5; ++i) {
2915 output[i*4 + 0] = h[i] >> 24;
2916 output[i*4 + 1] = h[i] >> 16;
2917 output[i*4 + 2] = h[i] >> 8;
2918 output[i*4 + 3] = h[i] >> 0;
2919 }
2920
2921 return 1;
2922 }
2923 #endif // STB_LIB_IMPLEMENTATION
2924
2925 //////////////////////////////////////////////////////////////////////////////
2926 //
2927 // Random Numbers via Meresenne Twister or LCG
2928 //
2929
2930 #ifndef STB_INCLUDE_STB_LIB_H
2931 STB_EXTERN unsigned long stb_srandLCG(unsigned long seed);
2932 STB_EXTERN unsigned long stb_randLCG(void);
2933 STB_EXTERN double stb_frandLCG(void);
2934
2935 STB_EXTERN void stb_srand(unsigned long seed);
2936 STB_EXTERN unsigned long stb_rand(void);
2937 STB_EXTERN double stb_frand(void);
2938 STB_EXTERN void stb_shuffle(void *p, size_t n, size_t sz,
2939 unsigned long seed);
2940 STB_EXTERN void stb_reverse(void *p, size_t n, size_t sz);
2941
2942 STB_EXTERN unsigned long stb_randLCG_explicit(unsigned long seed);
2943 #endif // STB_INCLUDE_STB_LIB_H
2944
2945 #ifdef STB_LIB_IMPLEMENTATION
stb_randLCG_explicit(unsigned long seed)2946 unsigned long stb_randLCG_explicit(unsigned long seed)
2947 {
2948 return seed * 2147001325 + 715136305;
2949 }
2950
2951 static unsigned long stb__rand_seed=0;
2952
stb_srandLCG(unsigned long seed)2953 unsigned long stb_srandLCG(unsigned long seed)
2954 {
2955 unsigned long previous = stb__rand_seed;
2956 stb__rand_seed = seed;
2957 return previous;
2958 }
2959
stb_randLCG(void)2960 unsigned long stb_randLCG(void)
2961 {
2962 stb__rand_seed = stb__rand_seed * 2147001325 + 715136305; // BCPL generator
2963 // shuffle non-random bits to the middle, and xor to decorrelate with seed
2964 return 0x31415926 ^ ((stb__rand_seed >> 16) + (stb__rand_seed << 16));
2965 }
2966
stb_frandLCG(void)2967 double stb_frandLCG(void)
2968 {
2969 return stb_randLCG() / ((double) (1 << 16) * (1 << 16));
2970 }
2971
stb_shuffle(void * p,size_t n,size_t sz,unsigned long seed)2972 void stb_shuffle(void *p, size_t n, size_t sz, unsigned long seed)
2973 {
2974 char *a;
2975 unsigned long old_seed;
2976 int i;
2977 if (seed)
2978 old_seed = stb_srandLCG(seed);
2979 a = (char *) p + (n-1) * sz;
2980
2981 for (i=n; i > 1; --i) {
2982 int j = stb_randLCG() % i;
2983 stb_swap(a, (char *) p + j * sz, sz);
2984 a -= sz;
2985 }
2986 if (seed)
2987 stb_srandLCG(old_seed);
2988 }
2989
stb_reverse(void * p,size_t n,size_t sz)2990 void stb_reverse(void *p, size_t n, size_t sz)
2991 {
2992 int i,j = n-1;
2993 for (i=0; i < j; ++i,--j) {
2994 stb_swap((char *) p + i * sz, (char *) p + j * sz, sz);
2995 }
2996 }
2997
2998 // public domain Mersenne Twister by Michael Brundage
2999 #define STB__MT_LEN 624
3000
3001 int stb__mt_index = STB__MT_LEN*sizeof(unsigned long)+1;
3002 unsigned long stb__mt_buffer[STB__MT_LEN];
3003
stb_srand(unsigned long seed)3004 void stb_srand(unsigned long seed)
3005 {
3006 int i;
3007 unsigned long old = stb_srandLCG(seed);
3008 for (i = 0; i < STB__MT_LEN; i++)
3009 stb__mt_buffer[i] = stb_randLCG();
3010 stb_srandLCG(old);
3011 stb__mt_index = STB__MT_LEN*sizeof(unsigned long);
3012 }
3013
3014 #define STB__MT_IA 397
3015 #define STB__MT_IB (STB__MT_LEN - STB__MT_IA)
3016 #define STB__UPPER_MASK 0x80000000
3017 #define STB__LOWER_MASK 0x7FFFFFFF
3018 #define STB__MATRIX_A 0x9908B0DF
3019 #define STB__TWIST(b,i,j) ((b)[i] & STB__UPPER_MASK) | ((b)[j] & STB__LOWER_MASK)
3020 #define STB__MAGIC(s) (((s)&1)*STB__MATRIX_A)
3021
stb_rand()3022 unsigned long stb_rand()
3023 {
3024 unsigned long * b = stb__mt_buffer;
3025 int idx = stb__mt_index;
3026 unsigned long s,r;
3027 int i;
3028
3029 if (idx >= STB__MT_LEN*sizeof(unsigned long)) {
3030 if (idx > STB__MT_LEN*sizeof(unsigned long))
3031 stb_srand(0);
3032 idx = 0;
3033 i = 0;
3034 for (; i < STB__MT_IB; i++) {
3035 s = STB__TWIST(b, i, i+1);
3036 b[i] = b[i + STB__MT_IA] ^ (s >> 1) ^ STB__MAGIC(s);
3037 }
3038 for (; i < STB__MT_LEN-1; i++) {
3039 s = STB__TWIST(b, i, i+1);
3040 b[i] = b[i - STB__MT_IB] ^ (s >> 1) ^ STB__MAGIC(s);
3041 }
3042
3043 s = STB__TWIST(b, STB__MT_LEN-1, 0);
3044 b[STB__MT_LEN-1] = b[STB__MT_IA-1] ^ (s >> 1) ^ STB__MAGIC(s);
3045 }
3046 stb__mt_index = idx + sizeof(unsigned long);
3047
3048 r = *(unsigned long *)((unsigned char *)b + idx);
3049
3050 r ^= (r >> 11);
3051 r ^= (r << 7) & 0x9D2C5680;
3052 r ^= (r << 15) & 0xEFC60000;
3053 r ^= (r >> 18);
3054
3055 return r;
3056 }
3057
stb_frand(void)3058 double stb_frand(void)
3059 {
3060 return stb_rand() / ((double) (1 << 16) * (1 << 16));
3061 }
3062 #endif
3063
3064 //////////////////////////////////////////////////////////////////////////////
3065 //
3066 // wildcards and regexping
3067 //
3068
3069 #ifndef STB_INCLUDE_STB_LIB_H
3070 STB_EXTERN int stb_wildmatch (char *expr, char *candidate);
3071 STB_EXTERN int stb_wildmatchi(char *expr, char *candidate);
3072 STB_EXTERN int stb_wildfind (char *expr, char *candidate);
3073 STB_EXTERN int stb_wildfindi (char *expr, char *candidate);
3074 #endif // STB_INCLUDE_STB_LIB_H
3075
3076 #ifdef STB_LIB_IMPLEMENTATION
stb__match_qstring(char * candidate,char * qstring,int qlen,int insensitive)3077 static int stb__match_qstring(char *candidate, char *qstring, int qlen, int insensitive)
3078 {
3079 int i;
3080 if (insensitive) {
3081 for (i=0; i < qlen; ++i)
3082 if (qstring[i] == '?') {
3083 if (!candidate[i]) return 0;
3084 } else
3085 if (tolower(qstring[i]) != tolower(candidate[i]))
3086 return 0;
3087 } else {
3088 for (i=0; i < qlen; ++i)
3089 if (qstring[i] == '?') {
3090 if (!candidate[i]) return 0;
3091 } else
3092 if (qstring[i] != candidate[i])
3093 return 0;
3094 }
3095 return 1;
3096 }
3097
stb__find_qstring(char * candidate,char * qstring,int qlen,int insensitive)3098 static int stb__find_qstring(char *candidate, char *qstring, int qlen, int insensitive)
3099 {
3100 char c;
3101
3102 int offset=0;
3103 while (*qstring == '?') {
3104 ++qstring;
3105 --qlen;
3106 ++candidate;
3107 if (qlen == 0) return 0;
3108 if (*candidate == 0) return -1;
3109 }
3110
3111 c = *qstring++;
3112 --qlen;
3113 if (insensitive) c = tolower(c);
3114
3115 while (candidate[offset]) {
3116 if (c == (insensitive ? tolower(candidate[offset]) : candidate[offset]))
3117 if (stb__match_qstring(candidate+offset+1, qstring, qlen, insensitive))
3118 return offset;
3119 ++offset;
3120 }
3121
3122 return -1;
3123 }
3124
stb__wildmatch_raw2(char * expr,char * candidate,int search,int insensitive)3125 int stb__wildmatch_raw2(char *expr, char *candidate, int search, int insensitive)
3126 {
3127 int where=0;
3128 int start = -1;
3129
3130 if (!search) {
3131 // parse to first '*'
3132 if (*expr != '*')
3133 start = 0;
3134 while (*expr != '*') {
3135 if (!*expr)
3136 return *candidate == 0 ? 0 : -1;
3137 if (*expr == '?') {
3138 if (!*candidate) return -1;
3139 } else {
3140 if (insensitive) {
3141 if (tolower(*candidate) != tolower(*expr))
3142 return -1;
3143 } else
3144 if (*candidate != *expr)
3145 return -1;
3146 }
3147 ++candidate, ++expr, ++where;
3148 }
3149 } else {
3150 // 0-length search string
3151 if (!*expr)
3152 return 0;
3153 }
3154
3155 assert(search || *expr == '*');
3156 if (!search)
3157 ++expr;
3158
3159 // implicit '*' at this point
3160
3161 while (*expr) {
3162 int o=0;
3163 // combine redundant * characters
3164 while (expr[0] == '*') ++expr;
3165
3166 // ok, at this point, expr[-1] == '*',
3167 // and expr[0] != '*'
3168
3169 if (!expr[0]) return start >= 0 ? start : 0;
3170
3171 // now find next '*'
3172 o = 0;
3173 while (expr[o] != '*') {
3174 if (expr[o] == 0)
3175 break;
3176 ++o;
3177 }
3178 // if no '*', scan to end, then match at end
3179 if (expr[o] == 0 && !search) {
3180 int z;
3181 for (z=0; z < o; ++z)
3182 if (candidate[z] == 0)
3183 return -1;
3184 while (candidate[z])
3185 ++z;
3186 // ok, now check if they match
3187 if (stb__match_qstring(candidate+z-o, expr, o, insensitive))
3188 return start >= 0 ? start : 0;
3189 return -1;
3190 } else {
3191 // if yes '*', then do stb__find_qmatch on the intervening chars
3192 int n = stb__find_qstring(candidate, expr, o, insensitive);
3193 if (n < 0)
3194 return -1;
3195 if (start < 0)
3196 start = where + n;
3197 expr += o;
3198 candidate += n+o;
3199 }
3200
3201 if (*expr == 0) {
3202 assert(search);
3203 return start;
3204 }
3205
3206 assert(*expr == '*');
3207 ++expr;
3208 }
3209
3210 return start >= 0 ? start : 0;
3211 }
3212
stb__wildmatch_raw(char * expr,char * candidate,int search,int insensitive)3213 int stb__wildmatch_raw(char *expr, char *candidate, int search, int insensitive)
3214 {
3215 char buffer[256];
3216 // handle multiple search strings
3217 char *s = strchr(expr, ';');
3218 char *last = expr;
3219 while (s) {
3220 int z;
3221 // need to allow for non-writeable strings... assume they're small
3222 if (s - last < 256) {
3223 stb_strncpy(buffer, last, s-last+1);
3224 z = stb__wildmatch_raw2(buffer, candidate, search, insensitive);
3225 } else {
3226 *s = 0;
3227 z = stb__wildmatch_raw2(last, candidate, search, insensitive);
3228 *s = ';';
3229 }
3230 if (z >= 0) return z;
3231 last = s+1;
3232 s = strchr(last, ';');
3233 }
3234 return stb__wildmatch_raw2(last, candidate, search, insensitive);
3235 }
3236
stb_wildmatch(char * expr,char * candidate)3237 int stb_wildmatch(char *expr, char *candidate)
3238 {
3239 return stb__wildmatch_raw(expr, candidate, 0,0) >= 0;
3240 }
3241
stb_wildmatchi(char * expr,char * candidate)3242 int stb_wildmatchi(char *expr, char *candidate)
3243 {
3244 return stb__wildmatch_raw(expr, candidate, 0,1) >= 0;
3245 }
3246
stb_wildfind(char * expr,char * candidate)3247 int stb_wildfind(char *expr, char *candidate)
3248 {
3249 return stb__wildmatch_raw(expr, candidate, 1,0);
3250 }
3251
stb_wildfindi(char * expr,char * candidate)3252 int stb_wildfindi(char *expr, char *candidate)
3253 {
3254 return stb__wildmatch_raw(expr, candidate, 1,1);
3255 }
3256
3257 #undef STB_LIB_IMPLEMENTATION
3258 #endif // STB_LIB_IMPLEMENTATION
3259
3260 #ifndef STB_INCLUDE_STB_LIB_H
3261 #define STB_INCLUDE_STB_LIB_H
3262 #undef STB_EXTERN
3263 #endif
3264
3265 /*
3266 ------------------------------------------------------------------------------
3267 This software is available under 2 licenses -- choose whichever you prefer.
3268 ------------------------------------------------------------------------------
3269 ALTERNATIVE A - MIT License
3270 Copyright (c) 2017 Sean Barrett
3271 Permission is hereby granted, free of charge, to any person obtaining a copy of
3272 this software and associated documentation files (the "Software"), to deal in
3273 the Software without restriction, including without limitation the rights to
3274 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
3275 of the Software, and to permit persons to whom the Software is furnished to do
3276 so, subject to the following conditions:
3277 The above copyright notice and this permission notice shall be included in all
3278 copies or substantial portions of the Software.
3279 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
3280 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
3281 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
3282 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
3283 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
3284 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
3285 SOFTWARE.
3286 ------------------------------------------------------------------------------
3287 ALTERNATIVE B - Public Domain (www.unlicense.org)
3288 This is free and unencumbered software released into the public domain.
3289 Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
3290 software, either in source code form or as a compiled binary, for any purpose,
3291 commercial or non-commercial, and by any means.
3292 In jurisdictions that recognize copyright laws, the author or authors of this
3293 software dedicate any and all copyright interest in the software to the public
3294 domain. We make this dedication for the benefit of the public at large and to
3295 the detriment of our heirs and successors. We intend this dedication to be an
3296 overt act of relinquishment in perpetuity of all present and future rights to
3297 this software under copyright law.
3298 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
3299 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
3300 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
3301 AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
3302 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
3303 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
3304 ------------------------------------------------------------------------------
3305 */
3306