# package octez-libs

A skip list represents a sequence of values. There are three main differences between these `skip list`

s and OCaml standard `list`

s:

1. A skip list cannot be empty.

2. A skip list grows at its end.

3. Each cell of the skip list provides several back pointers allowing to *skip* chunk of ancestors of the sequence to directly jump to a given position. More precisely, given a `basis`

parameter, the i-th back pointers of element number `n`

in the sequence points to `n - n mod basis^i - 1`

. The element number `n`

in the sequence contains `log_basis n`

back pointers.

The skip list is defined by a pair of dereferencing function of type `'ptr -> ('content, 'ptr) cell`

and the last cell of the sequence. The maintainance of this pair is left to the client. In particular, the client is responsible to correctly bind a cell to each back pointers reachable from the last cell.

A cell in the skip list carrying a given `'content`

and back pointers of type `'ptr`

.

```
val pp :
pp_ptr:(Format.formatter -> 'ptr -> unit) ->
pp_content:(Format.formatter -> 'content -> unit) ->
Format.formatter ->
('content, 'ptr) cell ->
unit
```

```
val encoding :
'ptr Data_encoding.t ->
'content Data_encoding.t ->
('content, 'ptr) cell Data_encoding.t
```

`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_result = {`

`rev_path : ('ptr, 'content) cell list;`

`last_cell : ('ptr, 'content) search_cell_result;`

`}`

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

.

```
val search :
deref:('ptr -> ('content, 'ptr) cell option) ->
compare:('content -> int) ->
cell:('content, 'ptr) cell ->
('content, 'ptr) search_result
```

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