skiplist

package
v0.0.0-...-eda3dc5 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 12, 2019 License: Apache-2.0 Imports: 10 Imported by: 0

Documentation

Index

Constants

View Source 
const MaxLevel = 32

MaxLevel is the limit for the skiplist levels

Variables

View Source 
var (
	MinItem unsafe.Pointer
	MaxItem = unsafe.Pointer(^uintptr(0))
)
View Source 
var Debug bool

Debug flag enables additional stats gathering

Functions

func Compare 

func Compare(cmp CompareFn, this, that unsafe.Pointer) int

func CompareBS 

func CompareBS(this, that unsafe.Pointer) int

CompareBS is a barrier session comparator based on seqno

func CompareBytes 

func CompareBytes(this, that unsafe.Pointer) int

CompareBytes is a byte item comparator

func CompareInt 

func CompareInt(this, that unsafe.Pointer) int

CompareInt is a helper integer item comparator

func NewByteKeyItem 

func NewByteKeyItem(k []byte) unsafe.Pointer

NewByteKeyItem creates a new item from bytes

Types

type AcceptFn 

type AcceptFn func(unsafe.Pointer) bool

type AccessBarrier 

type AccessBarrier struct {
	sync.Mutex
	// contains filtered or unexported fields
}

AccessBarrier is the SMR core data structure for the skiplist

func (*AccessBarrier) Acquire 

func (ab *AccessBarrier) Acquire() *BarrierSession

Acquire marks enter of an accessor in the skiplist

func (*AccessBarrier) FlushSession 

func (ab *AccessBarrier) FlushSession(ref unsafe.Pointer)

FlushSession closes the current barrier session and starts the new session. The caller should provide the destructor pointer for the new session.

func (*AccessBarrier) Release 

func (ab *AccessBarrier) Release(bs *BarrierSession)

Release marks leaving of an accessor in the skiplist

type ActionBuffer 

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

ActionBuffer is a temporary buffer used by skiplist operations

type BarrierSession 

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

BarrierSession handle tracks the live accessors of a barrier session

type BarrierSessionDestructor 

type BarrierSessionDestructor func(objectRef unsafe.Pointer)

BarrierSessionDestructor is a callback for SMR based reclaim of objects

type BatchOpCallback 

type BatchOpCallback func(*Node, CompareFn, unsafe.Pointer, BatchOpIterator) error

type BatchOpIterator 

type BatchOpIterator interface {
	Next()
	Valid() bool
	Item() unsafe.Pointer
}

type Builder 

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

Builder performs concurrent bottom-up skiplist build

func NewBuilder 

func NewBuilder() *Builder

NewBuilder creates a builder based on default config

func NewBuilderWithConfig 

func NewBuilderWithConfig(cfg Config) *Builder

NewBuilderWithConfig creates a builder from a config

func (*Builder) Assemble 

func (b *Builder) Assemble(segments ...*Segment) *Skiplist

Assemble multiple skiplist segments and form a parent skiplist

func (*Builder) NewSegment 

func (b *Builder) NewSegment() *Segment

NewSegment creates a new skiplist segment

func (*Builder) SetItemSizeFunc 

func (b *Builder) SetItemSizeFunc(fn ItemSizeFn)

SetItemSizeFunc configures items size function

type CompareFn 

type CompareFn func(unsafe.Pointer, unsafe.Pointer) int

CompareFn is the skiplist item comparator

type Config 

type Config struct {
	ItemSize ItemSizeFn

	UseMemoryMgmt     bool
	Malloc            MallocFn
	Free              FreeFn
	BarrierDestructor BarrierSessionDestructor
}

Config holds skiplist configuration

func DefaultConfig 

func DefaultConfig() Config

DefaultConfig returns default skiplist configuration

func (*Config) SetItemSizeFunc 

func (cfg *Config) SetItemSizeFunc(fn ItemSizeFn)

SetItemSizeFunc configures item size function

type FreeFn 

type FreeFn func(unsafe.Pointer)

FreeFn is a custom memory deallocator

type ItemSizeFn 

type ItemSizeFn func(unsafe.Pointer) int

ItemSizeFn returns size of a skiplist item

type Iterator 

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

Iterator is used for lookup and range operations on skiplist

func (*Iterator) Close 

func (it *Iterator) Close()

Close is a destructor

func (*Iterator) Delete 

func (it *Iterator) Delete()

Delete removes the current item from the skiplist

func (*Iterator) Get 

func (it *Iterator) Get() unsafe.Pointer

Get returns the current item

func (*Iterator) GetNode 

func (it *Iterator) GetNode() *Node

GetNode returns node which holds the current item

func (*Iterator) Next 

func (it *Iterator) Next()

Next moves iterator to the next item

func (*Iterator) Seek 

func (it *Iterator) Seek(itm unsafe.Pointer) bool

Seek moves iterator to a provided item

func (*Iterator) SeekFirst 

func (it *Iterator) SeekFirst()

SeekFirst moves cursor to the start

func (*Iterator) SeekPrev 

func (it *Iterator) SeekPrev(itm unsafe.Pointer, skip func(unsafe.Pointer) bool)

SeekPrev moves iterator to the provided item or an item less than the lookup item

func (*Iterator) SeekWithCmp 

func (it *Iterator) SeekWithCmp(itm unsafe.Pointer, cmp CompareFn, eqCmp CompareFn) bool

SeekWithCmp moves iterator to a provided item by using custom comparator

func (*Iterator) SeekWithSkip 

func (it *Iterator) SeekWithSkip(itm unsafe.Pointer, skipItm func(unsafe.Pointer) bool) bool

SeekWithSkip performs Seek() with optional skipping of nodes while reading nodes as part of finding the item.

func (*Iterator) Valid 

func (it *Iterator) Valid() bool

Valid returns true when iterator reaches the end If the specified item is not found, start with the predecessor node This is used for implementing disk block based storage

type MallocFn 

type MallocFn func(int) unsafe.Pointer

MallocFn is a custom memory allocator

type MergeIterator 

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

MergeIterator aggregates multiple iterators

func NewMergeIterator 

func NewMergeIterator(iters []*Iterator) *MergeIterator

NewMergeIterator creates an iterator that merges multiple iterators

func (*MergeIterator) Get 

func (mit *MergeIterator) Get() unsafe.Pointer

Get returns current item

func (*MergeIterator) GetNode 

func (mit *MergeIterator) GetNode() *Node

GetNode returns node for the current item

func (*MergeIterator) Next 

func (mit *MergeIterator) Next()

Next moves cursor to the next item

func (*MergeIterator) Seek 

func (mit *MergeIterator) Seek(itm unsafe.Pointer) bool

Seek moves cursor to the specified item, if present

func (*MergeIterator) SeekFirst 

func (mit *MergeIterator) SeekFirst()

SeekFirst moves cursor to the first item

func (*MergeIterator) Valid 

func (mit *MergeIterator) Valid() bool

Valid returns false when cursor reaches end

type Node 

type Node struct {
	GClink  *Node
	DataPtr uint64
	// contains filtered or unexported fields
}

Node represents skiplist node header 

func (n *Node) GetLink() *Node

GetLink returns link pointer from the node

func (*Node) Item 

func (n *Node) Item() unsafe.Pointer

Item returns item held by the node

func (Node) Level 

func (n Node) Level() int

Level returns the level of a node in the skiplist 

func (n *Node) SetLink(l *Node)

SetLink can be used to set link pointer for the node

func (Node) Size 

func (n Node) Size() int

Size returns memory used by the node

type NodeCallback 

type NodeCallback func(*Node)

NodeCallback is used by segment builder

type NodeRef 

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

NodeRef is a wrapper for node pointer

type Segment 

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

Segment is a skiplist segment

func (*Segment) Add 

func (s *Segment) Add(itm unsafe.Pointer)

Add an item into skiplist segment

func (*Segment) SetNodeCallback 

func (s *Segment) SetNodeCallback(fn NodeCallback)

SetNodeCallback sets callback for segment builder

type Skiplist 

type Skiplist struct {
	Stats Stats

	Config
	// contains filtered or unexported fields
}

Skiplist - core data structure

func New 

func New() *Skiplist

New creates a skiplist with default config

func NewWithConfig 

func NewWithConfig(cfg Config) *Skiplist

NewWithConfig creates a config from given config

func (*Skiplist) Delete 

func (s *Skiplist) Delete(itm unsafe.Pointer, cmp CompareFn,
	buf *ActionBuffer, sts *Stats) bool

Delete an item from the skiplist

func (*Skiplist) DeleteNode 

func (s *Skiplist) DeleteNode(n *Node, cmp CompareFn,
	buf *ActionBuffer, sts *Stats) bool

DeleteNode an item from the skiplist by specifying its node

func (*Skiplist) ExecBatchOps 

func (s *Skiplist) ExecBatchOps(opItr BatchOpIterator, head, tail *Node,
	callb BatchOpCallback, cmp CompareFn,
	validNode ValidNodeFn, sts *Stats) error

func (*Skiplist) FreeBuf 

func (s *Skiplist) FreeBuf(b *ActionBuffer)

FreeBuf frees an action buffer

func (*Skiplist) FreeNode 

func (s *Skiplist) FreeNode(n *Node, sts *Stats)

FreeNode deallocates the skiplist node memory

func (*Skiplist) GetAccesBarrier 

func (s *Skiplist) GetAccesBarrier() *AccessBarrier

GetAccesBarrier returns current active access barrier

func (*Skiplist) GetRangeSplitItems 

func (s *Skiplist) GetRangeSplitItems(nways int) []unsafe.Pointer

GetRangeSplitItems returns `nways` split range pivots of the skiplist items Explicit barrier and release should be used by the caller before and after this function call

func (*Skiplist) GetStats 

func (s *Skiplist) GetStats() StatsReport

GetStats returns skiplist stats

func (*Skiplist) Insert 

func (s *Skiplist) Insert(itm unsafe.Pointer, cmp CompareFn,
	buf *ActionBuffer, sts *Stats) (success bool)

Insert adds an item into the skiplist

func (*Skiplist) Insert2 

func (s *Skiplist) Insert2(itm unsafe.Pointer, inscmp CompareFn, eqCmp CompareFn,
	buf *ActionBuffer, randFn func() float32, sts *Stats) (*Node, bool)

Insert2 is a more verbose version of Insert

func (*Skiplist) Insert3 

func (s *Skiplist) Insert3(itm unsafe.Pointer, insCmp CompareFn, eqCmp CompareFn,
	buf *ActionBuffer, itemLevel int, skipFindPath bool, sts *Stats) (*Node, bool)

Insert3 is more verbose version of Insert2

func (*Skiplist) MakeBuf 

func (s *Skiplist) MakeBuf() *ActionBuffer

MakeBuf creates an action buffer

func (*Skiplist) MemoryInUse 

func (s *Skiplist) MemoryInUse() int64

MemoryInUse returns memory used by skiplist

func (*Skiplist) NewIterator 

func (s *Skiplist) NewIterator(cmp CompareFn,
	buf *ActionBuffer) *Iterator

NewIterator creates an iterator for skiplist

func (*Skiplist) NewLevel 

func (s *Skiplist) NewLevel(randFn func() float32) int

NewLevel returns a random level for the next node

func (*Skiplist) Size 

func (s *Skiplist) Size(n *Node) int

Size returns the size of a node

type Stats 

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

Stats keeps stats for a skiplist instance

func (*Stats) AddInt64 

func (s *Stats) AddInt64(src *int64, val int64)

AddInt64 provides atomic add

func (*Stats) AddUint64 

func (s *Stats) AddUint64(src *uint64, val uint64)

AddUint64 provides atomic add

func (*Stats) IsLocal 

func (s *Stats) IsLocal(flag bool)

IsLocal reports true if the stats is partial

func (*Stats) Merge 

func (s *Stats) Merge(sts *Stats)

Merge updates global stats with partial stats and resets partial stats

type StatsReport 

type StatsReport struct {
	ReadConflicts       uint64
	InsertConflicts     uint64
	NextPointersPerNode float64
	NodeDistribution    [MaxLevel + 1]int64
	NodeCount           int
	SoftDeletes         int64
	Memory              int64

	NodeAllocs int64
	NodeFrees  int64
}

StatsReport is used for reporting skiplist statistics

func (*StatsReport) Apply 

func (report *StatsReport) Apply(s *Stats)

Apply updates the report with provided paritial stats

func (StatsReport) String 

func (report StatsReport) String() string

type ValidNodeFn 

type ValidNodeFn func(*Node) bool

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.