1 files changed, 152 insertions, 0 deletions
diff --git a/lib/bitset.h b/lib/bitset.h
new file mode 100644
index 0000000..d8979de
--- /dev/null
+++ b/lib/bitset.h
@@ -0,0 +1,152 @@
+/*
+ * Copyright (c) 2026 Dylan Araps
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+#ifndef DYLAN_BITSET_H
+#define DYLAN_BITSET_H
+
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+
+#include "util.h"
+
+enum {
+  BITSET_WORD_BITS  = 64,
+  BITSET_WORD_SHIFT =  6,
+  BITSET_WORD_MASK  = BITSET_WORD_BITS - 1,
+};
+
+#define BITSET_W(n) (((n) + BITSET_WORD_MASK) >> BITSET_WORD_SHIFT)
+
+static inline u8
+bitset_get(const u64 *b, usize i)
+{
+  return (b[i >> BITSET_WORD_SHIFT] >> (i & BITSET_WORD_MASK)) & 1ull;
+}
+
+static inline void
+bitset_set(u64 *b, usize i)
+{
+  b[i >> BITSET_WORD_SHIFT] |= 1ull << (i & BITSET_WORD_MASK);
+}
+
+static inline void
+bitset_clr(u64 *b, usize i)
+{
+  b[i >> BITSET_WORD_SHIFT] &= ~(1ull << (i & BITSET_WORD_MASK));
+}
+
+static inline void
+bitset_tog(u64 *b, usize i)
+{
+  b[i >> BITSET_WORD_SHIFT] ^= 1ull << (i & BITSET_WORD_MASK);
+}
+
+static inline void
+bitset_assign(u64 *b, usize i, int v)
+{
+  u64 *w = &b[i >> BITSET_WORD_SHIFT];
+  u64  m = 1ull << (i & BITSET_WORD_MASK);
+  *w = v ? (*w | m) : (*w & ~m);
+}
+
+static inline usize
+bitset_count(const u64 *b, usize l)
+{
+  usize c = 0;
+  for (usize i = 0, w = BITSET_W(l); i < w; i++)
+    c += u64_popcount(b[i]);
+  return c;
+}
+
+static inline void
+bitset_set_all(u64 *v, usize n)
+{
+  memset(v, 0xff, BITSET_W(n) * sizeof *v);
+}
+
+static inline void
+bitset_clr_all(u64 *v, usize n)
+{
+  memset(v, 0, BITSET_W(n) * sizeof *v);
+}
+
+static inline void
+bitset_invert(u64 *v, usize n)
+{
+  usize w = BITSET_W(n);
+  for (usize i = 0; i < w; i++) v[i] = ~v[i];
+  usize r = n & BITSET_WORD_MASK;
+  if (r) v[w - 1] &= (1ull << r) - 1;
+}
+
+static inline void
+bitset_swap(u64 *b, usize i, usize j)
+{
+  u8 bi = bitset_get(b, i);
+  u8 bj = bitset_get(b, j);
+  bitset_assign(b, i, bj);
+  bitset_assign(b, j, bi);
+}
+
+static inline usize
+bitset_next_set(const u64 *b, usize i, usize n)
+{
+  if (i >= n) return SIZE_MAX;
+  usize wi = i >> BITSET_WORD_SHIFT;
+  usize wN = BITSET_W(n);
+  u64 w = b[wi];
+  w &= (~0ull << (i & BITSET_WORD_MASK));
+
+  for (;;) {
+    if (w) {
+      usize j = (wi << BITSET_WORD_SHIFT) + u64_ctz(w);
+      return j < n ? j : SIZE_MAX;
+    }
+
+    if (++wi >= wN) break;
+    w = b[wi];
+  }
+
+  return SIZE_MAX;
+}
+
+static inline usize
+bitset_prev_set(const u64 *b, usize i, usize n)
+{
+  if (i >= n) i = n - 1;
+  usize wi = i >> BITSET_WORD_SHIFT;
+  u64 w = b[wi];
+  u64 r = (u64)(i & BITSET_WORD_MASK);
+  w &= (r == BITSET_WORD_MASK) ? ~0ull : ((1ull << (r + 1)) - 1ull);
+
+  for (;;) {
+    if (w)
+      return (wi << BITSET_WORD_SHIFT) + (BITSET_WORD_MASK - (usize)u64_clz(w));
+    if (!wi) break;
+    w = b[--wi];
+  }
+
+  return SIZE_MAX;
+}
+
+#endif // DYLAN_BITSET_H
+