sortedmap

package module
v0.0.0-...-af46f3e Latest Latest
Warning

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

 Go to latest Published: Feb 6, 2021 License: Apache-2.0 Imports: 7 Imported by: 0

README

sortedmap

Go package providing sorted maps implemented as either a Left-Leaning Red-Black Tree (in memory) or a B+Tree (pageable)

API Reference

type Key interface{}
type Value interface{}

type Compare func(key1 Key, key2 Key) (result int, err error)

func CompareInt(key1 Key, key2 Key) (result int, err error)
func CompareUint32(key1 Key, key2 Key) (result int, err error)
func CompareUint64(key1 Key, key2 Key) (result int, err error)
func CompareString(key1 Key, key2 Key) (result int, err error)
func CompareByteSlice(key1 Key, key2 Key) (result int, err error)
func CompareTime(key1 Key, key2 Key) (result int, err error)

type SortedMap interface {
	BisectLeft(key Key) (index int, found bool, err error)  // Returns index of matching key:value pair or, if no match, index is to key:value just before where this key would go
	BisectRight(key Key) (index int, found bool, err error) // Returns index of matching key:value pair or, if no match, index is to key:value just after where this key would go
	DeleteByIndex(index int) (ok bool, err error)
	DeleteByKey(key Key) (ok bool, err error)
	Dump() (err error)
	GetByIndex(index int) (key Key, value Value, ok bool, err error)
	GetByKey(key Key) (value Value, ok bool, err error)
	Len() (numberOfItems int, err error)
	PatchByIndex(index int, value Value) (ok bool, err error)
	PatchByKey(key Key, value Value) (ok bool, err error)
	Put(key Key, value Value) (ok bool, err error)
	Validate() (err error)
}

type DumpCallbacks interface {
	DumpKey(key Key) (keyAsString string, err error)
	DumpValue(value Value) (valueAsString string, err error)
}

type LLRBTree interface {
	SortedMap
	Reset()
}

type LLRBTreeCallbacks interface {
	DumpCallbacks
}

func NewLLRBTree(compare Compare, callbacks LLRBTreeCallbacks) (tree LLRBTree)

var OnDiskByteOrder = cstruct.LittleEndian

type LayoutReport map[uint64]uint64

type BPlusTree interface {
	SortedMap
	FetchLocation() (rootObjectNumber uint64, rootObjectOffset uint64, rootObjectLength uint64)
	FetchLayoutReport() (layoutReport LayoutReport, err error)
	Flush(andPurge bool) (rootObjectNumber uint64, rootObjectOffset uint64, rootObjectLength uint64, err error)
	Purge(full bool) (err error)
	Touch() (err error)
	TouchItem(thisItemIndexToTouch uint64) (nextItemIndexToTouch uint64, err error)
	Prune() (err error)
	Discard() (err error)
}

type BPlusTreeCallbacks interface {
	DumpCallbacks
	GetNode(objectNumber uint64, objectOffset uint64, objectLength uint64) (nodeByteSlice []byte, err error)
	PutNode(nodeByteSlice []byte) (objectNumber uint64, objectOffset uint64, err error)
	DiscardNode(objectNumber uint64, objectOffset uint64, objectLength uint64) (err error)
	PackKey(key Key) (packedKey []byte, err error)
	UnpackKey(payloadData []byte) (key Key, bytesConsumed uint64, err error)
	PackValue(value Value) (packedValue []byte, err error)
	UnpackValue(payloadData []byte) (value Value, bytesConsumed uint64, err error)
}

type BPlusTreeCacheStats struct {
	EvictLowLimit  uint64
	EvictHighLimit uint64
	CleanLRUItems  uint64
	DirtyLRUItems  uint64
	CacheHits      uint64
	CacheMisses    uint64
}

type BPlusTreeCache interface {
	Stats() (bPlusTreeCacheStats *BPlusTreeCacheStats)
	UpdateLimits(evictLowLimit uint64, evictHighLimit uint64)
}

func NewBPlusTreeCache(evictLowLimit uint64, evictHighLimit uint64) (bPlusTreeCache BPlusTreeCache)

func NewBPlusTree(maxKeysPerNode uint64, compare Compare, callbacks BPlusTreeCallbacks, bPlusTreeCache BPlusTreeCache) (tree BPlusTree)

func OldBPlusTree(rootObjectNumber uint64, rootObjectOffset uint64, rootObjectLength uint64, compare Compare, callbacks BPlusTreeCallbacks, bPlusTreeCache BPlusTreeCache) (tree BPlusTree, err error)

Contributors

License

See the included LICENSE file

Documentation

Overview

Package sortedmap provides sorted maps implemented as either a Left-Leaning Red-Black Tree (in memory) or a B+Tree (pageable)

Index

Constants

View Source 
const (
	RED   = true
	BLACK = false
)

Variables

View Source 
var OnDiskByteOrder = cstruct.LittleEndian

OnDiskByteOrder specifies the endian-ness expected to be used to persist B+Tree data structures

Functions

func CompareByteSlice 

func CompareByteSlice(key1 Key, key2 Key) (result int, err error)

func CompareInt 

func CompareInt(key1 Key, key2 Key) (result int, err error)

func CompareString 

func CompareString(key1 Key, key2 Key) (result int, err error)

func CompareTime 

func CompareTime(key1 Key, key2 Key) (result int, err error)

func CompareUint16 

func CompareUint16(key1 Key, key2 Key) (result int, err error)

func CompareUint32 

func CompareUint32(key1 Key, key2 Key) (result int, err error)

func CompareUint64 

func CompareUint64(key1 Key, key2 Key) (result int, err error)

Types

type BPlusTree 

type BPlusTree interface {
	SortedMap
	FetchLocation() (rootObjectNumber uint64, rootObjectOffset uint64, rootObjectLength uint64)
	FetchLayoutReport() (layoutReport LayoutReport, err error)
	Flush(andPurge bool) (rootObjectNumber uint64, rootObjectOffset uint64, rootObjectLength uint64, err error)
	Purge(full bool) (err error)
	Touch() (err error)
	TouchItem(thisItemIndexToTouch uint64) (nextItemIndexToTouch uint64, err error)
	Prune() (err error)
	Discard() (err error)
}

BPlusTree interface declares the available methods available for a B+Tree

func NewBPlusTree 

func NewBPlusTree(maxKeysPerNode uint64, compare Compare, callbacks BPlusTreeCallbacks, bPlusTreeCache BPlusTreeCache) (tree BPlusTree)

NewBPlusTree is used to construct an in-memory B+Tree supporting the Tree interface

The supplied value of maxKeysPerNode, being precisely twice the computed value of (uint64) minKeysPerNode, must be even. In addition, minKeysPerNode must be computed to be greater than one to ensure that during node merge operations, there is always at least one sibling node with which to merge. Hence, maxKeysPerNode must also be at least four.

Note that if the B+Tree will reside only in memory, callback argument may be nil. That said, there is no advantage to using a B+Tree for an in-memory collection over the llrb-provided collection implementing the same APIs.

func OldBPlusTree 

func OldBPlusTree(rootObjectNumber uint64, rootObjectOffset uint64, rootObjectLength uint64, compare Compare, callbacks BPlusTreeCallbacks, bPlusTreeCache BPlusTreeCache) (tree BPlusTree, err error)

OldBPlusTree is used to re-construct a B+Tree previously persisted

type BPlusTreeCache 

type BPlusTreeCache interface {
	Stats() (bPlusTreeCacheStats *BPlusTreeCacheStats)
	UpdateLimits(evictLowLimit uint64, evictHighLimit uint64)
}

func NewBPlusTreeCache 

func NewBPlusTreeCache(evictLowLimit uint64, evictHighLimit uint64) (bPlusTreeCache BPlusTreeCache)

type BPlusTreeCacheStats 

type BPlusTreeCacheStats struct {
	EvictLowLimit  uint64
	EvictHighLimit uint64
	CleanLRUItems  uint64
	DirtyLRUItems  uint64
	CacheHits      uint64
	CacheMisses    uint64
}

type BPlusTreeCallbacks 

type BPlusTreeCallbacks interface {
	DumpCallbacks
	GetNode(objectNumber uint64, objectOffset uint64, objectLength uint64) (nodeByteSlice []byte, err error)
	PutNode(nodeByteSlice []byte) (objectNumber uint64, objectOffset uint64, err error)
	DiscardNode(objectNumber uint64, objectOffset uint64, objectLength uint64) (err error)
	PackKey(key Key) (packedKey []byte, err error)
	UnpackKey(payloadData []byte) (key Key, bytesConsumed uint64, err error)
	PackValue(value Value) (packedValue []byte, err error)
	UnpackValue(payloadData []byte) (value Value, bytesConsumed uint64, err error)
}

BPlusTreeCallbacks specifies the interface to a set of callbacks provided by the client

type Compare 

type Compare func(key1 Key, key2 Key) (result int, err error) // returns <0 if key1 < key2, 0 if key1 == key2, >0 if key1 > key2

type DumpCallbacks 

type DumpCallbacks interface {
	DumpKey(key Key) (keyAsString string, err error)
	DumpValue(value Value) (valueAsString string, err error)
}

DumpCallbacks specifies the interface to a set of callbacks provided by the client

type Key 

type Key interface{}

type LLRBTree 

type LLRBTree interface {
	SortedMap
	Reset()
}

func NewLLRBTree 

func NewLLRBTree(compare Compare, callbacks LLRBTreeCallbacks) (tree LLRBTree)

type LLRBTreeCallbacks 

type LLRBTreeCallbacks interface {
	DumpCallbacks
}

LLRBTreeCallbacks specifies the interface to a set of callbacks provided by the client

type LayoutReport 

type LayoutReport map[uint64]uint64

LayoutReport is a map where key is an objectNumber and value is objectBytes used in that objectNumber

type SortedMap 

type SortedMap interface {
	BisectLeft(key Key) (index int, found bool, err error)  // Returns index of matching key:value pair or, if no match, index is to key:value just before where this key would go
	BisectRight(key Key) (index int, found bool, err error) // Returns index of matching key:value pair or, if no match, index is to key:value just after where this key would go
	DeleteByIndex(index int) (ok bool, err error)
	DeleteByKey(key Key) (ok bool, err error)
	Dump() (err error)
	GetByIndex(index int) (key Key, value Value, ok bool, err error)
	GetByKey(key Key) (value Value, ok bool, err error)
	Len() (numberOfItems int, err error)
	PatchByIndex(index int, value Value) (ok bool, err error)
	PatchByKey(key Key, value Value) (ok bool, err error)
	Put(key Key, value Value) (ok bool, err error)
	Validate() (err error)
}

type Value 

type Value interface{}

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.