kevy-map 1.0.4

Open-addressing hashtable with bucket-addr prefetch API.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

//! Borrowing iterators over a [`KevyMap`] — `(&K, &V)`, `&K`-only, and
//! `&V`-only flavours.

use std::mem::MaybeUninit;

use crate::map::KevyMap;

/// `(&K, &V)` iterator over all live entries of a [`KevyMap`]; order unspecified.
pub struct Iter<'a, K, V> {
    metadata: &'a [u8],
    slots: &'a [MaybeUninit<(K, V)>],
    pos: usize,
}

impl<'a, K, V> Iter<'a, K, V> {
    /// Construct an iterator from a map's raw bucket slices.
    ///
    /// `metadata` may be longer than `slots` because the map keeps a
    /// trailing `GROUP_WIDTH - 1` byte mirror for SIMD-safe wraparound
    /// loads; only the first `slots.len()` metadata bytes correspond to
    /// real slots, and that's what we iterate over.
    pub(crate) fn new(metadata: &'a [u8], slots: &'a [MaybeUninit<(K, V)>]) -> Self {
        let real_len = slots.len();
        let metadata = &metadata[..real_len];
        Self {
            metadata,
            slots,
            pos: 0,
        }
    }

    /// Construct an iterator that starts at bucket `start` (clamped to
    /// `slots.len()`). Powers reservoir / random-start sampling for the
    /// `kevy-store` eviction sampler — chain two of these (start..end, then
    /// 0..start) to walk the table in a ring beginning at any position.
    pub(crate) fn with_start(
        metadata: &'a [u8],
        slots: &'a [MaybeUninit<(K, V)>],
        start: usize,
    ) -> Self {
        let real_len = slots.len();
        let metadata = &metadata[..real_len];
        Self {
            metadata,
            slots,
            pos: start.min(real_len),
        }
    }
}

impl<'a, K, V> Iterator for Iter<'a, K, V> {
    type Item = (&'a K, &'a V);
    fn next(&mut self) -> Option<Self::Item> {
        while self.pos < self.metadata.len() {
            let i = self.pos;
            self.pos += 1;
            if self.metadata[i] & 0x80 == 0 {
                // SAFETY: full slot. The borrow's lifetime is tied to
                // self.slots: &'a [MaybeUninit<(K, V)>].
                let kv = unsafe { self.slots[i].assume_init_ref() };
                return Some((&kv.0, &kv.1));
            }
        }
        None
    }
}

impl<'a, K, V> IntoIterator for &'a KevyMap<K, V> {
    type Item = (&'a K, &'a V);
    type IntoIter = Iter<'a, K, V>;
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

/// `&K` iterator over all live entries of a [`KevyMap`].
pub struct Keys<'a, K, V>(Iter<'a, K, V>);

impl<'a, K, V> Keys<'a, K, V> {
    pub(crate) fn new(inner: Iter<'a, K, V>) -> Self {
        Self(inner)
    }
}

impl<'a, K, V> Iterator for Keys<'a, K, V> {
    type Item = &'a K;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(k, _)| k)
    }
}

/// `&V` iterator over all live entries of a [`KevyMap`].
pub struct Values<'a, K, V>(Iter<'a, K, V>);

impl<'a, K, V> Values<'a, K, V> {
    pub(crate) fn new(inner: Iter<'a, K, V>) -> Self {
        Self(inner)
    }
}

impl<'a, K, V> Iterator for Values<'a, K, V> {
    type Item = &'a V;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(_, v)| v)
    }
}