Legend:
Library
Module
Module type
Parameter
Class
Class type
A skip list represents a sequence of values. There are three main differences between these skip lists and OCaml standard lists:
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.
type('content, 'ptr) cell
A cell in the skip list carrying a given 'content and back pointers of type 'ptr.
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.
val back_path :
deref:('ptr->('content, 'ptr)cell option)->cell_ptr:'ptr->target_index:int ->'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 and the path is minimal.
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 the minimal path from cell to lower.