package picos
Install
Dune Dependency
Authors
Maintainers
Sources
sha256=343a8b4759239ca0c107145b8e2cc94c14625fecc0b0887d3c40a9ab7537b8da
sha512=db22b0a5b3adc603c0e815c9011c779f892b9ace76be018b2198d3e24a7d96727c999701025fe5a5fd07d0b452cb7286fc50c939aba0e4dce809941e9ebc12a6
doc/picos.htbl/Picos_htbl/index.html
Module Picos_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_htbl.t =
Picos_htbl.create
~hashed_type:(module Int) ()
val t : (int, string) Picos_htbl.t = <abstr>
# Picos_htbl.try_add t 42 "The answer"
- : bool = true
# Picos_htbl.try_add t 101 "Basics"
- : bool = true
# Picos_htbl.find_exn t 42
- : string = "The answer"
# Picos_htbl.try_add t 101 "The basics"
- : bool = false
# Picos_htbl.remove_all t |> List.of_seq
- : (int * string) list = [(101, "Basics"); (42, "The answer")]