-
-let rec dump fmt t =
- incr tabs;
- let _ = match t with
- | Nil -> prtabs fmt; Format.fprintf fmt "#"
- | String s -> prtabs fmt; Format.fprintf fmt "(String %s)" s
- | Node(id,t,l,r,_) ->
- prtabs fmt;
- Format.fprintf fmt " (tag='";
- Tag.print fmt t;
- Format.fprintf fmt "', id='%i')\n" id;
- prtabs fmt;
- dump fmt l;
- Format.fprintf fmt "\n";
- prtabs fmt;
- dump fmt r;
- Format.fprintf fmt "\n";
- prtabs fmt;prtabs fmt;
- Format.fprintf fmt "(id='%i'end )\n" id
- in decr tabs
-
-
-let dump fmt t =
- tabs:=0;
- dump fmt t;
- tabs:=0
-
-let id = function Node(i,_,_,_,_) -> i
- | _ -> failwith "id"
-
-let tag = function Node(_,t,_,_,_) -> t
- | _ -> failwith "tag"
-
-let left = function Node(_,_,l,_,_) -> l
- | _ -> failwith "left"
-
-let right = function Node(_,_,_,r,_) -> r
- | _ -> failwith "right"
-
-let first_child = left
-let next_sibling = right
-
-let is_root = function Node (_,_,_,_,{contents=Nil}) -> true | _ -> false
-let is_left n = match n with
- | Node (_,_,_,_,{contents=p}) when not(is_root n) && (left p) == n -> true
- | _ -> false
-
-let is_right n = match n with
- | Node (_,_,_,_,{contents=p}) when not(is_root n) && (right p) == n -> true
- | _ -> false
-
-
-let compare t1 t2 = match t1,t2 with
- | Nil,Nil -> 0
- | String s1, String s2 -> String.compare s1 s2
- | Nil, String _ -> -1
- | String _, Nil -> 1
- | Node(i1,_,_,_,_), Node(i2,_,_,_,_) -> i1 - i2
- | _, Node _ -> -1
- | Node _ , _ -> 1
-let equal t1 t2 = (compare t1 t2) == 0
-
-let int_size = Sys.word_size/8
-let ssize s = ((String.length s)/4 +1)*4
-let rec size =
- function Nil -> (int_size,1,0,0)
- | String s -> (int_size + (ssize s),0,1,0)
- | Node(_,_,l,r,_) ->
- let sizel,nl,sl,il = size l
- and sizer,nr,sr,ir = size r
+external tree_select_child : tree -> [`Tree ] node -> int_vector -> [`Tree] node = "caml_xml_tree_select_child"
+external tree_select_foll_sibling : tree -> [`Tree ] node -> int_vector -> [`Tree] node = "caml_xml_tree_select_foll_sibling"
+external tree_select_desc : tree -> [`Tree ] node -> int_vector -> [`Tree] node = "caml_xml_tree_select_desc"
+external tree_select_foll_below : tree -> [`Tree ] node -> int_vector -> [`Tree] node -> [`Tree] node = "caml_xml_tree_select_foll_below"
+
+
+module HPtset = Hashtbl.Make(Ptset.Int)
+
+let vector_htbl = HPtset.create MED_H_SIZE
+
+let ptset_to_vector s =
+ try
+ HPtset.find vector_htbl s
+ with
+ Not_found ->
+ let v = int_vector_alloc (Ptset.Int.cardinal s) in
+ let _ = Ptset.Int.fold (fun e i -> int_vector_set v i e;i+1) s 0 in
+ HPtset.add vector_htbl s v; v
+
+
+type t = { doc : tree;
+ node : [`Tree] node;
+ ttable : (Tag.t,(Ptset.Int.t*Ptset.Int.t)) Hashtbl.t;
+ }
+
+let text_size t = text_size t.doc
+
+module MemUnion = Hashtbl.Make (struct
+ type t = Ptset.Int.t*Ptset.Int.t
+ let equal (x,y) (z,t) = (Ptset.Int.equal x z)&&(Ptset.Int.equal y t)
+ let equal a b = equal a b || equal b a
+ let hash (x,y) = (* commutative hash *)
+ let x = Ptset.Int.hash x
+ and y = Ptset.Int.hash y