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