Crate subtrie

Trie interface and implementation.

Re-exports

pub use self::recorder::Recorder;

pub use self::triedb::TrieDB;

pub use self::triedb::TrieDBBuilder;

pub use self::triedb::TrieDBIterator;

pub use self::triedb::TrieDBKeyIterator;

pub use self::triedbmut::Changenode;

pub use self::triedbmut::Changeset;

pub use self::triedbmut::ChildReference;

pub use self::triedbmut::NewChangesetNode;

pub use self::triedbmut::OwnedPrefix;

pub use self::triedbmut::TreeRefChangeset;

pub use self::triedbmut::TrieDBMut;

pub use self::triedbmut::TrieDBMutBuilder;

pub use self::triedbmut::Value;

Modules

mem_tree_db

Flat memory-based NodeDB implementation.

memory_db

Reference-counted memory-based NodeDB implementation.

nibble_ops

Utility methods to work on radix 16 nibble.

node

node_db

Database of byte-slices keyed to their hash.

proof

Generation and verification of compact proofs for Merkle-Patricia tries.

recorder

Trie query recorder.

trie_root

Generates trie root.

triedb

triedbmut

In-memory trie representation.

Structs

Bytes

A container for storing bytes.

BytesWeak

A weak reference of Bytes.

Lookup

Trie lookup helper object.

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.

TrieBuilder

Get trie root and insert visited node in a node_db. As for all ProcessEncodedNode implementation, it is only for full trie parsing (not existing trie).

TrieDBNodeDoubleEndedIterator

Double ended iterator for going through all nodes in the trie in pre-order traversal order.

TrieDBNodeIterator

Iterator for going through all nodes in the trie in pre-order traversal order.

TrieDBRawIterator

Iterator for going through all nodes in the trie in pre-order traversal order.

TrieRoot

Calculate the trie root of the trie.

TrieRootPrint

Calculate the trie root of the trie. Print a debug trace.

TrieRootUnhashed

Get the trie root node encoding.

Enums

CachedValue

A value as cached by the TrieCache.

MerkleValue

Either the hash or value of a node depending on its size.

RecordedForKey

Result of TrieRecorder::trie_nodes_recorded_for_key.

TrieAccess

Used to report the trie access to the TrieRecorder.

TrieError

Trie Errors.

TrieSpec

Trie types

Traits

Location

Trait alias for requirement of location with TrieLayout.

NodeCodec

Trait for trie node encoding/decoding. Uses a type parameter to allow registering positions without colling decode plan.

ProcessEncodedNode

Visitor trait to implement when using trie_visit.

Query

Description of what kind of query will be made to the trie.

Trie

A key-value datastore implemented as a database-backed modified Merkle tree.

TrieCache

A cache that can be used to speed-up certain operations when accessing the trie.

TrieConfiguration

This trait associates a trie definition with preferred methods. It also contains own default implementations and can be used to allow switching implementation.

TrieDoubleEndedIterator

Extending the TrieIterator trait with DoubleEndedIterator trait.

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.

TrieRecorder

A trie recorder that can be used to record all kind of TrieAccess’s.

Functions

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 MemoryDB. 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.

decode_compact_from_iter

Variant of ‘decode_compact’ that accept an iterator of encoded nodes as input.

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.

trie_visit

Function visiting trie from key value inputs with a ProccessEncodedNode callback. This is the main entry point of this module. Calls to each node occurs ordered by byte key value but with longest keys first (from node to branch to root), this differs from standard byte array ordering a bit.

Type Aliases

CError

Alias accessor to NodeCodec associated Error type from a TrieLayout.

DBValue

Database value

Partial

Representation of a nible slice (right aligned). It contains a right aligned padded first byte (first pair element is the number of nibbles (0 to max nb nibble - 1), second pair element is the padded nibble), and a slice over the remaining bytes.

Result

Trie result type. Boxed to avoid copying around extra space for the Hashers Out on successful queries.

TrieHash

Alias accessor to hasher hash output type from a TrieLayout.

TrieItem

Trie-Item type used for iterators over trie data.

TrieKeyItem

Trie-Item type used for iterators over trie key only.