Skip to content

Instantly share code, notes, and snippets.

@pacuna
Created October 3, 2020 23:17
Show Gist options
  • Save pacuna/cafbfcc46207d2ec60eebd610d4ea112 to your computer and use it in GitHub Desktop.
Save pacuna/cafbfcc46207d2ec60eebd610d4ea112 to your computer and use it in GitHub Desktop.
SkipList in Go (from original paper)
// 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
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment