Module Pooled_hashtbl

A 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_values
val hash : 'a -> int
val hash_param : int -> int -> 'a -> int
type (!'a, !'b) t
val sexp_of_t : ('a -> Sexplib0.Sexp.t) -> ('b -> Sexplib0.Sexp.t) -> ('a, 'b) t -> Sexplib0.Sexp.t

We 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.

Creators

val create : 'a 'b. ?growth_allowed:bool -> ?size:int -> 'a Base.Hashtbl.Key.t -> ('a, 'b) t

The 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.t
val of_alist_exn : 'a 'b. ?growth_allowed:bool -> ?size:int -> 'a Base.Hashtbl.Key.t -> ('a * 'b) list -> ('a, 'b) t
val of_alist_multi : 'a 'b. ?growth_allowed:bool -> ?size:int -> 'a Base.Hashtbl.Key.t -> ('a * 'b) list -> ('a, 'b list) t

Creates 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) @ local

Applies 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 = 2
val 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) @ local
val 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) @ local
val 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) @ local

Like 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)]

Accessors

type 'a key = 'a

Attempting to modify (set, remove, etc.) the hashtable during iteration (fold, iter, iter_keys, iteri) will raise an exception.

val is_empty : (_, _) t -> bool

Whether the dictionary is empty.

val length : (_, _) t -> int

How many key/value pairs the dictionary contains.

val to_alist : ('key, 'data) t -> ('key key * 'data) list

All key/value pairs.

val keys : ('key, _) t -> 'key key list

All keys in the dictionary, in the same order as to_alist.

val data : (_, 'data) t -> 'data list

All values in the dictionary, in the same order as to_alist.

val clear : (_, _) t -> unit

Removes all key/value pairs from the dictionary.

val copy : ('key, 'data) t -> ('key, 'data) t

A new dictionary containing the same key/value pairs.

val mem : ('key, 'data) t -> 'key key -> bool

Whether key has a value.

val find : 'key 'data 'phantom. ('key, 'data) t -> 'key key -> 'data option

Produces the current value, or absence thereof, for a given key.

val find_exn : 'key 'data 'phantom. ('key, 'data) t -> 'key key -> 'data

Like find. Raises if there is no value for the given key.

val find_or_add : ('key, 'data) t -> 'key key -> default:(unit -> 'data) @ local -> 'data

Like find. Adds the value default () if none exists, then returns it.

val findi_or_add : ('key, 'data) t -> 'key key -> default:('key key -> 'data) @ local -> 'data

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) @ local

Like 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) @ local

Like findi. Calls if_found ~key ~data if a value exists.

val find_and_remove : ('key, 'data) t -> 'key key -> 'data option

Like find. Removes the value for key, if any, from the dictionary before returning it.

val add : ('key, 'data) t -> key:'key key -> data:'data -> [ `Ok | `Duplicate ]

Adds a key/value pair for a key the dictionary does not contain, or reports a duplicate.

val add_exn : ('key, 'data) t -> key:'key key -> data:'data -> unit

Like add. Raises on duplicates.

val set : ('key, 'data) t -> key:'key key -> data:'data -> unit

Adds or replaces a key/value pair in the dictionary.

val remove : ('key, 'data) t -> 'key key -> unit

Removes any value for the given key.

val change : ('key, 'data) t -> 'key key -> f:('data option -> 'data option) @ local -> unit

Adds, replaces, or removes the value for a given key, depending on its current value or lack thereof.

val update : ('key, 'data) t -> 'key key -> f:('data option -> 'data) @ local -> unit

Adds or replaces the value for a given key, depending on its current value or lack thereof.

val update_and_return : ('key, 'data) t -> 'key key -> f:('data option -> 'data) @ local -> 'data

Like update. Returns the new value.

val incr : ?by:int -> ?remove_if_zero:bool -> ('key, int) t -> 'key key -> unit

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.

val decr : ?by:int -> ?remove_if_zero:bool -> ('key, int) t -> 'key key -> unit

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 -> 'acc

Combines every value in the dictionary.

val for_all : (_, 'data) t -> f:('data -> bool) @ local -> bool

Whether every value satisfies f.

val for_alli : ('key, 'data) t -> f:(key:'key key -> (data:'data -> bool) @ local) @ local -> bool

Like for_all. The predicate may also depend on the associated key.

val exists : (_, 'data) t -> f:('data -> bool) @ local -> bool

Whether at least one value satisfies f.

val existsi : ('key, 'data) t -> f:(key:'key key -> (data:'data -> bool) @ local) @ local -> bool

Like exists. The predicate may also depend on the associated key.

val count : (_, 'data) t -> f:('data -> bool) @ local -> int

How many values satisfy f.

val counti : ('key, 'data) t -> f:(key:'key key -> (data:'data -> bool) @ local) @ local -> int

Like count. The predicate may also depend on the associated key.

val iter_keys : ('key, _) t -> f:('key key -> unit) @ local -> unit

Calls f for every key.

val iter : (_, 'data) t -> f:('data -> unit) @ local -> unit

Calls f for every value.

val iteri : ('key, 'data) t -> f:(key:'key key -> (data:'data -> unit) @ local) @ local -> unit

Calls f for every key/value pair.

val map : ('key, 'data) t -> f:('data -> 'c) @ local -> ('key, 'c) t

Transforms every value.

val mapi : ('key, 'data) t -> f:(key:'key key -> (data:'data -> 'c) @ local) @ local -> ('key, 'c) t

Like map. The transformation may also depend on the associated key.

val map_inplace : (_, 'data) t -> f:('data -> 'data) @ local -> unit

Like map. Modifies the input.

val mapi_inplace : ('key, 'data) t -> f:(key:'key key -> (data:'data -> 'data) @ local) @ local -> unit

Like mapi. Modifies the input.

val filter_keys : ('key, 'data) t -> f:('key key -> bool) @ local -> ('key, 'data) t

Produces only those key/value pairs whose key satisfies f.

val filter : ('key, 'data) t -> f:('data -> bool) @ local -> ('key, 'data) t

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) t

Produces only those key/value pairs which satisfy f.

val filter_keys_inplace : ('key, _) t -> f:('key key -> bool) @ local -> unit

Like filter_keys. Modifies the input.

val filter_inplace : (_, 'data) t -> f:('data -> bool) @ local -> unit

Like filter. Modifies the input.

val filteri_inplace : ('key, 'data) t -> f:(key:'key key -> (data:'data -> bool) @ local) @ local -> unit

Like filteri. Modifies the input.

val filter_map : ('key, 'data) t -> f:('data -> 'c option) @ local -> ('key, 'c) t

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) t

Like filter_map. The new value may also depend on the associated key.

val filter_map_inplace : (_, 'data) t -> f:('data -> 'data option) @ local -> unit

Like filter_map. Modifies the input.

val filter_mapi_inplace : ('key, 'data) t -> f:(key:'key key -> (data:'data -> 'data option) @ local) @ local -> unit

Like filter_mapi. Modifies the input.

val partition_tf : ('key, 'data) t -> f:('data -> bool) @ local -> ('key, 'data) t * ('key, 'data) t

Splits 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) t

Like 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) t

Splits 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) t

Like 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) t

Merges 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 -> unit

Merges 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.t
val capacity : (_, _) t -> int
val growth_allowed : (_, _) t -> bool
val choose : ('a, 'b) t -> ('a key * 'b) option

Choose 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_exn : ('a, 'b) t -> #('a key * 'b)

Like choose. Raises if t is empty.

val choose_randomly : ?random_state:Base.Random.State.t -> ('a, 'b) t -> ('a key * 'b) option

Chooses 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.t

find_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) @ local

Just 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.

val find_and_call2 : 'a 'b 'c 'd 'e. ('a, 'b) t -> 'a key -> a:'d -> b:'e -> if_found:('b -> ('d -> ('e -> 'c) @ local) @ local) @ local -> (if_not_found:('a key -> ('d -> ('e -> 'c) @ local) @ local) @ local -> 'c) @ local
val findi_and_call1 : 'a 'b 'c 'd. ('a, 'b) t -> 'a key -> a:'d -> if_found:(key:'a key -> (data:'b -> ('d -> 'c) @ local) @ local) @ local -> (if_not_found:('a key -> ('d -> 'c) @ local) @ local -> 'c) @ local
val findi_and_call2 : 'a 'b 'c 'd 'e. ('a, 'b) t -> 'a key -> a:'d -> b:'e -> if_found: (key:'a key -> (data:'b -> ('d -> ('e -> 'c) @ local) @ local) @ local) @ local -> (if_not_found:('a key -> ('d -> ('e -> 'c) @ local) @ local) @ local -> 'c) @ local
val equal : ('b -> 'b -> bool) -> ('a, 'b) t -> ('a, 'b) t -> bool

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.

val similar : ('b1 -> 'b2 -> bool) -> ('a, 'b1) t -> ('a, 'b2) t -> bool
val add_multi : ('a, 'b list) t -> key:'a key -> data:'b -> unit

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.

val remove_multi : ('a, _ list) t -> 'a key -> unit

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.

val find_multi : 'a 'b. ('a, 'b list) t -> 'a key -> 'b list

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.t
include Base.Invariant.S2 with type ('a, 'b) t := ('a, 'b) t
val invariant : ('a -> unit) -> ('b -> unit) -> ('a, 'b) t -> unit
val validate : name:('a key -> Base.String.t) -> 'b Validate.check -> ('a, 'b) t Validate.check
module Using_hashable : sig ... end
module Poly : sig ... end
module type Key_plain = Core.Hashtbl_intf.Key_plain
module type Key = Core.Hashtbl_intf.Key
module type Key_binable = Core.Hashtbl_intf.Key_binable
module type Key_stable = Core.Hashtbl_intf.Key_stable
module type S_plain = Core.Hashtbl_intf.S_plain with type ('a, 'b) hashtbl = ('a, 'b) t
module type S = Core.Hashtbl_intf.S with type ('a, 'b) hashtbl = ('a, 'b) t
module type S_binable = Core.Hashtbl_intf.S_binable with type ('a, 'b) hashtbl = ('a, 'b) t
module type S_stable = Core.Hashtbl_intf.S_stable with type ('a, 'b) hashtbl = ('a, 'b) t
module Make_plain (Key : sig ... end) : sig ... end
module Make (Key : sig ... end) : sig ... end
module Make_binable (Key : sig ... end) : sig ... end
module Make_stable (Key : sig ... end) : sig ... end
module Make_plain_with_hashable (T : sig ... end) : sig ... end
module Make_with_hashable (T : sig ... end) : sig ... end
module Make_binable_with_hashable (T : sig ... end) : sig ... end
module Make_stable_with_hashable (T : sig ... end) : sig ... end
module Provide_of_sexp (Key : sig ... end) : sig ... end
module Provide_bin_io (Key : sig ... end) : sig ... end
module M (K : Base.T.T) : sig ... end
module Hashable = Base.Hashable
module Merge_into_action = Base.Hashtbl.Merge_into_action
val hashable : ('key, _) t -> 'key Hashable.t
module type For_deriving = Core.Hashtbl_intf.For_deriving
include For_deriving with type ('a, 'b) t := ('a, 'b) t
include Base.Hashtbl.For_deriving with type ('a, 'b) t := ('a, 'b) t
module type Sexp_of_m = sig ... end
module type M_of_sexp = sig ... end
module type M_sexp_grammar = sig ... end
module type Equal_m = sig ... end
val sexp_of_m__t : (module Sexp_of_m with type t = 'k) -> ('v -> Sexplib0.Sexp.t) -> ('k, 'v) t -> Sexplib0.Sexp.t
val m__t_of_sexp : (module M_of_sexp with type t = 'k) -> (Sexplib0.Sexp.t -> 'v) -> Sexplib0.Sexp.t -> ('k, 'v) t
val m__t_sexp_grammar : (module M_sexp_grammar with type t = 'k) -> 'v Sexplib0.Sexp_grammar.t -> ('k, 'v) t Sexplib0.Sexp_grammar.t @@ portable
val equal_m__t : (module Equal_m) -> ('v -> 'v -> bool) -> ('k, 'v) t -> ('k, 'v) t -> bool
module type M_quickcheck = Core.Hashtbl_intf.M_quickcheck
val quickcheck_generator_m__t : (module M_quickcheck with type t = 'k) -> 'v Base_quickcheck.Generator.t -> ('k, 'v) t Core.Quickcheck.Generator.t
val quickcheck_observer_m__t : (module M_quickcheck with type t = 'k) -> 'v Core.Quickcheck.Observer.t -> ('k, 'v) t Core.Quickcheck.Observer.t
val quickcheck_shrinker_m__t : (module M_quickcheck with type t = 'k) -> 'v Core.Quickcheck.Shrinker.t -> ('k, 'v) t Core.Quickcheck.Shrinker.t
val bin_shape_m__t : (module Core.Hashtbl_intf.Key_binable with type t = 'k) -> Bin_prot.Shape.t -> Bin_prot.Shape.t
val 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.sizer
val 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.writer
val 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.reader
val __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_reader
val resize : (_, _) t -> int -> unit

resize 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) -> unit

on_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.