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
20impl BranchNodeMasks {
21    /// Creates masks from optional hash and tree masks.
22    ///
23    /// Returns `None` if both masks are `None`, otherwise defaults missing masks to empty.
24    pub fn from_optional(hash_mask: Option<TrieMask>, tree_mask: Option<TrieMask>) -> Option<Self> {
25        match (hash_mask, tree_mask) {
26            (Some(h), Some(t)) => Some(Self { hash_mask: h, tree_mask: t }),
27            (Some(h), None) => Some(Self { hash_mask: h, tree_mask: TrieMask::default() }),
28            (None, Some(t)) => Some(Self { hash_mask: TrieMask::default(), tree_mask: t }),
29            (None, None) => None,
30        }
31    }
32
33    /// Returns true if both interior masks are empty.
34    pub const fn is_empty(&self) -> bool {
35        self.hash_mask.is_empty() && self.tree_mask.is_empty()
36    }
37
38    /// Updates this set of masks for `nibble` based on that child's mask bits.
39    pub const fn set_child_bits(&mut self, nibble: u8, hash_mask_bit: bool, tree_mask_bit: bool) {
40        if hash_mask_bit {
41            self.hash_mask.set_bit(nibble);
42        } else {
43            self.hash_mask.unset_bit(nibble);
44        }
45        if tree_mask_bit {
46            self.tree_mask.set_bit(nibble);
47        } else {
48            self.tree_mask.unset_bit(nibble);
49        }
50    }
51}
52
53/// Map from nibble path to branch node masks.
54pub type BranchNodeMasksMap = HashMap<Nibbles, BranchNodeMasks>;
55
56/// Carries all information needed by a sparse trie to reveal a particular node.
57#[derive(Debug, Clone, PartialEq, Eq)]
58pub struct ProofTrieNode {
59    /// Path of the node.
60    pub path: Nibbles,
61    /// The node itself.
62    pub node: TrieNode,
63    /// Tree and hash masks for the node, if known.
64    /// Both masks are always set together (from database branch nodes).
65    pub masks: Option<BranchNodeMasks>,
66}
reth_trie_common/trie.rs

reth_trie_common/
trie.rs
