flattener

package
v0.33.20-find-mismatch... Latest Latest
Warning

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

Go to latest
Published: May 9, 2024 License: AGPL-3.0 Imports: 9 Imported by: 1

Documentation

Index

Constants

View Source
const (
	EncodedTrieSize = encodedTrieSize
)

Variables

This section is empty.

Functions

func EncodeNode added in v0.25.0

func EncodeNode(n *node.Node, lchildIndex uint64, rchildIndex uint64, scratch []byte) []byte

EncodeNode encodes node. Scratch buffer is used to avoid allocs. WARNING: The returned buffer is likely to share the same underlying array as the scratch buffer. Caller is responsible for copying or using returned buffer before scratch buffer is used again.

func EncodeTrie added in v0.25.0

func EncodeTrie(trie *trie.MTrie, rootIndex uint64, scratch []byte) []byte

EncodeTrie encodes trie in the following format: - root node index (8 byte) - allocated reg count (8 byte) - allocated reg size (8 byte) - root node hash (32 bytes) Scratch buffer is used to avoid allocs. WARNING: The returned buffer is likely to share the same underlying array as the scratch buffer. Caller is responsible for copying or using returned buffer before scratch buffer is used again.

func ReadNode added in v0.25.0

func ReadNode(reader io.Reader, scratch []byte, getNode func(nodeIndex uint64) (*node.Node, error)) (*node.Node, error)

ReadNode reconstructs a node from data read from reader. Scratch buffer is used to avoid allocs. It should be used directly instead of using append. This function uses len(scratch) and ignores cap(scratch), so any extra capacity will not be utilized. If len(scratch) < 1024, then a new buffer will be allocated and used.

func ReadNodeFromCheckpointV3AndEarlier added in v0.25.0

func ReadNodeFromCheckpointV3AndEarlier(reader io.Reader, getNode getNodeFunc) (*node.Node, uint64, uint64, error)

ReadNodeFromCheckpointV3AndEarlier returns a node recontructed from data in checkpoint v3 and earlier versions. It also returns node's regCount and regSize. Encoded node in checkpoint v3 and earlier is in the following format: - version (2 bytes) - height (2 bytes) - lindex (8 bytes) - rindex (8 bytes) - max depth (2 bytes) - reg count (8 bytes) - path (2 bytes + 32 bytes) - payload (4 bytes + n bytes) - hash (2 bytes + 32 bytes)

func ReadNodeFromCheckpointV4 added in v0.25.2

func ReadNodeFromCheckpointV4(reader io.Reader, scratch []byte, getNode getNodeFunc) (*node.Node, uint64, uint64, error)

ReadNodeFromCheckpointV4 reconstructs a node from data read from reader. Scratch buffer is used to avoid allocs. It should be used directly instead of using append. This function uses len(scratch) and ignores cap(scratch), so any extra capacity will not be utilized. If len(scratch) < 1024, then a new buffer will be allocated and used. Leaf node is encoded in the following format: - node type (1 byte) - height (2 bytes) - max depth (2 bytes) - reg count (8 bytes) - hash (32 bytes) - path (32 bytes) - payload (4 bytes + n bytes)

func ReadTrie added in v0.25.0

func ReadTrie(reader io.Reader, scratch []byte, getNode func(nodeIndex uint64) (*node.Node, error)) (*trie.MTrie, error)

ReadTrie reconstructs a trie from data read from reader.

func ReadTrieFromCheckpointV3AndEarlier added in v0.25.0

func ReadTrieFromCheckpointV3AndEarlier(reader io.Reader, getNode getNodeFunc) (*trie.MTrie, error)

ReadTrieFromCheckpointV3AndEarlier reconstructs a trie from data in checkpoint v3 and earlier versions. Encoded trie in checkpoint v3 and earlier is in the following format: - version (2 bytes) - root node index (8 bytes) - root node hash (2 bytes + 32 bytes)

func ReadTrieFromCheckpointV4 added in v0.25.2

func ReadTrieFromCheckpointV4(reader io.Reader, scratch []byte, getNode getNodeFunc) (*trie.MTrie, error)

ReadTrieFromCheckpointV4 reconstructs a trie from data read from reader.

Types

type EncodedTrie added in v0.32.2

type EncodedTrie struct {
	RootIndex uint64
	RegCount  uint64
	RegSize   uint64
	RootHash  hash.Hash
}

func ReadEncodedTrie added in v0.32.2

func ReadEncodedTrie(reader io.Reader, scratch []byte) (EncodedTrie, error)

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(n *node.Node) *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. NodeIterator created by NewNodeIterator is safe for concurrent use because visitedNodes is always nil in this case.

func NewUniqueNodeIterator added in v0.25.0

func NewUniqueNodeIterator(n *node.Node, visitedNodes map[*node.Node]uint64) *NodeIterator

NewUniqueNodeIterator returns a node NodeIterator, which iterates through all unique nodes that weren't visited. This should be used for forest node iteration to avoid repeatedly traversing shared sub-tries. 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. WARNING: visitedNodes is not safe for concurrent use.

func (*NodeIterator) Next

func (i *NodeIterator) Next() bool

Next moves the cursor to the next node in order for Value method to return it. It returns true if there is a next node to iterate, in which case the Value method will return the node. It returns false if there is no more node to iterate, in which case the Value method will return nil.

func (*NodeIterator) Value

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

Value will return the current node at the cursor. Note: you should call Next() before calling

Jump to

Keyboard shortcuts

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