X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=src%2Fcache.ml;fp=src%2Fcache.ml;h=f4561af0badd2ae383e05c372f0ab43efd1b6356;hb=4b52da1a20a4fe031930bb96d2ca46bec06dc529;hp=0000000000000000000000000000000000000000;hpb=a223af3254fb51c279cfbccdc18c59484fdca74e;p=SXSI%2Fxpathcomp.git

diff --git a/src/cache.ml b/src/cache.ml
new file mode 100644
index 0000000..f4561af
--- /dev/null
+++ b/src/cache.ml
@@ -0,0 +1,125 @@
+let realloc l old_size new_size dummy =
+  let l' = Array.create new_size dummy in
+    Array.blit l 0 l' 0 (min old_size new_size);
+    l'
+
+module Lvl1 =
+  struct
+
+    type 'a t = { mutable line : 'a array;
+		 dummy : 'a }
+    let create n a = { line = Array.create n a;
+		       dummy = a }
+
+    let find c i =
+      let line = c.line in
+      let len = Array.length line in
+	if i >= len then c.dummy else line.(i)
+
+
+    let add c i v =
+      let line = c.line in
+      let len = Array.length line in
+	if i >= len then c.line <- realloc line len (i*2+1) c.dummy;
+	c.line.(i) <- v
+
+    let dummy c = c.dummy
+
+    let to_array c = c.line
+  end
+
+include Lvl1
+
+module Lvl2 =
+  struct
+    type 'a t = { mutable line : 'a array array;
+		 dummy : 'a;
+		 l1_size : int;
+		 dummy_line1 : 'a array
+	       }
+
+    let dummy_line = [| |]
+
+    let create ?(l1_size=512) n a =
+      let dummy_line1 = Array.create l1_size a in
+      { line = Array.create n dummy_line1;
+	dummy = a;
+	l1_size = l1_size;
+	dummy_line1 = dummy_line1;
+      }
+    let find c i j = c.line.(i).(j)
+    let add c i j v =
+      let line = c.line in
+      let len = Array.length line in
+      if i >= len then c.line <- realloc line len (i*2 + 1) c.dummy_line1;
+      let line = c.line.(i) in
+      let line =
+	if line == c.dummy_line1 then
+	    let nline = Array.copy line (*Array.create c.l1_size c.dummy*) in
+	      c.line.(i) <- nline;
+	      nline
+	  else line
+	in
+	  line.(j) <- v
+
+    let dummy c = c.dummy
+    let to_array c = c.line
+    let dummy_line c = c.dummy_line1
+  end
+
+module Lvl3 =
+  struct
+    type 'a t = { mutable line : 'a array array array;
+		 dummy : 'a;
+		 l1_size : int;
+		 l2_size : int;
+		 dummy_line1 : 'a array array;
+		 dummy_line2 : 'a array
+	       }
+    let dummy_line2 = [| |]
+    let dummy_line1 = [| |]
+
+
+
+    let create ?(l1_size=512) ?(l2_size=512) n a =
+      let dummy_line2 = Array.create l2_size a in
+      let dummy_line1 = Array.create l1_size dummy_line2 in
+      { line = Array.create n dummy_line1;
+	dummy = a;
+	l1_size = l1_size;
+	l2_size = l2_size;
+	dummy_line1 = dummy_line1;
+	dummy_line2 = dummy_line2
+      }
+    let find t i j k = t.line.(i).(j).(k)
+(*
+    let find t i j k =
+      let line = t.line in
+      let line1 = line.(i) in
+	if line1 == dummy_line1 then t.dummy else
+	  let line2 = line1.(j) in
+	    if line2 == dummy_line2 then t.dummy else line2.(k)
+*)
+
+    let add t i j k v =
+      let line = t.line in
+      let line1 =
+	let l1 = line.(i) in
+	  if l1 == t.dummy_line1 then
+	    let l1' = Array.copy l1 in
+	      line.(i) <- l1'; l1'
+	  else l1
+      in
+      let line2 =
+	let l2 = line1.(j) in
+	  if l2 == t.dummy_line2 then
+	    let l2' = Array.copy l2 in
+	      line1.(j) <- l2'; l2'
+	  else l2
+      in
+	line2.(k) <- v
+
+
+    let dummy a = a.dummy
+    let to_array a = a.line
+  end