ConcurrentSkipList

README

ConcurrentSkipList

A light, high-performance, concurrent, thread-safe skip list implementation written in Golang.

Getting Start

• Import package

go get github.com/AceDarkknight/ConcurrentSkipList

import "github.com/AceDarkknight/ConcurrentSkipList"

• Usage

// Create a new skip list. The parameter is the level of the skip list.
// Parameter must > 0 and <=32, if not, err is not nil.
skipList, err := ConcurrentSkipList.NewConcurrentSkipList(12)
if err != nil {
    fmt.Println(err)
}

// Insert index and value. The index must uint64 and value is interface.
skipList.Insert(uint64(1), 1)
skipList.Insert(uint64(2), 2)

// Search in skip list.
if node, ok := skipList.Search(uint64(1)); ok {
	fmt.Printf("index:%v value:%v\n", node.Index(), node.Value())
}

// Delete by index.
skipList.Delete(uint64(2))

// Get the level of skip list.
_ = skipList.Level()

// Get the length of skip list.
_ = skipList.Length()

// Iterate each node in skip list.
skipList.ForEach(func(node *ConcurrentSkipList.Node) bool {
	fmt.Printf("index:%v value:%v\n", node.Index(), node.Value())
	return true
})

// Select top 10 nodes of skip list.
nodes := skipList.Sub(0, 10)

TODO

• Reduce memory.
• Add reverse operation.

References

https://en.wikipedia.org/wiki/Skip_list

Documentation

Overview

Package ConcurrentSkipList provide an implementation of skip list. It's thread-safe in concurrency and high performance.

Index

• Constants
• func Hash(input []byte) uint64
• type ConcurrentSkipList
  • func NewConcurrentSkipList(level int) (*ConcurrentSkipList, error)
  • func (s *ConcurrentSkipList) Delete(index uint64)
  • func (s *ConcurrentSkipList) ForEach(f func(node *Node) bool)
  • func (s *ConcurrentSkipList) Insert(index uint64, value interface{})
  • func (s *ConcurrentSkipList) Length() int32
  • func (s *ConcurrentSkipList) Level() int
  • func (s *ConcurrentSkipList) Search(index uint64) (*Node, bool)
  • func (s *ConcurrentSkipList) Sub(startNumber int32, length int32) []*Node
• type Node
  • func (n *Node) Index() uint64
  • func (n *Node) Value() interface{}

Constants

const (
	MAX_LEVEL   = 32
	PROBABILITY = 0.25
	SHARDS      = 32
)

Comes from redis's implementation. Also you can see more detail in William Pugh's paper <Skip Lists: A Probabilistic Alternative to Balanced Trees>. The paper is in ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

Functions

func Hash

func Hash(input []byte) uint64

Hash will calculate the input's hash value using xxHash algorithm. It can be used to calculate the index of skip list. See more detail in https://cyan4973.github.io/xxHash/

Types

type ConcurrentSkipList

type ConcurrentSkipList struct {
	// contains filtered or unexported fields
}

ConcurrentSkipList is a struct contains a slice of concurrent skip list.

func NewConcurrentSkipList

func NewConcurrentSkipList(level int) (*ConcurrentSkipList, error)

NewConcurrentSkipList will create a new concurrent skip list with given level. Level must between 1 to 32. If not, will return an error. To determine the level, you can see the paper ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf. A simple way to determine the level is L(N) = log(1/PROBABILITY)(N). N is the count of the skip list which you can estimate. PROBABILITY is 0.25 in this case. For example, if you expect the skip list contains 10000000 elements, then N = 10000000, L(N) ≈ 12. After initialization, the head field's level equal to level parameter and point to tail field.

func (*ConcurrentSkipList) Delete

func (s *ConcurrentSkipList) Delete(index uint64)

Delete the node with the given index.

func (*ConcurrentSkipList) ForEach

func (s *ConcurrentSkipList) ForEach(f func(node *Node) bool)

ForEach will create a snapshot first shard by shard. Then iterate each node in snapshot and do the function f(). If f() return false, stop iterating and return. If skip list is inserted or deleted while iterating, the node in snapshot will not change. The performance is not very high and the snapshot with be stored in memory.

func (*ConcurrentSkipList) Insert

func (s *ConcurrentSkipList) Insert(index uint64, value interface{})

Insert will insert a value into skip list. If skip has these this index, overwrite the value, otherwise add it.

func (*ConcurrentSkipList) Length

func (s *ConcurrentSkipList) Length() int32

Length will return the length of skip list.

func (*ConcurrentSkipList) Level

func (s *ConcurrentSkipList) Level() int

Level will return the level of skip list.

func (*ConcurrentSkipList) Search

func (s *ConcurrentSkipList) Search(index uint64) (*Node, bool)

Search will search the skip list with the given index. If the index exists, return the value and true, otherwise return nil and false.

func (*ConcurrentSkipList) Sub

func (s *ConcurrentSkipList) Sub(startNumber int32, length int32) []*Node

Sub will return a slice the skip list who starts with startNumber. The startNumber start with 0 as same as slice and maximum length is skip list's length.

type Node

type Node struct {
	// contains filtered or unexported fields
}

func (*Node) Index

func (n *Node) Index() uint64

Index will return the node's index.

func (*Node) Value

func (n *Node) Value() interface{}

Value will return the node's value.