From 0c2338bfcdae0df1c68112a10247dc4e68a483ff Mon Sep 17 00:00:00 2001
From: kim <kim@3cdefd35-fc62-479d-8e8d-bae585ffb9ca>
Date: Mon, 7 Feb 2011 13:23:30 +0000
Subject: [PATCH] cherry pick from local- branch

git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/xpathcomp@949 3cdefd35-fc62-479d-8e8d-bae585ffb9ca
---
 OCamlDriver.cpp | 75 ++++++++++++++++++++++++++++++++++++++++---------
 tree.ml         |  9 +++++-
 tree.mli        |  2 ++
 3 files changed, 71 insertions(+), 15 deletions(-)

diff --git a/OCamlDriver.cpp b/OCamlDriver.cpp
index 3994970..a5e47f8 100644
--- a/OCamlDriver.cpp
+++ b/OCamlDriver.cpp
@@ -774,8 +774,10 @@ int iterjump(XMLTree* tree, treeNode node, TagType tag, treeNode anc){
   if (node == NULLT)
     return 0;
   else {
-    return /*1+iterjump(tree,tree->TaggedDescendant(node,tag),tag,node)
-	     +*/ iterjump(tree,tree->TaggedFollowingBelow(node,tag,anc),tag,anc);
+    return 
+      1
+      + iterjump(tree,tree->TaggedDescendant(node,tag),tag,node)
+      + iterjump(tree,tree->TaggedFollowingBelow(node,tag,anc),tag,anc);
   };
 }
 
@@ -792,8 +794,19 @@ int iterfcns(XMLTree* tree, treeNode node){
     return 0;
   else {
     int tmp = 1;
-    tmp += iterfcns(tree,tree->FirstElement(node));
-    tmp += iterfcns(tree,tree->NextElement(node));
+    tmp += iterfcns(tree,tree->FirstChild(node));
+    tmp += iterfcns(tree,tree->NextSibling(node));
+    return tmp;    
+  };
+}
+
+int iterfene(XMLTree* tree, treeNode node){
+  if (node == NULLT)
+    return 0;
+  else {
+    int tmp = 1;
+    tmp += iterfene(tree,tree->FirstElement(node));
+    tmp += iterfene(tree,tree->NextElement(node));
     return tmp;    
   };
 }
@@ -804,6 +817,12 @@ extern "C" value caml_benchmark_fcns(value tree){
 		    
 }
 
+extern "C" value caml_benchmark_fene(value tree){
+  int i = iterfene(XMLTREE(tree),0);
+  return Val_int(i);
+		    
+}
+
 int iterlcps(XMLTree* tree, treeNode node){
   if (node == NULLT)
     return 0;
@@ -815,6 +834,33 @@ int iterlcps(XMLTree* tree, treeNode node){
   };
 }
 
+int fulliterative(XMLTree* tree){
+  treeNode current = tree->Root();
+  treeNode next = NULLT;
+  int count = 1; //the root
+
+  do {
+  
+
+    while ((next = tree->FirstChild(current)) != NULLT) {
+      current = next;
+      count++;
+    };
+
+    while ( (next = tree->NextSibling(current)) == NULLT){
+      current = tree->Parent(current);
+      if (current == NULLT) return count;
+    }
+    current = next;
+    count++;
+  } while (true);
+
+}
+
+extern "C" value caml_benchmark_iter(value tree){
+  return Val_int(fulliterative(XMLTREE(tree)));
+}
+
 extern "C" value caml_benchmark_lcps(value tree){  
   iterlcps(XMLTREE(tree),0);
   return Val_unit;
@@ -847,14 +893,17 @@ extern "C" {
     return;
   }
 
-  dummy_node * create_tree(XMLTree* tree, treeNode i){
+  dummy_node * create_tree(XMLTree* tree, treeNode i, int mode){
     if (i == NULLT)
        return NULL;
     else {
       dummy_node * f, *n, *r;
-      f = create_tree(tree,tree->FirstChild(i));
-      n = create_tree(tree,tree->NextSibling(i));
-      r = new_dummy_node();
+      //mode = i % 3;
+      if (mode == 0) r = new_dummy_node();
+      f = create_tree(tree,tree->FirstChild(i), mode);
+      if (mode == 1) r = new_dummy_node();
+      n = create_tree(tree,tree->NextSibling(i), mode);
+      if (mode == 2) r = new_dummy_node();
       r->first = f;
       r->next = n;
       return r;
@@ -864,14 +913,12 @@ extern "C" {
   int iter_tree(dummy_node * n){
     if (n == NULL)
       return 0;
-    else {
-      return (1+ iter_tree(n->next)+ iter_tree(n->first) );
-    };
+    else
+      return 1 + iter_tree (n->first) + iter_tree (n->next);
   }
-
 }
-extern "C" value caml_build_pointers(value tree){
-  return ((value) create_tree(XMLTREE(Field(tree,0)),0));
+extern "C" value caml_build_pointers(value tree, value mode){
+  return ((value) create_tree(XMLTREE(Field(tree,0)),0, Int_val(mode)));
 }
 
 extern "C" value caml_iter_pointers (value node){
diff --git a/tree.ml b/tree.ml
index 7ea6f03..5327aa0 100644
--- a/tree.ml
+++ b/tree.ml
@@ -133,9 +133,15 @@ external benchmark_jump : tree -> Tag.t -> unit = "caml_benchmark_jump" "noalloc
 let benchmark_jump t s = benchmark_jump t.doc s
 
 external benchmark_fcns : tree -> int = "caml_benchmark_fcns" "noalloc"
+external benchmark_fene : tree -> int = "caml_benchmark_fene" "noalloc"
+external benchmark_iter : tree -> int = "caml_benchmark_iter" "noalloc"
 
 let benchmark_fcns t = benchmark_fcns t.doc
 
+let benchmark_fene t = benchmark_fene t.doc
+
+let benchmark_iter t = benchmark_iter t.doc
+
 external benchmark_lcps : tree -> unit = "caml_benchmark_lcps" "noalloc"
 
 let benchmark_lcps t = benchmark_lcps t.doc
@@ -491,7 +497,7 @@ let parent t n = tree_parent t.doc n
 
 let first_child t = let doc = t.doc in ();fun n -> tree_first_child doc n
 let first_element t = let doc = t.doc in (); fun n -> tree_first_element doc n
-
+let first_element t n = tree_first_element t.doc n
 (* these function will be called in two times: first partial application
    on the tag, then application of the tag and the tree, then application of
    the other arguments. We use the trick to let the compiler optimize application
@@ -505,6 +511,7 @@ let select_child t = fun ts ->
 
 let next_sibling t = let doc = t.doc in (); fun n ->  tree_next_sibling doc n
 let next_element t = let doc = t.doc in (); fun n ->  tree_next_element doc n
+let next_element t n = tree_next_element t.doc n
 
 let tagged_following_sibling t tag = (); fun n -> tree_tagged_following_sibling t.doc n tag
 
diff --git a/tree.mli b/tree.mli
index 24b8256..539103c 100644
--- a/tree.mli
+++ b/tree.mli
@@ -89,7 +89,9 @@ val is_open : t -> [`Tree] node -> bool
 
 val benchmark_jump : t -> Tag.t -> unit
 val benchmark_fcns : t -> int
+val benchmark_fene : t -> int
 val benchmark_lcps : t -> unit
+val benchmark_iter : t -> int
 val stats : t -> unit
 
 val test_suffix : t -> string -> int
-- 
2.17.1