flattener

package
v0.10.1-collection-pat... Latest Latest
Warning

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

Go to latest
Published: Oct 28, 2020 License: AGPL-3.0 Imports: 5 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func RebuildNodes

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

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

Types

type FlattenedForest

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

FlattenedForest represents an MForest 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.MForest) (*FlattenedForest, error)

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

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
	Key       []byte
	Value     []byte
	HashValue []byte
	MaxDepth  uint16
	RegCount  uint64
}

type StorableTrie

type StorableTrie struct {
	RootIndex uint64
	RootHash  []byte
}

StorableTrie is a data structure for storing trie

Jump to

Keyboard shortcuts

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