reth_db_api/
cursor.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
use std::{
    fmt,
    ops::{Bound, RangeBounds},
};

use crate::{
    common::{IterPairResult, PairResult, ValueOnlyResult},
    table::{DupSort, Table, TableRow},
    DatabaseError,
};

/// A read-only cursor over table `T`.
pub trait DbCursorRO<T: Table> {
    /// Positions the cursor at the first entry in the table, returning it.
    fn first(&mut self) -> PairResult<T>;

    /// Seeks to the KV pair exactly at `key`.
    fn seek_exact(&mut self, key: T::Key) -> PairResult<T>;

    /// Seeks to the KV pair whose key is greater than or equal to `key`.
    fn seek(&mut self, key: T::Key) -> PairResult<T>;

    /// Position the cursor at the next KV pair, returning it.
    #[allow(clippy::should_implement_trait)]
    fn next(&mut self) -> PairResult<T>;

    /// Position the cursor at the previous KV pair, returning it.
    fn prev(&mut self) -> PairResult<T>;

    /// Positions the cursor at the last entry in the table, returning it.
    fn last(&mut self) -> PairResult<T>;

    /// Get the KV pair at the cursor's current position.
    fn current(&mut self) -> PairResult<T>;

    /// Get an iterator that walks through the table.
    ///
    /// If `start_key` is `None`, then the walker will start from the first entry of the table,
    /// otherwise it starts at the entry greater than or equal to the provided key.
    fn walk(&mut self, start_key: Option<T::Key>) -> Result<Walker<'_, T, Self>, DatabaseError>
    where
        Self: Sized;

    /// Get an iterator that walks over a range of keys in the table.
    fn walk_range(
        &mut self,
        range: impl RangeBounds<T::Key>,
    ) -> Result<RangeWalker<'_, T, Self>, DatabaseError>
    where
        Self: Sized;

    /// Get an iterator that walks through the table in reverse order.
    ///
    /// If `start_key` is `None`, then the walker will start from the last entry of the table,
    /// otherwise it starts at the entry greater than or equal to the provided key.
    fn walk_back(
        &mut self,
        start_key: Option<T::Key>,
    ) -> Result<ReverseWalker<'_, T, Self>, DatabaseError>
    where
        Self: Sized;
}

/// A read-only cursor over the dup table `T`.
pub trait DbDupCursorRO<T: DupSort> {
    /// Positions the cursor at the next KV pair of the table, returning it.
    fn next_dup(&mut self) -> PairResult<T>;

    /// Positions the cursor at the next KV pair of the table, skipping duplicates.
    fn next_no_dup(&mut self) -> PairResult<T>;

    /// Positions the cursor at the next duplicate value of the current key.
    fn next_dup_val(&mut self) -> ValueOnlyResult<T>;

    /// Positions the cursor at the entry greater than or equal to the provided key/subkey pair.
    ///
    /// # Note
    ///
    /// The position of the cursor might not correspond to the key/subkey pair if the entry does not
    /// exist.
    fn seek_by_key_subkey(&mut self, key: T::Key, subkey: T::SubKey) -> ValueOnlyResult<T>;

    /// Get an iterator that walks through the dup table.
    ///
    /// The cursor will start at different points in the table depending on the values of `key` and
    /// `subkey`:
    ///
    /// | `key`  | `subkey` | **Equivalent starting position**        |
    /// |--------|----------|-----------------------------------------|
    /// | `None` | `None`   | [`DbCursorRO::first()`]                 |
    /// | `Some` | `None`   | [`DbCursorRO::seek()`]               |
    /// | `None` | `Some`   | [`DbDupCursorRO::seek_by_key_subkey()`] |
    /// | `Some` | `Some`   | [`DbDupCursorRO::seek_by_key_subkey()`] |
    fn walk_dup(
        &mut self,
        key: Option<T::Key>,
        subkey: Option<T::SubKey>,
    ) -> Result<DupWalker<'_, T, Self>, DatabaseError>
    where
        Self: Sized;
}

/// Read write cursor over table.
pub trait DbCursorRW<T: Table> {
    /// Database operation that will update an existing row if a specified value already
    /// exists in a table, and insert a new row if the specified value doesn't already exist
    fn upsert(&mut self, key: T::Key, value: T::Value) -> Result<(), DatabaseError>;

    /// Database operation that will insert a row at a given key. If the key is already
    /// present, the operation will result in an error.
    fn insert(&mut self, key: T::Key, value: T::Value) -> Result<(), DatabaseError>;

    /// Append value to next cursor item.
    ///
    /// This is efficient for pre-sorted data. If the data is not pre-sorted, use
    /// [`DbCursorRW::insert`].
    fn append(&mut self, key: T::Key, value: T::Value) -> Result<(), DatabaseError>;

    /// Delete current value that cursor points to
    fn delete_current(&mut self) -> Result<(), DatabaseError>;
}

/// Read Write Cursor over `DupSorted` table.
pub trait DbDupCursorRW<T: DupSort> {
    /// Delete all duplicate entries for current key.
    fn delete_current_duplicates(&mut self) -> Result<(), DatabaseError>;

    /// Append duplicate value.
    ///
    /// This is efficient for pre-sorted data. If the data is not pre-sorted, use `insert`.
    fn append_dup(&mut self, key: T::Key, value: T::Value) -> Result<(), DatabaseError>;
}

/// Provides an iterator to `Cursor` when handling `Table`.
pub struct Walker<'cursor, T: Table, CURSOR: DbCursorRO<T>> {
    /// Cursor to be used to walk through the table.
    cursor: &'cursor mut CURSOR,
    /// `(key, value)` where to start the walk.
    start: IterPairResult<T>,
}

impl<T, CURSOR> fmt::Debug for Walker<'_, T, CURSOR>
where
    T: Table,
    CURSOR: DbCursorRO<T> + fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Walker").field("cursor", &self.cursor).field("start", &self.start).finish()
    }
}

impl<T: Table, CURSOR: DbCursorRO<T>> Iterator for Walker<'_, T, CURSOR> {
    type Item = Result<TableRow<T>, DatabaseError>;
    fn next(&mut self) -> Option<Self::Item> {
        self.start.take().or_else(|| self.cursor.next().transpose())
    }
}

impl<'cursor, T: Table, CURSOR: DbCursorRO<T>> Walker<'cursor, T, CURSOR> {
    /// construct Walker
    pub fn new(cursor: &'cursor mut CURSOR, start: IterPairResult<T>) -> Self {
        Self { cursor, start }
    }

    /// convert current [`Walker`] to [`ReverseWalker`] which iterates reversely
    pub fn rev(self) -> ReverseWalker<'cursor, T, CURSOR> {
        let start = self.cursor.current().transpose();
        ReverseWalker::new(self.cursor, start)
    }
}

impl<T: Table, CURSOR: DbCursorRW<T> + DbCursorRO<T>> Walker<'_, T, CURSOR> {
    /// Delete current item that walker points to.
    pub fn delete_current(&mut self) -> Result<(), DatabaseError> {
        self.start.take();
        self.cursor.delete_current()
    }
}

/// Provides a reverse iterator to `Cursor` when handling `Table`.
/// Also check [`Walker`]
pub struct ReverseWalker<'cursor, T: Table, CURSOR: DbCursorRO<T>> {
    /// Cursor to be used to walk through the table.
    cursor: &'cursor mut CURSOR,
    /// `(key, value)` where to start the walk.
    start: IterPairResult<T>,
}

impl<T, CURSOR> fmt::Debug for ReverseWalker<'_, T, CURSOR>
where
    T: Table,
    CURSOR: DbCursorRO<T> + fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("ReverseWalker")
            .field("cursor", &self.cursor)
            .field("start", &self.start)
            .finish()
    }
}

impl<'cursor, T: Table, CURSOR: DbCursorRO<T>> ReverseWalker<'cursor, T, CURSOR> {
    /// construct `ReverseWalker`
    pub fn new(cursor: &'cursor mut CURSOR, start: IterPairResult<T>) -> Self {
        Self { cursor, start }
    }

    /// convert current [`ReverseWalker`] to [`Walker`] which iterate forwardly
    pub fn forward(self) -> Walker<'cursor, T, CURSOR> {
        let start = self.cursor.current().transpose();
        Walker::new(self.cursor, start)
    }
}

impl<T: Table, CURSOR: DbCursorRW<T> + DbCursorRO<T>> ReverseWalker<'_, T, CURSOR> {
    /// Delete current item that walker points to.
    pub fn delete_current(&mut self) -> Result<(), DatabaseError> {
        self.start.take();
        self.cursor.delete_current()
    }
}

impl<T: Table, CURSOR: DbCursorRO<T>> Iterator for ReverseWalker<'_, T, CURSOR> {
    type Item = Result<TableRow<T>, DatabaseError>;

    fn next(&mut self) -> Option<Self::Item> {
        let start = self.start.take();
        if start.is_some() {
            return start
        }

        self.cursor.prev().transpose()
    }
}

/// Provides a range iterator to `Cursor` when handling `Table`.
/// Also check [`Walker`]
pub struct RangeWalker<'cursor, T: Table, CURSOR: DbCursorRO<T>> {
    /// Cursor to be used to walk through the table.
    cursor: &'cursor mut CURSOR,
    /// `(key, value)` where to start the walk.
    start: IterPairResult<T>,
    /// `key` where to stop the walk.
    end_key: Bound<T::Key>,
    /// flag whether is ended
    is_done: bool,
}

impl<T, CURSOR> fmt::Debug for RangeWalker<'_, T, CURSOR>
where
    T: Table,
    CURSOR: DbCursorRO<T> + fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("RangeWalker")
            .field("cursor", &self.cursor)
            .field("start", &self.start)
            .field("end_key", &self.end_key)
            .field("is_done", &self.is_done)
            .finish()
    }
}

impl<T: Table, CURSOR: DbCursorRO<T>> Iterator for RangeWalker<'_, T, CURSOR> {
    type Item = Result<TableRow<T>, DatabaseError>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.is_done {
            return None
        }

        let next_item = self.start.take().or_else(|| self.cursor.next().transpose());

        match next_item {
            Some(Ok((key, value))) => match &self.end_key {
                Bound::Included(end_key) if &key <= end_key => Some(Ok((key, value))),
                Bound::Excluded(end_key) if &key < end_key => Some(Ok((key, value))),
                Bound::Unbounded => Some(Ok((key, value))),
                _ => {
                    self.is_done = true;
                    None
                }
            },
            Some(res @ Err(_)) => Some(res),
            None => {
                self.is_done = matches!(self.end_key, Bound::Unbounded);
                None
            }
        }
    }
}

impl<'cursor, T: Table, CURSOR: DbCursorRO<T>> RangeWalker<'cursor, T, CURSOR> {
    /// construct `RangeWalker`
    pub fn new(
        cursor: &'cursor mut CURSOR,
        start: IterPairResult<T>,
        end_key: Bound<T::Key>,
    ) -> Self {
        // mark done if range is empty.
        let is_done = match start {
            Some(Ok((ref start_key, _))) => match &end_key {
                Bound::Included(end_key) if start_key > end_key => true,
                Bound::Excluded(end_key) if start_key >= end_key => true,
                _ => false,
            },
            None => true,
            _ => false,
        };
        Self { cursor, start, end_key, is_done }
    }
}

impl<T: Table, CURSOR: DbCursorRW<T> + DbCursorRO<T>> RangeWalker<'_, T, CURSOR> {
    /// Delete current item that walker points to.
    pub fn delete_current(&mut self) -> Result<(), DatabaseError> {
        self.start.take();
        self.cursor.delete_current()
    }
}

/// Provides an iterator to `Cursor` when handling a `DupSort` table.
///
/// Reason why we have two lifetimes is to distinguish between `'cursor` lifetime
/// and inherited `'tx` lifetime. If there is only one, rust would short circle
/// the Cursor lifetime and it wouldn't be possible to use Walker.
pub struct DupWalker<'cursor, T: DupSort, CURSOR: DbDupCursorRO<T>> {
    /// Cursor to be used to walk through the table.
    pub cursor: &'cursor mut CURSOR,
    /// Value where to start the walk.
    pub start: IterPairResult<T>,
}

impl<T, CURSOR> fmt::Debug for DupWalker<'_, T, CURSOR>
where
    T: DupSort,
    CURSOR: DbDupCursorRO<T> + fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("DupWalker")
            .field("cursor", &self.cursor)
            .field("start", &self.start)
            .finish()
    }
}

impl<T: DupSort, CURSOR: DbCursorRW<T> + DbDupCursorRO<T>> DupWalker<'_, T, CURSOR> {
    /// Delete current item that walker points to.
    pub fn delete_current(&mut self) -> Result<(), DatabaseError> {
        self.start.take();
        self.cursor.delete_current()
    }
}

impl<T: DupSort, CURSOR: DbDupCursorRO<T>> Iterator for DupWalker<'_, T, CURSOR> {
    type Item = Result<TableRow<T>, DatabaseError>;
    fn next(&mut self) -> Option<Self::Item> {
        let start = self.start.take();
        if start.is_some() {
            return start
        }
        self.cursor.next_dup().transpose()
    }
}