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         void (*elt_dtor)(void *);
  24 };
  25
  26 static void
  27 _check(const vector *v)
  28 {
  29         assert(v);
  30         assert(v->capacity > 0);
  31         /* test that capacity is a power of two if not maxed out
  32          * https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2
  33          */
  34         if (v->capacity < SIZE_MAX)
  35                 assert((v->capacity & (v->capacity - 1)) == 0);
  36         assert(v->length <= v->capacity);
  37 }
  38
  39 vector *
  40 v_new(void (*elt_dtor)(void *))
  41 {
  42         vector *v   = malloc(sizeof *v);
  43         void **elts = malloc(INITIAL_CAPACITY * sizeof *elts);
  44         if (!v || !elts)
  45         {
  46                 free(v);
  47                 free(elts);
  48                 return NULL;
  49         }
  50         *v = (vector){
  51                 .capacity = INITIAL_CAPACITY,
  52                 .elts = elts,
  53                 .elt_dtor = elt_dtor
  54         };
  55         CHECK(v);
  56         return v;
  57 }
  58
  59 void
  60 v_free(vector *v)
  61 {
  62         if (!v)
  63                 return;
  64         v_clear(v);
  65         free(v->elts);
  66         free(v);
  67 }
  68
  69 size_t
  70 v_length(const vector *v)
  71 {
  72         return v ? v->length : 0;
  73 }
  74
  75 bool
  76 v_set_length(vector *v, size_t desired)
  77 {
  78         if (!v)
  79                 return false;
  80         if (v->elt_dtor) /* free any, if necessary */
  81                 for (size_t i = desired; i < v->length; i++)
  82                         v->elt_dtor(v->elts[i]);
  83         if (v_reserve_capacity(v, desired) < desired)
  84                 return false;
  85         for (size_t i = v->length; i < desired; i++)
  86                 v->elts[i] = NULL;
  87         v->length = desired;
  88
  89         CHECK(v);
  90         return true;
  91 }
  92
  93 size_t
  94 v_capacity(const vector *v)
  95 {
  96         return v ? v->capacity : 0;
  97 }
  98
  99 size_t
 100 v_reserve_capacity(vector *v, size_t desired)
 101 {
 102         if (!v)
 103                 return 0;
 104         if (desired <= v->capacity)
 105                 return v->capacity;
 106         size_t n = v->capacity;
 107         /* SIZE_MAX is one less than a power of two, so if
 108          * we keep looping too long we'll hit zero */
 109         while (0 < n && n < desired)
 110                 n *= 2;
 111         if (n == 0)
 112                 n = SIZE_MAX;
 113         void **enlarged = realloc(v->elts, n);
 114         if (!enlarged)
 115                 return v->capacity;
 116         v->elts = enlarged;
 117         v->capacity = n;
 118
 119         CHECK(v);
 120         return n;
 121 }
 122
 123 bool
 124 v_is_empty(const vector *v)
 125 {
 126         return v_length(v) == 0;
 127 }
 128
 129 void *
 130 v_at(const vector *v, size_t i)
 131 {
 132         if (!v || i >= v->length)
 133                 return NULL;
 134         return v->elts[i];
 135 }
 136
 137 void *
 138 v_first(const vector *v)
 139 {
 140         return v_at(v, 0);
 141 }
 142
 143 void *
 144 v_last(const vector *v)
 145 {
 146         /* successfully fails when length is 0 */
 147         return v_at(v, v_length(v)-1);
 148 }
 149
 150 bool
 151 v_append(vector *v, void *e)
 152 {
 153         return v_insert(v, v_length(v), e);
 154 }
 155
 156 bool
 157 v_prepend(vector *v, void *e)
 158 {
 159         return v_insert(v, 0, e);
 160 }
 161
 162 void *
 163 v_remove_first(vector *v)
 164 {
 165         return v_remove(v, 0);
 166 }
 167
 168 void *
 169 v_remove_last(vector *v)
 170 {
 171         return v_remove(v, v_length(v)-1);
 172 }
 173
 174 void *
 175 v_remove(vector *v, size_t i)
 176 {
 177         if (!v || i >= v->length)
 178                 return NULL;
 179         void *elt = v->elts[i];
 180         memmove(v->elts+i, v->elts+i+1, (v->length - (i+1)) * sizeof *v->elts);
 181         v->length--;
 182
 183         CHECK(v);
 184         return elt;
 185 }
 186
 187 bool
 188 v_insert(vector *v, size_t i, void *elt)
 189 {
 190         if (!v || v_reserve_capacity(v, v->length+1) < v->length+1)
 191                 return false;
 192         memmove(v->elts+i+1, v->elts+i, (v->length - i) * sizeof *v->elts);
 193         v->elts[i] = elt;
 194         v->length++;
 195
 196         CHECK(v);
 197         return true;
 198 }
 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 }