From: Kim Nguyễn Date: Wed, 18 Apr 2012 11:47:13 +0000 (+0200) Subject: Change from unordered_set to int array in low-level select_* functions. X-Git-Url: http://git.nguyen.vg/gitweb/?p=SXSI%2Fxpathcomp.git;a=commitdiff_plain;h=2cb4fceda48a09fc1acd65c54372651b14e0f404 Change from unordered_set to int array in low-level select_* functions. --- diff --git a/src/l2JIT.ml b/src/l2JIT.ml index b656faf..95c9131 100644 --- 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 --- 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 --- 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 --- 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 --- 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(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(); + 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 --- a/src/xml-tree_stub.cpp +++ b/src/xml-tree_stub.cpp @@ -1,6 +1,5 @@ -#include #include "xml-tree.hpp" -#include "common_stub.hpp" +#include "utils_stub.hpp" #include using namespace SXSI; @@ -20,32 +19,6 @@ static xml_tree::tag_t TAG(value i) return static_cast(Int_val(i)); } -static std::unordered_set*& HSET(value x) -{ - return Obj_val*>(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*>(); - HSET(hset) = new std::unordered_set(); - 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)))); }