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

reth_trie/
forward_cursor.rs
