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 /* The default size of a struct bvector's bits, measured in bits.
  23  * The struct's tiny member is used for storage. */
  24 #define BVEC_INIT_SIZE (sizeof *(((bvector_t)NULL)->tiny) * CHAR_BIT)
  25
  26 /* The default number of char pointers in a struct svector. */
  27 #define SVEC_INIT_SIZE 256
  28
  29 /* The default number of ints in a struct ivector. */
  30 #define IVEC_INIT_SIZE 256
  31
  32 /*
  33  * These try to hide the type of the "bits" member of bvector.  But if
  34  * that is changed to a type that's wider than unsigned long, the 1ul
  35  * constants in the code below must also be changed to a 1 that's at
  36  * least as wide as the new type.
  37  */
  38
  39 /* The *sizeof* struct bvector's bits member.  Not its size in bits. */
  40 #define BVEC_SIZEOF_BITS (sizeof *(((bvector_t)NULL)->bits))
  41 /* The number of bits held in one element of the bits member. */
  42 #define BVEC_BITS_BITS (BVEC_SIZEOF_BITS * CHAR_BIT)
  43 /* The index of bit n in struct bvector's bits member. */
  44 #define BVEC_WORD(n) ((n) / BVEC_BITS_BITS)
  45 /* The index of bit n within a single struct bvector's bits member. */
  46 #define BVEC_OFFSET(n) ((n) % BVEC_BITS_BITS)
  47 /* The number of elements bits needs to cover bit n, measured in bytes. */
  48 #define BVEC_BYTES(n) (((n) / BVEC_BITS_BITS + 1) * BVEC_SIZEOF_BITS)
  49
  50 /* bvector_resize ensures the storage used for bits can cover bit
  51  * newsize.  It always increases the size of the storage used for bits,
  52  * even if newsize would have been covered by the existing storage.
  53  * Thus it's normally only called when it's known the storage must grow. */
  54 static void bvector_resize (bvector_t vec, size_t newsize);
  55
  56 bvector_t
  57 bvector_create (void)
  58 {
  59     bvector_t vec;
  60
  61     /* See "wider than unsigned long" comment above. */
  62     assert (sizeof *vec->bits <= sizeof 1ul);
  63
  64     NEW(vec);
  65     bvector_init(vec);
  66
  67     return vec;
  68 }
  69
  70 void bvector_init(struct bvector *bv)
  71 {
  72     bv->bits = bv->tiny;
  73     bv->maxsize = BVEC_INIT_SIZE;
  74     memset(bv->tiny, 0, sizeof bv->tiny);
  75 }
  76
  77 void
  78 bvector_copy (bvector_t dest, bvector_t src)
  79 {
  80     size_t bytes = BVEC_BYTES(src->maxsize);
  81
  82     if (dest->bits != dest->tiny)
  83         free(dest->bits);
  84     if (bytes <= sizeof dest->tiny)
  85         dest->bits = dest->tiny;
  86     else
  87         dest->bits = mh_xmalloc (bytes);
  88     memcpy (dest->bits, src->bits, bytes);
  89     dest->maxsize = src->maxsize;
  90 }
  91
  92 void
  93 bvector_free (bvector_t vec)
  94 {
  95     bvector_fini(vec);
  96     free (vec);
  97 }
  98
  99 void bvector_fini(struct bvector *bv)
 100 {
 101     if (bv->bits != bv->tiny)
 102         free(bv->bits);
 103 }
 104
 105 void
 106 bvector_clear (bvector_t vec, size_t n)
 107 {
 108     if (n < vec->maxsize)
 109         vec->bits[BVEC_WORD(n)] &= ~(1ul << BVEC_OFFSET(n));
 110 }
 111
 112
 113 void
 114 bvector_clear_all (bvector_t vec)
 115 {
 116     memset (vec->bits, 0, BVEC_BYTES(vec->maxsize));
 117 }
 118
 119
 120 void
 121 bvector_set (bvector_t vec, size_t n)
 122 {
 123     size_t word = BVEC_WORD(n);
 124     size_t offset = BVEC_OFFSET(n);
 125
 126     if (n >= vec->maxsize)
 127         bvector_resize (vec, n);
 128     vec->bits[word] |= 1ul << offset;
 129 }
 130
 131 unsigned int
 132 bvector_at (bvector_t vec, size_t i)
 133 {
 134     if (i < vec->maxsize)
 135         return !!(vec->bits[BVEC_WORD(i)] & (1ul << BVEC_OFFSET(i)));
 136
 137     return 0;
 138 }
 139
 140 static void
 141 bvector_resize (bvector_t vec, size_t newsize)
 142 {
 143     size_t oldsize = vec->maxsize;
 144     size_t bytes;
 145
 146     while ((vec->maxsize *= 2) < newsize)
 147         ;
 148     bytes = BVEC_BYTES(vec->maxsize);
 149     if (vec->bits == vec->tiny) {
 150         vec->bits = mh_xmalloc(bytes);
 151         memcpy(vec->bits, vec->tiny, sizeof vec->tiny);
 152     } else
 153         vec->bits = mh_xrealloc(vec->bits, bytes);
 154
 155     memset(vec->bits + (oldsize / BVEC_BITS_BITS), 0,
 156         (vec->maxsize - oldsize) / CHAR_BIT);
 157 }
 158
 159 unsigned long
 160 bvector_first_bits (bvector_t vec)
 161 {
 162     return *vec->bits;
 163 }
 164
 165
 166 struct svector {
 167     char **strs;
 168     size_t maxsize;
 169     size_t size;
 170 };
 171
 172 static void svector_resize (svector_t, size_t);
 173
 174 svector_t
 175 svector_create (size_t init_size)
 176 {
 177     svector_t vec;
 178     size_t bytes;
 179
 180     NEW(vec);
 181     vec->maxsize = init_size ? init_size : SVEC_INIT_SIZE;
 182     bytes = vec->maxsize * sizeof (char *);
 183     vec->strs = mh_xcalloc (1, bytes);
 184     vec->size = 0;
 185
 186     return vec;
 187 }
 188
 189 void
 190 svector_free (svector_t vec)
 191 {
 192     free (vec->strs);
 193     free (vec);
 194 }
 195
 196 char *
 197 svector_push_back (svector_t vec, char *s)
 198 {
 199     if (++vec->size >= vec->maxsize)
 200         svector_resize (vec, vec->size);
 201     return vec->strs[vec->size-1] = s;
 202 }
 203
 204 char *
 205 svector_at (svector_t vec, size_t i)
 206 {
 207     if (i >= vec->maxsize)
 208         svector_resize (vec, i);
 209     return vec->strs[i];
 210 }
 211
 212 /*
 213  * Return address of first element that stringwise matches s.
 214  * The caller can replace the contents of the return address.
 215  */
 216 char **
 217 svector_find (svector_t vec, const char *s)
 218 {
 219     size_t i;
 220     char **str = vec->strs;
 221
 222     for (i = 0; i < vec->size; ++i, ++str) {
 223         if (*str  &&  ! strcmp(*str, s)) {
 224             return str;
 225         }
 226     }
 227
 228     return NULL;
 229 }
 230
 231 char **
 232 svector_strs (svector_t vec)
 233 {
 234     return vec->strs;
 235 }
 236
 237 size_t
 238 svector_size (svector_t vec)
 239 {
 240     return vec->size;
 241 }
 242
 243 static void
 244 svector_resize (svector_t vec, size_t maxsize)
 245 {
 246     size_t old_maxsize = vec->maxsize;
 247
 248     while ((vec->maxsize *= 2) < maxsize)
 249         ;
 250     vec->strs = mh_xrealloc (vec->strs, vec->maxsize * sizeof (char *));
 251     memset(vec->strs + old_maxsize, 0,
 252         (vec->maxsize - old_maxsize) * sizeof *vec->strs);
 253 }
 254
 255
 256 struct ivector {
 257     int *ints;
 258     size_t maxsize;
 259     size_t size;
 260 };
 261
 262 static void ivector_resize (ivector_t, size_t);
 263
 264 ivector_t
 265 ivector_create (size_t init_size)
 266 {
 267     ivector_t vec;
 268     size_t bytes;
 269
 270     NEW(vec);
 271     vec->maxsize = init_size ? init_size : IVEC_INIT_SIZE;
 272     bytes = vec->maxsize * sizeof (int);
 273     vec->ints = mh_xcalloc (1, bytes);
 274     vec->size = 0;
 275
 276     return vec;
 277 }
 278
 279 void
 280 ivector_free (ivector_t vec)
 281 {
 282     free (vec->ints);
 283     free (vec);
 284 }
 285
 286 int
 287 ivector_push_back (ivector_t vec, int n)
 288 {
 289     if (++vec->size >= vec->maxsize)
 290         ivector_resize (vec, vec->size);
 291     return vec->ints[vec->size-1] = n;
 292 }
 293
 294 int
 295 ivector_at (ivector_t vec, size_t i)
 296 {
 297     if (i >= vec->maxsize)
 298         ivector_resize (vec, i);
 299     return vec->ints[i];
 300 }
 301
 302 int *
 303 ivector_atp (ivector_t vec, size_t i)
 304 {
 305     if (i >= vec->maxsize)
 306         ivector_resize (vec, i);
 307     return &vec->ints[i];
 308 }
 309
 310 static void
 311 ivector_resize (ivector_t vec, size_t maxsize)
 312 {
 313     size_t old_maxsize = vec->maxsize;
 314
 315     while ((vec->maxsize *= 2) < maxsize)
 316         ;
 317     vec->ints = mh_xrealloc (vec->ints, vec->maxsize * sizeof (int));
 318     memset(vec->ints + old_maxsize, 0,
 319         (vec->maxsize - old_maxsize) * sizeof *vec->ints);
 320 }