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
  71 bvector_init(struct bvector *bv)
  72 {
  73     bv->bits = bv->tiny;
  74     bv->maxsize = BVEC_INIT_SIZE;
  75     memset(bv->tiny, 0, sizeof bv->tiny);
  76 }
  77
  78 void
  79 bvector_copy (bvector_t dest, bvector_t src)
  80 {
  81     size_t bytes = BVEC_BYTES(src->maxsize);
  82
  83     if (dest->bits != dest->tiny)
  84         free(dest->bits);
  85     if (bytes <= sizeof dest->tiny)
  86         dest->bits = dest->tiny;
  87     else
  88         dest->bits = mh_xmalloc (bytes);
  89     memcpy (dest->bits, src->bits, bytes);
  90     dest->maxsize = src->maxsize;
  91 }
  92
  93 void
  94 bvector_free (bvector_t vec)
  95 {
  96     bvector_fini(vec);
  97     free (vec);
  98 }
  99
 100 void
 101 bvector_fini(struct bvector *bv)
 102 {
 103     if (bv->bits != bv->tiny)
 104         free(bv->bits);
 105 }
 106
 107 void
 108 bvector_clear (bvector_t vec, size_t n)
 109 {
 110     if (n < vec->maxsize)
 111         vec->bits[BVEC_WORD(n)] &= ~(1ul << BVEC_OFFSET(n));
 112 }
 113
 114
 115 void
 116 bvector_clear_all (bvector_t vec)
 117 {
 118     memset (vec->bits, 0, BVEC_BYTES(vec->maxsize));
 119 }
 120
 121
 122 void
 123 bvector_set (bvector_t vec, size_t n)
 124 {
 125     size_t word = BVEC_WORD(n);
 126     size_t offset = BVEC_OFFSET(n);
 127
 128     if (n >= vec->maxsize)
 129         bvector_resize (vec, n);
 130     vec->bits[word] |= 1ul << offset;
 131 }
 132
 133 unsigned int
 134 bvector_at (bvector_t vec, size_t i)
 135 {
 136     if (i < vec->maxsize)
 137         return !!(vec->bits[BVEC_WORD(i)] & (1ul << BVEC_OFFSET(i)));
 138
 139     return 0;
 140 }
 141
 142 static void
 143 bvector_resize (bvector_t vec, size_t newsize)
 144 {
 145     size_t oldsize = vec->maxsize;
 146     size_t bytes;
 147
 148     while ((vec->maxsize *= 2) < newsize)
 149         ;
 150     bytes = BVEC_BYTES(vec->maxsize);
 151     if (vec->bits == vec->tiny) {
 152         vec->bits = mh_xmalloc(bytes);
 153         memcpy(vec->bits, vec->tiny, sizeof vec->tiny);
 154     } else
 155         vec->bits = mh_xrealloc(vec->bits, bytes);
 156
 157     memset(vec->bits + (oldsize / BVEC_BITS_BITS), 0,
 158         (vec->maxsize - oldsize) / CHAR_BIT);
 159 }
 160
 161 unsigned long
 162 bvector_first_bits (bvector_t vec)
 163 {
 164     return *vec->bits;
 165 }
 166
 167
 168 struct svector {
 169     char **strs;
 170     size_t maxsize;
 171     size_t size;
 172 };
 173
 174 static void svector_resize (svector_t, size_t);
 175
 176 svector_t
 177 svector_create (size_t init_size)
 178 {
 179     svector_t vec;
 180     size_t bytes;
 181
 182     NEW(vec);
 183     vec->maxsize = init_size ? init_size : SVEC_INIT_SIZE;
 184     bytes = vec->maxsize * sizeof (char *);
 185     vec->strs = mh_xcalloc (1, bytes);
 186     vec->size = 0;
 187
 188     return vec;
 189 }
 190
 191 void
 192 svector_free (svector_t vec)
 193 {
 194     free (vec->strs);
 195     free (vec);
 196 }
 197
 198 char *
 199 svector_push_back (svector_t vec, char *s)
 200 {
 201     if (++vec->size >= vec->maxsize)
 202         svector_resize (vec, vec->size);
 203     return vec->strs[vec->size-1] = s;
 204 }
 205
 206 char *
 207 svector_at (svector_t vec, size_t i)
 208 {
 209     if (i >= vec->maxsize)
 210         svector_resize (vec, i);
 211     return vec->strs[i];
 212 }
 213
 214 /*
 215  * Return address of first element that stringwise matches s.
 216  * The caller can replace the contents of the return address.
 217  */
 218 char **
 219 svector_find (svector_t vec, const char *s)
 220 {
 221     size_t i;
 222     char **str = vec->strs;
 223
 224     for (i = 0; i < vec->size; ++i, ++str) {
 225         if (*str  &&  ! strcmp(*str, s)) {
 226             return str;
 227         }
 228     }
 229
 230     return NULL;
 231 }
 232
 233 char **
 234 svector_strs (svector_t vec)
 235 {
 236     return vec->strs;
 237 }
 238
 239 size_t
 240 svector_size (svector_t vec)
 241 {
 242     return vec->size;
 243 }
 244
 245 static void
 246 svector_resize (svector_t vec, size_t maxsize)
 247 {
 248     size_t old_maxsize = vec->maxsize;
 249
 250     while ((vec->maxsize *= 2) < maxsize)
 251         ;
 252     vec->strs = mh_xrealloc (vec->strs, vec->maxsize * sizeof (char *));
 253     memset(vec->strs + old_maxsize, 0,
 254         (vec->maxsize - old_maxsize) * sizeof *vec->strs);
 255 }
 256
 257
 258 struct ivector {
 259     int *ints;
 260     size_t maxsize;
 261     size_t size;
 262 };
 263
 264 static void ivector_resize (ivector_t, size_t);
 265
 266 ivector_t
 267 ivector_create (size_t init_size)
 268 {
 269     ivector_t vec;
 270     size_t bytes;
 271
 272     NEW(vec);
 273     vec->maxsize = init_size ? init_size : IVEC_INIT_SIZE;
 274     bytes = vec->maxsize * sizeof (int);
 275     vec->ints = mh_xcalloc (1, bytes);
 276     vec->size = 0;
 277
 278     return vec;
 279 }
 280
 281 void
 282 ivector_free (ivector_t vec)
 283 {
 284     free (vec->ints);
 285     free (vec);
 286 }
 287
 288 int
 289 ivector_push_back (ivector_t vec, int n)
 290 {
 291     if (++vec->size >= vec->maxsize)
 292         ivector_resize (vec, vec->size);
 293     return vec->ints[vec->size-1] = n;
 294 }
 295
 296 int
 297 ivector_at (ivector_t vec, size_t i)
 298 {
 299     if (i >= vec->maxsize)
 300         ivector_resize (vec, i);
 301     return vec->ints[i];
 302 }
 303
 304 int *
 305 ivector_atp (ivector_t vec, size_t i)
 306 {
 307     if (i >= vec->maxsize)
 308         ivector_resize (vec, i);
 309     return &vec->ints[i];
 310 }
 311
 312 static void
 313 ivector_resize (ivector_t vec, size_t maxsize)
 314 {
 315     size_t old_maxsize = vec->maxsize;
 316
 317     while ((vec->maxsize *= 2) < maxsize)
 318         ;
 319     vec->ints = mh_xrealloc (vec->ints, vec->maxsize * sizeof (int));
 320     memset(vec->ints + old_maxsize, 0,
 321         (vec->maxsize - old_maxsize) * sizeof *vec->ints);
 322 }