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         if (n > SIZE_MAX / (sizeof *v->elts))
 123                 return v->capacity; /* realloc multiplication would overflow */
 124         void **enlarged = realloc(v->elts, n * sizeof *v->elts);
 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         return v_length(v) == 0;
 138 }
 139
 140 void *
 141 v_at(const vector *v, size_t i)
 142 {
 143         if (!v || i >= v->length)
 144                 return NULL;
 145         return v->elts[i];
 146 }
 147
 148 void *
 149 v_first(const vector *v)
 150 {
 151         return v_at(v, 0);
 152 }
 153
 154 void *
 155 v_last(const vector *v)
 156 {
 157         /* successfully fails when length is 0 */
 158         return v_at(v, v_length(v)-1);
 159 }
 160
 161 bool
 162 v_append(vector *v, void *e)
 163 {
 164         return v_insert(v, v_length(v), e);
 165 }
 166
 167 bool
 168 v_prepend(vector *v, void *e)
 169 {
 170         return v_insert(v, 0, e);
 171 }
 172
 173 void *
 174 v_remove_first(vector *v)
 175 {
 176         return v_remove(v, 0);
 177 }
 178
 179 void *
 180 v_remove_last(vector *v)
 181 {
 182         return v_remove(v, v_length(v)-1);
 183 }
 184
 185 void *
 186 v_remove(vector *v, size_t i)
 187 {
 188         if (!v || i >= v->length)
 189                 return NULL;
 190         void *elt = v->elts[i];
 191         memmove(v->elts+i, v->elts+i+1, (v->length - (i+1)) * sizeof *v->elts);
 192         v->length--;
 193
 194         CHECK(v);
 195         return elt;
 196 }
 197
 198 bool
 199 v_insert(vector *v, size_t i, void *elt)
 200 {
 201         if (!v || v_reserve_capacity(v, v->length+1) < v->length+1)
 202                 return false;
 203         memmove(v->elts+i+1, v->elts+i, (v->length - i) * sizeof *v->elts);
 204         v->elts[i] = elt;
 205         v->length++;
 206
 207         CHECK(v);
 208         return true;
 209 }
 210
 211 bool
 212 v_swap(vector *v, size_t i, size_t j)
 213 {
 214         if (!v || i >= v->length || j >= v->length)
 215                 return false;
 216         SWAP(v->elts[i], v->elts[j]);
 217
 218         CHECK(v);
 219         return true;
 220 }
 221
 222 void
 223 v_clear(vector *v)
 224 {
 225         v_set_length(v, 0);
 226 }
 227
 228 size_t
 229 v_find_index(const vector *v, const void *needle,
 230              comparator *cmp, void *aux)
 231 {
 232         if (!v || !cmp)
 233                 return SIZE_MAX;
 234         for (size_t i = 0; i < v->length; i++)
 235                 if (cmp(v->elts[i], needle, aux) == 0)
 236                         return i;
 237         return SIZE_MAX;
 238 }
 239
 240 size_t
 241 v_find_last_index(const vector *v, const void *needle,
 242                   comparator *cmp, void *aux)
 243 {
 244         if (!v || !cmp)
 245                 return SIZE_MAX;
 246         for (size_t i = v->length-1; i < SIZE_MAX; i--)
 247                 if (cmp(v->elts[i], needle, aux) == 0)
 248                         return i;
 249         return SIZE_MAX;
 250 }
 251
 252 /* from Bentley, https://www.youtube.com/watch?v=QvgYAQzg1z8 */
 253 static void
 254 _quicksort(vector *v, size_t lo, size_t hi,
 255            comparator *cmp, void *aux)
 256 {
 257         size_t i, m = lo;
 258         if (lo >= hi)
 259                 return;
 260         for (i = lo+1; i <= hi; i++)
 261                 if (cmp(v->elts[i], v->elts[lo], aux) < 0)
 262                 {
 263                         m++;
 264                         SWAP(v->elts[i], v->elts[m]);
 265                 }
 266         SWAP(v->elts[lo], v->elts[m]);
 267
 268         if (m > 0) /* avoid wrapping size_t */
 269                 _quicksort(v, lo, m-1, cmp, aux);
 270         _quicksort(v, m+1, hi, cmp, aux);
 271 }
 272
 273 bool
 274 v_sort(vector *v, comparator *cmp, void *aux)
 275 {
 276         if (!v || !cmp)
 277                 return false;
 278         _quicksort(v, 0, v->length-1, cmp, aux);
 279
 280         CHECK(v);
 281         return true;
 282 }
 283
 284 bool
 285 v_reverse(vector *v)
 286 {
 287         size_t n = v_length(v);
 288         if (n < 2)
 289                 return true;
 290         for (size_t i = n-1; i >= n/2; i--)
 291                 SWAP(v->elts[i], v->elts[n-i-1]);
 292         CHECK(v);
 293         return true;
 294 }