skiplist

Documentation

Index

• Constants
• Variables
• func ConsumeFirstIfLowerOrEqual(nc *genericstruct.NodeCache, off int64, key []byte) (int64, bool, error)
• func Delete(nc *genericstruct.NodeCache, off int64, key []byte) (bool, error)
• func InsertionAlgorithmV1(nc *genericstruct.NodeCache, off int64, key []byte, value int64) error
• func Lookup(nc *genericstruct.NodeCache, off int64, key []byte) (int64, bool, error)
• func NodeConstructor() genericstruct.Block
• type KeySearcher
  • func (k *KeySearcher) Found(key []byte) (it int64, ok bool, err error)
  • func (k *KeySearcher) FoundNode(key []byte) (it *Node, ok bool, err error)
  • func (k *KeySearcher) Insert(key []byte, value int64, level int) (int64, error)
  • func (k *KeySearcher) Steps(off int64, key []byte) error
  • func (k *KeySearcher) StepsFind(off int64, key []byte) (int64, *Node, error)
• type Node
  • func LookupNode(nc *genericstruct.NodeCache, off int64, key []byte) (*Node, bool, error)
  • func (n *Node) Dirty() bool
  • func (n *Node) Load(buf *bytebufferpool.ByteBuffer)
  • func (n *Node) Store(buf *bytebufferpool.ByteBuffer)
• type NodeHead

Constants

const Steps = 20

Variables

var EExists = errors.New("EExists")

var NodeMaster = &genericstruct.NodeMaster{Factory: NodeConstructor}

Functions

func ConsumeFirstIfLowerOrEqual

func ConsumeFirstIfLowerOrEqual(nc *genericstruct.NodeCache, off int64, key []byte) (int64, bool, error)

Removes the first Element of the skiplist, if it is lower or equal to KEY.

On success, it returns the Value, that is assigned to the first element. On failure (first element is greater than KEY, or list is empty), it does not modify anything.

func Delete

func Delete(nc *genericstruct.NodeCache, off int64, key []byte) (bool, error)

func InsertionAlgorithmV1

func InsertionAlgorithmV1(nc *genericstruct.NodeCache, off int64, key []byte, value int64) error

func Lookup

func Lookup(nc *genericstruct.NodeCache, off int64, key []byte) (int64, bool, error)

func NodeConstructor

func NodeConstructor() genericstruct.Block

Types

type KeySearcher

type KeySearcher struct {
	Cache *genericstruct.NodeCache
	Ptrs  [Steps]int64
	Jumps [Steps]int
}

This object must be used with care - otherwise the Skiplist becomes out of order.

func (*KeySearcher) Found

func (k *KeySearcher) Found(key []byte) (it int64, ok bool, err error)

func (*KeySearcher) FoundNode

func (k *KeySearcher) FoundNode(key []byte) (it *Node, ok bool, err error)

func (*KeySearcher) Insert

func (k *KeySearcher) Insert(key []byte, value int64, level int) (int64, error)

Inserts a key-value pair.

IMPORTANT: Must not be called, unless k.Steps() was called before with the same key, and k.Found() was checked with the same key, that this one doesn't exist

k.Steps(listHead,KEY)   // Perform the search
_,ok,_ := k.Found(KEY)  // Check, if we found the key.

// Insert the pair IF, AND ONLY IF, we didn't have the pair already.
if !ok { k.Insert(KEY,VALUE,level) }

func (*KeySearcher) Steps

func (k *KeySearcher) Steps(off int64, key []byte) error

func (*KeySearcher) StepsFind

func (k *KeySearcher) StepsFind(off int64, key []byte) (int64, *Node, error)

Fast path towards finding.

type Node

type Node struct {
	Head    NodeHead
	Key     []byte
	Tainted bool
}

func LookupNode

func LookupNode(nc *genericstruct.NodeCache, off int64, key []byte) (*Node, bool, error)

func (*Node) Dirty

func (n *Node) Dirty() bool

func (*Node) Load

func (n *Node) Load(buf *bytebufferpool.ByteBuffer)

func (*Node) Store

func (n *Node) Store(buf *bytebufferpool.ByteBuffer)

type NodeHead

type NodeHead struct {
	Nexts   [Steps]int64
	Content int64
	Rest    int32
}