diplodocus.org Git - nmh/blob - sbr/vector.c

   1 /* vector.c -- dynamically sized vectors
   2  *
   3  * This code is Copyright (c) 2013, by the authors of nmh.  See the
   4  * COPYRIGHT file in the root directory of the nmh distribution for
   5  * complete copyright information.
   6  */
   7
   8 /*
   9  * This file defines several kinds of vectors:
  10  *   bvector:  bit vector
  11  *   svector:  vector of char arrays
  12  *   ivector:  vector of ints
  13  *
  14  * The interfaces provide only the capabilities needed by nmh.  The
  15  * implementations rely on dynamic allocation, so that a vector
  16  * can be as large as needed, as long as it fits in (virtual) memory.
  17  */
  18
  19 #include <h/mh.h>
  20 #include <h/utils.h>
  21
  22 #define VEC_INIT_SIZE 256
  23
  24 /*
  25  * These try to hide the type of the "bits" member of bvector.  But if
  26  * that is changed to a type that's wider than unsigned long, the 1ul
  27  * constants in the code below must also be changed to a 1 that's at
  28  * least as wide as the new type.
  29  */
  30 #define BVEC_WORD(vec, max) ((max) / (sizeof *vec->bits * CHAR_BIT))
  31 #define BVEC_OFFSET(vec, max) ((max) % (sizeof *vec->bits * CHAR_BIT))
  32 #define BVEC_BYTES(vec, n) \
  33     ((BVEC_WORD (vec, n) + (BVEC_OFFSET (vec, n) == 0 ? 0 : 1))  * \
  34     sizeof *vec->bits)
  35
  36 struct bvector {
  37     unsigned long *bits;
  38     size_t maxsize;
  39 };
  40
  41 static void bvector_resize (bvector_t, size_t);
  42
  43 bvector_t
  44 bvector_create (size_t init_size) {
  45     bvector_t vec;
  46     size_t bytes;
  47
  48     /* See "wider than unsigned long" comment above. */
  49     assert (sizeof *vec->bits <= sizeof 1ul);
  50
  51     NEW(vec);
  52     bytes = BVEC_BYTES (vec, init_size  ?  init_size  :  VEC_INIT_SIZE);
  53
  54     vec->bits = mh_xcalloc (1, bytes);
  55     vec->maxsize = bytes * CHAR_BIT;
  56
  57     return vec;
  58 }
  59
  60 void
  61 bvector_copy (bvector_t dest, bvector_t src) {
  62     size_t bytes = BVEC_BYTES (dest, src->maxsize);
  63
  64     free (dest->bits);
  65     dest->bits = mh_xmalloc (bytes);
  66     memcpy (dest->bits, src->bits, bytes);
  67     dest->maxsize = src->maxsize;
  68 }
  69
  70 void
  71 bvector_free (bvector_t vec) {
  72     free (vec->bits);
  73     free (vec);
  74 }
  75
  76 void
  77 bvector_clear (bvector_t vec, size_t n) {
  78     size_t word = BVEC_WORD (vec,n);
  79     size_t offset = BVEC_OFFSET (vec, n);
  80
  81     if (n >= vec->maxsize)
  82         bvector_resize (vec, n);
  83
  84     vec->bits[word] &= ~(1ul << offset);
  85 }
  86
  87
  88 void
  89 bvector_clear_all (bvector_t vec) {
  90     memset (vec->bits, 0, BVEC_BYTES (vec, vec->maxsize));
  91 }
  92
  93
  94 void
  95 bvector_set (bvector_t vec, size_t n) {
  96     size_t word = BVEC_WORD (vec, n);
  97     size_t offset = BVEC_OFFSET (vec, n);
  98
  99     if (n >= vec->maxsize)
 100         bvector_resize (vec, n);
 101     vec->bits[word] |= 1ul << offset;
 102 }
 103
 104 unsigned int
 105 bvector_at (bvector_t vec, size_t i) {
 106     size_t word = BVEC_WORD (vec, i);
 107     size_t offset = BVEC_OFFSET (vec, i);
 108
 109     return i < vec->maxsize
 110         ?  (vec->bits[word] & (1ul << offset) ? 1 : 0)
 111         :  0;
 112 }
 113
 114 static void
 115 bvector_resize (bvector_t vec, size_t maxsize) {
 116     size_t old_maxsize = vec->maxsize;
 117     size_t bytes;
 118     size_t i;
 119
 120     while ((vec->maxsize *= 2) < maxsize)
 121         ;
 122     bytes = BVEC_BYTES (vec, vec->maxsize);
 123     vec->bits = mh_xrealloc (vec->bits, bytes);
 124     for (i = old_maxsize; i < vec->maxsize; ++i)
 125         bvector_clear (vec, i);
 126 }
 127
 128 const unsigned long *
 129 bvector_bits (bvector_t vec) {
 130     return vec->bits;
 131 }
 132
 133
 134 struct svector {
 135     char **strs;
 136     size_t maxsize;
 137     size_t size;
 138 };
 139
 140 static void svector_resize (svector_t, size_t);
 141
 142 svector_t
 143 svector_create (size_t init_size) {
 144     svector_t vec;
 145     size_t bytes;
 146
 147     NEW(vec);
 148     vec->maxsize = init_size ? init_size : VEC_INIT_SIZE;
 149     bytes = vec->maxsize * sizeof (char *);
 150     vec->strs = mh_xcalloc (1, bytes);
 151     vec->size = 0;
 152
 153     return vec;
 154 }
 155
 156 void
 157 svector_free (svector_t vec) {
 158     free (vec->strs);
 159     free (vec);
 160 }
 161
 162 char *
 163 svector_push_back (svector_t vec, char *s) {
 164     if (++vec->size >= vec->maxsize)
 165         svector_resize (vec, vec->size);
 166     return vec->strs[vec->size-1] = s;
 167 }
 168
 169 char *
 170 svector_at (svector_t vec, size_t i) {
 171     if (i >= vec->maxsize)
 172         svector_resize (vec, i);
 173     return vec->strs[i];
 174 }
 175
 176 /*
 177  * Return address of first element that stringwise matches s.
 178  * The caller can replace the contents of the return address.
 179  */
 180 char **
 181 svector_find (svector_t vec, const char *s) {
 182     size_t i;
 183     char **str = vec->strs;
 184
 185     for (i = 0; i < vec->size; ++i, ++str) {
 186         if (*str  &&  ! strcmp(*str, s)) {
 187             return str;
 188         }
 189     }
 190
 191     return NULL;
 192 }
 193
 194 char **
 195 svector_strs (svector_t vec) {
 196     return vec->strs;
 197 }
 198
 199 size_t
 200 svector_size (svector_t vec) {
 201     return vec->size;
 202 }
 203
 204 static void
 205 svector_resize (svector_t vec, size_t maxsize) {
 206     size_t old_maxsize = vec->maxsize;
 207     size_t i;
 208
 209     while ((vec->maxsize *= 2) < maxsize)
 210         ;
 211     vec->strs = mh_xrealloc (vec->strs, vec->maxsize * sizeof (char *));
 212     for (i = old_maxsize; i < vec->maxsize; ++i)
 213         vec->strs[i] = NULL;
 214 }
 215
 216
 217 struct ivector {
 218     int *ints;
 219     size_t maxsize;
 220     size_t size;
 221 };
 222
 223 static void ivector_resize (ivector_t, size_t);
 224
 225 ivector_t
 226 ivector_create (size_t init_size) {
 227     ivector_t vec;
 228     size_t bytes;
 229
 230     NEW(vec);
 231     vec->maxsize = init_size ? init_size : VEC_INIT_SIZE;
 232     bytes = vec->maxsize * sizeof (int);
 233     vec->ints = mh_xcalloc (1, bytes);
 234     vec->size = 0;
 235
 236     return vec;
 237 }
 238
 239 void
 240 ivector_free (ivector_t vec) {
 241     free (vec->ints);
 242     free (vec);
 243 }
 244
 245 int
 246 ivector_push_back (ivector_t vec, int n) {
 247     if (++vec->size >= vec->maxsize)
 248         ivector_resize (vec, vec->size);
 249     return vec->ints[vec->size-1] = n;
 250 }
 251
 252 int
 253 ivector_at (ivector_t vec, size_t i) {
 254     if (i >= vec->maxsize)
 255         ivector_resize (vec, i);
 256     return vec->ints[i];
 257 }
 258
 259 int *
 260 ivector_atp (ivector_t vec, size_t i) {
 261     if (i >= vec->maxsize)
 262         ivector_resize (vec, i);
 263     return &vec->ints[i];
 264 }
 265
 266 static void
 267 ivector_resize (ivector_t vec, size_t maxsize) {
 268     size_t old_maxsize = vec->maxsize;
 269     size_t i;
 270
 271     while ((vec->maxsize *= 2) < maxsize)
 272         ;
 273     vec->ints = mh_xrealloc (vec->ints, vec->maxsize * sizeof (int));
 274     for (i = old_maxsize; i < vec->maxsize; ++i)
 275         vec->ints[i] = 0;
 276 }