memorable/bounded/generic/
iter.rs

1use super::{
2  BulkDeletionEntry, BulkUpdateEntry, Entry, EntryValue, Memtable, PhantomRangeDeletionSpan,
3  PhantomRangeKey, PhantomRangeUpdateSpan, Query, QueryRange,
4};
5use core::ops::{ControlFlow, RangeBounds};
6use skl::generic::{
7  multiple_version::{
8    sync::{Iter as MapIter, IterAll, Range as MapRange, RangeAll},
9    Map,
10  },
11  Comparable, KeyRef, Type,
12};
13
14/// An iterator over the point entries (bulk-deletion and bulk-update operations will be ignored) of a `Memtable`.
15pub type IterAllPoints<'a, K, V> = IterAll<'a, K, V>;
16
17/// An iterator over the point entries (bulk-deletion and bulk-update operations will be ignored) of a `Memtable` within the specified range.
18pub type RangeAllPoints<'a, K, V, Q, R> = RangeAll<'a, K, V, Q, R>;
19
20/// An iterator over the entries of a `Memtable`.
21pub struct Iter<'a, K, V>
22where
23  K: ?Sized + Type,
24  V: ?Sized + Type,
25{
26  table: &'a Memtable<K, V>,
27  iter: MapIter<'a, K, V>,
28  query_version: u64,
29}
30
31impl<'a, K, V> Iter<'a, K, V>
32where
33  K: ?Sized + Type + 'static,
34  for<'b> K::Ref<'b>: KeyRef<'b, K>,
35  V: ?Sized + Type + 'static,
36{
37  pub(super) fn new(version: u64, table: &'a Memtable<K, V>) -> Self {
38    Self {
39      iter: table.inner.skl.iter(version),
40      query_version: version,
41      table,
42    }
43  }
44}
45
46impl<'a, K, V> Iterator for Iter<'a, K, V>
47where
48  K: ?Sized + Type + 'static,
49  for<'b> K::Ref<'b>: KeyRef<'b, K>,
50  V: ?Sized + Type + 'static,
51{
52  type Item = Entry<'a, K, V>;
53
54  #[inline]
55  fn next(&mut self) -> Option<Self::Item> {
56    loop {
57      let next = self.iter.next()?;
58      match self.table.validate(self.query_version, next) {
59        ControlFlow::Break(entry) => return entry,
60        ControlFlow::Continue(_) => continue,
61      }
62    }
63  }
64}
65
66impl<K, V> DoubleEndedIterator for Iter<'_, K, V>
67where
68  K: ?Sized + Type + 'static,
69  for<'b> K::Ref<'b>: KeyRef<'b, K>,
70  V: ?Sized + Type + 'static,
71{
72  #[inline]
73  fn next_back(&mut self) -> Option<Self::Item> {
74    loop {
75      let prev = self.iter.next_back()?;
76      match self.table.validate(self.query_version, prev) {
77        ControlFlow::Break(entry) => return entry,
78        ControlFlow::Continue(_) => continue,
79      }
80    }
81  }
82}
83
84/// An iterator over the entries of a `Memtable`.
85pub struct Range<'a, K, V, Q, R>
86where
87  K: ?Sized + Type + 'static,
88  for<'b> K::Ref<'b>: KeyRef<'b, K>,
89  V: ?Sized + Type + 'static,
90  R: RangeBounds<Q>,
91  Q: ?Sized + Comparable<K::Ref<'a>>,
92{
93  table: &'a Memtable<K, V>,
94  iter: MapRange<'a, K, V, Q, R>,
95  query_version: u64,
96}
97
98impl<'a, K, V, Q, R> Range<'a, K, V, Q, R>
99where
100  K: ?Sized + Type + 'static,
101  for<'b> K::Ref<'b>: KeyRef<'b, K>,
102  V: ?Sized + Type + 'static,
103  R: RangeBounds<Q>,
104  Q: ?Sized + Comparable<K::Ref<'a>>,
105{
106  pub(super) fn new(version: u64, table: &'a Memtable<K, V>, r: R) -> Self {
107    Self {
108      iter: table.inner.skl.range(version, r),
109      query_version: version,
110      table,
111    }
112  }
113}
114
115impl<'a, K, V, Q, R> Iterator for Range<'a, K, V, Q, R>
116where
117  K: ?Sized + Type + 'static,
118  for<'b> K::Ref<'b>: KeyRef<'b, K>,
119  V: ?Sized + Type + 'static,
120  R: RangeBounds<Q>,
121  Q: ?Sized + Comparable<K::Ref<'a>>,
122{
123  type Item = Entry<'a, K, V>;
124
125  #[inline]
126  fn next(&mut self) -> Option<Self::Item> {
127    loop {
128      let next = self.iter.next()?;
129      match self.table.validate(self.query_version, next) {
130        ControlFlow::Break(entry) => return entry,
131        ControlFlow::Continue(_) => continue,
132      }
133    }
134  }
135}
136
137impl<'a, K, V, Q, R> DoubleEndedIterator for Range<'a, K, V, Q, R>
138where
139  K: ?Sized + Type + 'static,
140  for<'b> K::Ref<'b>: KeyRef<'b, K>,
141  V: ?Sized + Type + 'static,
142  R: RangeBounds<Q>,
143  Q: ?Sized + Comparable<K::Ref<'a>>,
144{
145  #[inline]
146  fn next_back(&mut self) -> Option<Self::Item> {
147    loop {
148      let prev = self.iter.next_back()?;
149      match self.table.validate(self.query_version, prev) {
150        ControlFlow::Break(entry) => return entry,
151        ControlFlow::Continue(_) => continue,
152      }
153    }
154  }
155}
156
157macro_rules! bulk_iter {
158  (
159    $(
160      $(#[$meta:meta])*
161      $name:ident::<$span:ty>::$new:ident($iter:ident, $entry:ident).$iterator:ident.$method:ident
162    ), +$(,)?
163  ) => {
164    $(
165      $(#[$meta])*
166      pub struct $name<'a, K, V>
167      where
168        K: ?Sized + Type,
169        for<'b> K::Ref<'b>: KeyRef<'b, K>,
170        V: ?Sized + Type,
171      {
172        table: &'a Memtable<K, V>,
173        iter: $iter<'a, PhantomRangeKey<K>, $span>,
174        query_version: u64,
175      }
176
177      impl<'a, K, V> $name<'a, K, V>
178      where
179        K: ?Sized + Type + 'static,
180        for<'b> K::Ref<'b>: KeyRef<'b, K>,
181        V: ?Sized + Type + 'static,
182      {
183        #[inline]
184        pub(super) fn new(version: u64, table: &'a Memtable<K, V>) -> Self {
185          Self {
186            iter: table.inner.$iterator.$method(version),
187            query_version: version,
188            table,
189          }
190        }
191      }
192
193      impl<'a, K, V> Iterator for $name<'a, K, V>
194      where
195        K: ?Sized + Type,
196        for<'b> K::Ref<'b>: KeyRef<'b, K>,
197        V: ?Sized + Type,
198      {
199        type Item = $entry<'a, K, V>;
200
201        #[inline]
202        fn next(&mut self) -> Option<Self::Item> {
203          self
204            .iter
205            .next()
206            .map(|ent| $entry::$new(self.table, self.query_version, ent))
207        }
208      }
209
210      impl<K, V> DoubleEndedIterator for $name<'_, K, V>
211      where
212        K: ?Sized + Type,
213        for<'b> K::Ref<'b>: KeyRef<'b, K>,
214        V: ?Sized + Type,
215      {
216        #[inline]
217        fn next_back(&mut self) -> Option<Self::Item> {
218          self
219            .iter
220            .next_back()
221            .map(|ent| $entry::$new(self.table, self.query_version, ent))
222        }
223      }
224    )*
225  };
226}
227
228bulk_iter!(
229  /// An iterator over the range deletion entries of a `Memtable`.
230  BulkDeletionIter::<PhantomRangeDeletionSpan<K>>::new(MapIter, BulkDeletionEntry).range_del_skl.iter,
231  /// An iterator over the range update entries of a `Memtable`.
232  BulkUpdateIter::<PhantomRangeUpdateSpan<K, V>>::new(MapIter, BulkUpdateEntry).range_key_skl.iter,
233  /// An iterator over the range deletion entries of a `Memtable`.
234  BulkDeletionIterAll::<PhantomRangeDeletionSpan<K>>::versioned(IterAll, BulkDeletionEntry).range_del_skl.iter_all_versions,
235  /// An iterator over the range update entries of a `Memtable`.
236  BulkUpdateIterAll::<PhantomRangeUpdateSpan<K, V>>::versioned(IterAll, BulkUpdateEntry).range_key_skl.iter_all_versions,
237);
238
239macro_rules! bulk_range {
240  (
241    $(
242      $(#[$meta:meta])*
243      $name:ident::<$span:ty>::$new:ident($iter:ident, $entry:ident).$iterator:ident.$method:ident
244    ), +$(,)?
245  ) => {
246    $(
247      $(#[$meta])*
248      pub struct $name<'a, K, V, Q, R>
249      where
250        K: ?Sized + Type,
251        for<'b> K::Ref<'b>: KeyRef<'b, K>,
252        V: ?Sized + Type,
253        R: RangeBounds<Q>,
254        Q: ?Sized + Comparable<K::Ref<'a>>,
255      {
256        table: &'a Memtable<K, V>,
257        iter: $iter<'a, PhantomRangeKey<K>, $span, Query<Q>, QueryRange<Q, R>>,
258        query_version: u64,
259      }
260
261      impl<'a, K, V, Q, R> $name<'a, K, V, Q, R>
262      where
263        K: ?Sized + Type + 'static,
264        for<'b> K::Ref<'b>: KeyRef<'b, K>,
265        V: ?Sized + Type + 'static,
266        R: RangeBounds<Q>,
267        Q: ?Sized + Comparable<K::Ref<'a>>,
268      {
269        pub(super) fn new(version: u64, table: &'a Memtable<K, V>, range: R) -> Self {
270          Self {
271            iter: table
272              .inner
273              .$iterator
274              .$method(version, QueryRange::new(range)),
275            query_version: version,
276            table,
277          }
278        }
279      }
280
281      impl<'a, K, V, Q, R> Iterator for $name<'a, K, V, Q, R>
282      where
283        K: ?Sized + Type,
284        for<'b> K::Ref<'b>: KeyRef<'b, K>,
285        V: ?Sized + Type,
286        R: RangeBounds<Q>,
287        Q: ?Sized + Comparable<K::Ref<'a>>,
288      {
289        type Item = $entry<'a, K, V>;
290
291        #[inline]
292        fn next(&mut self) -> Option<Self::Item> {
293          self
294            .iter
295            .next()
296            .map(|ent| $entry::$new(self.table, self.query_version, ent))
297        }
298      }
299
300      impl<'a, K, V, Q, R> DoubleEndedIterator for $name<'a, K, V, Q, R>
301      where
302        K: ?Sized + Type,
303        for<'b> K::Ref<'b>: KeyRef<'b, K>,
304        V: ?Sized + Type,
305        R: RangeBounds<Q>,
306        Q: ?Sized + Comparable<K::Ref<'a>>,
307      {
308        #[inline]
309        fn next_back(&mut self) -> Option<Self::Item> {
310          self
311            .iter
312            .next_back()
313            .map(|ent| $entry::$new(self.table, self.query_version, ent))
314        }
315      }
316    )*
317  }
318}
319
320bulk_range!(
321  /// An iterator over the range deletion entries of a `Memtable`.
322  BulkDeletionRange::<PhantomRangeDeletionSpan<K>>::new(MapRange, BulkDeletionEntry).range_del_skl.range,
323  /// An iterator over the range update entries of a `Memtable`.
324  BulkUpdateRange::<PhantomRangeUpdateSpan<K, V>>::new(MapRange, BulkUpdateEntry).range_key_skl.range,
325  /// An iterator over the range deletion entries (all versions) of a `Memtable`.
326  BulkDeletionRangeAll::<PhantomRangeDeletionSpan<K>>::versioned(RangeAll, BulkDeletionEntry).range_del_skl.range_all_versions,
327  /// An iterator over the range update entries (all versions) of a `Memtable`.
328  BulkUpdateRangeAll::<PhantomRangeUpdateSpan<K, V>>::versioned(RangeAll, BulkUpdateEntry).range_key_skl.range_all_versions,
329);
330
331/// An iterator over the point entries (bulk-deletion and bulk-update operations will be ignored) of a `Memtable`.
332pub struct PointIter<'a, K, V>
333where
334  K: ?Sized + Type,
335  V: ?Sized + Type,
336{
337  table: &'a Memtable<K, V>,
338  iter: MapIter<'a, K, V>,
339  query_version: u64,
340}
341
342impl<'a, K, V> PointIter<'a, K, V>
343where
344  K: ?Sized + Type + 'static,
345  for<'b> K::Ref<'b>: KeyRef<'b, K>,
346  V: ?Sized + Type + 'static,
347{
348  pub(super) fn new(version: u64, table: &'a Memtable<K, V>) -> Self {
349    Self {
350      iter: table.inner.skl.iter(version),
351      query_version: version,
352      table,
353    }
354  }
355}
356
357impl<'a, K, V> Iterator for PointIter<'a, K, V>
358where
359  K: ?Sized + Type + 'static,
360  for<'b> K::Ref<'b>: KeyRef<'b, K>,
361  V: ?Sized + Type + 'static,
362{
363  type Item = Entry<'a, K, V>;
364
365  #[inline]
366  fn next(&mut self) -> Option<Self::Item> {
367    self.iter.next().map(|ent| {
368      let val = *ent.value();
369      Entry::new(self.table, self.query_version, ent, EntryValue::Point(val))
370    })
371  }
372}
373
374impl<K, V> DoubleEndedIterator for PointIter<'_, K, V>
375where
376  K: ?Sized + Type + 'static,
377  for<'b> K::Ref<'b>: KeyRef<'b, K>,
378  V: ?Sized + Type + 'static,
379{
380  #[inline]
381  fn next_back(&mut self) -> Option<Self::Item> {
382    self.iter.next_back().map(|ent| {
383      let val = *ent.value();
384      Entry::new(self.table, self.query_version, ent, EntryValue::Point(val))
385    })
386  }
387}
388
389/// An iterator over the point entries (bulk-deletion and bulk-update operations will be ignored) of a `Memtable` with in a specified range.
390pub struct PointRange<'a, K, V, Q, R>
391where
392  K: ?Sized + Type + 'static,
393  for<'b> K::Ref<'b>: KeyRef<'b, K>,
394  V: ?Sized + Type + 'static,
395  R: RangeBounds<Q>,
396  Q: ?Sized + Comparable<K::Ref<'a>>,
397{
398  table: &'a Memtable<K, V>,
399  iter: MapRange<'a, K, V, Q, R>,
400  query_version: u64,
401}
402
403impl<'a, K, V, Q, R> PointRange<'a, K, V, Q, R>
404where
405  K: ?Sized + Type + 'static,
406  for<'b> K::Ref<'b>: KeyRef<'b, K>,
407  V: ?Sized + Type + 'static,
408  R: RangeBounds<Q>,
409  Q: ?Sized + Comparable<K::Ref<'a>>,
410{
411  pub(super) fn new(version: u64, table: &'a Memtable<K, V>, r: R) -> Self {
412    Self {
413      iter: table.inner.skl.range(version, r),
414      query_version: version,
415      table,
416    }
417  }
418}
419
420impl<'a, K, V, Q, R> Iterator for PointRange<'a, K, V, Q, R>
421where
422  K: ?Sized + Type + 'static,
423  for<'b> K::Ref<'b>: KeyRef<'b, K>,
424  V: ?Sized + Type + 'static,
425  R: RangeBounds<Q>,
426  Q: ?Sized + Comparable<K::Ref<'a>>,
427{
428  type Item = Entry<'a, K, V>;
429
430  #[inline]
431  fn next(&mut self) -> Option<Self::Item> {
432    self.iter.next().map(|ent| {
433      let val = *ent.value();
434      Entry::new(self.table, self.query_version, ent, EntryValue::Point(val))
435    })
436  }
437}
438
439impl<'a, K, V, Q, R> DoubleEndedIterator for PointRange<'a, K, V, Q, R>
440where
441  K: ?Sized + Type + 'static,
442  for<'b> K::Ref<'b>: KeyRef<'b, K>,
443  V: ?Sized + Type + 'static,
444  R: RangeBounds<Q>,
445  Q: ?Sized + Comparable<K::Ref<'a>>,
446{
447  #[inline]
448  fn next_back(&mut self) -> Option<Self::Item> {
449    self.iter.next_back().map(|ent| {
450      let val = *ent.value();
451      Entry::new(self.table, self.query_version, ent, EntryValue::Point(val))
452    })
453  }
454}
memorable/bounded/generic/iter.rs

memorable/bounded/generic/
iter.rs
