Module Kcas

type 'a ref

Type of shared memory reference

type t

Type of compare and swap value

type 'a cas_result =
  1. | Aborted
  2. | Failed
  3. | Success of 'a

The type of CAS result.

val ref : 'a -> 'a ref

ref x returns a reference on a shared memory ceils containing the value x

val equal : 'a ref -> 'b ref -> bool
val is_on_ref : t -> 'a ref -> bool
val mk_cas : 'a ref -> 'a -> 'a -> t

mk_cas a o n returns a new CAS value, which when performed, updates the reference a to n if the current content of a is o

val set : 'a ref -> 'a -> unit

set r n updates the reference r to value n directly. Not Safe to use with shared memory !

val cas : 'a ref -> 'a -> 'a -> bool

cas r e u updates the reference r to value u if the current content of r is e.

val commit : t -> bool

commit c performs the CAS c and returns true if the CAS is successful.

val kCAS : t list -> bool

kCAS l performs a lock-free multi-word CAS and returns true if the multi-word CAS is successful.

kCAS requires ref of provided operations to follow a global total order. To eliminate a class of bugs kCAS presorts provided operations. If the operations are given in either ascending or descending order of get_id then the presort is done in linear time O(n). Otherwise presort may take linearithmic time O(n log n).

val get : 'a ref -> 'a

get a reads the value contained in reference a.

val get_id : 'a ref -> int

get_id a returns the unique id of the reference a.

val try_map : 'a ref -> ('a -> 'a option) -> 'a cas_result

try_map r f invokes f c, where c is the result of get r. If the result of f c is None, then Aborted is returned. If the result of f c is Some v, then attempt to CAS update r from c to v. If the CAS succeeds, then Success c is returned. If the CAS fails, then Failed is returned.

val map : 'a ref -> ('a -> 'a option) -> 'a cas_result

Like try_map but retries on CAS failure. Hence, map r f never returns Failed.

val incr : int ref -> unit

incr r atomically increments r

val decr : int ref -> unit

decr r atomically decrements r

module type Backoff = sig ... end
module Backoff : Backoff
module type W1 = sig ... end
module W1 : W1