Module Lockfree.Queue

Michael-Scott classic multi-producer multi-consumer queue.

All functions are lockfree. It is the recommended starting point when needing FIFO structure. It is inspired by Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms.

type 'a t

The type of lock-free queue.

val create : unit -> 'a t

create () returns a new queue, initially empty.

val is_empty : 'a t -> bool

is_empty q returns empty if q is empty.

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

push q v adds the element v at the end of the queue q.

val pop : 'a t -> 'a option

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

val clean_until : 'a t -> ('a -> bool) -> unit

clean_until q f drops the prefix of the queue until the element e, where f e is true. If no such element exists, then the queue is emptied.

type 'a cursor

The type of cursor.

val snapshot : 'a t -> 'a cursor

Obtain a snapshot of the queue. This is a constant time operation.

val next : 'a cursor -> ('a * 'a cursor) option

next c returns Some (e, c') where e is the head of the queue and c' is the tail, if the queue is non-empty. Otherwise, returns None.