package kcas_data

  1. Overview
  2. Docs

Module Kcas_data.DllistSource

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:

  • The sequence iterators, e.g. iter_l, iter_node_l, fold_l, find_node_opt_l, and find_node_l, are not provided.
  • The length operation is not provided.
  • The set operation is not provided.

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

Sourcetype !'a t

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

Sourcetype !'a node

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

Sourceval get : 'a node -> 'a

get node returns the value stored in the node.

Sourceval create : unit -> 'a t

create () return a new doubly-linked list.

Compositional interface

Sourcemodule Xt : sig ... end

Explicit transaction log passing on doubly-linked lists.

Non-compositional interface

Sourceval remove : 'a node -> unit

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

Sourceval is_empty : 'a t -> bool

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

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval take_blocking_l : '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.

Sourceval take_blocking_r : '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.

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

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

Sourceval transfer_l : 'a t -> 'a t -> unit

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

Sourceval transfer_r : 'a t -> 'a t -> unit

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

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceexception Empty

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

Sourceval 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.

Sourceval 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.