add bitset.hHEADmaster

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