skiplist

Header-only C library implementing a concurrent lock-free skip-list — specifically a splay-list, a skip-list with optional adaptive rebalancing that promotes hot keys toward the top. The entire implementation lives in preprocessor macros inside include/sl.h, generating type-specific code at compile time the same way C++ templates do, but without function dispatch or void pointers. Written by Gregory Burd; dual-licensed ISC or MIT.

How it works

The core algorithm is Fraser/Harris: insert by CAS at level 0 then opportunistically link upper levels, delete by marking the lowest bit of a forward pointer (logical delete) then unlinking (physical delete), use epoch-based reclamation (EBR) so readers don't observe freed memory. Level 0 is a doubly-linked list, which gives O(1) bidirectional iteration instead of the O(log n) reverse walks plain skip lists need.

Splay rebalancing is opt-in via SKIPLIST_SPLAY_REBALANCE. Based on Aksenov et al. 2020 — a node with hit ratio u/T settles at height K − 1 − log₂(T/u), so a key accessed 50% of the time ends up at depth 1. Search cost goes from O(log n) to O(log(1/p)) for hot keys. The rebalance pass fires only on read-only paths (search, contains, position queries). It never fires on remove, because promoting a soon-to-be-deleted node leaves dangling upper-level references after EBR reclaims it.

The README is careful about what splay does not buy: "This does not make a splay-list as fast as a B+tree" — the cache-line layout is wrong for that, even with the height optimization. The point is to make hot-key lookups within a skip list faster, not to outrun a different data structure.

API layout

The library is a stack of independent macro generators — pick the ones you need:

SKIPLIST_ENTRY(typename)        // embed in your node struct
SKIPLIST_DECL(...)              // core: init, insert, remove, search
SKIPLIST_DECL_ACCESS(...)       // high-level key/value interface
SKIPLIST_DECL_SNAPSHOTS(...)    // MVCC point-in-time snapshots
SKIPLIST_DECL_EBR(...)          // epoch-based reclamation
SKIPLIST_DECL_POOL(...)         // fixed-capacity cache-line-aligned pool allocator
SKIPLIST_DECL_ARCHIVE(...)      // binary serialization
SKIPLIST_DECL_VALIDATE(...)     // runtime integrity checks
SKIPLIST_DECL_DOT(...)          // GraphViz visualization

Compile-time knobs:

Single-threaded mode is roughly 30% faster than lock-free mode on tight loops because the atomic loads and CAS are gone. The pool allocator on top of that doubles to triples sequential insert throughput.

Indicative performance

x86_64, N=100k, gcc 13 -O2:

Other features

MVCC snapshots give point-in-time captures with restore. Binary serialization uses user-defined per-node handlers — no built-in opinion on what your nodes look like. Validation and DOT visualization make integrity checks and debugging direct.

Tests cover 97% line / 99% function / 58% branch on the implementation surface: 33 unit tests under ASan/LSan/UBSan, 7 concurrent tests under ThreadSanitizer, 6 single-threaded mode tests, Valgrind leak checking, plus an empirical test that reproduces the Aksenov 2020 paper's height-target predictions across different access distributions. Three build systems ship in the repo (plain Make, autoconf, Meson).

Where it fits

The MemTable in an lsm-tree is the classic in-memory sorted structure that wants O(log n) inserts and ordered iteration — skip lists and red-black trees are the two usual choices. RocksDB and LevelDB both use skip lists there. A lock-free implementation with a doubly-linked level 0 (cheap reverse scans) and optional MVCC snapshots is a natural fit for the MemTable + read-side snapshot pattern those engines already use. The single-threaded mode is interesting in its own right — many embedded use cases (config stores, DSL runtimes, in-process caches) don't need lock-free but do want ordered iteration and a small footprint.

Repo

codeberg.org/gregburd/skiplist — ISC OR MIT.