skl/dynamic/list/
iterator.rs

1use super::{Allocator, EntryRef, NodePointer, RefCounter, SkipList, Version};
2use crate::{allocator::Node, State, Transfer};
3use core::{
4  borrow::Borrow,
5  ops::{Bound, RangeBounds},
6};
7use dbutils::equivalentor::{BytesComparator, BytesRangeComparator};
8
9/// An iterator over the skipmap (this iterator will yields all versions). The current state of the iterator can be cloned by
10/// simply value copying the struct.
11pub struct Iter<'a, S, C, A, RC, Q = [u8], R = core::ops::RangeFull>
12where
13  A: Allocator,
14  RC: RefCounter,
15  Q: ?Sized,
16  S: State,
17{
18  pub(super) map: &'a SkipList<C, A, RC>,
19  pub(super) version: Version,
20  pub(super) range: Option<R>,
21  pub(super) all_versions: bool,
22  pub(super) head: Option<EntryRef<'a, S, C, A, RC>>,
23  pub(super) tail: Option<EntryRef<'a, S, C, A, RC>>,
24  pub(super) _phantom: core::marker::PhantomData<Q>,
25}
26
27impl<'a, S, C, A, RC, Q, R> Clone for Iter<'a, S, C, A, RC, Q, R>
28where
29  A: Allocator,
30  RC: RefCounter,
31  Q: ?Sized,
32  R: Clone,
33  S: State,
34  S::Data<'a, &'a [u8]>: Clone,
35{
36  fn clone(&self) -> Self {
37    Self {
38      map: self.map,
39      head: self.head.clone(),
40      tail: self.tail.clone(),
41      version: self.version,
42      range: self.range.clone(),
43      all_versions: self.all_versions,
44      _phantom: core::marker::PhantomData,
45    }
46  }
47}
48
49impl<'a, S, C, A, RC, Q, R> Copy for Iter<'a, S, C, A, RC, Q, R>
50where
51  A: Allocator,
52  RC: RefCounter,
53  Q: ?Sized,
54  R: Copy,
55  S: State,
56  S::Data<'a, &'a [u8]>: Copy,
57{
58}
59
60impl<'a, S, C, A, RC> Iter<'a, S, C, A, RC>
61where
62  A: Allocator,
63  RC: RefCounter,
64  S: State,
65{
66  #[inline]
67  pub(crate) const fn new(
68    version: Version,
69    map: &'a SkipList<C, A, RC>,
70    all_versions: bool,
71  ) -> Self {
72    Self {
73      map,
74      head: None,
75      tail: None,
76      version,
77      range: None,
78      all_versions,
79      _phantom: core::marker::PhantomData,
80    }
81  }
82}
83
84impl<'a, S, C, A, RC, Q, R> Iter<'a, S, C, A, RC, Q, R>
85where
86  A: Allocator,
87  RC: RefCounter,
88  Q: ?Sized,
89  S: State,
90{
91  #[inline]
92  pub(crate) fn range(
93    version: Version,
94    map: &'a SkipList<C, A, RC>,
95    r: R,
96    all_versions: bool,
97  ) -> Self {
98    Self {
99      map,
100      head: None,
101      tail: None,
102      version,
103      range: Some(r),
104      all_versions,
105      _phantom: core::marker::PhantomData,
106    }
107  }
108}
109
110impl<'a, S, C, A, RC, Q, R> Iter<'a, S, C, A, RC, Q, R>
111where
112  A: Allocator,
113  RC: RefCounter,
114  R: RangeBounds<Q>,
115  Q: ?Sized,
116  S: State,
117{
118  /// Returns the start bound of the iterator.
119  #[inline]
120  pub fn start_bound(&self) -> Bound<&Q> {
121    self
122      .range
123      .as_ref()
124      .map(|r| r.start_bound())
125      .unwrap_or(Bound::Unbounded)
126  }
127
128  /// Returns the end bound of the iterator.
129  #[inline]
130  pub fn end_bound(&self) -> Bound<&Q> {
131    self
132      .range
133      .as_ref()
134      .map(|r| r.end_bound())
135      .unwrap_or(Bound::Unbounded)
136  }
137
138  /// Returns the entry at the current head position of the iterator.
139  #[inline]
140  pub const fn head(&self) -> Option<&EntryRef<'a, S, C, A, RC>> {
141    self.head.as_ref()
142  }
143
144  /// Returns the entry at the current tail position of the iterator.
145  #[inline]
146  pub const fn tail(&self) -> Option<&EntryRef<'a, S, C, A, RC>> {
147    self.tail.as_ref()
148  }
149}
150
151impl<'a, S, C, A, RC, Q, R> Iter<'a, S, C, A, RC, Q, R>
152where
153  A: Allocator,
154  C: BytesComparator,
155  RC: RefCounter,
156  Q: ?Sized + Borrow<[u8]>,
157  R: RangeBounds<Q>,
158  S: Transfer<'a, &'a [u8]>,
159  S::Data<'a, &'a [u8]>: Copy,
160{
161  /// Advances to the next position. Returns the key and value if the
162  /// iterator is pointing at a valid entry, and `None` otherwise.
163  fn next_in(&mut self) -> Option<EntryRef<'a, S, C, A, RC>> {
164    unsafe {
165      let mut next_head = match self.head.as_ref() {
166        Some(head) => self.map.get_next(head.ptr, 0),
167        None => self.map.get_next(self.map.head, 0),
168      };
169
170      let next_head = if self.all_versions {
171        self
172          .map
173          .move_to_next(&mut next_head, self.version, |nk| self.check_bounds(nk))
174      } else {
175        self
176          .map
177          .move_to_next_maximum_version(&mut next_head, self.version, |nk| {
178            if let Some(ref head) = self.head {
179              !self.map.cmp.equivalent(head.key(), nk) && self.check_bounds(nk)
180            } else {
181              self.check_bounds(nk)
182            }
183          })
184      };
185
186      match (&next_head, &self.tail) {
187        (Some(next), Some(t))
188          if next
189            .key()
190            .cmp(t.key())
191            .then_with(|| t.version.cmp(&next.version))
192            .is_ge() =>
193        {
194          self.head = next_head;
195          None
196        }
197        (Some(_), _) => {
198          self.head = next_head;
199          next_head
200        }
201        (None, _) => {
202          self.head = next_head;
203          None
204        }
205      }
206    }
207  }
208
209  /// Advances to the prev position. Returns the key and value if the
210  /// iterator is pointing at a valid entry, and `None` otherwise.
211  fn prev(&mut self) -> Option<EntryRef<'a, S, C, A, RC>> {
212    unsafe {
213      let mut next_tail = match self.tail.as_ref() {
214        Some(tail) => self.map.get_prev(tail.ptr, 0),
215        None => self.map.get_prev(self.map.tail, 0),
216      };
217
218      let next_tail = if self.all_versions {
219        self
220          .map
221          .move_to_prev(&mut next_tail, self.version, |nk| self.check_bounds(nk))
222      } else {
223        self
224          .map
225          .move_to_prev_maximum_version(&mut next_tail, self.version, |nk| {
226            if let Some(ref tail) = self.tail {
227              !self.map.cmp.equivalent(tail.key(), nk) && self.check_bounds(nk)
228            } else {
229              self.check_bounds(nk)
230            }
231          })
232      };
233
234      match (&self.head, &next_tail) {
235        // The prev key is smaller than the latest head key we observed with this iterator.
236        (Some(h), Some(next))
237          if h
238            .key()
239            .cmp(next.key())
240            .then_with(|| h.version.cmp(&next.version))
241            .is_ge() =>
242        {
243          self.tail = next_tail;
244          None
245        }
246        (_, Some(_)) => {
247          self.tail = next_tail;
248          next_tail
249        }
250        (_, None) => {
251          self.tail = next_tail;
252          None
253        }
254      }
255    }
256  }
257
258  fn range_next_in(&mut self) -> Option<EntryRef<'a, S, C, A, RC>> {
259    unsafe {
260      let mut next_head = match self.head.as_ref() {
261        Some(head) => self.map.get_next(head.ptr, 0),
262        None => match self.range.as_ref().unwrap().start_bound() {
263          Bound::Included(key) => self
264            .map
265            .find_near(self.version, key.borrow(), false, true)
266            .0
267            .unwrap_or(<A::Node as Node>::Pointer::NULL),
268          Bound::Excluded(key) => self
269            .map
270            .find_near(Version::MIN, key.borrow(), false, false)
271            .0
272            .unwrap_or(<A::Node as Node>::Pointer::NULL),
273          Bound::Unbounded => self.map.get_next(self.map.head, 0),
274        },
275      };
276
277      self.head = if self.all_versions {
278        self
279          .map
280          .move_to_next(&mut next_head, self.version, |nk| self.check_bounds(nk))
281      } else {
282        self
283          .map
284          .move_to_next_maximum_version(&mut next_head, self.version, |nk| {
285            if let Some(ref head) = self.head {
286              !self.map.cmp.equivalent(head.key(), nk) && self.check_bounds(nk)
287            } else {
288              self.check_bounds(nk)
289            }
290          })
291      };
292
293      if let Some(ref h) = self.head {
294        match &self.tail {
295          Some(t) => {
296            let bound = Bound::Excluded(t.key());
297            if !below_upper_bound(&self.map.cmp, bound, h.key()) {
298              self.head = None;
299              self.tail = None;
300            }
301          }
302          None => {
303            let bound = self.range.as_ref().unwrap().end_bound().map(|b| b.borrow());
304            if !below_upper_bound_compare(&self.map.cmp, bound, h.key()) {
305              self.head = None;
306              self.tail = None;
307            }
308          }
309        }
310      }
311
312      self.head
313    }
314  }
315
316  fn range_prev(&mut self) -> Option<EntryRef<'a, S, C, A, RC>> {
317    unsafe {
318      let mut next_tail = match self.tail.as_ref() {
319        Some(tail) => self.map.get_prev(tail.ptr, 0),
320        None => match self.range.as_ref().unwrap().end_bound() {
321          Bound::Included(key) => self
322            .map
323            .find_near(Version::MIN, key.borrow(), true, true)
324            .0
325            .unwrap_or(<A::Node as Node>::Pointer::NULL),
326          Bound::Excluded(key) => self
327            .map
328            .find_near(self.version, key.borrow(), true, false)
329            .0
330            .unwrap_or(<A::Node as Node>::Pointer::NULL),
331          Bound::Unbounded => self.map.get_prev(self.map.tail, 0),
332        },
333      };
334
335      self.tail = if self.all_versions {
336        self
337          .map
338          .move_to_prev(&mut next_tail, self.version, |nk| self.check_bounds(nk))
339      } else {
340        self
341          .map
342          .move_to_prev_maximum_version(&mut next_tail, self.version, |nk| {
343            if let Some(ref tail) = self.tail {
344              !self.map.cmp.equivalent(tail.key(), nk) && self.check_bounds(nk)
345            } else {
346              self.check_bounds(nk)
347            }
348          })
349      };
350
351      if let Some(ref t) = self.tail {
352        match &self.head {
353          Some(h) => {
354            let bound = Bound::Excluded(h.key());
355            if !above_lower_bound(&self.map.cmp, bound, t.key()) {
356              self.head = None;
357              self.tail = None;
358            }
359          }
360          None => {
361            let bound = self
362              .range
363              .as_ref()
364              .unwrap()
365              .start_bound()
366              .map(|b| b.borrow());
367            if !above_lower_bound_compare(&self.map.cmp, bound, t.key()) {
368              self.head = None;
369              self.tail = None;
370            }
371          }
372        }
373      }
374
375      self.tail
376    }
377  }
378}
379
380impl<'a, S, C, A, RC, Q, R> Iter<'a, S, C, A, RC, Q, R>
381where
382  A: Allocator,
383  C: BytesComparator,
384  RC: RefCounter,
385  Q: ?Sized + Borrow<[u8]>,
386  R: RangeBounds<Q>,
387  S: Transfer<'a, &'a [u8]>,
388  S::Data<'a, &'a [u8]>: Copy,
389{
390  /// Moves the iterator to the highest element whose key is below the given bound.
391  /// If no such element is found then `None` is returned.
392  ///
393  /// **Note:** This method will clear the current state of the iterator.
394  pub fn seek_upper_bound<QR>(&mut self, upper: Bound<&QR>) -> Option<EntryRef<'a, S, C, A, RC>>
395  where
396    QR: ?Sized + Borrow<[u8]>,
397  {
398    self.head = None;
399    self.tail = None;
400
401    match upper {
402      Bound::Included(key) => self.seek_le(key).inspect(|ent| {
403        self.head = Some(*ent);
404      }),
405      Bound::Excluded(key) => self.seek_lt(key).inspect(|ent| {
406        self.head = Some(*ent);
407      }),
408      Bound::Unbounded => self.last(),
409    }
410  }
411
412  /// Moves the iterator to the lowest element whose key is above the given bound.
413  /// If no such element is found then `None` is returned.
414  ///
415  /// **Note:** This method will clear the current state of the iterator.
416  pub fn seek_lower_bound<QR>(&mut self, lower: Bound<&QR>) -> Option<EntryRef<'a, S, C, A, RC>>
417  where
418    QR: ?Sized + Borrow<[u8]>,
419  {
420    self.head = None;
421    self.tail = None;
422
423    match lower {
424      Bound::Included(key) => self.seek_ge(key).inspect(|ent| {
425        self.head = Some(*ent);
426      }),
427      Bound::Excluded(key) => self.seek_gt(key).inspect(|ent| {
428        self.head = Some(*ent);
429      }),
430      Bound::Unbounded => self.first(),
431    }
432  }
433
434  /// Moves the iterator to the first entry whose key is greater than or
435  /// equal to the given key. Returns the key and value if the iterator is
436  /// pointing at a valid entry, and `None` otherwise.
437  fn seek_ge<QR>(&self, key: &QR) -> Option<EntryRef<'a, S, C, A, RC>>
438  where
439    QR: ?Sized + Borrow<[u8]>,
440  {
441    unsafe {
442      let (n, _) = self.map.find_near(self.version, key.borrow(), false, true);
443
444      let mut n = n?;
445      if n.is_null() || n.offset() == self.map.tail.offset() {
446        return None;
447      }
448
449      if self.all_versions {
450        self.map.move_to_next(&mut n, self.version, |nk| {
451          if let Some(ref range) = self.range {
452            self.map.cmp.compare_contains(range, nk)
453          } else {
454            true
455          }
456        })
457      } else {
458        self
459          .map
460          .move_to_next_maximum_version(&mut n, self.version, |nk| {
461            if let Some(ref range) = self.range {
462              self.map.cmp.compare_contains(range, nk)
463            } else {
464              true
465            }
466          })
467      }
468    }
469  }
470
471  /// Moves the iterator to the first entry whose key is greater than
472  /// the given key. Returns the key and value if the iterator is
473  /// pointing at a valid entry, and `None` otherwise.
474  fn seek_gt<QR>(&self, key: &QR) -> Option<EntryRef<'a, S, C, A, RC>>
475  where
476    QR: ?Sized + Borrow<[u8]>,
477  {
478    unsafe {
479      let (n, _) = self.map.find_near(Version::MIN, key.borrow(), false, false);
480
481      let mut n = n?;
482      if n.is_null() || n.offset() == self.map.tail.offset() {
483        return None;
484      }
485
486      if self.all_versions {
487        self.map.move_to_next(&mut n, self.version, |nk| {
488          if let Some(ref range) = self.range {
489            self.map.cmp.compare_contains(range, nk)
490          } else {
491            true
492          }
493        })
494      } else {
495        self
496          .map
497          .move_to_next_maximum_version(&mut n, self.version, |nk| {
498            if let Some(ref range) = self.range {
499              self.map.cmp.compare_contains(range, nk)
500            } else {
501              true
502            }
503          })
504      }
505    }
506  }
507
508  /// Moves the iterator to the first entry whose key is less than or
509  /// equal to the given key. Returns the key and value if the iterator is
510  /// pointing at a valid entry, and `None` otherwise.
511  fn seek_le<QR>(&self, key: &QR) -> Option<EntryRef<'a, S, C, A, RC>>
512  where
513    QR: ?Sized + Borrow<[u8]>,
514  {
515    unsafe {
516      let (n, _) = self.map.find_near(Version::MIN, key.borrow(), true, true); // find less or equal.
517
518      let mut n = n?;
519      if n.is_null() || n.offset() == self.map.head.offset() {
520        return None;
521      }
522
523      if self.all_versions {
524        self.map.move_to_prev(&mut n, self.version, |nk| {
525          if let Some(ref range) = self.range {
526            self.map.cmp.compare_contains(range, nk)
527          } else {
528            true
529          }
530        })
531      } else {
532        self
533          .map
534          .move_to_prev_maximum_version(&mut n, self.version, |nk| {
535            if let Some(ref range) = self.range {
536              self.map.cmp.compare_contains(range, nk)
537            } else {
538              true
539            }
540          })
541      }
542    }
543  }
544
545  /// Moves the iterator to the last entry whose key is less than the given
546  /// key. Returns the key and value if the iterator is pointing at a valid entry,
547  /// and `None` otherwise.
548  fn seek_lt<QR>(&self, key: &QR) -> Option<EntryRef<'a, S, C, A, RC>>
549  where
550    QR: ?Sized + Borrow<[u8]>,
551  {
552    unsafe {
553      let (n, _) = self.map.find_near(self.version, key.borrow(), true, false); // find less or equal.
554
555      let mut n = n?;
556      if n.is_null() || n.offset() == self.map.head.offset() {
557        return None;
558      }
559
560      if self.all_versions {
561        self.map.move_to_prev(&mut n, self.version, |nk| {
562          if let Some(ref range) = self.range {
563            self.map.cmp.compare_contains(range, nk)
564          } else {
565            true
566          }
567        })
568      } else {
569        self
570          .map
571          .move_to_prev_maximum_version(&mut n, self.version, |nk| self.check_bounds(nk))
572      }
573    }
574  }
575
576  #[inline]
577  fn first(&mut self) -> Option<EntryRef<'a, S, C, A, RC>> {
578    self.head = None;
579    self.tail = None;
580    self.next()
581  }
582
583  #[inline]
584  fn last(&mut self) -> Option<EntryRef<'a, S, C, A, RC>> {
585    self.tail = None;
586    self.head = None;
587    self.prev()
588  }
589
590  #[inline]
591  fn check_bounds(&self, nk: &[u8]) -> bool {
592    if let Some(ref range) = self.range {
593      self.map.cmp.compare_contains(range, nk)
594    } else {
595      true
596    }
597  }
598}
599
600impl<'a, S, C, A, RC, Q, R> Iterator for Iter<'a, S, C, A, RC, Q, R>
601where
602  A: Allocator,
603  C: BytesComparator,
604  RC: RefCounter,
605  Q: ?Sized + Borrow<[u8]>,
606  R: RangeBounds<Q>,
607  S: Transfer<'a, &'a [u8]>,
608  S::Data<'a, &'a [u8]>: Copy,
609{
610  type Item = EntryRef<'a, S, C, A, RC>;
611
612  #[inline]
613  fn next(&mut self) -> Option<Self::Item> {
614    if self.range.is_some() {
615      self.range_next_in()
616    } else {
617      self.next_in()
618    }
619  }
620
621  #[inline]
622  fn last(mut self) -> Option<Self::Item>
623  where
624    Self: Sized,
625  {
626    Iter::last(&mut self)
627  }
628
629  #[inline]
630  fn max(self) -> Option<Self::Item>
631  where
632    Self: Sized,
633    Self::Item: Ord,
634  {
635    self.last()
636  }
637
638  #[inline]
639  fn min(mut self) -> Option<Self::Item>
640  where
641    Self: Sized,
642    Self::Item: Ord,
643  {
644    self.first()
645  }
646}
647
648impl<'a, S, C, A, RC, Q, R> DoubleEndedIterator for Iter<'a, S, C, A, RC, Q, R>
649where
650  A: Allocator,
651  C: BytesComparator,
652  RC: RefCounter,
653  Q: ?Sized + Borrow<[u8]>,
654  R: RangeBounds<Q>,
655  S: Transfer<'a, &'a [u8]>,
656  S::Data<'a, &'a [u8]>: Copy,
657{
658  #[inline]
659  fn next_back(&mut self) -> Option<Self::Item> {
660    if self.range.is_some() {
661      self.range_prev()
662    } else {
663      self.prev()
664    }
665  }
666}
667
668/// Helper function to check if a value is above a lower bound
669fn above_lower_bound_compare<C: BytesComparator>(
670  cmp: &C,
671  bound: Bound<&[u8]>,
672  other: &[u8],
673) -> bool {
674  match bound {
675    Bound::Unbounded => true,
676    Bound::Included(key) => cmp.compare(key, other).is_le(),
677    Bound::Excluded(key) => cmp.compare(key, other).is_lt(),
678  }
679}
680
681/// Helper function to check if a value is above a lower bound
682fn above_lower_bound<C: BytesComparator>(cmp: &C, bound: Bound<&[u8]>, other: &[u8]) -> bool {
683  match bound {
684    Bound::Unbounded => true,
685    Bound::Included(key) => cmp.compare(key, other).is_le(),
686    Bound::Excluded(key) => cmp.compare(key, other).is_lt(),
687  }
688}
689
690/// Helper function to check if a value is below an upper bound
691fn below_upper_bound_compare<C: BytesComparator>(
692  cmp: &C,
693  bound: Bound<&[u8]>,
694  other: &[u8],
695) -> bool {
696  match bound {
697    Bound::Unbounded => true,
698    Bound::Included(key) => cmp.compare(key, other).is_ge(),
699    Bound::Excluded(key) => cmp.compare(key, other).is_gt(),
700  }
701}
702
703/// Helper function to check if a value is below an upper bound
704fn below_upper_bound<C: BytesComparator>(cmp: &C, bound: Bound<&[u8]>, other: &[u8]) -> bool {
705  match bound {
706    Bound::Unbounded => true,
707    Bound::Included(key) => cmp.compare(key, other).is_ge(),
708    Bound::Excluded(key) => cmp.compare(key, other).is_gt(),
709  }
710}
skl/dynamic/list/iterator.rs

skl/dynamic/list/
iterator.rs
