c_cpp/lib/uthash/libut/src/utvector.c

   1 /*
   2 Copyright (c) 2003-2015, Troy D. Hanson     http://troydhanson.github.com/uthash/
   3 All rights reserved.
   4
   5 Redistribution and use in source and binary forms, with or without
   6 modification, are permitted provided that the following conditions are met:
   7
   8     * Redistributions of source code must retain the above copyright
   9       notice, this list of conditions and the following disclaimer.
  10
  11 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
  12 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  13 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
  14 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
  15 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  16 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  17 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  18 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  19 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  20 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  21 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  22 */
  23
  24 #include <assert.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include "utvector.h"
  28
  29 #define INITIAL_SIZE 16
  30
  31 /* utvector
  32  *
  33  * maintain a contiguous buffer of 'n' elements ('i' occupied)
  34  * the 'n' buffers are deep-inited at the time of allocation
  35  * the vector leaves popped slots as-is, clearing them on re-use
  36  * the memory management helper mm is used to define the size and
  37  * deep-init, deep-fini, deep-copy (into inited slots) and deep-clear.
  38  * deep-clear prepares a slot for re-use e.g. reset slot state.
  39  *
  40  */
  41
  42 void oom(void) {
  43   //fprintf(stderr,"out of memory\n");
  44   exit(-1);
  45 }
  46
  47 UT_vector *utvector_new(const UT_mm *mm) {
  48   UT_vector *v = malloc(sizeof(UT_vector)); if (!v) return NULL;
  49   utvector_init(v,mm);
  50   return v;
  51 }
  52
  53 unsigned utvector_len(UT_vector *v) {
  54   return v->i;
  55 }
  56
  57 void utvector_init(UT_vector *v, const UT_mm *mm) {
  58   v->mm = *mm;  // struct copy
  59   v->i = v->n = 0;
  60   v->d = NULL;
  61   utvector_reserve(v, INITIAL_SIZE); // also inits them, sets v->n
  62 }
  63
  64 void utvector_reserve(UT_vector *v, unsigned num) {
  65   if (v->n - v->i >= num) return;     // space is big enough, return
  66   unsigned n = num - (v->n - v->i);   // minimum we need to grow by
  67   if (n < (v->n * 2)) n = (v->n * 2); // grow by at least double current size
  68   char *d = realloc(v->d, (n + v->n) * v->mm.sz);
  69   if (!d) oom();
  70   v->d = d;
  71   void *b = v->d + (v->n * v->mm.sz); // start of newly allocated area
  72   utmm_init(&v->mm,b,n);
  73   v->n = n + v->n;
  74 }
  75
  76 void utvector_fini(UT_vector *v) {
  77   utmm_fini(&v->mm,v->d,v->n);
  78   free(v->d);
  79   v->d = NULL;
  80   v->i = v->n = 0;
  81 }
  82
  83 UT_vector * utvector_clone(UT_vector *src) {
  84   UT_vector *v = utvector_new(&src->mm);
  85   utvector_copy(v, src);
  86   return v;
  87 }
  88
  89 void utvector_clear(UT_vector *v) {
  90   v->i = 0;
  91 }
  92
  93 void utvector_copy(UT_vector *dst, UT_vector *src) { /* dst, src both inited */
  94   assert(dst->mm.sz == src->mm.sz); // double check that its inited
  95   utvector_clear(dst);
  96   utvector_reserve(dst, src->i);
  97   dst->i = src->i;
  98   utmm_clear(&dst->mm,dst->d,src->i);
  99   utmm_copy(&dst->mm, dst->d, src->d, src->i);
 100 }
 101
 102 void utvector_free(UT_vector *v) {
 103   utvector_fini(v);
 104   free(v);
 105 }
 106
 107 void *utvector_extend(UT_vector *v) {
 108   utvector_reserve(v,1);
 109   void *b = v->d + (v->i * v->mm.sz);
 110   utmm_clear(&v->mm,b,1);
 111   v->i++;
 112   return b;
 113 }
 114
 115 void *utvector_next(UT_vector *v, void *cur) {
 116   if (cur == NULL) return v->i ? v->d : NULL;
 117   assert(cur >= (void*)(v->d));  // user pointer must be inside our data area
 118   char *n = (char*)cur + v->mm.sz; // next slot address
 119   if (n >= v->d + (v->i * v->mm.sz)) n=NULL; // only if next slot occupied
 120   return n;
 121 }
 122
 123 void *utvector_head(UT_vector *v) {
 124   if (v->i == 0) return NULL;
 125   return v->d;
 126 }
 127
 128 void *utvector_tail(UT_vector *v) {
 129   if (v->i == 0) return NULL;
 130   return v->d + ((v->i - 1) * v->mm.sz);
 131 }
 132
 133 void *utvector_pop(UT_vector *v) {
 134   if (v->i == 0) return NULL;
 135   return v->d + (--(v->i) * v->mm.sz);
 136 }
 137
 138 void *utvector_elt(UT_vector *v, unsigned i) {
 139   if (i >= v->i) return NULL;
 140   return v->d + (i * v->mm.sz);
 141 }
 142
 143 /* shifting is not very efficient. we end up throwing away/fini'ing the
 144  * head of the vector, then doing a memmove, then having to init a new slot.
 145  * we don't return the shifted item because its been fini'd, and we have
 146  * no caller memory to copy it into anyway. a cpy_shift maybe handy */
 147 void utvector_shift(UT_vector *v) {
 148   assert (v->i);
 149   utmm_fini(&v->mm,v->d,1);
 150   v->i--;
 151   memmove(v->d, v->d + v->mm.sz, (v->n-1)*v->mm.sz);
 152   char *b = v->d + ((v->n-1) * v->mm.sz);
 153   utmm_init(&v->mm,b,1);
 154 }
 155
 156 void utvector_erase(UT_vector *v, unsigned i) {
 157   assert(v->i);
 158   if (i >= v->i) return;
 159   utmm_fini(&v->mm, v->d + (i * v->mm.sz), 1);
 160   v->i--;
 161   if (v->n - 1 > i) {
 162     memmove(v->d + (i * v->mm.sz), v->d + ((i+1) * v->mm.sz), (((v->n-1) - i) * v->mm.sz));
 163   }
 164   char *b = v->d + ((v->n-1) * v->mm.sz);
 165   utmm_init(&v->mm,b,1);
 166 }
 167
 168 void *utvector_push(UT_vector *v, void *e) {
 169   void *b  = utvector_extend(v);
 170   utmm_copy(&v->mm, b, e, 1);
 171   return v->d + ((v->i - 1) * v->mm.sz);
 172 }
 173
 174