skiplist

package
v0.0.0-...-b800c40 Latest Latest
Warning

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

 Go to latest Published: Aug 7, 2017 License: Apache-2.0 Imports: 10 Imported by: 0

Documentation

Index

Constants

View Source 
const MaxLevel = 32

Variables

View Source 
var Debug bool

Functions

func CompareBS 

func CompareBS(this, that unsafe.Pointer) int

func CompareBytes 

func CompareBytes(this, that unsafe.Pointer) int

func CompareInt 

func CompareInt(this, that unsafe.Pointer) int

func NewByteKeyItem 

func NewByteKeyItem(k []byte) unsafe.Pointer

func NewMergeIterator 

func NewMergeIterator(iters []*Iterator) *mIterator

Types

type AccessBarrier 

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

func (*AccessBarrier) Acquire 

func (ab *AccessBarrier) Acquire() *BarrierSession

func (*AccessBarrier) FlushSession 

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

func (*AccessBarrier) Release 

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

type ActionBuffer 

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

type BarrierSession 

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

type BarrierSessionDestructor 

type BarrierSessionDestructor func(objectRef unsafe.Pointer)

type Builder 

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

Concurrent bottom-up skiplist builder

func NewBuilder 

func NewBuilder() *Builder

func NewBuilderWithConfig 

func NewBuilderWithConfig(cfg Config) *Builder

func (*Builder) Assemble 

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

func (*Builder) NewSegment 

func (b *Builder) NewSegment() *Segment

func (*Builder) SetItemSizeFunc 

func (b *Builder) SetItemSizeFunc(fn ItemSizeFn)

type CompareFn 

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

type Config 

type Config struct {
	ItemSize ItemSizeFn

	UseMemoryMgmt     bool
	Malloc            MallocFn
	Free              FreeFn
	BarrierDestructor BarrierSessionDestructor
}

func DefaultConfig 

func DefaultConfig() Config

func (*Config) SetItemSizeFunc 

func (cfg *Config) SetItemSizeFunc(fn ItemSizeFn)

type FreeFn 

type FreeFn func(unsafe.Pointer)

type ItemSizeFn 

type ItemSizeFn func(unsafe.Pointer) int

type Iterator 

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

func (*Iterator) Close 

func (it *Iterator) Close()

func (*Iterator) Delete 

func (it *Iterator) Delete()

func (*Iterator) Get 

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

func (*Iterator) GetNode 

func (it *Iterator) GetNode() *Node

func (*Iterator) Next 

func (it *Iterator) Next()

func (*Iterator) Seek 

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

func (*Iterator) SeekFirst 

func (it *Iterator) SeekFirst()

func (*Iterator) SeekWithCmp 

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

func (*Iterator) Valid 

func (it *Iterator) Valid() bool

type MallocFn 

type MallocFn func(int) unsafe.Pointer

type Node 

type Node struct {
	GClink *Node
	// contains filtered or unexported fields
}
func (n *Node) GetLink() *Node

func (*Node) Item 

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

func (Node) Level 

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

func (Node) Size 

func (n Node) Size() int

type NodeCallback 

type NodeCallback func(*Node)

type NodeRef 

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

type Segment 

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

func (*Segment) Add 

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

func (*Segment) SetNodeCallback 

func (s *Segment) SetNodeCallback(fn NodeCallback)

type Skiplist 

type Skiplist struct {
	Stats Stats

	Config
	// contains filtered or unexported fields
}

func New 

func New() *Skiplist

func NewWithConfig 

func NewWithConfig(cfg Config) *Skiplist

func (*Skiplist) Delete 

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

func (*Skiplist) DeleteNode 

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

func (*Skiplist) FreeBuf 

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

func (*Skiplist) FreeNode 

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

func (*Skiplist) GetAccesBarrier 

func (s *Skiplist) GetAccesBarrier() *AccessBarrier

func (*Skiplist) GetRangeSplitItems 

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

Explicit barrier and release should be used by the caller before and after this function call

func (*Skiplist) GetStats 

func (s *Skiplist) GetStats() StatsReport

func (*Skiplist) HeadNode 

func (s *Skiplist) HeadNode() *Node

func (*Skiplist) Insert 

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

func (*Skiplist) Insert2 

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

func (*Skiplist) Insert3 

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

func (*Skiplist) MakeBuf 

func (s *Skiplist) MakeBuf() *ActionBuffer

func (*Skiplist) MemoryInUse 

func (s *Skiplist) MemoryInUse() int64

func (*Skiplist) NewIterator 

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

func (*Skiplist) NewLevel 

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

func (*Skiplist) Size 

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

func (*Skiplist) TailNode 

func (s *Skiplist) TailNode() *Node

type Stats 

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

func (*Stats) AddInt64 

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

func (*Stats) AddUint64 

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

func (*Stats) IsLocal 

func (s *Stats) IsLocal(flag bool)

func (*Stats) Merge 

func (s *Stats) Merge(sts *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
}

func (*StatsReport) Apply 

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

func (StatsReport) String 

func (s StatsReport) String() string

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.