Crate reference_trie

Reference implementation of a streamer.

Modules

nibble_ops	Utility methods to work on radix 16 nibble.
node
proof	Generation and verification of compact proofs for Merkle-Patricia tries.

Structs

AllowEmptyLayout	Trie that allows empty values
Bitmap	Children bitmap codec for radix 16 trie.
ExtensionLayout	Trie layout using extension nodes.
GenericNoExtensionLayout	Trie layout without extension nodes, allowing generic hasher.
NibbleSlice	Nibble-orientated view onto byte-slice, allowing nibble-precision offsets.
NibbleVec	Owning, nibble-oriented byte vector. Counterpart to NibbleSlice. Nibbles are always left aligned, so making a NibbleVec from a NibbleSlice can get costy.
Record	A record of a visited node.
Recorder	Records trie nodes as they pass it.
ReferenceNodeCodec	Simple reference implementation of a NodeCodec.
ReferenceNodeCodecNoExt	Simple reference implementation of a NodeCodec. Even if implementation follows initial specification of https://github.com/w3f/polkadot-re-spec/issues/8, this may not follow it in the future, it is mainly the testing codec without extension node.
ReferenceTrieStream	Reference implementation of a TrieStream with extension nodes.
ReferenceTrieStreamNoExt	Reference implementation of a TrieStream without extension.
TrieDB	A Trie implementation using a generic HashDB backing database, a Hasher implementation to generate keys and a NodeCodec implementation to encode/decode the nodes.
TrieDBIterator	Iterator for going through all values in the trie in pre-order traversal order.
TrieDBMut	A Trie implementation using a generic HashDB backing database.
TrieDBNodeIterator	Iterator for going through all nodes in the trie in pre-order traversal order.

Enums

TrieError

Trie Errors.

Traits

NodeCodec	Trait for trie node encoding/decoding.
Trie	A key-value datastore implemented as a database-backed modified Merkle tree.
TrieConfiguration	This trait associates a trie definition with preferred methods. It also contains own default implementations and can be used to allow switching implementation.
TrieIterator	A trie iterator that also supports random access (seek()).
TrieLayout	Trait with definition of trie layout. Contains all associated trait needed for a trie definition or implementation.
TrieMut	A key-value datastore implemented as a database-backed modified Merkle tree.
TrieStream	Byte-stream oriented trait for constructing closed-form tries.

Functions

calc_root	Trie builder root calculation utility.
calc_root_build	Trie builder trie building utility.
calc_root_build_no_extension	Trie builder trie building utility. This uses the variant without extension nodes.
calc_root_no_extension	Trie builder root calculation utility. This uses the variant without extension nodes.
compare_implementations	Compare trie builder and in memory trie.
compare_implementations_no_extension	Compare trie builder and in memory trie. This uses the variant without extension nodes.
compare_implementations_no_extension_unordered	compare_implementations_no_extension for unordered input (trie_root does ordering before running when trie_build expect correct ordering).
compare_no_extension_insert_remove	Testing utility that uses some periodic removal over its input test data.
compare_root	Compare trie builder and trie root implementations.
compare_unhashed	Compare trie builder and trie root unhashed implementations.
compare_unhashed_no_extension	Compare trie builder and trie root unhashed implementations. This uses the variant without extension nodes.
decode_compact	Reconstructs a partial trie DB from a compact representation. The encoding is a vector of mutated trie nodes with those child references omitted. The decode function reads them in order from the given slice, reconstructing the full nodes and inserting them into the given HashDB. It stops after fully constructing one partial trie and returns the root hash and the number of nodes read. If an error occurs during decoding, there are no guarantees about which entries were or were not added to the DB.
encode_compact	Generates a compact representation of the partial trie stored in the given DB. The encoding is a vector of mutated trie nodes with those child references omitted. The mutated trie nodes are listed in pre-order traversal order so that the full nodes can be efficiently reconstructed recursively.
reference_trie_root
reference_trie_root_no_extension

Type Definitions

NoExtensionLayout	Trie layout without extension nodes.
RefFatDB
RefFatDBMut
RefLookup
RefLookupNoExt
RefSecTrieDB
RefSecTrieDBMut
RefTrieDB
RefTrieDBMut
RefTrieDBMutAllowEmpty
RefTrieDBMutNoExt
RefTrieDBNoExt