node

Documentation

Index

• type Node
  • func NewInterimNode(height int, lchild, rchild *Node) *Node
  • func NewLeaf(path ledger.Path, payload *ledger.Payload, height int) *Node
  • func NewNode(height int, lchild, rchild *Node, path ledger.Path, payload *ledger.Payload, ...) *Node
  • func (n *Node) AllPayloads() []ledger.Payload
  • func (n *Node) Compactify() *Node
  • func (n *Node) FmtStr(prefix string, subpath string) string
  • func (n *Node) Hash() hash.Hash
  • func (n *Node) Height() int
  • func (n *Node) IsLeaf() bool
  • func (n *Node) LeftChild() *Node
  • func (n *Node) MaxDepth() uint16
  • func (n *Node) Path() *ledger.Path
  • func (n *Node) Payload() *ledger.Payload
  • func (n *Node) RegCount() uint64
  • func (n *Node) RightChild() *Node
  • func (n *Node) VerifyCachedHash() bool

Types

type Node

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

Node defines an Mtrie node

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.

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 payload.
• LEAF node: has _no_ children.

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 NewInterimNode

func NewInterimNode(height int, lchild, rchild *Node) *Node

NewInterimNode creates a new Node with the provided value and no children. UNCHECKED requirement: lchild.height and rchild.height must be smaller than height UNCHECKED requirement: if lchild != nil then height = lchild.height + 1, and same for rchild

func NewLeaf

func NewLeaf(path ledger.Path,
	payload *ledger.Payload,
	height int) *Node

NewLeaf creates a compact leaf Node. UNCHECKED requirement: height must be non-negative UNCHECKED requirement: payload is non nil UNCHECKED requirement: payload should be deep copied if received from external sources

func NewNode

func NewNode(height int,
	lchild,
	rchild *Node,
	path ledger.Path,
	payload *ledger.Payload,
	hashValue hash.Hash,
	maxDepth uint16,
	regCount uint64) *Node

NewNode creates a new Node. UNCHECKED requirement: combination of values must conform to a valid node type (see documentation of `Node` for details)

func (*Node) AllPayloads

func (n *Node) AllPayloads() []ledger.Payload

AllPayloads returns the payload of this node and all payloads of the subtrie

func (*Node) Compactify

func (n *Node) Compactify() *Node

Compactify checks if the subtree represented by an interim-node can be simplified to its most concise representation by looking only at its direct children. The compactified representation of a default node is `nil`. For a node that only has a _single_ child that is itself a leaf, this method returns a new, fully compactified leaf. Returns:

• n: if the node cannot be compactified, we return the original node `n`
• cn: if the node can be compactified, where cn is a newly created compactified leaf

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 hash value. Do NOT MODIFY returned slice!

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) IsLeaf

func (n *Node) IsLeaf() bool

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

func (*Node) LeftChild

func (n *Node) LeftChild() *Node

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

func (*Node) MaxDepth

func (n *Node) MaxDepth() uint16

MaxDepth returns the longest path from this node to compacted leafs in the subtree. in contrast to the Height, this value captures compactness of the subtrie.

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) Payload

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

Payload returns the the Node's payload. Do NOT MODIFY returned slices!

func (*Node) RegCount

func (n *Node) RegCount() uint64

RegCount returns number of registers allocated in the subtrie of this node.

func (*Node) RightChild

func (n *Node) RightChild() *Node

RightChild returns the 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 the hash of a node is valid