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