reth_db_api/
cursor.rs

1use std::{
2    fmt,
3    ops::{Bound, RangeBounds},
4};
5
6use crate::{
7    common::{IterPairResult, PairResult, ValueOnlyResult},
8    table::{DupSort, Table, TableRow},
9    DatabaseError,
10};
11
12/// A read-only cursor over table `T`.
13pub trait DbCursorRO<T: Table> {
14    /// Positions the cursor at the first entry in the table, returning it.
15    fn first(&mut self) -> PairResult<T>;
16
17    /// Seeks to the KV pair exactly at `key`.
18    fn seek_exact(&mut self, key: T::Key) -> PairResult<T>;
19
20    /// Seeks to the KV pair whose key is greater than or equal to `key`.
21    fn seek(&mut self, key: T::Key) -> PairResult<T>;
22
23    /// Position the cursor at the next KV pair, returning it.
24    #[allow(clippy::should_implement_trait)]
25    fn next(&mut self) -> PairResult<T>;
26
27    /// Position the cursor at the previous KV pair, returning it.
28    fn prev(&mut self) -> PairResult<T>;
29
30    /// Positions the cursor at the last entry in the table, returning it.
31    fn last(&mut self) -> PairResult<T>;
32
33    /// Get the KV pair at the cursor's current position.
34    fn current(&mut self) -> PairResult<T>;
35
36    /// Get an iterator that walks through the table.
37    ///
38    /// If `start_key` is `None`, then the walker will start from the first entry of the table,
39    /// otherwise it starts at the entry greater than or equal to the provided key.
40    fn walk(&mut self, start_key: Option<T::Key>) -> Result<Walker<'_, T, Self>, DatabaseError>
41    where
42        Self: Sized;
43
44    /// Get an iterator that walks over a range of keys in the table.
45    fn walk_range(
46        &mut self,
47        range: impl RangeBounds<T::Key>,
48    ) -> Result<RangeWalker<'_, T, Self>, DatabaseError>
49    where
50        Self: Sized;
51
52    /// Get an iterator that walks through the table in reverse order.
53    ///
54    /// If `start_key` is `None`, then the walker will start from the last entry of the table,
55    /// otherwise it starts at the entry greater than or equal to the provided key.
56    fn walk_back(
57        &mut self,
58        start_key: Option<T::Key>,
59    ) -> Result<ReverseWalker<'_, T, Self>, DatabaseError>
60    where
61        Self: Sized;
62}
63
64/// A read-only cursor over the dup table `T`.
65pub trait DbDupCursorRO<T: DupSort> {
66    /// Positions the cursor at the next KV pair of the table, returning it.
67    fn next_dup(&mut self) -> PairResult<T>;
68
69    /// Positions the cursor at the next KV pair of the table, skipping duplicates.
70    fn next_no_dup(&mut self) -> PairResult<T>;
71
72    /// Positions the cursor at the next duplicate value of the current key.
73    fn next_dup_val(&mut self) -> ValueOnlyResult<T>;
74
75    /// Positions the cursor at the entry greater than or equal to the provided key/subkey pair.
76    ///
77    /// # Note
78    ///
79    /// The position of the cursor might not correspond to the key/subkey pair if the entry does not
80    /// exist.
81    fn seek_by_key_subkey(&mut self, key: T::Key, subkey: T::SubKey) -> ValueOnlyResult<T>;
82
83    /// Get an iterator that walks through the dup table.
84    ///
85    /// The cursor will start at different points in the table depending on the values of `key` and
86    /// `subkey`:
87    ///
88    /// | `key`  | `subkey` | **Equivalent starting position**        |
89    /// |--------|----------|-----------------------------------------|
90    /// | `None` | `None`   | [`DbCursorRO::first()`]                 |
91    /// | `Some` | `None`   | [`DbCursorRO::seek()`]               |
92    /// | `None` | `Some`   | [`DbDupCursorRO::seek_by_key_subkey()`] |
93    /// | `Some` | `Some`   | [`DbDupCursorRO::seek_by_key_subkey()`] |
94    fn walk_dup(
95        &mut self,
96        key: Option<T::Key>,
97        subkey: Option<T::SubKey>,
98    ) -> Result<DupWalker<'_, T, Self>, DatabaseError>
99    where
100        Self: Sized;
101}
102
103/// Read write cursor over table.
104pub trait DbCursorRW<T: Table> {
105    /// Database operation that will update an existing row if a specified value already
106    /// exists in a table, and insert a new row if the specified value doesn't already exist
107    fn upsert(&mut self, key: T::Key, value: T::Value) -> Result<(), DatabaseError>;
108
109    /// Database operation that will insert a row at a given key. If the key is already
110    /// present, the operation will result in an error.
111    fn insert(&mut self, key: T::Key, value: T::Value) -> Result<(), DatabaseError>;
112
113    /// Append value to next cursor item.
114    ///
115    /// This is efficient for pre-sorted data. If the data is not pre-sorted, use
116    /// [`DbCursorRW::insert`].
117    fn append(&mut self, key: T::Key, value: T::Value) -> Result<(), DatabaseError>;
118
119    /// Delete current value that cursor points to
120    fn delete_current(&mut self) -> Result<(), DatabaseError>;
121}
122
123/// Read Write Cursor over `DupSorted` table.
124pub trait DbDupCursorRW<T: DupSort> {
125    /// Delete all duplicate entries for current key.
126    fn delete_current_duplicates(&mut self) -> Result<(), DatabaseError>;
127
128    /// Append duplicate value.
129    ///
130    /// This is efficient for pre-sorted data. If the data is not pre-sorted, use `insert`.
131    fn append_dup(&mut self, key: T::Key, value: T::Value) -> Result<(), DatabaseError>;
132}
133
134/// Provides an iterator to `Cursor` when handling `Table`.
135pub struct Walker<'cursor, T: Table, CURSOR: DbCursorRO<T>> {
136    /// Cursor to be used to walk through the table.
137    cursor: &'cursor mut CURSOR,
138    /// `(key, value)` where to start the walk.
139    start: IterPairResult<T>,
140}
141
142impl<T, CURSOR> fmt::Debug for Walker<'_, T, CURSOR>
143where
144    T: Table,
145    CURSOR: DbCursorRO<T> + fmt::Debug,
146{
147    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
148        f.debug_struct("Walker").field("cursor", &self.cursor).field("start", &self.start).finish()
149    }
150}
151
152impl<T: Table, CURSOR: DbCursorRO<T>> Iterator for Walker<'_, T, CURSOR> {
153    type Item = Result<TableRow<T>, DatabaseError>;
154    fn next(&mut self) -> Option<Self::Item> {
155        self.start.take().or_else(|| self.cursor.next().transpose())
156    }
157}
158
159impl<'cursor, T: Table, CURSOR: DbCursorRO<T>> Walker<'cursor, T, CURSOR> {
160    /// construct Walker
161    pub fn new(cursor: &'cursor mut CURSOR, start: IterPairResult<T>) -> Self {
162        Self { cursor, start }
163    }
164
165    /// convert current [`Walker`] to [`ReverseWalker`] which iterates reversely
166    pub fn rev(self) -> ReverseWalker<'cursor, T, CURSOR> {
167        let start = self.cursor.current().transpose();
168        ReverseWalker::new(self.cursor, start)
169    }
170}
171
172impl<T: Table, CURSOR: DbCursorRW<T> + DbCursorRO<T>> Walker<'_, T, CURSOR> {
173    /// Delete current item that walker points to.
174    pub fn delete_current(&mut self) -> Result<(), DatabaseError> {
175        self.start.take();
176        self.cursor.delete_current()
177    }
178}
179
180/// Provides a reverse iterator to `Cursor` when handling `Table`.
181/// Also check [`Walker`]
182pub struct ReverseWalker<'cursor, T: Table, CURSOR: DbCursorRO<T>> {
183    /// Cursor to be used to walk through the table.
184    cursor: &'cursor mut CURSOR,
185    /// `(key, value)` where to start the walk.
186    start: IterPairResult<T>,
187}
188
189impl<T, CURSOR> fmt::Debug for ReverseWalker<'_, T, CURSOR>
190where
191    T: Table,
192    CURSOR: DbCursorRO<T> + fmt::Debug,
193{
194    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
195        f.debug_struct("ReverseWalker")
196            .field("cursor", &self.cursor)
197            .field("start", &self.start)
198            .finish()
199    }
200}
201
202impl<'cursor, T: Table, CURSOR: DbCursorRO<T>> ReverseWalker<'cursor, T, CURSOR> {
203    /// construct `ReverseWalker`
204    pub fn new(cursor: &'cursor mut CURSOR, start: IterPairResult<T>) -> Self {
205        Self { cursor, start }
206    }
207
208    /// convert current [`ReverseWalker`] to [`Walker`] which iterate forwardly
209    pub fn forward(self) -> Walker<'cursor, T, CURSOR> {
210        let start = self.cursor.current().transpose();
211        Walker::new(self.cursor, start)
212    }
213}
214
215impl<T: Table, CURSOR: DbCursorRW<T> + DbCursorRO<T>> ReverseWalker<'_, T, CURSOR> {
216    /// Delete current item that walker points to.
217    pub fn delete_current(&mut self) -> Result<(), DatabaseError> {
218        self.start.take();
219        self.cursor.delete_current()
220    }
221}
222
223impl<T: Table, CURSOR: DbCursorRO<T>> Iterator for ReverseWalker<'_, T, CURSOR> {
224    type Item = Result<TableRow<T>, DatabaseError>;
225
226    fn next(&mut self) -> Option<Self::Item> {
227        let start = self.start.take();
228        if start.is_some() {
229            return start
230        }
231
232        self.cursor.prev().transpose()
233    }
234}
235
236/// Provides a range iterator to `Cursor` when handling `Table`.
237/// Also check [`Walker`]
238pub struct RangeWalker<'cursor, T: Table, CURSOR: DbCursorRO<T>> {
239    /// Cursor to be used to walk through the table.
240    cursor: &'cursor mut CURSOR,
241    /// `(key, value)` where to start the walk.
242    start: IterPairResult<T>,
243    /// `key` where to stop the walk.
244    end_key: Bound<T::Key>,
245    /// flag whether is ended
246    is_done: bool,
247}
248
249impl<T, CURSOR> fmt::Debug for RangeWalker<'_, T, CURSOR>
250where
251    T: Table,
252    CURSOR: DbCursorRO<T> + fmt::Debug,
253{
254    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
255        f.debug_struct("RangeWalker")
256            .field("cursor", &self.cursor)
257            .field("start", &self.start)
258            .field("end_key", &self.end_key)
259            .field("is_done", &self.is_done)
260            .finish()
261    }
262}
263
264impl<T: Table, CURSOR: DbCursorRO<T>> Iterator for RangeWalker<'_, T, CURSOR> {
265    type Item = Result<TableRow<T>, DatabaseError>;
266
267    fn next(&mut self) -> Option<Self::Item> {
268        if self.is_done {
269            return None
270        }
271
272        let next_item = self.start.take().or_else(|| self.cursor.next().transpose());
273
274        match next_item {
275            Some(Ok((key, value))) => match &self.end_key {
276                Bound::Included(end_key) if &key <= end_key => Some(Ok((key, value))),
277                Bound::Excluded(end_key) if &key < end_key => Some(Ok((key, value))),
278                Bound::Unbounded => Some(Ok((key, value))),
279                _ => {
280                    self.is_done = true;
281                    None
282                }
283            },
284            Some(res @ Err(_)) => Some(res),
285            None => {
286                self.is_done = matches!(self.end_key, Bound::Unbounded);
287                None
288            }
289        }
290    }
291}
292
293impl<'cursor, T: Table, CURSOR: DbCursorRO<T>> RangeWalker<'cursor, T, CURSOR> {
294    /// construct `RangeWalker`
295    pub fn new(
296        cursor: &'cursor mut CURSOR,
297        start: IterPairResult<T>,
298        end_key: Bound<T::Key>,
299    ) -> Self {
300        // mark done if range is empty.
301        let is_done = match start {
302            Some(Ok((ref start_key, _))) => match &end_key {
303                Bound::Included(end_key) if start_key > end_key => true,
304                Bound::Excluded(end_key) if start_key >= end_key => true,
305                _ => false,
306            },
307            None => true,
308            _ => false,
309        };
310        Self { cursor, start, end_key, is_done }
311    }
312}
313
314impl<T: Table, CURSOR: DbCursorRW<T> + DbCursorRO<T>> RangeWalker<'_, T, CURSOR> {
315    /// Delete current item that walker points to.
316    pub fn delete_current(&mut self) -> Result<(), DatabaseError> {
317        self.start.take();
318        self.cursor.delete_current()
319    }
320}
321
322/// Provides an iterator to `Cursor` when handling a `DupSort` table.
323///
324/// Reason why we have two lifetimes is to distinguish between `'cursor` lifetime
325/// and inherited `'tx` lifetime. If there is only one, rust would short circle
326/// the Cursor lifetime and it wouldn't be possible to use Walker.
327pub struct DupWalker<'cursor, T: DupSort, CURSOR: DbDupCursorRO<T>> {
328    /// Cursor to be used to walk through the table.
329    pub cursor: &'cursor mut CURSOR,
330    /// Value where to start the walk.
331    pub start: IterPairResult<T>,
332}
333
334impl<T, CURSOR> fmt::Debug for DupWalker<'_, T, CURSOR>
335where
336    T: DupSort,
337    CURSOR: DbDupCursorRO<T> + fmt::Debug,
338{
339    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
340        f.debug_struct("DupWalker")
341            .field("cursor", &self.cursor)
342            .field("start", &self.start)
343            .finish()
344    }
345}
346
347impl<T: DupSort, CURSOR: DbCursorRW<T> + DbDupCursorRO<T>> DupWalker<'_, T, CURSOR> {
348    /// Delete current item that walker points to.
349    pub fn delete_current(&mut self) -> Result<(), DatabaseError> {
350        self.start.take();
351        self.cursor.delete_current()
352    }
353}
354
355impl<T: DupSort, CURSOR: DbDupCursorRO<T>> Iterator for DupWalker<'_, T, CURSOR> {
356    type Item = Result<TableRow<T>, DatabaseError>;
357    fn next(&mut self) -> Option<Self::Item> {
358        let start = self.start.take();
359        if start.is_some() {
360            return start
361        }
362        self.cursor.next_dup().transpose()
363    }
364}
reth_db_api/cursor.rs

reth_db_api/
cursor.rs
