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         {
  56                 errno = EDOM;
  57                 return;
  58         }
  59         v_clear(v);
  60         free(v->elts);
  61         free(v);
  62 }
  63
  64 size_t
  65 v_length(const vector *v)
  66 {
  67         if (!v)
  68         {
  69                 errno = EDOM;
  70                 return SIZE_MAX;
  71         }
  72         return v->length;
  73 }
  74
  75 bool
  76 v_set_length(vector *v, size_t desired)
  77 {
  78         if (!v || desired == SIZE_MAX)
  79         {
  80                 errno = EDOM;
  81                 return false;
  82         }
  83         if (v->elt_dtor) /* free any, if necessary */
  84                 for (size_t i = desired; i < v->length; i++)
  85                         v->elt_dtor(v->elts[i]);
  86         if (!v_reserve_capacity(v, desired))
  87                 return false;
  88         for (size_t i = v->length; i < desired; i++)
  89                 v->elts[i] = NULL;
  90         v->length = desired;
  91
  92         CHECK(v);
  93         return true;
  94 }
  95
  96 size_t
  97 v_capacity(const vector *v)
  98 {
  99         if (!v)
 100         {
 101                 errno = EDOM;
 102                 return 0;
 103         }
 104         return v->capacity;
 105 }
 106
 107 size_t
 108 v_reserve_capacity(vector *v, size_t desired)
 109 {
 110         if (!v)
 111         {
 112                 errno = EDOM;
 113                 return 0;
 114         }
 115         if (desired <= v->capacity)
 116                 return v->capacity;
 117         size_t n = v->capacity;
 118         /* SIZE_MAX is one less than a power of two, so if
 119          * we keep looping too long we'll hit zero */
 120         while (0 < n && n < desired)
 121                 n *= 2;
 122         if (n == 0)
 123                 n = SIZE_MAX;
 124         void **enlarged = realloc(v->elts, n);
 125         if (!enlarged)
 126                 return v->capacity;
 127         v->elts = enlarged;
 128         v->capacity = n;
 129
 130         CHECK(v);
 131         return n;
 132 }
 133
 134 bool
 135 v_is_empty(const vector *v)
 136 {
 137         if (!v)
 138         {
 139                 errno = EDOM;
 140                 return true;
 141         }
 142         return v_length(v) == 0;
 143 }
 144
 145 void *
 146 v_at(const vector *v, size_t i)
 147 {
 148         if (!v || i >= v->length)
 149         {
 150                 errno = EDOM;
 151                 return NULL;
 152         }
 153         return v->elts[i];
 154 }
 155
 156 void *
 157 v_first(const vector *v)
 158 {
 159         return v_at(v, 0);
 160 }
 161
 162 void *
 163 v_last(const vector *v)
 164 {
 165         /* when length is 0, length-1 is SIZE_MAX */
 166         return v_at(v, v_length(v)-1);
 167 }
 168
 169 bool
 170 v_append(vector *v, void *e)
 171 {
 172         return v_insert(v, v_length(v), e);
 173 }
 174
 175 bool
 176 v_prepend(vector *v, void *e)
 177 {
 178         return v_insert(v, 0, e);
 179 }
 180
 181 void *
 182 v_remove_first(vector *v)
 183 {
 184         return v_remove(v, 0);
 185 }
 186
 187 void *
 188 v_remove_last(vector *v)
 189 {
 190         return v_remove(v, v_length(v)-1);
 191 }
 192
 193 void *
 194 v_remove(vector *v, size_t i)
 195 {
 196         if (!v || i >= v->length)
 197         {
 198                 errno = EDOM;
 199                 return NULL;
 200         }
 201         void *elt = v->elts[i];
 202         memmove(v->elts+i, v->elts+i+1, (v->length - (i+1)) * sizeof *v->elts);
 203         v->length--;
 204
 205         CHECK(v);
 206         return elt;
 207 }
 208
 209 bool
 210 v_insert(vector *v, size_t i, void *elt)
 211 {
 212         if (!v || i == SIZE_MAX)
 213         {
 214                 errno = EDOM;
 215                 return false;
 216         }
 217         if (!v_reserve_capacity(v, v->length+1))
 218                 return false;
 219         memmove(v->elts+i+1, v->elts+i, (v->length - i) * sizeof *v->elts);
 220         v->elts[i] = elt;
 221         v->length++;
 222
 223         CHECK(v);
 224         return true;
 225 }
 226
 227 bool
 228 v_swap(vector *v, size_t i, size_t j)
 229 {
 230         if (!v || i >= v->length || j >= v->length)
 231         {
 232                 errno = EDOM;
 233                 return false;
 234         }
 235         void *t = v->elts[i];
 236         v->elts[i] = v->elts[j];
 237         v->elts[j] = t;
 238
 239         CHECK(v);
 240         return true;
 241 }
 242
 243 void
 244 v_clear(vector *v)
 245 {
 246         v_set_length(v, 0);
 247 }
 248
 249 size_t
 250 v_find_index(const vector *v, const void *needle,
 251              int (*cmp)(const void *, const void *))
 252 {
 253         if (!v || !cmp)
 254         {
 255                 errno = EDOM;
 256                 return SIZE_MAX;
 257         }
 258         for (size_t i = 0; i < v->length; i++)
 259                 if (cmp(v->elts[i], needle) == 0)
 260                         return i;
 261         return SIZE_MAX;
 262 }
 263
 264 size_t
 265 v_find_last_index(const vector *v, const void *needle,
 266                   int (*cmp)(const void *, const void *))
 267 {
 268         if (!v || !cmp)
 269         {
 270                 errno = EDOM;
 271                 return SIZE_MAX;
 272         }
 273         for (size_t i = v->length-1; i < SIZE_MAX; i--)
 274                 if (cmp(v->elts[i], needle) == 0)
 275                         return i;
 276         return SIZE_MAX;
 277 }
 278
 279 bool
 280 v_sort(vector *v, int (*cmp)(const void *, const void *))
 281 {
 282         if (!v || !cmp)
 283         {
 284                 errno = EDOM;
 285                 return false;
 286         }
 287         qsort(v->elts, v->length, sizeof v->elts[0], cmp);
 288
 289         CHECK(v);
 290         return true;
 291 }
 292
 293 bool
 294 v_reverse(vector *v)
 295 {
 296         size_t n = v_length(v);
 297         if (n == SIZE_MAX)
 298                 return false;
 299         if (n < 2)
 300                 return true;
 301         for (size_t i = n-1; i >= n/2; i--)
 302         {
 303                 void *t = v->elts[i];
 304                 v->elts[i] = v->elts[n-i-1];
 305                 v->elts[n-i-1] = t;
 306         }
 307         CHECK(v);
 308         return true;
 309 }