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 thhe 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  * typsafe 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)