Pooled_hashtblA polymorphic hashtbl that uses Pool to avoid allocation.
This uses the standard linked-chain hashtable algorithm, albeit with links performed through a pool and hence avoiding caml_modify (for table manipulation), even when hashing object keys/values.
This implementation is worth exploring for your application if profiling demonstrates that garbage collection and the caml_modify write barrier are a significant part of your execution time.
include Core.Hashtbl_intf.Hashtbl_over_valuesval sexp_of_t :
('a -> Sexplib0.Sexp.t) ->
('b -> Sexplib0.Sexp.t) ->
('a, 'b) t ->
Sexplib0.Sexp.tWe provide a sexp_of_t but not a t_of_sexp for this type because one needs to be explicit about the hash and comparison functions used when creating a hashtable. Note that Hashtbl.Poly.t does have [@@deriving sexp], and uses OCaml's built-in polymorphic comparison and and polymorphic hashing.
val create :
'a 'b. ?growth_allowed:bool ->
?size:int ->
'a Base.Hashtbl.Key.t ->
('a, 'b) tThe module you pass to create must have a type that is hashable, sexpable, and comparable.
Example:
Hashtbl.create (module Int);; - : (int, '_a) Hashtbl.t = <abstr>;;
val of_alist :
'a 'b. ?growth_allowed:bool ->
?size:int ->
'a Base.Hashtbl.Key.t ->
('a * 'b) list ->
[ `Ok of ('a, 'b) t | `Duplicate_key of 'a ]Example:
Hashtbl.of_alist (module Int) [(3, "something"); (2, "whatever")] - : [ `Duplicate_key of int | `Ok of (int, string) Hashtbl.t ] = `Ok <abstr>
val of_alist_report_all_dups :
'a 'b. ?growth_allowed:bool ->
?size:int ->
'a Base.Hashtbl.Key.t ->
('a * 'b) list ->
[ `Ok of ('a, 'b) t | `Duplicate_keys of 'a list ]Whereas of_alist will report Duplicate_key no matter how many dups there are in your list, of_alist_report_all_dups will report each and every duplicate entry.
For example:
Hashtbl.of_alist (module Int) [(1, "foo"); (1, "bar"); (2, "foo"); (2, "bar")];; - : [ `Duplicate_key of int | `Ok of (int, string) Hashtbl.t ] = `Duplicate_key 1 Hashtbl.of_alist_report_all_dups (module Int) [(1, "foo"); (1, "bar"); (2, "foo"); (2, "bar")];; - : [ `Duplicate_keys of int list | `Ok of (int, string) Hashtbl.t ] = `Duplicate_keys [1; 2]
val of_alist_or_error :
'a 'b. ?growth_allowed:bool ->
?size:int ->
'a Base.Hashtbl.Key.t ->
('a * 'b) list ->
('a, 'b) t Base.Or_error.tval of_alist_exn :
'a 'b. ?growth_allowed:bool ->
?size:int ->
'a Base.Hashtbl.Key.t ->
('a * 'b) list ->
('a, 'b) tval of_alist_multi :
'a 'b. ?growth_allowed:bool ->
?size:int ->
'a Base.Hashtbl.Key.t ->
('a * 'b) list ->
('a, 'b list) tCreates a "multi" hashtable, i.e., a hashtable where each key points to a list potentially containing multiple values. So instead of short-circuiting with a `Duplicate_key variant on duplicates, as in of_alist, of_alist_multi folds those values into a list for the given key:
let h = Hashtbl.of_alist_multi (module Int) [(1, "a"); (1, "b"); (2, "c"); (2, "d")];; val h : (int, string list) Hashtbl.t = <abstr> Hashtbl.find_exn h 1;; - : string list = ["b"; "a"]
val create_mapped :
'a 'b 'r. ?growth_allowed:bool ->
?size:int ->
'a Base.Hashtbl.Key.t ->
get_key:('r -> 'a) @ local ->
(get_data:('r -> 'b) @ local ->
('r list ->
[ `Ok of ('a, 'b) t | `Duplicate_keys of 'a list ]) @ local) @ localApplies the get_key and get_data functions to the 'r list to create the initial keys and values, respectively, for the new hashtable.
create_mapped get_key get_data [x1;...;xn]
= of_alist [get_key x1, get_data x1; ...; get_key xn, get_data xn]Example:
let h =
Hashtbl.create_mapped (module Int)
~get_key:(local_ (fun x -> x))
~get_data:(local_ (fun x -> x + 1))
[1; 2; 3];;
val h : [ `Duplicate_keys of int list | `Ok of (int, int) Hashtbl.t ] = `Ok <abstr>
let h =
match h with
| `Ok x -> x
| `Duplicate_keys _ -> failwith ""
in
Hashtbl.find_exn h 1;;
- : int = 2val create_with_key :
'a 'r. ?growth_allowed:bool ->
?size:int ->
'a Base.Hashtbl.Key.t ->
get_key:('r -> 'a) @ local ->
('r list ->
[ `Ok of ('a, 'r) t | `Duplicate_keys of 'a list ]) @ local create_with_key ~get_key [x1;...;xn]
= of_alist [get_key x1, x1; ...; get_key xn, xn]val create_with_key_or_error :
'a 'r. ?growth_allowed:bool ->
?size:int ->
'a Base.Hashtbl.Key.t ->
get_key:('r -> 'a) @ local ->
('r list ->
('a, 'r) t Base.Or_error.t) @ localval create_with_key_exn :
'a 'r. ?growth_allowed:bool ->
?size:int ->
'a Base.Hashtbl.Key.t ->
get_key:('r -> 'a) @ local ->
('r list ->
('a, 'r) t) @ localval group :
'a 'b 'r. ?growth_allowed:bool ->
?size:int ->
'a Base.Hashtbl.Key.t ->
get_key:('r -> 'a) @ local ->
(get_data:('r -> 'b) @ local ->
(combine:('b -> ('b -> 'b) @ local) @ local ->
('r list ->
('a, 'b) t) @ local) @ local) @ localLike create_mapped, applies the get_key and get_data functions to the 'r list to create the initial keys and values, respectively, for the new hashtable -- and then, like add_multi, folds together values belonging to the same keys. Here, though, the function used for the folding is given by combine (instead of just being a cons).
Example:
Hashtbl.group (module Int)
~get_key:(local_ (fun x -> x / 2))
~get_data:(local_ (fun x -> x))
~combine:(local_ (fun x y -> x * y))
[ 1; 2; 3; 4]
|> Hashtbl.to_alist;;
- : (int * int) list = [(2, 4); (1, 6); (0, 1)]Attempting to modify (set, remove, etc.) the hashtable during iteration (fold, iter, iter_keys, iteri) will raise an exception.
val is_empty : (_, _) t -> boolWhether the dictionary is empty.
val length : (_, _) t -> intHow many key/value pairs the dictionary contains.
val data : (_, 'data) t -> 'data listAll values in the dictionary, in the same order as to_alist.
val clear : (_, _) t -> unitRemoves all key/value pairs from the dictionary.
Produces the current value, or absence thereof, for a given key.
Like find. Raises if there is no value for the given key.
Like find. Adds the value default () if none exists, then returns it.
Like find. Adds default key if no value exists.
val find_and_call :
'key 'data 'phantom 'c. ('key, 'data) t ->
'key key ->
if_found:('data -> 'c) @ local ->
(if_not_found:('key key -> 'c) @ local ->
'c) @ localLike find. Calls if_found data if a value exists, or if_not_found key otherwise. Avoids allocation Some.
val findi_and_call :
'key 'data 'phantom 'c. ('key, 'data) t ->
'key key ->
if_found:(key:'key key -> (data:'data -> 'c) @ local) @ local ->
(if_not_found:('key key -> 'c) @ local ->
'c) @ localLike findi. Calls if_found ~key ~data if a value exists.
Like find. Removes the value for key, if any, from the dictionary before returning it.
Adds a key/value pair for a key the dictionary does not contain, or reports a duplicate.
Adds or replaces a key/value pair in the dictionary.
Adds, replaces, or removes the value for a given key, depending on its current value or lack thereof.
Adds or replaces the value for a given key, depending on its current value or lack thereof.
Like update. Returns the new value.
Adds by to the value for key, default 0 if key is absent. May remove key if the result is 0, depending on remove_if_zero.
Subtracts by from the value for key, default 0 if key is absent. May remove key if the result is 0, depending on remove_if_zero.
val fold :
('key, 'data) t ->
init:'acc ->
f:(key:'key key -> (data:'data -> ('acc -> 'acc) @ local) @ local) @ local ->
'accCombines every value in the dictionary.
val for_all : (_, 'data) t -> f:('data -> bool) @ local -> boolWhether every value satisfies f.
Like for_all. The predicate may also depend on the associated key.
val exists : (_, 'data) t -> f:('data -> bool) @ local -> boolWhether at least one value satisfies f.
Like exists. The predicate may also depend on the associated key.
val count : (_, 'data) t -> f:('data -> bool) @ local -> intHow many values satisfy f.
Like count. The predicate may also depend on the associated key.
val iter : (_, 'data) t -> f:('data -> unit) @ local -> unitCalls f for every value.
Calls f for every key/value pair.
val mapi :
('key, 'data) t ->
f:(key:'key key -> (data:'data -> 'c) @ local) @ local ->
('key, 'c) tLike map. The transformation may also depend on the associated key.
val map_inplace : (_, 'data) t -> f:('data -> 'data) @ local -> unitLike map. Modifies the input.
val mapi_inplace :
('key, 'data) t ->
f:(key:'key key -> (data:'data -> 'data) @ local) @ local ->
unitLike mapi. Modifies the input.
Produces only those key/value pairs whose key satisfies f.
Produces only those key/value pairs whose value satisfies f.
val filteri :
('key, 'data) t ->
f:(key:'key key -> (data:'data -> bool) @ local) @ local ->
('key, 'data) tProduces only those key/value pairs which satisfy f.
Like filter_keys. Modifies the input.
val filter_inplace : (_, 'data) t -> f:('data -> bool) @ local -> unitLike filter. Modifies the input.
val filteri_inplace :
('key, 'data) t ->
f:(key:'key key -> (data:'data -> bool) @ local) @ local ->
unitLike filteri. Modifies the input.
Produces key/value pairs for which f produces Some.
val filter_mapi :
('key, 'data) t ->
f:(key:'key key -> (data:'data -> 'c option) @ local) @ local ->
('key, 'c) tLike filter_map. The new value may also depend on the associated key.
val filter_map_inplace :
(_, 'data) t ->
f:('data -> 'data option) @ local ->
unitLike filter_map. Modifies the input.
val filter_mapi_inplace :
('key, 'data) t ->
f:(key:'key key -> (data:'data -> 'data option) @ local) @ local ->
unitLike filter_mapi. Modifies the input.
val partition_tf :
('key, 'data) t ->
f:('data -> bool) @ local ->
('key, 'data) t * ('key, 'data) tSplits one dictionary into two. The first contains key/value pairs for which the value satisfies f. The second contains the remainder.
val partitioni_tf :
('key, 'data) t ->
f:(key:'key key -> (data:'data -> bool) @ local) @ local ->
('key, 'data) t * ('key, 'data) tLike partition_tf. The predicate may also depend on the associated key.
val partition_map :
('key, 'data) t ->
f:('data -> ('c, 'd) Base.Either.t) @ local ->
('key, 'c) t * ('key, 'd) tSplits one dictionary into two, corresponding respectively to First _ and Second _ results from f.
val partition_mapi :
('key, 'data) t ->
f:(key:'key key -> (data:'data -> ('c, 'd) Base.Either.t) @ local) @ local ->
('key, 'c) t * ('key, 'd) tLike partition_map. The split may also depend on the associated key.
val merge :
('key, 'data1) t ->
('key, 'data2) t ->
f:
(key:'key key ->
([ `Left of 'data1 | `Right of 'data2 | `Both of 'data1 * 'data2 ] ->
'data3 option) @ local) @ local ->
('key, 'data3) tMerges two dictionaries by fully traversing both. Not suitable for efficiently merging lists of dictionaries. See merge_into instead.
If the two dictionaries differ in their implementations, e.g. of hash or compare functions, those from the first argument are preferred.
val merge_into :
src:('key, 'data1) t ->
dst:('key, 'data2) t ->
f:
(key:'key key ->
('data1 ->
('data2 option ->
'data2 Base.Dictionary_mutable.Merge_into_action.t) @ local) @ local) @ local ->
unitMerges two dictionaries by traversing src and adding to dst. Computes the effect on dst of each key/value pair in src using f.
val sexp_of_key : ('a, _) t -> 'a key -> Sexplib0.Sexp.tval capacity : (_, _) t -> intval growth_allowed : (_, _) t -> boolChoose an arbitrary key/value pair of a hash table. Returns None if t is empty.
The choice is deterministic. Calling choose multiple times on the same table returns the same key/value pair, so long as the table is not mutated in between. Beyond determinism, no guarantees are made about how the choice is made. Expect bias toward certain hash values.
This hash bias can lead to degenerate performance in some cases, such as clearing a hash table using repeated choose and remove. At each iteration, finding the next element may have to scan farther from its initial hash value.
val choose_randomly :
?random_state:Base.Random.State.t ->
('a, 'b) t ->
('a key * 'b) optionChooses a random key/value pair of a hash table. Returns None if t is empty.
The choice is distributed uniformly across hash values, rather than across keys themselves. As a consequence, the closer the keys are to evenly spaced out in the table, the closer this function will be to a uniform choice of keys.
This function may be preferable to choose when nondeterministic choice is acceptable, and bias toward certain hash values is undesirable.
val choose_randomly_exn :
?random_state:Base.Random.State.t ->
('a, 'b) t ->
#('a key * 'b)Like choose_randomly. Raises if t is empty.
val find_or_null : 'a 'b. ('a, 'b) t -> 'a key -> 'b Basement.Or_null_shim.tfind_or_null returns This data if the key is found, Null if not.
val find_and_call1 :
'a 'b 'c 'd. ('a, 'b) t ->
'a key ->
a:'d ->
if_found:('b -> ('d -> 'c) @ local) @ local ->
(if_not_found:('a key -> ('d -> 'c) @ local) @ local ->
'c) @ localJust like find_and_call, but takes an extra argument which is passed to if_found and if_not_found, so that the client code can avoid allocating closures or using refs to pass this additional information. This function is only useful in code which tries to minimize heap allocation.
equal f t1 t2 and similar f t1 t2 both return true iff t1 and t2 have the same keys and for all keys k, f (find_exn t1 k) (find_exn t2 k). equal and similar only differ in their types.
add_multi t ~key ~data if key is present in the table then cons data on the list, otherwise add key with a single element list.
remove_multi t key updates the table, removing the head of the list bound to key. If the list has only one element (or is empty) then the binding is removed.
find_multi t key returns the empty list if key is not present in the table, returns t's values for key otherwise.
val hashable_s : ('key, _) t -> 'key Base.Hashtbl.Key.tinclude Base.Invariant.S2 with type ('a, 'b) t := ('a, 'b) tval invariant : ('a -> unit) -> ('b -> unit) -> ('a, 'b) t -> unitval validate :
name:('a key -> Base.String.t) ->
'b Validate.check ->
('a, 'b) t Validate.checkmodule Using_hashable : sig ... endmodule Poly : sig ... endmodule type Key_plain = Core.Hashtbl_intf.Key_plainmodule type Key = Core.Hashtbl_intf.Keymodule type Key_binable = Core.Hashtbl_intf.Key_binablemodule type Key_stable = Core.Hashtbl_intf.Key_stablemodule type S_plain =
Core.Hashtbl_intf.S_plain with type ('a, 'b) hashtbl = ('a, 'b) tmodule type S = Core.Hashtbl_intf.S with type ('a, 'b) hashtbl = ('a, 'b) tmodule type S_binable =
Core.Hashtbl_intf.S_binable with type ('a, 'b) hashtbl = ('a, 'b) tmodule type S_stable =
Core.Hashtbl_intf.S_stable with type ('a, 'b) hashtbl = ('a, 'b) tmodule Make_plain (Key : sig ... end) : sig ... endmodule Make_binable (Key : sig ... end) : sig ... endmodule Make_stable (Key : sig ... end) : sig ... endmodule Make_plain_with_hashable (T : sig ... end) : sig ... endmodule Make_with_hashable (T : sig ... end) : sig ... endmodule Make_binable_with_hashable (T : sig ... end) : sig ... endmodule Make_stable_with_hashable (T : sig ... end) : sig ... endmodule Provide_of_sexp (Key : sig ... end) : sig ... endmodule Provide_bin_io (Key : sig ... end) : sig ... endmodule Hashable = Base.Hashablemodule Merge_into_action = Base.Hashtbl.Merge_into_actionval hashable : ('key, _) t -> 'key Hashable.tmodule type For_deriving = Core.Hashtbl_intf.For_derivinginclude For_deriving with type ('a, 'b) t := ('a, 'b) tinclude Base.Hashtbl.For_deriving with type ('a, 'b) t := ('a, 'b) tmodule type Sexp_of_m = sig ... endmodule type M_of_sexp = sig ... endmodule type M_sexp_grammar = sig ... endmodule type Equal_m = sig ... endval sexp_of_m__t :
(module Sexp_of_m with type t = 'k) ->
('v -> Sexplib0.Sexp.t) ->
('k, 'v) t ->
Sexplib0.Sexp.tval m__t_of_sexp :
(module M_of_sexp with type t = 'k) ->
(Sexplib0.Sexp.t -> 'v) ->
Sexplib0.Sexp.t ->
('k, 'v) tval m__t_sexp_grammar :
(module M_sexp_grammar with type t = 'k) ->
'v Sexplib0.Sexp_grammar.t ->
('k, 'v) t Sexplib0.Sexp_grammar.t @@ portablemodule type M_quickcheck = Core.Hashtbl_intf.M_quickcheckval quickcheck_generator_m__t :
(module M_quickcheck with type t = 'k) ->
'v Base_quickcheck.Generator.t ->
('k, 'v) t Core.Quickcheck.Generator.tval quickcheck_observer_m__t :
(module M_quickcheck with type t = 'k) ->
'v Core.Quickcheck.Observer.t ->
('k, 'v) t Core.Quickcheck.Observer.tval quickcheck_shrinker_m__t :
(module M_quickcheck with type t = 'k) ->
'v Core.Quickcheck.Shrinker.t ->
('k, 'v) t Core.Quickcheck.Shrinker.tval bin_shape_m__t :
(module Core.Hashtbl_intf.Key_binable with type t = 'k) ->
Bin_prot.Shape.t ->
Bin_prot.Shape.tval bin_size_m__t :
(module Core.Hashtbl_intf.Key_binable with type t = 'k) ->
'v Bin_prot.Size.sizer ->
('k, 'v) t Bin_prot.Size.sizerval bin_write_m__t :
(module Core.Hashtbl_intf.Key_binable with type t = 'k) ->
'v Bin_prot.Write.writer ->
('k, 'v) t Bin_prot.Write.writerval bin_read_m__t :
(module Core.Hashtbl_intf.Key_binable with type t = 'k) ->
'v Bin_prot.Read.reader ->
('k, 'v) t Bin_prot.Read.readerval __bin_read_m__t__ :
(module Core.Hashtbl_intf.Key_binable with type t = 'k) ->
'v Bin_prot.Read.reader ->
('k, 'v) t Bin_prot.Read.vtag_readerval resize : (_, _) t -> int -> unitresize t size ensures that t can hold at least size entries without resizing (again), provided that t has growth enabled. This is useful for sizing global tables during application initialization, to avoid subsequent, expensive growth online. See Immediate.String.resize, for example.
val on_grow :
before:(unit -> 'a) ->
after:('a -> old_capacity:int -> new_capacity:int -> unit) ->
uniton_grow ~before ~after allows you to connect higher level loggers to the point where these hashtbls grow. before is called before the table grows, and after after it. This permits you to e.g. measure the time elapsed between the two.
This is only meant for debugging and profiling, e.g. note that once a callback is installed, there is no way to remove it.