README
¶
ConcurrentSkipList
A light, high-performance, concurrent, thread-safe skip list implementation written in Golang.
Getting Start
- Import package
go get github.com/slclub/skiplist
import "github.com/slclub/skiplist"
- 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
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
- func Safe()
- func Unsafe()
- type ConcurrentSkipList
- 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) SearchCloset(index uint64) ([]*Node, *Node)
- func (s *ConcurrentSkipList) Sub(startNumber int32, length int32) []*Node
- type Node
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
Variables ¶
This section is empty.
Functions ¶
func Hash ¶
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) SearchCloset ¶
func (s *ConcurrentSkipList) SearchCloset(index uint64) ([]*Node, *Node)
Source Files
Directories