skiplist

README

SkipLists

Whenever you find yourself in need of a sorted list/map for range scans or ordered iteration, you can resort to a SkipList. The SkipList in this project is based on LevelDBs skiplist

This package is the only one compatible with versions pre-generics.

Using skiplist.Map (generics Go >=1.18)

You can get the full example from examples/skiplist.go.

import (
	"github.com/thomasjungblut/go-sstables/skiplist"
	"log"
)

func main() {

	skipListMap := skiplist.NewSkipListMap[int, int](skiplist.OrderedComparator[int]{})
	skipListMap.Insert(13, 91)
	skipListMap.Insert(3, 1)
	skipListMap.Insert(5, 2)
	log.Printf("size: %d", skipListMap.Size())

	it, _ := skipListMap.Iterator()
	for {
		k, v, err := it.Next()
		if err == skiplist.Done {
			break
		}
		log.Printf("key: %d, value: %d", k, v)
	}

	log.Printf("starting at key: %d", 5)
	it, _ = skipListMap.IteratorStartingAt(5)
	for {
		k, v, err := it.Next()
		if err == skiplist.Done {
			break
		}
		log.Printf("key: %d, value: %d", k, v)
	}

	log.Printf("between: %d and %d", 8, 50)
	it, _ = skipListMap.IteratorBetween(8, 50)
	for {
		k, v, err := it.Next()
		if err == skiplist.Done {
			break
		}
		log.Printf("key: %d, value: %d", k, v)
	}
}

Using SkipListMap (pre-generics Go <1.18)

Here's an example on how to use it with versions lower than Go 1.18:

skipListMap := skiplist.NewSkipListMap(skiplist.IntComparator)
skipListMap.Insert(13, 91)
skipListMap.Insert(3, 1)
skipListMap.Insert(5, 2)
log.Printf("size: %d", skipListMap.Size())

it, _ := skipListMap.Iterator()
for {
    k, v, err := it.Next()
    if err == skiplist.Done {
        break
    }
    log.Printf("key: %d, value: %d", k, v)
}

log.Printf("starting at key: %d", 5)
it, _ = skipListMap.IteratorStartingAt(5)
for {
    k, v, err := it.Next()
    if err == skiplist.Done {
        break
    }
    log.Printf("key: %d, value: %d", k, v)
}

log.Printf("between: %d and %d", 8, 50)
it, _ = skipListMap.IteratorBetween(8, 50)
for {
    k, v, err := it.Next()
    if err == skiplist.Done {
        break
    }
    log.Printf("key: %d, value: %d", k, v)
}

You can supply any kind of element and comparator to sort arbitrary structs and primitives.

Documentation

Overview

Package skiplist is a translation from LevelDBs skiplist (https://github.com/google/leveldb/blob/master/db/skiplist.h)

Index

• Variables
• type BytesComparator
  • func (BytesComparator) Compare(a []byte, b []byte) int
• type Comparator
• type Iterator
  • func (it *Iterator[K, V]) Next() (_ K, _ V, done error)
• type IteratorI
• type Map
  • func (list *Map[K, V]) Contains(key K) bool
  • func (list *Map[K, V]) Get(key K) (_ V, err error)
  • func (list *Map[K, V]) Insert(key K, value V)
  • func (list *Map[K, V]) Iterator() (IteratorI[K, V], error)
  • func (list *Map[K, V]) IteratorBetween(keyLower K, keyHigher K) (IteratorI[K, V], error)
  • func (list *Map[K, V]) IteratorStartingAt(key K) (IteratorI[K, V], error)
  • func (list *Map[K, V]) Size() int
• type MapI
  • func NewSkipListMap[K any, V any](comp Comparator[K]) MapI[K, V]
• type Node
  • func (n *Node[K, V]) Next(height int) *Node[K, V]
  • func (n *Node[K, V]) SetNext(height int, node *Node[K, V])
• type NodeI
• type Ordered
• type OrderedComparator
  • func (OrderedComparator[T]) Compare(a T, b T) int

Variables

var Done = errors.New("no more items in iterator")

Done indicates an iterator has returned all items. https://github.com/GoogleCloudPlatform/google-cloud-go/wiki/Iterator-Guidelines

var NotFound = errors.New("key was not found")

Types

type BytesComparator

type BytesComparator struct {
}

func (BytesComparator) Compare

func (BytesComparator) Compare(a []byte, b []byte) int

type Comparator

type Comparator[T any] interface {
	// Compare contract (similar to Java):
	// < 0 when a < b
	// == 0 when a == b
	// > 0 when a > b
	Compare(a T, b T) int
}

type Iterator

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

func (*Iterator[K, V]) Next

func (it *Iterator[K, V]) Next() (_ K, _ V, done error)

type IteratorI

type IteratorI[K any, V any] interface {
	// Next returns the next key, value in sequence
	// returns Done as the error when the iterator is exhausted
	Next() (K, V, error)
}

type Map

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

func (*Map[K, V]) Contains

func (list *Map[K, V]) Contains(key K) bool

func (*Map[K, V]) Get

func (list *Map[K, V]) Get(key K) (_ V, err error)

func (*Map[K, V]) Insert

func (list *Map[K, V]) Insert(key K, value V)

func (*Map[K, V]) Iterator

func (list *Map[K, V]) Iterator() (IteratorI[K, V], error)

func (*Map[K, V]) IteratorBetween

func (list *Map[K, V]) IteratorBetween(keyLower K, keyHigher K) (IteratorI[K, V], error)

func (*Map[K, V]) IteratorStartingAt

func (list *Map[K, V]) IteratorStartingAt(key K) (IteratorI[K, V], error)

func (*Map[K, V]) Size

func (list *Map[K, V]) Size() int

type MapI

type MapI[K any, V any] interface {
	Size() int

	// Insert key/value into the list.
	// REQUIRES: nothing that compares equal to key is currently in the list.
	Insert(key K, value V)

	// Contains returns true if an entry that compares equal to key is in the list.
	Contains(key K) bool

	// Get returns the value element that compares equal to the key supplied or returns NotFound if it does not exist.
	Get(key K) (V, error)

	// Iterator returns an iterator over the whole sorted sequence
	Iterator() (IteratorI[K, V], error)

	// IteratorStartingAt returns an iterator over the sorted sequence starting at the given key (inclusive if key is in the list).
	// Using a key that is out of the sequence range will result in either an empty iterator or the full sequence.
	IteratorStartingAt(key K) (IteratorI[K, V], error)

	// IteratorBetween Returns an iterator over the sorted sequence starting at the given keyLower (inclusive if key is in the list)
	// and until the given keyHigher was reached (inclusive if key is in the list).
	// Using keys that are out of the sequence range will result in either an empty iterator or the full sequence.
	// If keyHigher is lower than keyLower an error will be returned
	IteratorBetween(keyLower K, keyHigher K) (IteratorI[K, V], error)
}

func NewSkipListMap

func NewSkipListMap[K any, V any](comp Comparator[K]) MapI[K, V]

type Node

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

func (*Node[K, V]) Next

func (n *Node[K, V]) Next(height int) *Node[K, V]

func (*Node[K, V]) SetNext

func (n *Node[K, V]) SetNext(height int, node *Node[K, V])

type NodeI

type NodeI[K any, V any] interface {
	Next(height int) *Node[K, V]
	SetNext(height int, node *Node[K, V])
}

type Ordered

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

Ordered represents the set of types for which the '<' and '>' operator work.

type OrderedComparator

type OrderedComparator[T Ordered] struct {
}

func (OrderedComparator[T]) Compare

func (OrderedComparator[T]) Compare(a T, b T) int