SkipList in Go (from original paper)

skiplist.go

// Implementation of a SkipList using the original paper's algorithm:
// https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf
//
// Example usage:
// sl := db.NewSkipList()
// sl.Insert([]byte("foo"), []byte("bar"))
// sl.Insert([]byte("foo"), []byte("world"))
// fmt.Println(string(sl.Search([]byte("foo"))))
//
package db

import (
	"bytes"
	"math"
	"math/rand"
)

const (
	MaxLevel = 12
	P        = .5
)

type Node struct {
	key     []byte
	value   []byte
	forward []*Node
}

type SkipList struct {
	level  int
	header *Node
}

func NewSkipList() *SkipList {
	nn := &Node{
		key:     []byte{math.MaxUint8, math.MaxUint8, math.MaxUint8, math.MaxUint8}, //MaxValue example for this type
		forward: make([]*Node, MaxLevel),
	}

	hf := make([]*Node, MaxLevel)
	for i := 0; i < MaxLevel; i++ {
		hf[i] = nn
	}

	return &SkipList{
		level: 0,
		header: &Node{
			key:     nil,
			forward: hf,
		},
	}
}

func randomLevel() int {
	lvl := 0
	for rand.Float64() < P && lvl < MaxLevel {
		lvl += 1
	}
	return lvl
}

func (sl *SkipList) Insert(k, v []byte) {
	update := make([]*Node, MaxLevel)
	x := sl.header
	for i := sl.level; i >= 0; i-- {
		for bytes.Compare(x.forward[i].key, k) < 0 {
			x = x.forward[i]
		}
		update[i] = x
	}
	x = x.forward[0]
	if bytes.Compare(x.key, k) == 0 {
		x.value = v
	} else {
		lvl := randomLevel()
		if lvl > sl.level {
			for i := sl.level + 1; i <= lvl; i++ {
				update[i] = sl.header
			}
			sl.level = lvl
		}
		x = &Node{
			key:     k,
			value:   v,
			forward: make([]*Node, MaxLevel),
		}
		for i := 0; i <= lvl; i++ {
			x.forward[i] = update[i].forward[i]
			update[i].forward[i] = x
		}
	}
}

func (sl *SkipList) Contains(k []byte) bool {
	x := sl.header
	for i := sl.level; i >= 0; i-- {
		for bytes.Compare(x.forward[i].key, k) < 0 {
			x = x.forward[i]
		}
	}
	x = x.forward[0]
	if bytes.Compare(x.key, k) == 0 {
		return true
	}
	return false
}

func (sl *SkipList) Search(k []byte) []byte {
	x := sl.header
	for i := sl.level; i >= 0; i-- {
		for bytes.Compare(x.forward[i].key, k) < 0 {
			x = x.forward[i]
		}
	}
	x = x.forward[0]
	if bytes.Compare(x.key, k) == 0 {
		return x.value
	}
	return nil
}

func (sl *SkipList) Delete(k []byte) {
	update := make([]*Node, MaxLevel)
	x := sl.header
	for i := sl.level; i >= 0; i-- {
		for bytes.Compare(x.forward[i].key, k) < 0 {
			x = x.forward[i]
		}
		update[i] = x
	}
	x = x.forward[0]
	if bytes.Compare(x.key, k) == 0 {
		for i := 0; i <= sl.level; i++ {
			if update[i].forward[i] != x {
				break
			}
			update[i].forward[i] = x.forward[i]
		}
		for sl.level > 0 && sl.header.forward[sl.level] == nil {
			sl.level -= 1
		}
	}
}