node

Documentation

Index

• type Node
  • func NewEmptyTreeRoot(height int) *Node
  • func NewInterimNode(height int, lchild, rchild *Node) *Node
  • func NewLeaf(key, value []byte, height int) *Node
  • func NewNode(height int, lchild, rchild *Node, key, value, hashValue []byte, ...) *Node
  • func (n *Node) DeepCopy() *Node
  • func (n *Node) Equals(o *Node) bool
  • func (n Node) FmtStr(prefix string, path string) string
  • func (n *Node) Hash() []byte
  • func (n *Node) Height() int
  • func (n *Node) IsLeaf() bool
  • func (n *Node) Key() []byte
  • func (n *Node) LeftChild() *Node
  • func (n *Node) MaxDepth() uint16
  • func (n *Node) RegCount() uint64
  • func (n *Node) RigthChild() *Node
  • func (n *Node) Value() []byte

Types

type Node

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

Node of a RamSafe MTrie.

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 three different types of nodes:

• LEAF node: fully defined by key-value pair and a height hash is pre-computed, lChild and rChild are nil)
• INTERIOR node: at least one of lChild or rChild is not nil. Height, and Hash value are set; (key-value is nil)
• ROOT of empty trie node: this is a special case, where the node has no children, and no key-value

Currently, we represent both data structures by Node instances

Nodes are supposed to be used in READ-ONLY fashion. However, for performance reasons, we not not copy read. TODO: optimized data structures might be able to reduce memory consumption

func NewEmptyTreeRoot

func NewEmptyTreeRoot(height int) *Node

NewLeaf creates a compact leaf Node UNCHECKED requirement: height must be non-negative

func NewInterimNode

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

newNode creates a new Node with the provided value and no children. UNCHECKED requirement: lchild.height and rchild.height must be smaller than height

func NewLeaf

func NewLeaf(key, value []byte, height int) *Node

NewLeaf creates a compact leaf Node UNCHECKED requirement: height must be non-negative

func NewNode

func NewNode(height int, lchild, rchild *Node, key, value, hashValue []byte, 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) DeepCopy

func (n *Node) DeepCopy() *Node

DeepCopy returns a deep copy of the Node (including deep copy of children) TODO: potentially can be removed

func (*Node) Equals

func (n *Node) Equals(o *Node) bool

Equals compares two nodes and all subsequent children this is an expensive call and should only be used for limited cases (e.g. testing) TODO: potentially can be removed

func (Node) FmtStr

func (n Node) FmtStr(prefix string, path string) string

FmtStr provides formatted string representation of the Node and sub tree

func (*Node) Hash

func (n *Node) Hash() []byte

Height 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) Key

func (n *Node) Key() []byte

Key returns the the Node's register key. The present node is a LEAF node, if and only if the returned key is NOT NULL. Do NOT MODIFY returned slices!

func (*Node) LeftChild

func (n *Node) LeftChild() *Node

LeftChild returns the the Node's left child. Only INTERIOR 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) RegCount

func (n *Node) RegCount() uint64

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

func (*Node) RigthChild

func (n *Node) RigthChild() *Node

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

func (*Node) Value

func (n *Node) Value() []byte

Value returns the the Node's register values. The present node is a LEAF node, if and only if the returned value is NOT NULL. Do NOT MODIFY returned slices!