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: 0

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

Source Files

View all Source files

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
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.