Documentation
¶
Index ¶
- func EmptyTrieRootHash() ledger.RootHash
- func SplitPaths(paths []ledger.Path, bitIndex int) int
- type MTrie
- func (mt *MTrie) AllPayloads() []ledger.Payload
- func (mt *MTrie) AllocatedRegCount() uint64
- func (mt *MTrie) DumpAsJSON(w io.Writer) error
- func (mt *MTrie) Equals(o *MTrie) bool
- func (mt *MTrie) IsAValidTrie() bool
- func (mt *MTrie) IsEmpty() bool
- func (mt *MTrie) MaxDepth() uint16
- func (mt *MTrie) RootHash() ledger.RootHash
- func (mt *MTrie) RootNode() *node.Node
- func (mt *MTrie) String() string
- func (mt *MTrie) UnsafeProofs(paths []ledger.Path, proofs []*ledger.TrieProof)
- func (mt *MTrie) UnsafeRead(paths []ledger.Path) []*ledger.Payload
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func EmptyTrieRootHash ¶
EmptyTrieRootHash returns the rootHash of an empty Trie for the specified path size bytes
func SplitPaths ¶ added in v0.17.0
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
Types ¶
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 the 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 where not affected by the write operation are shared between the original MTrie (before the register updates) and the updated MTrie (after the register writes).
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 NewTrieWithUpdatedRegisters ¶
func NewTrieWithUpdatedRegisters(parentTrie *MTrie, updatedPaths []ledger.Path, updatedPayloads []ledger.Payload) (*MTrie, error)
NewTrieWithUpdatedRegisters constructs a new trie containing all registers from the parent trie. 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 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 `updatedPayloads` are permuted IN-PLACE for optimized processing. TODO: move consistency checks from MForest to here, to make API safe and self-contained
func (*MTrie) AllPayloads ¶ added in v0.12.0
AllPayloads returns all payloads
func (*MTrie) AllocatedRegCount ¶
AllocatedRegCount returns the number of allocated registers in the trie. Concurrency safe (as Tries are immutable structures by convention)
func (*MTrie) DumpAsJSON ¶ added in v0.11.0
DumpAsJSON dumps the trie key value pairs to a file having each key value pair as a json row
func (*MTrie) Equals ¶
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 ¶ added in v0.12.0
IsAValidTrie verifies the content of the trie for potential issues
func (*MTrie) IsEmpty ¶ added in v0.17.0
IsEmpty checks if a trie is empty.
An empty try doesn't mean a trie with no allocated registers.
func (*MTrie) MaxDepth ¶
MaxDepth returns the length of the longest branch from root to leaf. Concurrency safe (as Tries are immutable structures by convention)
func (*MTrie) RootHash ¶
RootHash returns the trie's root hash. Concurrency safe (as Tries are immutable structures by convention)
func (*MTrie) RootNode ¶
RootNode returns the Trie's root Node Concurrency safe (as Tries are immutable structures by convention)
func (*MTrie) String ¶
String returns the trie's string representation. Concurrency safe (as Tries are immutable structures by convention)
func (*MTrie) UnsafeProofs ¶
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.
func (*MTrie) UnsafeRead ¶
UnsafeRead read payloads for the given paths. UNSAFE: requires _all_ paths to have a length of mt.Height bits. CAUTION: while reading the payloads, `paths` is permuted IN-PLACE for optimized processing. Return:
- `payloads` []*ledger.Payload For each path, the corresponding payload is written into payloads. AFTER the read operation completes, the order of `path` and `payloads` are such that for `path[i]` the corresponding register value is referenced by 0`payloads[i]`.
TODO move consistency checks from Forest into Trie to obtain a safe, self-contained API
Source Files