Lib.rs

› Algorithms
#skip-list #sorting #collection #node-index

stable-skiplist

Skiplist implementation in rust, providing fast insertion and removal. A normal skiplist is implemented, as well as an ordered skiplist and a skipmap. This is modified to work on stable Rust 1.9.0.

by Robert O'Callahan, JP-Ellis

2 releases

Uses old Rust 2015

0.1.1 Jul 7, 2016
0.1.0 Jul 7, 2016

#4 in #node-index

MIT license

200KB
4K SLoC

Rust Stable Skiplist

A skiplist provides a way of storing data with log(i) access, insertion and removal for an element in the ith position.

There are three kinds of collections defined here:

  • SkipList This behaves like nearly any other double-ended list.
  • OrderedSkipList Ensures that the elements are always sorted. Still allows for access nodes at a given index.
  • SkipMap A map in which the keys are ordered.

Documentation here.

This was forked from https://github.com/JP-Ellis/rust-skiplist and modified to use its own version of Bound, so that its range methods are usable with stable Rust.

lib.rs:

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:

  • Be well defined: f(a, b) should always return the same value
  • Be anti-symmetric: f(a, b) == Greater iff f(b, a) == Less and f(a, b) == Equal == f(b, a).
  • By transitive: If f(a, b) == Greater and f(b, c) == Greater then f(a, c) == Greater.

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.

Dependencies

~320–540KB