-/*
- * vector.c -- dynamically sized vectors
+/* vector.c -- dynamically sized vectors
*
* This code is Copyright (c) 2013, by the authors of nmh. See the
* COPYRIGHT file in the root directory of the nmh distribution for
#include <h/mh.h>
#include <h/utils.h>
-#define VEC_INIT_SIZE 256
+/* The default size of a struct bvector's bits, measured in bits.
+ * The struct's tiny member is used for storage. */
+#define BVEC_INIT_SIZE (sizeof *(((bvector_t)NULL)->tiny) * CHAR_BIT)
+
+/* The default number of char pointers in a struct svector. */
+#define SVEC_INIT_SIZE 256
+
+/* The default number of ints in a struct ivector. */
+#define IVEC_INIT_SIZE 256
/*
* These try to hide the type of the "bits" member of bvector. But if
* constants in the code below must also be changed to a 1 that's at
* least as wide as the new type.
*/
-#ifndef Nbby
-# define Nbby 8
-#endif
-#define BVEC_WORD(vec, max) ((max) / (sizeof *vec->bits * Nbby))
-#define BVEC_OFFSET(vec, max) ((max) % (sizeof *vec->bits * Nbby))
-#define BVEC_BYTES(vec, n) \
- ((BVEC_WORD (vec, n) + (BVEC_OFFSET (vec, n) == 0 ? 0 : 1)) * \
- sizeof *vec->bits)
-
-struct bvector {
- unsigned long *bits;
- size_t maxsize;
-};
-static void bvector_resize (bvector_t, size_t);
+/* The *sizeof* struct bvector's bits member. Not its size in bits. */
+#define BVEC_SIZEOF_BITS (sizeof *(((bvector_t)NULL)->bits))
+/* The number of bits held in one element of the bits member. */
+#define BVEC_BITS_BITS (BVEC_SIZEOF_BITS * CHAR_BIT)
+/* The index of bit n in struct bvector's bits member. */
+#define BVEC_WORD(n) ((n) / BVEC_BITS_BITS)
+/* The index of bit n within a single struct bvector's bits member. */
+#define BVEC_OFFSET(n) ((n) % BVEC_BITS_BITS)
+/* The number of elements bits needs to cover bit n, measured in bytes. */
+#define BVEC_BYTES(n) (((n) / BVEC_BITS_BITS + 1) * BVEC_SIZEOF_BITS)
+
+/* bvector_resize ensures the storage used for bits can cover bit
+ * newsize. It always increases the size of the storage used for bits,
+ * even if newsize would have been covered by the existing storage.
+ * Thus it's normally only called when it's known the storage must grow. */
+static void bvector_resize (bvector_t vec, size_t newsize);
bvector_t
-bvector_create (size_t init_size) {
- bvector_t vec = mh_xmalloc (sizeof *vec);
- size_t bytes = BVEC_BYTES (vec, init_size ? init_size : VEC_INIT_SIZE);
+bvector_create (void) {
+ bvector_t vec;
- vec->bits = mh_xmalloc (bytes);
- memset (vec->bits, 0, bytes);
- vec->maxsize = bytes * Nbby;
+ /* See "wider than unsigned long" comment above. */
+ assert (sizeof *vec->bits <= sizeof 1ul);
+
+ NEW(vec);
+ bvector_init(vec);
return vec;
}
+void bvector_init(struct bvector *bv)
+{
+ bv->bits = bv->tiny;
+ bv->maxsize = BVEC_INIT_SIZE;
+ memset(bv->tiny, 0, sizeof bv->tiny);
+}
+
void
bvector_copy (bvector_t dest, bvector_t src) {
- size_t bytes = BVEC_BYTES (dest, src->maxsize);
-
- free (dest->bits);
- dest->bits = mh_xmalloc (bytes);
+ size_t bytes = BVEC_BYTES(src->maxsize);
+
+ if (dest->bits != dest->tiny)
+ free(dest->bits);
+ if (bytes <= sizeof dest->tiny)
+ dest->bits = dest->tiny;
+ else
+ dest->bits = mh_xmalloc (bytes);
memcpy (dest->bits, src->bits, bytes);
dest->maxsize = src->maxsize;
}
void
bvector_free (bvector_t vec) {
- free (vec->bits);
+ bvector_fini(vec);
free (vec);
}
+void bvector_fini(struct bvector *bv)
+{
+ if (bv->bits != bv->tiny)
+ free(bv->bits);
+}
+
void
bvector_clear (bvector_t vec, size_t n) {
- size_t word = BVEC_WORD (vec,n);
- size_t offset = BVEC_OFFSET (vec, n);
-
- if (n >= vec->maxsize) bvector_resize (vec, n);
-
- assert (sizeof *vec->bits <= sizeof 1ul);
- vec->bits[word] &= ~(1ul << offset);
+ if (n < vec->maxsize)
+ vec->bits[BVEC_WORD(n)] &= ~(1ul << BVEC_OFFSET(n));
}
void
bvector_clear_all (bvector_t vec) {
- memset (vec->bits, 0, BVEC_BYTES (vec, vec->maxsize));
+ memset (vec->bits, 0, BVEC_BYTES(vec->maxsize));
}
void
bvector_set (bvector_t vec, size_t n) {
- size_t word = BVEC_WORD (vec, n);
- size_t offset = BVEC_OFFSET (vec, n);
+ size_t word = BVEC_WORD(n);
+ size_t offset = BVEC_OFFSET(n);
- if (n >= vec->maxsize) bvector_resize (vec, n);
- assert (sizeof *vec->bits <= sizeof 1ul);
+ if (n >= vec->maxsize)
+ bvector_resize (vec, n);
vec->bits[word] |= 1ul << offset;
}
unsigned int
bvector_at (bvector_t vec, size_t i) {
- size_t word = BVEC_WORD (vec, i);
- size_t offset = BVEC_OFFSET (vec, i);
+ if (i < vec->maxsize)
+ return !!(vec->bits[BVEC_WORD(i)] & (1ul << BVEC_OFFSET(i)));
- assert (sizeof *vec->bits <= sizeof 1ul);
- return i < vec->maxsize
- ? (vec->bits[word] & (1ul << offset) ? 1 : 0)
- : 0;
+ return 0;
}
static void
-bvector_resize (bvector_t vec, size_t maxsize) {
- size_t old_maxsize = vec->maxsize;
+bvector_resize (bvector_t vec, size_t newsize) {
+ size_t oldsize = vec->maxsize;
size_t bytes;
- size_t i;
- while ((vec->maxsize *= 2) < maxsize) continue;
- bytes = BVEC_BYTES (vec, vec->maxsize);
- vec->bits = mh_xrealloc (vec->bits, bytes);
- for (i = old_maxsize; i < vec->maxsize; ++i) bvector_clear (vec, i);
+ while ((vec->maxsize *= 2) < newsize)
+ ;
+ bytes = BVEC_BYTES(vec->maxsize);
+ if (vec->bits == vec->tiny) {
+ vec->bits = mh_xmalloc(bytes);
+ memcpy(vec->bits, vec->tiny, sizeof vec->tiny);
+ } else
+ vec->bits = mh_xrealloc(vec->bits, bytes);
+
+ memset(vec->bits + (oldsize / BVEC_BITS_BITS), 0,
+ (vec->maxsize - oldsize) / CHAR_BIT);
}
-const unsigned long *
-bvector_bits (bvector_t vec) {
- return vec->bits;
-}
-
-size_t
-bvector_maxsize (bvector_t vec) {
- return vec->maxsize;
+unsigned long
+bvector_first_bits (bvector_t vec) {
+ return *vec->bits;
}
svector_t
svector_create (size_t init_size) {
- svector_t vec = mh_xmalloc (sizeof *vec);
+ svector_t vec;
size_t bytes;
- vec->maxsize = init_size ? init_size : VEC_INIT_SIZE;
+ NEW(vec);
+ vec->maxsize = init_size ? init_size : SVEC_INIT_SIZE;
bytes = vec->maxsize * sizeof (char *);
- vec->strs = mh_xmalloc (bytes);
- memset (vec->strs, 0, bytes);
+ vec->strs = mh_xcalloc (1, bytes);
vec->size = 0;
return vec;
char *
svector_push_back (svector_t vec, char *s) {
- if (++vec->size >= vec->maxsize) svector_resize (vec, vec->size);
+ if (++vec->size >= vec->maxsize)
+ svector_resize (vec, vec->size);
return vec->strs[vec->size-1] = s;
}
char *
svector_at (svector_t vec, size_t i) {
- if (i >= vec->maxsize) svector_resize (vec, i);
+ if (i >= vec->maxsize)
+ svector_resize (vec, i);
return vec->strs[i];
}
+/*
+ * Return address of first element that stringwise matches s.
+ * The caller can replace the contents of the return address.
+ */
+char **
+svector_find (svector_t vec, const char *s) {
+ size_t i;
+ char **str = vec->strs;
+
+ for (i = 0; i < vec->size; ++i, ++str) {
+ if (*str && ! strcmp(*str, s)) {
+ return str;
+ }
+ }
+
+ return NULL;
+}
+
char **
svector_strs (svector_t vec) {
return vec->strs;
static void
svector_resize (svector_t vec, size_t maxsize) {
size_t old_maxsize = vec->maxsize;
- size_t i;
- while ((vec->maxsize *= 2) < maxsize) continue;
+ while ((vec->maxsize *= 2) < maxsize)
+ ;
vec->strs = mh_xrealloc (vec->strs, vec->maxsize * sizeof (char *));
- for (i = old_maxsize; i < vec->maxsize; ++i) vec->strs[i] = NULL;
+ memset(vec->strs + old_maxsize, 0,
+ (vec->maxsize - old_maxsize) * sizeof *vec->strs);
}
ivector_t
ivector_create (size_t init_size) {
- ivector_t vec = mh_xmalloc (sizeof *vec);
+ ivector_t vec;
size_t bytes;
- vec->maxsize = init_size ? init_size : VEC_INIT_SIZE;
+ NEW(vec);
+ vec->maxsize = init_size ? init_size : IVEC_INIT_SIZE;
bytes = vec->maxsize * sizeof (int);
- vec->ints = mh_xmalloc (bytes);
- memset (vec->ints, 0, bytes);
+ vec->ints = mh_xcalloc (1, bytes);
vec->size = 0;
return vec;
int
ivector_push_back (ivector_t vec, int n) {
- if (++vec->size >= vec->maxsize) ivector_resize (vec, vec->size);
+ if (++vec->size >= vec->maxsize)
+ ivector_resize (vec, vec->size);
return vec->ints[vec->size-1] = n;
}
int
ivector_at (ivector_t vec, size_t i) {
- if (i >= vec->maxsize) ivector_resize (vec, i);
+ if (i >= vec->maxsize)
+ ivector_resize (vec, i);
return vec->ints[i];
}
int *
ivector_atp (ivector_t vec, size_t i) {
- if (i >= vec->maxsize) ivector_resize (vec, i);
+ if (i >= vec->maxsize)
+ ivector_resize (vec, i);
return &vec->ints[i];
}
-size_t
-ivector_size (ivector_t vec) {
- return vec->size;
-}
-
static void
ivector_resize (ivector_t vec, size_t maxsize) {
size_t old_maxsize = vec->maxsize;
- size_t i;
- while ((vec->maxsize *= 2) < maxsize) continue;
+ while ((vec->maxsize *= 2) < maxsize)
+ ;
vec->ints = mh_xrealloc (vec->ints, vec->maxsize * sizeof (int));
- for (i = old_maxsize; i < vec->maxsize; ++i) vec->ints[i] = 0;
+ memset(vec->ints + old_maxsize, 0,
+ (vec->maxsize - old_maxsize) * sizeof *vec->ints);
}
projects / nmh / blobdiff