seekable_iterator/
pooled_iter.rs

1use core::{
2    borrow::{Borrow, BorrowMut},
3    ops::{Deref, DerefMut},
4};
5use alloc::borrow::ToOwned;
6
7use anchored_pool::{PooledResource, ResetNothing, ResourcePoolEmpty, BoundedPool};
8
9use crate::{comparator::Comparator, lending_iterator_support::LentItem, seekable::Seekable};
10use crate::{
11    pooled::{OutOfBuffers, PooledIterator},
12    cursor::{CursorLendingIterator, CursorPooledIterator},
13};
14
15
16/// Convert a [`CursorLendingIterator`] into a [`CursorPooledIterator`] by storing recently
17/// accessed items in reusable buffers.
18///
19/// This effectively allows the iterator to lend out multiple items at once, unlike a lending
20/// iterator which can only lend out one. This comes primarily at the cost of extra copying
21/// into buffers, and in memory usage. The costs of allocating buffers is likely amortized by
22/// their reuse.
23///
24/// The user of a `PooledIter` is required not to attempt to get more [`PoolItem`]s than there
25/// are buffers in the `PooledIter`; because `PooledIter` can only be used from a single thread,
26/// it is impossible for a buffer to be returned to the iterator while [`PooledIter::next`]
27/// is running, for example, unlike with the `ThreadsafePooledIter` type. Therefore, `PooledIter`
28/// panics in such a scenario.
29#[derive(Debug)]
30#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
31pub struct PooledIter<I, BorrowedItem: ToOwned> {
32    iter: I,
33    pool: BoundedPool<BorrowedItem::Owned, ResetNothing>,
34}
35
36impl<I, BorrowedItem> PooledIter<I, BorrowedItem>
37where
38    BorrowedItem:        ToOwned,
39    BorrowedItem::Owned: Default,
40{
41    /// Create a `PooledIter` that can lend out up to `num_buffers` items at a time.
42    ///
43    /// The user of a `PooledIter` is required not to attempt to get more than `num_buffers`
44    /// [`PoolItem`]s from this `PooledIter` at a time; because `PooledIter` can only be used from
45    /// a single thread, it is impossible for a buffer to be returned to the iterator while
46    /// [`PooledIter::next`] is running, for example, unlike with the `ThreadsafePooledIter` type.
47    /// Therefore, `PooledIter` panics in such a scenario.
48    #[must_use]
49    pub fn new(iter: I, num_buffers: usize) -> Self {
50        let pool = BoundedPool::new_default_without_reset(num_buffers);
51
52        Self { iter, pool }
53    }
54}
55
56impl<I, BorrowedItem> PooledIter<I, BorrowedItem>
57where
58    I:                             CursorLendingIterator,
59    BorrowedItem:                  ToOwned,
60    for<'lend> LentItem<'lend, I>: Borrow<BorrowedItem>,
61{
62    /// # Panics
63    /// Panics if there are no buffers available.
64    #[expect(clippy::needless_pass_by_value, reason = "lent item usually consists of references")]
65    #[inline]
66    fn fill_buffer(
67        pool: &BoundedPool<BorrowedItem::Owned, ResetNothing>,
68        item: LentItem<'_, I>,
69    ) -> PoolItem<BorrowedItem::Owned> {
70        let mut pool_item = pool.get();
71        item.borrow().clone_into(&mut pool_item);
72        PoolItem(pool_item)
73    }
74}
75
76impl<I, BorrowedItem> PooledIterator for PooledIter<I, BorrowedItem>
77where
78    I:                             CursorLendingIterator,
79    BorrowedItem:                  ToOwned,
80    for<'lend> LentItem<'lend, I>: Borrow<BorrowedItem>,
81{
82    type Item = PoolItem<BorrowedItem::Owned>;
83
84    /// Move the iterator one position forwards, and return the entry at that position.
85    /// Returns `None` if the iterator was at the last entry.
86    ///
87    /// # Panics
88    /// Panics if there are no buffers available.
89    fn next(&mut self) -> Option<Self::Item> {
90        self.iter.next().map(|item| Self::fill_buffer(&self.pool, item))
91    }
92
93    fn try_next(&mut self) -> Result<Option<Self::Item>, OutOfBuffers> {
94        let mut buffer = self.pool.try_get()
95            .map_err(|ResourcePoolEmpty| OutOfBuffers)?;
96
97        if let Some(item) = self.iter.next() {
98            item.borrow().clone_into(&mut buffer);
99            Ok(Some(PoolItem(buffer)))
100        } else {
101            Ok(None)
102        }
103    }
104
105    #[inline]
106    fn buffer_pool_size(&self) -> usize {
107        self.pool.pool_size()
108    }
109
110    fn available_buffers(&self) -> usize {
111        self.pool.available_resources()
112    }
113}
114
115impl<I, BorrowedItem> CursorPooledIterator for PooledIter<I, BorrowedItem>
116where
117    I:                             CursorLendingIterator,
118    BorrowedItem:                  ToOwned,
119    for<'lend> LentItem<'lend, I>: Borrow<BorrowedItem>,
120{
121    #[inline]
122    fn valid(&self) -> bool {
123        self.iter.valid()
124    }
125
126    /// Get the current value the iterator is at, if the iterator is [valid].
127    ///
128    /// # Panics
129    /// Panics if there are no buffers available.
130    ///
131    /// [valid]: CursorPooledIterator::valid
132    #[inline]
133    fn current(&self) -> Option<Self::Item> {
134        self.iter.current().map(|item| Self::fill_buffer(&self.pool, item))
135    }
136
137    fn try_current(&self) -> Result<Option<Self::Item>, OutOfBuffers> {
138        let mut buffer = self.pool.try_get()
139            .map_err(|ResourcePoolEmpty| OutOfBuffers)?;
140
141        if let Some(item) = self.iter.current() {
142            item.borrow().clone_into(&mut buffer);
143            Ok(Some(PoolItem(buffer)))
144        } else {
145            Ok(None)
146        }
147    }
148
149    /// Move the iterator one position back, and return the entry at that position.
150    /// Returns `None` if the iterator was at the first entry.
151    ///
152    /// Some iterator implementations used as `I` may have worse performance for backwards
153    /// iteration than forwards iteration, so prefer to not use `prev`.
154    ///
155    /// # Panics
156    /// Panics if there are no buffers available.
157    fn prev(&mut self) -> Option<Self::Item> {
158        self.iter.prev().map(|item| Self::fill_buffer(&self.pool, item))
159    }
160
161    fn try_prev(&mut self) -> Result<Option<Self::Item>, OutOfBuffers> {
162        let mut buffer = self.pool.try_get()
163            .map_err(|ResourcePoolEmpty| OutOfBuffers)?;
164
165        if let Some(item) = self.iter.prev() {
166            item.borrow().clone_into(&mut buffer);
167            Ok(Some(PoolItem(buffer)))
168        } else {
169            Ok(None)
170        }
171    }
172}
173
174impl<I, BorrowedItem, Key, Cmp> Seekable<Key, Cmp> for PooledIter<I, BorrowedItem>
175where
176    I:                             CursorLendingIterator + Seekable<Key, Cmp>,
177    BorrowedItem:                  ToOwned,
178    Key:                           ?Sized,
179    Cmp:                           Comparator<Key>,
180    for<'lend> LentItem<'lend, I>: Borrow<BorrowedItem>,
181{
182    #[inline]
183    fn reset(&mut self) {
184        self.iter.reset();
185    }
186
187    fn seek(&mut self, min_bound: &Key) {
188        self.iter.seek(min_bound);
189    }
190
191    fn seek_before(&mut self, strict_upper_bound: &Key) {
192        self.iter.seek_before(strict_upper_bound);
193    }
194
195    #[inline]
196    fn seek_to_first(&mut self) {
197        self.iter.seek_to_first();
198    }
199
200    fn seek_to_last(&mut self) {
201        self.iter.seek_to_last();
202    }
203}
204
205/// The type of an item returned by [`PooledIter`].
206///
207/// The owned item buffer is returned to [`PooledIter`] when the `PoolItem` is dropped.
208#[derive(Debug)]
209#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
210pub struct PoolItem<OwnedItem>(
211    PooledResource<BoundedPool<OwnedItem, ResetNothing>, OwnedItem>,
212);
213
214impl<OwnedItem> Deref for PoolItem<OwnedItem> {
215    type Target = OwnedItem;
216
217    #[inline]
218    fn deref(&self) -> &Self::Target {
219        &self.0
220    }
221}
222
223impl<OwnedItem> DerefMut for PoolItem<OwnedItem> {
224    #[inline]
225    fn deref_mut(&mut self) -> &mut Self::Target {
226        &mut self.0
227    }
228}
229
230impl<OwnedItem> Borrow<OwnedItem> for PoolItem<OwnedItem> {
231    #[inline]
232    fn borrow(&self) -> &OwnedItem {
233        self
234    }
235}
236
237impl<OwnedItem> BorrowMut<OwnedItem> for PoolItem<OwnedItem> {
238    #[inline]
239    fn borrow_mut(&mut self) -> &mut OwnedItem {
240        self
241    }
242}
243
244impl<OwnedItem> AsRef<OwnedItem> for PoolItem<OwnedItem> {
245    #[inline]
246    fn as_ref(&self) -> &OwnedItem {
247        self
248    }
249}
250
251impl<OwnedItem> AsMut<OwnedItem> for PoolItem<OwnedItem> {
252    #[inline]
253    fn as_mut(&mut self) -> &mut OwnedItem {
254        self
255    }
256}
257
258
259#[cfg(test)]
260mod tests {
261    use crate::test_iter::TestIter;
262    use super::*;
263
264
265    #[test]
266    fn pooled_test_iter() {
267        let data: &[u8] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].as_slice();
268        let mut iter = PooledIter::<_, u8>::new(TestIter::new(data).unwrap(), 2);
269
270        // Hold one buffer the entire time
271        let first = iter.next().unwrap();
272        assert_eq!(*first, 0);
273
274        for i in 1..=9 {
275            assert!(iter.valid());
276            let next = iter.next().unwrap();
277            // Both of the two buffers are in use
278            assert!(iter.try_next().is_err());
279            assert_eq!(*next, i);
280        }
281        drop(first);
282
283        assert!(iter.next().is_none());
284
285        for i in (0..=9).rev() {
286            let current = iter.current();
287            let prev = iter.prev().unwrap();
288
289            if current.is_some() {
290                // Both of the two buffers are in use
291                assert!(iter.try_next().is_err());
292            }
293
294            assert!(iter.valid());
295
296            // This drops `current`
297            assert!(!current.is_some_and(|curr| *curr == *prev));
298
299            let new_current = iter.current().unwrap();
300
301            assert_eq!(*prev, i);
302            assert_eq!(*new_current, i);
303        }
304    }
305
306    #[test]
307    fn seek_test() {
308        let data: &[u8] = [0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 7, 8, 9, 99].as_slice();
309        let mut iter = PooledIter::<_, u8>::new(TestIter::new(data).unwrap(), 1);
310
311        iter.seek_to_first();
312        assert_eq!(*iter.current().unwrap(), 0);
313
314        iter.seek(&0);
315        assert_eq!(*iter.current().unwrap(), 0);
316
317        iter.seek(&1);
318        assert_eq!(*iter.current().unwrap(), 1);
319
320        iter.seek(&9);
321        assert_eq!(*iter.current().unwrap(), 9);
322
323        iter.seek(&8);
324        assert_eq!(*iter.current().unwrap(), 8);
325
326        iter.seek(&10);
327        assert_eq!(*iter.current().unwrap(), 99);
328
329        iter.seek_before(&92);
330        assert_eq!(*iter.current().unwrap(), 9);
331
332        iter.seek_before(&99);
333        assert_eq!(*iter.current().unwrap(), 9);
334
335        iter.seek_before(&100);
336        assert_eq!(*iter.current().unwrap(), 99);
337
338        iter.seek_before(&1);
339        assert_eq!(*iter.current().unwrap(), 0);
340
341        iter.seek_before(&0);
342        assert!(!iter.valid());
343
344        iter.seek(&100);
345        assert!(!iter.valid());
346
347        iter.seek(&99);
348        assert_eq!(*iter.current().unwrap(), 99);
349
350        iter.seek_to_last();
351        assert_eq!(*iter.current().unwrap(), 99);
352
353        iter.seek_before(&4);
354        assert_eq!(*iter.current().unwrap(), 3);
355    }
356}
seekable_iterator/pooled_iter.rs

seekable_iterator/
pooled_iter.rs
