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
21pub use self::{depth_first::DepthFirstTrieIterator, in_memory::*, subnode::CursorSubNode};
22
23/// Factory for creating trie cursors.
24#[auto_impl::auto_impl(&)]
25pub trait TrieCursorFactory {
26    /// The account trie cursor type.
27    type AccountTrieCursor<'a>: TrieCursor
28    where
29        Self: 'a;
30
31    /// The storage trie cursor type.
32    type StorageTrieCursor<'a>: TrieCursor
33    where
34        Self: 'a;
35
36    /// Create an account trie cursor.
37    fn account_trie_cursor(&self) -> Result<Self::AccountTrieCursor<'_>, DatabaseError>;
38
39    /// Create a storage tries cursor.
40    fn storage_trie_cursor(
41        &self,
42        hashed_address: B256,
43    ) -> Result<Self::StorageTrieCursor<'_>, DatabaseError>;
44}
45
46/// A cursor for traversing stored trie nodes. The cursor must iterate over keys in
47/// lexicographical order.
48#[auto_impl::auto_impl(&mut)]
49pub trait TrieCursor {
50    /// Move the cursor to the key and return if it is an exact match.
51    fn seek_exact(
52        &mut self,
53        key: Nibbles,
54    ) -> Result<Option<(Nibbles, BranchNodeCompact)>, DatabaseError>;
55
56    /// Move the cursor to the key and return a value matching of greater than the key.
57    fn seek(&mut self, key: Nibbles)
58        -> Result<Option<(Nibbles, BranchNodeCompact)>, DatabaseError>;
59
60    /// Move the cursor to the next key.
61    fn next(&mut self) -> Result<Option<(Nibbles, BranchNodeCompact)>, DatabaseError>;
62
63    /// Get the current entry.
64    fn current(&mut self) -> Result<Option<Nibbles>, DatabaseError>;
65}
66
67/// Iterator wrapper for `TrieCursor` types
68#[derive(Debug)]
69pub struct TrieCursorIter<'a, C> {
70    cursor: &'a mut C,
71    /// The initial value from seek, if any
72    initial: Option<Result<(Nibbles, BranchNodeCompact), DatabaseError>>,
73}
74
75impl<'a, C> TrieCursorIter<'a, C> {
76    /// Create a new iterator from a mutable reference to a cursor. The Iterator will start from the
77    /// empty path.
78    pub fn new(cursor: &'a mut C) -> Self
79    where
80        C: TrieCursor,
81    {
82        let initial = cursor.seek(Nibbles::default()).transpose();
83        Self { cursor, initial }
84    }
85}
86
87impl<'a, C> From<&'a mut C> for TrieCursorIter<'a, C>
88where
89    C: TrieCursor,
90{
91    fn from(cursor: &'a mut C) -> Self {
92        Self::new(cursor)
93    }
94}
95
96impl<'a, C> Iterator for TrieCursorIter<'a, C>
97where
98    C: TrieCursor,
99{
100    type Item = Result<(Nibbles, BranchNodeCompact), DatabaseError>;
101
102    fn next(&mut self) -> Option<Self::Item> {
103        // If we have an initial value from seek, return it first
104        if let Some(initial) = self.initial.take() {
105            return Some(initial);
106        }
107
108        self.cursor.next().transpose()
109    }
110}
reth_trie/trie_cursor/mod.rs

reth_trie/trie_cursor/
mod.rs
