Crate skippy

A highly flexible, non-amortized worst-case O(log n) intrusive skip list.

The skip list can be used both as a sorted sequence (allowing it to be used as a set or map) and as an unsorted sequence of elements in arbitrary order (allowing it to be used as a vector/dynamic array). Elements support an optional notion of “size”, allowing insertions, removals, and lookups by index, as well as, due to the intrusive nature of the skip list, the ability to query an element’s index.

Internal nodes in the skip list are allocated deterministically so that between any two consecutive nodes at layer L, there are always between F / 2 and F nodes at layer L - 1, where F is a configurable fanout parameter. This is very similar to a B+ tree; in fact, this skip list is essentially a B+ tree where children are stored in linked lists rather than arrays.

Crate features

If the crate feature allocator_api is enabled, the skip list can be configured with the unstable Allocator trait. Otherwise, allocator-fallback will be used.

This crate can be used in no_std contexts by disabling the std feature.

Re-exports

pub use options::LeafSize;

pub use options::ListOptions;

pub use options::NoSize;

pub use options::Options;

Modules

basic

“Basic” implementations of LeafRef that store data of a given type.

iter

Skip list iterators.

options

Skip list options.

Structs

AllocItem

A type equal in size and alignment to the blocks of memory that SkipList allocates internally.

SkipList

A flexible intrusive skip list with worst-case non-amortized O(log n) operations.

This

A wrapper around a method’s self parameter.

Enums

LeafNext

The item/data that can be stored and retrieved with LeafRef::set_next and LeafRef::next.

Traits

LeafRef

Represents a reference to an item, or “leaf”, in a SkipList.