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, &mut V)` iterator over all live entries of a [`KevyMap`]; order
77/// unspecified. Keys stay shared — mutating a key would corrupt its bucket.
78pub struct IterMut<'a, K, V> {
79    metadata: &'a [u8],
80    slots: &'a mut [MaybeUninit<(K, V)>],
81    pos: usize,
82}
83
84impl<'a, K, V> IterMut<'a, K, V> {
85    /// Construct from a map's raw bucket slices (same mirror-tail trim as
86    /// [`Iter::new`]).
87    pub(crate) fn new(metadata: &'a [u8], slots: &'a mut [MaybeUninit<(K, V)>]) -> Self {
88        let metadata = &metadata[..slots.len()];
89        Self {
90            metadata,
91            slots,
92            pos: 0,
93        }
94    }
95}
96
97impl<'a, K, V> Iterator for IterMut<'a, K, V> {
98    type Item = (&'a K, &'a mut V);
99    fn next(&mut self) -> Option<Self::Item> {
100        while self.pos < self.metadata.len() {
101            let i = self.pos;
102            self.pos += 1;
103            if self.metadata[i] & 0x80 == 0 {
104                // SAFETY: full slot ⇒ initialised, and `pos` only advances, so
105                // each index is yielded at most once — the returned `&mut V`s
106                // are disjoint and all live within the `'a` borrow of `slots`.
107                let kv = unsafe { &mut *(self.slots.as_mut_ptr().add(i) as *mut (K, V)) };
108                return Some((&kv.0, &mut kv.1));
109            }
110        }
111        None
112    }
113}
114
115impl<'a, K, V> IntoIterator for &'a mut KevyMap<K, V> {
116    type Item = (&'a K, &'a mut V);
117    type IntoIter = IterMut<'a, K, V>;
118    fn into_iter(self) -> Self::IntoIter {
119        self.iter_mut()
120    }
121}
122
123/// `&K` iterator over all live entries of a [`KevyMap`].
124pub struct Keys<'a, K, V>(Iter<'a, K, V>);
125
126impl<'a, K, V> Keys<'a, K, V> {
127    pub(crate) fn new(inner: Iter<'a, K, V>) -> Self {
128        Self(inner)
129    }
130}
131
132impl<'a, K, V> Iterator for Keys<'a, K, V> {
133    type Item = &'a K;
134    fn next(&mut self) -> Option<Self::Item> {
135        self.0.next().map(|(k, _)| k)
136    }
137}
138
139/// `&V` iterator over all live entries of a [`KevyMap`].
140pub struct Values<'a, K, V>(Iter<'a, K, V>);
141
142impl<'a, K, V> Values<'a, K, V> {
143    pub(crate) fn new(inner: Iter<'a, K, V>) -> Self {
144        Self(inner)
145    }
146}
147
148impl<'a, K, V> Iterator for Values<'a, K, V> {
149    type Item = &'a V;
150    fn next(&mut self) -> Option<Self::Item> {
151        self.0.next().map(|(_, v)| v)
152    }
153}
kevy_map/iter.rs

kevy_map/
iter.rs
