* can be as large as needed, as long as it fits in (virtual) memory.
*/
-#include <h/mh.h>
-#include <h/utils.h>
+#include "h/mh.h"
+#include "h/utils.h"
/* The default size of a struct bvector's bits, measured in bits.
* The struct's tiny member is used for storage. */
/* 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)
-struct bvector {
- unsigned long *bits;
- size_t maxsize;
- unsigned long tiny[2]; /* Default fixed-size storage for 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.
static void bvector_resize (bvector_t vec, size_t newsize);
bvector_t
-bvector_create (size_t init_size) {
+bvector_create (void)
+{
bvector_t vec;
- size_t bytes;
/* See "wider than unsigned long" comment above. */
assert (sizeof *vec->bits <= sizeof 1ul);
NEW(vec);
-
- if (init_size <= BVEC_INIT_SIZE) {
- vec->bits = vec->tiny;
- vec->maxsize = BVEC_INIT_SIZE;
- memset(vec->tiny, 0, sizeof vec->tiny);
- return vec;
- }
-
- bytes = BVEC_BYTES(init_size);
- vec->bits = mh_xcalloc (1, bytes);
- vec->maxsize = bytes * CHAR_BIT;
+ bvector_init(vec);
return vec;
}
void
-bvector_copy (bvector_t dest, bvector_t src) {
+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(src->maxsize);
if (dest->bits != dest->tiny)
free(dest->bits);
- dest->bits = mh_xmalloc (bytes);
+ 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) {
- if (vec->bits != vec->tiny)
- free(vec->bits);
+bvector_free (bvector_t vec)
+{
+ bvector_fini(vec);
free (vec);
}
void
-bvector_clear (bvector_t vec, size_t n) {
- size_t word = BVEC_WORD(n);
- size_t offset = BVEC_OFFSET(n);
-
- if (n >= vec->maxsize)
- bvector_resize (vec, n);
+bvector_fini(struct bvector *bv)
+{
+ if (bv->bits != bv->tiny)
+ free(bv->bits);
+}
- vec->bits[word] &= ~(1ul << offset);
+void
+bvector_clear (bvector_t vec, size_t n)
+{
+ if (n < vec->maxsize)
+ vec->bits[BVEC_WORD(n)] &= ~(1ul << BVEC_OFFSET(n));
}
void
-bvector_clear_all (bvector_t vec) {
+bvector_clear_all (bvector_t vec)
+{
memset (vec->bits, 0, BVEC_BYTES(vec->maxsize));
}
void
-bvector_set (bvector_t vec, size_t n) {
+bvector_set (bvector_t vec, size_t n)
+{
size_t word = BVEC_WORD(n);
size_t offset = BVEC_OFFSET(n);
}
unsigned int
-bvector_at (bvector_t vec, size_t i) {
- size_t word = BVEC_WORD(i);
- size_t offset = BVEC_OFFSET(i);
+bvector_at (bvector_t vec, size_t i)
+{
+ if (i < vec->maxsize)
+ return !!(vec->bits[BVEC_WORD(i)] & (1ul << BVEC_OFFSET(i)));
- return i < vec->maxsize
- ? (vec->bits[word] & (1ul << offset) ? 1 : 0)
- : 0;
+ return 0;
}
static void
-bvector_resize (bvector_t vec, size_t newsize) {
+bvector_resize (bvector_t vec, size_t newsize)
+{
size_t oldsize = vec->maxsize;
size_t bytes;
}
unsigned long
-bvector_first_bits (bvector_t vec) {
+bvector_first_bits (bvector_t vec)
+{
return *vec->bits;
}
static void svector_resize (svector_t, size_t);
svector_t
-svector_create (size_t init_size) {
+svector_create (size_t init_size)
+{
svector_t vec;
size_t bytes;
}
void
-svector_free (svector_t vec) {
+svector_free (svector_t vec)
+{
free (vec->strs);
free (vec);
}
char *
-svector_push_back (svector_t vec, char *s) {
+svector_push_back (svector_t vec, char *s)
+{
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) {
+svector_at (svector_t vec, size_t i)
+{
if (i >= vec->maxsize)
svector_resize (vec, i);
return vec->strs[i];
* The caller can replace the contents of the return address.
*/
char **
-svector_find (svector_t vec, const char *s) {
+svector_find (svector_t vec, const char *s)
+{
size_t i;
char **str = vec->strs;
}
char **
-svector_strs (svector_t vec) {
+svector_strs (svector_t vec)
+{
return vec->strs;
}
size_t
-svector_size (svector_t vec) {
+svector_size (svector_t vec)
+{
return vec->size;
}
static void
-svector_resize (svector_t vec, size_t maxsize) {
+svector_resize (svector_t vec, size_t maxsize)
+{
size_t old_maxsize = vec->maxsize;
while ((vec->maxsize *= 2) < maxsize)
static void ivector_resize (ivector_t, size_t);
ivector_t
-ivector_create (size_t init_size) {
+ivector_create (size_t init_size)
+{
ivector_t vec;
size_t bytes;
}
void
-ivector_free (ivector_t vec) {
+ivector_free (ivector_t vec)
+{
free (vec->ints);
free (vec);
}
int
-ivector_push_back (ivector_t vec, int n) {
+ivector_push_back (ivector_t vec, int n)
+{
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) {
+ivector_at (ivector_t vec, size_t i)
+{
if (i >= vec->maxsize)
ivector_resize (vec, i);
return vec->ints[i];
}
int *
-ivector_atp (ivector_t vec, size_t i) {
+ivector_atp (ivector_t vec, size_t i)
+{
if (i >= vec->maxsize)
ivector_resize (vec, i);
return &vec->ints[i];
}
static void
-ivector_resize (ivector_t vec, size_t maxsize) {
+ivector_resize (ivector_t vec, size_t maxsize)
+{
size_t old_maxsize = vec->maxsize;
while ((vec->maxsize *= 2) < maxsize)
projects / nmh / blobdiff