summaryrefslogtreecommitdiff
path: root/libstd/bitset.myr
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2014-01-27 11:17:08 -0500
committerOri Bernstein <ori@eigenstate.org>2014-01-27 11:17:08 -0500
commit2f39b00d65470909bee4e94ac58fe2a2be5a7050 (patch)
tree86b33b58504a5b0c3ea34114ebd2b7d97570eb6d /libstd/bitset.myr
parentf432ef92f3d31e3b6d1104528753aef26aebc848 (diff)
downloadmc-2f39b00d65470909bee4e94ac58fe2a2be5a7050.tar.gz
Add bitset implementation.
Ported from libds.
Diffstat (limited to 'libstd/bitset.myr')
-rw-r--r--libstd/bitset.myr138
1 files changed, 138 insertions, 0 deletions
diff --git a/libstd/bitset.myr b/libstd/bitset.myr
new file mode 100644
index 0000000..92ad648
--- /dev/null
+++ b/libstd/bitset.myr
@@ -0,0 +1,138 @@
+use "alloc.use"
+use "mk.use"
+use "types.use"
+use "extremum.use"
+
+pkg std =
+ type bitset = struct
+ bits : size[:]
+ ;;
+
+ const mkbitset : (-> bitset#)
+ const bsdup : (bs : bitset# -> bitset#)
+ const bsfree : (bs : bitset# -> void)
+
+ generic bsput : (bs : bitset#, v : @a::(tcint,tctest,tcnum) -> void)
+ generic bsdel : (bs : bitset#, v : @a::(tcint,tctest,tcnum) -> void)
+ generic bshas : (bs : bitset#, v : @a::(tcint,tctest,tcnum) -> 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 bsissub : (a : bitset#, b : bitset# -> bool)
+
+ const bsclear : (bs : bitset# -> bitset#)
+ const bscount : (bs : bitset# -> bitset#)
+ const bsiter : (bs : bitset# -> bitset#)
+;;
+
+const Szbits = 8*sizeof(size)
+
+const mkbitset = {
+ -> zalloc()
+}
+
+const bsdup = {bs
+ -> mk([.bits=bs.bits])
+}
+
+const bsfree = {bs
+ slfree(bs.bits)
+ free(bs)
+}
+
+generic bsput = {bs, v
+ var idx
+ var off
+
+ idx = (v castto(size)) / Szbits
+ off = (v castto(size)) % Szbits
+ ensurespace(bs, idx)
+ bs.bits[idx] |= (1 << off)
+}
+
+generic bsdel = {bs, v
+ var idx
+ var off
+
+ idx = (v castto(size)) / Szbits
+ off = (v castto(size)) % Szbits
+ ensurespace(bs, idx)
+ bs.bits[idx] &= ~(1 << off)
+}
+
+generic bshas = {bs, v
+ var idx
+ var off
+
+ idx = (v castto(size)) / Szbits
+ off = (v castto(size)) % Szbits
+ ensurespace(bs, idx)
+ -> (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
+
+ ensurespace(b, a.bits.len)
+ for i = 0; i < a.bits.len; 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 ensurespace = {bs, v
+ if bs.bits.len*Szbits <= v
+ bs.bits = slzgrow(bs.bits, v + 1)
+ ;;
+}
+
+const eqsz = {a, b
+ var sz
+
+ sz = max(a.bits.len, b.bits.len)
+ ensurespace(a, sz)
+ ensurespace(b, sz)
+}