Hopscotch - Skip list implemented in Rust

What it says. Cuz it skips.

Motivation

Note this is a toy project and is not meant for production usage...yet(?). It's primary purpose will be as part of a database internals teaching project.

Details

The implementation of the algorithms in v1 adheres somewhat faithfully to the algorithms as laid out in the original paper by Pugh.

Uses a geometric distribution for determining if a new key is part of a level (fancy for saying we flip a coin). The geometric distrubution actually defaults to p = 0.25 but this is configurable.

Concurrency

NOTE: There may be a measure of undefined behavior here (sounds bad I know). Don't use this unless you really want to try some crazy hack I did.

A version of the skip list that allows for lock-free concurrent reads is now available by turning on the concurrent feature. This skip list has a couple major feature gaps:

1. Callers must get a lock (e.g. Mutex or RwLock) over the skip list before insertions can be done.

2. Delete has not been implemented yet because my use case does not require delete.

Work is planned to follow this up with a proper implementation of a fully concurrent and almost-lock-free skip list.

Other art

• subway
• rust-skiplist
• crossbeam-skiplist

References

• Blog - Notes and References on Skip Lists
• OpenDSA - 15.1 Skip Lists
• Learn Rust With Entirely Too Many Linked Lists
• Advanced Lifetimes
• std::linked_list
• Great reference on creating an iterator in Rust: Creating an Iterator in Rust