Open Broadcaster Software
Free, open source software for live streaming and recording
darray.h
Go to the documentation of this file.
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 
47 static inline void darray_init(struct darray *dst)
48 {
49  dst->array = NULL;
50  dst->num = 0;
51  dst->capacity = 0;
52 }
53 
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 
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 
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 
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 
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->num)
88  return;
89 
90  ptr = bmalloc(element_size * capacity);
91  if (dst->num)
92  memcpy(ptr, dst->array, element_size * dst->num);
93  if (dst->array)
94  bfree(dst->array);
95  dst->array = ptr;
96  dst->capacity = capacity;
97 }
98 
99 static inline void darray_ensure_capacity(const size_t element_size,
100  struct darray *dst,
101  const size_t new_size)
102 {
103  size_t new_cap;
104  void *ptr;
105  if (new_size <= dst->capacity)
106  return;
107 
108  new_cap = (!dst->capacity) ? new_size : dst->capacity * 2;
109  if (new_size > new_cap)
110  new_cap = new_size;
111  ptr = bmalloc(element_size * new_cap);
112  if (dst->capacity)
113  memcpy(ptr, dst->array, element_size * dst->capacity);
114  if (dst->array)
115  bfree(dst->array);
116  dst->array = ptr;
117  dst->capacity = new_cap;
118 }
119 
120 static inline void darray_resize(const size_t element_size, struct darray *dst,
121  const size_t size)
122 {
123  int b_clear;
124  size_t old_num;
125 
126  if (size == dst->num) {
127  return;
128  } else if (size == 0) {
129  dst->num = 0;
130  return;
131  }
132 
133  b_clear = size > dst->num;
134  old_num = dst->num;
135 
136  darray_ensure_capacity(element_size, dst, size);
137  dst->num = size;
138 
139  if (b_clear)
140  memset(darray_item(element_size, dst, old_num), 0,
141  element_size * (dst->num - old_num));
142 }
143 
144 static inline void darray_copy(const size_t element_size, struct darray *dst,
145  const struct darray *da)
146 {
147  if (da->num == 0) {
148  darray_free(dst);
149  } else {
150  darray_resize(element_size, dst, da->num);
151  memcpy(dst->array, da->array, element_size * da->num);
152  }
153 }
154 
155 static inline void darray_copy_array(const size_t element_size,
156  struct darray *dst, const void *array,
157  const size_t num)
158 {
159  darray_resize(element_size, dst, num);
160  memcpy(dst->array, array, element_size * dst->num);
161 }
162 
163 static inline void darray_move(struct darray *dst, struct darray *src)
164 {
165  darray_free(dst);
166  memcpy(dst, src, sizeof(struct darray));
167  src->array = NULL;
168  src->capacity = 0;
169  src->num = 0;
170 }
171 
172 static inline size_t darray_find(const size_t element_size,
173  const struct darray *da, const void *item,
174  const size_t idx)
175 {
176  size_t i;
177 
178  assert(idx <= da->num);
179 
180  for (i = idx; i < da->num; i++) {
181  void *compare = darray_item(element_size, da, i);
182  if (memcmp(compare, item, element_size) == 0)
183  return i;
184  }
185 
186  return DARRAY_INVALID;
187 }
188 
189 static inline size_t darray_push_back(const size_t element_size,
190  struct darray *dst, const void *item)
191 {
192  darray_ensure_capacity(element_size, dst, ++dst->num);
193  memcpy(darray_end(element_size, dst), item, element_size);
194 
195  return dst->num - 1;
196 }
197 
198 static inline void *darray_push_back_new(const size_t element_size,
199  struct darray *dst)
200 {
201  void *last;
202 
203  darray_ensure_capacity(element_size, dst, ++dst->num);
204 
205  last = darray_end(element_size, dst);
206  memset(last, 0, element_size);
207  return last;
208 }
209 
210 static inline size_t darray_push_back_array(const size_t element_size,
211  struct darray *dst,
212  const void *array, const size_t num)
213 {
214  size_t old_num;
215  if (!dst)
216  return 0;
217  if (!array || !num)
218  return dst->num;
219 
220  old_num = dst->num;
221  darray_resize(element_size, dst, dst->num + num);
222  memcpy(darray_item(element_size, dst, old_num), array,
223  element_size * num);
224 
225  return old_num;
226 }
227 
228 static inline size_t darray_push_back_darray(const size_t element_size,
229  struct darray *dst,
230  const struct darray *da)
231 {
232  return darray_push_back_array(element_size, dst, da->array, da->num);
233 }
234 
235 static inline void darray_insert(const size_t element_size, struct darray *dst,
236  const size_t idx, const void *item)
237 {
238  void *new_item;
239  size_t move_count;
240 
241  assert(idx <= dst->num);
242 
243  if (idx == dst->num) {
244  darray_push_back(element_size, dst, item);
245  return;
246  }
247 
248  move_count = dst->num - idx;
249  darray_ensure_capacity(element_size, dst, ++dst->num);
250 
251  new_item = darray_item(element_size, dst, idx);
252 
253  memmove(darray_item(element_size, dst, idx + 1), new_item,
254  move_count * element_size);
255  memcpy(new_item, item, element_size);
256 }
257 
258 static inline void *darray_insert_new(const size_t element_size,
259  struct darray *dst, const size_t idx)
260 {
261  void *item;
262  size_t move_count;
263 
264  assert(idx <= dst->num);
265  if (idx == dst->num)
266  return darray_push_back_new(element_size, dst);
267 
268  item = darray_item(element_size, dst, idx);
269 
270  move_count = dst->num - idx;
271  darray_ensure_capacity(element_size, dst, ++dst->num);
272  memmove(darray_item(element_size, dst, idx + 1), item,
273  move_count * element_size);
274 
275  memset(item, 0, element_size);
276  return item;
277 }
278 
279 static inline void darray_insert_array(const size_t element_size,
280  struct darray *dst, const size_t idx,
281  const void *array, const size_t num)
282 {
283  size_t old_num;
284 
285  assert(array != NULL);
286  assert(num != 0);
287  assert(idx < dst->num);
288 
289  old_num = dst->num;
290  darray_resize(element_size, dst, dst->num + num);
291 
292  memmove(darray_item(element_size, dst, idx + num),
293  darray_item(element_size, dst, idx),
294  element_size * (old_num - idx));
295  memcpy(darray_item(element_size, dst, idx), array, element_size * num);
296 }
297 
298 static inline void darray_insert_darray(const size_t element_size,
299  struct darray *dst, const size_t idx,
300  const struct darray *da)
301 {
302  darray_insert_array(element_size, dst, idx, da->array, da->num);
303 }
304 
305 static inline void darray_erase(const size_t element_size, struct darray *dst,
306  const size_t idx)
307 {
308  assert(idx < dst->num);
309 
310  if (idx >= dst->num || !--dst->num)
311  return;
312 
313  memmove(darray_item(element_size, dst, idx),
314  darray_item(element_size, dst, idx + 1),
315  element_size * (dst->num - idx));
316 }
317 
318 static inline void darray_erase_item(const size_t element_size,
319  struct darray *dst, const void *item)
320 {
321  size_t idx = darray_find(element_size, dst, item, 0);
322  if (idx != DARRAY_INVALID)
323  darray_erase(element_size, dst, idx);
324 }
325 
326 static inline void darray_erase_range(const size_t element_size,
327  struct darray *dst, const size_t start,
328  const size_t end)
329 {
330  size_t count, move_count;
331 
332  assert(start <= dst->num);
333  assert(end <= dst->num);
334  assert(end > start);
335 
336  count = end - start;
337  if (count == 1) {
338  darray_erase(element_size, dst, start);
339  return;
340  } else if (count == dst->num) {
341  dst->num = 0;
342  return;
343  }
344 
345  move_count = dst->num - end;
346  if (move_count)
347  memmove(darray_item(element_size, dst, start),
348  darray_item(element_size, dst, end),
349  move_count * element_size);
350 
351  dst->num -= count;
352 }
353 
354 static inline void darray_pop_back(const size_t element_size,
355  struct darray *dst)
356 {
357  assert(dst->num != 0);
358 
359  if (dst->num)
360  darray_erase(element_size, dst, dst->num - 1);
361 }
362 
363 static inline void darray_join(const size_t element_size, struct darray *dst,
364  struct darray *da)
365 {
366  darray_push_back_darray(element_size, dst, da);
367  darray_free(da);
368 }
369 
370 static inline void darray_split(const size_t element_size, struct darray *dst1,
371  struct darray *dst2, const struct darray *da,
372  const size_t idx)
373 {
374  struct darray temp;
375 
376  assert(da->num >= idx);
377  assert(dst1 != dst2);
378 
379  darray_init(&temp);
380  darray_copy(element_size, &temp, da);
381 
382  darray_free(dst1);
383  darray_free(dst2);
384 
385  if (da->num) {
386  if (idx)
387  darray_copy_array(element_size, dst1, temp.array,
388  temp.num);
389  if (idx < temp.num - 1)
390  darray_copy_array(element_size, dst2,
391  darray_item(element_size, &temp, idx),
392  temp.num - idx);
393  }
394 
395  darray_free(&temp);
396 }
397 
398 static inline void darray_move_item(const size_t element_size,
399  struct darray *dst, const size_t from,
400  const size_t to)
401 {
402  void *temp, *p_from, *p_to;
403 
404  if (from == to)
405  return;
406 
407  temp = malloc(element_size);
408  p_from = darray_item(element_size, dst, from);
409  p_to = darray_item(element_size, dst, to);
410 
411  memcpy(temp, p_from, element_size);
412 
413  if (to < from)
414  memmove(darray_item(element_size, dst, to + 1), p_to,
415  element_size * (from - to));
416  else
417  memmove(p_from, darray_item(element_size, dst, from + 1),
418  element_size * (to - from));
419 
420  memcpy(p_to, temp, element_size);
421  free(temp);
422 }
423 
424 static inline void darray_swap(const size_t element_size, struct darray *dst,
425  const size_t a, const size_t b)
426 {
427  void *temp, *a_ptr, *b_ptr;
428 
429  assert(a < dst->num);
430  assert(b < dst->num);
431 
432  if (a == b)
433  return;
434 
435  temp = malloc(element_size);
436  a_ptr = darray_item(element_size, dst, a);
437  b_ptr = darray_item(element_size, dst, b);
438 
439  memcpy(temp, a_ptr, element_size);
440  memcpy(a_ptr, b_ptr, element_size);
441  memcpy(b_ptr, temp, element_size);
442 
443  free(temp);
444 }
445 
446 /*
447  * Defines to make dynamic arrays more type-safe.
448  * Note: Still not 100% type-safe but much better than using darray directly
449  * Makes it a little easier to use as well.
450  *
451  * I did -not- want to use a gigantic macro to generate a crapload of
452  * typesafe inline functions per type. It just feels like a mess to me.
453  */
454 
455 #define DARRAY(type) \
456  union { \
457  struct darray da; \
458  struct { \
459  type *array; \
460  size_t num; \
461  size_t capacity; \
462  }; \
463  }
464 
465 #define da_init(v) darray_init(&v.da)
466 
467 #define da_free(v) darray_free(&v.da)
468 
469 #define da_alloc_size(v) (sizeof(*v.array) * v.num)
470 
471 #define da_end(v) darray_end(sizeof(*v.array), &v.da)
472 
473 #define da_reserve(v, capacity) \
474  darray_reserve(sizeof(*v.array), &v.da, capacity)
475 
476 #define da_resize(v, size) darray_resize(sizeof(*v.array), &v.da, size)
477 
478 #define da_copy(dst, src) darray_copy(sizeof(*dst.array), &dst.da, &src.da)
479 
480 #define da_copy_array(dst, src_array, n) \
481  darray_copy_array(sizeof(*dst.array), &dst.da, src_array, n)
482 
483 #define da_move(dst, src) darray_move(&dst.da, &src.da)
484 
485 #define da_find(v, item, idx) darray_find(sizeof(*v.array), &v.da, item, idx)
486 
487 #define da_push_back(v, item) darray_push_back(sizeof(*v.array), &v.da, item)
488 
489 #define da_push_back_new(v) darray_push_back_new(sizeof(*v.array), &v.da)
490 
491 #define da_push_back_array(dst, src_array, n) \
492  darray_push_back_array(sizeof(*dst.array), &dst.da, src_array, n)
493 
494 #define da_push_back_da(dst, src) \
495  darray_push_back_darray(sizeof(*dst.array), &dst.da, &src.da)
496 
497 #define da_insert(v, idx, item) \
498  darray_insert(sizeof(*v.array), &v.da, idx, item)
499 
500 #define da_insert_new(v, idx) darray_insert_new(sizeof(*v.array), &v.da, idx)
501 
502 #define da_insert_array(dst, idx, src_array, n) \
503  darray_insert_array(sizeof(*dst.array), &dst.da, idx, src_array, n)
504 
505 #define da_insert_da(dst, idx, src) \
506  darray_insert_darray(sizeof(*dst.array), &dst.da, idx, &src.da)
507 
508 #define da_erase(dst, idx) darray_erase(sizeof(*dst.array), &dst.da, idx)
509 
510 #define da_erase_item(dst, item) \
511  darray_erase_item(sizeof(*dst.array), &dst.da, item)
512 
513 #define da_erase_range(dst, from, to) \
514  darray_erase_range(sizeof(*dst.array), &dst.da, from, to)
515 
516 #define da_pop_back(dst) darray_pop_back(sizeof(*dst.array), &dst.da);
517 
518 #define da_join(dst, src) darray_join(sizeof(*dst.array), &dst.da, &src.da)
519 
520 #define da_split(dst1, dst2, src, idx) \
521  darray_split(sizeof(*src.array), &dst1.da, &dst2.da, &src.da, idx)
522 
523 #define da_move_item(v, from, to) \
524  darray_move_item(sizeof(*v.array), &v.da, from, to)
525 
526 #define da_swap(v, idx1, idx2) darray_swap(sizeof(*v.array), &v.da, idx1, idx2)
527 
528 #ifdef __cplusplus
529 }
530 #endif
Definition: darray.h:41
size_t capacity
Definition: darray.h:44
#define DARRAY_INVALID
Definition: darray.h:39
unsigned char uint8_t
Definition: vc_stdint.h:27
EXPORT void * bmalloc(size_t size)
void * array
Definition: darray.h:42
size_t num
Definition: darray.h:43
EXPORT void bfree(void *ptr)