begriffs open source - libderp/blob - src/vector.c

   1 #include "vector.h"
   2
   3 #include <assert.h>
   4 #include <errno.h>
   5 #include <stdint.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8
   9 #define INITIAL_CAPACITY 64
  10
  11 #ifdef NDEBUG
  12         #define CHECK(x) (void)(x)
  13 #else
  14         #define CHECK(x) _check(x)
  15 #endif
  16
  17 static void
  18 _check(const vector *v)
  19 {
  20         assert(v);
  21         assert(v->capacity > 0);
  22         /* test that capacity is a power of two if not maxed out
  23          * https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2
  24          */
  25         if (v->capacity < SIZE_MAX)
  26                 assert((v->capacity & (v->capacity - 1)) == 0);
  27         assert(v->length <= v->capacity);
  28         assert(v->length < SIZE_MAX);
  29 }
  30
  31 vector *
  32 v_new(void (*elt_dtor)(void *))
  33 {
  34         vector *v   = malloc(sizeof *v);
  35         void **elts = malloc(INITIAL_CAPACITY * sizeof *elts);
  36         if (!v || !elts)
  37         {
  38                 free(v);
  39                 free(elts);
  40                 return NULL;
  41         }
  42         *v = (vector){
  43                 .capacity = INITIAL_CAPACITY,
  44                 .elts = elts,
  45                 .elt_dtor = elt_dtor
  46         };
  47         CHECK(v);
  48         return v;
  49 }
  50
  51 void
  52 v_free(vector *v)
  53 {
  54         if (!v)
  55                 return;
  56         v_clear(v);
  57         free(v->elts);
  58         free(v);
  59 }
  60
  61 size_t
  62 v_length(const vector *v)
  63 {
  64         return v ? v->length : SIZE_MAX;
  65 }
  66
  67 bool
  68 v_set_length(vector *v, size_t len)
  69 {
  70         if (!v || len == SIZE_MAX)
  71                 return false;
  72         if (v->elt_dtor) /* free any, if necessary */
  73                 for (size_t i = len; i < v->length; i++)
  74                         v->elt_dtor(v->elts[i]);
  75         if (!v_reserve_capacity(v, len))
  76                 return false;
  77         for (size_t i = v->length; i < len; i++)
  78                 v->elts[i] = NULL;
  79         v->length = len;
  80
  81         CHECK(v);
  82         return true;
  83 }
  84
  85 size_t
  86 v_capacity(const vector *v)
  87 {
  88         return v ? v->capacity : 0;
  89 }
  90
  91 size_t
  92 v_reserve_capacity(vector *v, size_t desired)
  93 {
  94         if (!v)
  95                 return 0;
  96         if (desired <= v->capacity)
  97                 return v->capacity;
  98         size_t n = v->capacity;
  99         /* SIZE_MAX is one less than a power of two, so if
 100          * we keep looping too long we'll hit zero */
 101         while (0 < n && n < desired)
 102                 n *= 2;
 103         if (n == 0)
 104                 n = SIZE_MAX;
 105         void **enlarged = realloc(v->elts, n);
 106         if (!enlarged)
 107                 return v->capacity;
 108         v->elts = enlarged;
 109         v->capacity = n;
 110
 111         CHECK(v);
 112         return n;
 113 }
 114
 115 bool
 116 v_is_empty(const vector *v)
 117 {
 118         return v_length(v) == 0;
 119 }
 120
 121 void *
 122 v_at(const vector *v, size_t i)
 123 {
 124         if (!v || i >= v->length)
 125         {
 126                 errno = EDOM;
 127                 return NULL;
 128         }
 129         return v->elts[i];
 130 }
 131
 132 void *
 133 v_first(const vector *v)
 134 {
 135         return v_at(v, 0);
 136 }
 137
 138 void *
 139 v_last(const vector *v)
 140 {
 141         /* when length is 0, length-1 is SIZE_MAX */
 142         return v_at(v, v_length(v)-1);
 143 }
 144
 145 bool
 146 v_append(vector *v, void *e)
 147 {
 148         return v_insert(v, v_length(v), e);
 149 }
 150
 151 bool
 152 v_prepend(vector *v, void *e)
 153 {
 154         return v_insert(v, 0, e);
 155 }
 156
 157 void *
 158 v_remove_first(vector *v)
 159 {
 160         return v_remove(v, 0, 1);
 161 }
 162
 163 void *
 164 v_remove_last(vector *v)
 165 {
 166         return v_remove(v, v_length(v)-1, 1);
 167 }
 168
 169 bool
 170 v_insert(vector *v, size_t i, void *elt)
 171 {
 172         if (!v || !v_reserve_capacity(v, v->length+1))
 173                 return false;
 174         memmove(v->elts+i+1, v->elts+i, (v->length - i) * sizeof *v->elts);
 175         v->elts[i] = elt;
 176         v->length++;
 177
 178         CHECK(v);
 179         return true;
 180 }
 181
 182 bool
 183 v_swap(vector *v, size_t i, size_t j)
 184 {
 185         if (!v || i >= v->length || j >= v->length)
 186                 return false;
 187         void *t = v->elts[i];
 188         v->elts[i] = v->elts[j];
 189         v->elts[j] = t;
 190
 191         CHECK(v);
 192         return true;
 193 }
 194
 195 void
 196 v_clear(vector *v)
 197 {
 198         v_set_length(v, 0);
 199 }
 200
 201 size_t
 202 v_find_index(const vector *v, const void *needle,
 203              int (*cmp)(const void *, const void *))
 204 {
 205         if (!v)
 206                 return SIZE_MAX;
 207         for (size_t i = 0; i < v->length; i++)
 208                 if (cmp(v->elts[i], needle) == 0)
 209                         return i;
 210         return SIZE_MAX;
 211 }
 212
 213 size_t
 214 v_find_last_index(const vector *v, const void *needle,
 215                   int (*cmp)(const void *, const void *))
 216 {
 217         if (!v)
 218                 return SIZE_MAX;
 219         for (size_t i = v->length-1; i < SIZE_MAX; i--)
 220                 if (cmp(v->elts[i], needle) == 0)
 221                         return i;
 222         return SIZE_MAX;
 223 }
 224
 225 bool
 226 v_sort(vector *v, int (*cmp)(const void *, const void *))
 227 {
 228         if (!v)
 229                 return false;
 230         qsort(v->elts, v->length, sizeof v->elts[0], cmp);
 231
 232         CHECK(v);
 233         return true;
 234 }