Documentation ¶
Overview ¶
Basic usage of VersionedTree.
import "github.com/tendermint/iavl" import "github.com/tendermint/tmlibs/db" ... tree := iavl.NewVersionedTree(128, db.NewMemDB()) tree.IsEmpty() // true tree.Set([]byte("alice"), []byte("abc")) tree.SaveVersion(1) tree.Set([]byte("alice"), []byte("xyz")) tree.Set([]byte("bob"), []byte("xyz")) tree.SaveVersion(2) tree.LatestVersion() // 2 tree.GetVersioned([]byte("alice"), 1) // "abc" tree.GetVersioned([]byte("alice"), 2) // "xyz"
Proof of existence:
root := tree.Hash() val, proof, err := tree.GetVersionedWithProof([]byte("bob"), 2) // "xyz", KeyProof, nil proof.Verify([]byte("bob"), val, root) // nil
Proof of absence:
_, proof, err = tree.GetVersionedWithProof([]byte("tom"), 2) // nil, KeyProof, nil proof.Verify([]byte("tom"), nil, root) // nil
Now we delete an old version:
tree.DeleteVersion(1) tree.VersionExists(1) // false tree.Get([]byte("alice")) // "xyz" tree.GetVersioned([]byte("alice"), 1) // nil
Can't create a proof of absence for a version we no longer have:
_, proof, err = tree.GetVersionedWithProof([]byte("tom"), 1) // nil, nil, error
Index ¶
- Constants
- Variables
- func WriteDOTGraph(w io.Writer, tree *Tree, paths []*PathToKey)
- type KeyAbsentProof
- type KeyExistsProof
- type KeyFirstInRangeProof
- type KeyInRangeProof
- type KeyLastInRangeProof
- type KeyProof
- type KeyRangeProof
- type Node
- type PathToKey
- type Tree
- func (t *Tree) Get(key []byte) (index int, value []byte)
- func (t *Tree) GetByIndex(index int) (key []byte, value []byte)
- func (t *Tree) GetFirstInRangeWithProof(startKey, endKey []byte) ([]byte, []byte, *KeyFirstInRangeProof, error)
- func (t *Tree) GetLastInRangeWithProof(startKey, endKey []byte) ([]byte, []byte, *KeyLastInRangeProof, error)
- func (t *Tree) GetRangeWithProof(startKey []byte, endKey []byte, limit int) ([][]byte, [][]byte, *KeyRangeProof, error)
- func (t *Tree) GetWithProof(key []byte) ([]byte, KeyProof, error)
- func (t *Tree) Has(key []byte) bool
- func (t *Tree) Hash() []byte
- func (t *Tree) Height() int8
- func (t *Tree) Iterate(fn func(key []byte, value []byte) bool) (stopped bool)
- func (t *Tree) IterateRange(start, end []byte, ascending bool, fn func(key []byte, value []byte) bool) (stopped bool)
- func (t *Tree) IterateRangeInclusive(start, end []byte, ascending bool, fn func(key []byte, value []byte) bool) (stopped bool)
- func (t *Tree) Remove(key []byte) ([]byte, bool)
- func (t *Tree) Set(key []byte, value []byte) (updated bool)
- func (t *Tree) Size() int
- func (t *Tree) String() string
- type VersionedTree
- func (tree *VersionedTree) DeleteVersion(version uint64) error
- func (tree *VersionedTree) GetVersioned(key []byte, version uint64) (index int, value []byte)
- func (tree *VersionedTree) GetVersionedFirstInRangeWithProof(startKey, endKey []byte, version uint64) ([]byte, []byte, *KeyFirstInRangeProof, error)
- func (tree *VersionedTree) GetVersionedLastInRangeWithProof(startKey, endKey []byte, version uint64) ([]byte, []byte, *KeyLastInRangeProof, error)
- func (tree *VersionedTree) GetVersionedRangeWithProof(startKey, endKey []byte, limit int, version uint64) ([][]byte, [][]byte, *KeyRangeProof, error)
- func (tree *VersionedTree) GetVersionedWithProof(key []byte, version uint64) ([]byte, KeyProof, error)
- func (tree *VersionedTree) Hash() []byte
- func (tree *VersionedTree) IsEmpty() bool
- func (tree *VersionedTree) LatestVersion() uint64
- func (tree *VersionedTree) Load() error
- func (tree *VersionedTree) Remove(key []byte) ([]byte, bool)
- func (tree *VersionedTree) SaveVersion(version uint64) ([]byte, error)
- func (tree *VersionedTree) Set(key, val []byte) bool
- func (tree *VersionedTree) String() string
- func (tree *VersionedTree) Tree() *Tree
- func (tree *VersionedTree) VersionExists(version uint64) bool
Constants ¶
const Version = "0.5.0"
Variables ¶
var ( // ErrInvalidProof is returned by Verify when a proof cannot be validated. ErrInvalidProof = fmt.Errorf("invalid proof") // ErrInvalidInputs is returned when the inputs passed to the function are invalid. ErrInvalidInputs = fmt.Errorf("invalid inputs") // ErrInvalidRoot is returned when the root passed in does not match the proof's. ErrInvalidRoot = fmt.Errorf("invalid root") // ErrNilRoot is returned when the root of the tree is nil. ErrNilRoot = fmt.Errorf("tree root is nil") )
var ErrVersionDoesNotExist = fmt.Errorf("version does not exist")
Functions ¶
Types ¶
type KeyAbsentProof ¶
type KeyAbsentProof struct { RootHash data.Bytes `json:"root_hash"` Version uint64 `json:"version"` Left *pathWithNode `json:"left"` Right *pathWithNode `json:"right"` }
KeyAbsentProof represents a proof of the absence of a single key.
func ReadKeyAbsentProof ¶
func ReadKeyAbsentProof(data []byte) (*KeyAbsentProof, error)
ReadKeyAbsentProof will deserialize a KeyAbsentProof from bytes.
func (*KeyAbsentProof) Bytes ¶
func (proof *KeyAbsentProof) Bytes() []byte
Bytes returns a go-wire binary serialization
func (*KeyAbsentProof) Root ¶
func (proof *KeyAbsentProof) Root() []byte
func (*KeyAbsentProof) String ¶
func (p *KeyAbsentProof) String() string
type KeyExistsProof ¶
type KeyExistsProof struct { RootHash data.Bytes `json:"root_hash"` Version uint64 `json:"version"` *PathToKey `json:"path"` }
KeyExistsProof represents a proof of existence of a single key.
func ReadKeyExistsProof ¶
func ReadKeyExistsProof(data []byte) (*KeyExistsProof, error)
ReadKeyExistsProof will deserialize a KeyExistsProof from bytes.
func (*KeyExistsProof) Bytes ¶
func (proof *KeyExistsProof) Bytes() []byte
Bytes returns a go-wire binary serialization
func (*KeyExistsProof) Root ¶
func (proof *KeyExistsProof) Root() []byte
type KeyFirstInRangeProof ¶
type KeyFirstInRangeProof struct { KeyExistsProof `json:"key_proof"` Left *pathWithNode `json:"left"` Right *pathWithNode `json:"right"` }
KeyFirstInRangeProof is a proof that a given key is the first in a given range.
func (*KeyFirstInRangeProof) String ¶
func (proof *KeyFirstInRangeProof) String() string
String returns a string representation of the proof.
type KeyInRangeProof ¶
KeyInRangeProof is an interface which covers both first-in-range and last-in-range proofs.
type KeyLastInRangeProof ¶
type KeyLastInRangeProof struct { KeyExistsProof `json:"key_proof"` Left *pathWithNode `json:"left"` Right *pathWithNode `json:"right"` }
KeyLastInRangeProof is a proof that a given key is the last in a given range.
func (*KeyLastInRangeProof) String ¶
func (proof *KeyLastInRangeProof) String() string
String returns a string representation of the proof.
type KeyProof ¶
type KeyProof interface { // Verify verfies the proof is valid. To verify absence, // the value should be nil. Verify(key, value, root []byte) error // Root returns the root hash of the proof. Root() []byte // Serialize itself Bytes() []byte }
KeyProof represents a proof of existence or absence of a single key.
type KeyRangeProof ¶
type KeyRangeProof struct { RootHash data.Bytes `json:"root_hash"` Version uint64 `json:"version"` PathToKeys []*PathToKey `json:"paths"` Left *pathWithNode `json:"left"` Right *pathWithNode `json:"right"` }
KeyRangeProof is proof that a range of keys does or does not exist.
func (*KeyRangeProof) String ¶
func (proof *KeyRangeProof) String() string
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node represents a node in a Tree.
func MakeNode ¶
MakeNode constructs an *Node from an encoded byte slice.
The new node doesn't have its hash saved or set. The caller must set it afterwards.
type PathToKey ¶
type PathToKey struct {
InnerNodes []proofInnerNode `json:"inner_nodes"`
}
PathToKey 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.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree is an immutable AVL+ Tree. Note that this tree is not thread-safe.
func (*Tree) Get ¶
Get returns the index and value of the specified key if it exists, or nil and the next index, if it doesn't.
func (*Tree) GetByIndex ¶
GetByIndex gets the key and value at the specified index.
func (*Tree) GetFirstInRangeWithProof ¶
func (t *Tree) GetFirstInRangeWithProof(startKey, endKey []byte) ([]byte, []byte, *KeyFirstInRangeProof, error)
GetFirstInRangeWithProof gets the first key/value pair in the specified range, with a proof.
func (*Tree) GetLastInRangeWithProof ¶
func (t *Tree) GetLastInRangeWithProof(startKey, endKey []byte) ([]byte, []byte, *KeyLastInRangeProof, error)
GetLastInRangeWithProof gets the last key/value pair in the specified range, with a proof.
func (*Tree) GetRangeWithProof ¶
func (t *Tree) GetRangeWithProof(startKey []byte, endKey []byte, limit int) ([][]byte, [][]byte, *KeyRangeProof, error)
GetRangeWithProof gets key/value pairs within the specified range and limit. To specify a descending range, swap the start and end keys.
Returns a list of keys, a list of values and a proof.
func (*Tree) GetWithProof ¶
GetWithProof gets the value under the key if it exists, or returns nil. A proof of existence or absence is returned alongside the value.
func (*Tree) IterateRange ¶
func (t *Tree) IterateRange(start, end []byte, ascending bool, fn func(key []byte, value []byte) bool) (stopped bool)
IterateRange makes a callback for all nodes with key between start and end non-inclusive. If either are nil, then it is open on that side (nil, nil is the same as Iterate)
func (*Tree) IterateRangeInclusive ¶
func (t *Tree) IterateRangeInclusive(start, end []byte, ascending bool, fn func(key []byte, value []byte) bool) (stopped bool)
IterateRangeInclusive makes a callback for all nodes with key between start and end inclusive. If either are nil, then it is open on that side (nil, nil is the same as Iterate)
func (*Tree) Remove ¶
Remove tries to remove a key from the tree and if removed, returns its value, and 'true'.
type VersionedTree ¶
type VersionedTree struct {
// contains filtered or unexported fields
}
VersionedTree is a persistent tree which keeps track of versions.
func NewVersionedTree ¶
func NewVersionedTree(cacheSize int, db dbm.DB) *VersionedTree
NewVersionedTree returns a new tree with the specified cache size and datastore.
func (*VersionedTree) DeleteVersion ¶
func (tree *VersionedTree) DeleteVersion(version uint64) error
DeleteVersion deletes a tree version from disk. The version can then no longer be accessed.
func (*VersionedTree) GetVersioned ¶
func (tree *VersionedTree) GetVersioned(key []byte, version uint64) ( index int, value []byte, )
GetVersioned gets the value at the specified key and version.
func (*VersionedTree) GetVersionedFirstInRangeWithProof ¶
func (tree *VersionedTree) GetVersionedFirstInRangeWithProof(startKey, endKey []byte, version uint64) ([]byte, []byte, *KeyFirstInRangeProof, error)
GetVersionedFirstInRangeWithProof gets the first key/value pair in the specified range, with a proof.
func (*VersionedTree) GetVersionedLastInRangeWithProof ¶
func (tree *VersionedTree) GetVersionedLastInRangeWithProof(startKey, endKey []byte, version uint64) ([]byte, []byte, *KeyLastInRangeProof, error)
GetVersionedLastInRangeWithProof gets the last key/value pair in the specified range, with a proof.
func (*VersionedTree) GetVersionedRangeWithProof ¶
func (tree *VersionedTree) GetVersionedRangeWithProof(startKey, endKey []byte, limit int, version uint64) ([][]byte, [][]byte, *KeyRangeProof, error)
GetVersionedRangeWithProof gets key/value pairs within the specified range and limit. To specify a descending range, swap the start and end keys.
Returns a list of keys, a list of values and a proof.
func (*VersionedTree) GetVersionedWithProof ¶
func (tree *VersionedTree) GetVersionedWithProof(key []byte, version uint64) ([]byte, KeyProof, error)
GetVersionedWithProof gets the value under the key at the specified version if it exists, or returns nil. A proof of existence or absence is returned alongside the value.
func (*VersionedTree) Hash ¶
func (tree *VersionedTree) Hash() []byte
Hash returns the hash of the latest saved version of the tree, as returned by SaveVersion. If no versions have been saved, Hash returns nil.
func (*VersionedTree) IsEmpty ¶
func (tree *VersionedTree) IsEmpty() bool
IsEmpty returns whether or not the tree has any keys. Only trees that are not empty can be saved.
func (*VersionedTree) LatestVersion ¶
func (tree *VersionedTree) LatestVersion() uint64
LatestVersion returns the latest saved version of the tree.
func (*VersionedTree) Load ¶
func (tree *VersionedTree) Load() error
Load a versioned tree from disk. All tree versions are loaded automatically.
func (*VersionedTree) Remove ¶
func (tree *VersionedTree) Remove(key []byte) ([]byte, bool)
Remove removes a key from the working tree.
func (*VersionedTree) SaveVersion ¶
func (tree *VersionedTree) SaveVersion(version uint64) ([]byte, error)
SaveVersion saves a new tree version to disk, based on the current state of the tree. Multiple calls to SaveVersion with the same version are not allowed.
func (*VersionedTree) Set ¶
func (tree *VersionedTree) Set(key, val []byte) bool
Set sets a key in the working tree. Nil values are not supported.
func (*VersionedTree) String ¶
func (tree *VersionedTree) String() string
String returns a string representation of the tree.
func (*VersionedTree) Tree ¶
func (tree *VersionedTree) Tree() *Tree
Tree returns the current working tree.
func (*VersionedTree) VersionExists ¶
func (tree *VersionedTree) VersionExists(version uint64) bool
VersionExists returns whether or not a version exists.