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

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