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