btcd: github.com/btcsuite/btcd/database/internal/treap Index | Files

package treap

import "github.com/btcsuite/btcd/database/internal/treap"

Package treap implements a treap data structure that is used to hold ordered key/value pairs using a combination of binary search tree and heap semantics. It is a self-organizing and randomized data structure that doesn't require complex operations to to maintain balance. Search, insert, and delete operations are all O(log n). Both mutable and immutable variants are provided.

The mutable variant is typically faster since it is able to simply update the treap when modifications are made. However, a mutable treap is not safe for concurrent access without careful use of locking by the caller and care must be taken when iterating since it can change out from under the iterator.

The immutable variant works by creating a new version of the treap for all mutations by replacing modified nodes with new nodes that have updated values while sharing all unmodified nodes with the previous version. This is extremely useful in concurrent applications since the caller only has to atomically replace the treap pointer with the newly returned version after performing any mutations. All readers can simply use their existing pointer as a snapshot since the treap it points to is immutable. This effectively provides O(1) snapshot capability with efficient memory usage characteristics since the old nodes only remain allocated until there are no longer any references to them.

Index

Package Files

common.go doc.go immutable.go mutable.go treapiter.go

type Immutable Uses

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

Immutable represents a treap data structure which is used to hold ordered key/value pairs using a combination of binary search tree and heap semantics. It is a self-organizing and randomized data structure that doesn't require complex operations to maintain balance. Search, insert, and delete operations are all O(log n). In addition, it provides O(1) snapshots for multi-version concurrency control (MVCC).

All operations which result in modifying the treap return a new version of the treap with only the modified nodes updated. All unmodified nodes are shared with the previous version. This is extremely useful in concurrent applications since the caller only has to atomically replace the treap pointer with the newly returned version after performing any mutations. All readers can simply use their existing pointer as a snapshot since the treap it points to is immutable. This effectively provides O(1) snapshot capability with efficient memory usage characteristics since the old nodes only remain allocated until there are no longer any references to them.

func NewImmutable Uses

func NewImmutable() *Immutable

NewImmutable returns a new empty immutable treap ready for use. See the documentation for the Immutable structure for more details.

func (*Immutable) Delete Uses

func (t *Immutable) Delete(key []byte) *Immutable

Delete removes the passed key from the treap and returns the resulting treap if it exists. The original immutable treap is returned if the key does not exist.

func (*Immutable) ForEach Uses

func (t *Immutable) ForEach(fn func(k, v []byte) bool)

ForEach invokes the passed function with every key/value pair in the treap in ascending order.

func (*Immutable) Get Uses

func (t *Immutable) Get(key []byte) []byte

Get returns the value for the passed key. The function will return nil when the key does not exist.

func (*Immutable) Has Uses

func (t *Immutable) Has(key []byte) bool

Has returns whether or not the passed key exists.

func (*Immutable) Iterator Uses

func (t *Immutable) Iterator(startKey, limitKey []byte) *Iterator

Iterator returns a new iterator for the immutable treap. The newly returned iterator is not pointing to a valid item until a call to one of the methods to position it is made.

The start key and limit key parameters cause the iterator to be limited to a range of keys. The start key is inclusive and the limit key is exclusive. Either or both can be nil if the functionality is not desired.

func (*Immutable) Len Uses

func (t *Immutable) Len() int

Len returns the number of items stored in the treap.

func (*Immutable) Put Uses

func (t *Immutable) Put(key, value []byte) *Immutable

Put inserts the passed key/value pair.

func (*Immutable) Size Uses

func (t *Immutable) Size() uint64

Size returns a best estimate of the total number of bytes the treap is consuming including all of the fields used to represent the nodes as well as the size of the keys and values. Shared values are not detected, so the returned size assumes each value is pointing to different memory.

type Iterator Uses

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

Iterator represents an iterator for forwards and backwards iteration over the contents of a treap (mutable or immutable).

func (*Iterator) First Uses

func (iter *Iterator) First() bool

First moves the iterator to the first key/value pair. When there is only a single key/value pair both First and Last will point to the same pair. Returns false if there are no key/value pairs.

func (*Iterator) ForceReseek Uses

func (iter *Iterator) ForceReseek()

ForceReseek notifies the iterator that the underlying mutable treap has been updated, so the next call to Prev or Next needs to reseek in order to allow the iterator to continue working properly.

NOTE: Calling this function when the iterator is associated with an immutable treap has no effect as you would expect.

func (*Iterator) Key Uses

func (iter *Iterator) Key() []byte

Key returns the key of the current key/value pair or nil when the iterator is exhausted. The caller should not modify the contents of the returned slice.

func (*Iterator) Last Uses

func (iter *Iterator) Last() bool

Last moves the iterator to the last key/value pair. When there is only a single key/value pair both First and Last will point to the same pair. Returns false if there are no key/value pairs.

func (*Iterator) Next Uses

func (iter *Iterator) Next() bool

Next moves the iterator to the next key/value pair and returns false when the iterator is exhausted. When invoked on a newly created iterator it will position the iterator at the first item.

func (*Iterator) Prev Uses

func (iter *Iterator) Prev() bool

Prev moves the iterator to the previous key/value pair and returns false when the iterator is exhausted. When invoked on a newly created iterator it will position the iterator at the last item.

func (*Iterator) Seek Uses

func (iter *Iterator) Seek(key []byte) bool

Seek moves the iterator to the first key/value pair with a key that is greater than or equal to the given key and returns true if successful.

func (*Iterator) Valid Uses

func (iter *Iterator) Valid() bool

Valid indicates whether the iterator is positioned at a valid key/value pair. It will be considered invalid when the iterator is newly created or exhausted.

func (*Iterator) Value Uses

func (iter *Iterator) Value() []byte

Value returns the value of the current key/value pair or nil when the iterator is exhausted. The caller should not modify the contents of the returned slice.

type Mutable Uses

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

Mutable represents a treap data structure which is used to hold ordered key/value pairs using a combination of binary search tree and heap semantics. It is a self-organizing and randomized data structure that doesn't require complex operations to maintain balance. Search, insert, and delete operations are all O(log n).

func NewMutable Uses

func NewMutable() *Mutable

NewMutable returns a new empty mutable treap ready for use. See the documentation for the Mutable structure for more details.

func (*Mutable) Delete Uses

func (t *Mutable) Delete(key []byte)

Delete removes the passed key if it exists.

func (*Mutable) ForEach Uses

func (t *Mutable) ForEach(fn func(k, v []byte) bool)

ForEach invokes the passed function with every key/value pair in the treap in ascending order.

func (*Mutable) Get Uses

func (t *Mutable) Get(key []byte) []byte

Get returns the value for the passed key. The function will return nil when the key does not exist.

func (*Mutable) Has Uses

func (t *Mutable) Has(key []byte) bool

Has returns whether or not the passed key exists.

func (*Mutable) Iterator Uses

func (t *Mutable) Iterator(startKey, limitKey []byte) *Iterator

Iterator returns a new iterator for the mutable treap. The newly returned iterator is not pointing to a valid item until a call to one of the methods to position it is made.

The start key and limit key parameters cause the iterator to be limited to a range of keys. The start key is inclusive and the limit key is exclusive. Either or both can be nil if the functionality is not desired.

WARNING: The ForceSeek method must be called on the returned iterator if the treap is mutated. Failure to do so will cause the iterator to return unexpected keys and/or values.

For example:

iter := t.Iterator(nil, nil)
for iter.Next() {
	if someCondition {
		t.Delete(iter.Key())
		iter.ForceReseek()
	}
}

func (*Mutable) Len Uses

func (t *Mutable) Len() int

Len returns the number of items stored in the treap.

func (*Mutable) Put Uses

func (t *Mutable) Put(key, value []byte)

Put inserts the passed key/value pair.

func (*Mutable) Reset Uses

func (t *Mutable) Reset()

Reset efficiently removes all items in the treap.

func (*Mutable) Size Uses

func (t *Mutable) Size() uint64

Size returns a best estimate of the total number of bytes the treap is consuming including all of the fields used to represent the nodes as well as the size of the keys and values. Shared values are not detected, so the returned size assumes each value is pointing to different memory.

Package treap imports 3 packages (graph) and is imported by 49 packages. Updated 2017-05-27. Refresh now. Tools for package owners.