Une version marche bien avec bitvector

diff --git a/src/query_tree.ml b/src/query_tree.ml
index 679d992..d9e6ada 100644 (file)
--- a/src/query_tree.ml
+++ b/src/query_tree.ml
@@ -1,6 +1,7 @@
 open Table
 
-let compteur = ref 0
+let query_tree_size = ref 0
+
 let table_qtree = QTreeHash.create 97
                        
 
@@ -147,17 +148,13 @@ let rec eval_qtree tree start q =
        match q.desc with
          | Start -> start
          | Dom -> Bitvector.create ~init:true (Naive_tree.size tree)
-           (*let v = Bitvector.create (Naive_tree.size tree) in
-           for i=0 to (Bitvector.length v)-1 do
-             Bitvector.set v i true
-           done;
-           v*)
          | Tag (t,k) -> element_by_tag tree t k                     
          | Axis (a,q1) -> let v = eval_qtree tree start q1 in
                           eval_axis tree v a                      
          | Binop (op,q1,q2)-> begin
            let v1 = eval_qtree tree start q1 in
            let v2 = eval_qtree tree start q2 in
+           Table.node_compteur := !Table.node_compteur + 2*Bitvector.length v1; 
            match op with         
              | Union -> Bitvector.union v1 v2      
              | Inter -> Bitvector.inter v1 v2
@@ -165,9 +162,9 @@ let rec eval_qtree tree start q =
          end
        in
        QTreeHash.add table_qtree q res;
-       compteur := !compteur + Bitvector.length res; (*????8*)
        res
     end
   in
  (* debug tree q resultat;*)
+  incr query_tree_size;
   resultat

diff --git a/src/query_tree.mli b/src/query_tree.mli
index 7335e52..130d7cb 100644 (file)
--- a/src/query_tree.mli
+++ b/src/query_tree.mli
@@ -1,5 +1,5 @@
-val compteur : int ref
-(**the counter of nodes*)
+val query_tree_size : int ref
+(**the size of query_tree*)
 
 val element_by_tag : Naive_tree.t -> QNameSet.t -> Tree.NodeKind.t -> Bitvector.t
 (** [element_by_tag t tag] returns all the nodes whose tag equal to [tag] in the tree [t]. *)

diff --git a/src/table.ml b/src/table.ml
index c40e93b..1c10693 100644 (file)
--- a/src/table.ml
+++ b/src/table.ml
@@ -1,4 +1,6 @@
 
+let node_compteur = ref 0
+
 type query_tree_desc = Binop of op * query_tree * query_tree
                       | Axis of Xpath.Ast.axis * query_tree
                       | Start 
@@ -150,19 +152,20 @@ let get_descendant tree c v =
     else let n1 = Naive_tree.first_child tree n in
         let j = Naive_tree.preorder tree n in
         Bitvector.set acc j true;
+        incr node_compteur;
         let acc1 = aux n1 acc in
         let n2 = Naive_tree.next_sibling tree n in
         aux n2 acc1
   in       
   let v0 = Bitvector.create (Naive_tree.size tree) in
- (* let v = bitvector_of_nodes tree ln in*)
   if c then begin
     for i = 0 to (Bitvector.length v)-1 do
       if Bitvector.get v i then
        let n = Naive_tree.by_preorder tree i in
        let n1 = Naive_tree.first_child tree n in
        let _ = aux n1 v0 in 
-       Bitvector.set v0 i true
+       Bitvector.set v0 i true;
+       incr node_compteur
     done; end
   else
     for i = 0 to (Bitvector.length v)-1 do
@@ -179,10 +182,10 @@ let get_child tree v =
     else
       let n1 = Naive_tree.next_sibling tree n in
       Bitvector.set acc (Naive_tree.preorder tree n) true;
+      incr node_compteur;
       aux n1 acc
   in
   let v0 = Bitvector.create (Naive_tree.size tree) in
-  (*let v = bitvector_of_nodes tree ln in*)
   for i = 0 to (Bitvector.length v)-1 do
     if Bitvector.get v i then
       let n = Naive_tree.by_preorder tree i in
@@ -198,10 +201,10 @@ let get_followingSibling tree v =
     if n1 == Naive_tree.nil then acc
     else begin
       Bitvector.set acc (Naive_tree.preorder tree n1) true;
+      incr node_compteur;
       aux n1 acc end
   in
   let v0 = Bitvector.create (Naive_tree.size tree) in
- (* let v = bitvector_of_nodes tree ln in*)
   for i = 0 to (Bitvector.length v)-1 do
     if Bitvector.get v i then
       let n = Naive_tree.by_preorder tree i in
@@ -215,27 +218,27 @@ let rec get_firstBling tree n pred =
     
 let get_parent tree v = 
   let v0 = Bitvector.create (Naive_tree.size tree) in
- (* let v = bitvector_of_nodes tree ln in*)
   for i = 0 to (Bitvector.length v)-1 do
     if Bitvector.get v i then
       let n = Naive_tree.by_preorder tree i in
       let n1 = get_firstBling tree n Naive_tree.nil in
       let n2 = Naive_tree.parent_of_first tree n1 in
       if n2 != Naive_tree.nil then begin let j = Naive_tree.preorder tree n2 in
-                                        Bitvector.set v0 j true
+                                        Bitvector.set v0 j true;
+                                        incr node_compteur
       end
   done;
   v0
 
 let get_ancestor tree b v =
   let v0 = Bitvector.create (Naive_tree.size tree) in
- (* let v = bitvector_of_nodes tree ln in  *)
   if b then 
     begin
       for i = (Bitvector.length v)-1 downto 0 do
        if Bitvector.get v i then 
          begin
            Bitvector.set v0 i true;
+           incr node_compteur;
            let n = Naive_tree.by_preorder tree i in
            let n0 = ref n in
            while !n0 != Naive_tree.nil do
@@ -245,6 +248,7 @@ let get_ancestor tree b v =
              if n2 != Naive_tree.nil then begin let j = Naive_tree.preorder tree n2 in
                                                 Bitvector.set v0 j true;
                                                 Bitvector.set v j true;
+                                                node_compteur := !node_compteur + 2; 
              end
            done;
          end
@@ -263,6 +267,7 @@ let get_ancestor tree b v =
            if n2 != Naive_tree.nil then begin let j = Naive_tree.preorder tree n2 in
                                               Bitvector.set v0 j true;
                                               Bitvector.set v j true;
+                                              node_compteur := !node_compteur + 2; 
            end
          done;
        end
@@ -275,10 +280,10 @@ let get_preSibling tree v =
     if n1 == Naive_tree.nil then acc
     else begin
       Bitvector.set acc (Naive_tree.preorder tree n1) true;
+      incr node_compteur;
       aux n1 acc end
   in
   let v0 = Bitvector.create (Naive_tree.size tree) in
- (* let v = bitvector_of_nodes tree ln in*)
   for i = 0 to (Bitvector.length v)-1 do
     if Bitvector.get v i then
       let n = Naive_tree.by_preorder tree i in

diff --git a/src/table_driver.ml b/src/table_driver.ml
index e961abb..07c6523 100644 (file)
--- a/src/table_driver.ml
+++ b/src/table_driver.ml
@@ -5,7 +5,7 @@ open Query_tree
 let parse_xpath p =
   Xpath.Parser.parse (Ulexing.from_utf8_string p)
 
-let display = ref false
+let display = ref true
 
 let main () = 
   let () = Table_options.parse () in
@@ -49,7 +49,7 @@ let main () =
   let t2 = Unix.gettimeofday () in
   let t = (t2 -. t1) *. 1000. in
   let _ = if !Table_options.count then 
-       Format.fprintf Format.std_formatter "there are %i nodes\nit takes %fms\n" !Query_tree.compteur t;
+       Format.fprintf Format.std_formatter "there are %i nodes\nquery_tree size : %i\nit takes %fms\n" !Table.node_compteur !Query_tree.query_tree_size t;
   in
   exit 0
 

diff --git a/tests/exemple.xml b/tests/exemple.xml
index d599d06..da48927 100644 (file)
--- a/tests/exemple.xml
+++ b/tests/exemple.xml
@@ -1,12 +1,21 @@
 <regions>
        
-<asia><country lang="Standard Chinese">China</country>
+<asia><country lang="Standard Chinese">
+       <name>China</name>
           <capital>Beijing</capital>
+       </country>
+       
 </asia>
 
-<asia><country lang="Japanese">Japan</country>
+<europe><country lang="Japanese">
+               <name>Japan</country>
           <capital>Tokyo</capital>
-</asia>
+</europe>
+<america><country lang="Japanese">Japan</country>
+          <capital>Tokyo</capital>
+</america>
+
+
 
 </regions>
 

diff --git a/tests/single_test.sh b/tests/single_test.sh
index 3c6d2b3..902fec5 100755 (executable)
--- a/tests/single_test.sh
+++ b/tests/single_test.sh
@@ -1,18 +1,12 @@
 #!/bin/sh
 
-INPUT=tests/xmark_0.00.xml
+INPUT=tests/xmark_0.05.xml
 QUERIES="$INPUT".queries
 
-
-
- perl -MTime::HiRes -e 'print Time::HiRes::time(),"\n"';
 cat "$QUERIES" | while read N Q;
 do
  echo Query "$N : $Q"
- src/tatoo.native  -d "$INPUT" "$Q" > /tmp/huibo"$N".xml
+ src/tatoo.native -s -d "$INPUT" "$Q" -o /dev/null > /tmp/kim.xml
 
 
 done
-
- perl -MTime::HiRes -e 'print Time::HiRes::time(),"\n"';
-