trie

package
v0.8.0 Latest Latest
Warning

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

 Go to latest Published: Dec 11, 2023 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 added in v0.3.0 

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 added in v0.7.0 

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 DeltaDeletedGetter added in v0.8.0 

type DeltaDeletedGetter interface {
	Deleted() (nodeHashes map[common.Hash]struct{})
}

DeltaDeletedGetter returns the deleted node hashes recorded so far.

type DeltaMerger added in v0.8.0 

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

DeltaMerger merges the given deltas into the current deltas.

type DeltaRecorder added in v0.8.0 

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

DeltaRecorder records deltas done in a ongoing trie operation.

type Deltas added in v0.8.0 

type Deltas interface {
	DeltaMerger
	DeltaDeletedGetter
}

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

type Entries added in v0.8.0 

type Entries []Entry

Entries is a list of entry used to build a trie

type Entry added in v0.8.0 

type Entry struct{ Key, Value []byte }

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

type NewBatcher added in v0.8.0 

type NewBatcher interface {
	NewBatch() database.Batch
}

NewBatcher creates a new database batch.

type Node added in v0.7.0 

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 added in v0.7.0 

func LoadFromMap(data map[string]string) (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 added in v0.2.0 

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

ClearFromChild removes the child storage entry

func (*Trie) ClearPrefix added in v0.3.0 

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 added in v0.7.0 

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 added in v0.2.0 

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 added in v0.3.1 

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 added in v0.8.0 

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 added in v0.7.0 

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 added in v0.7.0 

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 added in v0.2.0 

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(maxInlineValue int) (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 added in v0.2.0 

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

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

func (*Trie) NextKey added in v0.2.0 

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 added in v0.8.0 

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) Snapshot added in v0.3.0 

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 added in v0.3.0 

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

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

type TrieLayout added in v0.8.0 

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 added in v0.7.0 

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

ParseVersion parses a state trie version string.

func (TrieLayout) Hash added in v0.8.0 

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 added in v0.8.0 

func (v TrieLayout) MaxInlineValue() int

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

func (TrieLayout) MustHash added in v0.8.0 

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 added in v0.8.0 

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 added in v0.8.0 

func (v TrieLayout) String() string

String returns a string representation of trie version

Source Files

View all Source files

Directories

Path Synopsis

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.