reth_trie/trie_cursor/
mod.rs

1use crate::{BranchNodeCompact, Nibbles};
2use alloy_primitives::B256;
3use reth_storage_errors::db::DatabaseError;
4
5/// In-memory implementations of trie cursors.
6mod in_memory;
7
8/// Cursor for iterating over a subtrie.
9pub mod subnode;
10
11/// Noop trie cursor implementations.
12pub mod noop;
13
14/// Depth-first trie iterator.
15pub mod depth_first;
16
17/// Mock trie cursor implementations.
18#[cfg(any(test, feature = "test-utils"))]
19pub mod mock;
20
21/// Metrics tracking trie cursor implementations.
22#[cfg(feature = "metrics")]
23pub mod metrics;
24#[cfg(feature = "metrics")]
25pub use metrics::{InstrumentedTrieCursor, InstrumentedTrieCursorFactory, TrieCursorMetrics};
26
27/// Uses the underlying factory directly when cursor metrics are disabled.
28#[cfg(not(feature = "metrics"))]
29pub type InstrumentedTrieCursorFactory<F> = F;
30
31pub use self::{depth_first::DepthFirstTrieIterator, in_memory::*, subnode::CursorSubNode};
32
33/// Factory for creating trie cursors.
34#[auto_impl::auto_impl(&)]
35pub trait TrieCursorFactory {
36    /// The account trie cursor type.
37    type AccountTrieCursor<'a>: TrieCursor
38    where
39        Self: 'a;
40
41    /// The storage trie cursor type.
42    type StorageTrieCursor<'a>: TrieStorageCursor
43    where
44        Self: 'a;
45
46    /// Create an account trie cursor.
47    fn account_trie_cursor(&self) -> Result<Self::AccountTrieCursor<'_>, DatabaseError>;
48
49    /// Create a storage tries cursor.
50    fn storage_trie_cursor(
51        &self,
52        hashed_address: B256,
53    ) -> Result<Self::StorageTrieCursor<'_>, DatabaseError>;
54}
55
56/// A cursor for traversing stored trie nodes. The cursor must iterate over keys in
57/// lexicographical order.
58#[auto_impl::auto_impl(&mut, Box)]
59pub trait TrieCursor {
60    /// Move the cursor to the key and return if it is an exact match.
61    fn seek_exact(
62        &mut self,
63        key: Nibbles,
64    ) -> Result<Option<(Nibbles, BranchNodeCompact)>, DatabaseError>;
65
66    /// Move the cursor to the key and return a value matching of greater than the key.
67    fn seek(&mut self, key: Nibbles)
68        -> Result<Option<(Nibbles, BranchNodeCompact)>, DatabaseError>;
69
70    /// Move the cursor to the next key.
71    fn next(&mut self) -> Result<Option<(Nibbles, BranchNodeCompact)>, DatabaseError>;
72
73    /// Get the current entry.
74    fn current(&mut self) -> Result<Option<Nibbles>, DatabaseError>;
75
76    /// Reset the cursor to the beginning.
77    ///
78    /// # Important
79    ///
80    /// After calling this method, the subsequent operation MUST be a [`TrieCursor::seek`] or
81    /// [`TrieCursor::seek_exact`] call.
82    fn reset(&mut self);
83}
84
85/// A cursor for traversing storage trie nodes.
86#[auto_impl::auto_impl(&mut, Box)]
87pub trait TrieStorageCursor: TrieCursor {
88    /// Set the hashed address for the storage trie cursor.
89    ///
90    /// # Important
91    ///
92    /// After calling this method, the subsequent operation MUST be a [`TrieCursor::seek`] or
93    /// [`TrieCursor::seek_exact`] call.
94    fn set_hashed_address(&mut self, hashed_address: B256);
95}
96
97/// Iterator wrapper for `TrieCursor` types
98#[derive(Debug)]
99pub struct TrieCursorIter<'a, C> {
100    cursor: &'a mut C,
101    /// The initial value from seek, if any
102    initial: Option<Result<(Nibbles, BranchNodeCompact), DatabaseError>>,
103}
104
105impl<'a, C> TrieCursorIter<'a, C> {
106    /// Create a new iterator from a mutable reference to a cursor. The Iterator will start from the
107    /// empty path.
108    pub fn new(cursor: &'a mut C) -> Self
109    where
110        C: TrieCursor,
111    {
112        let initial = cursor.seek(Nibbles::default()).transpose();
113        Self { cursor, initial }
114    }
115}
116
117impl<'a, C> From<&'a mut C> for TrieCursorIter<'a, C>
118where
119    C: TrieCursor,
120{
121    fn from(cursor: &'a mut C) -> Self {
122        Self::new(cursor)
123    }
124}
125
126impl<'a, C> Iterator for TrieCursorIter<'a, C>
127where
128    C: TrieCursor,
129{
130    type Item = Result<(Nibbles, BranchNodeCompact), DatabaseError>;
131
132    fn next(&mut self) -> Option<Self::Item> {
133        // If we have an initial value from seek, return it first
134        if let Some(initial) = self.initial.take() {
135            return Some(initial);
136        }
137
138        self.cursor.next().transpose()
139    }
140}
reth_trie/trie_cursor/mod.rs

reth_trie/trie_cursor/
mod.rs
