1 // stretchy_buffer.h - v1.02 - public domain - nothings.org/stb
2 // a vector<>-like dynamic array for C
5 // 1.02 - tweaks to syntax for no good reason
6 // 1.01 - added a "common uses" documentation section
7 // 1.0 - fixed bug in the version I posted prematurely
8 // 0.9 - rewrite to try to avoid strict-aliasing optimization
9 // issues, but won't compile as C++
11 // Will probably not work correctly with strict-aliasing optimizations.
15 // This implements an approximation to C++ vector<> for C, in that it
16 // provides a generic definition for dynamic arrays which you can
17 // still access in a typesafe way using arr[i] or *(arr+i). However,
18 // it is simply a convenience wrapper around the common idiom of
19 // of keeping a set of variables (in a struct or globals) which store
21 // - the length of the "in-use" part of the array
22 // - the current size of the allocated array
24 // I find it to be single most useful non-built-in-structure when
25 // programming in C (hash tables a close second), but to be clear
26 // it lacks many of the capabilities of C++ vector<>: there is no
27 // range checking, the object address isn't stable (see next section
28 // for details), the set of methods available is small (although
29 // the file stb.h has another implementation of stretchy buffers
30 // called 'stb_arr' which provides more methods, e.g. for insertion
35 // Unlike other stb header file libraries, there is no need to
36 // define an _IMPLEMENTATION symbol. Every #include creates as
37 // much implementation is needed.
39 // stretchy_buffer.h does not define any types, so you do not
40 // need to #include it to before defining data types that are
41 // stretchy buffers, only in files that *manipulate* stretchy
44 // If you want a stretchy buffer aka dynamic array containing
45 // objects of TYPE, declare such an array as:
47 // TYPE *myarray = NULL;
49 // (There is no typesafe way to distinguish between stretchy
50 // buffers and regular arrays/pointers; this is necessary to
51 // make ordinary array indexing work on these objects.)
53 // Unlike C++ vector<>, the stretchy_buffer has the same
54 // semantics as an object that you manually malloc and realloc.
55 // The pointer may relocate every time you add a new object
58 // 1. can't take long-term pointers to elements of the array
59 // 2. have to return the pointer from functions which might expand it
60 // (either as a return value or by passing it back)
62 // Now you can do the following things with this array:
64 // sb_free(TYPE *a) free the array
65 // sb_count(TYPE *a) the number of elements in the array
66 // sb_push(TYPE *a, TYPE v) adds v on the end of the array, a la push_back
67 // sb_add(TYPE *a, int n) adds n uninitialized elements at end of array & returns pointer to first added
68 // sb_last(TYPE *a) returns an lvalue of the last item in the array
69 // a[n] access the nth (counting from 0) element of the array
71 // #define STRETCHY_BUFFER_NO_SHORT_NAMES to only export
72 // names of the form 'stb_sb_' if you have a name that would
75 // Note that these are all macros and many of them evaluate
76 // their arguments more than once, so the arguments should
77 // be side-effect-free.
79 // Note that 'TYPE *a' in sb_push and sb_add must be lvalues
80 // so that the library can overwrite the existing pointer if
81 // the object has to be reallocated.
83 // In an out-of-memory condition, the code will try to
84 // set up a null-pointer or otherwise-invalid-pointer
85 // exception to happen later. It's possible optimizing
86 // compilers could detect this write-to-null statically
87 // and optimize away some of the code, but it should only
88 // be along the failure path. Nevertheless, for more security
89 // in the face of such compilers, #define STRETCHY_BUFFER_OUT_OF_MEMORY
90 // to a statement such as assert(0) or exit(1) or something
91 // to force a failure when out-of-memory occurs.
95 // The main application for this is when building a list of
96 // things with an unknown quantity, either due to loading from
97 // a file or through a process which produces an unpredictable
100 // My most common idiom is something like:
102 // SomeStruct *arr = NULL;
105 // SomeStruct new_one;
106 // new_one.whatever = whatever;
107 // new_one.whatup = whatup;
108 // new_one.foobar = barfoo;
109 // sb_push(arr, new_one);
112 // and various closely-related factorings of that. For example,
113 // you might have several functions to create/init new SomeStructs,
114 // and if you use the above idiom, you might prefer to make them
115 // return structs rather than take non-const-pointers-to-structs,
116 // so you can do things like:
118 // SomeStruct *arr = NULL;
122 // sb_push(arr, some_func1());
123 // } else if (case_B) {
124 // sb_push(arr, some_func2());
126 // sb_push(arr, some_func3());
130 // Note that the above relies on the fact that sb_push doesn't
131 // evaluate its second argument more than once. The macros do
132 // evaluate the *array* argument multiple times, and numeric
133 // arguments may be evaluated multiple times, but you can rely
134 // on the second argument of sb_push being evaluated only once.
136 // Of course, you don't have to store bare objects in the array;
137 // if you need the objects to have stable pointers, store an array
138 // of pointers instead:
140 // SomeStruct **arr = NULL;
143 // SomeStruct *new_one = malloc(sizeof(*new_one));
144 // new_one->whatever = whatever;
145 // new_one->whatup = whatup;
146 // new_one->foobar = barfoo;
147 // sb_push(arr, new_one);
152 // A long-standing tradition in things like malloc implementations
153 // is to store extra data before the beginning of the block returned
154 // to the user. The stretchy buffer implementation here uses the
155 // same trick; the current-count and current-allocation-size are
156 // stored before the beginning of the array returned to the user.
157 // (This means you can't directly free() the pointer, because the
158 // allocated pointer is different from the type-safe pointer provided
161 // The details are trivial and implementation is straightforward;
162 // the main trick is in realizing in the first place that it's
163 // possible to do this in a generic, type-safe way in C.
167 // This software is dual-licensed to the public domain and under the following
168 // license: you are granted a perpetual, irrevocable license to copy, modify,
169 // publish, and distribute this file as you see fit.
171 #ifndef STB_STRETCHY_BUFFER_H_INCLUDED
172 #define STB_STRETCHY_BUFFER_H_INCLUDED
174 #ifndef NO_STRETCHY_BUFFER_SHORT_NAMES
175 #define sb_free stb_sb_free
176 #define sb_push stb_sb_push
177 #define sb_count stb_sb_count
178 #define sb_add stb_sb_add
179 #define sb_last stb_sb_last
182 #define stb_sb_free(a) ((a) ? free(stb__sbraw(a)),0 : 0)
183 #define stb_sb_push(a,v) (stb__sbmaybegrow(a,1), (a)[stb__sbn(a)++] = (v))
184 #define stb_sb_count(a) ((a) ? stb__sbn(a) : 0)
185 #define stb_sb_add(a,n) (stb__sbmaybegrow(a,n), stb__sbn(a)+=(n), &(a)[stb__sbn(a)-(n)])
186 #define stb_sb_last(a) ((a)[stb__sbn(a)-1])
188 #define stb__sbraw(a) ((int *) (a) - 2)
189 #define stb__sbm(a) stb__sbraw(a)[0]
190 #define stb__sbn(a) stb__sbraw(a)[1]
192 #define stb__sbneedgrow(a,n) ((a)==0 || stb__sbn(a)+(n) >= stb__sbm(a))
193 #define stb__sbmaybegrow(a,n) (stb__sbneedgrow(a,(n)) ? stb__sbgrow(a,n) : 0)
194 #define stb__sbgrow(a,n) ((a) = stb__sbgrowf((a), (n), sizeof(*(a))))
198 static void * stb__sbgrowf(void *arr
, int increment
, int itemsize
)
200 int dbl_cur
= arr
? 2*stb__sbm(arr
) : 0;
201 int min_needed
= stb_sb_count(arr
) + increment
;
202 int m
= dbl_cur
> min_needed
? dbl_cur
: min_needed
;
203 int *p
= (int *) realloc(arr
? stb__sbraw(arr
) : 0, itemsize
* m
+ sizeof(int)*2);
210 #ifdef STRETCHY_BUFFER_OUT_OF_MEMORY
211 STRETCHY_BUFFER_OUT_OF_MEMORY
;
213 return (void *) (2*sizeof(int)); // try to force a NULL pointer exception later
216 #endif // STB_STRETCHY_BUFFER_H_INCLUDED