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