reth_trie/
forward_cursor.rs

1/// The implementation of forward-only in memory cursor over the entries.
2///
3/// The cursor operates under the assumption that the supplied collection is pre-sorted.
4#[derive(Debug)]
5pub struct ForwardInMemoryCursor<'a, K, V> {
6    /// The reference to the pre-sorted collection of entries.
7    entries: std::slice::Iter<'a, (K, V)>,
8    is_empty: bool,
9}
10
11impl<'a, K, V> ForwardInMemoryCursor<'a, K, V> {
12    /// Create new forward cursor positioned at the beginning of the collection.
13    ///
14    /// The cursor expects all of the entries to have been sorted in advance.
15    #[inline]
16    pub fn new(entries: &'a [(K, V)]) -> Self {
17        Self { entries: entries.iter(), is_empty: entries.is_empty() }
18    }
19
20    /// Returns `true` if the cursor is empty, regardless of its position.
21    #[inline]
22    pub const fn is_empty(&self) -> bool {
23        self.is_empty
24    }
25
26    /// Returns the current entry pointed to be the cursor, or `None` if no entries are left.
27    #[inline]
28    pub fn current(&self) -> Option<&(K, V)> {
29        self.entries.clone().next()
30    }
31
32    #[inline]
33    fn next(&mut self) -> Option<&(K, V)> {
34        self.entries.next()
35    }
36}
37
38impl<K, V> ForwardInMemoryCursor<'_, K, V>
39where
40    K: PartialOrd + Clone,
41    V: Clone,
42{
43    /// Returns the first entry from the current cursor position that's greater or equal to the
44    /// provided key. This method advances the cursor forward.
45    pub fn seek(&mut self, key: &K) -> Option<(K, V)> {
46        self.advance_while(|k| k < key)
47    }
48
49    /// Returns the first entry from the current cursor position that's greater than the provided
50    /// key. This method advances the cursor forward.
51    pub fn first_after(&mut self, key: &K) -> Option<(K, V)> {
52        self.advance_while(|k| k <= key)
53    }
54
55    /// Advances the cursor forward while `predicate` returns `true` or until the collection is
56    /// exhausted.
57    ///
58    /// Returns the first entry for which `predicate` returns `false` or `None`. The cursor will
59    /// point to the returned entry.
60    fn advance_while(&mut self, predicate: impl Fn(&K) -> bool) -> Option<(K, V)> {
61        let mut entry;
62        loop {
63            entry = self.current();
64            if entry.is_some_and(|(k, _)| predicate(k)) {
65                self.next();
66            } else {
67                break;
68            }
69        }
70        entry.cloned()
71    }
72}
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_cursor() {
80        let mut cursor = ForwardInMemoryCursor::new(&[(1, ()), (2, ()), (3, ()), (4, ()), (5, ())]);
81        assert_eq!(cursor.current(), Some(&(1, ())));
82
83        assert_eq!(cursor.seek(&0), Some((1, ())));
84        assert_eq!(cursor.current(), Some(&(1, ())));
85
86        assert_eq!(cursor.seek(&3), Some((3, ())));
87        assert_eq!(cursor.current(), Some(&(3, ())));
88
89        assert_eq!(cursor.seek(&3), Some((3, ())));
90        assert_eq!(cursor.current(), Some(&(3, ())));
91
92        assert_eq!(cursor.seek(&4), Some((4, ())));
93        assert_eq!(cursor.current(), Some(&(4, ())));
94
95        assert_eq!(cursor.seek(&6), None);
96        assert_eq!(cursor.current(), None);
97    }
98}
reth_trie/forward_cursor.rs

reth_trie/
forward_cursor.rs
