Module Kcas_data.Dllist

Doubly-linked list.

The interface provides a subset of the operations of the doubly-linked list data structure provided by the lwt-dllist package with some omissions:

A non-compositional take_all operation is added for privatization as well as conversions to a list of nodes (to_nodes_l and to_nodes_r) and to a list of values (to_list_l and to_list_r).

Probably the main reason to use a doubly-linked list like this rather than e.g. a 'a list Loc.t is the ability to remove a node without having to potentially iterate through the list:

let node_of_x = add_l x list in
(* ... and then later somewhere else ... *)
remove node_of_x

A doubly-linked list can also be used as a deque or double-ended queue, but a deque implementation that doesn't allow individual nodes to be removed is likely to be faster.

Common interface

type !'a t

Type of a doubly-linked list containing nodes of type 'a.

type !'a node

Type of a node containing a value of type 'a.

val create : unit -> 'a t

create () creates a new doubly-linked list.

Operations on nodes

val create_node : 'a -> 'a node

create_node value creates a new doubly-linked list node that is not in any list. The node can then e.g. be added to a list using move_l or move_r.

val get : 'a node -> 'a

get node returns the value stored in the node.

Compositional interface

module Xt : sig ... end

Explicit transaction log passing on doubly-linked lists.

Non-compositional interface

Operations on nodes

val remove : 'a node -> unit

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

val move_l : '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 : '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 : '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 : '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 : '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 : '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 : '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 : ?timeoutf:float -> '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 : ?timeoutf:float -> '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 : 'a t -> 'a t -> unit

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

val transfer_l : '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 : '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 : '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 : '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 : '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 : '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.

val take_all : 'a t -> 'a t

take_all l removes all nodes of the doubly-linked list l and returns a new doubly-linked list containing the removed nodes.

exception Empty

Raised when take_l or take_r is applied to an empty doubly-linked list.

val take_l : 'a t -> 'a

take_l l removes and returns the value of the leftmost node of the doubly-linked list l, or raises Empty if the list is empty.

  • raises Empty

    if the list is empty.

val take_r : 'a t -> 'a

take_r l removes and returns the value of the rightmost node of the doubly-linked list l, or raises Empty if the list is empty.

  • raises Empty

    if the list is empty.