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

   1 #include "vector.h"
   2
   3 #include <assert.h>
   4 #include <errno.h>
   5 #include <stdint.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8
   9 #define INITIAL_CAPACITY 64
  10
  11 #ifdef NDEBUG
  12         #define CHECK(x) (x)
  13 #else
  14         #define CHECK(x) _check(x)
  15 #endif
  16
  17 static vector *
  18 _check(vector *v)
  19 {
  20         assert(v);
  21         assert(v->capacity > 0);
  22         assert(v->length <= v->capacity);
  23         assert(v->length < SIZE_MAX);
  24         return v;
  25 }
  26
  27 vector *
  28 v_new(void (*elt_dtor)(void *))
  29 {
  30         vector *v   = malloc(sizeof *v);
  31         void **elts = malloc(INITIAL_CAPACITY * sizeof *elts);
  32         if (!v || !elts)
  33         {
  34                 free(v);
  35                 free(elts);
  36                 return NULL;
  37         }
  38         *v = (vector){
  39                 .capacity = INITIAL_CAPACITY,
  40                 .elts = elts,
  41                 .elt_dtor = elt_dtor
  42         };
  43         return CHECK(v);
  44 }
  45
  46 void
  47 v_free(vector *v)
  48 {
  49         if (!v)
  50                 return;
  51         v_clear(v);
  52         free(v->elts);
  53         free(v);
  54 }
  55
  56 size_t
  57 v_length(const vector *v)
  58 {
  59         return v ? v->length : SIZE_MAX;
  60 }
  61
  62 bool
  63 v_set_length(vector *v, size_t len)
  64 {
  65         if (!v || len == SIZE_MAX)
  66                 return false;
  67         if (v->elt_dtor) /* free any, if necessary */
  68                 for (size_t i = len; i < v->length; i++)
  69                         v->elt_dtor(v->elts[i]);
  70         if (!v_reserve_capacity(v, len))
  71                 return false;
  72         for (size_t i = v->length; i < len; i++)
  73                 v->elts[i] = NULL;
  74         v->length = len;
  75
  76         (void)CHECK(v);
  77         return true;
  78 }
  79
  80 size_t
  81 v_capacity(const vector *v)
  82 {
  83         return v ? v->capacity : 0;
  84 }
  85
  86 size_t
  87 v_reserve_capacity(vector *v, size_t desired)
  88 {
  89         if (!v)
  90                 return 0;
  91         if (desired <= v->capacity)
  92                 return v->capacity;
  93         size_t n = v->capacity;
  94         while (n < desired && n <= SIZE_MAX/2)
  95                 n *= 2;
  96         if (n < desired)
  97                 n = desired; /* > SIZE_MAX/2 */
  98         void **enlarged = realloc(v->elts, n);
  99         if (!enlarged)
 100                 return v->capacity;
 101         v->elts = enlarged;
 102         v->capacity = n;
 103
 104         (void)CHECK(v);
 105         return n;
 106 }
 107
 108 bool
 109 v_is_empty(const vector *v)
 110 {
 111         return v_length(v) == 0;
 112 }
 113
 114 void *
 115 v_at(const vector *v, size_t i)
 116 {
 117         if (!v || i >= v->length)
 118         {
 119                 errno = EDOM;
 120                 return NULL;
 121         }
 122         return v->elts[i];
 123 }
 124
 125 void *
 126 v_first(const vector *v)
 127 {
 128         return v_at(v, 0);
 129 }
 130
 131 void *
 132 v_last(const vector *v)
 133 {
 134         /* when length is 0, length-1 is SIZE_MAX */
 135         return v_at(v, v_length(v)-1);
 136 }
 137
 138 bool
 139 v_append(vector *v, void *e)
 140 {
 141         return v_insert(v, v_length(v), e);
 142 }
 143
 144 bool
 145 v_prepend(vector *v, void *e)
 146 {
 147         return v_insert(v, 0, e);
 148 }
 149
 150 void *
 151 v_remove_first(vector *v)
 152 {
 153         return v_remove(v, 0, 1);
 154 }
 155
 156 void *
 157 v_remove_last(vector *v)
 158 {
 159         return v_remove(v, v_length(v)-1, 1);
 160 }
 161
 162 bool
 163 v_insert(vector *v, size_t i, void *elt)
 164 {
 165         if (!v || !v_reserve_capacity(v, v->length+1))
 166                 return false;
 167         memmove(v->elts+i+1, v->elts+i, (v->length - i) * sizeof *v->elts);
 168         v->elts[i] = elt;
 169         v->length++;
 170
 171         (void)CHECK(v);
 172         return true;
 173 }
 174
 175 bool
 176 v_swap(vector *v, size_t i, size_t j)
 177 {
 178         if (!v || i >= v->length || j >= v->length)
 179                 return false;
 180         void *t = v->elts[i];
 181         v->elts[i] = v->elts[j];
 182         v->elts[j] = t;
 183
 184         (void)CHECK(v);
 185         return true;
 186 }
 187
 188 void
 189 v_clear(vector *v)
 190 {
 191         v_set_length(v, 0);
 192 }
 193
 194 size_t
 195 v_find_index(const vector *v, const void *needle,
 196              int (*cmp)(const void *, const void *))
 197 {
 198         if (!v)
 199                 return SIZE_MAX;
 200         for (size_t i = 0; i < v->length; i++)
 201                 if (cmp(v->elts[i], needle) == 0)
 202                         return i;
 203         return SIZE_MAX;
 204 }
 205
 206 size_t
 207 v_find_last_index(const vector *v, const void *needle,
 208                   int (*cmp)(const void *, const void *))
 209 {
 210         if (!v)
 211                 return SIZE_MAX;
 212         for (size_t i = v->length-1; i < SIZE_MAX; i--)
 213                 if (cmp(v->elts[i], needle) == 0)
 214                         return i;
 215         return SIZE_MAX;
 216 }
 217
 218 bool
 219 v_sort(vector *v, int (*cmp)(const void *, const void *))
 220 {
 221         if (!v)
 222                 return false;
 223         qsort(v->elts, v->length, sizeof v->elts[0], cmp);
 224
 225         (void)CHECK(v);
 226         return true;
 227 }