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