tree

package
v2.2.0-beta.6 Latest Latest
Warning

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

 Go to latest Published: Sep 5, 2025 License: Apache-2.0 Imports: 25 Imported by: 4

Documentation

Index

Constants

View Source 
const (
	Set = iota
	Remove
)

Variables

View Source 
var ErrNoImport = errors.New("no import in progress")

ErrNoImport is returned when calling methods on a closed importer

View Source 
var ErrorExportDone = errors.New("export done")

Functions

func NewImportNode 

func NewImportNode(key, value []byte, version int64, height int8) *inode.Node

Types

type BatchOperation 

type BatchOperation struct {
	Type  BatchOperationType
	Key   []byte
	Value []byte // nil for remove operations
}

func NewRemoveOperation 

func NewRemoveOperation(key []byte) BatchOperation

func NewSetOperation 

func NewSetOperation(key, value []byte) BatchOperation

type BatchOperationType 

type BatchOperationType int

type Exporter 

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

func (*Exporter) Close 

func (e *Exporter) Close() error

func (*Exporter) Next 

func (e *Exporter) Next() (*inode.SnapshotNode, error)

func (*Exporter) NextRawNode 

func (e *Exporter) NextRawNode() (*inode.Node, error)

Primary used for unit tests

type ImmutableTree 

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

func (*ImmutableTree) Clone 

func (tree *ImmutableTree) Clone() *ImmutableTree

func (*ImmutableTree) Close 

func (tree *ImmutableTree) Close() error

func (*ImmutableTree) Get 

func (tree *ImmutableTree) Get(key []byte) ([]byte, error)

func (*ImmutableTree) GetByIndex 

func (tree *ImmutableTree) GetByIndex(index int64) (key []byte, value []byte, err error)

func (*ImmutableTree) GetProof 

func (tree *ImmutableTree) GetProof(key []byte) (proof *ics23.CommitmentProof, err error)

func (*ImmutableTree) GetWithIndex 

func (tree *ImmutableTree) GetWithIndex(key []byte) (int64, []byte, error)

func (*ImmutableTree) Has 

func (tree *ImmutableTree) Has(key []byte) (bool, error)

func (*ImmutableTree) Hash 

func (tree *ImmutableTree) Hash() []byte

func (*ImmutableTree) Iterator 

func (tree *ImmutableTree) Iterator(start, end []byte, inclusive bool) (itr Iterator, err error)

func (*ImmutableTree) LoadVersion 

func (tree *ImmutableTree) LoadVersion(version int64) (err error)

func (*ImmutableTree) PathToLeaf 

func (tree *ImmutableTree) PathToLeaf(node *inode.Node, key []byte) (PathToLeaf, *inode.Node, error)

If the key does not exist, returns the path to the next leaf left of key (w/ path), except when key is less than the least item, in which case it returns a path to the least item.

func (*ImmutableTree) ReverseIterator 

func (tree *ImmutableTree) ReverseIterator(start, end []byte) (itr Iterator, err error)

func (*ImmutableTree) Version 

func (tree *ImmutableTree) Version() int64

func (*ImmutableTree) VersionExists 

func (tree *ImmutableTree) VersionExists(version int64) (bool, error)

type Importer 

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

Importer imports data into an empty MutableTree. It is created by MutableTree.Import(). Users must call Close() when done.

ExportNodes must be imported in the order returned by Exporter, i.e. depth-first post-order (LRN).

Importer is not concurrency-safe, it is the caller's responsibility to ensure the tree is not modified while performing an import.

func NewImporter 

func NewImporter(tree *Tree, version int64) (*Importer, error)

newImporter creates a new Importer for an empty Tree

version should correspond to the version that was initially exported. It must be greater than or equal to the highest ExportNode version number given.

func (*Importer) Add 

func (i *Importer) Add(node *inode.Node) error

Add adds an ExportNode to the import. ExportNodes must be added in the order returned by Exporter, i.e. depth-first post-order (LRN). Nodes are periodically flushed to the database, but the imported version is not visible until Commit() is called.

func (*Importer) Close 

func (i *Importer) Close()

Close frees all resources. It is safe to call multiple times. Uncommitted nodes may already have been flushed to the database, but will not be visible.

func (*Importer) Commit 

func (i *Importer) Commit() error

Commit finalizes the import by flushing any outstanding nodes to the database, making the version visible, and updating the tree metadata. It can only be called once, and calls Close() internally.

type Iterator 

type Iterator interface {
	// Domain returns the start (inclusive) and end (exclusive) limits of the iterator.
	// CONTRACT: start, end readonly []byte
	Domain() (start []byte, end []byte)

	// Valid returns whether the current iterator is valid. Once invalid, the LeafIterator remains
	// invalid forever.
	Valid() bool

	// Next moves the iterator to the next key in the database, as defined by order of iteration.
	// If Valid returns false, this method will panic.
	Next()

	// Key returns the key at the current position. Panics if the iterator is invalid.
	// CONTRACT: key readonly []byte
	Key() (key []byte)

	// Value returns the value at the current position. Panics if the iterator is invalid.
	// CONTRACT: value readonly []byte
	Value() (value []byte)

	// Error returns the last error encountered by the iterator, if any.
	Error() error

	// Close closes the iterator, releasing any allocated resources.
	Close() error
}

type LeafIterator 

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

func (*LeafIterator) Close 

func (i *LeafIterator) Close() error

func (*LeafIterator) Domain 

func (i *LeafIterator) Domain() (start []byte, end []byte)

func (*LeafIterator) Error 

func (i *LeafIterator) Error() error

func (*LeafIterator) Key 

func (i *LeafIterator) Key() (key []byte)

func (*LeafIterator) Next 

func (i *LeafIterator) Next()

func (*LeafIterator) Valid 

func (i *LeafIterator) Valid() bool

func (*LeafIterator) Value 

func (i *LeafIterator) Value() (value []byte)

type Options 

type Options struct {
	StateStorage  bool
	HeightFilter  int8
	EvictionDepth int8
	MetricsProxy  metrics.Proxy
}

func DefaultOptions 

func DefaultOptions() Options

type PathToLeaf 

type PathToLeaf []ProofInnerNode

PathToLeaf represents an inner path to a leaf node. Note that the nodes are ordered such that the last one is closest to the root of the tree.

func (PathToLeaf) Index 

func (pl PathToLeaf) Index() (idx int64)

returns -1 if invalid.

func (PathToLeaf) String 

func (pl PathToLeaf) String() string

type ProofInnerNode 

type ProofInnerNode struct {
	Height  int8   `json:"height"`
	Size    int64  `json:"size"`
	Version int64  `json:"version"`
	Left    []byte `json:"left"`
	Right   []byte `json:"right"`
}

func (ProofInnerNode) Hash 

func (pin ProofInnerNode) Hash(childHash []byte) ([]byte, error)

func (ProofInnerNode) String 

func (pin ProofInnerNode) String() string

type ProofLeafNode 

type ProofLeafNode struct {
	Key       []byte `json:"key"`
	ValueHash []byte `json:"value"`
	Version   int64  `json:"version"`
}

func (ProofLeafNode) Hash 

func (pln ProofLeafNode) Hash() ([]byte, error)

func (ProofLeafNode) String 

func (pln ProofLeafNode) String() string

type Tree 

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

func NewTree 

func NewTree(db idb.DB, pool *nodepool.NodePool, opts Options) *Tree

func (*Tree) AdvanceVersion 

func (tree *Tree) AdvanceVersion()

NOTE: This func is primary for unit test(no db, pure memory tree)

func (*Tree) BatchSetRemove 

func (tree *Tree) BatchSetRemove(operations []BatchOperation) error

func (*Tree) Close 

func (tree *Tree) Close() error

func (*Tree) Compare 

func (tree *Tree) Compare(other *Tree) error

func (*Tree) DeleteVersionsTo 

func (tree *Tree) DeleteVersionsTo(toVersion int64) error

func (*Tree) DeleteVersionsToSync 

func (tree *Tree) DeleteVersionsToSync(toVersion int64) error

func (*Tree) DetectWrongBranchHashes 

func (tree *Tree) DetectWrongBranchHashes(start, end int64) ([]*WrongVersionKey, error)

func (*Tree) EnsureLeftNode 

func (tree *Tree) EnsureLeftNode(node *inode.Node) *inode.Node

func (*Tree) EnsureRightNode 

func (tree *Tree) EnsureRightNode(node *inode.Node) *inode.Node

func (*Tree) Export 

func (tree *Tree) Export(order constants.TraverseOrderType) *Exporter

func (*Tree) ExportVersion 

func (tree *Tree) ExportVersion(version int64, order constants.TraverseOrderType) (*Exporter, error)

func (*Tree) Get 

func (tree *Tree) Get(key []byte) ([]byte, error)

func (*Tree) GetByIndex 

func (tree *Tree) GetByIndex(index int64) (key []byte, value []byte, err error)

func (*Tree) GetFromRoot 

func (tree *Tree) GetFromRoot(key []byte) ([]byte, error)

func (*Tree) GetImmutable 

func (tree *Tree) GetImmutable(version int64) (*ImmutableTree, error)

func (*Tree) GetProof 

func (tree *Tree) GetProof(version int64, key []byte) (proof *ics23.CommitmentProof, err error)

func (*Tree) GetRecent 

func (tree *Tree) GetRecent(version int64, key []byte) (bool, []byte, error)

func (*Tree) GetWithIndex 

func (tree *Tree) GetWithIndex(key []byte) (int64, []byte, error)

func (*Tree) Has 

func (tree *Tree) Has(key []byte) (bool, error)

func (*Tree) Hash 

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

func (*Tree) Height 

func (tree *Tree) Height() int8

func (*Tree) Import 

func (tree *Tree) Import(version int64) (*Importer, error)

func (*Tree) IterateRecent 

func (tree *Tree) IterateRecent(version int64, start, end []byte, ascending bool) (bool, Iterator)

func (*Tree) Iterator 

func (tree *Tree) Iterator(start, end []byte, inclusive bool) (itr Iterator, err error)

func (*Tree) IteratorLatestLeaves 

func (tree *Tree) IteratorLatestLeaves(version int64, limit int) (Iterator, error)

func (*Tree) LoadSnapshot 

func (tree *Tree) LoadSnapshot(version int64, traverseOrder constants.TraverseOrderType) (err error)

DB snapshot not cosmos sdk state snapshot

func (*Tree) LoadVersion 

func (tree *Tree) LoadVersion(version int64) (err error)

func (*Tree) Metrics 

func (tree *Tree) Metrics() metrics.Proxy

func (*Tree) Path 

func (tree *Tree) Path() string

func (*Tree) PausePruning 

func (tree *Tree) PausePruning(pause bool)

func (*Tree) Remove 

func (tree *Tree) Remove(key []byte) ([]byte, bool, error)

Remove removes a key from the working tree. The given key byte slice should not be modified after this call, since it may point to data stored inside IAVL.

func (*Tree) ReverseIterator 

func (tree *Tree) ReverseIterator(start, end []byte) (itr Iterator, err error)

func (*Tree) Revert 

func (tree *Tree) Revert(version int64) error

func (*Tree) Root 

func (tree *Tree) Root() *inode.Node

func (*Tree) SaveSnapshot 

func (tree *Tree) SaveSnapshot() (err error)

func (*Tree) SaveVersion 

func (tree *Tree) SaveVersion() ([]byte, int64, error)

func (*Tree) Set 

func (tree *Tree) Set(key, value []byte) (updated bool, err error)

Set sets a key in the working tree. Nil values are invalid. The given key/value byte slices must not be modified after this call, since they point to slices stored within IAVL. It returns true when an existing value was updated, while false means it was a new key.

func (*Tree) SetInitialVersion 

func (tree *Tree) SetInitialVersion(version int64) error

func (*Tree) Size 

func (tree *Tree) Size() int64

func (*Tree) Version 

func (tree *Tree) Version() int64

func (*Tree) VersionExists 

func (tree *Tree) VersionExists(version int64) (bool, error)

func (*Tree) WarmLeaves 

func (tree *Tree) WarmLeaves() error

func (*Tree) WorkingBytes 

func (tree *Tree) WorkingBytes() uint64

func (*Tree) WorkingHash 

func (tree *Tree) WorkingHash() []byte

func (*Tree) WorkingSize 

func (tree *Tree) WorkingSize() int64

func (*Tree) WrongBranchHashIterator 

func (tree *Tree) WrongBranchHashIterator(start, end int64) (Iterator, error)

type WrongBranchHashIterator 

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

func (*WrongBranchHashIterator) Close 

func (i *WrongBranchHashIterator) Close() error

func (*WrongBranchHashIterator) Domain 

func (i *WrongBranchHashIterator) Domain() (strat []byte, end []byte)

func (*WrongBranchHashIterator) Error 

func (i *WrongBranchHashIterator) Error() error

func (*WrongBranchHashIterator) Key 

func (i *WrongBranchHashIterator) Key() (key []byte)

func (*WrongBranchHashIterator) Next 

func (i *WrongBranchHashIterator) Next()

func (*WrongBranchHashIterator) Valid 

func (i *WrongBranchHashIterator) Valid() bool

func (*WrongBranchHashIterator) Value 

func (i *WrongBranchHashIterator) Value() (key []byte)

type WrongVersionKey 

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

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.