src/cache.ml

   1 INCLUDE "trace.ml"
   2
   3 let realloc l old_size new_size dummy =
   4   let l' = Array.create new_size dummy in
   5   Array.blit l 0 l' 0 (min old_size new_size);
   6   l'
   7
   8 module Lvl1 =
   9 struct
  10
  11   type 'a t = { mutable line : 'a array;
  12                 dummy : 'a }
  13
  14   let create n a = { line = Array.create n a;
  15                      dummy = a }
  16
  17   let find c i =
  18     let line = c.line in
  19     let len = Array.length line in
  20     if i >= len then c.dummy else line.(i)
  21
  22   let add c i v =
  23     let line = c.line in
  24     let len = Array.length line in
  25     if i >= len then c.line <- realloc line len (i*2+1) c.dummy;
  26     c.line.(i) <- v
  27
  28   let dummy c = c.dummy
  29
  30   let to_array c = c.line
  31 end
  32
  33 include Lvl1
  34
  35 module Lvl2 =
  36 struct
  37   type 'a t = { mutable line : 'a array array;
  38                 dummy : 'a;
  39                 l1_size : int;
  40                 dummy_line1 : 'a array
  41               }
  42
  43   let dummy_line = [| |]
  44
  45   let create ?(l1_size=512) n a =
  46     let dummy_line1 = Array.create l1_size a in
  47     { line = Array.create n dummy_line1;
  48       dummy = a;
  49       l1_size = l1_size;
  50       dummy_line1 = dummy_line1;
  51     }
  52
  53   let find c i j = c.line.(i).(j)
  54
  55   let add c i j v =
  56     let line = c.line in
  57     let len = Array.length line in
  58     if i >= len then
  59       c.line <- realloc line len (i*2 + 1) c.dummy_line1;
  60     let line = c.line.(i) in
  61     let line =
  62       if line == c.dummy_line1 then
  63         let nline = Array.copy line in
  64         c.line.(i) <- nline;
  65         nline
  66       else line
  67     in
  68     line.(j) <- v
  69
  70   let dummy c = c.dummy
  71   let to_array c = c.line
  72   let dummy_line c = c.dummy_line1
  73 end
  74
  75 module Lvl3 =
  76 struct
  77   type 'a t =
  78       { mutable line : 'a array array array;
  79         dummy : 'a;
  80         l1_size : int;
  81         l2_size : int;
  82         dummy_line1 : 'a array array;
  83         dummy_line2 : 'a array }
  84
  85   let dummy_line2 = [| |]
  86   let dummy_line1 = [| |]
  87
  88   let create ?(l1_size=512) ?(l2_size=512) n a =
  89     let dummy_line2 = Array.create l2_size a in
  90     let dummy_line1 = Array.create l1_size dummy_line2 in
  91     { line = Array.create n dummy_line1;
  92       dummy = a;
  93       l1_size = l1_size;
  94       l2_size = l2_size;
  95       dummy_line1 = dummy_line1;
  96       dummy_line2 = dummy_line2
  97     }
  98   let find t k j i = t.line.(i).(j).(k)
  99
 100
 101   let add t k j i v =
 102     let line = t.line in
 103     let line1 =
 104       let l1 = line.(i) in
 105       if l1 == t.dummy_line1 then
 106         let l1' = Array.copy l1 in
 107         line.(i) <- l1'; l1'
 108       else l1
 109     in
 110     let line2 =
 111       let l2 = line1.(j) in
 112       if l2 == t.dummy_line2 then
 113         let l2' = Array.copy l2 in
 114         line1.(j) <- l2'; l2'
 115       else l2
 116     in
 117     line2.(k) <- v
 118
 119   let dummy a = a.dummy
 120   let to_array a = a.line
 121 end