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.
val equal :
('content->'content-> bool)->('ptr->'ptr-> bool)->('content, 'ptr)cell->('content, 'ptr)cell->
bool
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).