# 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|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:

```c
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:

| Flag                       | Default   | Purpose                                                 |
|----------------------------|-----------|---------------------------------------------------------|
| `SKIPLIST_SINGLE_THREADED` | undefined | replace atomics with plain ops; drop `<stdatomic.h>`    |
| `SKIPLIST_SPLAY_REBALANCE` | undefined | adaptive height adjustment                              |
| `SKIPLIST_MAX_HEIGHT`      | 64        | maximum tower height (≤64)                              |
| `SKIPLIST_SPLAY_INTERVAL`  | 64        | accesses between rebalance passes (power of 2)          |
| `SKIPLIST_EBR_MAX_THREADS` | 128       | maximum concurrent EBR-registered threads               |

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:

| Operation                        | Throughput        | Latency  |
|----------------------------------|-------------------|----------|
| Sequential insert                | 611,852 ops/s     | 1,634 ns |
| Random insert                    | 168,695 ops/s     | 5,928 ns |
| Sequential search (hit)          | 1,722,553 ops/s   | 580 ns   |
| Forward iteration                | 22,300,984 ops/s  | 45 ns    |
| Pool insert (sequential)         | 1,526,033 ops/s   | 655 ns   |
| Concurrent insert (8 threads)    | 650,791 ops/s     | 1,537 ns |

## 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](https://codeberg.org/gregburd/skiplist) — ISC OR MIT.