Module Kcas_data.Queue

First-In First-Out (FIFO) queue.

The interface provides a subset of the OCaml Stdlib.Queue module. transfer and add_seq are not provided at all. Compositional versions of iter, fold, peek, top, and take are not provided.

The queue implementation is designed to avoid contention between a producer and a consumer operating concurrently. The implementation is also designed to avoid starvation. Performance in most concurrent use cases should be superior to what can be achieved with one or two locks.

Common interface

type !'a t

The type of queues containing elements of type 'a.

exception Empty

Raised when take or peek is applied to an empty queue.

val create : unit -> 'a t

create () returns a new empty queue.

val copy : 'a t -> 'a t

copy q returns a copy of the queue q.

Compositional interfaces

module Tx : sig ... end

Transactions on queues.

module Xt : sig ... end

Explicit transaction log passing on queues.

Non-compositional interface

val is_empty : 'a t -> bool

is_empty s determines whether the queue q is empty.

val length : 'a t -> int

length q returns the length of the queue q.

val clear : 'a t -> unit

clear q removes all elements from the queue q.

val swap : 'a t -> 'a t -> unit

swap q1 q2 exchanges the contents of the queues q1 and q2.

val to_seq : 'a t -> 'a Stdlib.Seq.t

to_seq s returns a domain safe sequence for iterating through the elements of the queue front to back.

The sequence is based on a constant time, O(1), snapshot of the queue and modifications of the queue have no effect on the sequence.

val add : 'a -> 'a t -> unit

add q x adds the element x at the end of the queue q.

val push : 'a -> 'a t -> unit

push is a synonym for add.

val peek_opt : 'a t -> 'a option

peek_opt q returns the first element in queue q, without removing it from the queue, or returns None if the queue is empty.

val take_opt : 'a t -> 'a option

take_opt q removes and returns the first element in queue q, or returns None if the queue is empty.

val peek : 'a t -> 'a

peek q returns the first element in queue s, or raises Empty if the queue is empty.

val top : 'a t -> 'a

top is a synonym for peek.

val take : 'a t -> 'a

take s removes and returns the first element in queue q, or raises Empty if the queue is empty.

val iter : ('a -> unit) -> 'a t -> unit

iter f s is equivalent to Seq.iter f (to_seq s).

val fold : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b

fold f s is equivalent to Seq.fold_left f a (to_seq s).