package tezos-protocol-016-PtMumbai

  1. Overview
  2. Docs
package tezos-protocol-016-PtMumbai
Legend:
Library
Module
Module type
Parameter
Class
Class type

Parameters

module _ : sig ... end

Signature

type ('content, 'ptr) cell

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

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

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: (Tezos_protocol_environment_016_PtMumbai.Format.formatter -> ('ptr, 'content) cell -> unit) -> Tezos_protocol_environment_016_PtMumbai.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:Tezos_protocol_environment_016_PtMumbai.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:Tezos_protocol_environment_016_PtMumbai.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.

This module contains functions in the Lwt monad.

module Make_monadic (M : MONAD) : MONADIC with type 'a result := 'a M.t

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

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct