payloadless

package
v0.51.1-payloadless-2 Latest Latest
Warning

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

 Go to latest Published: Sep 15, 2026 License: AGPL-3.0 Imports: 15 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	EncodedTrieSize = encodedTrieSize
)

Variables

View Source 
var ErrPayloadHashMismatch = errors.New("payload hash mismatch: storehouse value inconsistent with trie")

ErrPayloadHashMismatch is returned when the value supplied by valueReader does not hash to the leaf hash stored in the payloadless proof.

Functions

func EmptyTrieRootHash 

func EmptyTrieRootHash() ledger.RootHash

EmptyTrieRootHash returns the rootHash of an empty Trie for the specified path size bytes

func EncodeNode 

func EncodeNode(n *Node, lchildIndex uint64, rchildIndex uint64, scratch []byte) []byte

EncodeNode encodes node. Scratch buffer is used to avoid allocs. WARNING: The returned buffer is likely to share the same underlying array as the scratch buffer. Caller is responsible for copying or using returned buffer before scratch buffer is used again.

func EncodeTrie 

func EncodeTrie(trie *MTrie, rootIndex uint64, scratch []byte) []byte

EncodeTrie encodes trie in the following format: - root node index (8 byte) - allocated reg count (8 byte) - root node hash (32 bytes) Scratch buffer is used to avoid allocs. WARNING: The returned buffer is likely to share the same underlying array as the scratch buffer. Caller is responsible for copying or using returned buffer before scratch buffer is used again.

func ProveAndReconstruct 

func ProveAndReconstruct(
	l ledger.PayloadlessLedger,
	state ledger.State,
	registerIDs []flow.RegisterID,
	valueReader RegisterValueReader,
	pathFinderVersion uint8,
) ([]byte, error)

ProveAndReconstruct generates a reconstructed full batch proof for the given register IDs using a payloadless ledger and a value source. The returned bytes encode a *ledger.TrieBatchProof — wire-compatible with the full mtrie's proof format — so downstream consumers can stay mode-agnostic.

The flow:

  1. Convert register IDs to ledger keys and derive their paths via pathfinder.KeysToPaths.
  2. Build a path → (registerID, key) map so reconstructPayloadlessProof can recover the register ID for each leaf in the (path-sorted) proof and reuse the already-allocated key when building the payload.
  3. Call ledger.Prove() to get a *PayloadlessTrieBatchProof (leaf hashes, no values).
  4. Hand the proof, map, and valueReader to reconstructPayloadlessProof to verify each leaf hash and re-encode as a full *TrieBatchProof.

TODO(perf): overlap step 3 with the value reads from step 4. Today the steps run sequentially: Prove finishes, then per-leaf value reads run inline inside reconstructPayloadlessProof. The two I/O phases are independent and can run in parallel:

  • Phase A (parallel): l.Prove(query) and one valueReader call per registerID, fanned out via an errgroup with a bounded SetLimit (the reader's backend has its own concurrency limits — don't fan out blindly to N).
  • Phase B: once both complete, run a pure verify+build pass over the assembled (proof, value) pairs — no I/O.

The per-leaf verify work (HashLeaf + payload build) is microseconds and is not worth pipelining at finer grain.

Expected errors during normal operation:

func SplitPaths 

func SplitPaths(paths []ledger.Path, bitIndex int) int

SplitPaths permutes the input paths to be partitioned into 2 parts. The first part contains paths with a zero bit at the input bitIndex, the second part contains paths with a one at the bitIndex. The index of partition is returned.

This would be the partition step of an ascending quick sort of paths (lexicographic order) with the pivot being the path with all zeros and 1 at bitIndex. The comparison of paths is only based on the bit at bitIndex, the function therefore assumes all paths have equal bits from 0 to bitIndex-1

func TraverseNodes 

func TraverseNodes(trie *MTrie, processNode func(*Node) error) error

TraverseNodes traverses all nodes of the trie in DFS order

Types

type EncodedTrie 

type EncodedTrie struct {
	RootIndex uint64
	RegCount  uint64
	RootHash  hash.Hash
}

func ReadEncodedTrie 

func ReadEncodedTrie(reader io.Reader, scratch []byte) (EncodedTrie, error)

type Forest 

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

Forest holds several in-memory payloadless tries. As Forest is a storage-abstraction layer, we assume that all registers are addressed via paths of pre-defined uniform length.

Unlike the full mtrie Forest, this variant stores only leaf hashes (HashLeaf(path, value)) per register and not the underlying payload values. Reads therefore return leaf hashes, not values.

Forest has a limit, the forestCapacity, on the number of tries it is able to store. If more tries are added than the capacity, the Least Recently Used trie is removed (evicted) from the Forest. THIS IS A ROUGH HEURISTIC as it might evict tries that are still needed. In fully matured Flow, we will have an explicit eviction policy.

TODO: Storage Eviction Policy for Forest For the execution node: we only evict on sealing a result.

func NewForest 

func NewForest(forestCapacity int, metrics module.LedgerMetrics, onTreeEvicted func(tree *MTrie)) (*Forest, error)

NewForest returns a new instance of memory forest.

CAUTION on forestCapacity: the specified capacity MUST be SUFFICIENT to store all needed MTries in the forest. If more tries are added than the capacity, the Least Recently Added trie is removed (evicted) from the Forest (FIFO queue). Make sure you chose a sufficiently large forestCapacity, such that, when reaching the capacity, the Least Recently Added trie will never be needed again.

func (*Forest) AddTrie 

func (f *Forest) AddTrie(newTrie *MTrie) error

AddTrie adds a trie to the forest

func (*Forest) AddTries 

func (f *Forest) AddTries(newTries []*MTrie) error

AddTries adds a trie to the forest

func (*Forest) GetEmptyRootHash 

func (f *Forest) GetEmptyRootHash() ledger.RootHash

GetEmptyRootHash returns the rootHash of empty Trie

func (*Forest) GetTrie 

func (f *Forest) GetTrie(rootHash ledger.RootHash) (*MTrie, error)

GetTrie returns trie at specific rootHash warning, use this function for read-only operation

func (*Forest) GetTries 

func (f *Forest) GetTries() ([]*MTrie, error)

GetTries returns list of currently cached tree root hashes

func (*Forest) HasTrie 

func (f *Forest) HasTrie(rootHash ledger.RootHash) bool

HasTrie returns true if trie exist at specific rootHash

func (*Forest) IsAllocatedRegisters 

func (f *Forest) IsAllocatedRegisters(r *ledger.TrieRead) ([]bool, error)

IsAllocatedRegisters returns, for each input path, whether an allocated register exists in the trie identified by `r.RootHash`. A register is considered allocated when the leaf hash stored at its path is non-nil (i.e. the stored value is non-empty). TODO: can be optimized further if we don't care about changing the order of the input r.Paths

func (*Forest) MostRecentTouchedRootHash 

func (f *Forest) MostRecentTouchedRootHash() (ledger.RootHash, error)

MostRecentTouchedRootHash returns the rootHash of the most recently touched trie

func (*Forest) NewTrie 

func (f *Forest) NewTrie(u *ledger.TrieUpdate) (*MTrie, error)

NewTrie creates a new trie by updating values for registers in the parent trie, and returns new trie and error (if any). In case there are multiple updates to the same register, NewTrie will persist the latest written value. Note: NewTrie doesn't add new trie to forest, unlike Update().

Only the payload's value bytes are used; keys are discarded.

func (*Forest) Proofs 

func (f *Forest) Proofs(r *ledger.TrieRead) (*ledger.PayloadlessTrieBatchProof, error)

Proofs returns a batch proof for the given paths.

Proofs are generally _not_ provided in the register order of the query. In the current implementation, input paths in the TrieRead `r` are sorted in an ascendent order, The output proofs are provided following the order of the sorted paths.

Returned proofs carry leaf hashes (HashLeaf(path, value)) rather than full payloads.

func (*Forest) PurgeCacheExcept 

func (f *Forest) PurgeCacheExcept(rootHash ledger.RootHash) error

PurgeCacheExcept removes all tries in the memory except the one with the given root hash

func (*Forest) ReadLeafHashes 

func (f *Forest) ReadLeafHashes(r *ledger.TrieRead) ([]*hash.Hash, error)

ReadLeafHashes reads leaf hashes for a slice of paths and returns the leaf hashes in the same order as the input. A nil entry indicates the path has no allocated register in the trie. TODO: can be optimized further if we don't care about changing the order of the input r.Paths

func (*Forest) ReadSingleLeafHash 

func (f *Forest) ReadSingleLeafHash(r *ledger.TrieReadSingleValue) (*hash.Hash, error)

ReadSingleLeafHash reads the leaf hash for a single path. Returns nil if no leaf exists at that path or the leaf represents an unallocated register.

func (*Forest) Size 

func (f *Forest) Size() int

Size returns the number of active tries in this store

func (*Forest) Update 

func (f *Forest) Update(u *ledger.TrieUpdate) (ledger.RootHash, error)

Update creates a new trie by updating values for registers in the parent trie, adds new trie to forest, and returns rootHash and error (if any). In case there are multiple updates to the same register, Update will persist the latest written value. Note: Update adds new trie to forest, unlike NewTrie().

The input `u.Payloads` are interpreted by extracting only the value bytes; the payloadless trie does not store the payload key.

type MTrie 

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

MTrie represents a perfect in-memory full binary Merkle tree with uniform height. For a detailed description of the storage model, please consult `mtrie/README.md`

A MTrie is a thin wrapper around a trie's root Node. An MTrie implements the logic for forming MTrie-graphs from the elementary nodes. Specifically:

  • how Nodes (graph vertices) form a Trie,
  • how register values are read from the trie,
  • how Merkle proofs are generated from a trie, and
  • how a new Trie with updated values is generated.

`MTrie`s are _immutable_ data structures. Updating register values is implemented through copy-on-write, which creates a new `MTrie`. For minimal memory consumption, all sub-tries that were not affected by the write operation are shared between the original MTrie (before the register updates) and the updated MTrie (after the register writes).

MTrie expects that for a specific path, the register's key never changes.

DEFINITIONS and CONVENTIONS:

  • HEIGHT of a node v in a tree is the number of edges on the longest downward path between v and a tree leaf. The height of a tree is the height of its root. The height of a Trie is always the height of the fully-expanded tree.

func NewEmptyMTrie 

func NewEmptyMTrie() *MTrie

NewEmptyMTrie returns an empty Mtrie (root is nil)

func NewMTrie 

func NewMTrie(root *Node, regCount uint64) (*MTrie, error)

NewMTrie returns a Mtrie given the root.

No error returns are expected during normal operation.

func NewTrieWithUpdatedRegisters 

func NewTrieWithUpdatedRegisters(
	parentTrie *MTrie,
	updatedPaths []ledger.Path,
	updatedValues [][]byte,
	prune bool,
) (*MTrie, uint16, error)

NewTrieWithUpdatedRegisters constructs a new trie containing all registers from the parent trie, and returns:

  • updated trie
  • max depth touched during update (this isn't affected by prune flag)
  • error

The key-value pairs specify the registers whose values are supposed to hold updated values compared to the parent trie. Constructing the new trie is done in a COPY-ON-WRITE manner:

  • The original trie remains unchanged.
  • subtries that remain unchanged are referenced from the parent trie instead of copied.

UNSAFE: method requires the following conditions to be satisfied:

  • keys are NOT duplicated
  • requires _all_ paths to have a length of mt.Height bits.

CAUTION: `updatedPaths` and `updatedValues` are permuted IN-PLACE for optimized processing. CAUTION: MTrie expects that for a specific path, the value's key never changes. TODO: move consistency checks from MForest to here, to make API safe and self-contained

func ReadTrie 

func ReadTrie(reader io.Reader, scratch []byte, getNode func(nodeIndex uint64) (*Node, error)) (*MTrie, error)

ReadTrie reconstructs a trie from data read from reader.

func (*MTrie) AllLeafHashes 

func (mt *MTrie) AllLeafHashes() []*hash.Hash

AllLeafHashes returns all leaf hashes stored in the trie. Empty leaves (unallocated registers) are skipped.

CAUTION: each returned pointer aliases the corresponding trie node's internal leaf hash. Tries are immutable and shared copy-on-write across trie versions, so the caller MUST NOT modify any pointee; doing so would corrupt that node's cached hash. Callers needing mutable hashes must copy them. Do NOT MODIFY the returned hashes!

func (*MTrie) AllocatedRegCount 

func (mt *MTrie) AllocatedRegCount() uint64

AllocatedRegCount returns the number of allocated registers in the trie. Concurrency safe (as Tries are immutable structures by convention)

func (*MTrie) DumpAsJSON 

func (mt *MTrie) DumpAsJSON(w io.Writer) error

DumpAsJSON dumps the trie leaf entries to a writer having each leaf as a json row. Each entry contains the leaf's path and its stored leaf hash.

func (*MTrie) Equals 

func (mt *MTrie) Equals(o *MTrie) bool

Equals compares two tries for equality. Tries are equal iff they store the same data (i.e. root hash matches) and their number and height are identical

func (*MTrie) IsAValidTrie 

func (mt *MTrie) IsAValidTrie() bool

IsAValidTrie verifies the content of the trie for potential issues

func (*MTrie) IsEmpty 

func (mt *MTrie) IsEmpty() bool

IsEmpty checks if a trie is empty.

An empty trie (root is nil) is not the same as a trie whose registers are all unallocated.

func (*MTrie) ReadSingleLeafHash 

func (mt *MTrie) ReadSingleLeafHash(path ledger.Path) *hash.Hash

ReadSingleLeafHash reads and returns the leaf hash for a single path. Returns nil if no leaf exists at the given path or if the leaf represents an unallocated register.

CAUTION: the returned pointer aliases the trie node's internal leaf hash. Tries are immutable and shared copy-on-write across trie versions, so the caller MUST NOT modify the pointee; doing so would corrupt the node's cached hash. Callers needing a mutable hash must copy it (see the Forest layer, which returns a defensive copy). Do NOT MODIFY the returned hash!

func (*MTrie) RootHash 

func (mt *MTrie) RootHash() ledger.RootHash

RootHash returns the trie's root hash. Concurrency safe (as Tries are immutable structures by convention)

func (*MTrie) RootNode 

func (mt *MTrie) RootNode() *Node

RootNode returns the Trie's root Node Concurrency safe (as Tries are immutable structures by convention)

func (*MTrie) String 

func (mt *MTrie) String() string

String returns the trie's string representation. Concurrency safe (as Tries are immutable structures by convention)

func (*MTrie) UnsafeProofs 

func (mt *MTrie) UnsafeProofs(paths []ledger.Path) *ledger.PayloadlessTrieBatchProof

UnsafeProofs provides proofs for the given paths.

CAUTION: while updating, `paths` and `proofs` are permuted IN-PLACE for optimized processing. UNSAFE: requires _all_ paths to have a length of mt.Height bits. Paths in the input query don't have to be deduplicated, though deduplication would result in allocating less dynamic memory to store the proofs.

func (*MTrie) UnsafeRead 

func (mt *MTrie) UnsafeRead(paths []ledger.Path) []*hash.Hash

UnsafeRead reads leaf hashes for the given paths. UNSAFE: requires _all_ paths to have a length of mt.Height bits. CAUTION: while reading the leaf hashes, `paths` is permuted IN-PLACE for optimized processing. Return:

  • `leafHashes` []*hash.Hash For each path, the corresponding leaf hash is written into leafHashes. AFTER the read operation completes, the order of `path` and `leafHashes` are such that for `path[i]` the corresponding leaf hash is referenced by `leafHashes[i]`. A nil entry indicates that no leaf exists at that path or the leaf represents an unallocated register.

TODO move consistency checks from Forest into Trie to obtain a safe, self-contained API

type Node 

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

Node defines a payloadless Mtrie node.

Unlike the regular mtrie Node which stores full payloads, a payloadless Node stores only the leaf hash for leaf nodes. This enables significant memory savings while preserving the same root hash as a full trie.

DEFINITIONS:

  • HEIGHT of a node v in a tree is the number of edges on the longest downward path between v and a tree leaf (in a hypothetical, fully expanded (perfect) tree, i.e. without compactification or nil-pruning).

Conceptually, an MTrie is a sparse Merkle Trie, which has two node types:

  • INTERIM node: has at least one child (i.e. lChild or rChild is not nil). Interim nodes do not store a path and have no leafHash.
  • LEAF node: has _no_ children. It represents a single register, storing a path and the ability to provide the hash commitment of the register's content. Nodes at height 𝒽 = 0 are always leaves. Nodes with 𝒽 > 0 are either leaves or interim nodes. A leaf at height 𝒽 represents a height-𝒽 subtree that holds a single allocated register. Because such a subtree contains no branches, it is collapsed into one node — a COMPACTIFIED LEAF (per mtrie/README.md the term spans all heights 𝒽 ≥ 0). Compactification is optional and always root-hash-preserving. See documentation of `Node.leafHash` and `Node.hashValue` for storage and hashing details.

Per convention, we also consider nil as a leaf. Formally, nil is the generic representative for any empty (sub)-trie (i.e. a trie without allocated registers).

Nodes are supposed to be treated as _immutable_ data structures. TODO: optimized data structures might be able to reduce memory consumption

func NewInterimCompactifiedNode 

func NewInterimCompactifiedNode(height int, lChild, rChild *Node) *Node

NewInterimCompactifiedNode creates a new interim Node - compactified if possible. For compactification, we only consider the immediate children. When starting with a maximally pruned trie and creating only InterimCompactifiedNodes during an update, the resulting trie remains maximally pruned. Details on compactification:

  • If _both_ immediate children represent completely unallocated sub-tries, then the sub-trie with the new interim node is also completely empty. We return nil.
  • If either child is a leaf (i.e. representing a single allocated register) _and_ the other child represents a completely unallocated sub-trie, the new interim node also only holds a single allocated register. In this case, we return a compactified leaf.

UNCHECKED requirement:

  • for any child `c` that is non-nil, its height must satisfy: height = c.height + 1

func NewInterimNode 

func NewInterimNode(height int, lChild, rChild *Node) *Node

NewInterimNode creates a new interim Node. UNCHECKED requirement:

  • for any child `c` that is non-nil, its height must satisfy: height = c.height + 1

func NewLeaf 

func NewLeaf(path ledger.Path, value []byte, height int) *Node

NewLeaf constructs the leaf Node 𝓃 representing the single register (path, value) at the given height 𝒽. By construction, 𝓃.Hash() equals the hash that the height-𝒽 subtree containing the register would have in the fully-expanded trie. In other words, tries built from these constructors share the same root hash as a fully-expanded trie. That subtree hash is computed by compactification: the recursive application of hashing (see mtrie/README.md for details). It starts from the register's height-0 leaf hash and hashes upward 𝒽 levels, combining at each level with the default hash of the empty sibling subtree.

A `nil` or empty `value` denotes an unallocated register; the result is the default node for the given height (hash is DefaultHashForHeight(height) independent of path; see newDefaultLeaf for details).

It is safe for `path` or `value` to be mutated after the call to `NewLeaf` returns.

UNCHECKED requirement: height must be non-negative.

func NewLeafWithHash 

func NewLeafWithHash(path ledger.Path, leafHash hash.Hash, height int) *Node

NewLeafWithHash creates a leaf Node from a pre-computed leaf hash. This is used when converting from a full trie or loading from a payloadless checkpoint. The nodeHash is computed by extending the leafHash (height-0) to the specified height.

It is safe for `path` to be mutated after this function returns.

UNCHECKED requirement: height must be non-negative UNCHECKED requirement: leafHash must be HashLeaf(path, originalValue)

func NewNode 

func NewNode(height int,
	lchild,
	rchild *Node,
	path ledger.Path,
	leafHash *hash.Hash,
	hashValue hash.Hash,
) *Node

NewNode creates a new Node. CAUTION: INSECURE! Only intended to reconstruct Nodes from their serialization! UNCHECKED requirement: combination of values must conform to a valid node type (see documentation of `Node` for details)

func NewRelevelledLeaf 

func NewRelevelledLeaf(leaf *Node, relevellingHeight int) *Node

NewRelevelledLeaf creates a new compactified leaf 𝓁' for the same register (path, value) as the input leaf 𝓁, re-levelled to height `relevellingHeight`. This is needed when a register r is allocated or removed in the neighbourhood of 𝓁, changing the height at which 𝓁 can be compactified. Example: 

     trie without r                 trie with r

        parent                        parent
       ╱    ╲                         ╱    ╲
      𝓁      △         ◀──▶          ◯      △        height 𝒽
      ┊                            ╱  ╲
      ┊                           𝓁'   𝓃             height 𝒽-1
      ┊                           ┊
      •                           •                  height 0 (fully-expanded perfect trie)

parent : genuine branch at height 𝒽+1; its other child △ is a non-empty sibling subtree
         (the reason 𝓁 sits at height 𝒽, not higher). Unchanged by allocating r.
◯      : interim node materialized at 𝓁's former position ( height-𝒽 ).
𝓁, 𝓁'  : the SAME register (path, value); 𝓁' is 𝓁 re-levelled to a lower height 𝒽' (𝒽-1 shown).
𝓃      : compactified leaf representing register r.
•      : the register's actual leaf at height 0 in the fully-expanded (perfect) trie.
dotted : single-child perfect-trie path (┊) that compactification collapses into one node.

Implementation correctly handles leaves that represent either allocated or unallocated registers. For an unallocated register represented by an explicit default leaf (which carries the register's path), a new default leaf at `relevellingHeight` is created; this is useful for our shortcut for non-inclusion proofs utilizing explicitly represented default leaf nodes. A `nil` input yields a `nil` result.

UNCHECKED requirement: `leaf.IsLeaf()` must be true

func ReadNode 

func ReadNode(reader io.Reader, scratch []byte, getNode func(nodeIndex uint64) (*Node, error)) (*Node, error)

ReadNode reconstructs a node from data read from reader. Scratch buffer is used to avoid allocs. It should be used directly instead of using append. This function uses len(scratch) and ignores cap(scratch), so any extra capacity will not be utilized. If len(scratch) < 1024, then a new buffer will be allocated and used.

func (*Node) AllLeafHashes 

func (n *Node) AllLeafHashes() []*hash.Hash

AllLeafHashes returns the leaf hash of this node and all leaf hashes of the subtrie. Empty leaves (unallocated registers) are skipped.

func (*Node) FmtStr 

func (n *Node) FmtStr(prefix string, subpath string) string

FmtStr provides formatted string representation of the Node and sub tree

func (*Node) Hash 

func (n *Node) Hash() hash.Hash

Hash returns the Node's cached hash value, which is a fixed-size array, so the returned value is a copy; mutating it does not affect the Node.

func (*Node) Height 

func (n *Node) Height() int

Height returns the Node's height. Per definition, the height of a node v in a tree is the number of edges on the longest downward path between v and a tree leaf.

func (*Node) IsAllocatedRegisterLeaf 

func (n *Node) IsAllocatedRegisterLeaf() bool

IsAllocatedRegisterLeaf reports whether this node is a leaf representing an allocated register (equivalently, a non-default compactified leaf, at any height 𝒽 ≥ 0). It is a computationally very lightweight check intended to be run on leaf nodes, optimized for minimal computational cost rather than universal applicability.

On leaves it coincides with the negation of `IsDefaultNode`: 

𝓃.IsAllocatedRegisterLeaf() = ¬ 𝓃.IsDefaultNode()  for any node 𝓃 with 𝓃.IsLeaf() == true

CAUTION:

  • For non-leaf nodes, this function always returns false. We do *not* check whether the node could be compactified into a non-default leaf. This is a deliberate trade-off for minimal computational cost.
  • A false result therefore does NOT imply the sub-trie is empty/default: any interim node returns false regardless of the subtree beneath it. To test whether a sub-trie is empty/default, use the universally-applicable `IsDefaultNode`.

func (*Node) IsDefaultNode 

func (n *Node) IsDefaultNode() bool

IsDefaultNode returns true iff the sub-trie represented by this root node contains only unallocated registers. This is the case, if and only if the node is nil or the node's hash is equal to the default hash value at the respective height.

This function is universally applicable, irrespective of compactification, nil-pruning, or whether the node is a leaf or an interim node.

func (*Node) IsLeaf 

func (n *Node) IsLeaf() bool

IsLeaf returns true if and only if Node is a LEAF.

func (*Node) LeafHash 

func (n *Node) LeafHash() *hash.Hash

LeafHash returns the Node's leaf hash HashLeaf(path, value). Returns nil for interim nodes and for leaves that represent unallocated registers. Do NOT MODIFY returned hash!

func (*Node) LeftChild 

func (n *Node) LeftChild() *Node

LeftChild returns the Node's left child. Only INTERIM nodes have children. Do NOT MODIFY returned Node!

func (*Node) Path 

func (n *Node) Path() *ledger.Path

Path returns a pointer to the Node's register storage path. If the node is not a leaf, the function returns `nil`.

func (*Node) RightChild 

func (n *Node) RightChild() *Node

RightChild returns the Node's right child. Only INTERIM nodes have children. Do NOT MODIFY returned Node!

func (*Node) VerifyCachedHash 

func (n *Node) VerifyCachedHash() bool

VerifyCachedHash verifies that every node in the subtree rooted at this node has a cached `hashValue` matching its freshly recomputed hash. CAUTION: this recomputes the hash of every node in the subtree and is therefore very expensive on large tries.

type NodeIterator 

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

NodeIterator is an iterator over the nodes in a trie. It guarantees a DESCENDANTS-FIRST-RELATIONSHIP in the sequence of nodes it generates:

  • Consider the sequence of nodes, in the order they are generated by NodeIterator. Let `node[k]` denote the node with index `k` in this sequence.
  • Descendents-First-Relationship means that for any `node[k]`, all its descendents have indices strictly smaller than k in the iterator's sequence.

The Descendents-First-Relationship has the following important property: When re-building the Trie from the sequence of nodes, one can build the trie on the fly, as for each node, the children have been previously encountered.

func NewNodeIterator 

func NewNodeIterator(n *Node) *NodeIterator

NewNodeIterator returns a node NodeIterator, which iterates through all nodes comprising the MTrie. The Iterator guarantees a DESCENDANTS-FIRST-RELATIONSHIP in the sequence of nodes it generates:

  • Consider the sequence of nodes, in the order they are generated by NodeIterator. Let `node[k]` denote the node with index `k` in this sequence.
  • Descendents-First-Relationship means that for any `node[k]`, all its descendents have indices strictly smaller than k in the iterator's sequence.

The Descendents-First-Relationship has the following important property: When re-building the Trie from the sequence of nodes, one can build the trie on the fly, as for each node, the children have been previously encountered. NodeIterator created by NewNodeIterator is safe for concurrent use because visitedNodes is always nil in this case.

func NewUniqueNodeIterator 

func NewUniqueNodeIterator(n *Node, visitedNodes map[*Node]uint64) *NodeIterator

NewUniqueNodeIterator returns a node NodeIterator, which iterates through all unique nodes that weren't visited. This should be used for forest node iteration to avoid repeatedly traversing shared sub-tries. The Iterator guarantees a DESCENDANTS-FIRST-RELATIONSHIP in the sequence of nodes it generates:

  • Consider the sequence of nodes, in the order they are generated by NodeIterator. Let `node[k]` denote the node with index `k` in this sequence.
  • Descendents-First-Relationship means that for any `node[k]`, all its descendents have indices strictly smaller than k in the iterator's sequence.

The Descendents-First-Relationship has the following important property: When re-building the Trie from the sequence of nodes, one can build the trie on the fly, as for each node, the children have been previously encountered. WARNING: visitedNodes is not safe for concurrent use.

func (*NodeIterator) Next 

func (i *NodeIterator) Next() bool

Next moves the cursor to the next node in order for Value method to return it. It returns true if there is a next node to iterate, in which case the Value method will return the node. It returns false if there is no more node to iterate, in which case the Value method will return nil.

func (*NodeIterator) Value 

func (i *NodeIterator) Value() *Node

Value will return the current node at the cursor. Note: you should call Next() before calling

type OnTreeEvictedFunc 

type OnTreeEvictedFunc func(tree *MTrie)

type RegisterValueReader 

type RegisterValueReader func(registerID flow.RegisterID) (flow.RegisterValue, error)

RegisterValueReader is a function type that reads register values. It returns:

  • (value, nil) if the register is found
  • (nil, nil) if the register is not found (treated as empty/deleted)
  • (nil, error) for any other errors

type TrieCache 

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

TrieCache caches tries into memory, it acts as a fifo queue so when it reaches to the capacity it would evict the oldest trie from the cache.

Under the hood it uses a circular buffer of mtrie pointers and a map of rootHash to cache index for fast lookup

func NewTrieCache 

func NewTrieCache(capacity uint, onTreeEvicted OnTreeEvictedFunc) (*TrieCache, error)

NewTrieCache returns a new TrieCache with given capacity. Returns an error if capacity is zero.

func (*TrieCache) Count 

func (tc *TrieCache) Count() int

Count returns number of items stored in the cache

func (*TrieCache) Get 

func (tc *TrieCache) Get(rootHash ledger.RootHash) (*MTrie, bool)

Get returns the trie by rootHash, if not exist will return nil and false

func (*TrieCache) LastAddedTrie 

func (tc *TrieCache) LastAddedTrie() *MTrie

LastAddedTrie returns the last trie added to the cache

func (*TrieCache) Purge 

func (tc *TrieCache) Purge()

Purge removes all mtries stored in the buffer

func (*TrieCache) Push 

func (tc *TrieCache) Push(t *MTrie)

Push pushes trie to queue. If queue is full, it overwrites the oldest element.

func (*TrieCache) Tries 

func (tc *TrieCache) Tries() []*MTrie

Tries returns elements in queue, starting from the oldest element to the newest element.

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.