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