/* stb-2.11 - Sean's Tool Box -- public domain -- http://nothings.org/stb.h no warranty is offered or implied; use this code at your own risk This is a single header file with a bunch of useful utilities for getting stuff done in C/C++. Email bug reports, feature requests, etc. to 'sean' at the same site. Documentation: http://nothings.org/stb/stb_h.html Unit tests: http://nothings.org/stb/stb.c ============================================================================ You MUST #define STB_DEFINE in EXACTLY _one_ C or C++ file that includes this header, BEFORE the include, like this: #define STB_DEFINE #include "stb.h" All other files should just #include "stb.h" without the #define. ============================================================================ Version History 2.12 fix STB_ONLY -- lots of uint32s, TRUE/FALSE things had crept in 2.11 fix bug in stb_dirtree_get() which caused "c://path" sorts of stuff 2.10 STB_F(), STB_I() inline constants (also KI,KU,KF,KD) 2.09 stb_box_face_vertex_axis_side 2.08 bugfix stb_trimwhite() 2.07 colored printing in windows (why are we in 1985?) 2.06 comparison functions are now functions-that-return-functions and accept a struct-offset as a parameter (not thread-safe) 2.05 compile and pass tests under Linux (but no threads); thread cleanup 2.04 stb_cubic_bezier_1d, smoothstep, avoid dependency on registry 2.03 ? 2.02 remove integrated documentation 2.01 integrate various fixes; stb_force_uniprocessor 2.00 revised stb_dupe to use multiple hashes 1.99 stb_charcmp 1.98 stb_arr_deleten, stb_arr_insertn 1.97 fix stb_newell_normal() 1.96 stb_hash_number() 1.95 hack stb__rec_max; clean up recursion code to use new functions 1.94 stb_dirtree; rename stb_extra to stb_ptrmap 1.93 stb_sem_new() API cleanup (no blockflag-starts blocked; use 'extra') 1.92 stb_threadqueue--multi reader/writer queue, fixed size or resizeable 1.91 stb_bgio_* for reading disk asynchronously 1.90 stb_mutex uses CRITICAL_REGION; new stb_sync primitive for thread joining; workqueue supports stb_sync instead of stb_semaphore 1.89 support ';' in constant-string wildcards; stb_mutex wrapper (can implement with EnterCriticalRegion eventually) 1.88 portable threading API (only for win32 so far); worker thread queue 1.87 fix wildcard handling in stb_readdir_recursive 1.86 support ';' in wildcards 1.85 make stb_regex work with non-constant strings; beginnings of stb_introspect() 1.84 (forgot to make notes) 1.83 whoops, stb_keep_if_different wasn't deleting the temp file 1.82 bring back stb_compress from stb_file.h for cmirror 1.81 various bugfixes, STB_FASTMALLOC_INIT inits FASTMALLOC in release 1.80 stb_readdir returns utf8; write own utf8-utf16 because lib was wrong 1.79 stb_write 1.78 calloc() support for malloc wrapper, STB_FASTMALLOC 1.77 STB_FASTMALLOC 1.76 STB_STUA - Lua-like language; (stb_image, stb_csample, stb_bilinear) 1.75 alloc/free array of blocks; stb_hheap bug; a few stb_ps_ funcs; hash*getkey, hash*copy; stb_bitset; stb_strnicmp; bugfix stb_bst 1.74 stb_replaceinplace; use stdlib C function to convert utf8 to UTF-16 1.73 fix performance bug & leak in stb_ischar (C++ port lost a 'static') 1.72 remove stb_block, stb_block_manager, stb_decompress (to stb_file.h) 1.71 stb_trimwhite, stb_tokens_nested, etc. 1.70 back out 1.69 because it might problemize mixed builds; stb_filec() 1.69 (stb_file returns 'char *' in C++) 1.68 add a special 'tree root' data type for stb_bst; stb_arr_end 1.67 full C++ port. (stb_block_manager) 1.66 stb_newell_normal 1.65 stb_lex_item_wild -- allow wildcard items which MUST match entirely 1.64 stb_data 1.63 stb_log_name 1.62 stb_define_sort; C++ cleanup 1.61 stb_hash_fast -- Paul Hsieh's hash function (beats Bob Jenkins'?) 1.60 stb_delete_directory_recursive 1.59 stb_readdir_recursive 1.58 stb_bst variant with parent pointer for O(1) iteration, not O(log N) 1.57 replace LCG random with Mersenne Twister (found a public domain one) 1.56 stb_perfect_hash, stb_ischar, stb_regex 1.55 new stb_bst API allows multiple BSTs per node (e.g. secondary keys) 1.54 bugfix: stb_define_hash, stb_wildmatch, regexp 1.53 stb_define_hash; recoded stb_extra, stb_sdict use it 1.52 stb_rand_define, stb_bst, stb_reverse 1.51 fix 'stb_arr_setlen(NULL, 0)' 1.50 stb_wordwrap 1.49 minor improvements to enable the scripting language 1.48 better approach for stb_arr using stb_malloc; more invasive, clearer 1.47 stb_lex (lexes stb.h at 1.5ML/s on 3Ghz P4; 60/70% of optimal/flex) 1.46 stb_wrapper_*, STB_MALLOC_WRAPPER 1.45 lightly tested DFA acceleration of regexp searching 1.44 wildcard matching & searching; regexp matching & searching 1.43 stb_temp 1.42 allow stb_arr to use stb_malloc/realloc; note this is global 1.41 make it compile in C++; (disable stb_arr in C++) 1.40 stb_dupe tweak; stb_swap; stb_substr 1.39 stb_dupe; improve stb_file_max to be less stupid 1.38 stb_sha1_file: generate sha1 for file, even > 4GB 1.37 stb_file_max; partial support for utf8 filenames in Windows 1.36 remove STB__NO_PREFIX - poor interaction with IDE, not worth it streamline stb_arr to make it separately publishable 1.35 bugfixes for stb_sdict, stb_malloc(0), stristr 1.34 (streaming interfaces for stb_compress) 1.33 stb_alloc; bug in stb_getopt; remove stb_overflow 1.32 (stb_compress returns, smaller&faster; encode window & 64-bit len) 1.31 stb_prefix_count 1.30 (STB__NO_PREFIX - remove stb_ prefixes for personal projects) 1.29 stb_fput_varlen64, etc. 1.28 stb_sha1 1.27 ? 1.26 stb_extra 1.25 ? 1.24 stb_copyfile 1.23 stb_readdir 1.22 ? 1.21 ? 1.20 ? 1.19 ? 1.18 ? 1.17 ? 1.16 ? 1.15 stb_fixpath, stb_splitpath, stb_strchr2 1.14 stb_arr 1.13 ?stb, stb_log, stb_fatal 1.12 ?stb_hash2 1.11 miniML 1.10 stb_crc32, stb_adler32 1.09 stb_sdict 1.08 stb_bitreverse, stb_ispow2, stb_big32 stb_fopen, stb_fput_varlen, stb_fput_ranged stb_fcmp, stb_feq 1.07 (stb_encompress) 1.06 stb_compress 1.05 stb_tokens, (stb_hheap) 1.04 stb_rand 1.03 ?(s-strings) 1.02 ?stb_filelen, stb_tokens 1.01 stb_tolower 1.00 stb_hash, stb_intcmp stb_file, stb_stringfile, stb_fgets stb_prefix, stb_strlower, stb_strtok stb_image (stb_array), (stb_arena) Parenthesized items have since been removed. */ #ifndef STB__INCLUDE_STB_H #define STB__INCLUDE_STB_H #ifdef STB_INTROSPECT #define STB_DEFINE #endif #include // stdlib could have min/max #include // need FILE #include // stb_define_hash needs memcpy/memset #include // stb_dirtree #ifdef STB_PERSONAL typedef int Bool; #define False 0 #define True 1 #endif #ifdef STB_MALLOC_WRAPPER_PAGED #define STB_MALLOC_WRAPPER_DEBUG #endif #ifdef STB_MALLOC_WRAPPER_DEBUG #define STB_MALLOC_WRAPPER #endif #ifdef STB_MALLOC_WRAPPER_FASTMALLOC #define STB_FASTMALLOC #define STB_MALLOC_WRAPPER #endif #ifdef STB_FASTMALLOC #ifndef _WIN32 #undef STB_FASTMALLOC #endif #endif #ifdef STB_DEFINE #include #include #include #include #include #ifndef _WIN32 #include #else #include // _mktemp #include // _rmdir #endif #include // stat()/_stat() #include // stat()/_stat() #endif #define stb_min(a,b) ((a) < (b) ? (a) : (b)) #define stb_max(a,b) ((a) > (b) ? (a) : (b)) #ifndef STB_ONLY #if !defined(__cplusplus) && !defined(min) && !defined(max) #define min(x,y) stb_min(x,y) #define max(x,y) stb_max(x,y) #endif #ifndef M_PI #define M_PI 3.14159265358979323846f #endif #ifndef TRUE #define TRUE 1 #define FALSE 0 #endif #ifndef deg2rad #define deg2rad(a) ((a)*(M_PI/180)) #endif #ifndef rad2deg #define rad2deg(a) ((a)*(180/M_PI)) #endif #ifndef swap #ifndef __cplusplus #define swap(TYPE,a,b) \ do { TYPE stb__t; stb__t = (a); (a) = (b); (b) = stb__t; } while (0) #endif #endif typedef unsigned char uint8 ; typedef signed char int8 ; typedef unsigned short uint16; typedef signed short int16; #if defined(STB_USE_LONG_FOR_32_BIT_INT) || defined(STB_LONG32) typedef unsigned long uint32; typedef signed long int32; #else typedef unsigned int uint32; typedef signed int int32; #endif typedef unsigned char uchar ; typedef unsigned short ushort; typedef unsigned int uint ; typedef unsigned long ulong ; // produce compile errors if the sizes aren't right typedef char stb__testsize16[sizeof(int16)==2]; typedef char stb__testsize32[sizeof(int32)==4]; #endif #ifndef STB_TRUE #define STB_TRUE 1 #define STB_FALSE 0 #endif // if we're STB_ONLY, can't rely on uint32 or even uint, so all the // variables we'll use herein need typenames prefixed with 'stb': typedef unsigned char stb_uchar; typedef unsigned char stb_uint8; typedef unsigned int stb_uint; typedef unsigned short stb_uint16; typedef short stb_int16; typedef signed char stb_int8; #if defined(STB_USE_LONG_FOR_32_BIT_INT) || defined(STB_LONG32) typedef unsigned long stb_uint32; typedef long stb_int32; #else typedef unsigned int stb_uint32; typedef int stb_int32; #endif typedef char stb__testsize2_16[sizeof(stb_uint16)==2]; typedef char stb__testsize2_32[sizeof(stb_uint32)==4]; #ifdef __cplusplus #define STB_EXTERN extern "C" #else #define STB_EXTERN extern #endif // check for well-known debug defines #if defined(DEBUG) || defined(_DEBUG) || defined(DBG) #ifndef NDEBUG #define STB_DEBUG #endif #endif #ifdef STB_DEBUG #include #endif STB_EXTERN void stb_wrapper_malloc(void *newp, int sz, char *file, int line); STB_EXTERN void stb_wrapper_free(void *oldp, char *file, int line); STB_EXTERN void stb_wrapper_realloc(void *oldp, void *newp, int sz, char *file, int line); STB_EXTERN void stb_wrapper_calloc(size_t num, size_t sz, char *file, int line); STB_EXTERN void stb_wrapper_listall(void (*func)(void *ptr, int sz, char *file, int line)); STB_EXTERN void stb_wrapper_dump(char *filename); STB_EXTERN int stb_wrapper_allocsize(void *oldp); STB_EXTERN void stb_wrapper_check(void *oldp); #ifdef STB_DEFINE // this is a special function used inside malloc wrapper // to do allocations that aren't tracked (to avoid // reentrancy). Of course if someone _else_ wraps realloc, // this breaks, but if they're doing that AND the malloc // wrapper they need to explicitly check for reentrancy. // // only define realloc_raw() and we do realloc(NULL,sz) // for malloc() and realloc(p,0) for free(). static void * stb__realloc_raw(void *p, int sz) { if (p == NULL) return malloc(sz); if (sz == 0) { free(p); return NULL; } return realloc(p,sz); } #endif #ifdef _WIN32 STB_EXTERN void * stb_smalloc(size_t sz); STB_EXTERN void stb_sfree(void *p); STB_EXTERN void * stb_srealloc(void *p, size_t sz); STB_EXTERN void * stb_scalloc(size_t n, size_t sz); STB_EXTERN char * stb_sstrdup(char *s); #endif #ifdef STB_FASTMALLOC #define malloc stb_smalloc #define free stb_sfree #define realloc stb_srealloc #define strdup stb_sstrdup #define calloc stb_scalloc #endif #ifndef STB_MALLOC_ALLCHECK #define stb__check(p) 1 #else #ifndef STB_MALLOC_WRAPPER #error STB_MALLOC_ALLCHECK requires STB_MALLOC_WRAPPER #else #define stb__check(p) stb_mcheck(p) #endif #endif #ifdef STB_MALLOC_WRAPPER STB_EXTERN void * stb__malloc(int, char *, int); STB_EXTERN void * stb__realloc(void *, int, char *, int); STB_EXTERN void * stb__calloc(size_t n, size_t s, char *, int); STB_EXTERN void stb__free(void *, char *file, int); STB_EXTERN char * stb__strdup(char *s, char *file, int); STB_EXTERN void stb_malloc_checkall(void); STB_EXTERN void stb_malloc_check_counter(int init_delay, int rep_delay); #ifndef STB_MALLOC_WRAPPER_DEBUG #define stb_mcheck(p) 1 #else STB_EXTERN int stb_mcheck(void *); #endif #ifdef STB_DEFINE #ifdef STB_MALLOC_WRAPPER_DEBUG #define STB__PAD 32 #define STB__BIAS 16 #define STB__SIG 0x51b01234 #define STB__FIXSIZE(sz) (((sz+3) & ~3) + STB__PAD) #define STB__ptr(x,y) ((char *) (x) + (y)) #else #define STB__ptr(x,y) (x) #define STB__FIXSIZE(sz) (sz) #endif #ifdef STB_MALLOC_WRAPPER_DEBUG int stb_mcheck(void *p) { unsigned int sz; if (p == NULL) return 1; p = ((char *) p) - STB__BIAS; sz = * (unsigned int *) p; assert(* (unsigned int *) STB__ptr(p,4) == STB__SIG); assert(* (unsigned int *) STB__ptr(p,8) == STB__SIG); assert(* (unsigned int *) STB__ptr(p,12) == STB__SIG); assert(* (unsigned int *) STB__ptr(p,sz-4) == STB__SIG+1); assert(* (unsigned int *) STB__ptr(p,sz-8) == STB__SIG+1); assert(* (unsigned int *) STB__ptr(p,sz-12) == STB__SIG+1); assert(* (unsigned int *) STB__ptr(p,sz-16) == STB__SIG+1); stb_wrapper_check(STB__ptr(p, STB__BIAS)); return 1; } static void stb__check2(void *p, int sz, char *file, int line) { stb_mcheck(p); } void stb_malloc_checkall(void) { stb_wrapper_listall(stb__check2); } #else void stb_malloc_checkall(void) { } #endif static int stb__malloc_wait=(1 << 30), stb__malloc_next_wait = (1 << 30), stb__malloc_iter; void stb_malloc_check_counter(int init_delay, int rep_delay) { stb__malloc_wait = init_delay; stb__malloc_next_wait = rep_delay; } void stb_mcheck_all(void) { #ifdef STB_MALLOC_WRAPPER_DEBUG ++stb__malloc_iter; if (--stb__malloc_wait <= 0) { stb_malloc_checkall(); stb__malloc_wait = stb__malloc_next_wait; } #endif } #ifdef STB_MALLOC_WRAPPER_PAGED #define STB__WINDOWS_PAGE (1 << 12) #ifndef _WINDOWS_ STB_EXTERN __declspec(dllimport) void * __stdcall VirtualAlloc(void *p, unsigned long size, unsigned long type, unsigned long protect); STB_EXTERN __declspec(dllimport) int __stdcall VirtualFree(void *p, unsigned long size, unsigned long freetype); #endif #endif static void *stb__malloc_final(int sz) { #ifdef STB_MALLOC_WRAPPER_PAGED int aligned = (sz + STB__WINDOWS_PAGE - 1) & ~(STB__WINDOWS_PAGE-1); char *p = VirtualAlloc(NULL, aligned + STB__WINDOWS_PAGE, 0x2000, 0x04); // RESERVE, READWRITE if (p == NULL) return p; VirtualAlloc(p, aligned, 0x1000, 0x04); // COMMIT, READWRITE return p; #else return malloc(sz); #endif } static void stb__free_final(void *p) { #ifdef STB_MALLOC_WRAPPER_PAGED VirtualFree(p, 0, 0x8000); // RELEASE #else free(p); #endif } int stb__malloc_failure; static void *stb__realloc_final(void *p, int sz, int old_sz) { #ifdef STB_MALLOC_WRAPPER_PAGED void *q = stb__malloc_final(sz); if (q == NULL) return ++stb__malloc_failure, q; // @TODO: deal with p being smaller! memcpy(q, p, sz < old_sz ? sz : old_sz); stb__free_final(p); return q; #else return realloc(p,sz); #endif } void stb__free(void *p, char *file, int line) { stb_mcheck_all(); if (!p) return; #ifdef STB_MALLOC_WRAPPER_DEBUG stb_mcheck(p); #endif stb_wrapper_free(p,file,line); #ifdef STB_MALLOC_WRAPPER_DEBUG p = STB__ptr(p,-STB__BIAS); * (unsigned int *) STB__ptr(p,0) = 0xdeadbeef; * (unsigned int *) STB__ptr(p,4) = 0xdeadbeef; * (unsigned int *) STB__ptr(p,8) = 0xdeadbeef; * (unsigned int *) STB__ptr(p,12) = 0xdeadbeef; #endif stb__free_final(p); } void * stb__malloc(int sz, char *file, int line) { void *p; stb_mcheck_all(); if (sz == 0) return NULL; if (stb__malloc_iter == 12741) sz = sz; p = stb__malloc_final(STB__FIXSIZE(sz)); if (p == NULL) p = stb__malloc_final(STB__FIXSIZE(sz)); if (p == NULL) p = stb__malloc_final(STB__FIXSIZE(sz)); if (p == NULL) { ++stb__malloc_failure; #ifdef STB_MALLOC_WRAPPER_DEBUG stb_malloc_checkall(); #endif return p; } #ifdef STB_MALLOC_WRAPPER_DEBUG * (int *) STB__ptr(p,0) = STB__FIXSIZE(sz); * (unsigned int *) STB__ptr(p,4) = STB__SIG; * (unsigned int *) STB__ptr(p,8) = STB__SIG; * (unsigned int *) STB__ptr(p,12) = STB__SIG; * (unsigned int *) STB__ptr(p,STB__FIXSIZE(sz)-4) = STB__SIG+1; * (unsigned int *) STB__ptr(p,STB__FIXSIZE(sz)-8) = STB__SIG+1; * (unsigned int *) STB__ptr(p,STB__FIXSIZE(sz)-12) = STB__SIG+1; * (unsigned int *) STB__ptr(p,STB__FIXSIZE(sz)-16) = STB__SIG+1; p = STB__ptr(p, STB__BIAS); #endif stb_wrapper_malloc(p,sz,file,line); return p; } void * stb__realloc(void *p, int sz, char *file, int line) { void *q; stb_mcheck_all(); if (p == NULL) return stb__malloc(sz,file,line); if (sz == 0 ) { stb__free(p,file,line); return NULL; } #ifdef STB_MALLOC_WRAPPER_DEBUG stb_mcheck(p); p = STB__ptr(p,-STB__BIAS); #endif #ifdef STB_MALLOC_WRAPPER_PAGED { int n = stb_wrapper_allocsize(STB__ptr(p,STB__BIAS)); if (!n) stb_wrapper_check(STB__ptr(p,STB__BIAS)); q = stb__realloc_final(p, STB__FIXSIZE(sz), STB__FIXSIZE(n)); } #else q = realloc(p, STB__FIXSIZE(sz)); #endif if (q == NULL) return ++stb__malloc_failure, q; #ifdef STB_MALLOC_WRAPPER_DEBUG * (int *) STB__ptr(q,0) = STB__FIXSIZE(sz); * (unsigned int *) STB__ptr(q,4) = STB__SIG; * (unsigned int *) STB__ptr(q,8) = STB__SIG; * (unsigned int *) STB__ptr(q,12) = STB__SIG; * (unsigned int *) STB__ptr(q,STB__FIXSIZE(sz)-4) = STB__SIG+1; * (unsigned int *) STB__ptr(q,STB__FIXSIZE(sz)-8) = STB__SIG+1; * (unsigned int *) STB__ptr(q,STB__FIXSIZE(sz)-12) = STB__SIG+1; * (unsigned int *) STB__ptr(q,STB__FIXSIZE(sz)-16) = STB__SIG+1; q = STB__ptr(q, STB__BIAS); p = STB__ptr(p, STB__BIAS); #endif stb_wrapper_realloc(p,q,sz,file,line); return q; } STB_EXTERN int stb_log2_ceil(unsigned int); static void *stb__calloc(size_t n, size_t sz, char *file, int line) { void *q; stb_mcheck_all(); if (n == 0 || sz == 0) return NULL; if (stb_log2_ceil(n) + stb_log2_ceil(sz) >= 32) return NULL; q = stb__malloc(n*sz, file, line); if (q) memset(q, 0, n*sz); return q; } char * stb__strdup(char *s, char *file, int line) { char *p; stb_mcheck_all(); p = stb__malloc(strlen(s)+1, file, line); if (!p) return p; strcpy(p, s); return p; } #endif // STB_DEFINE #ifdef STB_FASTMALLOC #undef malloc #undef realloc #undef free #undef strdup #undef calloc #endif // include everything that might define these, BEFORE making macros #include #include #include #define malloc(s) stb__malloc ( s, __FILE__, __LINE__) #define realloc(p,s) stb__realloc(p,s, __FILE__, __LINE__) #define calloc(n,s) stb__calloc (n,s, __FILE__, __LINE__) #define free(p) stb__free (p, __FILE__, __LINE__) #define strdup(p) stb__strdup (p, __FILE__, __LINE__) #endif ////////////////////////////////////////////////////////////////////////////// // // Windows pretty display // STB_EXTERN void stbprint(const char *fmt, ...); STB_EXTERN char *stb_sprintf(const char *fmt, ...); #ifdef STB_DEFINE char *stb_sprintf(const char *fmt, ...) { static char buffer[1024]; va_list v; va_start(v,fmt); #ifdef _WIN32 _vsnprintf(buffer, 1024, fmt, v); #else vsnprintf(buffer, 1024, fmt, v); #endif va_end(v); buffer[1023] = 0; return buffer; } #ifdef _WIN32 #ifndef _WINDOWS_ STB_EXTERN __declspec(dllimport) int __stdcall WriteConsoleA(void *, const void *, unsigned int, unsigned int *, void *); STB_EXTERN __declspec(dllimport) void * __stdcall GetStdHandle(unsigned int); STB_EXTERN __declspec(dllimport) int __stdcall SetConsoleTextAttribute(void *, unsigned short); #endif static void stb__print_one(void *handle, char *s, int len) { if (len) if (WriteConsoleA(handle, s, len, NULL,NULL)) fwrite(s, 1, len, stdout); // if it fails, maybe redirected, so do normal } static void stb__print(char *s) { void *handle = GetStdHandle((unsigned int) -11); // STD_OUTPUT_HANDLE int pad=0; // number of padding characters to add char *t = s; while (*s) { int lpad; while (*s && *s != '{') { if (pad) { if (*s == '\r' || *s == '\n') pad = 0; else if (s[0] == ' ' && s[1] == ' ') { stb__print_one(handle, t, s-t); t = s; while (pad) { stb__print_one(handle, t, 1); --pad; } } } ++s; } if (!*s) break; stb__print_one(handle, t, s-t); if (s[1] == '{') { ++s; continue; } if (s[1] == '#') { t = s+3; if (isxdigit(s[2])) if (isdigit(s[2])) SetConsoleTextAttribute(handle, s[2] - '0'); else SetConsoleTextAttribute(handle, tolower(s[2]) - 'a' + 10); else { SetConsoleTextAttribute(handle, 0x0f); t=s+2; } } else if (s[1] == '!') { SetConsoleTextAttribute(handle, 0x0c); t = s+2; } else if (s[1] == '@') { SetConsoleTextAttribute(handle, 0x09); t = s+2; } else if (s[1] == '$') { SetConsoleTextAttribute(handle, 0x0a); t = s+2; } else { SetConsoleTextAttribute(handle, 0x08); // 0,7,8,15 => shades of grey t = s+1; } lpad = (t-s); s = t; while (*s && *s != '}') ++s; if (!*s) break; stb__print_one(handle, t, s-t); if (s[1] == '}') { t = s+2; } else { pad += 1+lpad; t = s+1; } s=t; SetConsoleTextAttribute(handle, 0x07); } stb__print_one(handle, t, s-t); SetConsoleTextAttribute(handle, 0x07); } void stbprint(const char *fmt, ...) { int res; char buffer[1024]; char *tbuf = buffer; va_list v; va_start(v,fmt); res = _vsnprintf(buffer, sizeof(buffer), fmt, v); va_end(v); buffer[sizeof(buffer)-1] = 0; if (res < 0) { tbuf = (char *) malloc(16384); va_start(v,fmt); res = _vsnprintf(tbuf,16384, fmt, v); va_end(v); tbuf[16383] = 0; } stb__print(tbuf); if (tbuf != buffer) free(tbuf); } #else // _WIN32 void stbprint(const char *fmt, ...) { va_list v; va_start(v,fmt); vprintf(fmt,v); va_end(v); } #endif // _WIN32 #endif // STB_DEFINE ////////////////////////////////////////////////////////////////////////////// // // Windows UTF8 filename handling // // Windows stupidly treats 8-bit filenames as some dopey code page, // rather than utf-8. If we want to use utf8 filenames, we have to // convert them to WCHAR explicitly and call WCHAR versions of the // file functions. So, ok, we do. #ifdef _WIN32 #define stb__fopen(x,y) _wfopen(stb__from_utf8(x), stb__from_utf8_alt(y)) #define stb__windows(x,y) x #else #define stb__fopen(x,y) fopen(x,y) #define stb__windows(x,y) y #endif typedef unsigned short stb__wchar; STB_EXTERN stb__wchar * stb_from_utf8(stb__wchar *buffer, char *str, int n); STB_EXTERN char * stb_to_utf8 (char *buffer, stb__wchar *str, int n); STB_EXTERN stb__wchar *stb__from_utf8(char *str); STB_EXTERN stb__wchar *stb__from_utf8_alt(char *str); STB_EXTERN char *stb__to_utf8(stb__wchar *str); #ifdef STB_DEFINE stb__wchar * stb_from_utf8(stb__wchar *buffer, char *str, int n) { stb_uint32 c; int i=0; --n; while (*str) { if (i >= n) return NULL; if (!(*str & 0x80)) buffer[i++] = *str++; else if ((*str & 0xe0) == 0xc0) { c = (*str++ & 0x1f) << 6; if ((*str & 0xc0) != 0x80) return NULL; buffer[i++] = c + (*str++ & 0x3f); } else if ((*str & 0xf0) == 0xe0) { c = (*str++ & 0x0f) << 12; if ((*str & 0xc0) != 0x80) return NULL; c += (*str++ & 0x3f) << 6; if ((*str & 0xc0) != 0x80) return NULL; buffer[i++] = c + (*str++ & 0x3f); } else if ((*str & 0xf8) == 0xf0) { c = (*str++ & 0x07) << 18; if ((*str & 0xc0) != 0x80) return NULL; c += (*str++ & 0x3f) << 12; if ((*str & 0xc0) != 0x80) return NULL; c += (*str++ & 0x3f) << 6; if ((*str & 0xc0) != 0x80) return NULL; c += (*str++ & 0x3f); // surrogate pair values are invalid if ((c & 0xFFFFF800) == 0xD800) return NULL; if (c >= 0x10000) { c -= 0x10000; if (i + 2 > n) return NULL; buffer[i++] = 0xD800 | (0x3ff & (c >> 10)); buffer[i++] = 0xDC00 | (0x3ff & (c )); } } else return NULL; } buffer[i] = 0; return buffer; } char * stb_to_utf8(char *buffer, stb__wchar *str, int n) { int i=0; --n; while (*str) { if (*str < 0x80) { if (i+1 > n) return NULL; buffer[i++] = (char) *str++; } else if (*str < 0x800) { if (i+2 > n) return NULL; buffer[i++] = 0xc0 + (*str >> 6); buffer[i++] = 0x80 + (*str & 0x3f); str += 1; } else if (*str >= 0xd800 && *str < 0xdc00) { stb_uint32 c; if (i+4 > n) return NULL; c = ((str[0] - 0xd800) << 10) + ((str[1]) - 0xdc00) + 0x10000; buffer[i++] = 0xf0 + (c >> 18); buffer[i++] = 0x80 + ((c >> 12) & 0x3f); buffer[i++] = 0x80 + ((c >> 6) & 0x3f); buffer[i++] = 0x80 + ((c ) & 0x3f); str += 2; } else if (*str >= 0xdc00 && *str < 0xe000) { return NULL; } else { if (i+3 > n) return NULL; buffer[i++] = 0xe0 + (*str >> 12); buffer[i++] = 0x80 + ((*str >> 6) & 0x3f); buffer[i++] = 0x80 + ((*str ) & 0x3f); str += 1; } } buffer[i] = 0; return buffer; } stb__wchar *stb__from_utf8(char *str) { static stb__wchar buffer[4096]; return stb_from_utf8(buffer, str, 4096); } stb__wchar *stb__from_utf8_alt(char *str) { static stb__wchar buffer[64]; return stb_from_utf8(buffer, str, 64); } char *stb__to_utf8(stb__wchar *str) { static char buffer[4096]; return stb_to_utf8(buffer, str, 4096); } #endif ////////////////////////////////////////////////////////////////////////////// // // Miscellany // STB_EXTERN void stb_fatal(char *fmt, ...); STB_EXTERN void stb_(char *fmt, ...); STB_EXTERN void stb_log(int active); STB_EXTERN void stb_log_fileline(int active); STB_EXTERN void stb_log_name(char *filename); STB_EXTERN void stb_swap(void *p, void *q, size_t sz); STB_EXTERN void *stb_copy(void *p, size_t sz); STB_EXTERN void stb_pointer_array_free(void *p, int len); STB_EXTERN void **stb_array_block_alloc(int count, int blocksize); #define stb_arrcount(x) (sizeof(x)/sizeof((x)[0])) STB_EXTERN int stb__record_fileline(char *f, int n); #ifdef STB_DEFINE static char *stb__file; static int stb__line; int stb__record_fileline(char *f, int n) { stb__file = f; stb__line = n; return 0; } void stb_fatal(char *s, ...) { va_list a; if (stb__file) fprintf(stderr, "[%s:%d] ", stb__file, stb__line); va_start(a,s); fputs("Fatal error: ", stderr); vfprintf(stderr, s, a); va_end(a); fputs("\n", stderr); #ifdef _WIN32 #ifdef STB_DEBUG __asm int 3; // trap to debugger! #endif #endif exit(1); } static int stb__log_active=1, stb__log_fileline=1; void stb_log(int active) { stb__log_active = active; } void stb_log_fileline(int active) { stb__log_fileline = active; } #ifdef STB_NO_STB_STRINGS char *stb__log_filename = "temp.log"; #else char *stb__log_filename = "stb.log"; #endif void stb_log_name(char *s) { stb__log_filename = s; } void stb_(char *s, ...) { if (stb__log_active) { FILE *f = fopen(stb__log_filename, "a"); if (f) { va_list a; if (stb__log_fileline && stb__file) fprintf(f, "[%s:%4d] ", stb__file, stb__line); va_start(a,s); vfprintf(f, s, a); va_end(a); fputs("\n", f); fclose(f); } } } typedef struct { char d[4]; } stb__4; typedef struct { char d[8]; } stb__8; // optimize the small cases, though you shouldn't be calling this for those! void stb_swap(void *p, void *q, size_t sz) { char buffer[256]; if (p == q) return; if (sz == 4) { stb__4 temp = * ( stb__4 *) p; * (stb__4 *) p = * ( stb__4 *) q; * (stb__4 *) q = temp; return; } else if (sz == 8) { stb__8 temp = * ( stb__8 *) p; * (stb__8 *) p = * ( stb__8 *) q; * (stb__8 *) q = temp; return; } while (sz > sizeof(buffer)) { stb_swap(p, q, sizeof(buffer)); p = (char *) p + sizeof(buffer); q = (char *) q + sizeof(buffer); sz -= sizeof(buffer); } memcpy(buffer, p , sz); memcpy(p , q , sz); memcpy(q , buffer, sz); } void *stb_copy(void *p, size_t sz) { void *q = malloc(sz); memcpy(q, p, sz); return q; } void stb_pointer_array_free(void *q, int len) { void **p = (void **) q; int i; for (i=0; i < len; ++i) free(p[i]); } void **stb_array_block_alloc(int count, int blocksize) { int i; char *p = (char *) malloc(sizeof(void *) * count + count * blocksize); void **q; if (p == NULL) return NULL; q = (void **) p; p += sizeof(void *) * count; for (i=0; i < count; ++i) q[i] = p + i * blocksize; return q; } #endif #ifdef STB_DEBUG // tricky hack to allow recording FILE,LINE even in varargs functions #define STB__RECORD_FILE(x) (stb__record_fileline(__FILE__, __LINE__),(x)) #define stb_log STB__RECORD_FILE(stb_log) #define stb_ STB__RECORD_FILE(stb_) #ifndef STB_FATAL_CLEAN #define stb_fatal STB__RECORD_FILE(stb_fatal) #endif #define STB__DEBUG(x) x #else #define STB__DEBUG(x) #endif ////////////////////////////////////////////////////////////////////////////// // // stb_temp // #define stb_temp(block, sz) stb__temp(block, sizeof(block), (sz)) STB_EXTERN void * stb__temp(void *b, int b_sz, int want_sz); STB_EXTERN void stb_tempfree(void *block, void *ptr); #ifdef STB_DEFINE void * stb__temp(void *b, int b_sz, int want_sz) { if (b_sz >= want_sz) return b; else return malloc(want_sz); } void stb_tempfree(void *b, void *p) { if (p != b) free(p); } #endif ////////////////////////////////////////////////////////////////////////////// // // math/sampling operations // #define stb_lerp(t,a,b) ( (a) + (t) * (float) ((b)-(a)) ) #define stb_unlerp(t,a,b) ( ((t) - (a)) / (float) ((b) - (a)) ) #define stb_clamp(x,xmin,xmax) ((x) < (xmin) ? (xmin) : (x) > (xmax) ? (xmax) : (x)) STB_EXTERN void stb_newell_normal(float *normal, int num_vert, float **vert, int normalize); STB_EXTERN int stb_box_face_vertex_axis_side(int face_number, int vertex_number, int axis); STB_EXTERN void stb_linear_controller(float *curpos, float target_pos, float acc, float deacc, float dt); STB_EXTERN int stb_float_eq(float x, float y, float delta, int max_ulps); STB_EXTERN int stb_is_prime(unsigned int m); STB_EXTERN unsigned int stb_power_of_two_nearest_prime(int n); STB_EXTERN float stb_smoothstep(float t); STB_EXTERN float stb_cubic_bezier_1d(float t, float p0, float p1, float p2, float p3); STB_EXTERN double stb_linear_remap(double x, double a, double b, double c, double d); #ifdef STB_DEFINE float stb_smoothstep(float t) { return (3 - 2*t)*(t*t); } float stb_cubic_bezier_1d(float t, float p0, float p1, float p2, float p3) { float it = 1-t; return it*it*it*p0 + 3*it*it*t*p1 + 3*it*t*t*p2 + t*t*t*p3; } void stb_newell_normal(float *normal, int num_vert, float **vert, int normalize) { int i,j; float p; normal[0] = normal[1] = normal[2] = 0; for (i=num_vert-1,j=0; j < num_vert; i=j++) { float *u = vert[i]; float *v = vert[j]; normal[0] += (u[1] - v[1]) * (u[2] + v[2]); normal[1] += (u[2] - v[2]) * (u[0] + v[0]); normal[2] += (u[0] - v[0]) * (u[1] + v[1]); } if (normalize) { p = normal[0]*normal[0] + normal[1]*normal[1] + normal[2]*normal[2]; p = (float) (1.0 / sqrt(p)); normal[0] *= p; normal[1] *= p; normal[2] *= p; } } int stb_box_face_vertex_axis_side(int face_number, int vertex_number, int axis) { static box_vertices[6][4][3] = { { { 1,1,1 }, { 1,0,1 }, { 1,0,0 }, { 1,1,0 } }, { { 0,0,0 }, { 0,0,1 }, { 0,1,1 }, { 0,1,0 } }, { { 0,0,0 }, { 0,1,0 }, { 1,1,0 }, { 1,0,0 } }, { { 0,0,0 }, { 1,0,0 }, { 1,0,1 }, { 0,0,1 } }, { { 1,1,1 }, { 0,1,1 }, { 0,0,1 }, { 1,0,1 } }, { { 1,1,1 }, { 1,1,0 }, { 0,1,0 }, { 0,1,1 } }, }; assert(face_number >= 0 && face_number < 6); assert(vertex_number >= 0 && vertex_number < 4); assert(axis >= 0 && axis < 3); return box_vertices[face_number][vertex_number][axis]; } void stb_linear_controller(float *curpos, float target_pos, float acc, float deacc, float dt) { float sign = 1, p, cp = *curpos; if (cp == target_pos) return; if (target_pos < cp) { target_pos = -target_pos; cp = -cp; sign = -1; } // first decelerate if (cp < 0) { p = cp + deacc * dt; if (p > 0) { p = 0; dt = dt - cp / deacc; if (dt < 0) dt = 0; } else { dt = 0; } cp = p; } // now accelerate p = cp + acc*dt; if (p > target_pos) p = target_pos; *curpos = p * sign; // @TODO: testing } float stb_quadratic_controller(float target_pos, float curpos, float maxvel, float maxacc, float dt, float *curvel) { return 0; // @TODO } int stb_float_eq(float x, float y, float delta, int max_ulps) { if (fabs(x-y) <= delta) return 1; if (abs(*(int *)&x - *(int *)&y) <= max_ulps) return 1; return 0; } int stb_is_prime(unsigned int m) { unsigned int i,j; if (m < 2) return 0; if (m == 2) return 1; if (!(m & 1)) return 0; if (m % 3 == 0) return (m == 3); for (i=5; (j=i*i), j <= m && j > i; i += 6) { if (m % i == 0) return 0; if (m % (i+2) == 0) return 0; } return 1; } unsigned int stb_power_of_two_nearest_prime(int n) { static signed char tab[32] = { 0,0,0,0,1,0,-1,0,1,-1,-1,3,-1,0,-1,2,1, 0,2,0,-1,-4,-1,5,-1,18,-2,15,2,-1,2,0 }; if (!tab[0]) { int i; for (i=0; i < 32; ++i) tab[i] = (1 << i) + 2*tab[i] - 1; tab[1] = 2; tab[0] = 1; } if (n >= 32) return 0xfffffffb; return tab[n]; } double stb_linear_remap(double x, double x_min, double x_max, double out_min, double out_max) { return stb_lerp(stb_unlerp(x,x_min,x_max),out_min,out_max); } #endif // create a macro so it's faster, but you can get at the function pointer #define stb_linear_remap(t,a,b,c,d) stb_lerp(stb_unlerp(t,a,b),c,d) ////////////////////////////////////////////////////////////////////////////// // // bit operations // #define stb_big32(c) (((c)[0]<<24) + (c)[1]*65536 + (c)[2]*256 + (c)[3]) #define stb_little32(c) (((c)[3]<<24) + (c)[2]*65536 + (c)[1]*256 + (c)[0]) #define stb_big16(c) ((c)[0]*256 + (c)[1]) #define stb_little16(c) ((c)[1]*256 + (c)[0]) STB_EXTERN int stb_bitcount(unsigned int a); STB_EXTERN unsigned int stb_bitreverse8(unsigned char n); STB_EXTERN unsigned int stb_bitreverse(unsigned int n); STB_EXTERN int stb_is_pow2(unsigned int n); STB_EXTERN int stb_log2_ceil(unsigned int n); STB_EXTERN int stb_log2_floor(unsigned int n); STB_EXTERN int stb_lowbit8(unsigned int n); STB_EXTERN int stb_highbit8(unsigned int n); #ifdef STB_DEFINE int stb_bitcount(unsigned int a) { a = (a & 0x55555555) + ((a >> 1) & 0x55555555); // max 2 a = (a & 0x33333333) + ((a >> 2) & 0x33333333); // max 4 a = (a + (a >> 4)) & 0x0f0f0f0f; // max 8 per 4, now 8 bits a = (a + (a >> 8)); // max 16 per 8 bits a = (a + (a >> 16)); // max 32 per 8 bits return a & 0xff; } unsigned int stb_bitreverse8(unsigned char n) { n = ((n & 0xAA) >> 1) + ((n & 0x55) << 1); n = ((n & 0xCC) >> 2) + ((n & 0x33) << 2); return (unsigned char) ((n >> 4) + (n << 4)); } unsigned int stb_bitreverse(unsigned int n) { n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1); n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2); n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4); n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8); return (n >> 16) | (n << 16); } int stb_is_pow2(unsigned int n) { return (n & (n-1)) == 0; } // tricky use of 4-bit table to identify 5 bit positions (note the '-1') // 3-bit table would require another tree level; 5-bit table wouldn't save one #ifdef _WIN32 #pragma warning(push) #pragma warning(disable: 4035) // disable warning about no return value int stb_log2_floor(unsigned int n) { __asm { bsr eax,n jnz done mov eax,-1 } done:; } #pragma warning(pop) #else int stb_log2_floor(unsigned int n) { static signed char log2_4[16] = { -1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3 }; // 2 compares if n < 16, 3 compares otherwise if (n < (1U << 14)) if (n < (1U << 4)) return 0 + log2_4[n ]; else if (n < (1U << 9)) return 5 + log2_4[n >> 5]; else return 10 + log2_4[n >> 10]; else if (n < (1U << 24)) if (n < (1U << 19)) return 15 + log2_4[n >> 15]; else return 20 + log2_4[n >> 20]; else if (n < (1U << 29)) return 25 + log2_4[n >> 25]; else return 30 + log2_4[n >> 30]; } #endif // define ceil from floor int stb_log2_ceil(unsigned int n) { if (stb_is_pow2(n)) return stb_log2_floor(n); else return 1 + stb_log2_floor(n); } int stb_highbit8(unsigned int n) { return stb_log2_ceil(n&255); } int stb_lowbit8(unsigned int n) { static signed char lowbit4[16] = { -1,0,1,0, 2,0,1,0, 3,0,1,0, 2,0,1,0 }; int k = lowbit4[n & 15]; if (k >= 0) return k; k = lowbit4[(n >> 4) & 15]; if (k >= 0) return k+4; return k; } #endif ////////////////////////////////////////////////////////////////////////////// // // qsort Compare Routines // #ifdef _WIN32 #define stb_stricmp(a,b) stricmp(a,b) #define stb_strnicmp(a,b,n) strnicmp(a,b,n) #else #define stb_stricmp(a,b) strcasecmp(a,b) #define stb_strnicmp(a,b,n) strncasecmp(a,b,n) #endif STB_EXTERN int (*stb_intcmp(int offset))(const void *a, const void *b); STB_EXTERN int (*stb_qsort_strcmp(int offset))(const void *a, const void *b); STB_EXTERN int (*stb_qsort_stricmp(int offset))(const void *a, const void *b); STB_EXTERN int (*stb_floatcmp(int offset))(const void *a, const void *b); STB_EXTERN int (*stb_doublecmp(int offset))(const void *a, const void *b); STB_EXTERN int (*stb_charcmp(int offset))(const void *a, const void *b); #ifdef STB_DEFINE static int stb__intcmpoffset, stb__charcmpoffset, stb__strcmpoffset; static int stb__floatcmpoffset, stb__doublecmpoffset; int stb__intcmp(const void *a, const void *b) { const int p = *(const int *) ((const char *) a + stb__intcmpoffset); const int q = *(const int *) ((const char *) b + stb__intcmpoffset); return p < q ? -1 : p > q; } int stb__charcmp(const void *a, const void *b) { const int p = *(const unsigned char *) ((const char *) a + stb__charcmpoffset); const int q = *(const unsigned char *) ((const char *) b + stb__charcmpoffset); return p < q ? -1 : p > q; } int stb__floatcmp(const void *a, const void *b) { const float p = *(const float *) ((const char *) a + stb__floatcmpoffset); const float q = *(const float *) ((const char *) b + stb__floatcmpoffset); return p < q ? -1 : p > q; } int stb__doublecmp(const void *a, const void *b) { const double p = *(const double *) ((const char *) a + stb__doublecmpoffset); const double q = *(const double *) ((const char *) b + stb__doublecmpoffset); return p < q ? -1 : p > q; } int stb__qsort_strcmp(const void *a, const void *b) { const char *p = *(const char **) ((const char *) a + stb__strcmpoffset); const char *q = *(const char **) ((const char *) b + stb__strcmpoffset); return strcmp(p,q); } int stb__qsort_stricmp(const void *a, const void *b) { const char *p = *(const char **) ((const char *) a + stb__strcmpoffset); const char *q = *(const char **) ((const char *) b + stb__strcmpoffset); return stb_stricmp(p,q); } int (*stb_intcmp(int offset))(const void *, const void *) { stb__intcmpoffset = offset; return &stb__intcmp; } int (*stb_charcmp(int offset))(const void *, const void *) { stb__charcmpoffset = offset; return &stb__charcmp; } int (*stb_qsort_strcmp(int offset))(const void *, const void *) { stb__strcmpoffset = offset; return &stb__qsort_strcmp; } int (*stb_qsort_stricmp(int offset))(const void *, const void *) { stb__strcmpoffset = offset; return &stb__qsort_stricmp; } int (*stb_floatcmp(int offset))(const void *, const void *) { stb__floatcmpoffset = offset; return &stb__floatcmp; } int (*stb_doublecmp(int offset))(const void *, const void *) { stb__doublecmpoffset = offset; return &stb__doublecmp; } #endif ////////////////////////////////////////////////////////////////////////////// // // Binary Search Toolkit // typedef struct { int minval, maxval, guess; int mode, step; } stb_search; STB_EXTERN int stb_search_binary(stb_search *s, int minv, int maxv, int find_smallest); STB_EXTERN int stb_search_open(stb_search *s, int minv, int find_smallest); STB_EXTERN int stb_probe(stb_search *s, int compare, int *result); // return 0 when done #ifdef STB_DEFINE enum { STB_probe_binary_smallest, STB_probe_binary_largest, STB_probe_open_smallest, STB_probe_open_largest, }; static int stb_probe_guess(stb_search *s, int *result) { switch(s->mode) { case STB_probe_binary_largest: if (s->minval == s->maxval) { *result = s->minval; return 0; } assert(s->minval < s->maxval); // if a < b, then a < p <= b s->guess = s->minval + (((unsigned) s->maxval - s->minval + 1) >> 1); break; case STB_probe_binary_smallest: if (s->minval == s->maxval) { *result = s->minval; return 0; } assert(s->minval < s->maxval); // if a < b, then a <= p < b s->guess = s->minval + (((unsigned) s->maxval - s->minval) >> 1); break; case STB_probe_open_smallest: case STB_probe_open_largest: s->guess = s->maxval; // guess the current maxval break; } *result = s->guess; return 1; } int stb_probe(stb_search *s, int compare, int *result) { switch(s->mode) { case STB_probe_open_smallest: case STB_probe_open_largest: { if (compare <= 0) { // then it lies within minval & maxval if (s->mode == STB_probe_open_smallest) s->mode = STB_probe_binary_smallest; else s->mode = STB_probe_binary_largest; } else { // otherwise, we need to probe larger s->minval = s->maxval + 1; s->maxval = s->minval + s->step; s->step += s->step; } break; } case STB_probe_binary_smallest: { // if compare < 0, then s->minval <= a < p // if compare = 0, then s->minval <= a <= p // if compare > 0, then p < a <= s->maxval if (compare <= 0) s->maxval = s->guess; else s->minval = s->guess+1; break; } case STB_probe_binary_largest: { // if compare < 0, then s->minval <= a < p // if compare = 0, then p <= a <= s->maxval // if compare > 0, then p < a <= s->maxval if (compare < 0) s->maxval = s->guess-1; else s->minval = s->guess; break; } } return stb_probe_guess(s, result); } int stb_search_binary(stb_search *s, int minv, int maxv, int find_smallest) { int r; if (maxv < minv) return minv-1; s->minval = minv; s->maxval = maxv; s->mode = find_smallest ? STB_probe_binary_smallest : STB_probe_binary_largest; stb_probe_guess(s, &r); return r; } int stb_search_open(stb_search *s, int minv, int find_smallest) { int r; s->step = 4; s->minval = minv; s->maxval = minv+s->step; s->mode = find_smallest ? STB_probe_open_smallest : STB_probe_open_largest; stb_probe_guess(s, &r); return r; } #endif ////////////////////////////////////////////////////////////////////////////// // // String Processing // #define stb_prefixi(s,t) (0==stb_strnicmp((s),(t),strlen(t))) enum stb_splitpath_flag { STB_PATH = 1, STB_FILE = 2, STB_EXT = 4, STB_PATH_FILE = STB_PATH + STB_FILE, STB_FILE_EXT = STB_FILE + STB_EXT, STB_EXT_NO_PERIOD = 8, }; STB_EXTERN char * stb_skipwhite(char *s); STB_EXTERN char * stb_trimwhite(char *s); STB_EXTERN char * stb_skipnewline(char *s); STB_EXTERN char * stb_strncpy(char *s, char *t, int n); STB_EXTERN char * stb_substr(char *t, int n); STB_EXTERN char * stb_duplower(char *s); STB_EXTERN void stb_tolower (char *s); STB_EXTERN char * stb_strchr2 (char *s, char p1, char p2); STB_EXTERN char * stb_strrchr2(char *s, char p1, char p2); STB_EXTERN char * stb_strtok(char *output, char *src, char *delimit); STB_EXTERN char * stb_strtok_keep(char *output, char *src, char *delimit); STB_EXTERN char * stb_strtok_invert(char *output, char *src, char *allowed); STB_EXTERN char * stb_dupreplace(char *s, char *find, char *replace); STB_EXTERN void stb_replaceinplace(char *s, char *find, char *replace); STB_EXTERN char * stb_splitpath(char *output, char *src, int flag); STB_EXTERN char * stb_splitpathdup(char *src, int flag); STB_EXTERN char * stb_replacedir(char *output, char *src, char *dir); STB_EXTERN char * stb_replaceext(char *output, char *src, char *ext); STB_EXTERN void stb_fixpath(char *path); STB_EXTERN int stb_suffix (char *s, char *t); STB_EXTERN int stb_suffixi(char *s, char *t); STB_EXTERN int stb_prefix (char *s, char *t); STB_EXTERN char * stb_strichr(char *s, char t); STB_EXTERN char * stb_stristr(char *s, char *t); STB_EXTERN int stb_prefix_count(char *s, char *t); STB_EXTERN char * stb_plural(int n); // "s" or "" STB_EXTERN char **stb_tokens(char *src, char *delimit, int *count); STB_EXTERN char **stb_tokens_nested(char *src, char *delimit, int *count, char *nest_in, char *nest_out); STB_EXTERN char **stb_tokens_nested_empty(char *src, char *delimit, int *count, char *nest_in, char *nest_out); STB_EXTERN char **stb_tokens_allowempty(char *src, char *delimit, int *count); STB_EXTERN char **stb_tokens_stripwhite(char *src, char *delimit, int *count); STB_EXTERN char **stb_tokens_withdelim(char *src, char *delimit, int *count); STB_EXTERN char **stb_tokens_quoted(char *src, char *delimit, int *count); // with 'quoted', allow delimiters to appear inside quotation marks, and don't // strip whitespace inside them (and we delete the quotation marks unless they // appear back to back, in which case they're considered escaped) #ifdef STB_DEFINE char *stb_plural(int n) { return n == 1 ? "" : "s"; } int stb_prefix(char *s, char *t) { while (*t) if (*s++ != *t++) return STB_FALSE; return STB_TRUE; } int stb_prefix_count(char *s, char *t) { int c=0; while (*t) { if (*s++ != *t++) break; ++c; } return c; } int stb_suffix(char *s, char *t) { size_t n = strlen(s); size_t m = strlen(t); if (m <= n) return 0 == strcmp(s+n-m, t); else return 0; } int stb_suffixi(char *s, char *t) { size_t n = strlen(s); size_t m = strlen(t); if (m <= n) return 0 == stb_stricmp(s+n-m, t); else return 0; } // originally I was using this table so that I could create known sentinel // values--e.g. change whitetable[0] to be true if I was scanning for whitespace, // and false if I was scanning for nonwhite. I don't appear to be using that // functionality anymore (I do for tokentable, though), so just replace it // with isspace() char *stb_skipwhite(char *s) { while (isspace((unsigned char) *s)) ++s; return s; } char *stb_skipnewline(char *s) { if (s[0] == '\r' || s[0] == '\n') { if (s[0]+s[1] == '\r' + '\n') ++s; ++s; } return s; } char *stb_trimwhite(char *s) { int i,n; s = stb_skipwhite(s); n = (int) strlen(s); for (i=n-1; i >= 0; --i) if (!isspace(s[i])) break; s[i+1] = 0; return s; } char *stb_strncpy(char *s, char *t, int n) { strncpy(s,t,n); s[n-1] = 0; return s; } char *stb_substr(char *t, int n) { char *a; int z = (int) strlen(t); if (z < n) n = z; a = (char *) malloc(n+1); strncpy(a,t,n); a[n] = 0; return a; } char *stb_duplower(char *s) { char *p = strdup(s), *q = p; while (*q) { *q = tolower(*q); ++q; } return p; } void stb_tolower(char *s) { while (*s) { *s = tolower(*s); ++s; } } char *stb_strchr2(char *s, char x, char y) { for(; *s; ++s) if (*s == x || *s == y) return s; return NULL; } char *stb_strrchr2(char *s, char x, char y) { char *r = NULL; for(; *s; ++s) if (*s == x || *s == y) r = s; return r; } char *stb_strichr(char *s, char t) { if (tolower(t) == toupper(t)) return strchr(s,t); return stb_strchr2(s, (char) tolower(t), (char) toupper(t)); } char *stb_stristr(char *s, char *t) { size_t n = strlen(t); char *z; if (n==0) return s; while ((z = stb_strichr(s, *t)) != NULL) { if (0==stb_strnicmp(z, t, n)) return z; s = z+1; } return NULL; } static char *stb_strtok_raw(char *output, char *src, char *delimit, int keep, int invert) { if (invert) { while (*src && strchr(delimit, *src) != NULL) { *output++ = *src++; } } else { while (*src && strchr(delimit, *src) == NULL) { *output++ = *src++; } } *output = 0; if (keep) return src; else return *src ? src+1 : src; } char *stb_strtok(char *output, char *src, char *delimit) { return stb_strtok_raw(output, src, delimit, 0, 0); } char *stb_strtok_keep(char *output, char *src, char *delimit) { return stb_strtok_raw(output, src, delimit, 1, 0); } char *stb_strtok_invert(char *output, char *src, char *delimit) { return stb_strtok_raw(output, src, delimit, 1,1); } static char **stb_tokens_raw(char *src_, char *delimit, int *count, int stripwhite, int allow_empty, char *start, char *end) { int nested = 0; unsigned char *src = (unsigned char *) src_; static char stb_tokentable[256]; // rely on static initializion to 0 static char stable[256],etable[256]; char *out; char **result; int num=0; unsigned char *s; s = (unsigned char *) delimit; while (*s) stb_tokentable[*s++] = 1; if (start) { s = (unsigned char *) start; while (*s) stable[*s++] = 1; s = (unsigned char *) end; if (s) while (*s) stable[*s++] = 1; s = (unsigned char *) end; if (s) while (*s) etable[*s++] = 1; } stable[0] = 1; // two passes through: the first time, counting how many s = (unsigned char *) src; while (*s) { // state: just found delimiter // skip further delimiters if (!allow_empty) { stb_tokentable[0] = 0; while (stb_tokentable[*s]) ++s; if (!*s) break; } ++num; // skip further non-delimiters stb_tokentable[0] = 1; if (stripwhite == 2) { // quoted strings while (!stb_tokentable[*s]) { if (*s != '"') ++s; else { ++s; if (*s == '"') ++s; // "" -> ", not start a string else { // begin a string while (*s) { if (s[0] == '"') { if (s[1] == '"') s += 2; // "" -> " else { ++s; break; } // terminating " } else ++s; } } } } } else while (nested || !stb_tokentable[*s]) { if (stable[*s]) { if (!*s) break; if (end ? etable[*s] : nested) --nested; else ++nested; } ++s; } if (allow_empty) { if (*s) ++s; } } // now num has the actual count... malloc our output structure // need space for all the strings: strings won't be any longer than // original input, since for every '\0' there's at least one delimiter result = (char **) malloc(sizeof(*result) * (num+1) + (s-src+1)); if (result == NULL) return result; out = (char *) (result + (num+1)); // second pass: copy out the data s = (unsigned char *) src; num = 0; nested = 0; while (*s) { char *last_nonwhite; // state: just found delimiter // skip further delimiters if (!allow_empty) { stb_tokentable[0] = 0; if (stripwhite) while (stb_tokentable[*s] || isspace(*s)) ++s; else while (stb_tokentable[*s]) ++s; } else if (stripwhite) { while (isspace(*s)) ++s; } if (!*s) break; // we're past any leading delimiters and whitespace result[num] = out; ++num; // copy non-delimiters stb_tokentable[0] = 1; last_nonwhite = out-1; if (stripwhite == 2) { while (!stb_tokentable[*s]) { if (*s != '"') { if (!isspace(*s)) last_nonwhite = out; *out++ = *s++; } else { ++s; if (*s == '"') { if (!isspace(*s)) last_nonwhite = out; *out++ = *s++; // "" -> ", not start string } else { // begin a quoted string while (*s) { if (s[0] == '"') { if (s[1] == '"') { *out++ = *s; s += 2; } else { ++s; break; } // terminating " } else *out++ = *s++; } last_nonwhite = out-1; // all in quotes counts as non-white } } } } else { while (nested || !stb_tokentable[*s]) { if (!isspace(*s)) last_nonwhite = out; if (stable[*s]) { if (!*s) break; if (end ? etable[*s] : nested) --nested; else ++nested; } *out++ = *s++; } } if (stripwhite) // rewind to last non-whitespace char out = last_nonwhite+1; *out++ = '\0'; if (*s) ++s; // skip delimiter } s = (unsigned char *) delimit; while (*s) stb_tokentable[*s++] = 0; if (start) { s = (unsigned char *) start; while (*s) stable[*s++] = 1; s = (unsigned char *) end; if (s) while (*s) stable[*s++] = 1; s = (unsigned char *) end; if (s) while (*s) etable[*s++] = 1; } if (count != NULL) *count = num; result[num] = 0; return result; } char **stb_tokens(char *src, char *delimit, int *count) { return stb_tokens_raw(src,delimit,count,0,0,0,0); } char **stb_tokens_nested(char *src, char *delimit, int *count, char *nest_in, char *nest_out) { return stb_tokens_raw(src,delimit,count,0,0,nest_in,nest_out); } char **stb_tokens_nested_empty(char *src, char *delimit, int *count, char *nest_in, char *nest_out) { return stb_tokens_raw(src,delimit,count,0,1,nest_in,nest_out); } char **stb_tokens_allowempty(char *src, char *delimit, int *count) { return stb_tokens_raw(src,delimit,count,0,1,0,0); } char **stb_tokens_stripwhite(char *src, char *delimit, int *count) { return stb_tokens_raw(src,delimit,count,1,1,0,0); } char **stb_tokens_quoted(char *src, char *delimit, int *count) { return stb_tokens_raw(src,delimit,count,2,1,0,0); } char *stb_dupreplace(char *src, char *find, char *replace) { size_t len_find = strlen(find); size_t len_replace = strlen(replace); int count = 0; char *s,*p,*q; s = strstr(src, find); if (s == NULL) return strdup(src); do { ++count; s = strstr(s + len_find, find); } while (s != NULL); p = (char *) malloc(strlen(src) + count * (len_replace - len_find) + 1); if (p == NULL) return p; q = p; s = src; for (;;) { char *t = strstr(s, find); if (t == NULL) { strcpy(q,s); assert(strlen(p) == strlen(src) + count*(len_replace-len_find)); return p; } memcpy(q, s, t-s); q += t-s; memcpy(q, replace, len_replace); q += len_replace; s = t + len_find; } } void stb_replaceinplace(char *src, char *find, char *replace) { size_t len_find = strlen(find); size_t len_replace = strlen(replace); int count = 0, delta; char *s,*p,*q; delta = len_replace - len_find; assert(delta <= 0); if (delta > 0) return; p = strstr(src, find); if (p == NULL) return; s = q = p; while (*s) { memcpy(q, replace, len_replace); p += len_find; q += len_replace; s = strstr(p, find); if (s == NULL) s = p + strlen(p); memmove(q, p, s-p); q += s-p; p = s; } *q = 0; } void stb_fixpath(char *path) { for(; *path; ++path) if (*path == '\\') *path = '/'; } static char *stb__splitpath_raw(char *buffer, char *path, int flag) { int len=0,x,y, n = (int) strlen(path), f1,f2; char *s = stb_strrchr2(path, '/', '\\'); char *t = strrchr(path, '.'); if (s && t && t < s) t = NULL; if (s) ++s; if (flag == STB_EXT_NO_PERIOD) flag |= STB_EXT; if (!(flag & (STB_PATH | STB_FILE | STB_EXT))) return NULL; f1 = s == NULL ? 0 : s-path; // start of filename f2 = t == NULL ? n : t-path; // just past end of filename if (flag & STB_PATH) { x = 0; if (f1 == 0 && flag == STB_PATH) len=2; } else if (flag & STB_FILE) { x = f1; } else { x = f2; if (flag & STB_EXT_NO_PERIOD) if (buffer[x] == '.') ++x; } if (flag & STB_EXT) y = n; else if (flag & STB_FILE) y = f2; else y = f1; if (buffer == NULL) { buffer = (char *) malloc(y-x + len + 1); if (!buffer) return NULL; } if (len) { strcpy(buffer, "./"); return buffer; } strncpy(buffer, path+x, y-x); buffer[y-x] = 0; return buffer; } char *stb_splitpath(char *output, char *src, int flag) { return stb__splitpath_raw(output, src, flag); } char *stb_splitpathdup(char *src, int flag) { return stb__splitpath_raw(NULL, src, flag); } char *stb_replacedir(char *output, char *src, char *dir) { char buffer[4096]; stb_splitpath(buffer, src, STB_FILE | STB_EXT); if (dir) sprintf(output, "%s/%s", dir, buffer); else strcpy(output, buffer); return output; } char *stb_replaceext(char *output, char *src, char *ext) { char buffer[4096]; stb_splitpath(buffer, src, STB_PATH | STB_FILE); if (ext) sprintf(output, "%s.%s", buffer, ext[0] == '.' ? ext+1 : ext); else strcpy(output, buffer); return output; } #endif ////////////////////////////////////////////////////////////////////////////// // // stb_alloc - hierarchical allocator // // inspired by http://swapped.cc/halloc // // // When you alloc a given block through stb_alloc, you have these choices: // // 1. does it have a parent? // 2. can it have children? // 3. can it be freed directly? // 4. is it transferrable? // 5. what is its alignment? // // Here are interesting combinations of those: // // children free transfer alignment // arena Y Y N n/a // no-overhead, chunked N N N normal // string pool alloc N N N 1 // parent-ptr, chunked Y N N normal // low-overhead, unchunked N Y Y normal // general purpose alloc Y Y Y normal // // Unchunked allocations will probably return 16-aligned pointers. If // we 16-align the results, we have room for 4 pointers. For smaller // allocations that allow finer alignment, we can reduce the pointers. // // The strategy is that given a pointer, assuming it has a header (only // the no-overhead allocations have no header), we can determine the // type of the header fields, and the number of them, by stepping backwards // through memory and looking at the tags in the bottom bits. // // Implementation strategy: // chunked allocations come from the middle of chunks, and can't // be freed. thefore they do not need to be on a sibling chain. // they may need child pointers if they have children. // // chunked, with-children // void *parent; // // unchunked, no-children -- reduced storage // void *next_sibling; // void *prev_sibling_nextp; // // unchunked, general // void *first_child; // void *next_sibling; // void *prev_sibling_nextp; // void *chunks; // // so, if we code each of these fields with different bit patterns // (actually same one for next/prev/child), then we can identify which // each one is from the last field. STB_EXTERN void stb_free(void *p); STB_EXTERN void *stb_malloc_global(size_t size); STB_EXTERN void *stb_malloc(void *context, size_t size); STB_EXTERN void *stb_malloc_nofree(void *context, size_t size); STB_EXTERN void *stb_malloc_leaf(void *context, size_t size); STB_EXTERN void *stb_malloc_raw(void *context, size_t size); STB_EXTERN void *stb_realloc(void *ptr, size_t newsize); STB_EXTERN void stb_reassign(void *new_context, void *ptr); STB_EXTERN void stb_malloc_validate(void *p, void *parent); extern int stb_alloc_chunk_size ; extern int stb_alloc_count_free ; extern int stb_alloc_count_alloc; extern int stb_alloc_alignment ; #ifdef STB_DEFINE int stb_alloc_chunk_size = 65536; int stb_alloc_count_free = 0; int stb_alloc_count_alloc = 0; int stb_alloc_alignment = -16; typedef struct stb__chunk { struct stb__chunk *next; int data_left; int alloc; } stb__chunk; typedef struct { void * next; void ** prevn; } stb__nochildren; typedef struct { void ** prevn; void * child; void * next; stb__chunk *chunks; } stb__alloc; typedef struct { stb__alloc *parent; } stb__chunked; #define STB__PARENT 1 #define STB__CHUNKS 2 typedef enum { STB__alloc = STB__CHUNKS, STB__chunked = STB__PARENT, STB__nochildren = 0, STB__chunk_raw = 4, } stb__alloc_type; #define STB__DECODE(x,v) ((void *) ((char *) (x) - (v))) #define STB__ENCODE(x,v) ((void *) ((char *) (x) + (v))) #define stb__parent(z) (stb__alloc *) STB__DECODE((z)->parent, STB__PARENT) #define stb__chunks(z) (stb__chunk *) STB__DECODE((z)->chunks, STB__CHUNKS) #define stb__setparent(z,p) (z)->parent = (stb__alloc *) STB__ENCODE((p), STB__PARENT) #define stb__setchunks(z,c) (z)->chunks = (stb__chunk *) STB__ENCODE((c), STB__CHUNKS) static stb__alloc stb__alloc_global = { NULL, NULL, NULL, (stb__chunk *) STB__ENCODE(NULL, STB__CHUNKS) }; static stb__alloc_type stb__identify(void *p) { void **q = (void **) p; assert(sizeof(int) == sizeof(*q)); // @TODO: deal with sizeof(pointer) != sizeof(int) return (stb__alloc_type) (((int *) q)[-1] & 3); } static void *** stb__prevn(void *p) { if (stb__identify(p) == STB__alloc) { stb__alloc *s = (stb__alloc *) p - 1; return &s->prevn; } else { stb__nochildren *s = (stb__nochildren *) p - 1; return &s->prevn; } } void stb_free(void *p) { if (p == NULL) return; // count frees so that unit tests can see what's happening ++stb_alloc_count_free; switch(stb__identify(p)) { case STB__chunked: // freeing a chunked-block with children does nothing; // they only get freed when the parent does // surely this is wrong, and it should free them immediately? // otherwise how are they getting put on the right chain? return; case STB__nochildren: { stb__nochildren *s = (stb__nochildren *) p - 1; // unlink from sibling chain *(s->prevn) = s->next; if (s->next) *stb__prevn(s->next) = s->prevn; free(s); return; } case STB__alloc: { stb__alloc *s = (stb__alloc *) p - 1; stb__chunk *c, *n; void *q; // unlink from sibling chain, if any *(s->prevn) = s->next; if (s->next) *stb__prevn(s->next) = s->prevn; // first free chunks c = (stb__chunk *) stb__chunks(s); while (c != NULL) { n = c->next; stb_alloc_count_free += c->alloc; free(c); c = n; } // validating stb__setchunks(s,NULL); s->prevn = NULL; s->next = NULL; // now free children while ((q = s->child) != NULL) { stb_free(q); } // now free self free(s); return; } default: assert(0); /* NOTREACHED */ } } void stb_malloc_validate(void *p, void *parent) { if (p == NULL) return; switch(stb__identify(p)) { case STB__chunked: // freeing a chunked-block with children does nothing; // they only get freed when the parent does return; case STB__nochildren: { stb__nochildren *n = (stb__nochildren *) p - 1; if (n->prevn) assert(*n->prevn == p); if (n->next) { assert(*stb__prevn(n->next) == &n->next); stb_malloc_validate(n, parent); } return; } case STB__alloc: { stb__alloc *s = (stb__alloc *) p - 1; if (s->prevn) assert(*s->prevn == p); if (s->child) { assert(*stb__prevn(s->child) == &s->child); stb_malloc_validate(s->child, p); } if (s->next) { assert(*stb__prevn(s->next) == &s->next); stb_malloc_validate(s->next, parent); } return; } default: assert(0); /* NOTREACHED */ } } static void * stb__try_chunk(stb__chunk *c, int size, int align, int pre_align) { char *memblock = (char *) (c+1), *q; int iq, start_offset; // we going to allocate at the end of the chunk, not the start. confusing, // but it means we don't need both a 'limit' and a 'cur', just a 'cur'. // the block ends at: p + c->data_left // then we move back by size start_offset = c->data_left - size; // now we need to check the alignment of that q = memblock + start_offset; iq = (int) q; assert(sizeof(q) == sizeof(iq)); // suppose align = 2 // then we need to retreat iq far enough that (iq & (2-1)) == 0 // to get (iq & (align-1)) = 0 requires subtracting (iq & (align-1)) start_offset -= iq & (align-1); assert(((int) (memblock+start_offset) & (align-1)) == 0); // now, if that + pre_align works, go for it! start_offset -= pre_align; if (start_offset >= 0) { c->data_left = start_offset; return memblock + start_offset; } return NULL; } static void stb__sort_chunks(stb__alloc *src) { stb__chunk *c = stb__chunks(src), *d; if (c == NULL) return; d = c->next; if (d == NULL) return; if (c->data_left > d->data_left) return; c->next = d->next; d->next = c; stb__setchunks(src, d); } static void * stb__alloc_chunk(stb__alloc *src, int size, int align, int pre_align) { void *p; stb__chunk *c = stb__chunks(src); if (c && size <= stb_alloc_chunk_size) { p = stb__try_chunk(c, size, align, pre_align); if (p) { ++c->alloc; return p; } // try a second chunk to reduce wastage if (c->next) { p = stb__try_chunk(c->next, size, align, pre_align); if (p) { ++c->alloc; return p; } // put the bigger chunk first, since the second will get buried // the upshot of this is that, until it gets allocated from, chunk #2 // is always the largest remaining chunk. (could formalize // this with a heap!) stb__sort_chunks(src); c = stb__chunks(src); } } // allocate a new chunk { stb__chunk *n; int chunk_size = stb_alloc_chunk_size; // we're going to allocate a new chunk to put this in if (size > chunk_size) chunk_size = size; assert(sizeof(*n) + pre_align <= 16); // loop trying to allocate a large enough chunk // the loop is because the alignment may cause problems if it's big while (1) { n = (stb__chunk *) malloc(16 + chunk_size); if (n == NULL) return NULL; n->data_left = chunk_size - sizeof(*n); p = stb__try_chunk(n, size, align, pre_align); if (p != NULL) { n->next = c; stb__setchunks(src, n); // if we just used up the whole block immediately, // move the following chunk up n->alloc = 1; if (size == chunk_size) stb__sort_chunks(src); return p; } free(n); chunk_size += 16+align; } } } static stb__alloc * stb__get_context(void *context) { if (context == NULL) { return &stb__alloc_global; } else { int u = stb__identify(context); // if context is chunked, grab parent if (u == STB__chunked) { stb__chunked *s = (stb__chunked *) context - 1; return stb__parent(s); } else { return (stb__alloc *) context - 1; } } } static void stb__insert_alloc(stb__alloc *src, stb__alloc *s) { s->prevn = &src->child; s->next = src->child; src->child = s+1; if (s->next) *stb__prevn(s->next) = &s->next; } static void stb__insert_nochild(stb__alloc *src, stb__nochildren *s) { s->prevn = &src->child; s->next = src->child; src->child = s+1; if (s->next) *stb__prevn(s->next) = &s->next; } static void * malloc_base(void *context, size_t size, stb__alloc_type t, int align) { void *p; stb__alloc *src = stb__get_context(context); if (align <= 0) { // compute worst-case C packed alignment // e.g. a 24-byte struct is 8-aligned int align_proposed = 1 << stb_lowbit8(size); if (align_proposed < 0) align_proposed = 4; if (align_proposed == 0) { if (size == 0) align_proposed = 1; else align_proposed = 256; } // a negative alignment means 'don't align any larger // than this'; so -16 means we align 1,2,4,8, or 16 if (align < 0) { if (align_proposed > -align) align_proposed = -align; } align = align_proposed; } assert(stb_is_pow2(align)); // don't cause misalignment when allocating nochildren if (t == STB__nochildren && align > 8) t = STB__alloc; switch (t) { case STB__alloc: { stb__alloc *s = (stb__alloc *) malloc(size + sizeof(*s)); if (s == NULL) return NULL; p = s+1; s->child = NULL; stb__insert_alloc(src, s); stb__setchunks(s,NULL); break; } case STB__nochildren: { stb__nochildren *s = (stb__nochildren *) malloc(size + sizeof(*s)); if (s == NULL) return NULL; p = s+1; stb__insert_nochild(src, s); break; } case STB__chunk_raw: { p = stb__alloc_chunk(src, size, align, 0); if (p == NULL) return NULL; break; } case STB__chunked: { stb__chunked *s; if (align < 4) align = 4; s = (stb__chunked *) stb__alloc_chunk(src, size, align, sizeof(*s)); if (s == NULL) return NULL; stb__setparent(s, src); p = s+1; break; } default: assert(0); /* NOTREACHED */ } ++stb_alloc_count_alloc; return p; } void *stb_malloc_global(size_t size) { return malloc_base(NULL, size, STB__alloc, stb_alloc_alignment); } void *stb_malloc(void *context, size_t size) { return malloc_base(context, size, STB__alloc, stb_alloc_alignment); } void *stb_malloc_nofree(void *context, size_t size) { return malloc_base(context, size, STB__chunked, stb_alloc_alignment); } void *stb_malloc_leaf(void *context, size_t size) { return malloc_base(context, size, STB__nochildren, stb_alloc_alignment); } void *stb_malloc_raw(void *context, size_t size) { return malloc_base(context, size, STB__chunk_raw, stb_alloc_alignment); } char *stb_malloc_string(void *context, size_t size) { return (char *) malloc_base(context, size, STB__chunk_raw, 1); } void *stb_realloc(void *ptr, size_t newsize) { stb__alloc_type t; if (ptr == NULL) return stb_malloc(NULL, newsize); if (newsize == 0) { stb_free(ptr); return NULL; } t = stb__identify(ptr); assert(t == STB__alloc || t == STB__nochildren); if (t == STB__alloc) { stb__alloc *s = (stb__alloc *) ptr - 1; s = (stb__alloc *) realloc(s, newsize + sizeof(*s)); if (s == NULL) return NULL; ptr = s+1; // update pointers (*s->prevn) = ptr; if (s->next) *stb__prevn(s->next) = &s->next; if (s->child) *stb__prevn(s->child) = &s->child; return ptr; } else { stb__nochildren *s = (stb__nochildren *) ptr - 1; s = (stb__nochildren *) realloc(ptr, newsize + sizeof(s)); if (s == NULL) return NULL; // update pointers (*s->prevn) = s+1; if (s->next) *stb__prevn(s->next) = &s->next; return s+1; } } void *stb_realloc_c(void *context, void *ptr, size_t newsize) { if (ptr == NULL) return stb_malloc(context, newsize); if (newsize == 0) { stb_free(ptr); return NULL; } // @TODO: verify you haven't changed contexts return stb_realloc(ptr, newsize); } void stb_reassign(void *new_context, void *ptr) { stb__alloc *src = stb__get_context(new_context); stb__alloc_type t = stb__identify(ptr); assert(t == STB__alloc || t == STB__nochildren); if (t == STB__alloc) { stb__alloc *s = (stb__alloc *) ptr - 1; // unlink from old *(s->prevn) = s->next; if (s->next) *stb__prevn(s->next) = s->prevn; stb__insert_alloc(src, s); } else { stb__nochildren *s = (stb__nochildren *) ptr - 1; // unlink from old *(s->prevn) = s->next; if (s->next) *stb__prevn(s->next) = s->prevn; stb__insert_nochild(src, s); } } #endif ////////////////////////////////////////////////////////////////////////////// // // stb_arr // // An stb_arr is directly useable as a pointer (use the actual type in your // definition), but when it resizes, it returns a new pointer and you can't // use the old one, so you have to be careful to copy-in-out as necessary. // // Use a NULL pointer as a 0-length array. // // float *my_array = NULL, *temp; // // // add elements on the end one at a time // stb_arr_push(my_array, 0.0f); // stb_arr_push(my_array, 1.0f); // stb_arr_push(my_array, 2.0f); // // assert(my_array[1] == 2.0f); // // // add an uninitialized element at the end, then assign it // *stb_arr_add(my_array) = 3.0f; // // // add three uninitialized elements at the end // temp = stb_arr_addn(my_array,3); // temp[0] = 4.0f; // temp[1] = 5.0f; // temp[2] = 6.0f; // // assert(my_array[5] == 5.0f); // // // remove the last one // stb_arr_pop(my_array); // // assert(stb_arr_len(my_array) == 6); #ifdef STB_MALLOC_WRAPPER #define STB__PARAMS , char *file, int line #define STB__ARGS , file, line #else #define STB__PARAMS #define STB__ARGS #endif // calling this function allocates an empty stb_arr attached to p // (whereas NULL isn't attached to anything) STB_EXTERN void stb_arr_malloc(void **target, void *context); // call this function with a non-NULL value to have all successive // stbs that are created be attached to the associated parent. Note // that once a given stb_arr is non-empty, it stays attached to its // current parent, even if you call this function again. // it turns the previous value, so you can restore it STB_EXTERN void* stb_arr_malloc_parent(void *p); // simple functions written on top of other functions #define stb_arr_empty(a) ( stb_arr_len(a) == 0 ) #define stb_arr_add(a) ( stb_arr_addn((a),1) ) #define stb_arr_push(a,v) ( *stb_arr_add(a)=(v) ) #ifdef __cplusplus #define STB__CAST(x) (x).cast() #else #define STB__CAST(x) ((stb__arr *) (x)) #endif typedef struct { int len, limit; int stb_malloc; unsigned int signature; } stb__arr; #define stb_arr_signature 0x51bada7b // ends with 0123 in decimal // access the header block stored before the data #define stb_arrhead(a) /*lint --e(826)*/ (STB__CAST(a) - 1) #define stb_arrhead2(a) /*lint --e(826)*/ (((stb__arr *) (a)) - 1) #ifdef STB_DEBUG #define stb_arr_check(a) assert(!a || stb_arrhead(a)->signature == stb_arr_signature) #define stb_arr_check2(a) assert(!a || stb_arrhead2(a)->signature == stb_arr_signature) #else #define stb_arr_check(a) 0 #define stb_arr_check2(a) 0 #endif // ARRAY LENGTH // get the array length; special case if pointer is NULL #define stb_arr_len(a) (STB__CAST(a) ? stb_arrhead(a)->len : 0) #define stb_arr_len2(a) ((stb__arr *) (a) ? stb_arrhead2(a)->len : 0) #define stb_arr_lastn(a) (stb_arr_len(a)-1) // check whether a given index is valid -- tests 0 <= i < stb_arr_len(a) #define stb_arr_valid(a,i) (STB__CAST(a) ? (int) (i) < stb_arrhead(a)->len : 0) // change the array length so is is exactly N entries long, creating // uninitialized entries as needed #define stb_arr_setlen(a,n) \ ((a)=stb__arr_setlen((a), sizeof(a[0]), (n))) // change the array length so that N is a valid index (that is, so // it is at least N entries long), creating uninitialized entries as needed #define stb_arr_makevalid(a,n) \ (stb_arr_len(a) < (n)+1 ? stb_arr_setlen((a),(n)+1) : (a)) // remove the last element of the array, returning it #define stb_arr_pop(a) ((stb_arr_check(a), (a))[--stb_arrhead(a)->len]) // access the last element in the array #define stb_arr_last(a) ((stb_arr_check(a), (a))[stb_arr_len(a)-1]) // is iterator at end of list? #define stb_arr_end(a,i) ((i) >= &(a)[stb_arr_len(a)]) // (internal) change the allocated length of the array #define stb_arr__grow(a,n) (stb_arr_check(a), stb_arrhead(a)->len += (n)) // add N new unitialized elements to the end of the array #define stb_arr__addn(a,n) /*lint --e(826)*/ \ ((stb_arr_len(a)+(n) > stb_arrcurmax(a)) \ ? ((a)=stb__arr_addlen((a),sizeof(*a),(n))) \ : ((stb_arr__grow(a,n), (a)))) // add N new unitialized elements to the end of the array, and return // a pointer to the first new one #define stb_arr_addn(a,n) (stb_arr__addn(a,n),(a)+stb_arr_len(a)-(n)) // add N new uninitialized elements starting at index 'i' #define stb_arr_insertn(a,i,n) ((a) = stb__arr_insertn(a, sizeof(*a), i, n)) // insert an element at i #define stb_arr_insert(a,i,v) ((a) = stb__arr_insertn(a, sizeof(*a), i, n), ((a)[i] = v)) // delete N elements from the middle starting at index 'i' #define stb_arr_deleten(a,i,n) ((a) = stb__arr_deleten(a, sizeof(*a), i, n)) // delete the i'th element #define stb_arr_delete(a,i) stb_arr_deleten(a,i,1) // delete the i'th element, swapping down from the end #define stb_arr_fastdelete(a,i) \ (stb_swap(&a[i], &a[stb_arrhead(a)->len-1], sizeof(*a)), stb_arr_pop(a)) // ARRAY STORAGE // get the array maximum storage; special case if NULL #define stb_arrcurmax(a) (STB__CAST(a) ? stb_arrhead(a)->limit : 0) #define stb_arrcurmax2(a) ((a) ? stb_arrhead2(a)->limit : 0) // set the maxlength of the array to n in anticipation of further growth #define stb_arr_setsize(a,n) (stb_arr_check(a), (a)=stb__arr_setsize(a,sizeof((a)[0]),n)) // make sure maxlength is large enough for at least N new allocations #define stb_arr_atleast(a,n) (stb_arr_len(a)+(n) > stb_arrcurmax(a) \ ? stb_arr_setsize((a), (n)) : 0) // make a copy of a given array (copies contents via 'memcpy'!) #define stb_arr_copy(a) stb__arr_copy(a, sizeof((a)[0])) // compute the storage needed to store all the elements of the array #define stb_arr_storage(a) (stb_arr_len(a) * sizeof((a)[0])) #define stb_arr_for(v,arr) for((v)=(arr); (v) < (arr)+stb_arr_len(arr); ++(v)) // IMPLEMENTATION STB_EXTERN void *stb_arr_free_(void *p); STB_EXTERN void *stb__arr_copy_(void *p, int elem_size); STB_EXTERN void *stb__arr_setsize_(void *p, int size, int limit STB__PARAMS); STB_EXTERN void *stb__arr_setlen_(void *p, int size, int newlen STB__PARAMS); STB_EXTERN void *stb__arr_addlen_(void *p, int size, int addlen STB__PARAMS); STB_EXTERN void *stb__arr_deleten_(void *p, int size, int loc, int n STB__PARAMS); STB_EXTERN void *stb__arr_insertn_(void *p, int size, int loc, int n STB__PARAMS); #ifdef __cplusplus // in C++, wrap all the above function calls in a template to avoid type error #define STB__ARR(t) stb_arr template struct stb_arr { T *ptr; // constructors stb_arr(void *p) { ptr = (T *) p; } stb_arr() { ptr = NULL; } // operator overloads operator T*() { return ptr; } stb__arr * cast() { return (stb__arr *) ptr; } T& operator[] (unsigned i) { return ptr[i]; } T& operator[] (int i ) { return ptr[i]; } stb_arr stb_arr_free__() { return stb_arr(stb_arr_free_(ptr)); } stb_arr stb__arr_copy__(int elem_size) { return stb_arr(stb__arr_copy_(ptr,elem_size)); } stb_arr stb__arr_setsize__(int size, int limit STB__PARAMS) { return stb_arr(stb__arr_setsize_(ptr, size, limit STB__ARGS)); } stb_arr stb__arr_setlen__(int size, int newlen STB__PARAMS) { return stb_arr(stb__arr_setlen_(ptr, size, newlen STB__ARGS)); } stb_arr stb__arr_addlen__(int size, int addlen STB__PARAMS) { return stb_arr(stb__arr_addlen_(ptr, size, addlen STB__ARGS)); } stb_arr stb__arr_deleten__(int size, int loc, int n STB__PARAMS) { return stb_arr(stb__arr_deleten_(ptr, size, loc, n STB__ARGS)); } stb_arr stb__arr_insertn__(int size, int loc, int n STB__PARAMS) { return stb_arr(stb__arr_insertn_(ptr, size, loc, n STB__ARGS)); } }; #define stb_arr_free(p) (p).stb_arr_free__() #define stb__arr_copy(p,e) (p).stb__arr_copy__(e) #ifndef STB_MALLOC_WRAPPER #define stb__arr_setsize(p,s,n) (p).stb__arr_setsize__(s,n) #define stb__arr_setlen(p,s,n) (p).stb__arr_setlen__(s,n) #define stb__arr_addlen(p,s,n) (p).stb__arr_addlen__(s,n) #define stb__arr_deleten(p,s,i,n) (p).stb__arr_deleten__(s,i,n) #define stb__arr_insertn(p,s,i,n) (p).stb__arr_insertn__(s,i,n) #else #define stb__arr_setsize(p,s,n) (p).stb__arr_setsize__(s,n,__FILE__,__LINE__) #define stb__arr_setlen(p,s,n) (p).stb__arr_setlen__(s,n,__FILE__,__LINE__) #define stb__arr_addlen(p,s,n) (p).stb__arr_addlen__(s,n,__FILE__,__LINE__) #define stb__arr_deleten(p,s,i,n) (p).stb__arr_deleten__(s,i,n,__FILE__,__LINE__) #define stb__arr_insertn(p,s,i,n) (p).stb__arr_insertn__(s,i,n,__FILE__,__LINE__) #endif #else #define STB__ARR(t) t * #define stb_arr_free stb_arr_free_ #define stb__arr_copy stb__arr_copy_ #ifndef STB_MALLOC_WRAPPER #define stb__arr_setsize stb__arr_setsize_ #define stb__arr_setlen stb__arr_setlen_ #define stb__arr_addlen stb__arr_addlen_ #define stb__arr_deleten stb__arr_deleten_ #define stb__arr_insertn stb__arr_insertn_ #else #define stb__arr_addlen(p,s,n) stb__arr_addlen_(p,s,n,__FILE__,__LINE__) #define stb__arr_setlen(p,s,n) stb__arr_setlen_(p,s,n,__FILE__,__LINE__) #define stb__arr_setsize(p,s,n) stb__arr_setsize_(p,s,n,__FILE__,__LINE__) #define stb__arr_deleten(p,s,i,n) stb__arr_deleten_(p,s,i,n,__FILE__,__LINE__) #define stb__arr_insertn(p,s,i,n) stb__arr_insertn_(p,s,i,n,__FILE__,__LINE__) #endif #endif #define stb_arr(x) STB__ARR(x) #ifdef STB_DEFINE static void *stb__arr_context; void *stb_arr_malloc_parent(void *p) { void *q = stb__arr_context; stb__arr_context = p; return q; } void stb_arr_malloc(void **target, void *context) { stb__arr *q = (stb__arr *) stb_malloc(context, sizeof(*q)); q->len = q->limit = 0; q->stb_malloc = 1; q->signature = stb_arr_signature; *target = (void *) (q+1); } static void * stb__arr_malloc(int size) { if (stb__arr_context) return stb_malloc(stb__arr_context, size); return malloc(size); } void * stb__arr_copy_(void *p, int elem_size) { stb__arr *q; if (p == NULL) return p; q = (stb__arr *) stb__arr_malloc(sizeof(*q) + elem_size * stb_arrhead2(p)->limit); stb_arr_check2(p); memcpy(q, stb_arrhead2(p), sizeof(*q) + elem_size * stb_arrhead2(p)->len); q->stb_malloc = !!stb__arr_context; return q+1; } void * stb_arr_free_(void *p) { stb_arr_check2(p); if (p) { stb__arr *q = stb_arrhead2(p); if (q->stb_malloc) stb_free(q); else free(q); } return NULL; } static void *stb__arrsize_(void *p, int size, int limit, int len STB__PARAMS) { stb__arr *a; stb_arr_check2(p); if (p == NULL) { if (len == 0 && size == 0) return p; a = (stb__arr *) stb__arr_malloc(sizeof(*a) + size*limit); a->limit = limit; a->len = len; a->stb_malloc = !!stb__arr_context; a->signature = stb_arr_signature; } else { a = stb_arrhead2(p); a->len = len; if (a->limit < limit) { void *p; if (a->limit >= 4 && limit < a->limit * 2) limit = a->limit * 2; if (a->stb_malloc) p = stb_realloc(a, sizeof(*a) + limit*size); else #ifdef STB_MALLOC_WRAPPER p = stb__realloc(a, sizeof(*a) + limit*size, file, line); #else p = realloc(a, sizeof(*a) + limit*size); #endif if (p) { a = (stb__arr *) p; a->limit = limit; } else { // throw an error! } } } a->len = stb_min(a->len, a->limit); return a+1; } void *stb__arr_setsize_(void *p, int size, int limit STB__PARAMS) { stb_arr_check2(p); return stb__arrsize_(p, size, limit, stb_arr_len2(p) STB__ARGS); } void *stb__arr_setlen_(void *p, int size, int newlen STB__PARAMS) { stb_arr_check2(p); if (stb_arrcurmax2(p) < newlen || p == NULL) { return stb__arrsize_(p, size, newlen, newlen STB__ARGS); } else { stb_arrhead2(p)->len = newlen; return p; } } void *stb__arr_addlen_(void *p, int size, int addlen STB__PARAMS) { return stb__arr_setlen_(p, size, stb_arr_len2(p) + addlen STB__ARGS); } void *stb__arr_insertn_(void *p, int size, int i, int n STB__PARAMS) { if (n) { int z; if (p == NULL) return stb__arr_addlen_(p, size, n STB__ARGS); z = stb_arr_len2(p); p = stb__arr_addlen_(p, size, i STB__ARGS); memmove((char *) p + (i+n)*size, (char *) p + i*size, size * (z-i)); } return p; } void *stb__arr_deleten_(void *p, int size, int i, int n STB__PARAMS) { if (n) { memmove((char *) p + i*size, (char *) p + (i+n)*size, size * (stb_arr_len2(p)-i)); stb_arrhead2(p)->len -= n; } return p; } #endif ////////////////////////////////////////////////////////////////////////////// // // Hashing // // typical use for this is to make a power-of-two hash table. // // let N = size of table (2^n) // let H = stb_hash(str) // let S = stb_rehash(H) | 1 // // then hash probe sequence P(i) for i=0..N-1 // P(i) = (H + S*i) & (N-1) // // the idea is that H has 32 bits of hash information, but the // table has only, say, 2^20 entries so only uses 20 of the bits. // then by rehashing the original H we get 2^12 different probe // sequences for a given initial probe location. (So it's optimal // for 64K tables and its optimality decreases past that.) // // ok, so I've added something that generates _two separate_ // 32-bit hashes simultaneously which should scale better to // very large tables. STB_EXTERN unsigned int stb_hash(char *str); STB_EXTERN unsigned int stb_hashptr(void *p); STB_EXTERN unsigned int stb_hashlen(char *str, int len); STB_EXTERN unsigned int stb_rehash_improved(unsigned int v); STB_EXTERN unsigned int stb_hash_fast(void *p, int len); STB_EXTERN unsigned int stb_hash2(char *str, unsigned int *hash2_ptr); STB_EXTERN unsigned int stb_hash_number(unsigned int hash); #define stb_rehash(x) ((x) + ((x) >> 6) + ((x) >> 19)) #ifdef STB_DEFINE unsigned int stb_hash(char *str) { unsigned int hash = 0; while (*str) hash = (hash << 7) + (hash >> 25) + *str++; return hash + (hash >> 16); } unsigned int stb_hashlen(char *str, int len) { unsigned int hash = 0; while (len-- > 0 && *str) hash = (hash << 7) + (hash >> 25) + *str++; return hash + (hash >> 16); } unsigned int stb_hashptr(void *p) { unsigned int x = (unsigned int) p; // typically lacking in low bits and high bits x = stb_rehash(x); x += x << 16; // pearson's shuffle x ^= x << 3; x += x >> 5; x ^= x << 2; x += x >> 15; x ^= x << 10; return stb_rehash(x); } unsigned int stb_rehash_improved(unsigned int v) { return stb_hashptr((void *) v); } unsigned int stb_hash2(char *str, unsigned int *hash2_ptr) { unsigned int hash1 = 0x3141592c; unsigned int hash2 = 0x77f044ed; while (*str) { hash1 = (hash1 << 7) + (hash1 >> 25) + *str; hash2 = (hash2 << 11) + (hash2 >> 21) + *str; ++str; } *hash2_ptr = hash2 + (hash1 >> 16); return hash1 + (hash2 >> 16); } // Paul Hsieh hash #define stb__get16_slow(p) ((p)[0] + ((p)[1] << 8)) #if defined(_MSC_VER) #define stb__get16(p) (*((unsigned short *) (p))) #else #define stb__get16(p) stb__get16_slow(p) #endif unsigned int stb_hash_fast(void *p, int len) { unsigned char *q = (unsigned char *) p; unsigned int hash = len; if (len <= 0 || q == NULL) return 0; /* Main loop */ if (((int) q & 1) == 0) { for (;len > 3; len -= 4) { unsigned int val; hash += stb__get16(q); val = (stb__get16(q+2) << 11); hash = (hash << 16) ^ hash ^ val; q += 4; hash += hash >> 11; } } else { for (;len > 3; len -= 4) { unsigned int val; hash += stb__get16_slow(q); val = (stb__get16_slow(q+2) << 11); hash = (hash << 16) ^ hash ^ val; q += 4; hash += hash >> 11; } } /* Handle end cases */ switch (len) { case 3: hash += stb__get16_slow(q); hash ^= hash << 16; hash ^= q[2] << 18; hash += hash >> 11; break; case 2: hash += stb__get16_slow(q); hash ^= hash << 11; hash += hash >> 17; break; case 1: hash += q[0]; hash ^= hash << 10; hash += hash >> 1; break; case 0: break; } /* Force "avalanching" of final 127 bits */ hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 4; hash += hash >> 17; hash ^= hash << 25; hash += hash >> 6; return hash; } unsigned int stb_hash_number(unsigned int hash) { hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 4; hash += hash >> 17; hash ^= hash << 25; hash += hash >> 6; return hash; } #endif ////////////////////////////////////////////////////////////////////////////// // // Perfect hashing for ints/pointers // // This is mainly useful for making faster pointer-indexed tables // that don't change frequently. E.g. for stb_ischar(). // typedef struct { stb_uint32 addend; stb_uint multiplicand; stb_uint b_mask; stb_uint8 small_bmap[16]; stb_uint16 *large_bmap; stb_uint table_mask; stb_uint32 *table; } stb_perfect; STB_EXTERN int stb_perfect_create(stb_perfect *,unsigned int*,int n); STB_EXTERN void stb_perfect_destroy(stb_perfect *); STB_EXTERN int stb_perfect_hash(stb_perfect *, unsigned int x); extern int stb_perfect_hash_max_failures; #ifdef STB_DEFINE int stb_perfect_hash_max_failures; int stb_perfect_hash(stb_perfect *p, unsigned int x) { stb_uint m = x * p->multiplicand; stb_uint y = x >> 16; stb_uint bv = (m >> 24) + y; stb_uint av = (m + y) >> 12; if (p->table == NULL) return -1; // uninitialized table fails bv &= p->b_mask; av &= p->table_mask; if (p->large_bmap) av ^= p->large_bmap[bv]; else av ^= p->small_bmap[bv]; return p->table[av] == x ? av : -1; } static void stb__perfect_prehash(stb_perfect *p, stb_uint x, stb_uint16 *a, stb_uint16 *b) { stb_uint m = x * p->multiplicand; stb_uint y = x >> 16; stb_uint bv = (m >> 24) + y; stb_uint av = (m + y) >> 12; bv &= p->b_mask; av &= p->table_mask; *b = bv; *a = av; } static unsigned long stb__perfect_rand(void) { static unsigned long stb__rand; stb__rand = stb__rand * 2147001325 + 715136305; return 0x31415926 ^ ((stb__rand >> 16) + (stb__rand << 16)); } typedef struct { unsigned short count; unsigned short b; unsigned short map; unsigned short *entries; } stb__slot; static int stb__slot_compare(const void *p, const void *q) { stb__slot *a = (stb__slot *) p; stb__slot *b = (stb__slot *) q; return a->count > b->count ? -1 : a->count < b->count; // sort large to small } int stb_perfect_create(stb_perfect *p, unsigned int *v, int n) { unsigned int buffer1[64], buffer2[64], buffer3[64], buffer4[64], buffer5[32]; unsigned short *as = (unsigned short *) stb_temp(buffer1, sizeof(*v)*n); unsigned short *bs = (unsigned short *) stb_temp(buffer2, sizeof(*v)*n); unsigned short *entries = (unsigned short *) stb_temp(buffer4, sizeof(*entries) * n); int size = 1 << stb_log2_ceil(n), bsize=8; int failure = 0,i,j,k; assert(n <= 32768); p->large_bmap = NULL; for(;;) { stb__slot *bcount = (stb__slot *) stb_temp(buffer3, sizeof(*bcount) * bsize); unsigned short *bloc = (unsigned short *) stb_temp(buffer5, sizeof(*bloc) * bsize); unsigned short *e; int bad=0; p->addend = stb__perfect_rand(); p->multiplicand = stb__perfect_rand() | 1; p->table_mask = size-1; p->b_mask = bsize-1; p->table = (stb_uint32 *) malloc(size * sizeof(*p->table)); for (i=0; i < bsize; ++i) { bcount[i].b = i; bcount[i].count = 0; bcount[i].map = 0; } for (i=0; i < n; ++i) { stb__perfect_prehash(p, v[i], as+i, bs+i); ++bcount[bs[i]].count; } qsort(bcount, bsize, sizeof(*bcount), stb__slot_compare); e = entries; // now setup up their entries index for (i=0; i < bsize; ++i) { bcount[i].entries = e; e += bcount[i].count; bcount[i].count = 0; bloc[bcount[i].b] = i; } // now fill them out for (i=0; i < n; ++i) { int b = bs[i]; int w = bloc[b]; bcount[w].entries[bcount[w].count++] = i; } stb_tempfree(buffer5,bloc); // verify for (i=0; i < bsize; ++i) for (j=0; j < bcount[i].count; ++j) assert(bs[bcount[i].entries[j]] == bcount[i].b); memset(p->table, 0, size*sizeof(*p->table)); // check if any b has duplicate a for (i=0; i < bsize; ++i) { if (bcount[i].count > 1) { for (j=0; j < bcount[i].count; ++j) { if (p->table[as[bcount[i].entries[j]]]) bad = 1; p->table[as[bcount[i].entries[j]]] = 1; } for (j=0; j < bcount[i].count; ++j) { p->table[as[bcount[i].entries[j]]] = 0; } if (bad) break; } } if (!bad) { // go through the bs and populate the table, first fit for (i=0; i < bsize; ++i) { if (bcount[i].count) { // go through the candidate table[b] values for (j=0; j < size; ++j) { // go through the a values and see if they fit for (k=0; k < bcount[i].count; ++k) { int a = as[bcount[i].entries[k]]; if (p->table[(a^j)&p->table_mask]) { break; // fails } } // if succeeded, accept if (k == bcount[i].count) { bcount[i].map = j; for (k=0; k < bcount[i].count; ++k) { int a = as[bcount[i].entries[k]]; p->table[(a^j)&p->table_mask] = 1; } break; } } if (j == size) break; // no match for i'th entry, so break out in failure } } if (i == bsize) { // success... fill out map if (bsize <= 16 && size <= 256) { p->large_bmap = NULL; for (i=0; i < bsize; ++i) p->small_bmap[bcount[i].b] = (stb_uint8) bcount[i].map; } else { p->large_bmap = (unsigned short *) malloc(sizeof(*p->large_bmap) * bsize); for (i=0; i < bsize; ++i) p->large_bmap[bcount[i].b] = bcount[i].map; } // initialize table to v[0], so empty slots will fail for (i=0; i < size; ++i) p->table[i] = v[0]; for (i=0; i < n; ++i) if (p->large_bmap) p->table[as[i] ^ p->large_bmap[bs[i]]] = v[i]; else p->table[as[i] ^ p->small_bmap[bs[i]]] = v[i]; // and now validate that none of them collided for (i=0; i < n; ++i) assert(stb_perfect_hash(p, v[i]) >= 0); stb_tempfree(buffer3, bcount); break; } } free(p->table); p->table = NULL; stb_tempfree(buffer3, bcount); ++failure; if (failure >= 4 && bsize < size) bsize *= 2; if (failure >= 8 && (failure & 3) == 0 && size < 4*n) { size *= 2; bsize *= 2; } if (failure == 6) { // make sure the input data is unique, so we don't infinite loop unsigned int *data = (unsigned int *) stb_temp(buffer3, n * sizeof(*data)); memcpy(data, v, sizeof(*data) * n); qsort(data, n, sizeof(*data), stb_intcmp(0)); for (i=1; i < n; ++i) { if (data[i] == data[i-1]) size = 0; // size is return value, so 0 it } stb_tempfree(buffer3, data); if (!size) break; } } if (failure > stb_perfect_hash_max_failures) stb_perfect_hash_max_failures = failure; stb_tempfree(buffer1, as); stb_tempfree(buffer2, bs); stb_tempfree(buffer4, entries); return size; } void stb_perfect_destroy(stb_perfect *p) { if (p->large_bmap) free(p->large_bmap); if (p->table ) free(p->table); p->large_bmap = NULL; p->table = NULL; p->b_mask = 0; p->table_mask = 0; } #endif ////////////////////////////////////////////////////////////////////////////// // // Perfect hash clients STB_EXTERN int stb_ischar(char s, char *set); #ifdef STB_DEFINE int stb_ischar(char c, char *set) { static unsigned char bit[8] = { 1,2,4,8,16,32,64,128 }; static stb_perfect p; static unsigned char (*tables)[256]; static STB__ARR(char *) sets = NULL; int z = stb_perfect_hash(&p, (int) set); if (z < 0) { int i,k,n,j,f; // special code that means free all existing data if (set == NULL) { sets = stb_arr_free(sets); free(tables); tables = NULL; stb_perfect_destroy(&p); return 0; } stb_arr_push(sets, set); stb_perfect_destroy(&p); n = stb_perfect_create(&p, (unsigned int *) (char **) sets, stb_arr_len(sets)); assert(n != 0); k = (n+7) >> 3; tables = (unsigned char (*)[256]) realloc(tables, sizeof(*tables) * k); memset(tables, 0, sizeof(*tables) * k); for (i=0; i < stb_arr_len(sets); ++i) { k = stb_perfect_hash(&p, (int) sets[i]); assert(k >= 0); n = k >> 3; f = bit[k&7]; for (j=0; !j || sets[i][j]; ++j) { tables[n][(unsigned char) sets[i][j]] |= f; } } z = stb_perfect_hash(&p, (int) set); } return tables[z >> 3][(unsigned char) c] & bit[z & 7]; } #endif ////////////////////////////////////////////////////////////////////////////// // // Instantiated data structures // // This is an attempt to implement a templated data structure. // // Hash table: call stb_define_hash(TYPE,N,KEY,K1,K2,HASH,VALUE) // TYPE -- will define a structure type containing the hash table // N -- the name, will prefix functions named: // N create // N destroy // N get // N set, N add, N update, // N remove // KEY -- the type of the key. 'x == y' must be valid // K1,K2 -- keys never used by the app, used as flags in the hashtable // HASH -- a piece of code ending with 'return' that hashes key 'k' // VALUE -- the type of the value. 'x = y' must be valid // // Note that stb_define_hash_base can be used to define more sophisticated // hash tables, e.g. those that make copies of the key or use special // comparisons (e.g. strcmp). #define STB_(prefix,name) stb__##prefix##name #define STB__(prefix,name) prefix##name #define STB__use(x) x #define STB__skip(x) #define stb_declare_hash(PREFIX,TYPE,N,KEY,VALUE) \ typedef struct st_##TYPE TYPE;\ PREFIX int STB__(N, init)(TYPE *h, int count);\ PREFIX int STB__(N, memory_usage)(TYPE *h);\ PREFIX TYPE * STB__(N, create)(void);\ PREFIX TYPE * STB__(N, copy)(TYPE *h);\ PREFIX void STB__(N, destroy)(TYPE *h);\ PREFIX int STB__(N,get_flag)(TYPE *a, KEY k, VALUE *v);\ PREFIX VALUE STB__(N,get)(TYPE *a, KEY k);\ PREFIX int STB__(N, set)(TYPE *a, KEY k, VALUE v);\ PREFIX int STB__(N, add)(TYPE *a, KEY k, VALUE v);\ PREFIX int STB__(N, update)(TYPE*a,KEY k,VALUE v);\ PREFIX int STB__(N, remove)(TYPE *a, KEY k, VALUE *v); #define STB_nocopy(x) (x) #define STB_nodelete(x) 0 #define STB_nofields #define STB_nonullvalue(x) #define STB_nullvalue(x) x #define STB_safecompare(x) x #define STB_nosafe(x) #ifdef __GNUC__ #define STB__nogcc(x) #else #define STB__nogcc(x) x #endif #define stb_define_hash_base(TYPE,FIELDS,N,LOAD_FACTOR, \ KEY,EMPTY,DEL,COPY,DISPOSE,SAFE,COMPARE,HASH, \ VALUE,HASVNULL,VNULL) \ \ typedef struct \ { \ KEY k; \ VALUE v; \ } STB_(N,_hashpair); \ \ STB__nogcc( typedef struct st_##TYPE TYPE; ) \ struct st_##TYPE { \ FIELDS \ STB_(N,_hashpair) *table; \ unsigned int mask; \ int count, limit; \ int deleted; \ \ int delete_threshhold; \ int grow_threshhold; \ int shrink_threshhold; \ unsigned char alloced, has_empty, has_del; \ VALUE ev; VALUE dv; \ }; \ \ static unsigned int STB_(N, hash)(KEY k) \ { \ HASH \ } \ \ int STB__(N, init)(TYPE *h, int count) \ { \ int i; \ if (count < 4) count = 4; \ h->limit = count; \ h->count = 0; \ h->mask = count-1; \ h->deleted = 0; \ h->grow_threshhold = (int) (count * LOAD_FACTOR); \ h->has_empty = h->has_del = 0; \ h->alloced = 0; \ if (count <= 64) \ h->shrink_threshhold = 0; \ else \ h->shrink_threshhold = (int) (count * (LOAD_FACTOR/2.25)); \ h->delete_threshhold = (int) (count * (1-LOAD_FACTOR)/2); \ h->table = (STB_(N,_hashpair)*) malloc(sizeof(h->table[0]) * count); \ if (h->table == NULL) return 0; \ /* ideally this gets turned into a memset32 automatically */ \ for (i=0; i < count; ++i) \ h->table[i].k = EMPTY; \ return 1; \ } \ \ int STB__(N, memory_usage)(TYPE *h) \ { \ return sizeof(*h) + h->limit * sizeof(h->table[0]); \ } \ \ TYPE * STB__(N, create)(void) \ { \ TYPE *h = (TYPE *) malloc(sizeof(*h)); \ if (h) { \ if (STB__(N, init)(h, 16)) \ h->alloced = 1; \ else { free(h); h=NULL; } \ } \ return h; \ } \ \ void STB__(N, destroy)(TYPE *a) \ { \ int i; \ for (i=0; i < a->limit; ++i) \ if (a->table[i].k != EMPTY && a->table[i].k != DEL) \ DISPOSE(a->table[i].k); \ free(a->table); \ if (a->alloced) \ free(a); \ } \ \ static void STB_(N, rehash)(TYPE *a, int count); \ \ int STB__(N,get_flag)(TYPE *a, KEY k, VALUE *v) \ { \ unsigned int h = STB_(N, hash)(k); \ unsigned int n = h & a->mask, s; \ if (k == EMPTY) { if (a->has_empty) *v = a->ev; return a->has_empty; } \ if (k == DEL ) { if (a->has_del ) *v = a->dv; return a->has_del; } \ if (a->table[n].k==EMPTY) return 0; \ SAFE(if (a->table[n].k != DEL)) \ if (COMPARE(a->table[n].k,k)) { *v = a->table[n].v; return 1; } \ s = stb_rehash(h) | 1; \ for(;;) { \ n = (n + s) & a->mask; \ if (a->table[n].k==EMPTY) return 0; \ SAFE(if (a->table[n].k == DEL) continue;) \ if (COMPARE(a->table[n].k,k)) \ { *v = a->table[n].v; return 1; } \ } \ } \ \ HASVNULL( \ VALUE STB__(N,get)(TYPE *a, KEY k) \ { \ VALUE v; \ if (STB__(N,get_flag)(a,k,&v)) return v; \ else return VNULL; \ } \ ) \ \ int STB__(N,getkey)(TYPE *a, KEY k, KEY *kout) \ { \ unsigned int h = STB_(N, hash)(k); \ unsigned int n = h & a->mask, s; \ if (k == EMPTY || k == DEL) return 0; \ if (a->table[n].k==EMPTY) return 0; \ SAFE(if (a->table[n].k != DEL)) \ if (COMPARE(a->table[n].k,k)) { *kout = a->table[n].k; return 1; } \ s = stb_rehash(h) | 1; \ for(;;) { \ n = (n + s) & a->mask; \ if (a->table[n].k==EMPTY) return 0; \ SAFE(if (a->table[n].k == DEL) continue;) \ if (COMPARE(a->table[n].k,k)) \ { *kout = a->table[n].k; return 1; } \ } \ } \ \ static int STB_(N,addset)(TYPE *a, KEY k, VALUE v, \ int allow_new, int allow_old, int copy) \ { \ unsigned int h = STB_(N, hash)(k); \ unsigned int n = h & a->mask; \ int b = -1; \ if (k == EMPTY) \ if (a->has_empty ? allow_old : allow_new) { \ n=a->has_empty; a->ev = v; a->has_empty = 1; return !n; \ } else return 0; \ if (k == DEL) \ if (a->has_del ? allow_old : allow_new) { \ n=a->has_del; a->dv = v; a->has_del = 1; return !n; \ } else return 0; \ if (a->table[n].k != EMPTY) { \ unsigned int s; \ if (a->table[n].k == DEL) \ b = n; \ else if (COMPARE(a->table[n].k,k)) { \ if (allow_old) \ a->table[n].v = v; \ return !allow_new; \ } \ s = stb_rehash(h) | 1; \ for(;;) { \ n = (n + s) & a->mask; \ if (a->table[n].k == EMPTY) break; \ if (a->table[n].k == DEL) { \ if (b < 0) b = n; \ } else if (COMPARE(a->table[n].k,k)) { \ if (allow_old) \ a->table[n].v = v; \ return !allow_new; \ } \ } \ } \ if (!allow_new) return 0; \ if (b < 0) b = n; else --a->deleted; \ a->table[b].k = copy ? COPY(k) : k; \ a->table[b].v = v; \ ++a->count; \ if (a->count > a->grow_threshhold) \ STB_(N,rehash)(a, a->limit*2); \ return 1; \ } \ \ int STB__(N, set)(TYPE *a, KEY k, VALUE v){return STB_(N,addset)(a,k,v,1,1,1);}\ int STB__(N, add)(TYPE *a, KEY k, VALUE v){return STB_(N,addset)(a,k,v,1,0,1);}\ int STB__(N, update)(TYPE*a,KEY k,VALUE v){return STB_(N,addset)(a,k,v,0,1,1);}\ \ int STB__(N, remove)(TYPE *a, KEY k, VALUE *v) \ { \ unsigned int h = STB_(N, hash)(k); \ unsigned int n = h & a->mask, s; \ if (k == EMPTY) { if (a->has_empty) { if(v)*v = a->ev; a->has_empty=0; return 1; } return 0; } \ if (k == DEL ) { if (a->has_del ) { if(v)*v = a->dv; a->has_del =0; return 1; } return 0; } \ if (a->table[n].k == EMPTY) return 0; \ if (SAFE(a->table[n].k == DEL || ) !COMPARE(a->table[n].k,k)) { \ s = stb_rehash(h) | 1; \ for(;;) { \ n = (n + s) & a->mask; \ if (a->table[n].k == EMPTY) return 0; \ SAFE(if (a->table[n].k == DEL) continue;) \ if (COMPARE(a->table[n].k,k)) break; \ } \ } \ DISPOSE(a->table[n].k); \ a->table[n].k = DEL; \ --a->count; \ ++a->deleted; \ if (v != NULL) \ *v = a->table[n].v; \ if (a->count < a->shrink_threshhold) \ STB_(N, rehash)(a, a->limit >> 1); \ else if (a->deleted > a->delete_threshhold) \ STB_(N, rehash)(a, a->limit); \ return 1; \ } \ \ TYPE * STB__(N, copy)(TYPE *a) \ { \ int i; \ TYPE *h = (TYPE *) malloc(sizeof(*h)); \ if (!h) return NULL; \ if (!STB__(N, init)(h, a->count)) { free(h); return NULL; } \ h->count = a->count; \ h->deleted = a->deleted; \ h->alloced = 1; \ h->ev = a->ev; h->dv = a->dv; \ h->has_empty = a->has_empty; h->has_del = a->has_del; \ memcpy(h->table, a->table, h->limit * sizeof(h->table[0])); \ for (i=0; i < a->limit; ++i) \ if (h->table[i].k != EMPTY && h->table[i].k != DEL) \ h->table[i].k = COPY(h->table[i].k); \ return h; \ } \ \ static void STB_(N, rehash)(TYPE *a, int count) \ { \ int i; \ TYPE b; \ STB__(N, init)(&b, count); \ for (i=0; i < a->limit; ++i) \ if (a->table[i].k != EMPTY && a->table[i].k != DEL) \ STB_(N,addset)(&b, a->table[i].k, a->table[i].v,1,1,0); \ free(a->table); \ a->table = b.table;\ a->mask = b.mask;\ a->count = b.count;\ a->limit = b.limit;\ a->deleted = b.deleted;\ a->delete_threshhold = b.delete_threshhold;\ a->grow_threshhold = b.grow_threshhold;\ a->shrink_threshhold = b.shrink_threshhold;\ } #define STB_equal(a,b) ((a) == (b)) #define stb_define_hash(TYPE,N,KEY,EMPTY,DEL,HASH,VALUE) \ stb_define_hash_base(TYPE,STB_nofields,N,0.85f, \ KEY,EMPTY,DEL,STB_nocopy,STB_nodelete,STB_nosafe,STB_equal,HASH,\ VALUE,STB_nonullvalue,0) ////////////////////////////////////////////////////////////////////////////// // // stb_ptrmap // // An stb_ptrmap data structure is an O(1) hash table between pointers. One // application is to let you store "extra" data associated with pointers, // which is why it was originally called stb_extra. stb_declare_hash(STB_EXTERN, stb_ptrmap, stb_ptrmap_, void *, void *) stb_declare_hash(STB_EXTERN, stb_idict, stb_idict_, stb_int32, stb_int32) STB_EXTERN void stb_ptrmap_delete(stb_ptrmap *e, void (*free_func)(void *)); STB_EXTERN stb_ptrmap *stb_ptrmap_new(void); STB_EXTERN stb_idict * stb_idict_new_size(int size); STB_EXTERN void stb_idict_remove_all(stb_idict *e); #ifdef STB_DEFINE #define STB_EMPTY ((void *) 2) #define STB_EDEL ((void *) 6) stb_define_hash_base(stb_ptrmap, STB_nofields, stb_ptrmap_,0.85f, void *,ST