radix

package
v0.0.0-...-e1dc7cb Latest Latest
Warning

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

 Go to latest Published: Feb 7, 2013 License: BSD-2-Clause-Views Imports: 12 Imported by: 0

README

radix

A quite complex tree consisting of a merkle tree inside a radix tree, where each node can contain a completely separate tree as value.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Stitch 

func Stitch(b []Nibble) (result []byte)

Stitch will implode a nibble slice into a byte slice.

Types

type HashTree 

type HashTree interface {
	Hash() []byte

	Configuration() (conf map[string]string, timestamp int64)
	Configure(conf map[string]string, timestamp int64)

	Finger(key []Nibble) *Print
	GetTimestamp(key []Nibble) (byteValue []byte, timestamp int64, present bool)
	PutTimestamp(key []Nibble, byteValue []byte, present bool, expected, timestamp int64) bool
	DelTimestamp(key []Nibble, expected int64) bool

	SubConfiguration(key []byte) (conf map[string]string, timestamp int64)
	SubConfigure(key []byte, conf map[string]string, timestamp int64)

	SubFinger(key, subKey []Nibble) (result *Print)
	SubGetTimestamp(key, subKey []Nibble) (byteValue []byte, timestamp int64, present bool)
	SubPutTimestamp(key, subKey []Nibble, byteValue []byte, present bool, subExpected, subTimestamp int64) bool
	SubDelTimestamp(key, subKey []Nibble, subExpected int64) bool
	SubClearTimestamp(key []Nibble, expected, timestamp int64) (deleted int)
	SubKillTimestamp(key []Nibble, expected int64) (deleted int)
}

HashTree is something that can be synchronized using Sync.

type NaiveTimer 

type NaiveTimer struct{}

NaiveTimer is a Timer that just provides the current system time.

func (NaiveTimer) ContinuousTime 

func (self NaiveTimer) ContinuousTime() int64

type Nibble 

type Nibble byte

To limit the number of children of each Node in the Tree, we explode any byte slice keys into nibble slices. But to avoid hairy bit operations we let each nibble live inside a complete byte, and only use least significant half of it. To let the compiler help us keep track of this all byte slices that are supposed to be exploded are Nibble slices.

func Rip 

func Rip(b []byte) (result []Nibble)

Rip will explode a byte slice into a nibble slice.

type Print 

type Print struct {
	Exists            bool
	Key               []Nibble
	Empty             bool
	Timestamp         int64
	SubTree           bool
	SubPrints         []SubPrint
	ByteHash          []byte
	TreeHash          []byte
	TreeDataTimestamp int64
	TreeSize          int
}

Prints are used to record hashes for Nodes.

type SubPrint 

type SubPrint struct {
	Key    []Nibble
	Sum    []byte
	Exists bool
}

SubPrints are used to record hashes for child trees.

type Sync 

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

Sync synchronizes HashTrees using their fingerprints and mutators.

func NewSync 

func NewSync(source, destination HashTree) *Sync

func (*Sync) DelCount 

func (self *Sync) DelCount() int

DelCount returns the number of entries this Sync has deleted from the source Tree.

func (*Sync) Destroy 

func (self *Sync) Destroy() *Sync

Destroy defines that this Sync will delete whatever it copies from the source Tree.

func (*Sync) From 

func (self *Sync) From(from []byte) *Sync

From defines from what key, inclusive, that this Sync will synchronize.

func (*Sync) PutCount 

func (self *Sync) PutCount() int

PutCount returns the number of entries this Sync has inserted into the destination Tree.

func (*Sync) Run 

func (self *Sync) Run() *Sync

Run will start this Sync and return when it is finished.

func (*Sync) To 

func (self *Sync) To(to []byte) *Sync

To defines from what key, exclusive, that this Sync will synchronize.

type Timer 

type Timer interface {
	ContinuousTime() int64
}

Since the Trees remove tombstones lazily, and after a timeout, we need something to provide times.

type Tree 

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

Tree is a merkle tree inside a radix tree, where each node can contain a separate sub tree.

Any method called Sub* does the same to a sub tree as the same method without Sub does to the main tree.

A Tree can be mirrored, which means that it contains another Tree where the keys are the values of the master Tree, and the values are the keys of the master Tree.

A Tree is configured to be mirrored or not by using AddConfiguration or SubAddConfiguration (for a sub tree) setting 'mirrored' to 'yes'.

func NewTree 

func NewTree() *Tree

func NewTreeTimer 

func NewTreeTimer(timer Timer) (result *Tree)

func (*Tree) AddConfiguration 

func (self *Tree) AddConfiguration(ts int64, key, value string) bool

AddConfiguration will set the key and value in the configuration of this tree, and set the provided timestamp as the new configuration timestamp.

func (*Tree) Clear 

func (self *Tree) Clear(timestamp int64)

Clear will remove all content of this Tree (including tombstones and sub trees) and any mirror Tree and replace the all with one giant tombstone, and clear any persistence.Logger assigned to this Tree.

func (*Tree) Configuration 

func (self *Tree) Configuration() (map[string]string, int64)

Configuration returns the current configuration and its timestamp.

func (*Tree) Configure 

func (self *Tree) Configure(conf map[string]string, ts int64)

Configure will set a new configuration and timestamp to this tree. If the configuration has mirrored=yes this tree will start mirroring all its keys and values in a mirror Tree.

func (*Tree) DataTimestamp 

func (self *Tree) DataTimestamp() int64

func (*Tree) Del 

func (self *Tree) Del(key []byte) (oldBytes []byte, existed bool)

Del will remove key from this Tree without keeping a tombstone.

func (*Tree) DelTimestamp 

func (self *Tree) DelTimestamp(key []Nibble, expected int64) (result bool)

func (*Tree) Describe 

func (self *Tree) Describe() string

Describe will return a complete and humanly readable (albeit slightly convoluted) description of this Tree.

func (*Tree) Each 

func (self *Tree) Each(f TreeIterator)

Each will iterate over the entire tree using f.

func (*Tree) EachBetween 

func (self *Tree) EachBetween(min, max []byte, mininc, maxinc bool, f TreeIterator)

EachBetween will iterate between min and max using f.

func (*Tree) EachBetweenIndex 

func (self *Tree) EachBetweenIndex(min, max *int, f TreeIndexIterator)

EachBetweenIndex will iterate between the min'th and the max'th entry using f.

func (*Tree) FakeDel 

func (self *Tree) FakeDel(key []byte, timestamp int64) (oldBytes []byte, oldTree *Tree, existed bool)

FakeDel will insert a tombstone at key with timestamp in this Tree.

func (*Tree) Finger 

func (self *Tree) Finger(key []Nibble) *Print

func (*Tree) First 

func (self *Tree) First() (key, byteValue []byte, timestamp int64, existed bool)

First returns the first key, value and timestamp in this Tree.

func (*Tree) Get 

func (self *Tree) Get(key []byte) (bValue []byte, timestamp int64, existed bool)

Get will return the value and timestamp at key.

func (*Tree) GetTimestamp 

func (self *Tree) GetTimestamp(key []Nibble) (bValue []byte, timestamp int64, present bool)

func (*Tree) Hash 

func (self *Tree) Hash() []byte

Hash returns the merkle hash of this Tree.

func (*Tree) Index 

func (self *Tree) Index(n int) (key []byte, byteValue []byte, timestamp int64, existed bool)

Index returns the key, value and timestamp at index in this Tree.

func (*Tree) IndexOf 

func (self *Tree) IndexOf(key []byte) (index int, existed bool)

IndexOf will return the index of (or the index it would have if it existed) key.

func (*Tree) Last 

func (self *Tree) Last() (key, byteValue []byte, timestamp int64, existed bool)

Last returns the last key, value and timestamp in this Tree.

func (*Tree) Load 

func (self *Tree) Load() float64

func (*Tree) Log 

func (self *Tree) Log(dir string) *Tree

Log will make this Tree start logging using a new persistence.Logger.

func (*Tree) MirrorEachBetween 

func (self *Tree) MirrorEachBetween(min, max []byte, mininc, maxinc bool, f TreeIterator)

MirrorEachBetween will iterate between min and max in the mirror Tree using f.

func (*Tree) MirrorEachBetweenIndex 

func (self *Tree) MirrorEachBetweenIndex(min, max *int, f TreeIndexIterator)

MirrorEachBetweenIndex will iterate between the min'th and the max'th entry in the mirror Tree using f.

func (*Tree) MirrorFirst 

func (self *Tree) MirrorFirst() (key, byteValue []byte, timestamp int64, existed bool)

MirrorFirst will return the first key, value and timestamp of the mirror Tree.

func (*Tree) MirrorIndex 

func (self *Tree) MirrorIndex(n int) (key, byteValue []byte, timestamp int64, existed bool)

MirrorIndex returns the key, value and timestamp at index in the mirror Tree.

func (*Tree) MirrorIndexOf 

func (self *Tree) MirrorIndexOf(key []byte) (index int, existed bool)

MirrorIndexOf will return the index of (or the index it would have if it existed) key in the mirror Tree.

func (*Tree) MirrorLast 

func (self *Tree) MirrorLast() (key, byteValue []byte, timestamp int64, existed bool)

MirrorLast will return the last key, value and timestamp of the mirror Tree.

func (*Tree) MirrorNext 

func (self *Tree) MirrorNext(key []byte) (nextKey, nextValue []byte, nextTimestamp int64, existed bool)

MirrorNext returns the next key, value and timestamp after key in the mirror Tree.

func (*Tree) MirrorNextIndex 

func (self *Tree) MirrorNextIndex(index int) (key, value []byte, timestamp int64, ind int, existed bool)

MirrorNextIndex will return the next key, value, timestamp and index after index in the mirror Tree.

func (*Tree) MirrorPrev 

func (self *Tree) MirrorPrev(key []byte) (prevKey, prevValue []byte, prevTimestamp int64, existed bool)

MirrorPrev returns the previous key, value and timestamp before key in the mirror Tree.

func (*Tree) MirrorPrevIndex 

func (self *Tree) MirrorPrevIndex(index int) (key, value []byte, timestamp int64, ind int, existed bool)

MirrorPrevIndex will return the previous key, value, timestamp and index before index in the mirror Tree.

func (*Tree) MirrorReverseEachBetween 

func (self *Tree) MirrorReverseEachBetween(min, max []byte, mininc, maxinc bool, f TreeIterator)

MirrorReverseEachBetween will iterate between min and max in the mirror Tree, in reverse order, using f.

func (*Tree) MirrorReverseEachBetweenIndex 

func (self *Tree) MirrorReverseEachBetweenIndex(min, max *int, f TreeIndexIterator)

MirrorReverseEachBetweenIndex will iterate between the min'th and the max'th entry of the mirror Tree, in reverse order, using f.

func (*Tree) MirrorReverseIndex 

func (self *Tree) MirrorReverseIndex(n int) (key, byteValue []byte, timestamp int64, existed bool)

MirrorReverseIndex returns the key, value and timestamp at index from the end in the mirror Tree.

func (*Tree) MirrorReverseIndexOf 

func (self *Tree) MirrorReverseIndexOf(key []byte) (index int, existed bool)

MirrorReverseIndexOf will return the index from the end (or the index it would have if it existed) key in the mirror Tree.

func (*Tree) MirrorSizeBetween 

func (self *Tree) MirrorSizeBetween(min, max []byte, mininc, maxinc bool) (i int)

MirrorSizeBetween returns the virtual, as in 'not including tombstones and sub trees', size of the mirror Tree between min and max.

func (*Tree) Next 

func (self *Tree) Next(key []byte) (nextKey, nextValue []byte, nextTimestamp int64, existed bool)

Next will return the next key, value and timestamp after key in this Tree.

func (*Tree) NextIndex 

func (self *Tree) NextIndex(index int) (key, value []byte, timestamp int64, ind int, existed bool)

NextIndex will return the next key, value, timestamp and index after index in this Tree.

func (*Tree) NextMarker 

func (self *Tree) NextMarker(key []byte) (nextKey []byte, existed bool)

NextMarker returns the next key of tombstone or real value after key.

func (*Tree) NextMarkerIndex 

func (self *Tree) NextMarkerIndex(index int) (key []byte, existed bool)

NextMarkerIndex will return the next key of tombstone or real value after the given index in this Tree.

func (*Tree) Prev 

func (self *Tree) Prev(key []byte) (prevKey, prevValue []byte, prevTimestamp int64, existed bool)

Prev will return the previous key, value and timestamp before key in this Tree.

func (*Tree) PrevIndex 

func (self *Tree) PrevIndex(index int) (key, value []byte, timestamp int64, ind int, existed bool)

PrevIndex will return the previous key, value, timestamp and index before index in this Tree.

func (*Tree) PrevMarker 

func (self *Tree) PrevMarker(key []byte) (prevKey []byte, existed bool)

PrevMarker returns the previous key of tombstone or real value before key.

func (*Tree) PrevMarkerIndex 

func (self *Tree) PrevMarkerIndex(index int) (key []byte, existed bool)

PrevMarkerIndex will return the previous key of tombstone or real value before the given index in this Tree.

func (*Tree) Put 

func (self *Tree) Put(key []byte, bValue []byte, timestamp int64) (oldBytes []byte, existed bool)

Put will put key and value with timestamp in this Tree.

func (*Tree) PutTimestamp 

func (self *Tree) PutTimestamp(key []Nibble, bValue []byte, present bool, expected, timestamp int64) (result bool)

func (*Tree) RealSize 

func (self *Tree) RealSize() int

RealSize returns the real, as in 'including tombstones and sub trees', size of this Tree.

func (*Tree) RealSizeBetween 

func (self *Tree) RealSizeBetween(min, max []byte, mininc, maxinc bool) int

RealSizeBetween returns the real, as in 'including tombstones and sub trees', size of this Tree between min anx max.

func (*Tree) Restore 

func (self *Tree) Restore() *Tree

Restore will temporarily stop the Logger of this Tree, make it replay all operations to allow us to restore the state logged in that directory, and then start recording again.

func (*Tree) ReverseEach 

func (self *Tree) ReverseEach(f TreeIterator)

ReverseEach will iterate over the entire tree in reverse order using f.

func (*Tree) ReverseEachBetween 

func (self *Tree) ReverseEachBetween(min, max []byte, mininc, maxinc bool, f TreeIterator)

ReverseEachBetween will iterate between min and max in reverse order using f.

func (*Tree) ReverseEachBetweenIndex 

func (self *Tree) ReverseEachBetweenIndex(min, max *int, f TreeIndexIterator)

ReverseEachBetweenIndex will iterate between the min'th and the max'th entry in reverse order using f.

func (*Tree) ReverseIndex 

func (self *Tree) ReverseIndex(n int) (key []byte, byteValue []byte, timestamp int64, existed bool)

ReverseIndex returns the key, value and timestamp at index from the end in this Tree.

func (*Tree) ReverseIndexOf 

func (self *Tree) ReverseIndexOf(key []byte) (index int, existed bool)

MirrorReverseIndexOf will return the index from the end (or the index it would have if it existed) key.

func (*Tree) Size 

func (self *Tree) Size() int

Size returns the virtual, as in 'not including tombstones and sub trees', size of this Tree.

func (*Tree) SizeBetween 

func (self *Tree) SizeBetween(min, max []byte, mininc, maxinc bool) int

SizeBetween returns the virtual, as in 'not including tombstones and sub trees', size of this Tree between min and max.

func (*Tree) String 

func (self *Tree) String() string

String returns a humanly readable string representation of this Tree.

func (*Tree) SubAddConfiguration 

func (self *Tree) SubAddConfiguration(treeKey []byte, ts int64, key, value string) bool

func (*Tree) SubClear 

func (self *Tree) SubClear(key []byte, timestamp int64) (deleted int)

func (*Tree) SubClearTimestamp 

func (self *Tree) SubClearTimestamp(key []Nibble, expected, timestamp int64) (deleted int)

func (*Tree) SubConfiguration 

func (self *Tree) SubConfiguration(key []byte) (conf map[string]string, timestamp int64)

func (*Tree) SubConfigure 

func (self *Tree) SubConfigure(key []byte, conf map[string]string, timestamp int64)

func (*Tree) SubDel 

func (self *Tree) SubDel(key, subKey []byte) (oldBytes []byte, existed bool)

func (*Tree) SubDelTimestamp 

func (self *Tree) SubDelTimestamp(key, subKey []Nibble, subExpected int64) (result bool)

func (*Tree) SubEachBetween 

func (self *Tree) SubEachBetween(key, min, max []byte, mininc, maxinc bool, f TreeIterator)

func (*Tree) SubEachBetweenIndex 

func (self *Tree) SubEachBetweenIndex(key []byte, min, max *int, f TreeIndexIterator)

func (*Tree) SubFakeDel 

func (self *Tree) SubFakeDel(key, subKey []byte, timestamp int64) (oldBytes []byte, existed bool)

func (*Tree) SubFinger 

func (self *Tree) SubFinger(key, subKey []Nibble) (result *Print)

func (*Tree) SubFirst 

func (self *Tree) SubFirst(key []byte) (firstKey []byte, firstBytes []byte, firstTimestamp int64, existed bool)

func (*Tree) SubGet 

func (self *Tree) SubGet(key, subKey []byte) (byteValue []byte, timestamp int64, existed bool)

func (*Tree) SubGetTimestamp 

func (self *Tree) SubGetTimestamp(key, subKey []Nibble) (byteValue []byte, timestamp int64, present bool)

func (*Tree) SubIndexOf 

func (self *Tree) SubIndexOf(key, subKey []byte) (index int, existed bool)

func (*Tree) SubKill 

func (self *Tree) SubKill(key []byte) (deleted int)

func (*Tree) SubKillTimestamp 

func (self *Tree) SubKillTimestamp(key []Nibble, expected int64) (deleted int)

func (*Tree) SubLast 

func (self *Tree) SubLast(key []byte) (lastKey []byte, lastBytes []byte, lastTimestamp int64, existed bool)

func (*Tree) SubMirrorEachBetween 

func (self *Tree) SubMirrorEachBetween(key, min, max []byte, mininc, maxinc bool, f TreeIterator)

func (*Tree) SubMirrorEachBetweenIndex 

func (self *Tree) SubMirrorEachBetweenIndex(key []byte, min, max *int, f TreeIndexIterator)

func (*Tree) SubMirrorFirst 

func (self *Tree) SubMirrorFirst(key []byte) (firstKey []byte, firstBytes []byte, firstTimestamp int64, existed bool)

func (*Tree) SubMirrorIndexOf 

func (self *Tree) SubMirrorIndexOf(key, subKey []byte) (index int, existed bool)

func (*Tree) SubMirrorLast 

func (self *Tree) SubMirrorLast(key []byte) (lastKey []byte, lastBytes []byte, lastTimestamp int64, existed bool)

func (*Tree) SubMirrorNext 

func (self *Tree) SubMirrorNext(key, subKey []byte) (nextKey, nextValue []byte, nextTimestamp int64, existed bool)

func (*Tree) SubMirrorNextIndex 

func (self *Tree) SubMirrorNextIndex(key []byte, index int) (foundKey, foundValue []byte, foundTimestamp int64, foundIndex int, existed bool)

func (*Tree) SubMirrorPrev 

func (self *Tree) SubMirrorPrev(key, subKey []byte) (prevKey, prevValue []byte, prevTimestamp int64, existed bool)

func (*Tree) SubMirrorPrevIndex 

func (self *Tree) SubMirrorPrevIndex(key []byte, index int) (foundKey, foundValue []byte, foundTimestamp int64, foundIndex int, existed bool)

func (*Tree) SubMirrorReverseEachBetween 

func (self *Tree) SubMirrorReverseEachBetween(key, min, max []byte, mininc, maxinc bool, f TreeIterator)

func (*Tree) SubMirrorReverseEachBetweenIndex 

func (self *Tree) SubMirrorReverseEachBetweenIndex(key []byte, min, max *int, f TreeIndexIterator)

func (*Tree) SubMirrorReverseIndexOf 

func (self *Tree) SubMirrorReverseIndexOf(key, subKey []byte) (index int, existed bool)

func (*Tree) SubMirrorSizeBetween 

func (self *Tree) SubMirrorSizeBetween(key, min, max []byte, mininc, maxinc bool) (result int)

func (*Tree) SubNext 

func (self *Tree) SubNext(key, subKey []byte) (nextKey, nextValue []byte, nextTimestamp int64, existed bool)

func (*Tree) SubNextIndex 

func (self *Tree) SubNextIndex(key []byte, index int) (foundKey, foundValue []byte, foundTimestamp int64, foundIndex int, existed bool)

func (*Tree) SubPrev 

func (self *Tree) SubPrev(key, subKey []byte) (prevKey, prevValue []byte, prevTimestamp int64, existed bool)

func (*Tree) SubPrevIndex 

func (self *Tree) SubPrevIndex(key []byte, index int) (foundKey, foundValue []byte, foundTimestamp int64, foundIndex int, existed bool)

func (*Tree) SubPut 

func (self *Tree) SubPut(key, subKey []byte, byteValue []byte, timestamp int64) (oldBytes []byte, existed bool)

func (*Tree) SubPutTimestamp 

func (self *Tree) SubPutTimestamp(key, subKey []Nibble, bValue []byte, present bool, subExpected, subTimestamp int64) (result bool)

func (*Tree) SubReverseEachBetween 

func (self *Tree) SubReverseEachBetween(key, min, max []byte, mininc, maxinc bool, f TreeIterator)

func (*Tree) SubReverseEachBetweenIndex 

func (self *Tree) SubReverseEachBetweenIndex(key []byte, min, max *int, f TreeIndexIterator)

func (*Tree) SubReverseIndexOf 

func (self *Tree) SubReverseIndexOf(key, subKey []byte) (index int, existed bool)

func (*Tree) SubSize 

func (self *Tree) SubSize(key []byte) (result int)

func (*Tree) SubSizeBetween 

func (self *Tree) SubSizeBetween(key, min, max []byte, mininc, maxinc bool) (result int)

func (*Tree) ToMap 

func (self *Tree) ToMap() (result map[string][]byte)

ToMap will return a dubious map representation of this Tree, where each byte slice key is converted to a string.

type TreeIndexIterator 

type TreeIndexIterator func(key, value []byte, timestamp int64, index int) (cont bool)

TreeIndexIterators iterate over trees, and see the key, value, timestamp and index of what they iterate over. If they return false, the iteration will end.

type TreeIterator 

type TreeIterator func(key, value []byte, timestamp int64) (cont bool)

TreeIterators iterate over trees, and see the key, value and timestamp of what they iterate over. If they return false, the iteration will end.

Source Files

View all Source files

Directories

Path Synopsis

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.