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 struct Dynarray
  13 {
  14     Lt *lt;
  15     size_t element_size;
  16     size_t capacity;
  17     size_t count;
  18     char *data;
  19 };
  20
  21 Dynarray *create_dynarray(size_t element_size)
  22 {
  23     Lt *lt = create_lt();
  24
  25     Dynarray *dynarray = PUSH_LT(lt, nth_calloc(1, sizeof(Dynarray)), free);
  26     if (dynarray == NULL) {
  27         RETURN_LT(lt, NULL);
  28     }
  29     dynarray->lt = lt;
  30
  31     dynarray->element_size = element_size;
  32     dynarray->capacity = DYNARRAY_INIT_CAPACITY;
  33     dynarray->count = 0;
  34
  35     dynarray->data = PUSH_LT(lt, nth_calloc(DYNARRAY_INIT_CAPACITY, element_size), free);
  36     if (dynarray->data == NULL) {
  37         RETURN_LT(lt, NULL);
  38     }
  39
  40     return dynarray;
  41 }
  42
  43 void destroy_dynarray(Dynarray *dynarray)
  44 {
  45     trace_assert(dynarray);
  46     RETURN_LT0(dynarray->lt);
  47 }
  48
  49 void *dynarray_pointer_at(Dynarray *dynarray, size_t index) {
  50     trace_assert(index < dynarray->count);
  51     return dynarray->data + index * dynarray->element_size;
  52 }
  53
  54 size_t dynarray_count(const Dynarray *dynarray)
  55 {
  56     trace_assert(dynarray);
  57     return dynarray->count;
  58 }
  59
  60 void *dynarray_data(Dynarray *dynarray)
  61 {
  62     trace_assert(dynarray);
  63     return dynarray->data;
  64 }
  65
  66 void dynarray_clear(Dynarray *dynarray)
  67 {
  68     trace_assert(dynarray);
  69     dynarray->count = 0;
  70 }
  71
  72 static
  73 int dynarray_grow(Dynarray *dynarray)
  74 {
  75     if (dynarray->count < dynarray->capacity) {
  76         return 0;
  77     }
  78
  79     void *new_data = nth_realloc(
  80         dynarray->data,
  81         dynarray->capacity * dynarray->element_size * 2);
  82     if (new_data == NULL) {
  83         return -1;
  84     }
  85
  86     dynarray->data = REPLACE_LT(dynarray->lt, dynarray->data, new_data);
  87     if (dynarray->data == NULL) {
  88         return -1;
  89     }
  90
  91     dynarray->capacity *= 2;
  92
  93     return 0;
  94 }
  95
  96 int dynarray_push(Dynarray *dynarray, const void *element)
  97 {
  98     trace_assert(dynarray);
  99     trace_assert(element);
 100
 101     if (dynarray_grow(dynarray) < 0) {
 102         return -1;
 103     }
 104
 105     memcpy(
 106         (char*) dynarray->data + dynarray->count * dynarray->element_size,
 107         element,
 108         dynarray->element_size);
 109
 110     dynarray->count++;
 111
 112     return 0;
 113 }
 114
 115 bool dynarray_contains(const Dynarray *dynarray,
 116                        const void *element)
 117 {
 118     trace_assert(dynarray);
 119     trace_assert(element);
 120
 121     for (size_t i = 0; i < dynarray->count; ++i) {
 122         if (memcmp((const char*)dynarray->data + i * dynarray->element_size,
 123                    (const char*)element,
 124                    dynarray->element_size) == 0) {
 125             return true;
 126         }
 127     }
 128
 129     return false;
 130 }
 131
 132 void dynarray_delete_at(Dynarray *dynarray, size_t index)
 133 {
 134     trace_assert(dynarray);
 135     trace_assert(index < dynarray->count);
 136     memmove(
 137         dynarray->data + index * dynarray->element_size,
 138         dynarray->data + (index + 1) * dynarray->element_size,
 139         dynarray->element_size * (dynarray->count - index - 1));
 140     dynarray->count--;
 141 }
 142
 143 void dynarray_insert_before(Dynarray *dynarray, size_t index, void *element)
 144 {
 145     trace_assert(dynarray);
 146     trace_assert(element);
 147     trace_assert(index <= dynarray->count);
 148
 149     dynarray_grow(dynarray);
 150
 151     memmove(
 152         dynarray->data + (index + 1) * dynarray->element_size,
 153         dynarray->data + index * dynarray->element_size,
 154         dynarray->element_size * (dynarray->count - index));
 155
 156     memcpy(
 157         dynarray->data + index * dynarray->element_size,
 158         element,
 159         dynarray->element_size);
 160
 161     dynarray->count++;
 162 }
 163
 164 int dynarray_push_empty(Dynarray *dynarray)
 165 {
 166     trace_assert(dynarray);
 167
 168     if (dynarray_grow(dynarray) < 0) {
 169         return -1;
 170     }
 171
 172     memset(
 173         (char*) dynarray->data + dynarray->count * dynarray->element_size,
 174         0,
 175         dynarray->element_size);
 176
 177     dynarray->count++;
 178
 179     return 0;
 180 }
 181
 182 // TODO(#980): dynarray_push and dynarray_push_empty have duplicate codez
 183
 184 void dynarray_pop(Dynarray *dynarray, void *element)
 185 {
 186     trace_assert(dynarray);
 187     trace_assert(dynarray->count > 0);
 188
 189     dynarray->count--;
 190
 191     if (element) {
 192         memcpy(
 193             element,
 194             dynarray->data + dynarray->count * dynarray->element_size,
 195             dynarray->element_size);
 196     }
 197 }
 198
 199 void dynarray_replace_at(Dynarray *dynarray, size_t index, void *element)
 200 {
 201     trace_assert(dynarray);
 202     trace_assert(element);
 203     trace_assert(index < dynarray->count);
 204
 205     memcpy(
 206         dynarray->data + index * dynarray->element_size,
 207         element,
 208         dynarray->element_size);
 209 }
 210
 211 void dynarray_copy_to(Dynarray *dynarray, void *dest, size_t index)
 212 {
 213     trace_assert(dynarray);
 214     trace_assert(dest);
 215     trace_assert(index < dynarray->count);
 216
 217     memcpy(dest, dynarray->data + index * dynarray->element_size, dynarray->element_size);
 218 }
 219
 220 void dynarray_swap(Dynarray *dynarray, size_t i, size_t j)
 221 {
 222     trace_assert(dynarray);
 223     trace_assert(i < dynarray->count);
 224     trace_assert(j < dynarray->count);
 225
 226     if (i == j) return;
 227
 228     char *a = dynarray_pointer_at(dynarray, i);
 229     char *b = dynarray_pointer_at(dynarray, j);
 230
 231     for (size_t k = 0; k < dynarray->element_size; ++k) {
 232         char t = a[k];
 233         a[k] = b[k];
 234         b[k] = t;
 235     }
 236 }