flattener

package
v0.10.1-consensus-desr... Latest Latest
Warning

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

Go to latest
Published: Oct 30, 2020 License: AGPL-3.0 Imports: 9 Imported by: 1

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func EncodeStorableNode

func EncodeStorableNode(storableNode *StorableNode) []byte

EncodeStorableNode encodes StorableNode

func EncodeStorableTrie

func EncodeStorableTrie(storableTrie *StorableTrie) []byte

EncodeStorableTrie encodes StorableTrie

func RebuildNodes

func RebuildNodes(storableNodes []*StorableNode) ([]*node.Node, error)

RebuildNodes generates a list of Nodes from a sequence of StorableNodes. The sequence must obey the DESCENDANTS-FIRST-RELATIONSHIP

func RebuildTries

func RebuildTries(flatForest *FlattenedForest) ([]*trie.MTrie, error)

RebuildTries construct a forest from a storable FlattenedForest

Types

type FlattenedForest

type FlattenedForest struct {
	Nodes []*StorableNode
	Tries []*StorableTrie
}

FlattenedForest represents an Forest as a flattened data structure. Specifically it consists of :

  • a list of storable nodes, where references to nodes are replaced by index in the slice
  • and a list of storable tries, each referencing their respective root node by index.

0 is a special index, meaning nil, but is included in this list for ease of use and removing would make it necessary to constantly add/subtract indexes

As an important property, the nodes are listed in an order which satisfies Descendents-First-Relationship. 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 FlattenForest

func FlattenForest(f *mtrie.Forest) (*FlattenedForest, error)

FlattenForest returns forest FlattenedForest, which contains all nodes and tries of the Forest.

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(mTrie *trie.MTrie) *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.

func (*NodeIterator) Next

func (i *NodeIterator) Next() bool

func (*NodeIterator) Value

func (i *NodeIterator) Value() *node.Node

type StorableNode

type StorableNode struct {
	LIndex     uint64
	RIndex     uint64
	Height     uint16 // Height where the node is at
	Path       []byte // path
	EncPayload []byte // encoded data for payload
	HashValue  []byte
	MaxDepth   uint16
	RegCount   uint64
}

func ReadStorableNode

func ReadStorableNode(reader io.Reader) (*StorableNode, error)

ReadStorableNode reads a storable node from io

type StorableTrie

type StorableTrie struct {
	RootIndex uint64
	RootHash  []byte
}

StorableTrie is a data structure for storing trie

func ReadStorableTrie

func ReadStorableTrie(reader io.Reader) (*StorableTrie, error)

ReadStorableTrie reads a storable trie from io

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL