diff options
Diffstat (limited to 'lib/hashset.ml')
| -rw-r--r-- | lib/hashset.ml | 34 |
1 files changed, 30 insertions, 4 deletions
diff --git a/lib/hashset.ml b/lib/hashset.ml index 6bec81c756..af33544dc6 100644 --- a/lib/hashset.ml +++ b/lib/hashset.ml @@ -1,6 +1,6 @@ (************************************************************************) (* v * The Coq Proof Assistant / The Coq Development Team *) -(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2015 *) +(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2016 *) (* \VV/ **************************************************************) (* // * This file is distributed under the terms of the *) (* * GNU Lesser General Public License Version 2.1 *) @@ -16,15 +16,23 @@ module type EqType = sig type t - val equal : t -> t -> bool + val eq : t -> t -> bool end +type statistics = { + num_bindings: int; + num_buckets: int; + max_bucket_length: int; + bucket_histogram: int array +} + module type S = sig type elt type t val create : int -> t val clear : t -> unit val repr : int -> elt -> t -> elt + val stats : t -> statistics end module Make (E : EqType) = @@ -154,7 +162,7 @@ module Make (E : EqType) = t.hashes.(index) <- newhashes; if sz <= t.limit && newsz > t.limit then begin t.oversize <- t.oversize + 1; - for i = 0 to over_limit do test_shrink_bucket t done; + for _i = 0 to over_limit do test_shrink_bucket t done; end; if t.oversize > Array.length t.table / over_limit then resize t end else if Weak.check bucket i then begin @@ -175,7 +183,7 @@ module Make (E : EqType) = if i >= sz then ifnotfound index else if h = hashes.(i) then begin match Weak.get bucket i with - | Some v when E.equal v d -> v + | Some v when E.eq v d -> v | _ -> loop (i + 1) end else loop (i + 1) in @@ -185,6 +193,24 @@ module Make (E : EqType) = let ifnotfound index = add_aux t Weak.set (Some d) h index; d in find_or h t d ifnotfound + let stats t = + let fold accu bucket = max (count_bucket 0 bucket 0) accu in + let max_length = Array.fold_left fold 0 t.table in + let histogram = Array.make (max_length + 1) 0 in + let iter bucket = + let len = count_bucket 0 bucket 0 in + histogram.(len) <- succ histogram.(len) + in + let () = Array.iter iter t.table in + let fold (num, len, i) k = (num + k * i, len + k, succ i) in + let (num, len, _) = Array.fold_left fold (0, 0, 0) histogram in + { + num_bindings = num; + num_buckets = len; + max_bucket_length = Array.length histogram; + bucket_histogram = histogram; + } + end module Combine = struct |