kevy_map/
iter.rs

1//! Borrowing iterators over a [`KevyMap`] — `(&K, &V)`, `&K`-only, and
2//! `&V`-only flavours.
3
4use std::mem::MaybeUninit;
5
6use crate::map::KevyMap;
7
8/// `(&K, &V)` iterator over all live entries of a [`KevyMap`]; order unspecified.
9pub struct Iter<'a, K, V> {
10    metadata: &'a [u8],
11    slots: &'a [MaybeUninit<(K, V)>],
12    pos: usize,
13}
14
15impl<'a, K, V> Iter<'a, K, V> {
16    /// Construct an iterator from a map's raw bucket slices.
17    ///
18    /// `metadata` may be longer than `slots` because the map keeps a
19    /// trailing `GROUP_WIDTH - 1` byte mirror for SIMD-safe wraparound
20    /// loads; only the first `slots.len()` metadata bytes correspond to
21    /// real slots, and that's what we iterate over.
22    pub(crate) fn new(metadata: &'a [u8], slots: &'a [MaybeUninit<(K, V)>]) -> Self {
23        let real_len = slots.len();
24        let metadata = &metadata[..real_len];
25        Self {
26            metadata,
27            slots,
28            pos: 0,
29        }
30    }
31
32    /// Construct an iterator that starts at bucket `start` (clamped to
33    /// `slots.len()`). Powers reservoir / random-start sampling for the
34    /// `kevy-store` eviction sampler — chain two of these (start..end, then
35    /// 0..start) to walk the table in a ring beginning at any position.
36    pub(crate) fn with_start(
37        metadata: &'a [u8],
38        slots: &'a [MaybeUninit<(K, V)>],
39        start: usize,
40    ) -> Self {
41        let real_len = slots.len();
42        let metadata = &metadata[..real_len];
43        Self {
44            metadata,
45            slots,
46            pos: start.min(real_len),
47        }
48    }
49}
50
51impl<'a, K, V> Iterator for Iter<'a, K, V> {
52    type Item = (&'a K, &'a V);
53    fn next(&mut self) -> Option<Self::Item> {
54        while self.pos < self.metadata.len() {
55            let i = self.pos;
56            self.pos += 1;
57            if self.metadata[i] & 0x80 == 0 {
58                // SAFETY: full slot. The borrow's lifetime is tied to
59                // self.slots: &'a [MaybeUninit<(K, V)>].
60                let kv = unsafe { self.slots[i].assume_init_ref() };
61                return Some((&kv.0, &kv.1));
62            }
63        }
64        None
65    }
66}
67
68impl<'a, K, V> IntoIterator for &'a KevyMap<K, V> {
69    type Item = (&'a K, &'a V);
70    type IntoIter = Iter<'a, K, V>;
71    fn into_iter(self) -> Self::IntoIter {
72        self.iter()
73    }
74}
75
76/// `&K` iterator over all live entries of a [`KevyMap`].
77pub struct Keys<'a, K, V>(Iter<'a, K, V>);
78
79impl<'a, K, V> Keys<'a, K, V> {
80    pub(crate) fn new(inner: Iter<'a, K, V>) -> Self {
81        Self(inner)
82    }
83}
84
85impl<'a, K, V> Iterator for Keys<'a, K, V> {
86    type Item = &'a K;
87    fn next(&mut self) -> Option<Self::Item> {
88        self.0.next().map(|(k, _)| k)
89    }
90}
91
92/// `&V` iterator over all live entries of a [`KevyMap`].
93pub struct Values<'a, K, V>(Iter<'a, K, V>);
94
95impl<'a, K, V> Values<'a, K, V> {
96    pub(crate) fn new(inner: Iter<'a, K, V>) -> Self {
97        Self(inner)
98    }
99}
100
101impl<'a, K, V> Iterator for Values<'a, K, V> {
102    type Item = &'a V;
103    fn next(&mut self) -> Option<Self::Item> {
104        self.0.next().map(|(_, v)| v)
105    }
106}
kevy_map/iter.rs

kevy_map/
iter.rs
