-
Notifications
You must be signed in to change notification settings - Fork 849
/
cursor.rs
296 lines (256 loc) · 10.3 KB
/
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
use std::{
marker::PhantomData,
ops::{Bound, RangeBounds},
};
use crate::{
common::{IterPairResult, PairResult, ValueOnlyResult},
table::{DupSort, Table},
Error,
};
/// Read only cursor over table.
pub trait DbCursorRO<'tx, T: Table> {
/// First item in table
fn first(&mut self) -> PairResult<T>;
/// Seeks for the exact `(key, value)` pair with `key`.
fn seek_exact(&mut self, key: T::Key) -> PairResult<T>;
/// Seeks for a `(key, value)` pair greater or equal than `key`.
fn seek(&mut self, key: T::Key) -> PairResult<T>;
/// Returns the next `(key, value)` pair.
#[allow(clippy::should_implement_trait)]
fn next(&mut self) -> PairResult<T>;
/// Returns the previous `(key, value)` pair.
fn prev(&mut self) -> PairResult<T>;
/// Returns the last `(key, value)` pair.
fn last(&mut self) -> PairResult<T>;
/// Returns the current `(key, value)` pair of the cursor.
fn current(&mut self) -> PairResult<T>;
/// Returns an iterator that walks through the table. If `start_key`
/// is None, starts from the first entry of the table. If it not, starts at a key
/// greater or equal than the key value wrapped inside Some().
fn walk<'cursor>(
&'cursor mut self,
start_key: Option<T::Key>,
) -> Result<Walker<'cursor, 'tx, T, Self>, Error>
where
Self: Sized;
/// Returns an iterator for the keys in the specified range.
fn walk_range<'cursor>(
&'cursor mut self,
range: impl RangeBounds<T::Key>,
) -> Result<RangeWalker<'cursor, 'tx, T, Self>, Error>
where
Self: Sized;
/// Returns an iterator that walks backwards through the table. If `start_key`
/// is None, starts from the last entry of the table. If it not, starts at a key
/// greater or equal than the key value wrapped inside Some().
fn walk_back<'cursor>(
&'cursor mut self,
start_key: Option<T::Key>,
) -> Result<ReverseWalker<'cursor, 'tx, T, Self>, Error>
where
Self: Sized;
}
/// Read only cursor over DupSort table.
pub trait DbDupCursorRO<'tx, T: DupSort> {
/// Returns the next `(key, value)` pair of a DupSort table.
fn next_dup(&mut self) -> PairResult<T>;
/// Returns the next `(key, value)` pair skipping the duplicates.
fn next_no_dup(&mut self) -> PairResult<T>;
/// Returns the next `value` of a duplicate `key`.
fn next_dup_val(&mut self) -> ValueOnlyResult<T>;
/// Seek by key and subkey. Make sure that the returned value subkey matches the queried one.
fn seek_by_key_subkey(&mut self, key: T::Key, subkey: T::SubKey) -> ValueOnlyResult<T>;
/// Returns an iterator starting at a key greater or equal than `start_key` of a DupSort
/// table.
fn walk_dup<'cursor>(
&'cursor mut self,
key: Option<T::Key>,
subkey: Option<T::SubKey>,
) -> Result<DupWalker<'cursor, 'tx, T, Self>, Error>
where
Self: Sized;
}
/// Read write cursor over table.
pub trait DbCursorRW<'tx, 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<(), Error>;
/// 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<(), Error>;
/// 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<(), Error>;
/// Delete current value that cursor points to
fn delete_current(&mut self) -> Result<(), Error>;
}
/// Read Write Cursor over DupSorted table.
pub trait DbDupCursorRW<'tx, T: DupSort> {
/// Delete all duplicate entries for current key.
fn delete_current_duplicates(&mut self) -> Result<(), Error>;
/// 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<(), Error>;
}
/// Provides an iterator to `Cursor` when handling `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 Walker<'cursor, 'tx, T: Table, CURSOR: DbCursorRO<'tx, T>> {
/// Cursor to be used to walk through the table.
cursor: &'cursor mut CURSOR,
/// `(key, value)` where to start the walk.
start: IterPairResult<T>,
/// Phantom data for 'tx. As it is only used for `DbCursorRO`.
_tx_phantom: PhantomData<&'tx T>,
}
impl<'cursor, 'tx, T: Table, CURSOR: DbCursorRO<'tx, T>> std::iter::Iterator
for Walker<'cursor, 'tx, T, CURSOR>
{
type Item = Result<(T::Key, T::Value), Error>;
fn next(&mut self) -> Option<Self::Item> {
let start = self.start.take();
if start.is_some() {
return start
}
self.cursor.next().transpose()
}
}
impl<'cursor, 'tx, T: Table, CURSOR: DbCursorRO<'tx, T>> Walker<'cursor, 'tx, T, CURSOR> {
/// construct Walker
pub fn new(cursor: &'cursor mut CURSOR, start: IterPairResult<T>) -> Self {
Self { cursor, start, _tx_phantom: std::marker::PhantomData }
}
/// convert current [`Walker`] to [`ReverseWalker`] which iterates reversely
pub fn rev(self) -> ReverseWalker<'cursor, 'tx, T, CURSOR> {
let start = self.cursor.current().transpose();
ReverseWalker::new(self.cursor, start)
}
}
/// Provides a reverse iterator to `Cursor` when handling `Table`.
/// Also check [`Walker`]
pub struct ReverseWalker<'cursor, 'tx, T: Table, CURSOR: DbCursorRO<'tx, T>> {
/// Cursor to be used to walk through the table.
cursor: &'cursor mut CURSOR,
/// `(key, value)` where to start the walk.
start: IterPairResult<T>,
/// Phantom data for 'tx. As it is only used for `DbCursorRO`.
_tx_phantom: PhantomData<&'tx T>,
}
impl<'cursor, 'tx, T: Table, CURSOR: DbCursorRO<'tx, T>> ReverseWalker<'cursor, 'tx, T, CURSOR> {
/// construct ReverseWalker
pub fn new(cursor: &'cursor mut CURSOR, start: IterPairResult<T>) -> Self {
Self { cursor, start, _tx_phantom: std::marker::PhantomData }
}
/// convert current [`ReverseWalker`] to [`Walker`] which iterate forwardly
pub fn forward(self) -> Walker<'cursor, 'tx, T, CURSOR> {
let start = self.cursor.current().transpose();
Walker::new(self.cursor, start)
}
}
impl<'cursor, 'tx, T: Table, CURSOR: DbCursorRO<'tx, T>> std::iter::Iterator
for ReverseWalker<'cursor, 'tx, T, CURSOR>
{
type Item = Result<(T::Key, T::Value), Error>;
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, 'tx, T: Table, CURSOR: DbCursorRO<'tx, 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 start the walk.
start_key: Bound<T::Key>,
/// `key` where to stop the walk.
end_key: Bound<T::Key>,
/// flag whether is ended
is_done: bool,
/// Phantom data for 'tx. As it is only used for `DbCursorRO`.
_tx_phantom: PhantomData<&'tx T>,
}
impl<'cursor, 'tx, T: Table, CURSOR: DbCursorRO<'tx, T>> std::iter::Iterator
for RangeWalker<'cursor, 'tx, T, CURSOR>
{
type Item = Result<(T::Key, T::Value), Error>;
fn next(&mut self) -> Option<Self::Item> {
if self.is_done {
return None
}
let start = self.start.take();
if start.is_some() && matches!(self.start_key, Bound::Included(_) | Bound::Unbounded) {
return start
}
match self.cursor.next().transpose() {
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 if matches!(self.end_key, Bound::Unbounded) => {
self.is_done = true;
None
}
_ => None,
}
}
}
impl<'cursor, 'tx, T: Table, CURSOR: DbCursorRO<'tx, T>> RangeWalker<'cursor, 'tx, T, CURSOR> {
/// construct RangeWalker
pub fn new(
cursor: &'cursor mut CURSOR,
start: IterPairResult<T>,
start_key: Bound<T::Key>,
end_key: Bound<T::Key>,
) -> Self {
Self {
cursor,
start,
start_key,
end_key,
is_done: false,
_tx_phantom: std::marker::PhantomData,
}
}
}
/// 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, 'tx, T: DupSort, CURSOR: DbDupCursorRO<'tx, 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>,
/// Phantom data for 'tx. As it is only used for `DbDupCursorRO`.
pub _tx_phantom: PhantomData<&'tx T>,
}
impl<'cursor, 'tx, T: DupSort, CURSOR: DbDupCursorRO<'tx, T>> std::iter::Iterator
for DupWalker<'cursor, 'tx, T, CURSOR>
{
type Item = Result<(T::Key, T::Value), Error>;
fn next(&mut self) -> Option<Self::Item> {
let start = self.start.take();
if start.is_some() {
return start
}
self.cursor.next_dup().transpose()
}
}