skiplist

README

fast-skiplist

import "github.com/Laisky/fast-skiplist/v2"

New Features

upgrade to go v1.18 to support generic

Documentation

Index

• Constants
• type Element
  • func (e *Element[T]) Key() T
  • func (e *Element[T]) Next() *Element[T]
  • func (e *Element[T]) Value() interface{}
• type Number
• type SkipList
  • func New[T Sortable]() *SkipList[T]
  • func NewWithMaxLevel[T Sortable](maxLevel int) *SkipList[T]
  • func (list *SkipList[T]) Front() *Element[T]
  • func (list *SkipList[T]) Get(key T) *Element[T]
  • func (list *SkipList[T]) Len() int
  • func (list *SkipList[T]) Remove(key T) *Element[T]
  • func (list *SkipList[T]) Set(key T, value interface{}) *Element[T]
  • func (list *SkipList[T]) SetProbability(newProbability float64)
• type Sortable

Constants

const (
	// DefaultMaxLevel default height/level of the list
	//
	// Suitable for math.Floor(math.Pow(math.E, 18)) == 65659969 elements in list
	DefaultMaxLevel int = 18
	// DefaultProbability default probability of a node could hoist to the higher level
	DefaultProbability float64 = 1 / math.E
)

Types

type Element

type Element[T Sortable] struct {
	// contains filtered or unexported fields
}

func (*Element[T]) Key

func (e *Element[T]) Key() T

Key allows retrieval of the key for a given Element

func (*Element[T]) Next

func (e *Element[T]) Next() *Element[T]

Next returns the following Element or nil if we're at the end of the list. Only operates on the bottom level of the skip list (a fully linked list).

func (*Element[T]) Value

func (e *Element[T]) Value() interface{}

Value allows retrieval of the value for a given Element

type Number

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

Number is a number type

type SkipList

type SkipList[T Sortable] struct {
	// contains filtered or unexported fields
}

func New

func New[T Sortable]() *SkipList[T]

New creates a new skip list with default parameters. Returns a pointer to the new list.

func NewWithMaxLevel

func NewWithMaxLevel[T Sortable](maxLevel int) *SkipList[T]

NewWithMaxLevel creates a new skip list with MaxLevel set to the provided number. maxLevel has to be int(math.Ceil(math.Log(N))) for DefaultProbability (where N is an upper bound on the number of elements in a skip list). See http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.524 Returns a pointer to the new list.

func (*SkipList[T]) Front

func (list *SkipList[T]) Front() *Element[T]

Front returns the head node of the list.

func (*SkipList[T]) Get

func (list *SkipList[T]) Get(key T) *Element[T]

Get finds an element by key. It returns element pointer if found, nil if not found. Locking is optimistic and happens only after searching with a fast check for deletion after locking.

func (*SkipList[T]) Len

func (list *SkipList[T]) Len() int

Len returns the number of elements in the list.

func (*SkipList[T]) Remove

func (list *SkipList[T]) Remove(key T) *Element[T]

Remove deletes an element from the list. Returns removed element pointer if found, nil if not found. Locking is optimistic and happens only after searching with a fast check on adjacent nodes after locking.

func (*SkipList[T]) Set

func (list *SkipList[T]) Set(key T, value interface{}) *Element[T]

Set inserts a value in the list with the specified key, ordered by the key. If the key exists, it updates the value in the existing node. Returns a pointer to the new element. Locking is optimistic and happens only after searching.

func (*SkipList[T]) SetProbability

func (list *SkipList[T]) SetProbability(newProbability float64)

SetProbability changes the current P value of the list. It doesn't alter any existing data, only changes how future insert heights are calculated.

type Sortable

type Sortable interface {
	Number | string
}

Sortable Data types that can be compared by >, <, ==