Documentation
¶
Index ¶
- func EmptyTrieRootHash() ledger.RootHash
- func SplitPaths(paths []ledger.Path, bitIndex int) int
- func TraverseNodes(trie *MTrie, processNode func(*node.Node) error) error
- type MTrie
- func (mt *MTrie) AllPayloads() []*ledger.Payload
- func (mt *MTrie) AllocatedRegCount() uint64
- func (mt *MTrie) AllocatedRegSize() 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) ReadSinglePayload(path ledger.Path) *ledger.Payload
- func (mt *MTrie) RootHash() ledger.RootHash
- func (mt *MTrie) RootNode() *node.Node
- func (mt *MTrie) String() string
- func (mt *MTrie) UnsafeProofs(paths []ledger.Path) *ledger.TrieBatchProof
- func (mt *MTrie) UnsafeRead(paths []ledger.Path) []*ledger.Payload
- func (mt *MTrie) UnsafeValueSizes(paths []ledger.Path) []int
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).
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 NewTrieWithUpdatedRegisters ¶
func NewTrieWithUpdatedRegisters( parentTrie *MTrie, updatedPaths []ledger.Path, updatedPayloads []ledger.Payload, 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 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. CAUTION: MTrie expects that for a specific path, the payload's key never changes. 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) AllocatedRegSize ¶ added in v0.25.2
AllocatedRegSize returns the size (number of bytes) 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) ReadSinglePayload ¶ added in v0.26.2
ReadSinglePayload reads and returns a payload for a single path.
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 ¶
func (mt *MTrie) UnsafeProofs(paths []ledger.Path) *ledger.TrieBatchProof
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 ¶
UnsafeRead reads 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
func (*MTrie) UnsafeValueSizes ¶ added in v0.23.9
UnsafeValueSizes returns payload value sizes for the given paths. UNSAFE: requires _all_ paths to have a length of mt.Height bits. CAUTION: while getting payload value sizes, `paths` is permuted IN-PLACE for optimized processing. Return:
- `sizes` []int For each path, the corresponding payload value size is written into sizes. AFTER the size operation completes, the order of `path` and `sizes` are such that for `path[i]` the corresponding register value size is referenced by `sizes[i]`.
TODO move consistency checks from Forest into Trie to obtain a safe, self-contained API
Source Files