Skip to main content

skl.go

skl.go - Overview​

This file implements a concurrent skiplist data structure adapted from RocksDB's inline skiplist. It provides efficient insertion, retrieval, and iteration over a sorted set of key-value pairs. It is optimized for concurrent access and supports overwrites.

Detailed Documentation​

Constants​

maxHeight​

const maxHeight = 20

The maximum height of the skiplist.

heightIncrease​

const heightIncrease = math.MaxUint32 / 3

Determines the probability of a node having a higher level.

MaxNodeSize​

const MaxNodeSize = int(unsafe.Sizeof(node{}))

The memory footprint of a node of maximum height.

Structs​

node​

type node struct {
	value atomic.Uint64
	keyOffset uint32
	keySize   uint16
	height uint16
	tower [maxHeight]atomic.Uint32
}

Represents a node in the skiplist.

  • value: Stores the value's offset and size in the arena.
  • keyOffset: Stores the key's offset in the arena.
  • keySize: Stores the key's size.
  • height: The height of the node in the skiplist.
  • tower: An array of atomic uint32 values, representing the offsets of the next nodes in each level.

Skiplist​

type Skiplist struct {
	height  atomic.Int32
	head    *node
	ref     atomic.Int32
	arena   *Arena
	OnClose func()
}

Represents the skiplist data structure.

  • height: The current height of the skiplist.
  • head: A pointer to the head node of the skiplist.
  • ref: An atomic counter for managing the skiplist's lifecycle.
  • arena: A pointer to the arena where nodes and keys are allocated.
  • OnClose: A function to be called when the skiplist is no longer referenced.

Functions​

IncrRef​

func (s *Skiplist) IncrRef()

Increases the reference count of the skiplist.

DecrRef​

func (s *Skiplist) DecrRef()

Decreases the reference count of the skiplist. Deallocates the Skiplist when the reference count reaches zero.

newNode​

func newNode(arena *Arena, key []byte, v y.ValueStruct, height int) *node

Creates a new node in the arena.

  • arena: The arena to allocate the node in.
  • key: The key to store in the node.
  • v: The value to store in the node.
  • height: The height of the new node.

Returns:

  • A pointer to the newly created node.

encodeValue​

func encodeValue(valOffset uint32, valSize uint32) uint64

Encodes the value offset and size into a uint64.

  • valOffset: The offset of the value in the arena.
  • valSize: The size of the value.

Returns:

  • A uint64 containing the encoded value offset and size.

decodeValue​

func decodeValue(value uint64) (valOffset uint32, valSize uint32)

Decodes the value offset and size from a uint64.

  • value: The encoded uint64 value.

Returns:

  • valOffset: The offset of the value in the arena.
  • valSize: The size of the value.

NewSkiplist​

func NewSkiplist(arenaSize int64) *Skiplist

Creates a new empty skiplist.

  • arenaSize: The size of the arena to allocate for the skiplist.

Returns:

  • A pointer to the newly created skiplist.

getValueOffset​

func (s *node) getValueOffset() (uint32, uint32)

Gets the value offset and size from the node.

Returns:

  • uint32: The offset of the value in the arena.
  • uint32: The size of the value.

key​

func (s *node) key(arena *Arena) []byte

Gets the key from the arena.

  • arena: The arena containing the key.

Returns:

  • The key as a byte slice.

setValue​

func (s *node) setValue(arena *Arena, v y.ValueStruct)

Sets the value of a node.

  • arena: The arena to allocate the value in.
  • v: The value to set.

getNextOffset​

func (s *node) getNextOffset(h int) uint32

Gets the offset of the next node at a given level.

  • h: The level to get the next node offset from.

Returns:

  • The offset of the next node at the given level.

casNextOffset​

func (s *node) casNextOffset(h int, old, val uint32) bool

Atomically compares and swaps the next offset at a given level.

  • h: The level to perform the compare and swap.
  • old: The old offset value.
  • val: The new offset value.

Returns:

  • true if the compare and swap was successful, false otherwise.

randomHeight​

func (s *Skiplist) randomHeight() int

Generates a random height for a new node.

Returns:

  • A random height between 1 and maxHeight.

getNext​

func (s *Skiplist) getNext(nd *node, height int) *node

Gets the next node at a given level.

  • nd: The current node.
  • height: The level to get the next node from.

Returns:

  • A pointer to the next node at the given level.

findNear​

func (s *Skiplist) findNear(key []byte, less bool, allowEqual bool) (*node, bool)

Finds the node near to the key.

  • key: The key to search for.
  • less: If true, finds the rightmost node such that node.key < key (if allowEqual=false) or node.key <= key (if allowEqual=true). If false, finds the leftmost node such that node.key > key (if allowEqual=false) or node.key >= key (if allowEqual=true).
  • allowEqual: If true, allows finding a node with the same key.

Returns:

  • *node: The node found.
  • bool: True if the node has key equal to the given key.

findSpliceForLevel​

func (s *Skiplist) findSpliceForLevel(key []byte, before *node, level int) (*node, *node)

Finds the nodes before and after the key at a given level.

  • key: The key to search for.
  • before: The node to start searching from.
  • level: The level to search at.

Returns:

  • *node: The node before the key.
  • *node: The node after the key.

getHeight​

func (s *Skiplist) getHeight() int32

Gets the current height of the skiplist.

Returns:

  • The current height of the skiplist.

Put​

func (s *Skiplist) Put(key []byte, v y.ValueStruct)

Inserts the key-value pair into the skiplist.

  • key: The key to insert.
  • v: The value to insert.

Empty​

func (s *Skiplist) Empty() bool

Checks if the skiplist is empty.

Returns:

  • true if the skiplist is empty, false otherwise.

findLast​

func (s *Skiplist) findLast() *node

Finds the last node in the skiplist.

Returns:

  • A pointer to the last node in the skiplist, or nil if the skiplist is empty.

Get​

func (s *Skiplist) Get(key []byte) y.ValueStruct

Gets the value associated with the key.

  • key: The key to search for.

Returns:

  • The value associated with the key, or an empty y.ValueStruct if the key is not found.

NewIterator​

func (s *Skiplist) NewIterator() *Iterator

Creates a new iterator for the skiplist.

Returns:

  • A pointer to the newly created iterator.

MemSize​

func (s *Skiplist) MemSize() int64

Returns the memory usage of the skiplist.

Returns:

  • The memory usage of the skiplist in bytes.

Structs​

Iterator​

type Iterator struct {
	list *Skiplist
	n    *node
}

Represents an iterator for the skiplist.

  • list: A pointer to the skiplist being iterated over.
  • n: A pointer to the current node in the iteration.

Functions​

Close​

func (s *Iterator) Close() error

Closes the iterator and releases resources.

Returns:

  • nil

Valid​

func (s *Iterator) Valid() bool

Checks if the iterator is currently pointing to a valid node.

Returns:

  • true if the iterator is valid, false otherwise.

Key​

func (s *Iterator) Key() []byte

Gets the key of the current node.

Returns:

  • The key of the current node as a byte slice.

Value​

func (s *Iterator) Value() y.ValueStruct

Gets the value of the current node.

Returns:

  • The value of the current node.

ValueUint64​

func (s *Iterator) ValueUint64() uint64

Gets the uint64 value of the current node.

Returns:

  • The uint64 value of the current node.

Next​

func (s *Iterator) Next()

Advances the iterator to the next node.

Prev​

func (s *Iterator) Prev()

Moves the iterator to the previous node.

Seek​

func (s *Iterator) Seek(target []byte)

Seeks the iterator to the first node with a key greater than or equal to the target.

  • target: The target key.

SeekForPrev​

func (s *Iterator) SeekForPrev(target []byte)

Seeks the iterator to the first node with a key less than or equal to the target.

  • target: The target key.

SeekToFirst​

func (s *Iterator) SeekToFirst()

Seeks the iterator to the first node in the skiplist.

SeekToLast​

func (s *Iterator) SeekToLast()

Seeks the iterator to the last node in the skiplist.

Structs​

UniIterator​

type UniIterator struct {
	iter     *Iterator
	reversed bool
}

Represents a unidirectional iterator for the skiplist.

  • iter: A pointer to the underlying iterator.
  • reversed: Indicates whether the iterator is reversed.

Functions​

NewUniIterator​

func (s *Skiplist) NewUniIterator(reversed bool) *UniIterator

Creates a new unidirectional iterator for the skiplist.

  • reversed: Indicates whether the iterator should be reversed.

Returns:

  • A pointer to the newly created unidirectional iterator.

Next​

func (s *UniIterator) Next()

Advances the iterator to the next node.

Rewind​

func (s *UniIterator) Rewind()

Rewinds the iterator to the beginning or end, depending on the direction.

Seek​

func (s *UniIterator) Seek(key []byte)

Seeks the iterator to the first node with a key greater than or equal to the target (or less than or equal to if reversed).

  • key: The target key.

Key​

func (s *UniIterator) Key() []byte

Gets the key of the current node.

Returns:

  • The key of the current node as a byte slice.

Value​

func (s *UniIterator) Value() y.ValueStruct

Gets the value of the current node.

Returns:

  • The value of the current node.

Valid​

func (s *UniIterator) Valid() bool

Checks if the iterator is currently pointing to a valid node.

Returns:

  • true if the iterator is valid, false otherwise.

Close​

func (s *UniIterator) Close() error

Closes the iterator and releases resources.

Returns:

  • nil

Code Examples​

Creating a new Skiplist​

package main

import (
	"fmt"

	"github.com/dgraph-io/badger/v4/y"
	"github.com/hypermode/storage/skl"
)

func main() {
	arenaSize := int64(1 << 20) // 1MB arena size
	skiplist := skl.NewSkiplist(arenaSize)
	defer skiplist.DecrRef()

	key := []byte("exampleKey")
	value := y.ValueStruct{Value: []byte("exampleValue")}

	skiplist.Put(key, value)

	retrievedValue := skiplist.Get(key)

	fmt.Printf("Retrieved Value: %s\n", retrievedValue.Value)
}