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

reth_trie/trie_cursor/
mod.rs
