점프 표 SkipList (go 언어 구현)
12883 단어 데이터 구조
https://github.com/AceDarkknight/ConcurrentSkipList
데이터 구조
저 희 는 Concurrent SkipList 라 는 데이터 구 조 를 사용 하여 전체 skip list 를 대표 합 니 다. 여러 개의 skipList 를 포함 하 는 절편 을 볼 수 있 습 니 다.
// ConcurrentSkipList is a struct contains a slice of concurrent skip list.
type ConcurrentSkipList struct {
skipLists []*skipList
level int
}
skipList 의 구 조 는 다음 과 같 습 니 다. 모든 skipList 는 머리 결점, 꼬리 노드, 높이, 길 이 를 제외 하고 읽 기와 쓰기 자물쇠 가 있어 서 병행 안전 을 보장 합 니 다.
type skipList struct {
level int
length int32
head *Node
tail *Node
mutex sync.RWMutex
}
그 중에서 우 리 는 모든 노드 를 하나의 Node 라 고 부 릅 니 다. Node 의 구 조 는 다음 과 같 습 니 다. index 는 노드 의 색인 값 을 대표 하고 value 는 노드 의 값 을 대표 하 며 nextNodes 는 이 노드 가 가리 키 는 다음 노드 를 기록 합 니 다.
type Node struct {
index uint64
value interface{}
nextNodes []*Node
}
concurrentSkipList. go 원본 파일
/*
Package ConcurrentSkipList provide an implementation of skip list. It's thread-safe in concurrency and high performance.
*/
package ConcurrentSkipList
import (
"errors"
"math"
"sync/atomic"
"github.com/OneOfOne/xxhash"
)
// Comes from redis's implementation.
// Also you can see more detail in William Pugh's paper .
// The paper is in ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
const (
MAX_LEVEL = 32
PROBABILITY = 0.25
SHARDS = 32
)
// shardIndex is used to indicate which shard a given index belong to.
var shardIndexes = make([]uint64, SHARDS)
// init will initialize the shardIndexes.
func init() {
var step uint64 = 1 << 59 // 2^64/SHARDS
var t uint64 = math.MaxUint64
for i := SHARDS - 1; i >= 0; i-- {
shardIndexes[i] = t
t -= step
}
}
// ConcurrentSkipList is a struct contains a slice of concurrent skip list.
type ConcurrentSkipList struct {
skipLists []*skipList
level int
}
// 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 NewConcurrentSkipList(level int) (*ConcurrentSkipList, error) {
if level <= 0 || level > MAX_LEVEL {
return nil, errors.New("invalid level, level must between 1 to 32")
}
skipLists := make([]*skipList, SHARDS, SHARDS)
for i := 0; i < SHARDS; i++ {
skipLists[i] = newSkipList(level)
}
return &ConcurrentSkipList{
skipLists: skipLists,
level: level,
}, nil
}
// Level will return the level of skip list.
func (s *ConcurrentSkipList) Level() int {
return s.level
}
// Length will return the length of skip list.
func (s *ConcurrentSkipList) Length() int32 {
var length int32
for _, sl := range s.skipLists {
length += sl.getLength()
}
return length
}
// 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 (s *ConcurrentSkipList) Search(index uint64) (*Node, bool) {
sl := s.skipLists[getShardIndex(index)]
if atomic.LoadInt32(&sl.length) == 0 {
return nil, false
}
result := sl.searchWithoutPreviousNodes(index)
return result, result != nil
}
// Insert will insert a value into skip list. If skip has these this index, overwrite the value, otherwise add it.
func (s *ConcurrentSkipList) Insert(index uint64, value interface{}) {
// Ignore nil value.
if value == nil {
return
}
sl := s.skipLists[getShardIndex(index)]
sl.insert(index, value)
}
// Delete the node with the given index.
func (s *ConcurrentSkipList) Delete(index uint64) {
sl := s.skipLists[getShardIndex(index)]
if atomic.LoadInt32(&sl.length) == 0 {
return
}
sl.delete(index)
}
// 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 (s *ConcurrentSkipList) ForEach(f func(node *Node) bool) {
for _, sl := range s.skipLists {
if sl.getLength() == 0 {
continue
}
nodes := sl.snapshot()
stop := false
for _, node := range nodes {
if !f(node) {
stop = true
break
}
}
if stop {
break
}
}
}
// 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.
func (s *ConcurrentSkipList) Sub(startNumber int32, length int32) []*Node {
// Ignore invalid parameter.
if startNumber > s.Length() || startNumber < 0 || length <= 0 {
return nil
}
var result []*Node
var position, count int32 = 0, 0
for _, sl := range s.skipLists {
if l := sl.getLength(); l == 0 || position+l <= startNumber {
position += l
continue
}
nodes := sl.snapshot()
for _, node := range nodes {
if position < startNumber {
position++
continue
}
if count == length {
break
}
result = append(result, node)
count++
}
if count == length {
break
}
}
return result
}
// Locate which shard the given index belong to.
func getShardIndex(index uint64) int {
result := -1
for i, t := range shardIndexes {
if index <= t {
result = i
break
}
}
return result
}
// 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/
func Hash(input []byte) uint64 {
h := xxhash.New64()
h.Write(input)
return h.Sum64()
}
skipList. go 원본 파일
package ConcurrentSkipList
import (
"math/rand"
"sync"
"sync/atomic"
)
type skipList struct {
level int
length int32
head *Node
tail *Node
mutex sync.RWMutex
}
// newSkipList will create a concurrent skip list with given level.
func newSkipList(level int) *skipList {
head := newNode(0, nil, level)
var tail *Node
for i := 0; i < len(head.nextNodes); i++ {
head.nextNodes[i] = tail
}
return &skipList{
level: level,
length: 0,
head: head,
tail: tail,
}
}
// searchWithPreviousNode will search given index in skip list.
// The first return value represents the previous nodes need to update when call Insert function.
// The second return value represents the value with given index or the closet value whose index is larger than given index.
func (s *skipList) searchWithPreviousNodes(index uint64) ([]*Node, *Node) {
// Store all previous value whose index is less than index and whose next value's index is larger than index.
previousNodes := make([]*Node, s.level)
// fmt.Printf("start doSearch:%v
", index)
currentNode := s.head
// Iterate from top level to bottom level.
for l := s.level - 1; l >= 0; l-- {
// Iterate value util value's index is >= given index.
// The max iterate count is skip list's length. So the worst O(n) is N.
for currentNode.nextNodes[l] != s.tail && currentNode.nextNodes[l].index < index {
currentNode = currentNode.nextNodes[l]
}
// When next value's index is >= given index, add current value whose index < given index.
previousNodes[l] = currentNode
}
// Avoid point to tail which will occur panic in Insert and Delete function.
// When the next value is tail.
// The index is larger than the maximum index in the skip list or skip list's length is 0. Don't point to tail.
// When the next value isn't tail.
// Next value's index must >= given index. Point to it.
if currentNode.nextNodes[0] != s.tail {
currentNode = currentNode.nextNodes[0]
}
// fmt.Printf("previous value:
")
// for _, n := range previousNodes {
// fmt.Printf("%p\t", n)
// }
// fmt.Println()
// fmt.Printf("end doSearch %v
", index)
return previousNodes, currentNode
}
// searchWithoutPreviousNodes will return the value whose index is given index.
// If can not find the given index, return nil.
// This function is faster than searchWithPreviousNodes and it used to only searching index.
func (s *skipList) searchWithoutPreviousNodes(index uint64) *Node {
currentNode := s.head
// Read lock and unlock.
s.mutex.RLock()
defer s.mutex.RUnlock()
// Iterate from top level to bottom level.
for l := s.level - 1; l >= 0; l-- {
// Iterate value util value's index is >= given index.
// The max iterate count is skip list's length. So the worst O(n) is N.
for currentNode.nextNodes[l] != s.tail && currentNode.nextNodes[l].index < index {
currentNode = currentNode.nextNodes[l]
}
}
currentNode = currentNode.nextNodes[0]
if currentNode == s.tail || currentNode.index > index {
return nil
} else if currentNode.index == index {
return currentNode
} else {
return nil
}
}
// insert will insert a value into skip list and update the length.
// If skip has these this index, overwrite the value, otherwise add it.
func (s *skipList) insert(index uint64, value interface{}) {
// Write lock and unlock.
s.mutex.Lock()
defer s.mutex.Unlock()
previousNodes, currentNode := s.searchWithPreviousNodes(index)
if currentNode != s.head && currentNode.index == index {
currentNode.value = value
return
}
// Make a new value.
newNode := newNode(index, value, s.randomLevel())
// Adjust pointer. Similar to update linked list.
for i := len(newNode.nextNodes) - 1; i >= 0; i-- {
// Firstly, new value point to next value.
newNode.nextNodes[i] = previousNodes[i].nextNodes[i]
// Secondly, previous nodes point to new value.
previousNodes[i].nextNodes[i] = newNode
// Finally, in order to release the slice, point to nil.
previousNodes[i] = nil
}
atomic.AddInt32(&s.length, 1)
for i := len(newNode.nextNodes); i < len(previousNodes); i++ {
previousNodes[i] = nil
}
}
// delete will find the index is existed or not firstly.
// If existed, delete it and update length, otherwise do nothing.
func (s *skipList) delete(index uint64) {
// Write lock and unlock.
s.mutex.Lock()
defer s.mutex.Unlock()
previousNodes, currentNode := s.searchWithPreviousNodes(index)
// If skip list length is 0 or could not find value with the given index.
if currentNode != s.head && currentNode.index == index {
// Adjust pointer. Similar to update linked list.
for i := 0; i < len(currentNode.nextNodes); i++ {
previousNodes[i].nextNodes[i] = currentNode.nextNodes[i]
currentNode.nextNodes[i] = nil
previousNodes[i] = nil
}
atomic.AddInt32(&s.length, -1)
}
for i := len(currentNode.nextNodes); i < len(previousNodes); i++ {
previousNodes[i] = nil
}
}
// snapshot will create a snapshot of the skip list and return a slice of the nodes.
func (s *skipList) snapshot() []*Node {
s.mutex.RLock()
defer s.mutex.RUnlock()
result := make([]*Node, s.length)
i := 0
currentNode := s.head.nextNodes[0]
for currentNode != s.tail {
node := &Node{
index: currentNode.index,
value: currentNode.value,
nextNodes: nil,
}
result[i] = node
currentNode = currentNode.nextNodes[0]
i++
}
return result
}
// getLength will return the length of skip list.
func (s *skipList) getLength() int32 {
return atomic.LoadInt32(&s.length)
}
// randomLevel will generate and random level that level > 0 and level < skip list's level
// This comes from redis's implementation.
func (s *skipList) randomLevel() int {
level := 1
for rand.Float64() < PROBABILITY && level < s.level {
level++
}
return level
}
node. go 원본 파일
package ConcurrentSkipList
type Node struct {
index uint64
value interface{}
nextNodes []*Node
}
// newNode will create a node using in this package but not external package.
func newNode(index uint64, value interface{}, level int) *Node {
return &Node{
index: index,
value: value,
nextNodes: make([]*Node, level, level),
}
}
// Index will return the node's index.
func (n *Node) Index() uint64 {
return n.index
}
// Value will return the node's value.
func (n *Node) Value() interface{} {
return n.value
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.