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

reth_db_api/
cursor.rs
