Documentation
¶
Overview ¶
Package trie implements Merkle Patricia Tries.
Index ¶
- func DeriveRoot(list DerivableList) thor.Bytes32
- type DatabaseReader
- type DatabaseWriter
- type DerivableList
- type Iterator
- type Leaf
- type MissingNodeError
- type Node
- type NodeIterator
- type Root
- type Trie
- func (t *Trie) Commit(db DatabaseWriter, newVer Version, skipHash bool) error
- func (t *Trie) Get(key []byte) ([]byte, []byte, error)
- func (t *Trie) Hash() thor.Bytes32
- func (t *Trie) NodeIterator(start []byte, minVer Version) NodeIterator
- func (t *Trie) RootNode() Node
- func (t *Trie) SetCacheTTL(ttl uint16)
- func (t *Trie) Update(key, value, meta []byte) error
- type Version
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DeriveRoot ¶
func DeriveRoot(list DerivableList) thor.Bytes32
Types ¶
type DatabaseReader ¶
DatabaseReader wraps the Get method of a backing store for the trie.
type DatabaseWriter ¶
type DatabaseWriter interface { // Put stores the mapping (path, ver)->value in the database. // Implementations must not hold onto the value bytes, the trie // will reuse the slice across calls to Put. Put(path []byte, ver Version, value []byte) error }
DatabaseWriter wraps the Put method of a backing store for the trie.
type DerivableList ¶
type Iterator ¶
type Iterator struct { Key []byte // Current data key on which the iterator is positioned on Value []byte // Current data value on which the iterator is positioned on Meta []byte // Current metadata on which the iterator is positioned on Err error // contains filtered or unexported fields }
Iterator is a key-value trie iterator that traverses a Trie.
func NewIterator ¶
func NewIterator(it NodeIterator) *Iterator
NewIterator creates a new key-value iterator from a node iterator. Note that the value returned by the iterator is raw. If the content is encoded (e.g. storage value is RLP-encoded), it's caller's duty to decode it.
type MissingNodeError ¶
type MissingNodeError struct { Ref refNode // the ref node of the missing node Path []byte // hex-encoded path to the missing node Err error // the actual error }
MissingNodeError is returned by the trie functions (Get, Update) in the case where a trie node is not present in the local database. It contains information necessary for retrieving the missing node.
func (*MissingNodeError) Error ¶
func (err *MissingNodeError) Error() string
type NodeIterator ¶
type NodeIterator interface { // Next moves the iterator to the next node. If the parameter is false, any child // nodes will be skipped. Next(bool) bool // Error returns the error status of the iterator. Error() error // Blob returns the encoded blob and version num of the current node. // If the current node is not stored as standalone node, the returned blob has zero length. Blob() ([]byte, Version, error) // Path returns the hex-encoded path to the current node. // Callers must not retain references to the return value after calling Next. // For leaf nodes, the last element of the path is the 'terminator symbol' 0x10. Path() []byte // Leaf returns the leaf node if the current node is a leaf node, or nil returned. Leaf() *Leaf // LeafKey returns the key of the leaf. The method panics if the iterator is not // positioned at a leaf. Callers must not retain references to the value after // calling Next. LeafKey() []byte }
NodeIterator is an iterator to traverse the trie pre-order.
type Trie ¶
type Trie struct {
// contains filtered or unexported fields
}
Trie is a Merkle Patricia Trie. The zero value is an empty trie with no database. Use New to create a trie that sits on top of a database.
Trie is not safe for concurrent use.
func FromRootNode ¶ added in v2.2.0
func FromRootNode(rootNode Node, db DatabaseReader) *Trie
FromRootNode creates a trie from a live root node.
func New ¶
func New(root Root, db DatabaseReader) *Trie
New creates a trie with an existing root node from db.
If root hash is zero or the hash of an empty string, the trie is initially empty . Accessing the trie loads nodes from db on demand.
func (*Trie) Commit ¶
func (t *Trie) Commit(db DatabaseWriter, newVer Version, skipHash bool) error
Commit writes all nodes to the trie's database.
Committing flushes nodes from memory. Subsequent Get calls will load nodes from the database. If skipHash is true, less disk space is taken up but crypto features of merkle trie lost.
func (*Trie) Get ¶
Get returns the value with meta for key stored in the trie. The value and meta bytes must not be modified by the caller. If a node was not found in the database, a MissingNodeError is returned.
func (*Trie) Hash ¶
Hash returns the root hash of the trie. It does not write to the database and can be used even if the trie doesn't have one.
func (*Trie) NodeIterator ¶
func (t *Trie) NodeIterator(start []byte, minVer Version) NodeIterator
NodeIterator returns an iterator that returns nodes of the trie. Iteration starts at the key after the given start key. Nodes with version smaller than minVer are filtered out.
func (*Trie) SetCacheTTL ¶ added in v2.2.0
SetCacheTTL sets the number of 'cache generations' to keep. A cache generation is increased by a call to Commit.
func (*Trie) Update ¶
Update associates key with value in the trie. Subsequent calls to Get will return value. If value has length zero, any existing value is deleted from the trie and calls to Get will return nil.
The value bytes must not be modified by the caller while they are stored in the trie.
If a node was not found in the database, a MissingNodeError is returned.