Change from unordered_set<tag> to int array in low-level select_* functions.

diff --git a/src/l2JIT.ml b/src/l2JIT.ml
index b656faf..95c9131 100644 (file)
--- a/src/l2JIT.ml
+++ b/src/l2JIT.ml
@@ -13,12 +13,12 @@ type jump =
   | NEXT_ELEMENT of StateSet.t
   | TAGGED_DESCENDANT of StateSet.t * Tag.t
   | TAGGED_FOLLOWING of StateSet.t * Tag.t
-  | SELECT_DESCENDANT of StateSet.t * Ptset.Int.t * Tree.unordered_set
-  | SELECT_FOLLOWING of StateSet.t * Ptset.Int.t * Tree.unordered_set
+  | SELECT_DESCENDANT of StateSet.t * Ptset.Int.t * Tree.tag_list
+  | SELECT_FOLLOWING of StateSet.t * Ptset.Int.t * Tree.tag_list
   | TAGGED_CHILD of StateSet.t * Tag.t
   | TAGGED_SIBLING of StateSet.t * Tag.t
-  | SELECT_CHILD of StateSet.t * Ptset.Int.t * Tree.unordered_set
-  | SELECT_SIBLING of StateSet.t * Ptset.Int.t * Tree.unordered_set
+  | SELECT_CHILD of StateSet.t * Ptset.Int.t * Tree.tag_list
+  | SELECT_SIBLING of StateSet.t * Ptset.Int.t * Tree.tag_list
   | TAGGED_SUBTREE of StateSet.t * Tag.t
   | ELEMENT_SUBTREE of StateSet.t
 
@@ -31,12 +31,12 @@ let _first_element s = FIRST_ELEMENT s
 let _next_element s = NEXT_ELEMENT s
 let _tagged_descendant s t = TAGGED_DESCENDANT(s,t)
 let _tagged_following s t = TAGGED_FOLLOWING(s,t)
-let _select_descendant s t = SELECT_DESCENDANT(s,t, Tree.unordered_set_of_set t)
-let _select_following s t = SELECT_FOLLOWING(s,t, Tree.unordered_set_of_set t)
+let _select_descendant s t = SELECT_DESCENDANT(s,t, Tree.tag_list_of_set t)
+let _select_following s t = SELECT_FOLLOWING(s,t, Tree.tag_list_of_set t)
 let _tagged_child s t = TAGGED_CHILD(s,t)
 let _tagged_following_sibling s t = TAGGED_SIBLING(s,t)
-let _select_child s t = SELECT_CHILD(s,t, Tree.unordered_set_of_set t)
-let _select_following_sibling s t = SELECT_SIBLING(s,t, Tree.unordered_set_of_set t)
+let _select_child s t = SELECT_CHILD(s,t, Tree.tag_list_of_set t)
+let _select_following_sibling s t = SELECT_SIBLING(s,t, Tree.tag_list_of_set t)
 let _tagged_subtree s t = TAGGED_SUBTREE (s, t)
 let _element_subtree s = ELEMENT_SUBTREE s
 
@@ -196,11 +196,12 @@ let compute_jump auto tree tag states dir =
     let jkind = Ata.top_down_approx auto states tree in
     let jump = translate_jump tree tag jkind dir states in
     LOG(__ "level2-jit" 2
-       "Computed jumps for %s %a %s: %a\n%!"
-         (Tag.to_string tag)
-         StateSet.print states
-         (if dir == DIR_LEFT then "left" else "right")
-         print_jump jump
+          "Computed jumps for %s %a %s, from %a : %a%!"
+          (Tag.to_string tag)
+          StateSet.print states
+          (if dir == DIR_LEFT then "left" else "right")
+          Ata.print_kind jkind
+          print_jump jump
     );
     jump
 

diff --git a/src/l2JIT.mli b/src/l2JIT.mli
index f269fc6..9d97d4a 100644 (file)
--- a/src/l2JIT.mli
+++ b/src/l2JIT.mli
@@ -6,12 +6,12 @@ type jump =
   | NEXT_ELEMENT of StateSet.t
   | TAGGED_DESCENDANT of StateSet.t * Tag.t
   | TAGGED_FOLLOWING of StateSet.t * Tag.t
-  | SELECT_DESCENDANT of StateSet.t * Ptset.Int.t * Tree.unordered_set
-  | SELECT_FOLLOWING of StateSet.t * Ptset.Int.t * Tree.unordered_set
+  | SELECT_DESCENDANT of StateSet.t * Ptset.Int.t * Tree.tag_list
+  | SELECT_FOLLOWING of StateSet.t * Ptset.Int.t * Tree.tag_list
   | TAGGED_CHILD of StateSet.t * Tag.t
   | TAGGED_SIBLING of StateSet.t * Tag.t
-  | SELECT_CHILD of StateSet.t * Ptset.Int.t * Tree.unordered_set
-  | SELECT_SIBLING of StateSet.t * Ptset.Int.t * Tree.unordered_set
+  | SELECT_CHILD of StateSet.t * Ptset.Int.t * Tree.tag_list
+  | SELECT_SIBLING of StateSet.t * Ptset.Int.t * Tree.tag_list
   | TAGGED_SUBTREE of StateSet.t * Tag.t
   | ELEMENT_SUBTREE of StateSet.t
 

diff --git a/src/tree.ml b/src/tree.ml
index 166eeea..fae8eba 100644 (file)
--- a/src/tree.ml
+++ b/src/tree.ml
@@ -212,26 +212,25 @@ external nullt : unit -> 'a Node.t = "caml_xml_tree_nullt"
 let nil : [`Tree ] Node.t = Node.nil
 let root : [`Tree ] Node.t = Node.null
 
-type unordered_set
+type tag_list
 
-external unordered_set_alloc : int -> unordered_set = "caml_unordered_set_alloc"
-external unordered_set_length : unordered_set -> int = "caml_unordered_set_length"
-external unordered_set_insert : unordered_set -> int -> unit = "caml_unordered_set_set" "noalloc"
+external tag_list_alloc : int -> tag_list = "caml_tag_list_alloc"
+external tag_list_set : tag_list -> int -> Tag.t -> unit = "caml_tag_list_set" "noalloc"
 
 module HPtset = Hashtbl.Make(Ptset.Int)
 
 let vector_htbl = HPtset.create MED_H_SIZE
 
-let unordered_set_of_set s =
+let tag_list_of_set s =
   try
     HPtset.find vector_htbl s
   with
-      Not_found ->
-       let v = unordered_set_alloc (Ptset.Int.cardinal s) in
-       let _ = Ptset.Int.iter (fun e -> unordered_set_insert v e) s in
-         HPtset.add vector_htbl s v; v
-
-let ptset_to_vector = unordered_set_of_set
+    Not_found ->
+      let v = tag_list_alloc (Ptset.Int.cardinal s + 1) in
+      let i = ref 0 in
+      let () = Ptset.Int.iter (fun e -> tag_list_set v !i e; incr i) s in
+      let () = tag_list_set v !i Tag.nullt in
+      HPtset.add vector_htbl s v; v
 
 (** tree interface *)
 
@@ -247,7 +246,7 @@ let first_element t n = tree_first_element t.doc n
 external tree_tagged_child : tree -> [`Tree] Node.t -> Tag.t -> [`Tree] Node.t = "caml_xml_tree_tagged_child" "noalloc"
 let tagged_child t n tag = tree_tagged_child t.doc n tag
 
-external tree_select_child : tree -> [`Tree ] Node.t -> unordered_set -> [`Tree] Node.t = "caml_xml_tree_select_child" "noalloc"
+external tree_select_child : tree -> [`Tree ] Node.t -> tag_list -> [`Tree] Node.t = "caml_xml_tree_select_child" "noalloc"
 let select_child t n tag_set = tree_select_child t.doc n tag_set
 
 external tree_last_child : tree -> [`Tree] Node.t -> [`Tree] Node.t = "caml_xml_tree_last_child" "noalloc"
@@ -265,7 +264,7 @@ external tree_tagged_sibling : tree -> [`Tree] Node.t -> Tag.t -> [`Tree] Node.t
 let tagged_sibling t n tag = tree_tagged_sibling t.doc n tag
 
 
-external tree_select_sibling : tree -> [`Tree ] Node.t -> unordered_set -> [`Tree] Node.t = "caml_xml_tree_select_sibling" "noalloc"
+external tree_select_sibling : tree -> [`Tree ] Node.t -> tag_list -> [`Tree] Node.t = "caml_xml_tree_select_sibling" "noalloc"
 let select_sibling t n tag_set = tree_select_sibling t.doc n tag_set
 
 external tree_prev_sibling : tree -> [`Tree] Node.t -> [`Tree] Node.t = "caml_xml_tree_prev_sibling" "noalloc"
@@ -279,13 +278,13 @@ let tagged_descendant t n tag = tree_tagged_descendant t.doc n tag
 external tree_tagged_next : tree -> [`Tree ] Node.t -> Tag.t -> [`Tree ] Node.t = "caml_xml_tree_tagged_next" "noalloc"
 let tagged_next t n tag = tree_tagged_next t.doc n tag
 
-external tree_select_descendant : tree -> [`Tree ] Node.t -> unordered_set -> [`Tree] Node.t = "caml_xml_tree_select_descendant" "noalloc"
+external tree_select_descendant : tree -> [`Tree ] Node.t -> tag_list -> [`Tree] Node.t = "caml_xml_tree_select_descendant" "noalloc"
 let select_descendant t n tag_set = tree_select_descendant t.doc n tag_set
 
 external tree_tagged_following_before : tree -> [`Tree ] Node.t -> Tag.t -> [`Tree ] Node.t -> [`Tree ] Node.t = "caml_xml_tree_tagged_following_before" "noalloc"
 let tagged_following_before t n tag ctx = tree_tagged_following_before t.doc n tag ctx
 
-external tree_select_following_before : tree -> [`Tree ] Node.t -> unordered_set -> [`Tree] Node.t -> [`Tree] Node.t = "caml_xml_tree_select_following_before" "noalloc"
+external tree_select_following_before : tree -> [`Tree ] Node.t -> tag_list -> [`Tree] Node.t -> [`Tree] Node.t = "caml_xml_tree_select_following_before" "noalloc"
 let select_following_before t n tag_set ctx = tree_select_following_before t.doc n tag_set ctx
 
 external tree_parent : tree -> [`Tree] Node.t -> [`Tree] Node.t = "caml_xml_tree_parent" "noalloc"

diff --git a/src/tree.mli b/src/tree.mli
index ee9a5f4..6640b27 100644 (file)
--- a/src/tree.mli
+++ b/src/tree.mli
@@ -15,28 +15,28 @@ val size : t -> int
 val is_root : node -> bool
 val is_nil : node -> bool
 
-type unordered_set
+type tag_list
 
-val unordered_set_of_set : Ptset.Int.t -> unordered_set
+val tag_list_of_set : Ptset.Int.t -> tag_list
 
 val first_child : t -> node -> node
 val first_element : t -> node -> node
 val tagged_child : t -> node -> Tag.t -> node
-val select_child : t -> node -> unordered_set -> node
+val select_child : t -> node -> tag_list -> node
 
 
 val next_sibling : t -> node -> node
 val prev_sibling : t -> node -> node
 val next_element : t -> node -> node
 val tagged_sibling : t -> node ->  Tag.t -> node
-val select_sibling : t -> node -> unordered_set -> node
+val select_sibling : t -> node -> tag_list -> node
 
 val tagged_descendant : t -> node -> Tag.t -> node
 val tagged_next : t -> node -> Tag.t -> node
-val select_descendant : t -> node -> unordered_set -> node
+val select_descendant : t -> node -> tag_list -> node
 
 val tagged_following_before : t -> node -> Tag.t -> node ->  node
-val select_following_before : t -> node -> unordered_set -> node -> node
+val select_following_before : t -> node -> tag_list -> node -> node
 
 val parent : t -> node -> node
 val is_first_child : t -> node -> bool

diff --git a/src/utils_stub.cpp b/src/utils_stub.cpp
index dc3688a..8ee3e0b 100644 (file)
--- a/src/utils_stub.cpp
+++ b/src/utils_stub.cpp
@@ -1,4 +1,4 @@
-#include "common_stub.hpp"
+#include "utils_stub.hpp"
 
 extern "C" value caml_clz(value i)
 {
@@ -9,3 +9,29 @@ extern "C" value caml_leading_bit(value i)
 {
   return Val_long( ( 1 << (sizeof(unsigned long)*8 - __builtin_clzl(Long_val(i)) - 1)));
 }
+
+xml_tree::tag_t*& TAGLIST(value x)
+{
+  return Obj_val<xml_tree::tag_t*>(x);
+}
+
+static void finalize_tag_list(value x)
+{
+  xml_tree::tag_t * t = TAGLIST(x);
+  delete [] t;
+}
+
+extern "C" value caml_tag_list_alloc(value length)
+{
+  CAMLparam1(length);
+  CAMLlocal1(tlist);
+  tlist = sxsi_alloc_custom<xml_tree::tag_t*>();
+  TAGLIST(tlist) = new xml_tree::tag_t[Int_val(length)];
+  CAMLreturn (tlist);
+}
+
+NoAlloc extern "C" value caml_tag_list_set(value tl, value i, value v)
+{
+  TAGLIST(tl)[Int_val(i)] = Int_val(v);
+  return Val_unit;
+}

diff --git a/src/xml-tree_stub.cpp b/src/xml-tree_stub.cpp
index 2551c66..47b6c63 100644 (file)
--- a/src/xml-tree_stub.cpp
+++ b/src/xml-tree_stub.cpp
@@ -1,6 +1,5 @@
-#include <unordered_set>
 #include "xml-tree.hpp"
-#include "common_stub.hpp"
+#include "utils_stub.hpp"
 #include <cstdio>
 
 using namespace SXSI;
@@ -20,32 +19,6 @@ static xml_tree::tag_t TAG(value i)
   return static_cast<xml_tree::tag_t>(Int_val(i));
 }
 
-static std::unordered_set<xml_tree::tag_t>*& HSET(value x)
-{
-  return Obj_val<std::unordered_set<xml_tree::tag_t>*>(x);
-}
-
-
-NoAlloc extern "C" value caml_unordered_set_length(value hset)
-{
-  return (Val_int((HSET(hset))->size()));
-}
-
-extern "C" value caml_unordered_set_alloc(value unit)
-{
-  CAMLparam1(unit);
-  CAMLlocal1(hset);
-  hset = sxsi_alloc_custom<std::unordered_set<xml_tree::tag_t>*>();
-  HSET(hset) = new std::unordered_set<xml_tree::tag_t>();
-  CAMLreturn (hset);
-}
-
-NoAlloc extern "C"  value caml_unordered_set_set(value set, value v)
-{
-  HSET(set)->insert(TAG(v));
-  return (Val_unit);
-}
-
 extern "C"  value caml_xml_tree_save(value tree, value fd, value prefix)
 {
   CAMLparam3(tree, fd, prefix);
@@ -219,7 +192,7 @@ caml_xml_tree_tagged_child(value tree, value node, value tag)
 NoAlloc extern "C" value
 caml_xml_tree_select_child(value tree, value node, value tags)
 {
-  return (Val_int(XMLTREE(tree)->select_child(TREENODE(node), HSET(tags))));
+  return (Val_int(XMLTREE(tree)->select_child(TREENODE(node), TAGLIST(tags))));
 }
 
 NoAlloc extern "C" value
@@ -233,7 +206,7 @@ NoAlloc extern "C" value
 caml_xml_tree_select_sibling(value tree, value node, value tags)
 {
   return (Val_int(XMLTREE(tree)->select_sibling(TREENODE(node),
-                                                HSET(tags))));
+                                                TAGLIST(tags))));
 }
 
 NoAlloc extern "C" value
@@ -254,7 +227,7 @@ NoAlloc extern "C" value
 caml_xml_tree_select_descendant(value tree, value node, value tags)
 {
   return (Val_int(XMLTREE(tree)->select_descendant(TREENODE(node),
-                                                   HSET(tags))));
+                                                   TAGLIST(tags))));
 }
 
 NoAlloc extern "C" value caml_xml_tree_tagged_following_before(value tree,
@@ -273,7 +246,7 @@ NoAlloc extern "C"  value caml_xml_tree_select_following_before(value tree,
                                                                 value closing)
 {
   return (Val_int(XMLTREE(tree)->select_following_before(TREENODE(node),
-                                                         HSET(tags),
+                                                         TAGLIST(tags),
                                                          TREENODE(closing))));
 }