reth_trie_common/
trie.rs

1//! Types related to sparse trie nodes and masks.
2
3use crate::Nibbles;
4use alloy_primitives::map::HashMap;
5use alloy_trie::{nodes::TrieNode, TrieMask};
6
7/// Branch node masks containing `hash_mask` and `tree_mask`.
8///
9/// Consolidates `hash_mask` and `tree_mask` into a single struct, reducing `HashMap` overhead
10/// when storing masks by path. Instead of two separate `HashMap<Nibbles, TrieMask>`,
11/// we use a single `HashMap<Nibbles, BranchNodeMasks>`.
12#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
13pub struct BranchNodeMasks {
14    /// Hash mask indicating which children are stored as hashes.
15    pub hash_mask: TrieMask,
16    /// Tree mask indicating which children are complete subtrees.
17    pub tree_mask: TrieMask,
18}
19
20/// Map from nibble path to branch node masks.
21pub type BranchNodeMasksMap = HashMap<Nibbles, BranchNodeMasks>;
22
23/// Struct for passing around branch node mask information.
24///
25/// Branch nodes can have up to 16 children (one for each nibble).
26/// The masks represent which children are stored in different ways:
27/// - `hash_mask`: Indicates which children are stored as hashes in the database
28/// - `tree_mask`: Indicates which children are complete subtrees stored in the database
29///
30/// These masks are essential for efficient trie traversal and serialization, as they
31/// determine how nodes should be encoded and stored on disk.
32#[derive(Debug, PartialEq, Eq, Clone, Copy)]
33pub struct TrieMasks {
34    /// Branch node hash mask, if any.
35    ///
36    /// When a bit is set, the corresponding child node's hash is stored in the trie.
37    ///
38    /// This mask enables selective hashing of child nodes.
39    pub hash_mask: Option<TrieMask>,
40    /// Branch node tree mask, if any.
41    ///
42    /// When a bit is set, the corresponding child subtree is stored in the database.
43    pub tree_mask: Option<TrieMask>,
44}
45
46impl TrieMasks {
47    /// Helper function, returns both fields `hash_mask` and `tree_mask` as [`None`]
48    pub const fn none() -> Self {
49        Self { hash_mask: None, tree_mask: None }
50    }
51}
52
53/// Carries all information needed by a sparse trie to reveal a particular node.
54#[derive(Debug, Clone, PartialEq, Eq)]
55pub struct ProofTrieNode {
56    /// Path of the node.
57    pub path: Nibbles,
58    /// The node itself.
59    pub node: TrieNode,
60    /// Tree and hash masks for the node, if known.
61    pub masks: TrieMasks,
62}
reth_trie_common/trie.rs

reth_trie_common/
trie.rs
