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 #define VEC_INIT_SIZE 256
  23
  24 /*
  25  * These try to hide the type of the "bits" member of bvector.  But if
  26  * that is changed to a type that's wider than unsigned long, the 1ul
  27  * constants in the code below must also be changed to a 1 that's at
  28  * least as wide as the new type.
  29  */
  30 #ifndef Nbby
  31 # define Nbby 8
  32 #endif
  33 #define BVEC_WORD(vec, max) ((max) / (sizeof *vec->bits * Nbby))
  34 #define BVEC_OFFSET(vec, max) ((max) % (sizeof *vec->bits * Nbby))
  35 #define BVEC_BYTES(vec, n) \
  36     ((BVEC_WORD (vec, n) + (BVEC_OFFSET (vec, n) == 0 ? 0 : 1))  * \
  37     sizeof *vec->bits)
  38
  39 struct bvector {
  40     unsigned long *bits;
  41     size_t maxsize;
  42 };
  43
  44 static void bvector_resize (bvector_t, size_t);
  45
  46 bvector_t
  47 bvector_create (size_t init_size) {
  48     bvector_t vec;
  49     size_t bytes;
  50
  51     NEW(vec);
  52     bytes = BVEC_BYTES (vec, init_size  ?  init_size  :  VEC_INIT_SIZE);
  53
  54     vec->bits = mh_xmalloc (bytes);
  55     memset (vec->bits, 0, bytes);
  56     vec->maxsize = bytes * Nbby;
  57
  58     return vec;
  59 }
  60
  61 void
  62 bvector_copy (bvector_t dest, bvector_t src) {
  63     size_t bytes = BVEC_BYTES (dest, src->maxsize);
  64
  65     free (dest->bits);
  66     dest->bits = mh_xmalloc (bytes);
  67     memcpy (dest->bits, src->bits, bytes);
  68     dest->maxsize = src->maxsize;
  69 }
  70
  71 void
  72 bvector_free (bvector_t vec) {
  73     free (vec->bits);
  74     free (vec);
  75 }
  76
  77 void
  78 bvector_clear (bvector_t vec, size_t n) {
  79     size_t word = BVEC_WORD (vec,n);
  80     size_t offset = BVEC_OFFSET (vec, n);
  81
  82     if (n >= vec->maxsize)
  83         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)
 102         bvector_resize (vec, n);
 103     assert (sizeof *vec->bits <= sizeof 1ul);
 104     vec->bits[word] |= 1ul << offset;
 105 }
 106
 107 unsigned int
 108 bvector_at (bvector_t vec, size_t i) {
 109     size_t word = BVEC_WORD (vec, i);
 110     size_t offset = BVEC_OFFSET (vec, i);
 111
 112     assert (sizeof *vec->bits <= sizeof 1ul);
 113     return i < vec->maxsize
 114         ?  (vec->bits[word] & (1ul << offset) ? 1 : 0)
 115         :  0;
 116 }
 117
 118 static void
 119 bvector_resize (bvector_t vec, size_t maxsize) {
 120     size_t old_maxsize = vec->maxsize;
 121     size_t bytes;
 122     size_t i;
 123
 124     while ((vec->maxsize *= 2) < maxsize)
 125         ;
 126     bytes = BVEC_BYTES (vec, vec->maxsize);
 127     vec->bits = mh_xrealloc (vec->bits, bytes);
 128     for (i = old_maxsize; i < vec->maxsize; ++i)
 129         bvector_clear (vec, i);
 130 }
 131
 132 const unsigned long *
 133 bvector_bits (bvector_t vec) {
 134     return vec->bits;
 135 }
 136
 137 size_t
 138 bvector_maxsize (bvector_t vec) {
 139     return vec->maxsize;
 140 }
 141
 142
 143 struct svector {
 144     char **strs;
 145     size_t maxsize;
 146     size_t size;
 147 };
 148
 149 static void svector_resize (svector_t, size_t);
 150
 151 svector_t
 152 svector_create (size_t init_size) {
 153     svector_t vec;
 154     size_t bytes;
 155
 156     NEW(vec);
 157     vec->maxsize = init_size ? init_size : VEC_INIT_SIZE;
 158     bytes = vec->maxsize * sizeof (char *);
 159     vec->strs = mh_xmalloc (bytes);
 160     memset (vec->strs, 0, bytes);
 161     vec->size = 0;
 162
 163     return vec;
 164 }
 165
 166 void
 167 svector_free (svector_t vec) {
 168     free (vec->strs);
 169     free (vec);
 170 }
 171
 172 char *
 173 svector_push_back (svector_t vec, char *s) {
 174     if (++vec->size >= vec->maxsize)
 175         svector_resize (vec, vec->size);
 176     return vec->strs[vec->size-1] = s;
 177 }
 178
 179 char *
 180 svector_at (svector_t vec, size_t i) {
 181     if (i >= vec->maxsize)
 182         svector_resize (vec, i);
 183     return vec->strs[i];
 184 }
 185
 186 /*
 187  * Return address of first element that stringwise matches s.
 188  * The caller can replace the contents of the return address.
 189  */
 190 char **
 191 svector_find (svector_t vec, const char *s) {
 192     size_t i;
 193     char **str = vec->strs;
 194
 195     for (i = 0; i < vec->size; ++i, ++str) {
 196         if (*str  &&  ! strcmp(*str, s)) {
 197             return str;
 198         }
 199     }
 200
 201     return NULL;
 202 }
 203
 204 char **
 205 svector_strs (svector_t vec) {
 206     return vec->strs;
 207 }
 208
 209 size_t
 210 svector_size (svector_t vec) {
 211     return vec->size;
 212 }
 213
 214 static void
 215 svector_resize (svector_t vec, size_t maxsize) {
 216     size_t old_maxsize = vec->maxsize;
 217     size_t i;
 218
 219     while ((vec->maxsize *= 2) < maxsize)
 220         ;
 221     vec->strs = mh_xrealloc (vec->strs, vec->maxsize * sizeof (char *));
 222     for (i = old_maxsize; i < vec->maxsize; ++i)
 223         vec->strs[i] = NULL;
 224 }
 225
 226
 227 struct ivector {
 228     int *ints;
 229     size_t maxsize;
 230     size_t size;
 231 };
 232
 233 static void ivector_resize (ivector_t, size_t);
 234
 235 ivector_t
 236 ivector_create (size_t init_size) {
 237     ivector_t vec;
 238     size_t bytes;
 239
 240     NEW(vec);
 241     vec->maxsize = init_size ? init_size : VEC_INIT_SIZE;
 242     bytes = vec->maxsize * sizeof (int);
 243     vec->ints = mh_xmalloc (bytes);
 244     memset (vec->ints, 0, bytes);
 245     vec->size = 0;
 246
 247     return vec;
 248 }
 249
 250 void
 251 ivector_free (ivector_t vec) {
 252     free (vec->ints);
 253     free (vec);
 254 }
 255
 256 int
 257 ivector_push_back (ivector_t vec, int n) {
 258     if (++vec->size >= vec->maxsize)
 259         ivector_resize (vec, vec->size);
 260     return vec->ints[vec->size-1] = n;
 261 }
 262
 263 int
 264 ivector_at (ivector_t vec, size_t i) {
 265     if (i >= vec->maxsize)
 266         ivector_resize (vec, i);
 267     return vec->ints[i];
 268 }
 269
 270 int *
 271 ivector_atp (ivector_t vec, size_t i) {
 272     if (i >= vec->maxsize)
 273         ivector_resize (vec, i);
 274     return &vec->ints[i];
 275 }
 276
 277 size_t
 278 ivector_size (ivector_t vec) {
 279     return vec->size;
 280 }
 281
 282 static void
 283 ivector_resize (ivector_t vec, size_t maxsize) {
 284     size_t old_maxsize = vec->maxsize;
 285     size_t i;
 286
 287     while ((vec->maxsize *= 2) < maxsize)
 288         ;
 289     vec->ints = mh_xrealloc (vec->ints, vec->maxsize * sizeof (int));
 290     for (i = old_maxsize; i < vec->maxsize; ++i)
 291         vec->ints[i] = 0;
 292 }