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