skiplist

README

skiplist

Simple skip list for Go.

Sorted []byte key/value store with expected O(log n) operations.

Install

go get github.com/toastsandwich/skiplist

Usage

import "github.com/toastsandwich/skiplist"

s := skiplist.NewSkipList(0, 0) // defaults: max level 32, p 0.5

if err := s.Put([]byte("user:1"), []byte("Alice")); err != nil {
    // handle ErrNilKey, ErrNilVal, or ErrSkiplistFull
}

val, err := s.Get([]byte("user:1"))
if err == skiplist.ErrKeyNotFound {
    // missing key
}

for k, v := range s.All() {
    // sorted order
}

s.ForEach(func(k, v []byte) bool {
    return true // return false to stop early
})

if err := s.Pop([]byte("user:1")); err != nil {
    // handle ErrKeyNotFound or ErrNilKey
}

n := s.Len() // O(1) entry count

Pass 0 for either NewSkipList argument to use defaults. DefaultValues() returns those defaults explicitly: (32, 0.5).

Optional size limit

Set MaxLen on the list to cap how many distinct keys it holds. 0 means unlimited. Updates to existing keys still succeed when full; only new inserts return ErrSkiplistFull.

s := skiplist.NewSkipList(32, 0.5)
s.MaxLen = 1000

API

Method	Returns	Notes
Put(key, val)	error	Insert or update
Get(key)	([]byte, error)	Zero allocs on hit
Pop(key)	error	Remove by key
All()	iter.Seq2[[]byte, []byte]	Sorted iteration via range
ForEach(fn)	—	Callback iteration; return false to stop
Len()	int	Current entry count

Exported errors: ErrNilKey, ErrNilVal, ErrKeyNotFound, ErrSkiplistFull.

Not safe for concurrent use.

SyncSkipList (concurrent)

Use SyncSkipList when multiple goroutines hit the same map. It wraps the same logic with an RWMutex — many readers, one writer at a time.

s := skiplist.NewSyncSkipList(0, 0)

if err := s.Put([]byte("user:1"), []byte("Alice")); err != nil {
    // handle error
}

val, err := s.Get([]byte("user:1"))

if err := s.Pop([]byte("user:1")); err != nil {
    // handle error
}

n := s.Len() // int64

Ownership: Put takes the key and value slices. Do not reuse or mutate them after the call.

Method	Returns	Notes
Put(key, val)	error	Insert or update; takes slice ownership
Get(key)	([]byte, error)	Safe concurrent reads; zero allocs on hit
Pop(key)	error	Remove by key
Len()	int64	Current entry count
Cap()	int64	Max entries allowed

No All() or ForEach() on SyncSkipList yet.

How Skip Lists Work

A skip list is a sorted linked list with extra "express lane" layers on top.

Level 2: HEAD ----------------------> [50] ------------> NIL
Level 1: HEAD ----------> [20] --> [50] --> [80] --> NIL
Level 0: HEAD --> [10] --> [20] --> [50] --> [80] --> NIL

• Every element lives on level 0.
• On insert, a node is randomly assigned a height. With the default p=0.5:
  • ~50% stay at level 0
  • ~25% reach level 1
  • ~12.5% reach level 2, and so on
• Search starts at the highest level, skips forward while keys are smaller, then drops down levels.
• Higher levels act as shortcuts, giving expected O(log n) performance for put, get, and delete.

Benchmarks (heavy load)

# SkipList
go test -run=^$ -bench='BenchmarkSkipList' -benchmem -count=3 -benchtime=1s

# SyncSkipList
go test -run=^$ -bench='BenchmarkSyncSkipList' -benchmem -count=3 -benchtime=1s

SkipList (Intel Core i7-11800H)

Op	ns/op	allocs/op
Put	268	3
Get	244	0
Pop	572	4
PutGetMix	619	3

SyncSkipList (Apple M2)

Op	ns/op	allocs/op
Put	350	2
Get	260	0
Pop	625	0
PutGetMix	720	2

Notes for both:

• Get, Pop, and PutGetMix run against a preloaded list of 1M elements.
• Pop benchmark does pop + re-insert to keep size stable.

Get has zero allocations on hits for both types.

Charts

Three-way comparison of concurrent skip list implementations on Apple M2 (benchtime=1s, count=3). All use []byte keys (key-NNNNNNNN). MauriceGit is wrapped with sync.RWMutex; fast-skiplist uses its built-in mutex.

Head-to-head under parallel load: 100K preloaded keys (read-only) and 10K keys with mixed 33% Put / 33% Get / 33% Delete+reinsert.

License

MIT

Documentation

Overview

Package skiplist is a sorted []byte key/value store.

Put, Get, and Pop are O(log n) on average. Keys sort with bytes.Compare.

Use SkipList for single-threaded code. Use SyncSkipList when goroutines share the same map.

s := NewSkipList(0, 0) // defaults: max level 32, p 0.5
s.Put([]byte("a"), []byte("1"))
v, _ := s.Get([]byte("a"))
s.Pop([]byte("a"))
for k, v := range s.All() { _ = k; _ = v }

safe := NewSyncSkipList(0, 0)
safe.Put([]byte("a"), []byte("1"))
v, _ = safe.Get([]byte("a"))

SyncSkipList is the mutex-protected skip list.

Same operations as SkipList, safe to call from many goroutines. Put takes ownership of the key and value slices — do not use them after Put returns.

There is no All() or ForEach() yet; use Get in a loop or add your own iteration under RLock if you need a full scan.

Example

Example demonstrates basic usage of SkipList.

s := NewSkipList(16, 0.5)

s.Put([]byte("cat"), []byte("meow"))
s.Put([]byte("dog"), []byte("woof"))
s.Put([]byte("cat"), []byte("purr")) // update

if v, err := s.Get([]byte("cat")); err == nil {
	fmt.Println("cat ->", string(v))
}

fmt.Println("All entries:")
for k, v := range s.All() {
	fmt.Printf("  %s: %s\n", k, v)
}

s.Pop([]byte("dog"))
fmt.Println("After pop dog, len via iteration:")
count := 0
for range s.All() {
	count++
}
fmt.Println("count:", count)

Output:
cat -> purr
All entries:
  cat: purr
  dog: woof
After pop dog, len via iteration:
count: 1

Index

• Variables
• func DefaultValues() (int, float64)
• func MaxEntries(maxLevel int, p float64) int64
• func MaxLevelFor(n int64, p float64) int
• type Element
  • func (e *Element) Reset() *Element
  • func (e *Element) SetLevel(l int)
• type SkipList
  • func NewSkipList(maxlevel int, p float64) *SkipList
  • func (s *SkipList) All() iter.Seq2[[]byte, []byte]
  • func (s *SkipList) Cap() int64
  • func (s *SkipList) ForEach(do func(key, value []byte) bool)
  • func (s *SkipList) Get(key []byte) ([]byte, error)
  • func (s *SkipList) Len() int
  • func (s *SkipList) NewElement(key, val []byte, l int) *Element
  • func (s *SkipList) Pop(key []byte) error
  • func (s *SkipList) Put(key, val []byte) error
  • func (s *SkipList) Reset()
• type SyncSkipList
  • func NewSyncSkipList(maxlevel int, p float64) *SyncSkipList
  • func (s *SyncSkipList) Cap() int64
  • func (s *SyncSkipList) Get(key []byte) ([]byte, error)
  • func (s *SyncSkipList) Len() int64
  • func (s *SyncSkipList) Pop(key []byte) error
  • func (s *SyncSkipList) Put(key, val []byte) error
  • func (s *SyncSkipList) Reset()

Examples

• Package

Variables

var (
	ErrNilKey       = errors.New("key cannot be nil or zero len slice of byte")
	ErrNilVal       = errors.New("value cannot be nil or zero len slice of byte")
	ErrKeyNotFound  = errors.New("key not found")
	ErrSkiplistFull = errors.New("skip list is full")
)

Functions

func DefaultValues

func DefaultValues() (int, float64)

DefaultValues returns the default max level (32) and probability (0.5).

func MaxEntries

func MaxEntries(maxLevel int, p float64) int64

MaxEntries returns how many entries maxLevel and p can hold: (1/p)^maxLevel. For p=0.5 and maxLevel=32 this is 2^32.

func MaxLevelFor

func MaxLevelFor(n int64, p float64) int

MaxLevelFor returns the minimum max level needed for n entries at probability p: ceil(log_{1/p}(n)).

Types

type Element

type Element struct {
	Key, Value []byte
	Level      int
	// contains filtered or unexported fields
}

Element is one node in the list. Most callers use Put instead.

func (*Element) Reset

func (e *Element) Reset() *Element

func (*Element) SetLevel

func (e *Element) SetLevel(l int)

SetLevel sets the node height. Does not update links.

type SkipList

type SkipList struct {
	Header   *Element
	MaxLevel int
	P        float64

	// MaxLen is the max number of entries. 0 means unlimited.
	// Theoretical max at current MaxLevel and P is MaxEntries(MaxLevel, P).
	MaxLen int64
	// contains filtered or unexported fields
}

SkipList stores sorted []byte key/value pairs.

func NewSkipList

func NewSkipList(maxlevel int, p float64) *SkipList

NewSkipList creates a list. Pass 0 for either arg to use defaults (32, 0.5).

func (*SkipList) All

func (s *SkipList) All() iter.Seq2[[]byte, []byte]

All iterates key/value pairs in sorted order. Don't modify the list while ranging.

func (*SkipList) Cap

func (s *SkipList) Cap() int64

Capacity returns the enforced entry limit when MaxLen is set. When MaxLen is 0 (unlimited), returns MaxEntries(MaxLevel, P).

func (*SkipList) ForEach

func (s *SkipList) ForEach(do func(key, value []byte) bool)

ForEach walks all pairs in sorted order. Return false from do to stop early.

func (*SkipList) Get

func (s *SkipList) Get(key []byte) ([]byte, error)

Get returns the value for key. ErrKeyNotFound if missing, ErrNilKey if empty.

func (*SkipList) Len

func (s *SkipList) Len() int

Len returns the number of entries.

func (*SkipList) NewElement

func (s *SkipList) NewElement(key, val []byte, l int) *Element

NewElement builds a node with level l. Use Put for normal inserts.

func (*SkipList) Pop

func (s *SkipList) Pop(key []byte) error

Pop removes key. ErrKeyNotFound if missing, ErrNilKey if empty.

func (*SkipList) Put

func (s *SkipList) Put(key, val []byte) error

Put inserts or updates a key/value pair. ErrNilKey or ErrNilVal on empty input. ErrSkiplistFull if MaxLen is reached.

func (*SkipList) Reset

func (s *SkipList) Reset()

Reset the skiplist

type SyncSkipList

type SyncSkipList struct {
	Header *Element

	MaxLevel int
	P        float64

	MaxLen int64
	// contains filtered or unexported fields
}

SyncSkipList is a sorted []byte map safe for concurrent use.

func NewSyncSkipList

func NewSyncSkipList(maxlevel int, p float64) *SyncSkipList

NewSyncSkipList creates a concurrent skip list. Pass 0 for either argument to use defaults (32, 0.5). MaxLen is set to the theoretical max for those settings.

func (*SyncSkipList) Cap

func (s *SyncSkipList) Cap() int64

Cap returns the entry limit (MaxLen).

func (*SyncSkipList) Get

func (s *SyncSkipList) Get(key []byte) ([]byte, error)

Get returns the value for key. Safe for concurrent readers. Zero allocs on hit. Returns ErrKeyNotFound or ErrNilKey.

func (*SyncSkipList) Len

func (s *SyncSkipList) Len() int64

Len returns the number of entries.

func (*SyncSkipList) Pop

func (s *SyncSkipList) Pop(key []byte) error

Pop removes key. Returns ErrKeyNotFound or ErrNilKey.

func (*SyncSkipList) Put

func (s *SyncSkipList) Put(key, val []byte) error

Put inserts or updates a key/value pair. Takes ownership of key and val — do not read or write those slices afterward. Returns ErrNilKey, ErrNilVal, or ErrSkiplistFull.

func (*SyncSkipList) Reset

func (s *SyncSkipList) Reset()

Reset the skiplist