package octez-l2-libs

  1. Overview
  2. Docs
Octez layer2 libraries

Install 

dune-project
 Dependency

www.tezos.com Readme Edit opam file Versions (5)

Authors

  1. T
    Tezos devteam
  2. W
    WebAssembly Authors

Maintainers

  1. C
    contact@tezos.com

Sources

octez-19.1.tar.gz
sha256=55ea1fb8bb3273a7fc270ca8f650d45c56449665619482aad9bc12f3ea736b7e
sha512=fec850fc2d17d7490bbabd5147d62aad13b3aaed8774270f8a38ab419670ed03e0fd30cf8642a97984eca5c2446726fe590ad99c015f7ec50919dc7652f25053

doc/octez-l2-libs.smart-rollup/Octez_smart_rollup/Inbox/Skip_list/index.html

Module Inbox.Skip_listSource

Sourcetype ('content, 'ptr) cell

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

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

index cell returns the position of cell in the sequence.

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

content cell is the content carried by the cell.

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

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

back_pointers cell returns the back pointers of cell.

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

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

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

Sourcetype ('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
Sourcetype ('ptr, 'content) search_result = {
  1. rev_path : ('ptr, 'content) cell list;
  2. last_cell : ('ptr, 'content) search_cell_result;
}
Sourceval pp_search_result : pp_cell:(Format.formatter -> ('ptr, 'content) cell -> unit) -> Format.formatter -> ('ptr, 'content) search_result -> unit
Sourcemodule type MONADIC = sig ... end

Functions in the empty monad are accessible directly.

include MONADIC with type 'a result := 'a
Sourceval 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.

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

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