trie

package
v0.9.0 Latest Latest
Warning

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

Go to latest
Published: Mar 1, 2024 License: LGPL-3.0 Imports: 13 Imported by: 2

Documentation

Index

Constants

View Source
const (
	// NoMaxInlineValueSize is the numeric representation used to indicate that there is no max value size.
	NoMaxInlineValueSize = math.MaxInt
	// V1MaxInlineValueSize is the maximum size of a value to be hashed in state trie version 1.
	V1MaxInlineValueSize = 32
)
View Source
const DefaultStateVersion = V1

DefaultStateVersion sets the state version we should use as default See https://github.com/paritytech/substrate/blob/5e76587825b9a9d52d8cb02ba38828adf606157b/primitives/storage/src/lib.rs#L435-L439

Variables

View Source
var ChildStorageKeyPrefix = []byte(":child_storage:default:")

ChildStorageKeyPrefix is the prefix for all child storage keys

View Source
var EmptyHash = common.MustBlake2bHash([]byte{0})

EmptyHash is the empty trie hash.

View Source
var ErrChildTrieDoesNotExist = errors.New("child trie does not exist")
View Source
var ErrParseVersion = errors.New("parsing version failed")

ErrParseVersion is returned when parsing a state trie version fails.

View Source
var NoVersion = TrieLayout(math.MaxUint8)

Functions

func GetFromDB

func GetFromDB(db db.DBGetter, rootHash common.Hash, key []byte) (
	value []byte, err error)

GetFromDB retrieves a value at the given key from the trie using the database. It recursively descends into the trie using the database starting from the root node until it reaches the node with the given key. It then reads the value from the database.

func PopulateNodeHashes

func PopulateNodeHashes(n *Node, nodeHashes map[common.Hash]struct{})

PopulateNodeHashes writes the node hash values of the node given and of all its descendant nodes as keys to the nodeHashes map. It is assumed the node and its descendant nodes have their Merkle value already computed.

Types

type DeltaMerger

type DeltaMerger interface {
	MergeWith(deltas tracking.Getter)
}

DeltaMerger merges the given deltas into the current deltas.

type DeltaRecorder

type DeltaRecorder interface {
	RecordDeleted(nodeHash common.Hash)
}

DeltaRecorder records deltas done in a ongoing trie operation.

type Deltas

type Deltas interface {
	DeltaMerger
	tracking.Getter
	DeltaRecorder
	DeepCopy() (deepCopy *tracking.Deltas)
}

Deltas is the interface for the trie local deltas since the last snapshot.

type Entries

type Entries []Entry

Entries is a list of entry used to build a trie

type Entry

type Entry struct{ Key, Value []byte }

Entry is a key-value pair used to build a trie

type NewBatcher

type NewBatcher interface {
	NewBatch() database.Batch
}

NewBatcher creates a new database batch.

type Node

type Node = node.Node

Node is a node in the trie and can be a leaf or a branch.

type Trie

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

Trie is a base 16 modified Merkle Patricia trie.

func LoadFromMap

func LoadFromMap(data map[string]string, version TrieLayout) (trie Trie, err error)

LoadFromMap loads the given data mapping of key to value into a new empty trie. The keys are in hexadecimal little Endian encoding and the values are hexadecimal encoded.

func NewEmptyTrie

func NewEmptyTrie() *Trie

NewEmptyTrie creates a trie with a nil root

func NewTrie

func NewTrie(root *Node, db db.Database) *Trie

NewTrie creates a trie with an existing root node

func (*Trie) ClearFromChild

func (t *Trie) ClearFromChild(keyToChild, key []byte) error

ClearFromChild removes the child storage entry

func (*Trie) ClearPrefix

func (t *Trie) ClearPrefix(prefixLE []byte) (err error)

ClearPrefix deletes all nodes in the trie for which the key contains the prefix given in little Endian format.

func (*Trie) ClearPrefixLimit

func (t *Trie) ClearPrefixLimit(prefixLE []byte, limit uint32) (
	deleted uint32, allDeleted bool, err error)

ClearPrefixLimit deletes the keys having the prefix given in little Endian format for up to `limit` keys. It returns the number of deleted keys and a boolean indicating if all keys with the prefix were deleted within the limit.

func (*Trie) DeepCopy

func (t *Trie) DeepCopy() (trieCopy *Trie)

DeepCopy deep copies the trie and returns the copy. Note this method is meant to be used in tests and should not be used in production since it's rather inefficient compared to the copy on write mechanism achieved through snapshots.

func (*Trie) Delete

func (t *Trie) Delete(keyLE []byte) (err error)

Delete removes the node of the trie with the key matching the key given in little Endian format. If no node is found at this key, nothing is deleted.

func (*Trie) DeleteChild

func (t *Trie) DeleteChild(keyToChild []byte) (err error)

DeleteChild deletes the child storage trie

func (*Trie) Entries

func (t *Trie) Entries() (keyValueMap map[string][]byte)

Entries returns all the key-value pairs in the trie as a map of keys to values where the keys are encoded in Little Endian.

func (*Trie) Equal

func (t *Trie) Equal(other *Trie) bool

Equal is to compare one trie with other, this method will ignore the shared db instance

func (*Trie) GenesisBlock

func (t *Trie) GenesisBlock() (genesisHeader types.Header, err error)

GenesisBlock creates a genesis block from the trie.

func (*Trie) Get

func (t *Trie) Get(keyLE []byte) (value []byte)

Get returns the value in the node of the trie which matches its key with the key given. Note the key argument is given in little Endian format.

func (*Trie) GetChangedNodeHashes

func (t *Trie) GetChangedNodeHashes() (inserted, deleted map[common.Hash]struct{}, err error)

GetChangedNodeHashes returns the two sets of hashes for all nodes inserted and deleted in the state trie since the last snapshot. Returned inserted map is safe for mutation, but deleted is not safe for mutation.

func (*Trie) GetChild

func (t *Trie) GetChild(keyToChild []byte) (*Trie, error)

GetChild returns the child trie at key :child_storage:[keyToChild]

func (*Trie) GetFromChild

func (t *Trie) GetFromChild(keyToChild, key []byte) ([]byte, error)

GetFromChild retrieves a key-value pair from the child trie located in the main trie at key :child_storage:[keyToChild]

func (*Trie) GetKeysWithPrefix

func (t *Trie) GetKeysWithPrefix(prefixLE []byte) (keysLE [][]byte)

GetKeysWithPrefix returns all keys in little Endian format from nodes in the trie that have the given little Endian formatted prefix in their key.

func (*Trie) Hash

func (t *Trie) Hash() (rootHash common.Hash, err error)

Hash returns the hashed root of the trie.

func (*Trie) Load

func (t *Trie) Load(db db.DBGetter, rootHash common.Hash) error

Load reconstructs the trie from the database from the given root hash. It is used when restarting the node to load the current state trie.

func (*Trie) MustHash

func (t *Trie) MustHash() common.Hash

MustHash returns the hashed root of the trie. It panics if it fails to hash the root node.

func (*Trie) NextKey

func (t *Trie) NextKey(keyLE []byte) (nextKeyLE []byte)

NextKey returns the next key in the trie in lexicographic order. It returns nil if no next key is found.

func (*Trie) Put

func (t *Trie) Put(keyLE, value []byte) (err error)

Put inserts a value into the trie at the key specified in little Endian format.

func (*Trie) PutIntoChild

func (t *Trie) PutIntoChild(keyToChild, key, value []byte) error

PutIntoChild puts a key-value pair into the child trie located in the main trie at key :child_storage:[keyToChild]

func (*Trie) RootNode

func (t *Trie) RootNode() *Node

RootNode returns a copy of the root node of the trie.

func (*Trie) SetChild

func (t *Trie) SetChild(keyToChild []byte, child *Trie) error

SetChild inserts a child trie into the main trie at key :child_storage:[keyToChild] A child trie is added as a node (K, V) in the main trie. K is the child storage key associated to the child trie, and V is the root hash of the child trie.

func (*Trie) SetVersion

func (t *Trie) SetVersion(v TrieLayout)

func (*Trie) Snapshot

func (t *Trie) Snapshot() (newTrie *Trie)

Snapshot creates a copy of the trie. Note it does not deep copy the trie, but will copy on write as modifications are done on this new trie. It does a snapshot of all child tries as well, and resets the set of deleted hashes.

func (*Trie) String

func (t *Trie) String() string

String returns the trie stringified through pre-order traversal

func (*Trie) WriteDirty

func (t *Trie) WriteDirty(db NewBatcher) error

WriteDirty writes all dirty nodes to the database and sets them to clean

type TrieLayout

type TrieLayout uint8

TrieLayout is the state trie version which dictates how a Merkle root should be constructed. It is defined in https://spec.polkadot.network/#defn-state-version

const (
	// V0 is the state trie version 0 where the values of the keys are
	// inserted into the trie directly.
	// TODO set to iota once CI passes
	V0 TrieLayout = iota
	V1
)

func ParseVersion

func ParseVersion[T string | uint8](v T) (version TrieLayout, err error)

ParseVersion parses a state trie version string.

func (TrieLayout) Hash

func (v TrieLayout) Hash(t *Trie) (common.Hash, error)

Hash returns the root hash of the trie built using the given entries

func (TrieLayout) MaxInlineValue

func (v TrieLayout) MaxInlineValue() int

MaxInlineValue returns the maximum size of a value to be inlined in the trie node

func (TrieLayout) MustHash

func (v TrieLayout) MustHash(t Trie) common.Hash

MustHash returns the root hash of the trie built using the given entries or panics if it fails

func (TrieLayout) Root

func (v TrieLayout) Root(entries Entries) (common.Hash, error)

Root returns the root hash of the trie built using the given entries

func (TrieLayout) String

func (v TrieLayout) String() string

String returns a string representation of trie version

Directories

Path Synopsis
Package node defines the `Node` structure with methods to be used in the modified Merkle-Patricia Radix-16 trie.
Package node defines the `Node` structure with methods to be used in the modified Merkle-Patricia Radix-16 trie.

Jump to

Keyboard shortcuts

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