summaryrefslogtreecommitdiff
path: root/lib/std/bitset.myr
diff options
context:
space:
mode:
Diffstat (limited to 'lib/std/bitset.myr')
-rw-r--r--lib/std/bitset.myr155
1 files changed, 155 insertions, 0 deletions
diff --git a/lib/std/bitset.myr b/lib/std/bitset.myr
new file mode 100644
index 0000000..7843c7d
--- /dev/null
+++ b/lib/std/bitset.myr
@@ -0,0 +1,155 @@
+use "alloc.use"
+use "die.use"
+use "extremum.use"
+use "mk.use"
+use "slcp.use"
+use "sldup.use"
+use "slfill.use"
+use "types.use"
+
+pkg std =
+ type bitset = struct
+ bits : size[:]
+ ;;
+
+ const mkbs : (-> bitset#)
+ const bsdup : (bs : bitset# -> bitset#)
+ const bsfree : (bs : bitset# -> void)
+
+ const bsmax : (a : bitset# -> size)
+
+ generic bsput : (bs : bitset#, v : @a::(integral,numeric) -> void)
+ generic bsdel : (bs : bitset#, v : @a::(integral,numeric) -> void)
+ generic bshas : (bs : bitset#, v : @a::(integral,numeric) -> bool)
+
+ const bsdiff : (a : bitset#, b : bitset# -> void)
+ const bsintersect : (a : bitset#, b : bitset# -> void)
+ const bsunion : (a : bitset#, b : bitset# -> void)
+ const bseq : (a : bitset#, b : bitset# -> bool)
+ const bsissubset : (a : bitset#, b : bitset# -> bool)
+
+
+ const bsclear : (bs : bitset# -> bitset#)
+;;
+
+const mkbs = {
+ -> zalloc()
+}
+
+const bsdup = {bs
+ -> mk([.bits=sldup(bs.bits)])
+}
+
+const bsfree = {bs
+ slfree(bs.bits)
+ free(bs)
+}
+
+const bsclear = {bs
+ slfill(bs.bits, 0)
+ -> bs
+}
+
+const bsmax = {bs
+ -> bs.bits.len * sizeof(size) * 8
+}
+
+generic bsput = {bs, v
+ var idx
+ var off
+
+ idx = (v castto(size)) / (8*sizeof(size))
+ off = (v castto(size)) % (8*sizeof(size))
+ ensurelen(bs, idx)
+ bs.bits[idx] |= (1 << off)
+}
+
+generic bsdel = {bs, v
+ var idx
+ var off
+
+ idx = (v castto(size)) / (8*sizeof(size))
+ off = (v castto(size)) % (8*sizeof(size))
+ if idx >= bs.bits.len
+ ->
+ ;;
+ bs.bits[idx] &= ~(1 << off)
+}
+
+generic bshas = {bs, v
+ var idx
+ var off
+
+ idx = (v castto(size)) / (8*sizeof(size))
+ off = (v castto(size)) % (8*sizeof(size))
+ if idx >= bs.bits.len
+ -> false
+ ;;
+ -> (bs.bits[idx] & (1 << off)) != 0
+}
+
+const bsunion = {a, b
+ var i
+
+ eqsz(a, b)
+ for i = 0; i < b.bits.len; i++
+ a.bits[i] |= b.bits[i]
+ ;;
+}
+
+const bsintersect = {a, b
+ var i, n
+
+ n = min(a.bits.len, b.bits.len)
+ for i = 0; i < n; i++
+ a.bits[i] &= b.bits[i]
+ ;;
+}
+
+const bsdiff = {a, b
+ var i, n
+
+ n = min(b.bits.len, a.bits.len)
+ for i = 0; i < n; i++
+ a.bits[i] &= ~b.bits[i]
+ ;;
+}
+
+const bsissubset = {a, b
+ var i
+
+ eqsz(a, b);
+ for i = 0; i < a.bits.len; i++
+ if (b.bits[i] & a.bits[i]) != b.bits[i]
+ -> false
+ ;;
+ ;;
+ -> true
+}
+
+const bseq = {a, b
+ var i
+
+ eqsz(a, b)
+ for i = 0; i < a.bits.len; i++
+ if a.bits[i] != b.bits[i]
+ -> false
+ ;;
+ ;;
+ -> true
+}
+
+const ensurelen = {bs, len
+ if bs.bits.len <= len
+ bs.bits = slzgrow(bs.bits, len + 1)
+ ;;
+}
+
+const eqsz = {a, b
+ var sz
+
+ sz = max(a.bits.len, b.bits.len)
+ ensurelen(a, sz)
+ ensurelen(b, sz)
+}
+