skiplist

README

Skip List

probabilistic, mutable list-based data structure

---

Package skiplist implements a probabilistic, mutable list-based data structure that are a simple and efficient substitute for balanced trees. The algorithm is well depicted by the article.

Inspiration

The library provides generic implementation of

• skiplist.Set[K] ordered set of elements
• skiplist.Map[K] ordered set of key, value pairs
• skiplist.GF2[K] finite field on modulo 2

For each of the data type it standardize interfaces around

// Set behavior trait
type Set[K skiplist.Key] interface {
  Add(K) bool
  Has(K) bool
  Cut(K) bool
  Values(K) *Element[K]
  Successors(K) *Element[K]
  Split(K) Set[K]
}

// Map (Key, Value) pairs behavior trait
type Map[K skiplist.Key, V any] interface {
  Put(K, V) bool
  Get(K) (V, bool)
  Cut(K) (V, bool)
  Keys(K) *Element[K]
  Successors(K) *Element[K]
  Split(K) Map[K, V]
}

Installing

The latest version of the library is available at main branch. All development, including new features and bug fixes, take place on the main branch using forking and pull requests as described in contribution guidelines. The stable version is available via Golang modules.

1. Use go get to retrieve the library and add it as dependency to your application.

go get github.com/fogfish/skiplist@latest

1. Import it in your code

import (
  "github.com/fogfish/skiplist"
)

Quick Example

Here is a minimal example on creating an instance of the skiplist.Map. See the full example

package main

import (
  "github.com/fogfish/skiplist"
)

func main() {
  kv := skiplist.NewMap[int, string]()

  kv.Put(5, "instance")
  kv.Get(5)
  kv.Cut(5)
}

How To Contribute

The library is MIT licensed and accepts contributions via GitHub pull requests:

1. Fork it
2. Create your feature branch (git checkout -b my-new-feature)
3. Commit your changes (git commit -am 'Added some feature')
4. Push to the branch (git push origin my-new-feature)
5. Create new Pull Request

The build and testing process requires Go latest version.

Build and run in your development console.

git clone https://github.com/fogfish/skiplist
cd skiplist
go test

go test -run=^$ -bench=. -cpu 1

go test -fuzz=FuzzSetAddCut
go test -fuzz=FuzzMapIntPutGet
go test -fuzz=FuzzMapStringPutGet
go test -fuzz=FuzzGF2

commit message

The commit message helps us to write a good release note, speed-up review process. The message should address two question what changed and why. The project follows the template defined by chapter Contributing to a Project of Git book.

bugs

If you experience any issues with the library, please let us know via GitHub issues. We appreciate detailed and accurate reports that help us to identity and replicate the issue.

License

Documentation

Overview

Package skiplist implements a probabilistic list-based data structure that are a simple and efficient substitute for balanced trees.

Please see the article that depicts the data structure https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.524

Index

• Constants
• func ForGF2[K Num](gf2 *GF2[K], key *Element[K]) pair.Seq[K, Arc[K]]
• func ForHashMap[K Key, V any](kv *HashMap[K, V], key *Element[K]) pair.Seq[K, V]
• func ForMap[K Key, V any](kv *Map[K, V], el *Pair[K, V]) pair.Seq[K, V]
• func ForSet[K Key](set *Set[K], el *Element[K]) seq.Seq[K]
• type Allocator
• type Arc
  • func (arc Arc[K]) String() string
• type Element
  • func (el *Element[K]) Next() *Element[K]
  • func (el *Element[K]) NextOn(level int) *Element[K]
  • func (el *Element[K]) Rank() int
  • func (el *Element[K]) String() string
• type GF2
  • func NewGF2[K Num](opts ...SetConfig[K]) *GF2[K]
  • func (f *GF2[K]) Add(key K) (Arc[K], Arc[K])
  • func (f *GF2[K]) Get(key K) (Arc[K], bool)
  • func (f *GF2[K]) Keys() *Element[K]
  • func (f *GF2[K]) Length() int
  • func (f *GF2[K]) Put(arc Arc[K]) bool
  • func (f *GF2[K]) String() string
  • func (f *GF2[K]) Successor(key K) *Element[K]
• type HashMap
  • func NewHashMap[K Key, V any](opts ...SetConfig[K]) *HashMap[K, V]
  • func (kv *HashMap[K, V]) Cut(key K) (V, bool)
  • func (kv *HashMap[K, V]) Get(key K) (V, bool)
  • func (kv *HashMap[K, V]) Keys() *Element[K]
  • func (kv *HashMap[K, V]) Length() int
  • func (kv *HashMap[K, V]) Level() int
  • func (kv *HashMap[K, V]) Put(key K, val V) (bool, *Element[K])
  • func (kv *HashMap[K, V]) Skip(level int, key K) (*Element[K], [L]*Element[K])
  • func (kv *HashMap[K, V]) Split(key K) *HashMap[K, V]
  • func (kv *HashMap[K, V]) String() string
  • func (kv *HashMap[K, V]) Successor(key K) *Element[K]
• type Key
• type Map
  • func NewMap[K Key, V any](opts ...MapConfig[K, V]) *Map[K, V]
  • func (kv *Map[K, V]) CreatePair(maxL int, key K, val V) (int, *Pair[K, V])
  • func (kv *Map[K, V]) Cut(key K) (bool, *Pair[K, V])
  • func (kv *Map[K, V]) Get(key K) (V, *Pair[K, V])
  • func (kv *Map[K, V]) Head() *Pair[K, V]
  • func (kv *Map[K, V]) Length() int
  • func (kv *Map[K, V]) Level() int
  • func (kv *Map[K, V]) NewPair(key K, rank int) *Pair[K, V]
  • func (kv *Map[K, V]) Put(key K, val V) (bool, *Pair[K, V])
  • func (kv *Map[K, V]) Skip(level int, key K) (*Pair[K, V], [L]*Pair[K, V])
  • func (kv *Map[K, V]) Split(key K) *Map[K, V]
  • func (kv *Map[K, V]) String() string
  • func (kv *Map[K, V]) Successor(key K) *Pair[K, V]
  • func (kv *Map[K, V]) Values() *Pair[K, V]
• type MapConfig
  • func MapWithAllocator[K Key, V any](malloc Allocator[K, Pair[K, V]]) MapConfig[K, V]
  • func MapWithBlockSize[K Key, V any](b int) MapConfig[K, V]
  • func MapWithProbability[K Key, V any](p float64) MapConfig[K, V]
  • func MapWithRandomSource[K Key, V any](random rand.Source) MapConfig[K, V]
• type Num
• type Pair
  • func (el *Pair[K, V]) Next() *Pair[K, V]
  • func (el *Pair[K, V]) NextOn(level int) *Pair[K, V]
  • func (el *Pair[K, V]) Rank() int
  • func (el *Pair[K, V]) String() string
• type Set
  • func NewSet[K Key](opts ...SetConfig[K]) *Set[K]
  • func (set *Set[K]) Add(key K) (bool, *Element[K])
  • func (set *Set[K]) CreateElement(maxL int, key K) (int, *Element[K])
  • func (set *Set[K]) Cut(key K) (bool, *Element[K])
  • func (set *Set[K]) Has(key K) (bool, *Element[K])
  • func (set *Set[K]) Head() *Element[K]
  • func (set *Set[K]) Length() int
  • func (set *Set[K]) Level() int
  • func (set *Set[K]) NewElement(key K, rank int) *Element[K]
  • func (set *Set[K]) Skip(level int, key K) (*Element[K], [L]*Element[K])
  • func (set *Set[K]) Split(key K) *Set[K]
  • func (set *Set[K]) String() string
  • func (set *Set[K]) Successor(key K) *Element[K]
  • func (set *Set[K]) Values() *Element[K]
• type SetConfig
  • func SetWithAllocator[K Key](malloc Allocator[K, Element[K]]) SetConfig[K]
  • func SetWithBlockSize[K Key](b int) SetConfig[K]
  • func SetWithProbability[K Key](p float64) SetConfig[K]
  • func SetWithRandomSource[K Key](random rand.Source) SetConfig[K]

Constants

const L = 22

L depth of fingers at each node.

The value is estimated as math.Log10(float64(n)) / math.Log10(1/p) n = 4294967296, p = 1/math.E

Functions

func ForGF2

func ForGF2[K Num](gf2 *GF2[K], key *Element[K]) pair.Seq[K, Arc[K]]

func ForHashMap

func ForHashMap[K Key, V any](kv *HashMap[K, V], key *Element[K]) pair.Seq[K, V]

func ForMap

func ForMap[K Key, V any](kv *Map[K, V], el *Pair[K, V]) pair.Seq[K, V]

Iterate over Map elements

seq := skiplist.ForMap(kv, kv.Successor(key))
for has := seq != nil; has; has = seq.Next() {
	seq.Key()
}

func ForSet

func ForSet[K Key](set *Set[K], el *Element[K]) seq.Seq[K]

Build generic iterate over Set elements

seq := skiplist.ForSet(set, set.Successor(key))
for has := seq != nil; has; has = seq.Next() {
	seq.Key()
}

Types

type Allocator

type Allocator[K Key, T any] interface {
	Alloc(K) *T
	Free(K)
}

Memory allocator

type Arc

type Arc[K Num] struct {
	Rank   uint32
	Lo, Hi K
}

func (Arc[K]) String

func (arc Arc[K]) String() string

type Element

type Element[K Key] struct {
	Key     K
	Fingers []*Element[K]
}

Each element is represented by a Element in a skip structures. Each node has a height or level (length of fingers array), which corresponds to the number of forward pointers the node has. When a new element is inserted into the list, a node with a random level is inserted to represent the element. Random levels are generated with a simple pattern: 50% are level 1, 25% are level 2, 12.5% are level 3 and so on.

func (*Element[K]) Next

func (el *Element[K]) Next() *Element[K]

Return next element in the set. Use for-loop to iterate through set elements

for e := set.Successor(...); e != nil; e.Next() { /* ... */}

func (*Element[K]) NextOn

func (el *Element[K]) NextOn(level int) *Element[K]

Return next element in the set on level. Use for-loop to iterate through set elements

for e := set.ValuesOn(...); e != nil; e.NextOn(...) { /* ... */}

func (*Element[K]) Rank

func (el *Element[K]) Rank() int

Rank of node

func (*Element[K]) String

func (el *Element[K]) String() string

Cast Element into string

type GF2

type GF2[K Num] struct {
	// contains filtered or unexported fields
}

func NewGF2

func NewGF2[K Num](opts ...SetConfig[K]) *GF2[K]

func (*GF2[K]) Add

func (f *GF2[K]) Add(key K) (Arc[K], Arc[K])

Add new element to the field

func (*GF2[K]) Get

func (f *GF2[K]) Get(key K) (Arc[K], bool)

Check elements position on the field

func (*GF2[K]) Keys

func (f *GF2[K]) Keys() *Element[K]

func (*GF2[K]) Length

func (f *GF2[K]) Length() int

func (*GF2[K]) Put

func (f *GF2[K]) Put(arc Arc[K]) bool

Put element

func (*GF2[K]) String

func (f *GF2[K]) String() string

func (*GF2[K]) Successor

func (f *GF2[K]) Successor(key K) *Element[K]

type HashMap

type HashMap[K Key, V any] struct {
	// contains filtered or unexported fields
}

func NewHashMap

func NewHashMap[K Key, V any](opts ...SetConfig[K]) *HashMap[K, V]

func (*HashMap[K, V]) Cut

func (kv *HashMap[K, V]) Cut(key K) (V, bool)

func (*HashMap[K, V]) Get

func (kv *HashMap[K, V]) Get(key K) (V, bool)

func (*HashMap[K, V]) Keys

func (kv *HashMap[K, V]) Keys() *Element[K]

func (*HashMap[K, V]) Length

func (kv *HashMap[K, V]) Length() int

func (*HashMap[K, V]) Level

func (kv *HashMap[K, V]) Level() int

func (*HashMap[K, V]) Put

func (kv *HashMap[K, V]) Put(key K, val V) (bool, *Element[K])

func (*HashMap[K, V]) Skip

func (kv *HashMap[K, V]) Skip(level int, key K) (*Element[K], [L]*Element[K])

func (*HashMap[K, V]) Split

func (kv *HashMap[K, V]) Split(key K) *HashMap[K, V]

func (*HashMap[K, V]) String

func (kv *HashMap[K, V]) String() string

func (*HashMap[K, V]) Successor

func (kv *HashMap[K, V]) Successor(key K) *Element[K]

type Key

type Key interface {
	~string |
		~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 |
		~float32 | ~float64
}

Constraint on key types supported by the data structures

type Map

type Map[K Key, V any] struct {
	// contains filtered or unexported fields
}

Map of Elements

func NewMap

func NewMap[K Key, V any](opts ...MapConfig[K, V]) *Map[K, V]

New create instance of SkipList

func (*Map[K, V]) CreatePair

func (kv *Map[K, V]) CreatePair(maxL int, key K, val V) (int, *Pair[K, V])

creates a new node, randomly defines empty fingers (level of the node)

func (*Map[K, V]) Cut

func (kv *Map[K, V]) Cut(key K) (bool, *Pair[K, V])

Cut element from the set, returns true if element is removed

func (*Map[K, V]) Get

func (kv *Map[K, V]) Get(key K) (V, *Pair[K, V])

Check is element exists in set

func (*Map[K, V]) Head

func (kv *Map[K, V]) Head() *Pair[K, V]

Head of skiplist

func (*Map[K, V]) Length

func (kv *Map[K, V]) Length() int

func (*Map[K, V]) Level

func (kv *Map[K, V]) Level() int

Max level of skip list

func (*Map[K, V]) NewPair

func (kv *Map[K, V]) NewPair(key K, rank int) *Pair[K, V]

allocate new pair

func (*Map[K, V]) Put

func (kv *Map[K, V]) Put(key K, val V) (bool, *Pair[K, V])

func (*Map[K, V]) Skip

func (kv *Map[K, V]) Skip(level int, key K) (*Pair[K, V], [L]*Pair[K, V])

skip algorithm is similar to search algorithm that traversing forward pointers. skip maintain the vector path that contains a pointer to the rightmost node of level i or higher that is to the left of the location of the insertion/deletion.

func (*Map[K, V]) Split

func (kv *Map[K, V]) Split(key K) *Map[K, V]

Split set of elements by key

func (*Map[K, V]) String

func (kv *Map[K, V]) String() string

Cast set into string

func (*Map[K, V]) Successor

func (kv *Map[K, V]) Successor(key K) *Pair[K, V]

Successor elements from set

func (*Map[K, V]) Values

func (kv *Map[K, V]) Values() *Pair[K, V]

All set elements

type MapConfig

type MapConfig[K Key, V any] func(*Map[K, V])

Configure Set properties

func MapWithAllocator

func MapWithAllocator[K Key, V any](malloc Allocator[K, Pair[K, V]]) MapConfig[K, V]

Configure Memory Allocator

func MapWithBlockSize

func MapWithBlockSize[K Key, V any](b int) MapConfig[K, V]

Configure Probability table so that each level takes (√B)ⁿ elements

func MapWithProbability

func MapWithProbability[K Key, V any](p float64) MapConfig[K, V]

Configure Probability table Use math.Log(B)/B < p < math.Pow(B, -0.5)

The probability help to control the "distance" between elements on each level Use p = math.Pow(B, -0.5), where B is number of elements On L1 distance is √B, L2 distance is B, Ln distance is (√B)ⁿ

func MapWithRandomSource

func MapWithRandomSource[K Key, V any](random rand.Source) MapConfig[K, V]

Configure Random Generator

type Num

type Num interface {
	~uint8 | ~uint16 | ~uint32 | ~uint64
}

type Pair

type Pair[K Key, V any] struct {
	Key     K
	Value   V
	Fingers []*Pair[K, V]
}

Each key-value pair is represented by a Pair in a skip structures. Each node has a height or level (length of fingers array), which corresponds to the number of forward pointers the node has. When a new element is inserted into the list, a node with a random level is inserted to represent the element. Random levels are generated with a simple pattern: 50% are level 1, 25% are level 2, 12.5% are level 3 and so on.

func (*Pair[K, V]) Next

func (el *Pair[K, V]) Next() *Pair[K, V]

Return next element in the set. Use for-loop to iterate through set elements

for e := set.Successor(...); e != nil; e.Next() { /* ... */}

func (*Pair[K, V]) NextOn

func (el *Pair[K, V]) NextOn(level int) *Pair[K, V]

Return next element in the set on level. Use for-loop to iterate through set elements

for e := set.ValuesOn(...); e != nil; e.NextOn(...) { /* ... */}

func (*Pair[K, V]) Rank

func (el *Pair[K, V]) Rank() int

Rank of node

func (*Pair[K, V]) String

func (el *Pair[K, V]) String() string

Cast Element into string

type Set

type Set[K Key] struct {
	// contains filtered or unexported fields
}

Set of Elements

func NewSet

func NewSet[K Key](opts ...SetConfig[K]) *Set[K]

New create instance of SkipList

func (*Set[K]) Add

func (set *Set[K]) Add(key K) (bool, *Element[K])

Add element to set, return true if element is new

func (*Set[K]) CreateElement

func (set *Set[K]) CreateElement(maxL int, key K) (int, *Element[K])

mkNode creates a new node, randomly defines empty fingers (level of the node)

func (*Set[K]) Cut

func (set *Set[K]) Cut(key K) (bool, *Element[K])

Cut element from the set, returns true if element is removed

func (*Set[K]) Has

func (set *Set[K]) Has(key K) (bool, *Element[K])

Check is element exists in set

func (*Set[K]) Head

func (set *Set[K]) Head() *Element[K]

Head of skiplist

func (*Set[K]) Length

func (set *Set[K]) Length() int

func (*Set[K]) Level

func (set *Set[K]) Level() int

Max level of skip list

func (*Set[K]) NewElement

func (set *Set[K]) NewElement(key K, rank int) *Element[K]

allocate new node

func (*Set[K]) Skip

func (set *Set[K]) Skip(level int, key K) (*Element[K], [L]*Element[K])

skip algorithm is similar to search algorithm that traversing forward pointers. skip maintain the vector path that contains a pointer to the rightmost node of level i or higher that is to the left of the location of the insertion/deletion.

func (*Set[K]) Split

func (set *Set[K]) Split(key K) *Set[K]

Split set of elements by key

func (*Set[K]) String

func (set *Set[K]) String() string

Cast set into string

func (*Set[K]) Successor

func (set *Set[K]) Successor(key K) *Element[K]

Successor elements of key

func (*Set[K]) Values

func (set *Set[K]) Values() *Element[K]

All set elements

type SetConfig

type SetConfig[K Key] func(*Set[K])

Configure Set properties

func SetWithAllocator

func SetWithAllocator[K Key](malloc Allocator[K, Element[K]]) SetConfig[K]

Configure Memory Allocator

func SetWithBlockSize

func SetWithBlockSize[K Key](b int) SetConfig[K]

Configure Probability table so that each level takes (√B)ⁿ elements

func SetWithProbability

func SetWithProbability[K Key](p float64) SetConfig[K]

Configure Probability table Use math.Log(B)/B < p < math.Pow(B, -0.5)

The probability help to control the "distance" between elements on each level Use p = math.Pow(B, -0.5), where B is number of elements On L1 distance is √B, L2 distance is B, Ln distance is (√B)ⁿ

func SetWithRandomSource

func SetWithRandomSource[K Key](random rand.Source) SetConfig[K]

Configure Random Generator