1 /*
2 * Copyright (c) 2013 Hugh Bailey <obs.jim@gmail.com>
3 *
4 * Permission to use, copy, modify, and distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 */
16
17 #pragma once
18
19 #include "c99defs.h"
20 #include <string.h>
21 #include <stdlib.h>
22 #include <assert.h>
23
24 #include "bmem.h"
25
26 #ifdef __cplusplus
27 extern "C" {
28 #endif
29
30 /*
31 * Dynamic array.
32 *
33 * NOTE: Not type-safe when using directly.
34 * Specifying size per call with inline maximizes compiler optimizations
35 *
36 * See DARRAY macro at the bottom of the file for slightly safer usage.
37 */
38
39 #define DARRAY_INVALID ((size_t)-1)
40
41 struct darray {
42 void *array;
43 size_t num;
44 size_t capacity;
45 };
46
darray_init(struct darray * dst)47 static inline void darray_init(struct darray *dst)
48 {
49 dst->array = NULL;
50 dst->num = 0;
51 dst->capacity = 0;
52 }
53
darray_free(struct darray * dst)54 static inline void darray_free(struct darray *dst)
55 {
56 bfree(dst->array);
57 dst->array = NULL;
58 dst->num = 0;
59 dst->capacity = 0;
60 }
61
darray_alloc_size(const size_t element_size,const struct darray * da)62 static inline size_t darray_alloc_size(const size_t element_size,
63 const struct darray *da)
64 {
65 return element_size * da->num;
66 }
67
darray_item(const size_t element_size,const struct darray * da,size_t idx)68 static inline void *darray_item(const size_t element_size,
69 const struct darray *da, size_t idx)
70 {
71 return (void *)(((uint8_t *)da->array) + element_size * idx);
72 }
73
darray_end(const size_t element_size,const struct darray * da)74 static inline void *darray_end(const size_t element_size,
75 const struct darray *da)
76 {
77 if (!da->num)
78 return NULL;
79
80 return darray_item(element_size, da, da->num - 1);
81 }
82
darray_reserve(const size_t element_size,struct darray * dst,const size_t capacity)83 static inline void darray_reserve(const size_t element_size, struct darray *dst,
84 const size_t capacity)
85 {
86 void *ptr;
87 if (capacity == 0 || capacity <= dst->capacity)
88 return;
89
90 ptr = bmalloc(element_size * capacity);
91 if (dst->array) {
92 if (dst->num)
93 memcpy(ptr, dst->array, element_size * dst->num);
94
95 bfree(dst->array);
96 }
97 dst->array = ptr;
98 dst->capacity = capacity;
99 }
100
darray_ensure_capacity(const size_t element_size,struct darray * dst,const size_t new_size)101 static inline void darray_ensure_capacity(const size_t element_size,
102 struct darray *dst,
103 const size_t new_size)
104 {
105 size_t new_cap;
106 void *ptr;
107 if (new_size <= dst->capacity)
108 return;
109
110 new_cap = (!dst->capacity) ? new_size : dst->capacity * 2;
111 if (new_size > new_cap)
112 new_cap = new_size;
113 ptr = bmalloc(element_size * new_cap);
114 if (dst->array) {
115 if (dst->capacity)
116 memcpy(ptr, dst->array, element_size * dst->capacity);
117
118 bfree(dst->array);
119 }
120 dst->array = ptr;
121 dst->capacity = new_cap;
122 }
123
darray_resize(const size_t element_size,struct darray * dst,const size_t size)124 static inline void darray_resize(const size_t element_size, struct darray *dst,
125 const size_t size)
126 {
127 int b_clear;
128 size_t old_num;
129
130 if (size == dst->num) {
131 return;
132 } else if (size == 0) {
133 dst->num = 0;
134 return;
135 }
136
137 b_clear = size > dst->num;
138 old_num = dst->num;
139
140 darray_ensure_capacity(element_size, dst, size);
141 dst->num = size;
142
143 if (b_clear)
144 memset(darray_item(element_size, dst, old_num), 0,
145 element_size * (dst->num - old_num));
146 }
147
darray_copy(const size_t element_size,struct darray * dst,const struct darray * da)148 static inline void darray_copy(const size_t element_size, struct darray *dst,
149 const struct darray *da)
150 {
151 if (da->num == 0) {
152 darray_free(dst);
153 } else {
154 darray_resize(element_size, dst, da->num);
155 memcpy(dst->array, da->array, element_size * da->num);
156 }
157 }
158
darray_copy_array(const size_t element_size,struct darray * dst,const void * array,const size_t num)159 static inline void darray_copy_array(const size_t element_size,
160 struct darray *dst, const void *array,
161 const size_t num)
162 {
163 darray_resize(element_size, dst, num);
164 memcpy(dst->array, array, element_size * dst->num);
165 }
166
darray_move(struct darray * dst,struct darray * src)167 static inline void darray_move(struct darray *dst, struct darray *src)
168 {
169 darray_free(dst);
170 memcpy(dst, src, sizeof(struct darray));
171 src->array = NULL;
172 src->capacity = 0;
173 src->num = 0;
174 }
175
darray_find(const size_t element_size,const struct darray * da,const void * item,const size_t idx)176 static inline size_t darray_find(const size_t element_size,
177 const struct darray *da, const void *item,
178 const size_t idx)
179 {
180 size_t i;
181
182 assert(idx <= da->num);
183
184 for (i = idx; i < da->num; i++) {
185 void *compare = darray_item(element_size, da, i);
186 if (memcmp(compare, item, element_size) == 0)
187 return i;
188 }
189
190 return DARRAY_INVALID;
191 }
192
darray_push_back(const size_t element_size,struct darray * dst,const void * item)193 static inline size_t darray_push_back(const size_t element_size,
194 struct darray *dst, const void *item)
195 {
196 darray_ensure_capacity(element_size, dst, ++dst->num);
197 memcpy(darray_end(element_size, dst), item, element_size);
198
199 return dst->num - 1;
200 }
201
darray_push_back_new(const size_t element_size,struct darray * dst)202 static inline void *darray_push_back_new(const size_t element_size,
203 struct darray *dst)
204 {
205 void *last;
206
207 darray_ensure_capacity(element_size, dst, ++dst->num);
208
209 last = darray_end(element_size, dst);
210 memset(last, 0, element_size);
211 return last;
212 }
213
darray_push_back_array(const size_t element_size,struct darray * dst,const void * array,const size_t num)214 static inline size_t darray_push_back_array(const size_t element_size,
215 struct darray *dst,
216 const void *array, const size_t num)
217 {
218 size_t old_num;
219 if (!dst)
220 return 0;
221 if (!array || !num)
222 return dst->num;
223
224 old_num = dst->num;
225 darray_resize(element_size, dst, dst->num + num);
226 memcpy(darray_item(element_size, dst, old_num), array,
227 element_size * num);
228
229 return old_num;
230 }
231
darray_push_back_darray(const size_t element_size,struct darray * dst,const struct darray * da)232 static inline size_t darray_push_back_darray(const size_t element_size,
233 struct darray *dst,
234 const struct darray *da)
235 {
236 return darray_push_back_array(element_size, dst, da->array, da->num);
237 }
238
darray_insert(const size_t element_size,struct darray * dst,const size_t idx,const void * item)239 static inline void darray_insert(const size_t element_size, struct darray *dst,
240 const size_t idx, const void *item)
241 {
242 void *new_item;
243 size_t move_count;
244
245 assert(idx <= dst->num);
246
247 if (idx == dst->num) {
248 darray_push_back(element_size, dst, item);
249 return;
250 }
251
252 move_count = dst->num - idx;
253 darray_ensure_capacity(element_size, dst, ++dst->num);
254
255 new_item = darray_item(element_size, dst, idx);
256
257 memmove(darray_item(element_size, dst, idx + 1), new_item,
258 move_count * element_size);
259 memcpy(new_item, item, element_size);
260 }
261
darray_insert_new(const size_t element_size,struct darray * dst,const size_t idx)262 static inline void *darray_insert_new(const size_t element_size,
263 struct darray *dst, const size_t idx)
264 {
265 void *item;
266 size_t move_count;
267
268 assert(idx <= dst->num);
269 if (idx == dst->num)
270 return darray_push_back_new(element_size, dst);
271
272 item = darray_item(element_size, dst, idx);
273
274 move_count = dst->num - idx;
275 darray_ensure_capacity(element_size, dst, ++dst->num);
276 memmove(darray_item(element_size, dst, idx + 1), item,
277 move_count * element_size);
278
279 memset(item, 0, element_size);
280 return item;
281 }
282
darray_insert_array(const size_t element_size,struct darray * dst,const size_t idx,const void * array,const size_t num)283 static inline void darray_insert_array(const size_t element_size,
284 struct darray *dst, const size_t idx,
285 const void *array, const size_t num)
286 {
287 size_t old_num;
288
289 assert(array != NULL);
290 assert(num != 0);
291 assert(idx <= dst->num);
292
293 old_num = dst->num;
294 darray_resize(element_size, dst, dst->num + num);
295
296 memmove(darray_item(element_size, dst, idx + num),
297 darray_item(element_size, dst, idx),
298 element_size * (old_num - idx));
299 memcpy(darray_item(element_size, dst, idx), array, element_size * num);
300 }
301
darray_insert_darray(const size_t element_size,struct darray * dst,const size_t idx,const struct darray * da)302 static inline void darray_insert_darray(const size_t element_size,
303 struct darray *dst, const size_t idx,
304 const struct darray *da)
305 {
306 darray_insert_array(element_size, dst, idx, da->array, da->num);
307 }
308
darray_erase(const size_t element_size,struct darray * dst,const size_t idx)309 static inline void darray_erase(const size_t element_size, struct darray *dst,
310 const size_t idx)
311 {
312 assert(idx < dst->num);
313
314 if (idx >= dst->num || !--dst->num)
315 return;
316
317 memmove(darray_item(element_size, dst, idx),
318 darray_item(element_size, dst, idx + 1),
319 element_size * (dst->num - idx));
320 }
321
darray_erase_item(const size_t element_size,struct darray * dst,const void * item)322 static inline void darray_erase_item(const size_t element_size,
323 struct darray *dst, const void *item)
324 {
325 size_t idx = darray_find(element_size, dst, item, 0);
326 if (idx != DARRAY_INVALID)
327 darray_erase(element_size, dst, idx);
328 }
329
darray_erase_range(const size_t element_size,struct darray * dst,const size_t start,const size_t end)330 static inline void darray_erase_range(const size_t element_size,
331 struct darray *dst, const size_t start,
332 const size_t end)
333 {
334 size_t count, move_count;
335
336 assert(start <= dst->num);
337 assert(end <= dst->num);
338 assert(end > start);
339
340 count = end - start;
341 if (count == 1) {
342 darray_erase(element_size, dst, start);
343 return;
344 } else if (count == dst->num) {
345 dst->num = 0;
346 return;
347 }
348
349 move_count = dst->num - end;
350 if (move_count)
351 memmove(darray_item(element_size, dst, start),
352 darray_item(element_size, dst, end),
353 move_count * element_size);
354
355 dst->num -= count;
356 }
357
darray_pop_back(const size_t element_size,struct darray * dst)358 static inline void darray_pop_back(const size_t element_size,
359 struct darray *dst)
360 {
361 assert(dst->num != 0);
362
363 if (dst->num)
364 darray_erase(element_size, dst, dst->num - 1);
365 }
366
darray_join(const size_t element_size,struct darray * dst,struct darray * da)367 static inline void darray_join(const size_t element_size, struct darray *dst,
368 struct darray *da)
369 {
370 darray_push_back_darray(element_size, dst, da);
371 darray_free(da);
372 }
373
darray_split(const size_t element_size,struct darray * dst1,struct darray * dst2,const struct darray * da,const size_t idx)374 static inline void darray_split(const size_t element_size, struct darray *dst1,
375 struct darray *dst2, const struct darray *da,
376 const size_t idx)
377 {
378 struct darray temp;
379
380 assert(da->num >= idx);
381 assert(dst1 != dst2);
382
383 darray_init(&temp);
384 darray_copy(element_size, &temp, da);
385
386 darray_free(dst1);
387 darray_free(dst2);
388
389 if (da->num) {
390 if (idx)
391 darray_copy_array(element_size, dst1, temp.array,
392 temp.num);
393 if (idx < temp.num - 1)
394 darray_copy_array(element_size, dst2,
395 darray_item(element_size, &temp, idx),
396 temp.num - idx);
397 }
398
399 darray_free(&temp);
400 }
401
darray_move_item(const size_t element_size,struct darray * dst,const size_t from,const size_t to)402 static inline void darray_move_item(const size_t element_size,
403 struct darray *dst, const size_t from,
404 const size_t to)
405 {
406 void *temp, *p_from, *p_to;
407
408 if (from == to)
409 return;
410
411 temp = malloc(element_size);
412 if (!temp) {
413 bcrash("darray_move_item: out of memory");
414 return;
415 }
416
417 p_from = darray_item(element_size, dst, from);
418 p_to = darray_item(element_size, dst, to);
419
420 memcpy(temp, p_from, element_size);
421
422 if (to < from)
423 memmove(darray_item(element_size, dst, to + 1), p_to,
424 element_size * (from - to));
425 else
426 memmove(p_from, darray_item(element_size, dst, from + 1),
427 element_size * (to - from));
428
429 memcpy(p_to, temp, element_size);
430 free(temp);
431 }
432
darray_swap(const size_t element_size,struct darray * dst,const size_t a,const size_t b)433 static inline void darray_swap(const size_t element_size, struct darray *dst,
434 const size_t a, const size_t b)
435 {
436 void *temp, *a_ptr, *b_ptr;
437
438 assert(a < dst->num);
439 assert(b < dst->num);
440
441 if (a == b)
442 return;
443
444 temp = malloc(element_size);
445 if (!temp)
446 bcrash("darray_swap: out of memory");
447
448 a_ptr = darray_item(element_size, dst, a);
449 b_ptr = darray_item(element_size, dst, b);
450
451 memcpy(temp, a_ptr, element_size);
452 memcpy(a_ptr, b_ptr, element_size);
453 memcpy(b_ptr, temp, element_size);
454
455 free(temp);
456 }
457
458 /*
459 * Defines to make dynamic arrays more type-safe.
460 * Note: Still not 100% type-safe but much better than using darray directly
461 * Makes it a little easier to use as well.
462 *
463 * I did -not- want to use a gigantic macro to generate a crapload of
464 * typesafe inline functions per type. It just feels like a mess to me.
465 */
466
467 #define DARRAY(type) \
468 union { \
469 struct darray da; \
470 struct { \
471 type *array; \
472 size_t num; \
473 size_t capacity; \
474 }; \
475 }
476
477 #define da_init(v) darray_init(&v.da)
478
479 #define da_free(v) darray_free(&v.da)
480
481 #define da_alloc_size(v) (sizeof(*v.array) * v.num)
482
483 #define da_end(v) darray_end(sizeof(*v.array), &v.da)
484
485 #define da_reserve(v, capacity) \
486 darray_reserve(sizeof(*v.array), &v.da, capacity)
487
488 #define da_resize(v, size) darray_resize(sizeof(*v.array), &v.da, size)
489
490 #define da_copy(dst, src) darray_copy(sizeof(*dst.array), &dst.da, &src.da)
491
492 #define da_copy_array(dst, src_array, n) \
493 darray_copy_array(sizeof(*dst.array), &dst.da, src_array, n)
494
495 #define da_move(dst, src) darray_move(&dst.da, &src.da)
496
497 #ifdef ENABLE_DARRAY_TYPE_TEST
498 #ifdef __cplusplus
499 #define da_type_test(v, item) \
500 ({ \
501 if (false) { \
502 auto _t = v.array; \
503 _t = (item); \
504 (void)_t; \
505 *(v).array = *(item); \
506 } \
507 })
508 #else
509 #define da_type_test(v, item) \
510 ({ \
511 if (false) { \
512 const typeof(*v.array) *_t; \
513 _t = (item); \
514 (void)_t; \
515 *(v).array = *(item); \
516 } \
517 })
518 #endif
519 #endif // ENABLE_DARRAY_TYPE_TEST
520
521 #ifdef ENABLE_DARRAY_TYPE_TEST
522 #define da_find(v, item, idx) \
523 ({ \
524 da_type_test(v, item); \
525 darray_find(sizeof(*v.array), &v.da, item, idx); \
526 })
527 #else
528 #define da_find(v, item, idx) darray_find(sizeof(*v.array), &v.da, item, idx)
529 #endif
530
531 #ifdef ENABLE_DARRAY_TYPE_TEST
532 #define da_push_back(v, item) \
533 ({ \
534 da_type_test(v, item); \
535 darray_push_back(sizeof(*v.array), &v.da, item); \
536 })
537 #else
538 #define da_push_back(v, item) darray_push_back(sizeof(*v.array), &v.da, item)
539 #endif
540
541 #define da_push_back_new(v) darray_push_back_new(sizeof(*v.array), &v.da)
542
543 #ifdef ENABLE_DARRAY_TYPE_TEST
544 #define da_push_back_array(dst, src_array, n) \
545 ({ \
546 da_type_test(dst, src_array); \
547 darray_push_back_array(sizeof(*dst.array), &dst.da, src_array, \
548 n); \
549 })
550 #else
551 #define da_push_back_array(dst, src_array, n) \
552 darray_push_back_array(sizeof(*dst.array), &dst.da, src_array, n)
553 #endif
554
555 #ifdef ENABLE_DARRAY_TYPE_TEST
556 #define da_push_back_da(dst, src) \
557 ({ \
558 da_type_test(dst, src.array); \
559 darray_push_back_darray(sizeof(*dst.array), &dst.da, &src.da); \
560 })
561 #else
562 #define da_push_back_da(dst, src) \
563 darray_push_back_darray(sizeof(*dst.array), &dst.da, &src.da)
564 #endif
565
566 #ifdef ENABLE_DARRAY_TYPE_TEST
567 #define da_insert(v, idx, item) \
568 ({ \
569 da_type_test(v, item); \
570 darray_insert(sizeof(*v.array), &v.da, idx, item); \
571 })
572 #else
573 #define da_insert(v, idx, item) \
574 darray_insert(sizeof(*v.array), &v.da, idx, item)
575 #endif
576
577 #define da_insert_new(v, idx) darray_insert_new(sizeof(*v.array), &v.da, idx)
578
579 #ifdef ENABLE_DARRAY_TYPE_TEST
580 #define da_insert_array(dst, idx, src_array, n) \
581 ({ \
582 da_type_test(dst, src_array); \
583 darray_insert_array(sizeof(*dst.array), &dst.da, idx, \
584 src_array, n); \
585 })
586 #else
587 #define da_insert_array(dst, idx, src_array, n) \
588 darray_insert_array(sizeof(*dst.array), &dst.da, idx, src_array, n)
589 #endif
590
591 #ifdef ENABLE_DARRAY_TYPE_TEST
592 #define da_insert_da(dst, idx, src) \
593 ({ \
594 da_type_test(dst, src.array); \
595 darray_insert_darray(sizeof(*dst.array), &dst.da, idx, \
596 &src.da); \
597 })
598 #else
599 #define da_insert_da(dst, idx, src) \
600 darray_insert_darray(sizeof(*dst.array), &dst.da, idx, &src.da)
601 #endif
602
603 #define da_erase(dst, idx) darray_erase(sizeof(*dst.array), &dst.da, idx)
604
605 #ifdef ENABLE_DARRAY_TYPE_TEST
606 #define da_erase_item(dst, item) \
607 ({ \
608 da_type_test(dst, item); \
609 darray_erase_item(sizeof(*dst.array), &dst.da, item); \
610 })
611 #else
612 #define da_erase_item(dst, item) \
613 darray_erase_item(sizeof(*dst.array), &dst.da, item)
614 #endif
615
616 #define da_erase_range(dst, from, to) \
617 darray_erase_range(sizeof(*dst.array), &dst.da, from, to)
618
619 #define da_pop_back(dst) darray_pop_back(sizeof(*dst.array), &dst.da);
620
621 #define da_join(dst, src) darray_join(sizeof(*dst.array), &dst.da, &src.da)
622
623 #define da_split(dst1, dst2, src, idx) \
624 darray_split(sizeof(*src.array), &dst1.da, &dst2.da, &src.da, idx)
625
626 #define da_move_item(v, from, to) \
627 darray_move_item(sizeof(*v.array), &v.da, from, to)
628
629 #define da_swap(v, idx1, idx2) darray_swap(sizeof(*v.array), &v.da, idx1, idx2)
630
631 #ifdef __cplusplus
632 }
633 #endif
634