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

   1 #include "vector.h"
   2
   3 #include <assert.h>
   4 #include <stdint.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7
   8 #define INITIAL_CAPACITY 64
   9
  10 #ifdef NDEBUG
  11         #define CHECK(x) (void)(x)
  12 #else
  13         #define CHECK(x) _check(x)
  14 #endif
  15
  16 struct vector
  17 {
  18         size_t length;
  19         size_t capacity;
  20         void **elts;
  21         void (*elt_dtor)(void *);
  22 };
  23
  24 static void
  25 _check(const vector *v)
  26 {
  27         assert(v);
  28         assert(v->capacity > 0);
  29         /* test that capacity is a power of two if not maxed out
  30          * https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2
  31          */
  32         if (v->capacity < SIZE_MAX)
  33                 assert((v->capacity & (v->capacity - 1)) == 0);
  34         assert(v->length <= v->capacity);
  35 }
  36
  37 vector *
  38 v_new(void (*elt_dtor)(void *))
  39 {
  40         vector *v   = malloc(sizeof *v);
  41         void **elts = malloc(INITIAL_CAPACITY * sizeof *elts);
  42         if (!v || !elts)
  43         {
  44                 free(v);
  45                 free(elts);
  46                 return NULL;
  47         }
  48         *v = (vector){
  49                 .capacity = INITIAL_CAPACITY,
  50                 .elts = elts,
  51                 .elt_dtor = elt_dtor
  52         };
  53         CHECK(v);
  54         return v;
  55 }
  56
  57 void
  58 v_free(vector *v)
  59 {
  60         if (!v)
  61                 return;
  62         v_clear(v);
  63         free(v->elts);
  64         free(v);
  65 }
  66
  67 size_t
  68 v_length(const vector *v)
  69 {
  70         return v ? v->length : 0;
  71 }
  72
  73 bool
  74 v_set_length(vector *v, size_t desired)
  75 {
  76         if (!v)
  77                 return false;
  78         if (v->elt_dtor) /* free any, if necessary */
  79                 for (size_t i = desired; i < v->length; i++)
  80                         v->elt_dtor(v->elts[i]);
  81         if (v_reserve_capacity(v, desired) < desired)
  82                 return false;
  83         for (size_t i = v->length; i < desired; i++)
  84                 v->elts[i] = NULL;
  85         v->length = desired;
  86
  87         CHECK(v);
  88         return true;
  89 }
  90
  91 size_t
  92 v_capacity(const vector *v)
  93 {
  94         return v ? v->capacity : 0;
  95 }
  96
  97 size_t
  98 v_reserve_capacity(vector *v, size_t desired)
  99 {
 100         if (!v)
 101                 return 0;
 102         if (desired <= v->capacity)
 103                 return v->capacity;
 104         size_t n = v->capacity;
 105         /* SIZE_MAX is one less than a power of two, so if
 106          * we keep looping too long we'll hit zero */
 107         while (0 < n && n < desired)
 108                 n *= 2;
 109         if (n == 0)
 110                 n = SIZE_MAX;
 111         void **enlarged = realloc(v->elts, n);
 112         if (!enlarged)
 113                 return v->capacity;
 114         v->elts = enlarged;
 115         v->capacity = n;
 116
 117         CHECK(v);
 118         return n;
 119 }
 120
 121 bool
 122 v_is_empty(const vector *v)
 123 {
 124         return v_length(v) == 0;
 125 }
 126
 127 void *
 128 v_at(const vector *v, size_t i)
 129 {
 130         if (!v || i >= v->length)
 131                 return NULL;
 132         return v->elts[i];
 133 }
 134
 135 void *
 136 v_first(const vector *v)
 137 {
 138         return v_at(v, 0);
 139 }
 140
 141 void *
 142 v_last(const vector *v)
 143 {
 144         /* successfully fails when length is 0 */
 145         return v_at(v, v_length(v)-1);
 146 }
 147
 148 bool
 149 v_append(vector *v, void *e)
 150 {
 151         return v_insert(v, v_length(v), e);
 152 }
 153
 154 bool
 155 v_prepend(vector *v, void *e)
 156 {
 157         return v_insert(v, 0, e);
 158 }
 159
 160 void *
 161 v_remove_first(vector *v)
 162 {
 163         return v_remove(v, 0);
 164 }
 165
 166 void *
 167 v_remove_last(vector *v)
 168 {
 169         return v_remove(v, v_length(v)-1);
 170 }
 171
 172 void *
 173 v_remove(vector *v, size_t i)
 174 {
 175         if (!v || i >= v->length)
 176                 return NULL;
 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) < 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 #define SWAP(x, y) do { void *swaptmp = (x); (x) = (y); (y) = swaptmp; } while (0)
 199
 200 bool
 201 v_swap(vector *v, size_t i, size_t j)
 202 {
 203         if (!v || i >= v->length || j >= v->length)
 204                 return false;
 205         SWAP(v->elts[i], v->elts[j]);
 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              comparator *cmp, void *aux)
 220 {
 221         if (!v || !cmp)
 222                 return SIZE_MAX;
 223         for (size_t i = 0; i < v->length; i++)
 224                 if (cmp(v->elts[i], needle, aux) == 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                   comparator *cmp, void *aux)
 232 {
 233         if (!v || !cmp)
 234                 return SIZE_MAX;
 235         for (size_t i = v->length-1; i < SIZE_MAX; i--)
 236                 if (cmp(v->elts[i], needle, aux) == 0)
 237                         return i;
 238         return SIZE_MAX;
 239 }
 240
 241 /* from Bentley, https://www.youtube.com/watch?v=QvgYAQzg1z8 */
 242 static void
 243 _quicksort(vector *v, size_t lo, size_t hi,
 244            comparator *cmp, void *aux)
 245 {
 246         size_t i, m = lo;
 247         if (lo >= hi)
 248                 return;
 249         for (i = lo+1; i <= hi; i++)
 250                 if (cmp(v->elts[i], v->elts[lo], aux) < 0)
 251                 {
 252                         m++;
 253                         SWAP(v->elts[i], v->elts[m]);
 254                 }
 255         SWAP(v->elts[lo], v->elts[m]);
 256
 257         if (m > 0) /* avoid wrapping size_t */
 258                 _quicksort(v, lo, m-1, cmp, aux);
 259         _quicksort(v, m+1, hi, cmp, aux);
 260 }
 261
 262 bool
 263 v_sort(vector *v, comparator *cmp, void *aux)
 264 {
 265         if (!v || !cmp)
 266                 return false;
 267         _quicksort(v, 0, v->length-1, cmp, aux);
 268
 269         CHECK(v);
 270         return true;
 271 }
 272
 273 bool
 274 v_reverse(vector *v)
 275 {
 276         size_t n = v_length(v);
 277         if (n < 2)
 278                 return true;
 279         for (size_t i = n-1; i >= n/2; i--)
 280         {
 281                 void *t = v->elts[i];
 282                 v->elts[i] = v->elts[n-i-1];
 283                 v->elts[n-i-1] = t;
 284         }
 285         CHECK(v);
 286         return true;
 287 }