Module Inbox.Skip_list

type ('content, 'ptr) cell

A cell in the skip list carrying a given 'content and back pointers of type 'ptr.

val pp : pp_ptr:(Stdlib.Format.formatter -> 'ptr -> unit) -> pp_content:(Stdlib.Format.formatter -> 'content -> unit) -> Stdlib.Format.formatter -> ('content, 'ptr) cell -> unit
val equal : ('ptr -> 'ptr -> bool) -> ('content -> 'content -> bool) -> ('content, 'ptr) cell -> ('content, 'ptr) cell -> bool
val encoding : 'ptr Data_encoding.t -> 'content Data_encoding.t -> ('content, 'ptr) cell Data_encoding.t
val index : (_, _) cell -> Z.t

index cell returns the position of cell in the sequence.

val content : ('content, 'ptr) cell -> 'content

content cell is the content carried by the cell.

val back_pointer : ('content, 'ptr) cell -> int -> 'ptr option

back_pointer cell i returns Some ptr if ptr is the i-th back pointer of cell. Returns None if the cell contains less than i + 1 back pointers.

val back_pointers : ('content, 'ptr) cell -> 'ptr list

back_pointers cell returns the back pointers of cell.

val genesis : 'content -> ('content, 'ptr) cell

genesis content is the first cell of a skip list. It has no back pointers.

val next : prev_cell:('content, 'ptr) cell -> prev_cell_ptr:'ptr -> 'content -> ('content, 'ptr) cell

next ~prev_cell ~prev_cell_ptr content creates a new cell that carries some content, that follows prev_cell.

type ('ptr, 'content) search_cell_result =
  1. | Found of ('ptr, 'content) cell
  2. | Nearest of {
    1. lower : ('ptr, 'content) cell;
    2. upper : ('ptr, 'content) cell option;
    }
  3. | No_exact_or_lower_ptr
  4. | Deref_returned_none
type ('ptr, 'content) search_result = {
  1. rev_path : ('ptr, 'content) cell list;
  2. last_cell : ('ptr, 'content) search_cell_result;
}
val pp_search_result : pp_cell:(Stdlib.Format.formatter -> ('ptr, 'content) cell -> unit) -> Stdlib.Format.formatter -> ('ptr, 'content) search_result -> unit
module type MONADIC = sig ... end

Functions in the empty monad are accessible directly.

include MONADIC with type 'a result := 'a
val find : deref:('ptr -> ('content, 'ptr) cell option) -> cell_ptr:'ptr -> target_index:Z.t -> ('content, 'ptr) cell option

find ~deref ~cell_ptr ~target_index returns Some cell where cell is the cell at position target_index. This is done by dereferencing the last pointer of the path returned by back_path.

val back_path : deref:('ptr -> ('content, 'ptr) cell option) -> cell_ptr:'ptr -> target_index:Z.t -> 'ptr list option

back_path ~deref ~cell_ptr ~target_index returns Some path where path is a sequence of back pointers to traverse to go from cell_ptr to the cell at position target_index in the sequence denoted by (deref, cell_ptr).

val valid_back_path : equal_ptr:('ptr -> 'ptr -> bool) -> deref:('ptr -> ('content, 'ptr) cell option) -> cell_ptr:'ptr -> target_ptr:'ptr -> 'ptr list -> bool

valid_back_path ~equal_ptr ~deref ~cell_ptr ~target_ptr path returns true iff path is a valid and minimal path from cell_ptr to target_ptr in the skip list denoted by (deref, cell_ptr).

search ~deref ~compare ~cell allows to find a cell of the skip list according to its content. This function assumes that the content of the cells is in increasing order according to the ordering defined by the function compare. In other words, this function assumes that compare is a function that returns a negative integer for cells before the target and a positive integer for cells after the target. The value returned by this function is {rev_path; last_cell} such that.

  • rev_path = [] if and only if compare (content cell) > 0
  • For all the cases below, if there is a path from cell A to cell B, rev_path contains the list of cells to go from B to A. Consequently, the first element of rev_path is B. Except for Nearest_lower, this path is a minimal path.
  • last_pointer = Deref_returned_none if deref fails to associate a cell to a pointer during the search. In that case, rev_path is a path from cell to candidate where candidate is the last cell for which candidate did not fail and such that compare (content (candidate)) > 0.
  • last_pointer = No_exact_or_lower_ptr if for all cell of the skip list, compare (content cell) > 0. In that case, rev_path is a path from cell to the genesis cell.
  • last_pointer = Found target if there is a cell target such that compare (content target) = 0 and a path from cell to target. In that case, rev_path is the minimal path from cell to target.
  • last_pointer = Nearest_lower {lower;upper} if there is no cell in the skip list such that compare (content cell) = 0. In that case lower is the unique cell such that compare (content lower) < 0 and for all other cells candidate such that compare (content candidate) < 0 then there is a path from lower to candidate. upper, if it exists is the successor cell to lower, i.e. deref ((back_pointer upper) 0) = Some lower. In that case, rev_path is a path from cell to lower. This path is *NOT* minimal but almost. The path is minimal from cell to upper=Some up. By minimality, the path is logarithmic. Consequently, since there is a direct pointer from up to lower, the passe to lower is also logarithmic.

If a target cell target_cell exists, i.e. there is a cell such that compare target_cell = 0, then it is not necessary for deref to return Some cell for all cell such that compare cell < 0. If a target_cell does not exist, the lowest bound for which deref must return Some cell is unknown.

module Lwt : MONADIC with type 'a result := 'a Lwt.t

This module contains functions in the Lwt monad.

This functor can be used to build monadic functions for the skip list.