diff options
| -rw-r--r-- | bitset.h | 58 |
1 files changed, 58 insertions, 0 deletions
diff --git a/bitset.h b/bitset.h new file mode 100644 index 0000000..f3a8944 --- /dev/null +++ b/bitset.h @@ -0,0 +1,58 @@ +#ifndef BITSET_H +#define BITSET_H + +#include <stdint.h> +#include <stdbit.h> + +#include "arena.h" + +#define BITSET_BYTES sizeof(uintmax_t) +#define BITSET_BITS (8 * BITSET_BYTES) +#define BITSET_CAP(n) (((n)/BITSET_BITS)+1) +#define BITSET_HAS(s, i) (1 & ((s)[(i)/BITSET_BITS] >> ((i)&(BITSET_BITS-1)))) +#define BITSET_MASK(i) ((uintmax_t)1 << ((i)&(BITSET_BITS-1))) +#define BITSET_SET(s, i) ((s)[(i)/BITSET_BITS] |= BITSET_MASK(i)) +#define BITSET_CLR(s, i) ((s)[(i)/BITSET_BITS] &= ~BITSET_MASK(i)) +#define BITSET_ALLOC(a, n) new_arr(a, uintmax_t, BITSET_CAP(n)) +#define BITSET_SET_ALL(s, n) memset(s, 0xff, BITSET_CAP(n) * BITSET_BYTES) +#define BITSET_CLR_ALL(s, n) memset(s, 0x00, BITSET_CAP(n) * BITSET_BYTES) + +typedef struct { + size_t cap; + uintmax_t *data; +} BitSet; + +static inline void bitset_fit(BitSet *s, size_t sz, Arena *a) { + if (s->cap >= sz) return; + size_t c = stdc_bit_ceil(sz); + s->data = resize(a, s->data, BITSET_CAP(s->cap), BITSET_CAP(c)); + s->cap = c; + for (uint32_t i = BITSET_CAP(s->cap); i < c; i++) + s->data[i] = 0; +} + +static inline void bitset_clr(BitSet *s) { + if (s->data) BITSET_CLR_ALL(s->data, s->cap); +} + +static inline void bitset_fill(BitSet *s, size_t n, Arena *a) { + bitset_fit(s, n - 1, a); + if (s->data) BITSET_SET_ALL(s->data, s->cap); +} + +static inline void bitset_add(BitSet *s, uint32_t n, Arena *a) { + bitset_fit(s, n, a); + BITSET_SET(s->data, n); +} + +static inline int bitset_has(BitSet *s, uint32_t n) { + return (n / BITSET_BITS < s->cap) && BITSET_HAS(s->data, n); +} + +static inline void bitset_del(BitSet *s, uint32_t n) { + if (BITSET_HAS(s->data, n)) { + BITSET_CLR(s->data, n); + } +} + +#endif |