reth_db_api/
cursor.rs

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

reth_db_api/
cursor.rs
