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     NEW(vec);
  49     bytes = BVEC_BYTES (vec, init_size  ?  init_size  :  VEC_INIT_SIZE);
  50
  51     vec->bits = mh_xcalloc (1, bytes);
  52     vec->maxsize = bytes * CHAR_BIT;
  53
  54     return vec;
  55 }
  56
  57 void
  58 bvector_copy (bvector_t dest, bvector_t src) {
  59     size_t bytes = BVEC_BYTES (dest, src->maxsize);
  60
  61     free (dest->bits);
  62     dest->bits = mh_xmalloc (bytes);
  63     memcpy (dest->bits, src->bits, bytes);
  64     dest->maxsize = src->maxsize;
  65 }
  66
  67 void
  68 bvector_free (bvector_t vec) {
  69     free (vec->bits);
  70     free (vec);
  71 }
  72
  73 void
  74 bvector_clear (bvector_t vec, size_t n) {
  75     size_t word = BVEC_WORD (vec,n);
  76     size_t offset = BVEC_OFFSET (vec, n);
  77
  78     if (n >= vec->maxsize)
  79         bvector_resize (vec, n);
  80
  81     assert (sizeof *vec->bits <= sizeof 1ul);
  82     vec->bits[word] &= ~(1ul << offset);
  83 }
  84
  85
  86 void
  87 bvector_clear_all (bvector_t vec) {
  88     memset (vec->bits, 0, BVEC_BYTES (vec, vec->maxsize));
  89 }
  90
  91
  92 void
  93 bvector_set (bvector_t vec, size_t n) {
  94     size_t word = BVEC_WORD (vec, n);
  95     size_t offset = BVEC_OFFSET (vec, n);
  96
  97     if (n >= vec->maxsize)
  98         bvector_resize (vec, n);
  99     assert (sizeof *vec->bits <= sizeof 1ul);
 100     vec->bits[word] |= 1ul << offset;
 101 }
 102
 103 unsigned int
 104 bvector_at (bvector_t vec, size_t i) {
 105     size_t word = BVEC_WORD (vec, i);
 106     size_t offset = BVEC_OFFSET (vec, i);
 107
 108     assert (sizeof *vec->bits <= sizeof 1ul);
 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 size_t
 134 bvector_maxsize (bvector_t vec) {
 135     return vec->maxsize;
 136 }
 137
 138
 139 struct svector {
 140     char **strs;
 141     size_t maxsize;
 142     size_t size;
 143 };
 144
 145 static void svector_resize (svector_t, size_t);
 146
 147 svector_t
 148 svector_create (size_t init_size) {
 149     svector_t vec;
 150     size_t bytes;
 151
 152     NEW(vec);
 153     vec->maxsize = init_size ? init_size : VEC_INIT_SIZE;
 154     bytes = vec->maxsize * sizeof (char *);
 155     vec->strs = mh_xcalloc (1, bytes);
 156     vec->size = 0;
 157
 158     return vec;
 159 }
 160
 161 void
 162 svector_free (svector_t vec) {
 163     free (vec->strs);
 164     free (vec);
 165 }
 166
 167 char *
 168 svector_push_back (svector_t vec, char *s) {
 169     if (++vec->size >= vec->maxsize)
 170         svector_resize (vec, vec->size);
 171     return vec->strs[vec->size-1] = s;
 172 }
 173
 174 char *
 175 svector_at (svector_t vec, size_t i) {
 176     if (i >= vec->maxsize)
 177         svector_resize (vec, i);
 178     return vec->strs[i];
 179 }
 180
 181 /*
 182  * Return address of first element that stringwise matches s.
 183  * The caller can replace the contents of the return address.
 184  */
 185 char **
 186 svector_find (svector_t vec, const char *s) {
 187     size_t i;
 188     char **str = vec->strs;
 189
 190     for (i = 0; i < vec->size; ++i, ++str) {
 191         if (*str  &&  ! strcmp(*str, s)) {
 192             return str;
 193         }
 194     }
 195
 196     return NULL;
 197 }
 198
 199 char **
 200 svector_strs (svector_t vec) {
 201     return vec->strs;
 202 }
 203
 204 size_t
 205 svector_size (svector_t vec) {
 206     return vec->size;
 207 }
 208
 209 static void
 210 svector_resize (svector_t vec, size_t maxsize) {
 211     size_t old_maxsize = vec->maxsize;
 212     size_t i;
 213
 214     while ((vec->maxsize *= 2) < maxsize)
 215         ;
 216     vec->strs = mh_xrealloc (vec->strs, vec->maxsize * sizeof (char *));
 217     for (i = old_maxsize; i < vec->maxsize; ++i)
 218         vec->strs[i] = NULL;
 219 }
 220
 221
 222 struct ivector {
 223     int *ints;
 224     size_t maxsize;
 225     size_t size;
 226 };
 227
 228 static void ivector_resize (ivector_t, size_t);
 229
 230 ivector_t
 231 ivector_create (size_t init_size) {
 232     ivector_t vec;
 233     size_t bytes;
 234
 235     NEW(vec);
 236     vec->maxsize = init_size ? init_size : VEC_INIT_SIZE;
 237     bytes = vec->maxsize * sizeof (int);
 238     vec->ints = mh_xcalloc (1, bytes);
 239     vec->size = 0;
 240
 241     return vec;
 242 }
 243
 244 void
 245 ivector_free (ivector_t vec) {
 246     free (vec->ints);
 247     free (vec);
 248 }
 249
 250 int
 251 ivector_push_back (ivector_t vec, int n) {
 252     if (++vec->size >= vec->maxsize)
 253         ivector_resize (vec, vec->size);
 254     return vec->ints[vec->size-1] = n;
 255 }
 256
 257 int
 258 ivector_at (ivector_t vec, size_t i) {
 259     if (i >= vec->maxsize)
 260         ivector_resize (vec, i);
 261     return vec->ints[i];
 262 }
 263
 264 int *
 265 ivector_atp (ivector_t vec, size_t i) {
 266     if (i >= vec->maxsize)
 267         ivector_resize (vec, i);
 268     return &vec->ints[i];
 269 }
 270
 271 size_t
 272 ivector_size (ivector_t vec) {
 273     return vec->size;
 274 }
 275
 276 static void
 277 ivector_resize (ivector_t vec, size_t maxsize) {
 278     size_t old_maxsize = vec->maxsize;
 279     size_t i;
 280
 281     while ((vec->maxsize *= 2) < maxsize)
 282         ;
 283     vec->ints = mh_xrealloc (vec->ints, vec->maxsize * sizeof (int));
 284     for (i = old_maxsize; i < vec->maxsize; ++i)
 285         vec->ints[i] = 0;
 286 }