kevy_map/
slot.rs

1//! Slot-index access: probe once, then reach the same entry again without
2//! hashing.
3//!
4//! A slot index is only a position. Any insert or remove may move, free or
5//! reuse it, so every access re-checks that the slot is occupied and hands
6//! back the key stored there; a caller that keeps an index across
7//! mutations compares that key before trusting the value. Nothing here can
8//! read an uninitialised slot.
9
10use core::borrow::Borrow;
11
12use kevy_hash::KevyHash;
13
14use crate::map::KevyMap;
15
16impl<K, V> KevyMap<K, V> {
17    /// The slot `key` occupies, or `None` if it is absent. One probe; the
18    /// index stays valid until the next insert or remove.
19    ///
20    /// ```
21    /// let mut m = kevy_map::KevyMap::new();
22    /// m.insert(7u64, "seven");
23    /// let slot = m.find_slot(&7).ok_or("present")?;
24    /// assert_eq!(m.slot(slot), Some((&7, &"seven")));
25    /// assert_eq!(m.find_slot(&8), None);
26    /// # Ok::<(), &str>(())
27    /// ```
28    #[inline]
29    #[must_use]
30    pub fn find_slot<Q>(&self, key: &Q) -> Option<usize>
31    where
32        K: Borrow<Q>,
33        Q: KevyHash + Eq + ?Sized,
34    {
35        self.find_by_borrow(key)
36    }
37
38    /// The key and value at `slot`, or `None` when the slot is out of range
39    /// or not occupied. No hashing; the returned key says whose entry it is.
40    ///
41    /// ```
42    /// let mut m = kevy_map::KevyMap::new();
43    /// m.insert(1u64, 10u32);
44    /// let slot = m.find_slot(&1).ok_or("present")?;
45    /// m.remove(&1);
46    /// assert_eq!(m.slot(slot), None, "a freed slot reads as empty");
47    /// assert_eq!(m.slot(usize::MAX), None);
48    /// # Ok::<(), &str>(())
49    /// ```
50    #[inline]
51    #[must_use]
52    pub fn slot(&self, slot: usize) -> Option<(&K, &V)> {
53        if !self.slot_is_full(slot) {
54            return None;
55        }
56        // SAFETY: `slot_is_full` checked `slot < cap` and that its metadata
57        // byte marks an initialised entry.
58        let kv = unsafe { (*self.slots_ptr.as_ptr().add(slot)).assume_init_ref() };
59        Some((&kv.0, &kv.1))
60    }
61
62    /// Mutable [`slot`](Self::slot): the key and a mutable value at `slot`,
63    /// or `None` when the slot is out of range or not occupied.
64    ///
65    /// ```
66    /// let mut m = kevy_map::KevyMap::new();
67    /// m.insert(1u64, 10u32);
68    /// let slot = m.find_slot(&1).ok_or("present")?;
69    /// if let Some((&1, v)) = m.slot_mut(slot) {
70    ///     *v += 1;
71    /// }
72    /// assert_eq!(m.get(&1), Some(&11));
73    /// # Ok::<(), &str>(())
74    /// ```
75    #[inline]
76    #[must_use]
77    pub fn slot_mut(&mut self, slot: usize) -> Option<(&K, &mut V)> {
78        if !self.slot_is_full(slot) {
79            return None;
80        }
81        // SAFETY: as in `slot`.
82        let kv = unsafe { (*self.slots_ptr.as_ptr().add(slot)).assume_init_mut() };
83        Some((&kv.0, &mut kv.1))
84    }
85
86    #[inline]
87    fn slot_is_full(&self, slot: usize) -> bool {
88        // SAFETY: read only after the bound check; the metadata array holds
89        // at least `cap` bytes.
90        slot < self.cap && unsafe { *self.metadata_ptr.as_ptr().add(slot) } & 0x80 == 0
91    }
92}
93
94#[cfg(test)]
95mod tests {
96    use crate::KevyMap;
97
98    #[test]
99    fn a_slot_follows_its_entry_until_the_table_changes_shape() {
100        let mut m: KevyMap<u64, u64> = KevyMap::new();
101        assert_eq!(m.slot(0), None, "an unallocated table has no slots");
102        for k in 0..crate::scaled(1000) as u64 {
103            m.insert(k, k * 2);
104        }
105        for k in 0..crate::scaled(1000) as u64 {
106            let s = m.find_slot(&k).expect("present");
107            assert_eq!(m.slot(s), Some((&k, &(k * 2))));
108            *m.slot_mut(s).expect("full").1 += 1;
109            assert_eq!(m.get(&k), Some(&(k * 2 + 1)));
110        }
111        let s = m.find_slot(&5).expect("present");
112        m.remove(&5);
113        assert_eq!(m.slot(s), None);
114        assert!(m.slot_mut(s).is_none());
115        let full = (0..m.capacity()).filter(|&i| m.slot(i).is_some()).count();
116        assert_eq!(full, m.len(), "exactly the occupied slots read as full");
117    }
118}
kevy_map/slot.rs

kevy_map/
slot.rs
