Add a bitmap to keep track of whether a subtree needs to be

[tatoo.git] / src / bitvector.ml

diff --git a/src/bitvector.ml b/src/bitvector.ml
new file mode 100644 (file)
index 0000000..a44a58e
--- /dev/null
+++ b/src/bitvector.ml
@@ -0,0 +1,36 @@
+type t = { length : int;
+           bits : string; }
+
+let create ?(init=false) size =
+  let i = if init then '\xff' else '\x00' in
+  { length = size;
+    bits = String.make (1 + size / 8) i
+  }
+
+let length v = v.length
+
+let unsafe_get v n =
+  let i = n / 8
+  and j = n mod 8 in
+  (((Char.code (String.unsafe_get v.bits i)) lsr j) land 1) == 1
+
+
+let unsafe_set v n (b:bool) =
+  let x : int = Obj.magic b in
+  let i = n / 8
+  and j = n mod 8 in
+  let m = 1 lsl j in
+  let w = Char.code (String.unsafe_get v.bits i) in
+  let w = (w land lnot m) lor (~-x land m) in
+  String.unsafe_set v.bits i (Char.unsafe_chr (w land 0xff))
+;;
+
+let get v n =
+  if n < 0 || n >= v.length then failwith "Bitvector.get"
+  else unsafe_get v n
+;;
+
+let set v n b =
+  if n < 0 || n >= v.length then failwith "Bitvector.set"
+  else unsafe_set v n b
+;;