Class MerkleTrie

An ITrie implementation implemented Merkle Patricia Trie.

Inheritance

Object

MerkleTrie

Implements

ITrie

Inherited Members

Object.Equals(Object)

Object.Equals(Object, Object)

Object.GetHashCode()

System.Object.GetType()

Object.MemberwiseClone()

Object.ReferenceEquals(Object, Object)

System.Object.ToString()

Namespace: Libplanet.Store.Trie

Assembly: Libplanet.Store.dll

Syntax

public class MerkleTrie : ITrie

Constructors

MerkleTrie(IKeyValueStore, HashDigest<SHA256>, HashNodeCache)

An ITrie implementation.

Declaration

public MerkleTrie(IKeyValueStore keyValueStore, HashDigest<SHA256> rootHash, HashNodeCache cache = null)

Parameters

Type	Name	Description
IKeyValueStore	keyValueStore	The IKeyValueStore storage to store nodes.
HashDigest<SHA256>	rootHash	The root Hash of MerkleTrie.
HashNodeCache	cache	The HashNodeCache to use as cache.

MerkleTrie(IKeyValueStore, INode, HashNodeCache)

An ITrie implementation.

Declaration

public MerkleTrie(IKeyValueStore keyValueStore, INode root = null, HashNodeCache cache = null)

Parameters

Type	Name	Description
IKeyValueStore	keyValueStore	The IKeyValueStore storage to store nodes.
INode	root	The root node of MerkleTrie. If it is null, it will be treated like empty trie.
HashNodeCache	cache	The HashNodeCache to use as cache.

Fields

EmptyRootHash

An ITrie implementation implemented Merkle Patricia Trie.

Declaration

public static readonly HashDigest<SHA256> EmptyRootHash

Field Value

Type	Description
HashDigest<SHA256>

Properties

Hash

The state root hash of the trie.

Declaration

public HashDigest<SHA256> Hash { get; }

Property Value

Type	Description
HashDigest<SHA256>

Remarks

If Root is null, this still gives a unique HashDigest<T> value corresponding to null that is never recorded.

See Also

Root

Recorded

Whether Root is recorded in the store.

Declaration

public bool Recorded { get; }

Property Value

Type	Description
System.Boolean

Remarks

A Root that is null is always considered as recorded.

Root

The root of the ITrie. This is null if and only if the ITrie is empty. That is, this is never a "hashed node" of a null root.

Declaration

public INode Root { get; }

Property Value

Type	Description
INode

See Also

Hash

Methods

Diff(ITrie)

Lists every non-null Bencodex.Types.IValue that is different from the one stored in other given any KeyBytes path.

Declaration

public IEnumerable<(KeyBytes Path, IValue TargetValue, IValue SourceValue)> Diff(ITrie other)

Parameters

Type	Name	Description
ITrie	other	The other MerkleTrie to compare to.

Returns

Type	Description
IEnumerable<(T1 Item1, T2 Item2, T3 Item3)<KeyBytes, Bencodex.Types.IValue, Bencodex.Types.IValue>>	A list of tuples where each tuple consists of the path where the difference occurred, the "old" value from other and the current "new" value.

Remarks

This operation has the following properties:

• This operation is non-symmetric. That is, in general, trieA.Diff(trieB) and trieB.Diff(trieA) are not the same.
• Values existing in other but not in the source instance, considered as null in the source, are not included in the result.

Exceptions

Type	Condition
InvalidTrieNodeException	Thrown when the method fails to traverse the ITrie.

Get(KeyBytes)

Gets the values stored with key in Set(in KeyBytes, IValue).

Declaration

public IValue Get(KeyBytes key)

Parameters

Type	Name	Description
KeyBytes	key	The key used in Set(in KeyBytes, IValue) to store a value.

Returns

Type	Description
Bencodex.Types.IValue	The value associated to the specified key. Absent value is represented as null.

Get(IReadOnlyList<KeyBytes>)

Gets the values stored with keys in Set(in KeyBytes, IValue).

Declaration

public IReadOnlyList<IValue> Get(IReadOnlyList<KeyBytes> keys)

Parameters

Type	Name	Description
IReadOnlyList<KeyBytes>	keys	The keys used in Set(in KeyBytes, IValue) to store a value.

Returns

Type	Description
IReadOnlyList<Bencodex.Types.IValue>	The values associated to the specified keys. The associated values are ordered in the same way to the corresponding keys. Absent values are represented as null.

GetNode(Nibbles)

Gets the first node encountered at nibbles when traversing down from Root.

Declaration

public INode GetNode(Nibbles nibbles)

Parameters

Type	Name	Description
Nibbles	nibbles	The path to check.

Returns

Type	Description
INode	A node at nibbles, if any. Otherwise null.

Remarks

There may be more than one INode at nibbles. For instance, a FullNode, a ValueNode as the value of the aforementioned FullNode, and up to two additional HashNodes is possible.

As such, for two equivalent ITries, Libplanet.Store.Tries that would have the same committed Hashes, this may return different types of INode depending on the actual underlying "structure". However, returned INodes for such ITries are equivalent as sub-ITries.

Exceptions

Type	Condition
InvalidTrieNodeException	Thrown when an unknown type of INode is encountered while traversing to the given path.

IterateNodes()

Iterates and every stored INode along with its respective path in Nibbles.

Declaration

public IEnumerable<(Nibbles Path, INode Node)> IterateNodes()

Returns

Type	Description
IEnumerable<(T1 Item1, T2 Item2)<Nibbles, INode>>	An IEnumerable<T> of all INodes in no particular order.

Remarks

This is a very heavy operation.

IterateValues()

Iterates and every stored Bencodex.Types.IValue along with its respective path in KeyBytes.

Declaration

public IEnumerable<(KeyBytes Path, IValue Value)> IterateValues()

Returns

Type	Description
IEnumerable<(T1 Item1, T2 Item2)<KeyBytes, Bencodex.Types.IValue>>	An IEnumerable<T> of all Bencodex.Types.IValues in no particular order.

Remarks

This is a very heavy operation.

Remove(in KeyBytes)

Removes the value at the path corresponding to given key in memory.

Declaration

public ITrie Remove(in KeyBytes key)

Parameters

Type	Name	Description
KeyBytes	key	The unique key to associate with the value.

Returns

Type	Description
ITrie	Returns new updated ITrie.

Remarks

This should not actually remove anything from storage. The removal of the value at the marked path given by key is actually recorded to storage when Commit(ITrie) is called. Regardless, there is actually no removal of any value from storage even when Commit(ITrie) is called.

See Also

Commit(ITrie)

Set(in KeyBytes, IValue)

Stores the value at the path corresponding to given key in memory.

Declaration

public ITrie Set(in KeyBytes key, IValue value)

Parameters

Type	Name	Description
KeyBytes	key	The unique key to associate with the value.
Bencodex.Types.IValue	value	The value to store.

Returns

Type	Description
ITrie	Returns new updated ITrie.

Remarks

This should not actually write anything to storage. Stored value is actually written to storage when Commit(ITrie) is called.

Exceptions

Type	Condition
System.ArgumentNullException	Thrown when the given value is null.

See Also

Commit(ITrie)

Implements

ITrie

Extension Methods

TrieExtensions.GetMetadata(ITrie)

TrieExtensions.SetMetadata(ITrie, IValue)

TrieExtensions.SetMetadata(ITrie, TrieMetadata)