skiplist

Documentation

Index

• Constants
• Variables
• type ConcurrentSkipList
  • func NewConcurrent[K constraints.Ordered, T any]() *ConcurrentSkipList[K, T]
  • func (c *ConcurrentSkipList[K, T]) Delete(score K)
  • func (c *ConcurrentSkipList[K, T]) Draw() *ConcurrentSkipList[K, T]
  • func (c *ConcurrentSkipList[K, T]) Get(score K) (elem T, ok bool)
  • func (c *ConcurrentSkipList[K, T]) Insert(score K, elem T)
  • func (c *ConcurrentSkipList[K, T]) InsertOrUpdate(score K, elem T, cb InsertOrUpdateCb[T])
  • func (c *ConcurrentSkipList[K, T]) Len() int
  • func (c *ConcurrentSkipList[K, T]) Range(callback func(score K, v T) bool)
  • func (c *ConcurrentSkipList[K, T]) RangePrev(callback func(k K, v T) bool) *ConcurrentSkipList[K, T]
  • func (c *ConcurrentSkipList[K, T]) Remove(score K) *ConcurrentSkipList[K, T]
  • func (c *ConcurrentSkipList[K, T]) Set(score K, elem T)
  • func (c *ConcurrentSkipList[K, T]) TopMax(limit int, callback func(k K, v T) bool)
  • func (c *ConcurrentSkipList[K, T]) TopMin(limit int, callback func(score K, v T) bool)
  • func (c *ConcurrentSkipList[K, T]) TryGet(score K) (elem T, ok bool)
• type InsertOrUpdateCb
• type Node
• type Number
• type SkipList
  • func New[K constraints.Ordered, T any]() *SkipList[K, T]
  • func (s *SkipList[K, T]) Delete(score K)
  • func (s *SkipList[K, T]) Draw() *SkipList[K, T]
  • func (s *SkipList[K, T]) Get(score K) (elem T)
  • func (s *SkipList[K, T]) GetWithMeta(score K) (elem T, number Number[K], ok bool)
  • func (s *SkipList[K, T]) Insert(score K, elem T)
  • func (s *SkipList[K, T]) InsertInner(score K, elem T, level int) (prev T, replaced bool)
  • func (s *SkipList[K, T]) InsertOrUpdate(score K, elem T, cb InsertOrUpdateCb[T])
  • func (s *SkipList[K, T]) Len() int
  • func (s *SkipList[K, T]) Range(callback func(score K, v T) bool)
  • func (s *SkipList[K, T]) RangePrev(callback func(k K, v T) bool) *SkipList[K, T]
  • func (s *SkipList[K, T]) Remove(score K) *SkipList[K, T]
  • func (s *SkipList[K, T]) Set(score K, elem T)
  • func (s *SkipList[K, T]) Swap(score K, elem T) (prev T, replaced bool)
  • func (s *SkipList[K, T]) TopMax(limit int, callback func(k K, v T) bool)
  • func (s *SkipList[K, T]) TopMin(limit int, callback func(score K, v T) bool)
  • func (s *SkipList[K, T]) TryGet(score K) (elem T, ok bool)

Constants

const (
	SKIPLIST_MAXLEVEL = 32
)

Variables

var (
	ErrNotFound = errors.New("not found element")
)

Types

type ConcurrentSkipList

type ConcurrentSkipList[K constraints.Ordered, T any] struct {
	*SkipList[K, T]
	// contains filtered or unexported fields
}

ConcurrentSkipList represents a concurrent-safe skip list It embeds SkipList and adds a RWMutex for thread safety

func NewConcurrent

func NewConcurrent[K constraints.Ordered, T any]() *ConcurrentSkipList[K, T]

NewConcurrent returns a new concurrent-safe skip list

func (*ConcurrentSkipList[K, T]) Delete

func (c *ConcurrentSkipList[K, T]) Delete(score K)

Delete removes an element from the concurrent skip list

func (*ConcurrentSkipList[K, T]) Draw

func (c *ConcurrentSkipList[K, T]) Draw() *ConcurrentSkipList[K, T]

Draw draws the concurrent skip list

func (*ConcurrentSkipList[K, T]) Get

func (c *ConcurrentSkipList[K, T]) Get(score K) (elem T, ok bool)

Get retrieves an element from the concurrent skip list

func (*ConcurrentSkipList[K, T]) Insert

func (c *ConcurrentSkipList[K, T]) Insert(score K, elem T)

Insert inserts a new element into the concurrent skip list

func (*ConcurrentSkipList[K, T]) InsertOrUpdate

func (c *ConcurrentSkipList[K, T]) InsertOrUpdate(score K, elem T, cb InsertOrUpdateCb[T])

Insert or update an element into the concurrent skip list

func (*ConcurrentSkipList[K, T]) Len

func (c *ConcurrentSkipList[K, T]) Len() int

Len returns the length of the concurrent skip list

func (*ConcurrentSkipList[K, T]) Range

func (c *ConcurrentSkipList[K, T]) Range(callback func(score K, v T) bool)

Range iterates over elements in the concurrent skip list

func (*ConcurrentSkipList[K, T]) RangePrev

func (c *ConcurrentSkipList[K, T]) RangePrev(callback func(k K, v T) bool) *ConcurrentSkipList[K, T]

RangePrev iterates over elements in the concurrent skip list in reverse order

func (*ConcurrentSkipList[K, T]) Remove

func (c *ConcurrentSkipList[K, T]) Remove(score K) *ConcurrentSkipList[K, T]

Remove removes an element from the concurrent skip list

func (*ConcurrentSkipList[K, T]) Set

func (c *ConcurrentSkipList[K, T]) Set(score K, elem T)

Set sets a new element into the concurrent skip list

func (*ConcurrentSkipList[K, T]) TopMax

func (c *ConcurrentSkipList[K, T]) TopMax(limit int, callback func(k K, v T) bool)

TopMax returns the top max elements from the concurrent skip list

func (*ConcurrentSkipList[K, T]) TopMin

func (c *ConcurrentSkipList[K, T]) TopMin(limit int, callback func(score K, v T) bool)

TopMin returns the top min elements from the concurrent skip list

func (*ConcurrentSkipList[K, T]) TryGet

func (c *ConcurrentSkipList[K, T]) TryGet(score K) (elem T, ok bool)

TryGet retrieves an element from the concurrent skip list

type InsertOrUpdateCb

type InsertOrUpdateCb[T any] func(prev T, new T) T

type Node

type Node[K constraints.Ordered, T any] struct {
	NodeLevel []struct {
		// contains filtered or unexported fields
	}
	// contains filtered or unexported fields
}

type Number

type Number[K constraints.Ordered] struct {
	Total    int
	Keys     []K
	Level    []int
	MaxLevel []int
}

debug 使用

type SkipList

type SkipList[K constraints.Ordered, T any] struct {
	// contains filtered or unexported fields
}

func New

func New[K constraints.Ordered, T any]() *SkipList[K, T]

初始化skiplist func New[T any](compare func(T, T) int) *SkipList[T] {

func (*SkipList[K, T]) Delete

func (s *SkipList[K, T]) Delete(score K)

根据score删除

func (*SkipList[K, T]) Draw

func (s *SkipList[K, T]) Draw() *SkipList[K, T]

func (*SkipList[K, T]) Get

func (s *SkipList[K, T]) Get(score K) (elem T)

根据score获取value值

func (*SkipList[K, T]) GetWithMeta

func (s *SkipList[K, T]) GetWithMeta(score K) (elem T, number Number[K], ok bool)

debug使用, 返回查找某个key 比较的次数+经过的节点数

func (*SkipList[K, T]) Insert

func (s *SkipList[K, T]) Insert(score K, elem T)

设置值

func (*SkipList[K, T]) InsertInner

func (s *SkipList[K, T]) InsertInner(score K, elem T, level int) (prev T, replaced bool)

方便给作者调试用的函数

func (*SkipList[K, T]) InsertOrUpdate

func (s *SkipList[K, T]) InsertOrUpdate(score K, elem T, cb InsertOrUpdateCb[T])

Insert or update an element into the skip list

func (*SkipList[K, T]) Len

func (s *SkipList[K, T]) Len() int

返回长度

func (*SkipList[K, T]) Range

func (s *SkipList[K, T]) Range(callback func(score K, v T) bool)

遍历

func (*SkipList[K, T]) RangePrev

func (s *SkipList[K, T]) RangePrev(callback func(k K, v T) bool) *SkipList[K, T]

从后向前倒序遍历b tree

func (*SkipList[K, T]) Remove

func (s *SkipList[K, T]) Remove(score K) *SkipList[K, T]

根据score删除元素

func (*SkipList[K, T]) Set

func (s *SkipList[K, T]) Set(score K, elem T)

设置值, 和Insert是同义词

func (*SkipList[K, T]) Swap

func (s *SkipList[K, T]) Swap(score K, elem T) (prev T, replaced bool)

func (*SkipList[K, T]) TopMax

func (s *SkipList[K, T]) TopMax(limit int, callback func(k K, v T) bool)

返回最大的n个值, 降序返回, 10, 9, 8, 7

func (*SkipList[K, T]) TopMin

func (s *SkipList[K, T]) TopMin(limit int, callback func(score K, v T) bool)

返回最小的n个值, 升序返回, 比如0,1,2,3

func (*SkipList[K, T]) TryGet

func (s *SkipList[K, T]) TryGet(score K) (elem T, ok bool)

获取