Open Broadcaster Software
Free, open source software for live streaming and recording
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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 = dst->num;
211 
212  assert(array != NULL);
213  assert(num != 0);
214 
215  darray_resize(element_size, dst, dst->num+num);
216  memcpy(darray_item(element_size, dst, old_num), array,
217  element_size*num);
218 
219  return old_num;
220 }
221 
222 static inline size_t darray_push_back_darray(const size_t element_size,
223  struct darray *dst, const struct darray *da)
224 {
225  return darray_push_back_array(element_size, dst, da->array, da->num);
226 }
227 
228 static inline void darray_insert(const size_t element_size, struct darray *dst,
229  const size_t idx, const void *item)
230 {
231  void *new_item;
232  size_t move_count;
233 
234  assert(idx <= dst->num);
235 
236  if (idx == dst->num) {
237  darray_push_back(element_size, dst, item);
238  return;
239  }
240 
241  move_count = dst->num - idx;
242  darray_ensure_capacity(element_size, dst, ++dst->num);
243 
244  new_item = darray_item(element_size, dst, idx);
245 
246  memmove(darray_item(element_size, dst, idx+1), new_item,
247  move_count*element_size);
248  memcpy(new_item, item, element_size);
249 }
250 
251 static inline void *darray_insert_new(const size_t element_size,
252  struct darray *dst, const size_t idx)
253 {
254  void *item;
255  size_t move_count;
256 
257  assert(idx <= dst->num);
258  if (idx == dst->num)
259  return darray_push_back_new(element_size, dst);
260 
261  item = darray_item(element_size, dst, idx);
262 
263  move_count = dst->num - idx;
264  darray_ensure_capacity(element_size, dst, ++dst->num);
265  memmove(darray_item(element_size, dst, idx+1), item,
266  move_count*element_size);
267 
268  memset(item, 0, element_size);
269  return item;
270 }
271 
272 static inline void darray_insert_array(const size_t element_size,
273  struct darray *dst, const size_t idx,
274  const void *array, const size_t num)
275 {
276  size_t old_num;
277 
278  assert(array != NULL);
279  assert(num != 0);
280  assert(idx < dst->num);
281 
282  old_num = dst->num;
283  darray_resize(element_size, dst, dst->num+num);
284 
285  memmove(darray_item(element_size, dst, idx+num),
286  darray_item(element_size, dst, idx),
287  element_size*(old_num-idx));
288  memcpy(darray_item(element_size, dst, idx), array, element_size*num);
289 }
290 
291 static inline void darray_insert_darray(const size_t element_size,
292  struct darray *dst, const size_t idx, const struct darray *da)
293 {
294  darray_insert_array(element_size, dst, idx, da->array, da->num);
295 }
296 
297 static inline void darray_erase(const size_t element_size, struct darray *dst,
298  const size_t idx)
299 {
300  assert(idx < dst->num);
301 
302  if (idx >= dst->num || !--dst->num)
303  return;
304 
305  memmove(darray_item(element_size, dst, idx),
306  darray_item(element_size, dst, idx+1),
307  element_size*(dst->num-idx));
308 }
309 
310 static inline void darray_erase_item(const size_t element_size,
311  struct darray *dst, const void *item)
312 {
313  size_t idx = darray_find(element_size, dst, item, 0);
314  if (idx != DARRAY_INVALID)
315  darray_erase(element_size, dst, idx);
316 }
317 
318 static inline void darray_erase_range(const size_t element_size,
319  struct darray *dst, const size_t start, const size_t end)
320 {
321  size_t count, move_count;
322 
323  assert(start <= dst->num);
324  assert(end <= dst->num);
325  assert(end > start);
326 
327  count = end-start;
328  if (count == 1) {
329  darray_erase(element_size, dst, start);
330  return;
331  } else if (count == dst->num) {
332  dst->num = 0;
333  return;
334  }
335 
336  move_count = dst->num - end;
337  if (move_count)
338  memmove(darray_item(element_size, dst, start),
339  darray_item(element_size, dst, end),
340  move_count * element_size);
341 
342  dst->num -= count;
343 }
344 
345 static inline void darray_pop_back(const size_t element_size,
346  struct darray *dst)
347 {
348  assert(dst->num != 0);
349 
350  if (dst->num)
351  darray_erase(element_size, dst, dst->num-1);
352 }
353 
354 static inline void darray_join(const size_t element_size, struct darray *dst,
355  struct darray *da)
356 {
357  darray_push_back_darray(element_size, dst, da);
358  darray_free(da);
359 }
360 
361 static inline void darray_split(const size_t element_size, struct darray *dst1,
362  struct darray *dst2, const struct darray *da, const size_t idx)
363 {
364  struct darray temp;
365 
366  assert(da->num >= idx);
367  assert(dst1 != dst2);
368 
369  darray_init(&temp);
370  darray_copy(element_size, &temp, da);
371 
372  darray_free(dst1);
373  darray_free(dst2);
374 
375  if (da->num) {
376  if (idx)
377  darray_copy_array(element_size, dst1, temp.array,
378  temp.num);
379  if (idx < temp.num-1)
380  darray_copy_array(element_size, dst2,
381  darray_item(element_size, &temp, idx),
382  temp.num-idx);
383  }
384 
385  darray_free(&temp);
386 }
387 
388 static inline void darray_move_item(const size_t element_size,
389  struct darray *dst, const size_t from, const size_t to)
390 {
391  void *temp, *p_from, *p_to;
392 
393  if (from == to)
394  return;
395 
396  temp = malloc(element_size);
397  p_from = darray_item(element_size, dst, from);
398  p_to = darray_item(element_size, dst, to);
399 
400  memcpy(temp, p_from, element_size);
401 
402  if (to < from)
403  memmove(darray_item(element_size, dst, to+1), p_to,
404  element_size*(from-to));
405  else
406  memmove(p_from, darray_item(element_size, dst, from+1),
407  element_size*(to-from));
408 
409  memcpy(p_to, temp, element_size);
410  free(temp);
411 }
412 
413 static inline void darray_swap(const size_t element_size,
414  struct darray *dst, const size_t a, const size_t b)
415 {
416  void *temp, *a_ptr, *b_ptr;
417 
418  assert(a < dst->num);
419  assert(b < dst->num);
420 
421  if (a == b)
422  return;
423 
424  temp = malloc(element_size);
425  a_ptr = darray_item(element_size, dst, a);
426  b_ptr = darray_item(element_size, dst, b);
427 
428  memcpy(temp, a_ptr, element_size);
429  memcpy(a_ptr, b_ptr, element_size);
430  memcpy(b_ptr, temp, element_size);
431 
432  free(temp);
433 }
434 
435 /*
436  * Defines to make dynamic arrays more type-safe.
437  * Note: Still not 100% type-safe but much better than using darray directly
438  * Makes it a little easier to use as well.
439  *
440  * I did -not- want to use a gigantic macro to generate a crapload of
441  * typesafe inline functions per type. It just feels like a mess to me.
442  */
443 
444 #define DARRAY(type) \
445  union { \
446  struct darray da; \
447  struct { \
448  type *array; \
449  size_t num; \
450  size_t capacity; \
451  }; \
452  }
453 
454 #define da_init(v) darray_init(&v.da)
455 
456 #define da_free(v) darray_free(&v.da)
457 
458 #define da_alloc_size(v) (sizeof(*v.array)*v.num)
459 
460 #define da_end(v) darray_end(sizeof(*v.array), &v.da)
461 
462 #define da_reserve(v, capacity) \
463  darray_reserve(sizeof(*v.array), &v.da, capacity)
464 
465 #define da_resize(v, size) darray_resize(sizeof(*v.array), &v.da, size)
466 
467 #define da_copy(dst, src) \
468  darray_copy(sizeof(*dst.array), &dst.da, &src.da)
469 
470 #define da_copy_array(dst, src_array, n) \
471  darray_copy_array(sizeof(*dst.array), &dst.da, src_array, n)
472 
473 #define da_move(dst, src) darray_move(&dst.da, &src.da)
474 
475 #define da_find(v, item, idx) \
476  darray_find(sizeof(*v.array), &v.da, item, idx)
477 
478 #define da_push_back(v, item) darray_push_back(sizeof(*v.array), &v.da, item)
479 
480 #define da_push_back_new(v) darray_push_back_new(sizeof(*v.array), &v.da)
481 
482 #define da_push_back_array(dst, src_array, n) \
483  darray_push_back_array(sizeof(*dst.array), &dst.da, src_array, n)
484 
485 #define da_push_back_da(dst, src) \
486  darray_push_back_darray(sizeof(*dst.array), &dst.da, &src.da)
487 
488 #define da_insert(v, idx, item) \
489  darray_insert(sizeof(*v.array), &v.da, idx, item)
490 
491 #define da_insert_new(v, idx) \
492  darray_insert_new(sizeof(*v.array), &v.da, idx)
493 
494 #define da_insert_array(dst, idx, src_array, n) \
495  darray_insert_array(sizeof(*dst.array), &dst.da, idx, \
496  src_array, n)
497 
498 #define da_insert_da(dst, idx, src) \
499  darray_insert_darray(sizeof(*dst.array), &dst.da, idx, \
500  &src.da)
501 
502 #define da_erase(dst, idx) \
503  darray_erase(sizeof(*dst.array), &dst.da, idx)
504 
505 #define da_erase_item(dst, item) \
506  darray_erase_item(sizeof(*dst.array), &dst.da, item)
507 
508 #define da_erase_range(dst, from, to) \
509  darray_erase_range(sizeof(*dst.array), &dst.da, from, to)
510 
511 #define da_pop_back(dst) \
512  darray_pop_back(sizeof(*dst.array), &dst.da);
513 
514 #define da_join(dst, src) \
515  darray_join(sizeof(*dst.array), &dst.da, &src.da)
516 
517 #define da_split(dst1, dst2, src, idx) \
518  darray_split(sizeof(*src.array), &dst1.da, &dst2.da, \
519  &src.da, idx)
520 
521 #define da_move_item(v, from, to) \
522  darray_move_item(sizeof(*v.array), &v.da, from, to)
523 
524 #define da_swap(v, idx1, idx2) \
525  darray_swap(sizeof(*v.array), &v.da, idx1, idx2)
526 
527 #ifdef __cplusplus
528 }
529 #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)