Module Dllist.Xt

Explicit transaction log passing on doubly-linked lists.

Operations on nodes

val remove : xt:'x Kcas.Xt.t -> 'a node -> unit

remove n removes the node n from the doubly-linked list it is part of. remove is idempotent.

val move_l : xt:'x Kcas.Xt.t -> 'a node -> 'a t -> unit

move_l n l removes the node n from the doubly-linked list it is part of and then adds it to the left of the list l.

val move_r : xt:'x Kcas.Xt.t -> 'a node -> 'a t -> unit

move_r n l removes the node n from the doubly-linked list it is part of and then adds it to the right of the list l.

Operations on lists

val is_empty : xt:'x Kcas.Xt.t -> 'a t -> bool

is_empty l determines whether the doubly-linked list l is empty or not.

Adding or removing values at the ends of a list

val add_l : xt:'x Kcas.Xt.t -> 'a -> 'a t -> 'a node

add_l v l creates and returns a new node with the value v and adds the node to the left of the doubly-linked list l.

val add_r : xt:'x Kcas.Xt.t -> 'a -> 'a t -> 'a node

add_r v l creates and returns a new node with the value v and adds the node to the right of the doubly-linked list l.

val take_opt_l : xt:'x Kcas.Xt.t -> 'a t -> 'a option

take_opt_l l removes and returns the value of leftmost node of the doubly-linked list l, or return None if the list is empty.

val take_opt_r : xt:'x Kcas.Xt.t -> 'a t -> 'a option

take_opt_r l removes and returns the value of rightmost node of the doubly-linked list l, or return None if the list is empty.

val take_blocking_l : xt:'x Kcas.Xt.t -> 'a t -> 'a

take_blocking_l l removes and returns the value of leftmost node of the doubly-linked list l, or blocks waiting for the list to become non-empty.

val take_blocking_r : xt:'x Kcas.Xt.t -> 'a t -> 'a

take_blocking_r l removes and returns the value of rightmost node of the doubly-linked list l, or blocks waiting for the list to become non-empty.

Moving all nodes between lists

val swap : xt:'x Kcas.Xt.t -> 'a t -> 'a t -> unit

swap l1 l2 exchanges the nodes of the doubly-linked lists l1 and l2.

val transfer_l : xt:'x Kcas.Xt.t -> 'a t -> 'a t -> unit

transfer_l l1 l2 removes all nodes of l1 and adds them to the left of l2.

val transfer_r : xt:'x Kcas.Xt.t -> 'a t -> 'a t -> unit

transfer_r l1 l2 removes all nodes of l1 and adds them to the right of l2.

Extracting all values or nodes from a list

val to_list_l : xt:'x Kcas.Xt.t -> 'a t -> 'a list

to_list_l l collects the values of the nodes of the doubly-linked list l to a list in left-to-right order.

NOTE: This operation is linear time, O(n), and should typically be avoided unless the list is privatized, e.g. by using take_all.

val to_list_r : xt:'x Kcas.Xt.t -> 'a t -> 'a list

to_list_r l collects the values of the nodes of the doubly-linked list l to a list in right-to-left order.

NOTE: This operation is linear time, O(n), and should typically be avoided unless the list is privatized, e.g. by using take_all.

val to_nodes_l : xt:'x Kcas.Xt.t -> 'a t -> 'a node list

to_nodes_l l collects the nodes of the doubly-linked list l to a list in left-to-right order.

NOTE: This operation is linear time, O(n), and should typically be avoided unless the list is privatized, e.g. by using take_all.

val to_nodes_r : xt:'x Kcas.Xt.t -> 'a t -> 'a node list

to_nodes_r l collects the nodes of the doubly-linked list l to a list in right-to-left order.

NOTE: This operation is linear time, O(n), and should typically be avoided unless the list is privatized, e.g. by using take_all.