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);
 161 }
 162
 163 void *
 164 v_remove_last(vector *v)
 165 {
 166         return v_remove(v, v_length(v)-1);
 167 }
 168
 169 void *
 170 v_remove(vector *v, size_t i)
 171 {
 172         if (!v || i >= v->length)
 173         {
 174                 errno = EDOM;
 175                 return NULL;
 176         }
 177         void *elt = v->elts[i];
 178         memmove(v->elts+i, v->elts+i+1, (v->length - (i+1)) * sizeof *v->elts);
 179         v->length--;
 180
 181         CHECK(v);
 182         return elt;
 183 }
 184
 185 bool
 186 v_insert(vector *v, size_t i, void *elt)
 187 {
 188         if (!v || !v_reserve_capacity(v, v->length+1))
 189                 return false;
 190         memmove(v->elts+i+1, v->elts+i, (v->length - i) * sizeof *v->elts);
 191         v->elts[i] = elt;
 192         v->length++;
 193
 194         CHECK(v);
 195         return true;
 196 }
 197
 198 bool
 199 v_swap(vector *v, size_t i, size_t j)
 200 {
 201         if (!v || i >= v->length || j >= v->length)
 202                 return false;
 203         void *t = v->elts[i];
 204         v->elts[i] = v->elts[j];
 205         v->elts[j] = t;
 206
 207         CHECK(v);
 208         return true;
 209 }
 210
 211 void
 212 v_clear(vector *v)
 213 {
 214         v_set_length(v, 0);
 215 }
 216
 217 size_t
 218 v_find_index(const vector *v, const void *needle,
 219              int (*cmp)(const void *, const void *))
 220 {
 221         if (!v)
 222                 return SIZE_MAX;
 223         for (size_t i = 0; i < v->length; i++)
 224                 if (cmp(v->elts[i], needle) == 0)
 225                         return i;
 226         return SIZE_MAX;
 227 }
 228
 229 size_t
 230 v_find_last_index(const vector *v, const void *needle,
 231                   int (*cmp)(const void *, const void *))
 232 {
 233         if (!v)
 234                 return SIZE_MAX;
 235         for (size_t i = v->length-1; i < SIZE_MAX; i--)
 236                 if (cmp(v->elts[i], needle) == 0)
 237                         return i;
 238         return SIZE_MAX;
 239 }
 240
 241 bool
 242 v_sort(vector *v, int (*cmp)(const void *, const void *))
 243 {
 244         if (!v)
 245                 return false;
 246         qsort(v->elts, v->length, sizeof v->elts[0], cmp);
 247
 248         CHECK(v);
 249         return true;
 250 }