1 /*
2 * A header-only typesafe dynamic array implementation for plain C,
3 * kinda like C++ std::vector. This code is compatible with C++, but should
4 * only be used with POD (plain old data) types, as it uses memcpy() etc
5 * instead of copy/move construction/assignment.
6 * It requires a new type (created with the DA_TYPEDEF(ELEMENT_TYPE, ARRAY_TYPE_NAME)
7 * macro) for each kind of element you want to put in a dynamic array; however
8 * the "functions" to manipulate the array are actually macros and the same
9 * for all element types.
10 * The array elements are accessed via dynArr.p[i] or da_get(dynArr, i)
11 * - the latter checks whether i is a valid index and asserts if not.
12 *
13 * One thing to keep in mind is that, because of using macros, the arguments to
14 * the "functions" are usually evaluated more than once, so you should avoid
15 * putting things with side effect (like function-calls with side effects or i++)
16 * into them. Notable exceptions are the value arguments (v) of da_push()
17 * and da_insert(), so it's still ok to do da_push(arr, fun_with_sideffects());
18 * or da_insert(a, 3, x++);
19 *
20 * The function-like da_* macros are short aliases of dg_dynarr_* macros.
21 * If the short names clash with anything in your code or other headers
22 * you are using, you can, before #including this header, do
23 * #define DG_DYNARR_NO_SHORTNAMES
24 * and use the long dg_dynarr_* forms of the macros instead.
25 *
26 * Using this library in your project:
27 * Put this file somewhere in your project.
28 * In *one* of your .c/.cpp files, do
29 * #define DG_DYNARR_IMPLEMENTATION
30 * #include "DG_dynarr.h"
31 * to create the implementation of this library in that file.
32 * You can just #include "DG_dynarr.h" (without the #define) in other source
33 * files to use it there.
34 *
35 * See below this comment block for a usage example.
36 *
37 * You can #define your own allocators, assertion and the amount of runtime
38 * checking of indexes, see CONFIGURATION section in the code for more information.
39 *
40 *
41 * This is heavily inspired by Sean Barrett's stretchy_buffer.h
42 * ( see: https://github.com/nothings/stb/blob/master/stretchy_buffer.h )
43 * However I wanted to have a struct that holds the array pointer and the length
44 * and capacity, so that struct always remains at the same address while the
45 * array memory might be reallocated.
46 * I can live with arr.p[i] instead of arr[i], but I like how he managed to use
47 * macros to create an API that doesn't force the user to specify the stored
48 * type over and over again, so I stole some of his tricks :-)
49 *
50 * This has been tested with GCC 4.8 and clang 3.8 (-std=gnu89, -std=c99 and as C++;
51 * -std=c89 works if you convert the C++-style comments to C comments) and
52 * Microsoft Visual Studio 6 and 2010 (32bit) and 2013 (32bit and 64bit).
53 * I guess it works with all (recentish) C++ compilers and C compilers supporting
54 * C99 or even C89 + C++ comments (otherwise converting the comments should help).
55 *
56 * (C) 2016 Daniel Gibson
57 *
58 * LICENSE
59 * This software is dual-licensed to the public domain and under the following
60 * license: you are granted a perpetual, irrevocable license to copy, modify,
61 * publish, and distribute this file as you see fit.
62 * No warranty implied; use at your own risk.
63 *
64 * So you can do whatever you want with this code, including copying it
65 * (or parts of it) into your own source.
66 * No need to mention me or this "license" in your code or docs, even though
67 * it would be appreciated, of course.
68 */
69 #if 0 /* Usage Example: */
70 #define DG_DYNARR_IMPLEMENTATION /* this define is only needed in *one* .c/.cpp file! */
71 #include "DG_dynarr.h"
72
73 DA_TYPEDEF(int, MyIntArrType); /* creates MyIntArrType - a dynamic array for ints */
74
75 void printIntArr(MyIntArrType* arr, const char* name)
76 {
77 /* note that arr is a pointer here, so use *arr in the da_*() functions. */
78 printf("%s = {", name);
79 if(da_count(*arr) > 0)
80 printf(" %d", arr->p[0]);
81 for(int i=1; i<da_count(*arr); ++i)
82 printf(", %d", arr->p[i]);
83 printf(" }\n");
84 }
85
86 void myFunction()
87 {
88 MyIntArrType a1 = {0};
89 /* make sure to zero out the struct
90 * instead of = {0}; you could also call da_init(a1);
91 */
92
93 da_push(a1, 42);
94 assert(da_count(a1) == 1 && a1.p[0] == 42);
95
96 int* addedElements = da_addn_uninit(a1, 3);
97 assert(da_count(a1) == 4);
98 for(size_t i=0; i<3; ++i)
99 addedElements[i] = i+5;
100
101 printIntArr(&a1, "a1"); /* "a1 = { 42, 5, 6, 7 }" */
102
103 MyIntArrType a2;
104 da_init(a2);
105
106 da_addn(a2, a1.p, da_count(a1)); /* copy all elements from a1 to a2 */
107 assert(da_count(a2) == 4);
108
109 da_insert(a2, 1, 11);
110 printIntArr(&a2, "a2"); /* "a2 = { 42, 11, 5, 6, 7 }" */
111
112 da_delete(a2, 2);
113 printIntArr(&a2, "a2"); /* "a2 = { 42, 11, 6, 7 }" */
114
115 da_deletefast(a2, 0);
116 printIntArr(&a2, "a2"); /* "a2 = { 7, 11, 6 }" */
117
118 da_push(a1, 3);
119 printIntArr(&a1, "a1"); /* "a1 = { 42, 5, 6, 7, 3 }" */
120
121 int x=da_pop(a1);
122 printf("x = %d\n", x); /* "x = 3" */
123 printIntArr(&a1, "a1"); /* "a1 = { 42, 5, 6, 7 }" */
124
125 da_free(a1); /* make sure not to leak memory! */
126 da_free(a2);
127 }
128 #endif /* 0 (usage example) */
129
130 #ifndef DG__DYNARR_H
131 #define DG__DYNARR_H
132
133 /* ######### CONFIGURATION #########
134 *
135 * following: some #defines that you can tweak to your liking
136 *
137 * you can reduce some overhead by defining DG_DYNARR_INDEX_CHECK_LEVEL to 2, 1 or 0
138 */
139 #ifndef DG_DYNARR_INDEX_CHECK_LEVEL
140
141 /* 0: (almost) no index checking
142 * 1: macros "returning" something return a.p[0] or NULL if the index was invalid
143 * 2: assertions in all macros taking indexes that make sure they're valid
144 * 3: 1 and 2
145 */
146 #define DG_DYNARR_INDEX_CHECK_LEVEL 3
147
148 #endif /* DG_DYNARR_INDEX_CHECK_LEVEL */
149
150 /* you can #define your own DG_DYNARR_ASSERT(condition, msgstring)
151 * that will be used for all assertions in this code.
152 */
153 #ifndef DG_DYNARR_ASSERT
154 #include <assert.h>
155 #define DG_DYNARR_ASSERT(cond, msg) assert((cond) && msg)
156 #endif
157
158 /* you can #define DG_DYNARR_OUT_OF_MEMORY to some code that will be executed
159 * if allocating memory fails
160 * it's needed only before the #define DG_DYNARR_IMPLEMENTATION #include of
161 * this header, so the following is here only for reference and commented out
162 */
163 /*
164 #ifndef DG_DYNARR_OUT_OF_MEMORY
165 #define DG_DYNARR_OUT_OF_MEMORY DG_DYNARR_ASSERT(0, "Out of Memory!");
166 #endif
167 */
168
169 /* By default, C's malloc(), realloc() and free() is used to allocate/free heap memory
170 * (see beginning of "#ifdef DG_DYNARR_IMPLEMENTATION" block below).
171 * You can #define DG_DYNARR_MALLOC, DG_DYNARR_REALLOC and DG_DYNARR_FREE yourself
172 * to provide alternative implementations like Win32 Heap(Re)Alloc/HeapFree
173 * it's needed only before the #define DG_DYNARR_IMPLEMENTATION #include of
174 * this header, so the following is here only for reference and commented out
175 */
176 /*
177 #define DG_DYNARR_MALLOC(elemSize, numElems) malloc(elemSize*numElems)
178
179 // oldNumElems is not used for C's realloc, but maybe you need it for
180 // your allocator to copy the old elements over
181 #define DG_DYNARR_REALLOC(ptr, elemSize, oldNumElems, newCapacity) \
182 realloc(ptr, elemSize*newCapacity);
183
184 #define DG_DYNARR_FREE(ptr) free(ptr)
185 */
186
187 /* if you want to prepend something to the non inline (DG_DYNARR_INLINE) functions,
188 * like "__declspec(dllexport)" or whatever, #define DG_DYNARR_DEF
189 */
190 #ifndef DG_DYNARR_DEF
191 /* by defaults it's empty. */
192 #define DG_DYNARR_DEF
193 #endif
194
195 /* some functions are inline, in case your compiler doesn't like "static inline"
196 * but wants "__inline__" or something instead, #define DG_DYNARR_INLINE accordingly.
197 */
198 #ifndef DG_DYNARR_INLINE
199 #define DG_DYNARR_INLINE static INLINE
200 #endif
201
202 /* ############### Short da_* aliases for the long names ############### */
203
204 #ifndef DG_DYNARR_NO_SHORTNAMES
205
206 /* this macro is used to create an array type (struct) for elements of TYPE
207 * use like DA_TYPEDEF(int, MyIntArrType); MyIntArrType ia = {0}; da_push(ia, 42); ...
208 */
209 #define DA_TYPEDEF(TYPE, NewArrayTypeName) \
210 DG_DYNARR_TYPEDEF(TYPE, NewArrayTypeName)
211
212 /* makes sure the array is initialized and can be used.
213 * either do YourArray arr = {0}; or YourArray arr; da_init(arr);
214 */
215 #define da_init(a) \
216 dg_dynarr_init(a)
217
218 /* This allows you to provide an external buffer that'll be used as long as it's big enough
219 * once you add more elements than buf can hold, fresh memory will be allocated on the heap
220 * Use like:
221 * DA_TYPEDEF(double, MyDoubleArrType);
222 * MyDoubleArrType arr;
223 * double buf[8];
224 * dg_dynarr_init_external(arr, buf, 8);
225 * dg_dynarr_push(arr, 1.23);
226 * ...
227 */
228 #define da_init_external(a, buf, buf_cap) \
229 dg_dynarr_init_external(a, buf, buf_cap)
230
231 /* use this to free the memory allocated by dg_dynarr once you don't need the array anymore
232 * Note: it is safe to add new elements to the array after da_free()
233 * it will allocate new memory, just like it would directly after da_init()
234 */
235 #define da_free(a) \
236 dg_dynarr_free(a)
237
238 /* add an element to the array (appended at the end) */
239 #define da_push(a, v) \
240 dg_dynarr_push(a, v)
241
242 /* add an element to the array (appended at the end)
243 * does the same as push, just for consistency with addn (like insert and insertn)
244 */
245 #define da_add(a, v) \
246 dg_dynarr_add(a, v)
247
248 /* append n elements to a and initialize them from array vals, doesn't return anything
249 * ! vals (and all other args) are evaluated multiple times !
250 */
251 #define da_addn(a, vals, n) \
252 dg_dynarr_addn(a, vals, n)
253
254 /* add n elements to the end of the array and zeroes them with memset()
255 * returns pointer to first added element, NULL if out of memory (array is empty then)
256 */
257 #define da_addn_zeroed(a, n) \
258 dg_dynarr_addn_zeroed(a, n)
259
260 /* add n elements to the end of the array, will remain uninitialized
261 * returns pointer to first added element, NULL if out of memory (array is empty then)
262 */
263 #define da_addn_uninit(a, n) \
264 dg_dynarr_addn_uninit(a, n)
265
266 /* insert a single value v at index idx */
267 #define da_insert(a, idx, v) \
268 dg_dynarr_insert(a, idx, v)
269
270 /* insert n elements into a at idx, initialize them from array vals
271 * doesn't return anything
272 * ! vals (and all other args) is evaluated multiple times !
273 */
274 #define da_insertn(a, idx, vals, n) \
275 dg_dynarr_insertn(a, idx, vals, n)
276
277 /* insert n elements into a at idx and zeroe them with memset()
278 * returns pointer to first inserted element or NULL if out of memory
279 */
280 #define da_insertn_zeroed(a, idx, n) \
281 dg_dynarr_insertn_zeroed(a, idx, n)
282
283 /* insert n uninitialized elements into a at idx;
284 * returns pointer to first inserted element or NULL if out of memory
285 */
286 #define da_insertn_uninit(a, idx, n) \
287 dg_dynarr_insertn_uninit(a, idx, n)
288
289 /* set a single value v at index idx - like "a.p[idx] = v;" but with checks (unless disabled) */
290 #define da_set(a, idx, v) \
291 dg_dynarr_set(a, idx, v)
292
293 /* overwrite n elements of a, starting at idx, with values from array vals
294 * doesn't return anything
295 * ! vals (and all other args) is evaluated multiple times !
296 */
297 #define da_setn(a, idx, vals, n) \
298 dg_dynarr_setn(a, idx, vals, n)
299
300 /* delete the element at idx, moving all following elements (=> keeps order) */
301 #define da_delete(a, idx) \
302 dg_dynarr_delete(a, idx)
303
304 /* delete n elements starting at idx, moving all following elements (=> keeps order) */
305 #define da_deleten(a, idx, n) \
306 dg_dynarr_deleten(a, idx, n)
307
308 /* delete the element at idx, move the last element there (=> doesn't keep order) */
309 #define da_deletefast(a, idx) \
310 dg_dynarr_deletefast(a, idx)
311
312 /* delete n elements starting at idx, move the last n elements there (=> doesn't keep order) */
313 #define da_deletenfast(a, idx, n) \
314 dg_dynarr_deletenfast(a, idx, n)
315
316 /* removes all elements from the array, but does not free the buffer
317 * (if you want to free the buffer too, just use da_free())
318 */
319 #define da_clear(a) \
320 dg_dynarr_clear(a)
321
322 /* sets the logical number of elements in the array
323 * if cnt > dg_dynarr_count(a), the logical count will be increased accordingly
324 * and the new elements will be uninitialized
325 */
326 #define da_setcount(a, cnt) \
327 dg_dynarr_setcount(a, cnt)
328
329 /* make sure the array can store cap elements without reallocating
330 * logical count remains unchanged
331 */
332 #define da_reserve(a, cap) \
333 dg_dynarr_reserve(a, cap)
334
335 /* this makes sure a only uses as much memory as for its elements
336 * => maybe useful if a used to contain a huge amount of elements,
337 * but you deleted most of them and want to free some memory
338 * Note however that this implies an allocation and copying the remaining
339 * elements, so only do this if it frees enough memory to be worthwhile!
340 */
341 #define da_shrink_to_fit(a) \
342 dg_dynarr_shrink_to_fit(a)
343
344 /* removes and returns the last element of the array */
345 #define da_pop(a) \
346 dg_dynarr_pop(a)
347
348 /* returns the last element of the array */
349 #define da_last(a) \
350 dg_dynarr_last(a)
351
352 /* returns the pointer *to* the last element of the array
353 * (in contrast to dg_dynarr_end() which returns a pointer *after* the last element)
354 * returns NULL if array is empty
355 */
356 #define da_lastptr(a) \
357 dg_dynarr_lastptr(a)
358
359 /* get element at index idx (like a.p[idx]), but with checks
360 * (unless you disabled them with #define DG_DYNARR_INDEX_CHECK_LEVEL 0)
361 */
362 #define da_get(a, idx) \
363 dg_dynarr_get(a,idx)
364
365 /* get pointer to element at index idx (like &a.p[idx]), but with checks
366 * and it returns NULL if idx is invalid
367 */
368 #define da_getptr(a, idx) \
369 dg_dynarr_getptr(a, idx)
370
371 /* returns a pointer to the first element of the array
372 * (together with dg_dynarr_end() you can do C++-style iterating)
373 */
374 #define da_begin(a) \
375 dg_dynarr_begin(a)
376
377 /* returns a pointer to the past-the-end element of the array
378 * Allows C++-style iterating, in case you're into that kind of thing:
379 * for(T *it=da_begin(a), *end=da_end(a); it!=end; ++it) foo(*it);
380 * (see da_lastptr() to get a pointer *to* the last element)
381 */
382 #define da_end(a) \
383 dg_dynarr_end(a)
384
385 /* returns (logical) number of elements currently in the array */
386 #define da_count(a) \
387 dg_dynarr_count(a)
388
389 /* get the current reserved capacity of the array */
390 #define da_capacity(a) \
391 dg_dynarr_capacity(a)
392
393 /* returns 1 if the array is empty, else 0 */
394 #define da_empty(a) \
395 dg_dynarr_empty(a)
396
397 /* returns 1 if the last (re)allocation when inserting failed (Out Of Memory)
398 * or if the array has never allocated any memory yet, else 0
399 * deleting the contents when growing fails instead of keeping old may seem
400 * a bit uncool, but it's simple and OOM should rarely happen on modern systems
401 * anyway - after all you need to deplete both RAM and swap/pagefile.sys
402 */
403 #define da_oom(a) \
404 dg_dynarr_oom(a)
405
406 /* sort a using the given qsort()-comparator cmp
407 * (just a slim wrapper around qsort())
408 */
409 #define da_sort(a, cmp) \
410 dg_dynarr_sort(a, cmp)
411
412 #endif /* DG_DYNARR_NO_SHORTNAMES */
413
414 /* ######### Implementation of the actual macros (using the long names) ##########
415 *
416 * use like DG_DYNARR_TYPEDEF(int, MyIntArrType); MyIntArrType ia = {0}; dg_dynarr_push(ia, 42); ...
417 */
418 #define DG_DYNARR_TYPEDEF(TYPE, NewArrayTypeName) \
419 typedef struct { TYPE* p; dg__dynarr_md md; } NewArrayTypeName;
420
421 /* makes sure the array is initialized and can be used.
422 * either do YourArray arr = {0}; or YourArray arr; dg_dynarr_init(arr);
423 */
424 #define dg_dynarr_init(a) \
425 dg__dynarr_init((void**)&(a).p, &(a).md, NULL, 0)
426
427 /* this allows you to provide an external buffer that'll be used as long as it's big enough
428 * once you add more elements than buf can hold, fresh memory will be allocated on the heap
429 */
430 #define dg_dynarr_init_external(a, buf, buf_cap) \
431 dg__dynarr_init((void**)&(a).p, &(a).md, (buf), (buf_cap))
432
433 /* use this to free the memory allocated by dg_dynarr
434 * Note: it is safe to add new elements to the array after dg_dynarr_free()
435 * it will allocate new memory, just like it would directly after dg_dynarr_init()
436 */
437 #define dg_dynarr_free(a) \
438 dg__dynarr_free((void**)&(a).p, &(a).md)
439
440 /* add an element to the array (appended at the end) */
441 #define dg_dynarr_push(a, v) \
442 (dg__dynarr_maybegrowadd(dg__dynarr_unp(a), 1) ? (((a).p[(a).md.cnt++] = (v)),0) : 0)
443
444 /* add an element to the array (appended at the end)
445 * does the same as push, just for consistency with addn (like insert and insertn)
446 */
447 #define dg_dynarr_add(a, v) \
448 dg_dynarr_push((a), (v))
449
450 /* append n elements to a and initialize them from array vals, doesn't return anything
451 * ! vals (and all other args) are evaluated multiple times !
452 */
453 #define dg_dynarr_addn(a, vals, n) do { \
454 DG_DYNARR_ASSERT((vals)!=NULL, "Don't pass NULL als vals to dg_dynarr_addn!"); \
455 if((vals)!=NULL && dg__dynarr_add(dg__dynarr_unp(a), n, 0)) { \
456 size_t i_=(a).md.cnt-(n), v_=0; \
457 while(i_<(a).md.cnt) (a).p[i_++]=(vals)[v_++]; \
458 } } DG__DYNARR_WHILE0
459
460 /* add n elements to the end of the array and zeroe them with memset()
461 * returns pointer to first added element, NULL if out of memory (array is empty then)
462 */
463 #define dg_dynarr_addn_zeroed(a, n) \
464 (dg__dynarr_add(dg__dynarr_unp(a), (n), 1) ? &(a).p[(a).md.cnt-(size_t)(n)] : NULL)
465
466 /* add n elements to the end of the array, which are uninitialized
467 * returns pointer to first added element, NULL if out of memory (array is empty then)
468 */
469 #define dg_dynarr_addn_uninit(a, n) \
470 (dg__dynarr_add(dg__dynarr_unp(a), (n), 0) ? &(a).p[(a).md.cnt-(size_t)(n)] : NULL)
471
472 /* insert a single value v at index idx */
473 #define dg_dynarr_insert(a, idx, v) \
474 (dg__dynarr_checkidxle((a),(idx)), \
475 dg__dynarr_insert(dg__dynarr_unp(a), (idx), 1, 0), \
476 (a).p[dg__dynarr_idx((a).md, (idx))] = (v))
477
478 /* insert n elements into a at idx, initialize them from array vals
479 * doesn't return anything
480 * ! vals (and all other args) is evaluated multiple times !
481 */
482 #define dg_dynarr_insertn(a, idx, vals, n) do { \
483 DG_DYNARR_ASSERT((vals)!=NULL, "Don't pass NULL as vals to dg_dynarr_insertn!"); \
484 dg__dynarr_checkidxle((a),(idx)); \
485 if((vals)!=NULL && dg__dynarr_insert(dg__dynarr_unp(a), (idx), (n), 0)){ \
486 size_t i_=(idx), v_=0, e_=(idx)+(n); \
487 while(i_ < e_) (a).p[i_++] = (vals)[v_++]; \
488 }} DG__DYNARR_WHILE0
489
490 /* insert n elements into a at idx and zeroe them with memset()
491 * returns pointer to first inserted element or NULL if out of memory
492 */
493 #define dg_dynarr_insertn_zeroed(a, idx, n) \
494 (dg__dynarr_checkidxle((a),(idx)), \
495 dg__dynarr_insert(dg__dynarr_unp(a), (idx), (n), 1) \
496 ? &(a).p[dg__dynarr_idx((a).md, (idx))] : NULL)
497
498 /* insert n uninitialized elements into a at idx;
499 * returns pointer to first inserted element or NULL if out of memory
500 */
501 #define dg_dynarr_insertn_uninit(a, idx, n) \
502 (dg__dynarr_checkidxle((a),(idx)), \
503 dg__dynarr_insert(dg__dynarr_unp(a), idx, n, 0) \
504 ? &(a).p[dg__dynarr_idx((a).md, (idx))] : NULL)
505
506 /* set a single value v at index idx - like "a.p[idx] = v;" but with checks (unless disabled) */
507 #define dg_dynarr_set(a, idx, v) \
508 (dg__dynarr_checkidx((a),(idx)), \
509 (a).p[dg__dynarr_idx((a).md, (idx))] = (v))
510
511 /* overwrite n elements of a, starting at idx, with values from array vals
512 * doesn't return anything
513 * ! vals (and all other args) is evaluated multiple times !
514 */
515 #define dg_dynarr_setn(a, idx, vals, n) do { \
516 DG_DYNARR_ASSERT((vals)!=NULL, "Don't pass NULL as vals to dg_dynarr_setn!"); \
517 size_t idx_=(idx); size_t end_=idx_+(size_t)n; \
518 dg__dynarr_checkidx((a),idx_); dg__dynarr_checkidx((a),end_-1); \
519 if((vals)!=NULL && idx_ < (a).md.cnt && end_ <= (a).md.cnt) { \
520 size_t v_=0; \
521 while(idx_ < end_) (a).p[idx_++] = (vals)[v_++]; \
522 }} DG__DYNARR_WHILE0
523
524 /* delete the element at idx, moving all following elements (=> keeps order) */
525 #define dg_dynarr_delete(a, idx) \
526 (dg__dynarr_checkidx((a),(idx)), dg__dynarr_delete(dg__dynarr_unp(a), (idx), 1))
527
528 /* delete n elements starting at idx, moving all following elements (=> keeps order) */
529 #define dg_dynarr_deleten(a, idx, n) \
530 (dg__dynarr_checkidx((a),(idx)), dg__dynarr_delete(dg__dynarr_unp(a), (idx), (n)))
531 /* TODO: check whether idx+n < count? */
532
533 /* delete the element at idx, move the last element there (=> doesn't keep order) */
534 #define dg_dynarr_deletefast(a, idx) \
535 (dg__dynarr_checkidx((a),(idx)), dg__dynarr_deletefast(dg__dynarr_unp(a), (idx), 1))
536
537 /* delete n elements starting at idx, move the last n elements there (=> doesn't keep order) */
538 #define dg_dynarr_deletenfast(a, idx, n) \
539 (dg__dynarr_checkidx((a),(idx)), dg__dynarr_deletefast(dg__dynarr_unp(a), idx, n))
540 /* TODO: check whether idx+n < count? */
541
542 /* removes all elements from the array, but does not free the buffer
543 * (if you want to free the buffer too, just use dg_dynarr_free())
544 */
545 #define dg_dynarr_clear(a) \
546 ((a).md.cnt=0)
547
548 /* sets the logical number of elements in the array
549 * if cnt > dg_dynarr_count(a), the logical count will be increased accordingly
550 * and the new elements will be uninitialized
551 */
552 #define dg_dynarr_setcount(a, n) \
553 (dg__dynarr_maybegrow(dg__dynarr_unp(a), (n)) ? ((a).md.cnt = (n)) : 0)
554
555 /* make sure the array can store cap elements without reallocating
556 * logical count remains unchanged
557 */
558 #define dg_dynarr_reserve(a, cap) \
559 dg__dynarr_maybegrow(dg__dynarr_unp(a), (cap))
560
561 /* this makes sure a only uses as much memory as for its elements
562 * => maybe useful if a used to contain a huge amount of elements,
563 * but you deleted most of them and want to free some memory
564 * Note however that this implies an allocation and copying the remaining
565 * elements, so only do this if it frees enough memory to be worthwhile!
566 */
567 #define dg_dynarr_shrink_to_fit(a) \
568 dg__dynarr_shrink_to_fit(dg__dynarr_unp(a))
569
570 #if (DG_DYNARR_INDEX_CHECK_LEVEL == 1) || (DG_DYNARR_INDEX_CHECK_LEVEL == 3)
571
572 /* removes and returns the last element of the array */
573 #define dg_dynarr_pop(a) \
574 (dg__dynarr_check_notempty((a), "Don't pop an empty array!"), \
575 (a).p[((a).md.cnt > 0) ? (--(a).md.cnt) : 0])
576
577 /* returns the last element of the array */
578 #define dg_dynarr_last(a) \
579 (dg__dynarr_check_notempty((a), "Don't call da_last() on an empty array!"), \
580 (a).p[((a).md.cnt > 0) ? ((a).md.cnt-1) : 0])
581
582 #elif (DG_DYNARR_INDEX_CHECK_LEVEL == 0) || (DG_DYNARR_INDEX_CHECK_LEVEL == 2)
583
584 /* removes and returns the last element of the array */
585 #define dg_dynarr_pop(a) \
586 (dg__dynarr_check_notempty((a), "Don't pop an empty array!"), \
587 (a).p[--(a).md.cnt])
588
589 /* returns the last element of the array */
590 #define dg_dynarr_last(a) \
591 (dg__dynarr_check_notempty((a), "Don't call da_last() on an empty array!"), \
592 (a).p[(a).md.cnt-1])
593
594 #else /* invalid DG_DYNARR_INDEX_CHECK_LEVEL */
595 #error Invalid index check level DG_DYNARR_INDEX_CHECK_LEVEL (must be 0-3) !
596 #endif /* DG_DYNARR_INDEX_CHECK_LEVEL */
597
598 /* returns the pointer *to* the last element of the array
599 * (in contrast to dg_dynarr_end() which returns a pointer *after* the last element)
600 * returns NULL if array is empty
601 */
602 #define dg_dynarr_lastptr(a) \
603 (((a).md.cnt > 0) ? ((a).p + (a).md.cnt - 1) : NULL)
604
605 /* get element at index idx (like a.p[idx]), but with checks
606 * (unless you disabled them with #define DG_DYNARR_INDEX_CHECK_LEVEL 0)
607 */
608 #define dg_dynarr_get(a, idx) \
609 (dg__dynarr_checkidx((a),(idx)), (a).p[dg__dynarr_idx((a).md, (idx))])
610
611 /* get pointer to element at index idx (like &a.p[idx]), but with checks
612 * (unless you disabled them with #define DG_DYNARR_INDEX_CHECK_LEVEL 0)
613 * if index-checks are disabled, it returns NULL on invalid index (else it asserts() before returning)
614 */
615 #define dg_dynarr_getptr(a, idx) \
616 (dg__dynarr_checkidx((a),(idx)), \
617 ((size_t)(idx) < (a).md.cnt) ? ((a).p+(size_t)(idx)) : NULL)
618
619 /* returns a pointer to the first element of the array
620 * (together with dg_dynarr_end() you can do C++-style iterating)
621 */
622 #define dg_dynarr_begin(a) \
623 ((a).p)
624
625 /* returns a pointer to the past-the-end element of the array
626 * Allows C++-style iterating, in case you're into that kind of thing:
627 * for(T *it=dg_dynarr_begin(a), *end=dg_dynarr_end(a); it!=end; ++it) foo(*it);
628 * (see dg_dynarr_lastptr() to get a pointer *to* the last element)
629 */
630 #define dg_dynarr_end(a) \
631 ((a).p + (a).md.cnt)
632
633 /* returns (logical) number of elements currently in the array */
634 #define dg_dynarr_count(a) \
635 ((a).md.cnt)
636
637 /* get the current reserved capacity of the array */
638 #define dg_dynarr_capacity(a) \
639 ((a).md.cap & DG__DYNARR_SIZE_T_ALL_BUT_MSB)
640
641 /* returns 1 if the array is empty, else 0 */
642 #define dg_dynarr_empty(a) \
643 ((a).md.cnt == 0)
644
645 /* returns 1 if the last (re)allocation when inserting failed (Out Of Memory)
646 * or if the array has never allocated any memory yet, else 0
647 * deleting the contents when growing fails instead of keeping old may seem
648 * a bit uncool, but it's simple and OOM should rarely happen on modern systems
649 * anyway - after all you need to deplete both RAM and swap/pagefile.sys
650 * or deplete the address space, which /might/ happen with 32bit applications
651 * but probably not with 64bit (at least in the foreseeable future)
652 */
653 #define dg_dynarr_oom(a) \
654 ((a).md.cap == 0)
655
656 /* sort a using the given qsort()-comparator cmp
657 * (just a slim wrapper around qsort())
658 */
659 #define dg_dynarr_sort(a, cmp) \
660 qsort((a).p, (a).md.cnt, sizeof((a).p[0]), (cmp))
661
662 /* ######### Implementation-Details that are not part of the API ########## */
663
664 #include <stdlib.h> /* size_t, malloc(), free(), realloc() */
665 #include <string.h> /* memset(), memcpy(), memmove() */
666
667 #ifdef __cplusplus
668 extern "C" {
669 #endif
670
671 typedef struct {
672 size_t cnt; /* logical number of elements */
673 size_t cap; /* cap & DG__DYNARR_SIZE_T_ALL_BUT_MSB is actual capacity (in elements, *not* bytes!) */
674 /* if(cap & DG__DYNARR_SIZE_T_MSB) the current memory is not allocated by dg_dynarr,
675 * but was set with dg_dynarr_init_external()
676 * that's handy to give an array a base-element storage on the stack, for example
677 * TODO: alternatively, we could introduce a flag field to this struct and use that,
678 * so we don't have to calculate & everytime cap is needed
679 */
680 } dg__dynarr_md;
681
682 /* I used to have the following in an enum, but MSVC assumes enums are always 32bit ints */
683 static const size_t DG__DYNARR_SIZE_T_MSB = ((size_t)1) << (sizeof(size_t)*8 - 1);
684 static const size_t DG__DYNARR_SIZE_T_ALL_BUT_MSB = (((size_t)1) << (sizeof(size_t)*8 - 1))-1;
685
686 /* "unpack" the elements of an array struct for use with helper functions
687 * (to void** arr, dg__dynarr_md* md, size_t itemsize)
688 */
689 #define dg__dynarr_unp(a) \
690 (void**)&(a).p, &(a).md, sizeof((a).p[0])
691
692 /* MSVC warns about "conditional expression is constant" when using the
693 * do { ... } while(0) idiom in macros..
694 */
695 #ifdef _MSC_VER
696 #if _MSC_VER >= 1400 // MSVC 2005 and newer
697 /* people claim MSVC 2005 and newer support __pragma, even though it's only documented
698 * for 2008+ (https://msdn.microsoft.com/en-us/library/d9x1s805%28v=vs.90%29.aspx)
699 * the following workaround is based on
700 * http://cnicholson.net/2009/03/stupid-c-tricks-dowhile0-and-c4127/
701 */
702 #define DG__DYNARR_WHILE0 \
703 __pragma(warning(push)) \
704 __pragma(warning(disable:4127)) \
705 while(0) \
706 __pragma(warning(pop))
707 #else /* older MSVC versions don't support __pragma - I heard this helps for them */
708 #define DG__DYNARR_WHILE0 while(0,0)
709 #endif
710
711 #else /* other compilers */
712
713 #define DG__DYNARR_WHILE0 while(0)
714
715 #endif /* _MSC_VER */
716
717 #if (DG_DYNARR_INDEX_CHECK_LEVEL == 2) || (DG_DYNARR_INDEX_CHECK_LEVEL == 3)
718
719 #define dg__dynarr_checkidx(a,i) \
720 DG_DYNARR_ASSERT((size_t)i < a.md.cnt, "index out of bounds!")
721
722 /* special case for insert operations: == cnt is also ok, insert will append then */
723 #define dg__dynarr_checkidxle(a,i) \
724 DG_DYNARR_ASSERT((size_t)i <= a.md.cnt, "index out of bounds!")
725
726 #define dg__dynarr_check_notempty(a, msg) \
727 DG_DYNARR_ASSERT(a.md.cnt > 0, msg)
728
729 #elif (DG_DYNARR_INDEX_CHECK_LEVEL == 0) || (DG_DYNARR_INDEX_CHECK_LEVEL == 1)
730
731 /* no assertions that check if index is valid */
732 #define dg__dynarr_checkidx(a,i) (void)0
733 #define dg__dynarr_checkidxle(a,i) (void)0
734
735 #define dg__dynarr_check_notempty(a, msg) (void)0
736
737 #else /* invalid DG_DYNARR_INDEX_CHECK_LEVEL */
738 #error Invalid index check level DG_DYNARR_INDEX_CHECK_LEVEL (must be 0-3) !
739 #endif /* DG_DYNARR_INDEX_CHECK_LEVEL */
740
741 #if (DG_DYNARR_INDEX_CHECK_LEVEL == 1) || (DG_DYNARR_INDEX_CHECK_LEVEL == 3)
742
743 /* the given index, if valid, else 0 */
744 #define dg__dynarr_idx(md,i) \
745 (((size_t)(i) < md.cnt) ? (size_t)(i) : 0)
746
747 #elif (DG_DYNARR_INDEX_CHECK_LEVEL == 0) || (DG_DYNARR_INDEX_CHECK_LEVEL == 2)
748
749 /* don't check and default to 0 if invalid, but just use the given value */
750 #define dg__dynarr_idx(md,i) (size_t)(i)
751
752 #else /* invalid DG_DYNARR_INDEX_CHECK_LEVEL */
753 #error Invalid index check level DG_DYNARR_INDEX_CHECK_LEVEL (must be 0-3) !
754 #endif /* DG_DYNARR_INDEX_CHECK_LEVEL */
755
756 /* the functions allocating/freeing memory are not implemented inline, but
757 * in the #ifdef DG_DYNARR_IMPLEMENTATION section
758 * one reason is that dg__dynarr_grow has the most code in it, the other is
759 * that windows has weird per-dll heaps so free() or realloc() should be
760 * called from code in the same dll that allocated the memory - these kind
761 * of wrapper functions that end up compiled into the exe or *one* dll
762 * (instead of inline functions compiled into everything) should ensure that.
763 */
764
765 DG_DYNARR_DEF void
766 dg__dynarr_free(void** p, dg__dynarr_md* md);
767
768 DG_DYNARR_DEF void
769 dg__dynarr_shrink_to_fit(void** arr, dg__dynarr_md* md, size_t itemsize);
770
771 /* grow array to have enough space for at least min_needed elements
772 * if it fails (OOM), the array will be deleted, a.p will be NULL, a.md.cap and a.md.cnt will be 0
773 * and the functions returns 0; else (on success) it returns 1
774 */
775 DG_DYNARR_DEF int
776 dg__dynarr_grow(void** arr, dg__dynarr_md* md, size_t itemsize, size_t min_needed);
777
778 /* the following functions are implemented inline, because they're quite short
779 * and mosty implemented in functions so the macros don't get too ugly
780 */
781
782 DG_DYNARR_INLINE void
dg__dynarr_init(void ** p,dg__dynarr_md * md,void * buf,size_t buf_cap)783 dg__dynarr_init(void** p, dg__dynarr_md* md, void* buf, size_t buf_cap)
784 {
785 *p = buf;
786 md->cnt = 0;
787 if(buf == NULL) md->cap = 0;
788 else md->cap = (DG__DYNARR_SIZE_T_MSB | buf_cap);
789 }
790
791 DG_DYNARR_INLINE int
dg__dynarr_maybegrow(void ** arr,dg__dynarr_md * md,size_t itemsize,size_t min_needed)792 dg__dynarr_maybegrow(void** arr, dg__dynarr_md* md, size_t itemsize, size_t min_needed)
793 {
794 if((md->cap & DG__DYNARR_SIZE_T_ALL_BUT_MSB) >= min_needed) return 1;
795 else return dg__dynarr_grow(arr, md, itemsize, min_needed);
796 }
797
798 DG_DYNARR_INLINE int
dg__dynarr_maybegrowadd(void ** arr,dg__dynarr_md * md,size_t itemsize,size_t num_add)799 dg__dynarr_maybegrowadd(void** arr, dg__dynarr_md* md, size_t itemsize, size_t num_add)
800 {
801 size_t min_needed = md->cnt+num_add;
802 if((md->cap & DG__DYNARR_SIZE_T_ALL_BUT_MSB) >= min_needed) return 1;
803 else return dg__dynarr_grow(arr, md, itemsize, min_needed);
804 }
805
806 DG_DYNARR_INLINE int
dg__dynarr_insert(void ** arr,dg__dynarr_md * md,size_t itemsize,size_t idx,size_t n,int init0)807 dg__dynarr_insert(void** arr, dg__dynarr_md* md, size_t itemsize, size_t idx, size_t n, int init0)
808 {
809 /* allow idx == md->cnt to append */
810 size_t oldCount = md->cnt;
811 size_t newCount = oldCount+n;
812 if(idx <= oldCount && dg__dynarr_maybegrow(arr, md, itemsize, newCount))
813 {
814 unsigned char* p = (unsigned char*)*arr; /* *arr might have changed in dg__dynarr_grow()! */
815 /* move all existing items after a[idx] to a[idx+n] */
816 if(idx < oldCount) memmove(p+(idx+n)*itemsize, p+idx*itemsize, itemsize*(oldCount - idx));
817
818 /* if the memory is supposed to be zeroed, do that */
819 if(init0) memset(p+idx*itemsize, 0, n*itemsize);
820
821 md->cnt = newCount;
822 return 1;
823 }
824 return 0;
825 }
826
827 DG_DYNARR_INLINE int
dg__dynarr_add(void ** arr,dg__dynarr_md * md,size_t itemsize,size_t n,int init0)828 dg__dynarr_add(void** arr, dg__dynarr_md* md, size_t itemsize, size_t n, int init0)
829 {
830 size_t cnt = md->cnt;
831 if(dg__dynarr_maybegrow(arr, md, itemsize, cnt+n))
832 {
833 unsigned char* p = (unsigned char*)*arr; /* *arr might have changed in dg__dynarr_grow()! */
834 /* if the memory is supposed to be zeroed, do that */
835 if(init0) memset(p+cnt*itemsize, 0, n*itemsize);
836
837 md->cnt += n;
838 return 1;
839 }
840 return 0;
841 }
842
843 DG_DYNARR_INLINE void
dg__dynarr_delete(void ** arr,dg__dynarr_md * md,size_t itemsize,size_t idx,size_t n)844 dg__dynarr_delete(void** arr, dg__dynarr_md* md, size_t itemsize, size_t idx, size_t n)
845 {
846 size_t cnt = md->cnt;
847 if(idx < cnt)
848 {
849 if(idx+n >= cnt) md->cnt = idx; /* removing last element(s) => just reduce count */
850 else
851 {
852 unsigned char* p = (unsigned char*)*arr;
853 /* move all items following a[idx+n] to a[idx] */
854 memmove(p+itemsize*idx, p+itemsize*(idx+n), itemsize*(cnt - (idx+n)));
855 md->cnt -= n;
856 }
857 }
858 }
859
860 DG_DYNARR_INLINE void
dg__dynarr_deletefast(void ** arr,dg__dynarr_md * md,size_t itemsize,size_t idx,size_t n)861 dg__dynarr_deletefast(void** arr, dg__dynarr_md* md, size_t itemsize, size_t idx, size_t n)
862 {
863 size_t cnt = md->cnt;
864 if(idx < cnt)
865 {
866 if(idx+n >= cnt) md->cnt = idx; /* removing last element(s) => just reduce count */
867 else
868 {
869 unsigned char* p = (unsigned char*)*arr;
870 /* copy the last n items to a[idx] - but handle the case that
871 * the array has less than n elements left after the deleted elements
872 */
873 size_t numItemsAfterDeleted = cnt - (idx+n);
874 size_t m = (n < numItemsAfterDeleted) ? n : numItemsAfterDeleted;
875 memcpy(p+itemsize*idx, p+itemsize*(cnt - m), itemsize*m);
876 md->cnt -= n;
877 }
878 }
879 }
880
881 #ifdef __cplusplus
882 } /* extern "C" */
883 #endif
884
885 #endif /* DG__DYNARR_H */
886
887 /* ############## Implementation of non-inline functions ############## */
888
889 #ifdef DG_DYNARR_IMPLEMENTATION
890
891 /* by default, C's malloc(), realloc() and free() is used to allocate/free heap memory.
892 * you can #define DG_DYNARR_MALLOC, DG_DYNARR_REALLOC and DG_DYNARR_FREE
893 * to provide alternative implementations like Win32 Heap(Re)Alloc/HeapFree
894 */
895 #ifndef DG_DYNARR_MALLOC
896 #define DG_DYNARR_MALLOC(elemSize, numElems) malloc(elemSize*numElems)
897
898 /* oldNumElems is not used here, but maybe you need it for your allocator
899 * to copy the old elements over
900 */
901 #define DG_DYNARR_REALLOC(ptr, elemSize, oldNumElems, newCapacity) \
902 realloc(ptr, elemSize*newCapacity);
903
904 #define DG_DYNARR_FREE(ptr) free(ptr)
905 #endif
906
907 /* you can #define DG_DYNARR_OUT_OF_MEMORY to some code that will be executed
908 * if allocating memory fails
909 */
910 #ifndef DG_DYNARR_OUT_OF_MEMORY
911 #define DG_DYNARR_OUT_OF_MEMORY DG_DYNARR_ASSERT(0, "Out of Memory!");
912 #endif
913
914 #ifdef __cplusplus
915 extern "C" {
916 #endif
917
918 DG_DYNARR_DEF void
dg__dynarr_free(void ** p,dg__dynarr_md * md)919 dg__dynarr_free(void** p, dg__dynarr_md* md)
920 {
921 /* only free memory if it doesn't point to external memory */
922 if(!(md->cap & DG__DYNARR_SIZE_T_MSB))
923 {
924 DG_DYNARR_FREE(*p);
925 *p = NULL;
926 md->cap = 0;
927 }
928 md->cnt = 0;
929 }
930
931 DG_DYNARR_DEF int
dg__dynarr_grow(void ** arr,dg__dynarr_md * md,size_t itemsize,size_t min_needed)932 dg__dynarr_grow(void** arr, dg__dynarr_md* md, size_t itemsize, size_t min_needed)
933 {
934 size_t cap = md->cap & DG__DYNARR_SIZE_T_ALL_BUT_MSB;
935
936 DG_DYNARR_ASSERT(min_needed > cap, "dg__dynarr_grow() should only be called if storage actually needs to grow!");
937
938 if(min_needed < DG__DYNARR_SIZE_T_MSB)
939 {
940 size_t newcap = (cap > 4) ? (2*cap) : 8; /* allocate for at least 8 elements */
941 /* make sure not to set DG__DYNARR_SIZE_T_MSB (unlikely anyway) */
942 if(newcap >= DG__DYNARR_SIZE_T_MSB) newcap = DG__DYNARR_SIZE_T_MSB-1;
943 if(min_needed > newcap) newcap = min_needed;
944
945 /* the memory was allocated externally, don't free it, just copy contents */
946 if(md->cap & DG__DYNARR_SIZE_T_MSB)
947 {
948 void* p = DG_DYNARR_MALLOC(itemsize, newcap);
949 if(p != NULL) memcpy(p, *arr, itemsize*md->cnt);
950 *arr = p;
951 }
952 else
953 {
954 void* p = DG_DYNARR_REALLOC(*arr, itemsize, md->cnt, newcap);
955 if(p == NULL) DG_DYNARR_FREE(*arr); /* realloc failed, at least don't leak memory */
956 *arr = p;
957 }
958
959 /* TODO: handle OOM by setting highest bit of count and keeping old data? */
960
961 if(*arr) md->cap = newcap;
962 else
963 {
964 md->cap = 0;
965 md->cnt = 0;
966
967 DG_DYNARR_OUT_OF_MEMORY ;
968
969 return 0;
970 }
971 return 1;
972 }
973 DG_DYNARR_ASSERT(min_needed < DG__DYNARR_SIZE_T_MSB, "Arrays must stay below SIZE_T_MAX/2 elements!");
974 return 0;
975 }
976
977 DG_DYNARR_DEF void
dg__dynarr_shrink_to_fit(void ** arr,dg__dynarr_md * md,size_t itemsize)978 dg__dynarr_shrink_to_fit(void** arr, dg__dynarr_md* md, size_t itemsize)
979 {
980 /* only do this if we allocated the memory ourselves */
981 if(!(md->cap & DG__DYNARR_SIZE_T_MSB))
982 {
983 size_t cnt = md->cnt;
984 if(cnt == 0) dg__dynarr_free(arr, md);
985 else if((md->cap & DG__DYNARR_SIZE_T_ALL_BUT_MSB) > cnt)
986 {
987 void* p = DG_DYNARR_MALLOC(itemsize, cnt);
988 if(p != NULL)
989 {
990 memcpy(p, *arr, cnt*itemsize);
991 md->cap = cnt;
992 DG_DYNARR_FREE(*arr);
993 *arr = p;
994 }
995 }
996 }
997 }
998
999 #ifdef __cplusplus
1000 } /* extern "C" */
1001 #endif
1002
1003 #endif /* DG_DYNARR_IMPLEMENTATION */
1004