Up

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.

Signature

include Core_hashtbl_intf.Hashtbl
val hash : 'a -> int
val hash_param : int -> int -> 'a -> int
type ('a, 'b) t

We use [@@deriving sexp_of] but not [@@deriving sexp] because we want people to be explicit about the hash and comparison functions used when creating hashtables. One can use Hashtbl.Poly.t, which does have [@@deriving sexp], to use polymorphic comparison and hashing.

val sexp_of_t : ('a -> Sexplib.Sexp.t) -> ('b -> Sexplib.Sexp.t) -> ('a, 'b) t -> Sexplib.Sexp.t
include Invariant.S2 with type ('a, 'b) t := ('a, 'b) t
type ('a, 'b) t
val invariant : 'a Invariant_intf.inv -> 'b Invariant_intf.inv -> ('a, 'b) t Invariant_intf.inv
include Core_hashtbl_intf.Creators with type ('a, 'b) t := ('a, 'b) t with type 'a key = 'a with type ('a, 'b, 'z) create_options := ('a, 'b, 'z) Core_hashtbl_intf.create_options_with_hashable
type ('a, 'b) t
type 'a key = 'a
type ('key, 'data, 'z) create_options
val create : ('a key, 'b, unit -> ('a, 'b) t) create_options
val of_alist : ('a key, 'b, ('a key * 'b) list -> [
| `Ok of ('a, 'b) t
| `Duplicate_key of 'a key
]) create_options
val of_alist_report_all_dups : ('a key, 'b, ('a key * 'b) list -> [
| `Ok of ('a, 'b) t
| `Duplicate_keys of 'a key list
]) create_options
val of_alist_or_error : ('a key, 'b, ('a key * 'b) list -> ('a, 'b) t Or_error.t) create_options
val of_alist_exn : ('a key, 'b, ('a key * 'b) list -> ('a, 'b) t) create_options
val of_alist_multi : ('a key, 'b list, ('a key * 'b) list -> ('a, 'b list) t) create_options
val create_mapped : ('a key, 'b, get_key:('r -> 'a key) -> get_data:('r -> 'b) -> 'r list -> [
| `Ok of ('a, 'b) t
| `Duplicate_keys of 'a key list
]) create_options 
 create_mapped get_key get_data [x1,...,xn]
         = of_alist [get_key x1, get_data x1; ...; get_key xn, get_data xn]
val create_with_key : ('a key, 'r, get_key:('r -> 'a key) -> 'r list -> [
| `Ok of ('a, 'r) t
| `Duplicate_keys of 'a key list
]) create_options 
 create_with_key ~get_key [x1,...,xn]
         = of_alist [get_key x1, x1; ...; get_key xn, xn]
val create_with_key_or_error : ('a key, 'r, get_key:('r -> 'a key) -> 'r list -> ('a, 'r) t Or_error.t) create_options
val create_with_key_exn : ('a key, 'r, get_key:('r -> 'a key) -> 'r list -> ('a, 'r) t) create_options
val group : ('a key, 'b, get_key:('r -> 'a key) -> get_data:('r -> 'b) -> combine:('b -> 'b -> 'b) -> 'r list -> ('a, 'b) t) create_options
include Core_hashtbl_intf.Accessors with type ('a, 'b) t := ('a, 'b) t with type 'a key := 'a key with type ('a, 'z) map_options := ('a, 'z) Core_hashtbl_intf.no_map_options
type ('a, 'b) t
type 'a key
type ('a, 'z) map_options
val sexp_of_key : ('a, _) t -> 'a key -> Sexplib.Sexp.t
val clear : (_, _) t -> unit
val copy : ('a, 'b) t -> ('a, 'b) t
val fold : ('a, 'b) t -> init:'c -> f:(key:'a key -> data:'b -> 'c -> 'c) -> 'c
val iter_vals : (_, 'b) t -> f:('b -> unit) -> unit
val iteri : ('a, 'b) t -> f:(key:'a key -> data:'b -> unit) -> unit
val iter_keys : ('a, _) t -> f:('a key -> unit) -> unit
val iter : ('a, 'b) t -> f:(key:'a key -> data:'b -> unit) -> unit
val existsi : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> bool
val exists : (_, 'b) t -> f:('b -> bool) -> bool
val for_alli : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> bool
val for_all : (_, 'b) t -> f:('b -> bool) -> bool
val counti : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> int
val count : (_, 'b) t -> f:('b -> bool) -> int
val length : (_, _) t -> int
val is_empty : (_, _) t -> bool
val mem : ('a, _) t -> 'a key -> bool
val remove : ('a, _) t -> 'a key -> unit
val replace : ('a, 'b) t -> key:'a key -> data:'b -> unit
val set : ('a, 'b) t -> key:'a key -> data:'b -> unit
val add : ('a, 'b) t -> key:'a key -> data:'b -> [
| `Ok
| `Duplicate
]
val add_or_error : ('a, 'b) t -> key:'a key -> data:'b -> unit Or_error.t
val add_exn : ('a, 'b) t -> key:'a key -> data:'b -> unit
val change : ('a, 'b) t -> 'a key -> f:('b option -> 'b option) -> unit

change t key ~f changes t's value for key to be f (find t key).

val update : ('a, 'b) t -> 'a key -> f:('b option -> 'b) -> unit

update t key ~f is change t key ~f:(fun o -> Some (f o)).

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 map : ('c, ('a, 'b) t -> f:('b -> 'c) -> ('a, 'c) t) map_options

map t f returns new table with bound values replaced by f applied to the bound values

val mapi : ('c, ('a, 'b) t -> f:(key:'a key -> data:'b -> 'c) -> ('a, 'c) t) map_options

like map, but function takes both key and data as arguments

val filter_map : ('c, ('a, 'b) t -> f:('b -> 'c option) -> ('a, 'c) t) map_options

returns new map with bound values filtered by f applied to the bound values

val filter_mapi : ('c, ('a, 'b) t -> f:(key:'a key -> data:'b -> 'c option) -> ('a, 'c) t) map_options

like filter_map, but function takes both key and data as arguments

val filter : ('a, 'b) t -> f:('b -> bool) -> ('a, 'b) t
val filteri : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> ('a, 'b) t
val partition_map : ('c, ('d, ('a, 'b) t -> f:('b -> [
| `Fst of 'c
| `Snd of 'd
]) -> ('a, 'c) t * ('a, 'd) t) map_options) map_options

returns new maps with bound values partitioned by f applied to the bound values

val partition_mapi : ('c, ('d, ('a, 'b) t -> f:(key:'a key -> data:'b -> [
| `Fst of 'c
| `Snd of 'd
]) -> ('a, 'c) t * ('a, 'd) t) map_options) map_options

like partition_map, but function takes both key and data as arguments

val partition_tf : ('a, 'b) t -> f:('b -> bool) -> ('a, 'b) t * ('a, 'b) t
val partitioni_tf : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> ('a, 'b) t * ('a, 'b) t
val find_or_add : ('a, 'b) t -> 'a key -> default:(unit -> 'b) -> 'b

find_or_add t k ~default returns the data associated with key k if it is in the table t, otherwise it lets d = default() and adds it to the table.

val find : ('a, 'b) t -> 'a key -> 'b option

find t k returns Some (the current binding) of k in t, or None if no such binding exists

val find_exn : ('a, 'b) t -> 'a key -> 'b

find_exn t k returns the current binding of k in t, or raises Not_found if no such binding exists.

val find_and_call : ('a, 'b) t -> 'a key -> if_found:('b -> 'c) -> if_not_found:('a key -> 'c) -> 'c

find_and_call t k ~if_found ~if_not_found

is equivalent to:

match find t k with Some v -> if_found v | None -> if_not_found k

except that it doesn't allocate the option.

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

find_and_remove t k returns Some (the current binding) of k in t and removes it, or None is no such binding exists

val merge : ('c, ('k, 'a) t -> ('k, 'b) t -> f:(key:'k key -> [
| `Left of 'a
| `Right of 'b
| `Both of 'a * 'b
] -> 'c option) -> ('k, 'c) t) map_options

Merge two hashtables.

The result of merge f h1 h2 has as keys the set of all k in the union of the sets of keys of h1 and h2 for which d(k) is not None, where:

d(k) =

  • f ~key:k (Some d1) None if k in h1 is to d1, and h2 does not map k;
  • f ~key:k None (Some d2) if k in h2 is to d2, and h1 does not map k;
  • f ~key:k (Some d1) (Some d2) otherwise, where k in h1 is to d1 and k in h2 is to d2.

Each key k is mapped to a single piece of data x, where d(k) = Some x.

val merge_into : f:(key:'a key -> 'b -> 'c option -> 'c option) -> src:('a, 'b) t -> dst:('a, 'c) t -> unit

Merge one hashtable into another.

After merge_into f src dst, for every key in src, key will be re-mapped in dst to v if f ~key d1 (find dst key) = Some v.

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

Returns the list of all keys for given hashtable.

Returns the list of all data for given hashtable.

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

Returns the list of all data for given hashtable.

val filter_inplace : (_, 'b) t -> f:('b -> bool) -> unit

filter_inplace t ~f removes all the elements from t that don't satisfy f.

val filteri_inplace : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> unit
val filter_keys_inplace : ('a, _) t -> f:('a key -> bool) -> unit

replace_all t ~f applies f to all elements in t, transforming them in place

val replace_all : (_, 'b) t -> f:('b -> 'b) -> unit

replace_all t ~f applies f to all elements in t, transforming them in place

val replace_alli : ('a, 'b) t -> f:(key:'a key -> data:'b -> 'b) -> unit

filter_replace_all combines the effects of replace_all and filter_inplace

val filter_replace_all : (_, 'b) t -> f:('b -> 'b option) -> unit

filter_replace_all combines the effects of replace_all and filter_inplace

val filter_replace_alli : ('a, 'b) t -> f:(key:'a key -> data:'b -> 'b option) -> unit
val equal : ('a, 'b) t -> ('a, 'b) t -> ('b -> 'b -> bool) -> bool

equal t1 t2 f and similar t1 t2 f 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 : ('a, 'b1) t -> ('a, 'b2) t -> ('b1 -> 'b2 -> bool) -> bool
val to_alist : ('a, 'b) t -> ('a key * 'b) list

Returns the list of all (key,data) pairs for given hashtable.

val validate : name:('a key -> string) -> 'b Validate.check -> ('a, 'b) t Validate.check
val incr : ?by:int -> ('a, int) t -> 'a key -> unit
val hashable : ('key, _) t -> 'key Hashable.t
module Poly : sig .. end
module type Key = Core_hashtbl_intf.Key
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 Make (Key : Key) : S with type key = Key.t
module Make_binable (Key : Key_binable) : S_binable with type key = Key.t
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 Zero.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.