list

Documentation

Overview

list/x_skl_utils.go

Index

• Constants
• type BasicLinkedList
• type LinkedList
  • func NewLinkedList[T comparable]() LinkedList[T]
• type NodeElement
  • func NewNodeElement[T comparable](v T) *NodeElement[T]
  • func (e *NodeElement[T]) HasNext() bool
  • func (e *NodeElement[T]) HasPrev() bool
  • func (e *NodeElement[T]) Next() *NodeElement[T]
  • func (e *NodeElement[T]) Prev() *NodeElement[T]
• type SkipList
  • func NewSkl[K infra.OrderedKey, V any](typ SklType, opts ...SklOption[K, V]) (SkipList[K, V], error)
• type SklElement
• type SklIterationItem
• type SklOption
  • func WithSklKeyCmpDesc[K infra.OrderedKey, V any]() SklOption[K, V]
  • func WithSklRandLevelGen[K infra.OrderedKey, V any](gen SklRand) SklOption[K, V]
  • func WithXComSklEnableConc[K infra.OrderedKey, V any]() SklOption[K, V]
  • func WithXComSklValComparator[K infra.OrderedKey, V any](cmp SklValComparator[V]) SklOption[K, V]
  • func WithXConcSklDataNodeLinkedListMode[K infra.OrderedKey, V any](cmp SklValComparator[V]) SklOption[K, V]
  • func WithXConcSklDataNodeRbtreeMode[K infra.OrderedKey, V any](cmp SklValComparator[V], borrowSucc ...bool) SklOption[K, V]
  • func WithXConcSklDataNodeUniqueMode[K infra.OrderedKey, V any]() SklOption[K, V]
  • func WithXConcSklOptimisticVersionGen[K infra.OrderedKey, V any](verGen id.UUIDGen) SklOption[K, V]
• type SklRand
• type SklType
• type SklValComparator
• type XSkipList
  • func NewXSkl[K infra.OrderedKey, V any](typ SklType, opts ...SklOption[K, V]) (XSkipList[K, V], error)

Constants

const (
	ErrXSklNotFound           = sklError("[x-skl] key or value not found")
	ErrXSklDisabledValReplace = sklError("[x-skl] value replace is disabled")
	ErrXSklConcRWLoadFailed   = sklError("[x-skl] concurrent read-write causes load failed")
	ErrXSklConcRWLoadEmpty    = sklError("[x-skl] concurrent read-write causes load empty")
	ErrXSklConcRemoving       = sklError("[x-skl] concurrent removing")
	ErrXSklConcRemoveTryLock  = sklError("[x-skl] concurrent remove acquires segmented lock failed")
	ErrXSklUnknownReason      = sklError("[x-skl] unknown reason error")
	ErrXSklUnknownType        = sklError("[x-skl] unknown skip list type")
	ErrXSklIsFull             = sklError("[x-skl] is full")
	ErrXSklIsEmpty            = sklError("[x-skl] is empty")
)

Types

type BasicLinkedList

type BasicLinkedList[T comparable] interface {
	Len() int64
	// Append appends the elements to the list l and returns the new elements.
	Append(elements ...*NodeElement[T]) []*NodeElement[T]
	// AppendValue appends the values to the list l and returns the new elements.
	AppendValue(values ...T) []*NodeElement[T]
	// InsertAfter inserts a value v as a new element immediately after element dstE and returns new element.
	// If e is nil, the value v will not be inserted.
	InsertAfter(v T, dstE *NodeElement[T]) *NodeElement[T]
	// InsertBefore inserts a value v as a new element immediately before element dstE and returns new element.
	// If e is nil, the value v will not be inserted.
	InsertBefore(v T, dstE *NodeElement[T]) *NodeElement[T]
	// Remove removes targetE from l if targetE is an element of list l and returns targetE or nil if the list is empty.
	Remove(targetE *NodeElement[T]) *NodeElement[T]
	// Foreach traverses the list l and executes function fn for each element.
	// If fn returns an error, the traversal stops and returns the error.
	Foreach(fn func(idx int64, e *NodeElement[T]) error) error
	// FindFirst finds the first element that satisfies the compareFn and returns the element and true if found.
	// If compareFn is not provided, it will use the default compare function that compares the value of element.
	FindFirst(v T, compareFn ...func(e *NodeElement[T]) bool) (*NodeElement[T], bool)
}

BasicLinkedList is a singly linked list interface.

type LinkedList

type LinkedList[T comparable] interface {
	BasicLinkedList[T]
	// ReverseForeach iterates the list in reverse order, calling fn for each element,
	// until either all elements have been visited.
	ReverseForeach(fn func(idx int64, e *NodeElement[T]))
	// Front returns the first element of doubly linked list l or nil if the list is empty.
	Front() *NodeElement[T]
	// Back returns the last element of doubly linked list l or nil if the list is empty.
	Back() *NodeElement[T]
	// PushFront inserts a new element e with value v at the front of list l and returns e.
	PushFront(v T) *NodeElement[T]
	// PushBack inserts a new element e with value v at the back of list l and returns e.
	PushBack(v T) *NodeElement[T]
	// MoveToFront moves an element e to the front of list l.
	MoveToFront(targetE *NodeElement[T]) bool
	// MoveToBack moves an element e to the back of list l.
	MoveToBack(targetE *NodeElement[T]) bool
	// MoveBefore moves an element srcE in front of element dstE.
	MoveBefore(srcE, dstE *NodeElement[T]) bool
	// MoveAfter moves an element srcE next to element dstE.
	MoveAfter(srcE, dstE *NodeElement[T]) bool
	// PushFrontList inserts a copy of another linked list at the front of list l.
	PushFrontList(srcList LinkedList[T])
	// PushBackList inserts a copy of another linked list at the back of list l.
	PushBackList(srcList LinkedList[T])
}

LinkedList is the doubly linked list interface.

func NewLinkedList

func NewLinkedList[T comparable]() LinkedList[T]

type NodeElement

type NodeElement[T comparable] struct {
	Value T // The type of value may be a small size type.
	// contains filtered or unexported fields
}

func NewNodeElement

func NewNodeElement[T comparable](v T) *NodeElement[T]

func (*NodeElement[T]) HasNext

func (e *NodeElement[T]) HasNext() bool

func (*NodeElement[T]) HasPrev

func (e *NodeElement[T]) HasPrev() bool

func (*NodeElement[T]) Next

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

func (*NodeElement[T]) Prev

func (e *NodeElement[T]) Prev() *NodeElement[T]

type SkipList

type SkipList[K infra.OrderedKey, V any] interface {
	Levels() int32
	Len() int64
	IndexCount() uint64
	Insert(key K, val V, ifNotPresent ...bool) error
	LoadFirst(key K) (SklElement[K, V], error)
	RemoveFirst(key K) (SklElement[K, V], error)
	Foreach(action func(i int64, item SklIterationItem[K, V]) bool)
	PopHead() (SklElement[K, V], error)
	PeekHead() SklElement[K, V]
}

The classic and unique skip list.

func NewSkl

func NewSkl[K infra.OrderedKey, V any](typ SklType, opts ...SklOption[K, V]) (SkipList[K, V], error)

type SklElement

type SklElement[K infra.OrderedKey, V any] interface {
	Key() K
	Val() V
}

type SklIterationItem

type SklIterationItem[K infra.OrderedKey, V any] interface {
	SklElement[K, V]
	NodeLevel() uint32
	NodeItemCount() int64
}

type SklOption

type SklOption[K infra.OrderedKey, V any] func(*sklOptions[K, V]) error

func WithSklKeyCmpDesc

func WithSklKeyCmpDesc[K infra.OrderedKey, V any]() SklOption[K, V]

func WithSklRandLevelGen

func WithSklRandLevelGen[K infra.OrderedKey, V any](gen SklRand) SklOption[K, V]

func WithXComSklEnableConc

func WithXComSklEnableConc[K infra.OrderedKey, V any]() SklOption[K, V]

func WithXComSklValComparator

func WithXComSklValComparator[K infra.OrderedKey, V any](cmp SklValComparator[V]) SklOption[K, V]

func WithXConcSklDataNodeLinkedListMode

func WithXConcSklDataNodeLinkedListMode[K infra.OrderedKey, V any](cmp SklValComparator[V]) SklOption[K, V]

func WithXConcSklDataNodeRbtreeMode

func WithXConcSklDataNodeRbtreeMode[K infra.OrderedKey, V any](cmp SklValComparator[V], borrowSucc ...bool) SklOption[K, V]

func WithXConcSklDataNodeUniqueMode

func WithXConcSklDataNodeUniqueMode[K infra.OrderedKey, V any]() SklOption[K, V]

func WithXConcSklOptimisticVersionGen

func WithXConcSklOptimisticVersionGen[K infra.OrderedKey, V any](verGen id.UUIDGen) SklOption[K, V]

type SklRand

type SklRand func(maxLevel int, currentElements int64) int32

type SklType

type SklType uint8

const (
	// XComSkl is the classic skip list.
	// It does not support duplicate keys and values.
	// It is not thread-safe.
	XComSkl SklType = iota
	// XConcSkl is the concurrent skip list.
	// It supports duplicate keys and values.
	XConcSkl
)

type SklValComparator

type SklValComparator[V any] func(i, j V) int64

type XSkipList

type XSkipList[K infra.OrderedKey, V any] interface {
	SkipList[K, V]
	LoadIfMatch(key K, matcher func(that V) bool) ([]SklElement[K, V], error)
	LoadAll(key K) ([]SklElement[K, V], error)
	RemoveIfMatch(key K, matcher func(that V) bool) ([]SklElement[K, V], error)
	RemoveAll(key K) ([]SklElement[K, V], error)
}

The X means the extended interface and it could store duplicate keys and values.

func NewXSkl

func NewXSkl[K infra.OrderedKey, V any](typ SklType, opts ...SklOption[K, V]) (XSkipList[K, V], error)