package picos_aux

  1. Overview
  2. Docs

Module Picos_aux_htblSource

Lock-free hash table.

The operations provided by this hash table are designed to work as building blocks of non-blocking algorithms. Specifically, the operation signatures and semantics are designed to allow building consensus protocols over arbitrary numbers of processes.

🏎ī¸ 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

Sourcetype (!'k, !'v) t

Represents a lock-free hash table mapping keys of type 'k to values of type 'v.

Sourcetype 'k hashed_type = (module Hashtbl.HashedType with type t = 'k)

First-class module type abbreviation.

Sourceval create : ?hashed_type:'k hashed_type -> ?min_buckets:int -> ?max_buckets:int -> unit -> ('k, 'v) t

create ~hashed_type:(module Key) () creates a new empty lock-free hash table.

  • The optional hashed_type argument can and usually should be used to specify the equal and hash operations on keys. Slow polymorphic equality (=) and slow polymorphic seeded_hash (Bits64.to_int (Random.bits64 ())) is used by default.
  • The default min_buckets is unspecified and a given min_buckets may be adjusted by the implementation.
  • The default max_buckets is unspecified and a given max_buckets may be adjusted by the implementation.
Sourceval hashed_type_of : ('k, 'v) t -> 'k hashed_type

hashed_type_of htbl returns a copy of the hashed type used when the hash table htbl was created.

Sourceval min_buckets_of : ('k, 'v) t -> int

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.

Sourceval max_buckets_of : ('k, 'v) t -> int

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

Sourceval find_exn : ('k, 'v) t -> 'k -> 'v

find_exn htbl key returns the current binding of key in the hash table htbl or raises Not_found if no such binding exists.

  • raises Not_found

    in case no binding of key exists in the hash table htbl.

Sourceval mem : ('k, 'v) t -> 'k -> bool

mem htbl key determines whether the hash table htbl has a binding for the key.

Adding bindings

Sourceval try_add : ('k, 'v) t -> 'k -> 'v -> bool

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.

Updating bindings

Sourceval try_set : ('k, 'v) t -> 'k -> 'v -> bool

try_set htbl key value tries to update an existing binding of key to value in the hash table htbl. Returns true on success and false in case the hash table did not contain a binding for key.

Sourceval try_compare_and_set : ('k, 'v) t -> 'k -> 'v -> 'v -> bool

try_compare_and_set htbl key before after tries to update an existing binding of key from the before value to the after value in the hash table htbl. Returns true on success and false in case the hash table did not contain a binding of key to the before value.

ℹī¸ The values are compared using physical equality, i.e. the == operator.

Sourceval set_exn : ('k, 'v) t -> 'k -> 'v -> 'v

set_exn htbl key after tries to update an existing binding of key from some before value to the after value in the hash table htbl. Returns the before value on success or raises Not_found if no such binding exists.

  • raises Not_found

    in case no binding of key exists in the hash table htbl.

Removing bindings

Sourceval try_remove : ('k, 'v) t -> 'k -> bool

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.

Sourceval try_compare_and_remove : ('k, 'v) t -> 'k -> 'v -> bool

try_compare_and_remove htbl key before tries to remove a binding of key to the before value from the hash table htbl. Returns true on success and false in case the hash table did not contain a binding of key to the before value.

ℹī¸ The values are compared using physical equality, i.e. the == operator.

Sourceval remove_exn : ('k, 'v) t -> 'k -> 'v

remove_exn htbl key tries to remove a binding of key to some before value from the hash table htbl. Returns the before value on success or raises Not_found if no such binding exists.

  • raises Not_found

    in case no binding of key exists in the hash table htbl.

Examining contents

Sourceval to_seq : ('k, 'v) t -> ('k * 'v) Seq.t

to_seq htbl takes a snapshot of the bindings in the hash table htbl and returns them as an association sequence.

🐌 This is a linear time operation.

Sourceval remove_all : ('k, 'v) t -> ('k * 'v) Seq.t

remove_all htbl takes a snapshot of the bindings in the hash table htbl, removes the bindings from the hash table, and returns the snapshot as an association sequence.

🐌 This is a linear time operation.

Sourceval find_random_exn : ('k, 'v) t -> 'k

find_random_exn htbl tries to find a random binding from the hash table htbl 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.

  • raises Not_found

    in case the hash table htbl is empty.

Examples

An example top-level session:

  # module Htbl = Picos_aux_htbl
  module Htbl = Picos_aux_htbl

  # let t : (int, string) Htbl.t =
      Htbl.create
        ~hashed_type:(module Int) ()
  val t : (int, string) Htbl.t = <abstr>

  # Htbl.try_add t 42 "The answer"
  - : bool = true

  # Htbl.try_add t 101 "Basics"
  - : bool = true

  # Htbl.find_exn t 42
  - : string = "The answer"

  # Htbl.try_add t 101 "The basics"
  - : bool = false

  # Htbl.remove_all t |> List.of_seq
  - : (int * string) list = [(101, "Basics"); (42, "The answer")]