kevy_map/
scan.rs

1//! Incremental, rehash-tolerant table scanning — the cursor arithmetic
2//! behind a Redis-style `SCAN`.
3//!
4//! [`KevyMap::scan_step`] visits one *home bucket-group* (16 buckets) per
5//! call and returns the next cursor (0 = the sweep is complete). The
6//! cursor walks group indices in **reverse-binary-increment** order —
7//! Redis `dictScan`'s algorithm — masked to the CURRENT table size on
8//! every call. Because the table's capacity is always a power of two and
9//! an entry's home group in a doubled table is its old home group plus
10//! one new high bit, this ordering guarantees: **every key present in
11//! the map for the whole duration of a sweep is visited at least once,
12//! even if the table grows (rehashes) between calls.** Keys may be
13//! visited more than once across a grow; callers must tolerate
14//! duplicates (Redis SCAN has the same contract).
15//!
16//! Displacement: `KevyMap` is open-addressing, so an entry's *stored*
17//! slot is not a pure function of its hash — a rehash can move it
18//! relative to other entries, which would break the guarantee if we
19//! enumerated stored positions. We therefore enumerate by **home**
20//! bucket (`hash & mask`, a pure function of hash and capacity) and,
21//! for each home group, walk the probe run forward collecting entries
22//! whose recomputed home falls in the group. See
23//! [`KevyMap::visit_home_group`] for the run-termination proof.
24
25use kevy_hash::KevyHash;
26
27use crate::map::{EMPTY, GROUP_WIDTH, KevyMap};
28
29impl<K: KevyHash + Eq, V> KevyMap<K, V> {
30    /// Visit one bucket-group's worth of the map and return the next
31    /// cursor. Start a sweep with `cursor = 0`; a returned `0` means the
32    /// sweep is complete. Grows between calls never skip a key that was
33    /// present throughout (see the module docs); shrinks don't exist
34    /// (`KevyMap` never shrinks in place).
35    ///
36    /// `f` is called once per entry whose home group is the cursor's
37    /// group — at most once per entry per call, in unspecified order.
38    ///
39    /// Bounded work: one call touches one 16-bucket home group plus its
40    /// probe-run overhang (short at the 7/8 load factor).
41    pub fn scan_step(&self, cursor: u64, mut f: impl FnMut(&K, &V)) -> u64 {
42        if self.cap == 0 {
43            return 0;
44        }
45        // cap is a power of two ≥ MIN_CAP (16), so ngroups ≥ 1 and gmask
46        // is a low-bit mask.
47        let ngroups = (self.cap / GROUP_WIDTH) as u64;
48        let gmask = ngroups - 1;
49        self.visit_home_group((cursor & gmask) as usize, &mut f);
50        // dictScan's reverse-binary increment: force every bit above the
51        // mask to 1 so the +1 carry (performed in the bit-reversed
52        // domain) clears them — the result is always ≤ gmask, and a
53        // cursor minted against a smaller table resumes correctly
54        // against a larger one.
55        let v = (cursor | !gmask).reverse_bits();
56        v.wrapping_add(1).reverse_bits()
57    }
58
59    /// Call `f` for every entry whose *home* bucket (`hash & mask`) lies
60    /// in aligned group `g` (buckets `[16g, 16g + 16)`).
61    ///
62    /// Walk + termination: insert probes 16-wide windows starting at the
63    /// home bucket, so an entry with home `h` sits at `p ≥ h` where the
64    /// contiguous range `[h, window(p))` holds no EMPTY — except that
65    /// tombstone reuse may place it up to `GROUP_WIDTH - 1` slots past
66    /// the first EMPTY at-or-after `h` (both inside one window). EMPTY
67    /// slots are only ever consumed (deletes leave DELETED; only a grow
68    /// mints a fresh all-EMPTY table), so the bound never decays.
69    /// Therefore every group-`g` entry lies at or before
70    /// `first-EMPTY-at-or-after(16g + 15) + GROUP_WIDTH - 1`, which is
71    /// exactly where this walk stops.
72    fn visit_home_group(&self, g: usize, f: &mut impl FnMut(&K, &V)) {
73        let start = g * GROUP_WIDTH;
74        let mut past_empty: Option<usize> = None;
75        // `off` covers at most the whole table (a live table always has
76        // ≥ cap/8 EMPTY slots — occupied + deleted never exceeds the 7/8
77        // threshold — so the walk terminates far earlier in practice).
78        for off in 0..self.cap {
79            let p = (start + off) & self.mask;
80            // SAFETY: p < cap ⇒ metadata pointer in-bounds.
81            let meta = unsafe { *self.metadata_ptr.as_ptr().add(p) };
82            if meta & 0x80 == 0 {
83                // SAFETY: occupied slot ⇒ initialised.
84                let kv = unsafe { (*self.slots_ptr.as_ptr().add(p)).assume_init_ref() };
85                let home = (kv.0.kevy_hash() as usize) & self.mask;
86                if home / GROUP_WIDTH == g {
87                    f(&kv.0, &kv.1);
88                }
89            }
90            match &mut past_empty {
91                Some(0) => return,
92                Some(t) => *t -= 1,
93                // The terminating EMPTY must sit at-or-after the LAST
94                // home bucket of the group (off ≥ GROUP_WIDTH - 1) so it
95                // bounds every home in the group, not just the first.
96                None if meta == EMPTY && off + 1 >= GROUP_WIDTH => {
97                    past_empty = Some(GROUP_WIDTH - 1);
98                }
99                None => {}
100            }
101        }
102    }
103}
104
105#[cfg(test)]
106#[path = "scan_tests.rs"]
107mod tests;
kevy_map/scan.rs

kevy_map/
scan.rs
