package picos_aux
Install
Dune Dependency
Authors
Maintainers
Sources
sha256=862d61383e2df93a876bedcffb1fd1ddc0f96c50b0e9c07943a2aee1f0e182be
sha512=87805379017ef4a7f2c11b954625a3757a0f1431bb9ba59132202de278b3e41adbe0cdc20e3ab23b7c9a8c5a15faeb7ec79348e7d80f2b14274b00df0893b8c0
doc/picos_aux.htbl/Picos_aux_htbl/index.html
Module Picos_aux_htblSource
Lock-free hash table.
🏎️ Single key reads with this hash table are actually wait-free rather than just lock-free. Internal resizing automatically uses all the threads that are trying to write to the hash table.
API
Represents a lock-free hash table mapping keys of type 'k to values of type 'v.
First-class module type abbreviation.
val create :
?hashed_type:'k hashed_type ->
?min_buckets:int ->
?max_buckets:int ->
unit ->
('k, 'v) tcreate ~hashed_type:(module Key) () creates a new empty lock-free hash table.
- The optional
hashed_typeargument can and usually should be used to specify theequalandhashoperations on keys. Slow polymorphic equality(=)and slow polymorphicseeded_hash (Bits64.to_int (Random.bits64 ()))is used by default. - The default
min_bucketsis unspecified and a givenmin_bucketsmay be adjusted by the implementation. - The default
max_bucketsis unspecified and a givenmax_bucketsmay be adjusted by the implementation.
hashed_type_of htbl returns a copy of the hashed type used when the hash table htbl was created.
min_buckets_of htbl returns the minimum number of buckets of the hash table htbl.
ℹ️ The returned value may not be the same as given to create.
max_buckets_of htbl returns the maximum number of buckets of the hash table htbl.
ℹ️ The returned value may not be the same as given to create.
Looking up bindings
find_exn htbl key returns the current binding of key in the hash table htbl or raises Not_found if no such binding exists.
mem htbl key determines whether the hash table htbl has a binding for the key.
to_seq htbl takes a snapshot of the bindings in the hash table and returns them as an association sequence.
🐌 This is a linear time operation.
find_random_exn htbl tries to find a random binding from the hash table and returns the key of the binding or raises Not_found in case the hash table is empty.
🐌 This is an expected constant time operation with worst case linear time complexity.
Adding bindings
try_add htbl key value tries to add a new binding of key to value to the hash table htbl. Returns true on success and false in case the hash table already contained a binding for key.
Removing bindings
try_remove htbl key tries to remove a binding of key from the hash table htbl. Returns true on success and false in case the hash table did not contain a binding for key.
remove_exn htbl key tries to remove a binding of key from the hash table htbl and return it or raise Not_found if no such binding exists.
remove_all htbl takes a snapshot of the bindings in the hash table, removes the bindings from the hash table, and returns the snapshot as an association sequence.
🐌 This is a linear time operation.
Examples
An example top-level session:
# let t : (int, string) Picos_aux_htbl.t =
Picos_aux_htbl.create
~hashed_type:(module Int) ()
val t : (int, string) Picos_aux_htbl.t = <abstr>
# Picos_aux_htbl.try_add t 42 "The answer"
- : bool = true
# Picos_aux_htbl.try_add t 101 "Basics"
- : bool = true
# Picos_aux_htbl.find_exn t 42
- : string = "The answer"
# Picos_aux_htbl.try_add t 101 "The basics"
- : bool = false
# Picos_aux_htbl.remove_all t |> List.of_seq
- : (int * string) list = [(101, "Basics"); (42, "The answer")]