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

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