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