diff options
Diffstat (limited to 'clib')
| -rw-r--r-- | clib/cList.ml | 6 | ||||
| -rw-r--r-- | clib/cList.mli | 3 | ||||
| -rw-r--r-- | clib/hashset.ml | 38 |
3 files changed, 30 insertions, 17 deletions
diff --git a/clib/cList.ml b/clib/cList.ml index 6b13fac48c..d5520aa2b7 100644 --- a/clib/cList.ml +++ b/clib/cList.ml @@ -23,6 +23,7 @@ sig val for_all_i : (int -> 'a -> bool) -> int -> 'a list -> bool val for_all2eq : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool val prefix_of : 'a eq -> 'a list -> 'a list -> bool + val same_length : 'a list -> 'b list -> bool val interval : int -> int -> int list val make : int -> 'a -> 'a list val addn : int -> 'a -> 'a list -> 'a list @@ -154,6 +155,11 @@ external cast : 'a cell -> 'a list = "%identity" (** {6 Equality, testing} *) +let rec same_length l1 l2 = match l1, l2 with +| [], [] -> true +| _ :: l1, _ :: l2 -> same_length l1 l2 +| ([], _ :: _) | (_ :: _, []) -> false + let rec compare cmp l1 l2 = if l1 == l2 then 0 else match l1,l2 with diff --git a/clib/cList.mli b/clib/cList.mli index c8e471f989..6c8df88767 100644 --- a/clib/cList.mli +++ b/clib/cList.mli @@ -42,6 +42,9 @@ sig (** [prefix_of eq l1 l2] returns [true] if [l1] is a prefix of [l2], [false] otherwise. It uses [eq] to compare elements *) + val same_length : 'a list -> 'b list -> bool + (** A more efficient variant of [for_all2eq (fun _ _ -> true)] *) + (** {6 Creating lists} *) val interval : int -> int -> int list diff --git a/clib/hashset.ml b/clib/hashset.ml index 89136e7870..ae43e7db92 100644 --- a/clib/hashset.ml +++ b/clib/hashset.ml @@ -52,7 +52,7 @@ module Make (E : EqType) = mutable rover : int; (* for internal bookkeeping *) } - let get_index t h = (h land max_int) mod (Array.length t.table) + let get_index t h = (h land max_int) mod (Array.length t) let limit = 7 let over_limit = 2 @@ -135,7 +135,7 @@ module Make (E : EqType) = let add_weak ob oh oi = let setter nb ni _ = Weak.blit ob oi nb ni 1 in let h = oh.(oi) in - add_aux newt setter None h (get_index newt h); + add_aux newt setter None h (get_index newt.table h); in iter_weak add_weak t; t.table <- newt.table; @@ -178,24 +178,28 @@ module Make (E : EqType) = in loop 0 - let find_or h t d ifnotfound = - let index = get_index t h in - let bucket = t.table.(index) in + let repr h d t = + let table = t.table in + let index = get_index table h in + let bucket = table.(index) in let hashes = t.hashes.(index) in let sz = Weak.length bucket in - let rec loop i = - if i >= sz then ifnotfound index - else if Int.equal h hashes.(i) then begin + let pos = ref 0 in + let ans = ref None in + while !pos < sz && !ans == None do + let i = !pos in + if Int.equal h hashes.(i) then begin match Weak.get bucket i with - | Some v when E.eq v d -> v - | _ -> loop (i + 1) - end else loop (i + 1) - in - loop 0 - - let repr h d t = - let ifnotfound index = add_aux t Weak.set (Some d) h index; d in - find_or h t d ifnotfound + | Some v as res when E.eq v d -> ans := res + | _ -> incr pos + end else incr pos + done; + if !pos >= sz then + let () = add_aux t Weak.set (Some d) h index in + d + else match !ans with + | None -> assert false + | Some v -> v let stats t = let fold accu bucket = max (count_bucket 0 bucket 0) accu in |