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()

Object.GetType()

Object.MemberwiseClone()

Object.ReferenceEquals(Object, Object)

Object.ToString()

Namespace: Libplanet.Store.Trie

Assembly: Libplanet.Store.dll

Syntax

public class MerkleTrie : ITrie

Constructors

MerkleTrie(IKeyValueStore, HashDigest<SHA256>)

An ITrie implementation.

Declaration

public MerkleTrie(IKeyValueStore keyValueStore, HashDigest<SHA256> rootHash)

Parameters

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

MerkleTrie(IKeyValueStore, INode)

An ITrie implementation.

Declaration

public MerkleTrie(IKeyValueStore keyValueStore, INode root = 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.

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
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()

An ITrie implementation implemented Merkle Patricia Trie.

Declaration

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

Returns

Type	Description
IEnumerable<(T1 Item1, T2 Item2)<Nibbles, INode>>

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.

Set(in KeyBytes, IValue)

Stores the value to the node 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.

Exceptions

Type	Condition
ArgumentNullException	Thrown when the given value is null.

See Also

Commit(ITrie)

Implements

ITrie

Extension Methods

TrieExtensions.Set(ITrie, IImmutableDictionary<KeyBytes, IValue>)