skiplist

package
v0.0.0-...-5c6c1e7 Latest Latest
Warning

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

 Go to latest Published: Jul 29, 2022 License: Apache-2.0 Imports: 13 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var File_skiplist_proto protoreflect.FileDescriptor

Functions

This section is empty.

Types

type ListStore 

type ListStore interface {
	SaveElement(id int64, element *SkipListElement) error
	DeleteElement(id int64) error
	LoadElement(id int64) (*SkipListElement, error)
}

type MemStore 

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

func (*MemStore) DeleteElement 

func (m *MemStore) DeleteElement(id int64) error

func (*MemStore) LoadElement 

func (m *MemStore) LoadElement(id int64) (*SkipListElement, error)

func (*MemStore) SaveElement 

func (m *MemStore) SaveElement(id int64, element *SkipListElement) error

type NameBatch 

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

func LoadNameBatch 

func LoadNameBatch(data []byte) *NameBatch

func NewNameBatch 

func NewNameBatch() *NameBatch

func (*NameBatch) ContainsName 

func (nb *NameBatch) ContainsName(name string) (found bool)

func (*NameBatch) DeleteName 

func (nb *NameBatch) DeleteName(name string)

func (*NameBatch) ListNames 

func (nb *NameBatch) ListNames(startFrom string, visitNamesFn func(name string) bool) bool

func (*NameBatch) SplitBy 

func (nb *NameBatch) SplitBy(name string) (x, y *NameBatch)

func (*NameBatch) ToBytes 

func (nb *NameBatch) ToBytes() []byte

func (*NameBatch) WriteName 

func (nb *NameBatch) WriteName(name string)

type NameBatchData 

type NameBatchData struct {
	Names [][]byte `protobuf:"bytes,1,rep,name=names,proto3" json:"names,omitempty"`
	// contains filtered or unexported fields
}

func (*NameBatchData) Descriptor deprecated 

func (*NameBatchData) Descriptor() ([]byte, []int)

Deprecated: Use NameBatchData.ProtoReflect.Descriptor instead.

func (*NameBatchData) GetNames 

func (x *NameBatchData) GetNames() [][]byte

func (*NameBatchData) ProtoMessage 

func (*NameBatchData) ProtoMessage()

func (*NameBatchData) ProtoReflect 

func (x *NameBatchData) ProtoReflect() protoreflect.Message

func (*NameBatchData) Reset 

func (x *NameBatchData) Reset()

func (*NameBatchData) String 

func (x *NameBatchData) String() string

type NameList 

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

func LoadNameList 

func LoadNameList(data []byte, store ListStore, batchSize int) *NameList

func (*NameList) DeleteName 

func (nl *NameList) DeleteName(name string) error

// case 1: exists in nextNode 

if nextNode != nil && nextNode.Key == name {
	remove from nextNode, update nextNode
	// TODO: merge with prevNode if possible?
	return
}

if nextNode is nil 

prevNode = list.Largestnode

if prevNode == nil and nextNode.Prev != nil 

prevNode = load(nextNode.Prev)

// case 2: does not exist // case 2.1 

if prevNode == nil {
	return
}

// case 2.2 

if prevNameBatch does not contain name {
	return
}

// case 3 delete from prevNameBatch if prevNameBatch + nextNode < capacityList 

// case 3.1
merge

else 

// case 3.2
update prevNode

func (*NameList) HasChanges 

func (nl *NameList) HasChanges() bool

func (*NameList) ListNames 

func (nl *NameList) ListNames(startFrom string, visitNamesFn func(name string) bool) error

func (*NameList) RemoteAllListElement 

func (nl *NameList) RemoteAllListElement() error

func (*NameList) ToBytes 

func (nl *NameList) ToBytes() []byte

func (*NameList) WriteName 

func (nl *NameList) WriteName(name string) error

Be reluctant to create new nodes. Try to fit into either previous node or next node. Prefer to add to previous node.

There are multiple cases after finding the name for greater or equal node

  1. found and node.Key == name The node contains a batch with leading key the same as the name nothing to do

  2. no such node found or node.Key > name

    if no such node found prevNode = list.LargestNode

    // case 2.1 if previousNode contains name nothing to do

    // prefer to add to previous node if prevNode != nil { // case 2.2 if prevNode has capacity prevNode.add name, and save return // case 2.3 split prevNode by name }

    // case 2.4 // merge into next node. Avoid too many nodes if adding data in reverse order. if nextNode is not nil and nextNode has capacity delete nextNode.Key nextNode.Key = name nextNode.batch.add name insert nodeNode.Key return

    // case 2.5 if prevNode is nil insert new node with key = name, value = batch{name} return

type SkipList 

type SkipList struct {
	StartLevels [maxLevel]*SkipListElementReference
	EndLevels   [maxLevel]*SkipListElementReference
	MaxNewLevel int
	MaxLevel    int
	ListStore   ListStore
	HasChanges  bool
}

func New 

func New(listStore ListStore) *SkipList

New returns a new empty, initialized Skiplist.

func NewSeed 

func NewSeed(seed int64, listStore ListStore) *SkipList

NewSeedEps returns a new empty, initialized Skiplist. Given a seed, a deterministic height/list behaviour can be achieved. Eps is used to compare keys given by the ExtractKey() function on equality.

func (*SkipList) ChangeValue 

func (t *SkipList) ChangeValue(e *SkipListElement, newValue []byte) (err error)

ChangeValue can be used to change the actual value of a node in the skiplist without the need of Deleting and reinserting the node again. Be advised, that ChangeValue only works, if the actual key from ExtractKey() will stay the same! ok is an indicator, wether the value is actually changed.

func (*SkipList) DeleteByKey 

func (t *SkipList) DeleteByKey(key []byte) (id int64, err error)

Delete removes an element equal to e from the skiplist, if there is one. If there are multiple entries with the same value, Delete will remove one of them (Which one will change based on the actual skiplist layout) Delete runs in approx. O(log(n))

func (*SkipList) DeleteElement 

func (t *SkipList) DeleteElement(element *SkipListElement) error

func (*SkipList) Find 

func (t *SkipList) Find(key []byte) (prevIfVisited *SkipListElement, elem *SkipListElement, ok bool, err error)

Find tries to find an element in the skiplist based on the key from the given ListElement. elem can be used, if ok is true. Find runs in approx. O(log(n))

func (*SkipList) FindGreaterOrEqual 

func (t *SkipList) FindGreaterOrEqual(key []byte) (prevIfVisited *SkipListElement, elem *SkipListElement, ok bool, err error)

FindGreaterOrEqual finds the first element, that is greater or equal to the given ListElement e. The comparison is done on the keys (So on ExtractKey()). FindGreaterOrEqual runs in approx. O(log(n))

func (*SkipList) GetLargestNode 

func (t *SkipList) GetLargestNode() (*SkipListElement, error)

GetLargestNode returns the very last/largest node in the skiplist. GetLargestNode runs in O(1)

func (*SkipList) GetLargestNodeReference 

func (t *SkipList) GetLargestNodeReference() *SkipListElementReference

func (*SkipList) GetSmallestNode 

func (t *SkipList) GetSmallestNode() (*SkipListElement, error)

GetSmallestNode returns the very first/smallest node in the skiplist. GetSmallestNode runs in O(1)

func (*SkipList) InsertByKey 

func (t *SkipList) InsertByKey(key []byte, idIfKnown int64, value []byte) (id int64, err error)

Insert inserts the given ListElement into the skiplist. Insert runs in approx. O(log(n))

func (*SkipList) IsEmpty 

func (t *SkipList) IsEmpty() bool

IsEmpty checks, if the skiplist is empty.

func (*SkipList) LoadElement 

func (t *SkipList) LoadElement(ref *SkipListElementReference) (*SkipListElement, error)

func (*SkipList) Next 

func (t *SkipList) Next(e *SkipListElement) (*SkipListElement, error)

Next returns the next element based on the given node. Next will loop around to the first node, if you call it on the last!

func (*SkipList) Prev 

func (t *SkipList) Prev(e *SkipListElement) (*SkipListElement, error)

Prev returns the previous element based on the given node. Prev will loop around to the last node, if you call it on the first!

func (*SkipList) SaveElement 

func (t *SkipList) SaveElement(element *SkipListElement) error

type SkipListElement 

type SkipListElement struct {
	Id    int64                       `protobuf:"varint,1,opt,name=id,proto3" json:"id,omitempty"`
	Next  []*SkipListElementReference `protobuf:"bytes,2,rep,name=next,proto3" json:"next,omitempty"`
	Level int32                       `protobuf:"varint,3,opt,name=level,proto3" json:"level,omitempty"`
	Key   []byte                      `protobuf:"bytes,4,opt,name=key,proto3" json:"key,omitempty"`
	Value []byte                      `protobuf:"bytes,5,opt,name=value,proto3" json:"value,omitempty"`
	Prev  *SkipListElementReference   `protobuf:"bytes,6,opt,name=prev,proto3" json:"prev,omitempty"`
	// contains filtered or unexported fields
}

func (*SkipListElement) Descriptor deprecated 

func (*SkipListElement) Descriptor() ([]byte, []int)

Deprecated: Use SkipListElement.ProtoReflect.Descriptor instead.

func (*SkipListElement) GetId 

func (x *SkipListElement) GetId() int64

func (*SkipListElement) GetKey 

func (x *SkipListElement) GetKey() []byte

func (*SkipListElement) GetLevel 

func (x *SkipListElement) GetLevel() int32

func (*SkipListElement) GetNext 

func (x *SkipListElement) GetNext() []*SkipListElementReference

func (*SkipListElement) GetPrev 

func (x *SkipListElement) GetPrev() *SkipListElementReference

func (*SkipListElement) GetValue 

func (x *SkipListElement) GetValue() []byte

func (*SkipListElement) ProtoMessage 

func (*SkipListElement) ProtoMessage()

func (*SkipListElement) ProtoReflect 

func (x *SkipListElement) ProtoReflect() protoreflect.Message

func (*SkipListElement) Reference 

func (node *SkipListElement) Reference() *SkipListElementReference

func (*SkipListElement) Reset 

func (x *SkipListElement) Reset()

func (*SkipListElement) String 

func (x *SkipListElement) String() string

type SkipListElementReference 

type SkipListElementReference struct {
	ElementPointer int64  `protobuf:"varint,1,opt,name=element_pointer,json=elementPointer,proto3" json:"element_pointer,omitempty"`
	Key            []byte `protobuf:"bytes,2,opt,name=key,proto3" json:"key,omitempty"`
	// contains filtered or unexported fields
}

func (*SkipListElementReference) Descriptor deprecated 

func (*SkipListElementReference) Descriptor() ([]byte, []int)

Deprecated: Use SkipListElementReference.ProtoReflect.Descriptor instead.

func (*SkipListElementReference) GetElementPointer 

func (x *SkipListElementReference) GetElementPointer() int64

func (*SkipListElementReference) GetKey 

func (x *SkipListElementReference) GetKey() []byte

func (*SkipListElementReference) IsNil 

func (ref *SkipListElementReference) IsNil() bool

func (*SkipListElementReference) ProtoMessage 

func (*SkipListElementReference) ProtoMessage()

func (*SkipListElementReference) ProtoReflect 

func (x *SkipListElementReference) ProtoReflect() protoreflect.Message

func (*SkipListElementReference) Reset 

func (x *SkipListElementReference) Reset()

func (*SkipListElementReference) String 

func (x *SkipListElementReference) String() string

type SkipListProto 

type SkipListProto struct {
	StartLevels []*SkipListElementReference `protobuf:"bytes,1,rep,name=start_levels,json=startLevels,proto3" json:"start_levels,omitempty"`
	EndLevels   []*SkipListElementReference `protobuf:"bytes,2,rep,name=end_levels,json=endLevels,proto3" json:"end_levels,omitempty"`
	MaxNewLevel int32                       `protobuf:"varint,3,opt,name=max_new_level,json=maxNewLevel,proto3" json:"max_new_level,omitempty"`
	MaxLevel    int32                       `protobuf:"varint,4,opt,name=max_level,json=maxLevel,proto3" json:"max_level,omitempty"`
	// contains filtered or unexported fields
}

func (*SkipListProto) Descriptor deprecated 

func (*SkipListProto) Descriptor() ([]byte, []int)

Deprecated: Use SkipListProto.ProtoReflect.Descriptor instead.

func (*SkipListProto) GetEndLevels 

func (x *SkipListProto) GetEndLevels() []*SkipListElementReference

func (*SkipListProto) GetMaxLevel 

func (x *SkipListProto) GetMaxLevel() int32

func (*SkipListProto) GetMaxNewLevel 

func (x *SkipListProto) GetMaxNewLevel() int32

func (*SkipListProto) GetStartLevels 

func (x *SkipListProto) GetStartLevels() []*SkipListElementReference

func (*SkipListProto) ProtoMessage 

func (*SkipListProto) ProtoMessage()

func (*SkipListProto) ProtoReflect 

func (x *SkipListProto) ProtoReflect() protoreflect.Message

func (*SkipListProto) Reset 

func (x *SkipListProto) Reset()

func (*SkipListProto) String 

func (x *SkipListProto) 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.