seekable_iterator/
seekable.rs

1use crate::comparator::Comparator;
2use crate::lending_iterator_support::{LendItem, LentItem};
3
4
5/// A trait adding seek functionality to one of the cursor iterator traits.
6///
7/// See [`CursorIterator`], [`CursorLendingIterator`], or [`CursorPooledIterator`] for more.
8///
9/// Additionally, the keys of implementors must be sorted by a comparator of the indicated
10/// [`Comparator`] type.
11///
12/// Implementors of `Seekable` and [`CursorLendingIterator`] should strongly consider implementing
13/// [`ItemToKey`] as well.
14///
15/// [`CursorIterator`]: crate::cursor::CursorIterator
16/// [`CursorLendingIterator`]: crate::cursor::CursorLendingIterator
17/// [`CursorPooledIterator`]: crate::cursor::CursorPooledIterator
18pub trait Seekable<Key: ?Sized, Cmp: ?Sized + Comparator<Key>> {
19    /// Reset the iterator to its initial position, before the first entry and after the last
20    /// entry (if there are any entries in the collection).
21    ///
22    /// The iterator becomes `!valid()`, and is conceptually one position before the first entry
23    /// and one position after the last entry (if there are any entries in the collection).
24    fn reset(&mut self);
25
26    /// Move the iterator to the smallest key which is greater or equal than the provided
27    /// `min_bound`.
28    ///
29    /// If there is no such key, the iterator becomes `!valid()`, and is conceptually
30    /// one position before the first entry and one position after the last entry (if there are
31    /// any entries in the collection).
32    fn seek(&mut self, min_bound: &Key);
33
34    /// Move the iterator to the greatest key which is strictly less than the provided
35    /// `strict_upper_bound`.
36    ///
37    /// If there is no such key, the iterator becomes `!valid()`, and is conceptually
38    /// one position before the first entry and one position after the last entry (if there are
39    /// any entries in the collection).
40    ///
41    /// Some implementations may have worse performance for `seek_before` than [`seek`].
42    ///
43    /// [`seek`]: Seekable::seek
44    fn seek_before(&mut self, strict_upper_bound: &Key);
45
46    /// Move the iterator to the smallest key in the collection.
47    ///
48    /// If the collection is empty, the iterator is `!valid()`.
49    fn seek_to_first(&mut self);
50
51    /// Move the iterator to the greatest key in the collection.
52    ///
53    /// If the collection is empty, the iterator is `!valid()`.
54    fn seek_to_last(&mut self);
55}
56
57/// Convert one of the items of an iterator into a `Key` reference, intended for use with a
58/// [`SeekableLendingIterator`].
59///
60/// This conversion is expected to be cheap.
61///
62/// [`SeekableLendingIterator`]: crate::seekable_iterators::SeekableLendingIterator
63pub trait ItemToKey<Key: ?Sized>: for<'lend> LendItem<'lend> {
64    /// Convert one of the items of an iterator into a `Key` reference, intended for use with
65    /// a [`SeekableLendingIterator`].
66    ///
67    /// This conversion is expected to be cheap.
68    ///
69    /// [`SeekableLendingIterator`]: crate::seekable_iterators::SeekableLendingIterator
70    #[must_use]
71    fn item_to_key(item: LentItem<'_, Self>) -> &'_ Key;
72}
73
74#[cfg(any(feature = "lender", feature = "lending-iterator"))]
75macro_rules! delegate_seekable {
76    ($struct_name:ident.$field:tt $($extra_i_bounds:tt)*) => {
77        impl<Key, Cmp, I> Seekable<Key, Cmp> for $struct_name<I>
78        where
79            Key: ?Sized,
80            Cmp: ?Sized + Comparator<Key>,
81            I:   Seekable<Key, Cmp> + $($extra_i_bounds)*,
82        {
83            #[inline]
84            fn reset(&mut self) {
85                self.$field.reset();
86            }
87
88            #[inline]
89            fn seek(&mut self, min_bound: &Key) {
90                self.$field.seek(min_bound);
91            }
92
93            #[inline]
94            fn seek_before(&mut self, strict_upper_bound: &Key) {
95                self.$field.seek_before(strict_upper_bound);
96            }
97
98            #[inline]
99            fn seek_to_first(&mut self) {
100                self.$field.seek_to_first();
101            }
102
103            #[inline]
104            fn seek_to_last(&mut self) {
105                self.$field.seek_to_last();
106            }
107        }
108    };
109}
110
111#[cfg(any(feature = "lender", feature = "lending-iterator"))]
112pub(crate) use delegate_seekable;
seekable_iterator/seekable.rs

seekable_iterator/
seekable.rs
