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
   7 #define INITIAL_CAPACITY 64
   8
   9 #ifdef NDEBUG
  10         #define CHECK(x) (x)
  11 #else
  12         #define CHECK(x) _check(x)
  13 #endif
  14
  15 static vector *
  16 _check(vector *v)
  17 {
  18         assert(v);
  19         assert(v->capacity > 0);
  20         assert(v->length <= v->capacity);
  21         assert(v->length < SIZE_MAX);
  22         return v;
  23 }
  24
  25 vector *
  26 v_new(void (*elt_dtor)(void *))
  27 {
  28         vector *v   = malloc(sizeof *v);
  29         void **elts = malloc(INITIAL_CAPACITY * sizeof *elts);
  30         if (!v || !elts)
  31         {
  32                 free(v);
  33                 free(elts);
  34                 return NULL;
  35         }
  36         *v = (vector){
  37                 .capacity = INITIAL_CAPACITY,
  38                 .elts = elts,
  39                 .elt_dtor = elt_dtor
  40         };
  41         return CHECK(v);
  42 }
  43
  44 void
  45 v_free(vector *v)
  46 {
  47         if (!v)
  48                 return;
  49         v_clear(v);
  50         free(v->elts);
  51         free(v);
  52 }
  53
  54 size_t
  55 v_length(const vector *v)
  56 {
  57         return v ? v->length : SIZE_MAX;
  58 }
  59
  60 bool
  61 v_set_length(vector *v, size_t len)
  62 {
  63         if (!v || len == SIZE_MAX)
  64                 return false;
  65         if (v->elt_dtor) /* free any, if necessary */
  66                 for (size_t i = len; i < v->length; i++)
  67                         v->elt_dtor(v->elts[i]);
  68         if (!v_reserve_capacity(v, len))
  69                 return false;
  70         for (size_t i = v->length; i < len; i++)
  71                 v->elts[i] = NULL;
  72         v->length = len;
  73
  74         (void)CHECK(v);
  75         return true;
  76 }
  77
  78 size_t
  79 v_capacity(const vector *v)
  80 {
  81         return v ? v->capacity : 0;
  82 }
  83
  84 size_t v_reserve_capacity(vector *v, size_t desired)
  85 {
  86         if (!v)
  87                 return 0;
  88         if (desired <= v->capacity)
  89                 return v->capacity;
  90         size_t n;
  91         for (n = v->capacity; n < desired && n < SIZE_MAX/2; n *= 2)
  92                 ;
  93         if (n < desired)
  94                 n = desired; /* desired >= SIZE_MAX/2 */
  95         void **enlarged = realloc(v->elts, n);
  96         if (!enlarged)
  97                 return v->capacity;
  98         v->elts = enlarged;
  99         v->capacity = n;
 100
 101         (void)CHECK(v);
 102         return n;
 103 }
 104
 105 void
 106 v_clear(vector *v)
 107 {
 108         assert(v_set_length(v, 0));
 109 }