Crate skiplist [] [src]

A skiplist is a way of storing elements in such a way that elements can be efficiently accessed, inserted and removed, all in O(log(n)) on average.

Conceptually, a skiplist resembles something like:

<head> ----------> [2] --------------------------------------------------> [9] ---------->
<head> ----------> [2] ------------------------------------[7] ----------> [9] ---------->
<head> ----------> [2] ----------> [4] ------------------> [7] ----------> [9] --> [10] ->
<head> --> [1] --> [2] --> [3] --> [4] --> [5] --> [6] --> [7] --> [8] --> [9] --> [10] ->

where we each node [x] has references to nodes further down the list, allowing the algorithm to effectively skip ahead.

The ordered skiplist has an associated sorting function which must be well-behaved. Specifically, given some ordering function f(a, b), it must satisfy the folowing properties:

Failure to satisfy these properties can result in unexpected behaviour at best, and at worst will cause a segfault, null deref, or some other bad behaviour.

Reexports

pub use ordered_skiplist::OrderedSkipList;
pub use skipmap::SkipMap;
pub use skiplist::SkipList;

Modules

ordered_skiplist
skiplist
skipmap