src/dynarray.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4
   5 #include "system/stacktrace.h"
   6 #include "system/lt.h"
   7 #include "system/nth_alloc.h"
   8 #include "dynarray.h"
   9
  10 #define DYNARRAY_INIT_CAPACITY 8
  11
  12 void *dynarray_pointer_at(const Dynarray *dynarray, size_t index)
  13 {
  14     trace_assert(index < dynarray->count);
  15     return (uint8_t *)dynarray->data + index * dynarray->element_size;
  16 }
  17
  18 void dynarray_clear(Dynarray *dynarray)
  19 {
  20     trace_assert(dynarray);
  21     dynarray->count = 0;
  22 }
  23
  24 static
  25 int dynarray_grow(Dynarray *dynarray)
  26 {
  27     if (dynarray->count < dynarray->capacity) {
  28         return 0;
  29     }
  30
  31     if (dynarray->capacity == 0) {
  32         dynarray->capacity = DYNARRAY_INIT_CAPACITY;
  33     } else {
  34         dynarray->capacity *= 2;
  35     }
  36
  37     dynarray->data = nth_realloc(
  38         dynarray->data,
  39         dynarray->capacity * dynarray->element_size * 2);
  40
  41     return 0;
  42 }
  43
  44 int dynarray_push(Dynarray *dynarray, const void *element)
  45 {
  46     trace_assert(dynarray);
  47     trace_assert(element);
  48
  49     if (dynarray_grow(dynarray) < 0) {
  50         return -1;
  51     }
  52
  53     memcpy(
  54         (char*) dynarray->data + dynarray->count * dynarray->element_size,
  55         element,
  56         dynarray->element_size);
  57
  58     dynarray->count++;
  59
  60     return 0;
  61 }
  62
  63 bool dynarray_contains(const Dynarray *dynarray,
  64                        const void *element)
  65 {
  66     trace_assert(dynarray);
  67     trace_assert(element);
  68
  69     for (size_t i = 0; i < dynarray->count; ++i) {
  70         if (memcmp((const char*)dynarray->data + i * dynarray->element_size,
  71                    (const char*)element,
  72                    dynarray->element_size) == 0) {
  73             return true;
  74         }
  75     }
  76
  77     return false;
  78 }
  79
  80 void dynarray_delete_at(Dynarray *dynarray, size_t index)
  81 {
  82     trace_assert(dynarray);
  83     trace_assert(index < dynarray->count);
  84     memmove(
  85         (uint8_t *) dynarray->data + index * dynarray->element_size,
  86         (uint8_t *) dynarray->data + (index + 1) * dynarray->element_size,
  87         dynarray->element_size * (dynarray->count - index - 1));
  88     dynarray->count--;
  89 }
  90
  91 void dynarray_insert_before(Dynarray *dynarray, size_t index, void *element)
  92 {
  93     trace_assert(dynarray);
  94     trace_assert(element);
  95     trace_assert(index <= dynarray->count);
  96
  97     dynarray_grow(dynarray);
  98
  99     memmove(
 100         (uint8_t*) dynarray->data + (index + 1) * dynarray->element_size,
 101         (uint8_t*) dynarray->data + index * dynarray->element_size,
 102         dynarray->element_size * (dynarray->count - index));
 103
 104     memcpy(
 105         (uint8_t*) dynarray->data + index * dynarray->element_size,
 106         element,
 107         dynarray->element_size);
 108
 109     dynarray->count++;
 110 }
 111
 112 int dynarray_push_empty(Dynarray *dynarray)
 113 {
 114     trace_assert(dynarray);
 115
 116     if (dynarray_grow(dynarray) < 0) {
 117         return -1;
 118     }
 119
 120     memset(
 121         (char*) dynarray->data + dynarray->count * dynarray->element_size,
 122         0,
 123         dynarray->element_size);
 124
 125     dynarray->count++;
 126
 127     return 0;
 128 }
 129
 130 // TODO(#980): dynarray_push and dynarray_push_empty have duplicate codez
 131
 132 void dynarray_pop(Dynarray *dynarray, void *element)
 133 {
 134     trace_assert(dynarray);
 135     trace_assert(dynarray->count > 0);
 136
 137     dynarray->count--;
 138
 139     if (element) {
 140         memcpy(
 141             element,
 142             (uint8_t*) dynarray->data + dynarray->count * dynarray->element_size,
 143             dynarray->element_size);
 144     }
 145 }
 146
 147 void dynarray_replace_at(Dynarray *dynarray, size_t index, void *element)
 148 {
 149     trace_assert(dynarray);
 150     trace_assert(element);
 151     trace_assert(index < dynarray->count);
 152
 153     memcpy(
 154         (uint8_t*) dynarray->data + index * dynarray->element_size,
 155         element,
 156         dynarray->element_size);
 157 }
 158
 159 void dynarray_copy_to(Dynarray *dynarray, void *dest, size_t index)
 160 {
 161     trace_assert(dynarray);
 162     trace_assert(dest);
 163     trace_assert(index < dynarray->count);
 164
 165     memcpy(dest, (uint8_t*) dynarray->data + index * dynarray->element_size, dynarray->element_size);
 166 }
 167
 168 void dynarray_swap(Dynarray *dynarray, size_t i, size_t j)
 169 {
 170     trace_assert(dynarray);
 171     trace_assert(i < dynarray->count);
 172     trace_assert(j < dynarray->count);
 173
 174     if (i == j) return;
 175
 176     char *a = dynarray_pointer_at(dynarray, i);
 177     char *b = dynarray_pointer_at(dynarray, j);
 178
 179     for (size_t k = 0; k < dynarray->element_size; ++k) {
 180         char t = a[k];
 181         a[k] = b[k];
 182         b[k] = t;
 183     }
 184 }