rc_hashmap/
handle_hash_map.rs

1//! HandleHashMap: structural layer with stable handles and debug reentrancy guard.
2
3use crate::hash::DefaultHashBuilder;
4use crate::reentrancy::DebugReentrancy;
5use core::borrow::Borrow;
6use core::hash::{BuildHasher, Hash};
7use hashbrown::HashTable;
8use slotmap::{DefaultKey, SlotMap};
9
10#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
11pub struct Handle(DefaultKey);
12
13impl Handle {
14    pub(crate) fn new(k: DefaultKey) -> Self {
15        Handle(k)
16    }
17    pub(crate) fn raw_handle(&self) -> DefaultKey {
18        self.0
19    }
20
21    pub fn key<'a, K, V, S>(&self, map: &'a HandleHashMap<K, V, S>) -> Option<&'a K>
22    where
23        K: Eq + Hash,
24        S: BuildHasher + Clone + Default,
25    {
26        map.handle_key(*self)
27    }
28
29    pub fn value<'a, K, V, S>(&self, map: &'a HandleHashMap<K, V, S>) -> Option<&'a V>
30    where
31        K: Eq + Hash,
32        S: BuildHasher + Clone + Default,
33    {
34        map.handle_value(*self)
35    }
36
37    pub fn value_mut<'a, K, V, S>(&self, map: &'a mut HandleHashMap<K, V, S>) -> Option<&'a mut V>
38    where
39        K: Eq + Hash,
40        S: BuildHasher + Clone + Default,
41    {
42        map.handle_value_mut(*self)
43    }
44}
45
46#[derive(Debug)]
47struct Entry<K, V> {
48    key: K,
49    value: V,
50    hash: u64,
51}
52
53pub struct HandleHashMap<K, V, S = DefaultHashBuilder> {
54    hasher: S,
55    index: HashTable<DefaultKey>,
56    slots: SlotMap<DefaultKey, Entry<K, V>>, // storage using generational keys
57    reentrancy: DebugReentrancy,
58}
59
60#[derive(Debug)]
61pub enum InsertError {
62    DuplicateKey,
63}
64
65impl<K, V> HandleHashMap<K, V>
66where
67    K: Eq + Hash,
68{
69    pub fn new() -> Self {
70        Self::with_hasher(Default::default())
71    }
72}
73
74impl<K, V> Default for HandleHashMap<K, V>
75where
76    K: Eq + Hash,
77{
78    fn default() -> Self {
79        Self::new()
80    }
81}
82
83/// Iterator over immutable entries in `HandleHashMap`.
84pub struct Iter<'a, K, V, S> {
85    it: slotmap::basic::Iter<'a, DefaultKey, Entry<K, V>>,
86    pub(crate) _pd: core::marker::PhantomData<&'a (K, V, S)>,
87}
88
89impl<'a, K, V, S> Iterator for Iter<'a, K, V, S> {
90    type Item = (Handle, &'a K, &'a V);
91    #[inline]
92    fn next(&mut self) -> Option<Self::Item> {
93        self.it
94            .next()
95            .map(|(k, e)| (Handle::new(k), &e.key, &e.value))
96    }
97}
98
99/// Iterator over mutable entries in `HandleHashMap`.
100pub struct IterMut<'a, K, V, S> {
101    it: slotmap::basic::IterMut<'a, DefaultKey, Entry<K, V>>,
102    pub(crate) _pd: core::marker::PhantomData<&'a (K, V, S)>,
103}
104
105impl<'a, K, V, S> Iterator for IterMut<'a, K, V, S> {
106    type Item = (Handle, &'a K, &'a mut V);
107    #[inline]
108    fn next(&mut self) -> Option<Self::Item> {
109        self.it
110            .next()
111            .map(|(k, e)| (Handle::new(k), &e.key, &mut e.value))
112    }
113}
114
115impl<K, V, S> HandleHashMap<K, V, S>
116where
117    K: Eq + Hash,
118    S: BuildHasher + Clone + Default,
119{
120    pub fn with_hasher(hasher: S) -> Self {
121        Self {
122            index: HashTable::new(),
123            hasher,
124            slots: SlotMap::with_key(),
125            reentrancy: DebugReentrancy::new(),
126        }
127    }
128
129    fn make_hash<Q>(&self, q: &Q) -> u64
130    where
131        Q: ?Sized + Hash,
132    {
133        self.hasher.hash_one(q)
134    }
135
136    pub fn len(&self) -> usize {
137        self.slots.len()
138    }
139    pub fn is_empty(&self) -> bool {
140        self.slots.is_empty()
141    }
142
143    pub fn find<Q>(&self, q: &Q) -> Option<Handle>
144    where
145        K: Borrow<Q>,
146        Q: ?Sized + Hash + Eq,
147    {
148        let _g = self.reentrancy.enter();
149        let hash = self.make_hash(q);
150        if let Some(&k) = self.index.find(hash, |&k| {
151            self.slots
152                .get(k)
153                .map(|e| e.key.borrow() == q)
154                .unwrap_or(false)
155        }) {
156            return Some(Handle::new(k));
157        }
158        None
159    }
160
161    pub fn contains_key<Q>(&self, q: &Q) -> bool
162    where
163        K: Borrow<Q>,
164        Q: ?Sized + Hash + Eq,
165    {
166        let _g = self.reentrancy.enter();
167        let hash = self.make_hash(q);
168        self.index
169            .find(hash, |&k| {
170                self.slots
171                    .get(k)
172                    .map(|e| e.key.borrow() == q)
173                    .unwrap_or(false)
174            })
175            .is_some()
176    }
177
178    pub fn insert(&mut self, key: K, value: V) -> Result<Handle, InsertError> {
179        let _g = self.reentrancy.enter();
180        let hash = self.make_hash(&key);
181        let entry = Entry { key, value, hash };
182        // Use HashTable::entry to deduplicate or insert.
183        match self.index.entry(
184            hash,
185            |&kk| {
186                self.slots
187                    .get(kk)
188                    .map(|e| e.key == entry.key)
189                    .unwrap_or(false)
190            },
191            |&kk| self.slots.get(kk).map(|e| e.hash).unwrap_or(0),
192        ) {
193            hashbrown::hash_table::Entry::Occupied(_) => Err(InsertError::DuplicateKey),
194            hashbrown::hash_table::Entry::Vacant(v) => {
195                let k = self.slots.insert(entry);
196                let _ = v.insert(k);
197                Ok(Handle::new(k))
198            }
199        }
200    }
201
202    pub fn insert_with<F>(&mut self, key: K, default: F) -> Result<Handle, InsertError>
203    where
204        F: FnOnce() -> V,
205    {
206        let _g = self.reentrancy.enter();
207        let hash = self.make_hash(&key);
208        match self.index.entry(
209            hash,
210            |&kk| self.slots.get(kk).map(|e| e.key == key).unwrap_or(false),
211            |&kk| self.slots.get(kk).map(|e| e.hash).unwrap_or(0),
212        ) {
213            hashbrown::hash_table::Entry::Occupied(_) => Err(InsertError::DuplicateKey),
214            hashbrown::hash_table::Entry::Vacant(v) => {
215                let value = default();
216                let entry = Entry { key, value, hash };
217                let k = self.slots.insert(entry);
218                let _ = v.insert(k);
219                Ok(Handle::new(k))
220            }
221        }
222    }
223
224    pub fn remove(&mut self, handle: Handle) -> Option<(K, V)> {
225        let _g = self.reentrancy.enter();
226        let k = handle.raw_handle();
227
228        // Remove slot
229        let entry = self.slots.remove(k)?;
230
231        // Unlink from index via occupied entry removal
232        self.index
233            .find_entry(entry.hash, |&kk| kk == k)
234            .unwrap()
235            .remove();
236
237        Some((entry.key, entry.value))
238    }
239
240    pub(crate) fn handle_key(&self, h: Handle) -> Option<&K> {
241        let _g = self.reentrancy.enter();
242        self.slots.get(h.raw_handle()).map(|e| &e.key)
243    }
244
245    pub(crate) fn handle_value(&self, h: Handle) -> Option<&V> {
246        let _g = self.reentrancy.enter();
247        self.slots.get(h.raw_handle()).map(|e| &e.value)
248    }
249
250    pub(crate) fn handle_value_mut(&mut self, h: Handle) -> Option<&mut V> {
251        let _g = self.reentrancy.enter();
252        self.slots.get_mut(h.raw_handle()).map(|e| &mut e.value)
253    }
254
255    pub fn iter(&self) -> Iter<'_, K, V, S> {
256        let it = self.slots.iter();
257        Iter {
258            it,
259            _pd: core::marker::PhantomData,
260        }
261    }
262
263    pub fn iter_mut(&mut self) -> IterMut<'_, K, V, S> {
264        let it = self.slots.iter_mut();
265        IterMut {
266            it,
267            _pd: core::marker::PhantomData,
268        }
269    }
270}
271
272#[cfg(test)]
273mod tests {
274    use super::*;
275    use std::cell::Cell;
276    use std::collections::BTreeSet;
277    use std::hash::Hasher;
278
279    /// Invariant: Duplicate keys are rejected and the map remains unchanged.
280    #[test]
281    fn duplicate_insert_rejected() {
282        let mut m: HandleHashMap<String, i32> = HandleHashMap::new();
283        let handle = m.insert("dup".to_string(), 1).unwrap();
284        match m.insert("dup".to_string(), 2) {
285            Err(InsertError::DuplicateKey) => {}
286            other => panic!("unexpected result: {:?}", other),
287        }
288        assert_eq!(*handle.value(&m).unwrap(), 1);
289        assert_eq!(m.len(), 1);
290    }
291
292    /// Invariant: `find(k).is_some() == contains_key(k)` for present/absent keys.
293    #[test]
294    fn find_contains_parity() {
295        let mut m: HandleHashMap<String, i32> = HandleHashMap::new();
296        let present = ["a", "b", "c"];
297        for (i, k) in present.iter().enumerate() {
298            m.insert((*k).to_string(), i as i32).unwrap();
299        }
300
301        for k in present {
302            let s = k.to_string();
303            assert!(m.find(&s).is_some());
304            assert!(m.contains_key(&s));
305        }
306
307        for k in ["x", "y", "z"] {
308            let s = k.to_string();
309            assert!(m.find(&s).is_none());
310            assert!(!m.contains_key(&s));
311        }
312    }
313
314    /// Invariant: Borrowed lookup works (store `String`, query with `&str`).
315    #[test]
316    fn borrowed_lookup_with_str() {
317        let mut m: HandleHashMap<String, i32> = HandleHashMap::new();
318        m.insert("hello".to_string(), 1).unwrap();
319        assert!(m.contains_key("hello"));
320        assert!(!m.contains_key("world"));
321
322        // Also validate borrowed find
323        assert!(m.find("hello").is_some());
324        assert!(m.find("world").is_none());
325    }
326
327    /// Invariant: Handle-based access yields references while the entry exists and
328    /// becomes `None` after removal. Mutating via `value_mut` updates the stored value.
329    #[test]
330    fn handle_access_and_mutation() {
331        let mut m: HandleHashMap<String, i32> = HandleHashMap::new();
332        let h = m.insert("k1".to_string(), 10).unwrap();
333        assert_eq!(h.key(&m), Some(&"k1".to_string()));
334        assert_eq!(h.value(&m), Some(&10));
335        let new_val = h
336            .value_mut(&mut m)
337            .map(|v| {
338                *v += 5;
339                *v
340            })
341            .unwrap();
342        assert_eq!(new_val, 15);
343        assert_eq!(h.value(&m), Some(&15));
344
345        let (_k, _v) = m.remove(h).unwrap();
346        assert!(h.value(&m).is_none());
347    }
348
349    /// Invariant: Removing an entry invalidates its handle and does not alias a new
350    /// entry inserted afterward, even if the physical slot is reused (generational keys).
351    #[test]
352    fn stale_handle_does_not_alias_new_entry() {
353        let mut m: HandleHashMap<String, i32> = HandleHashMap::new();
354        let h1 = m.insert("old".to_string(), 1).unwrap();
355        let (_k, _v) = m.remove(h1).unwrap();
356        // Next insert likely reuses the freed slot with bumped generation.
357        let h2 = m.insert("new".to_string(), 2).unwrap();
358        assert_ne!(h1, h2, "handles must differ across generations");
359        assert!(h1.value(&m).is_none(), "stale handle must not resolve");
360        assert!(m.contains_key("new"));
361        assert!(!m.contains_key("old"));
362    }
363
364    /// Invariant: Iteration yields each live entry exactly once; `iter_mut` updates
365    /// values as seen by subsequent lookups.
366    #[test]
367    fn iteration_and_mutation() {
368        let mut m: HandleHashMap<String, i32> = HandleHashMap::new();
369        let keys = ["k1", "k2", "k3"];
370        for (i, k) in keys.iter().enumerate() {
371            m.insert((*k).to_string(), i as i32).unwrap();
372        }
373
374        let seen: BTreeSet<String> = m.iter().map(|(_h, k, _v)| k.clone()).collect();
375        let expected: BTreeSet<String> = keys.iter().map(|s| (*s).to_string()).collect();
376        assert_eq!(seen, expected);
377
378        for (_h, _k, v) in m.iter_mut() {
379            *v += 10;
380        }
381        for k in keys {
382            let h = m.find(&k.to_string()).unwrap();
383            assert_eq!(
384                h.value(&m),
385                Some(&match k {
386                    "k1" => 10,
387                    "k2" => 11,
388                    "k3" => 12,
389                    _ => unreachable!(),
390                })
391            );
392        }
393    }
394
395    /// Invariant: Lookups work under heavy hash collisions; equality resolves to the
396    /// correct entry. This also exercises collision probing via `Eq`.
397    #[test]
398    fn collision_handling_with_const_hasher() {
399        #[derive(Clone, Default)]
400        struct ConstBuildHasher;
401        struct ConstHasher;
402        impl BuildHasher for ConstBuildHasher {
403            type Hasher = ConstHasher;
404            fn build_hasher(&self) -> Self::Hasher {
405                ConstHasher
406            }
407        }
408        impl core::hash::Hasher for ConstHasher {
409            fn write(&mut self, _bytes: &[u8]) {}
410            fn finish(&self) -> u64 {
411                0
412            } // force all keys into the same hash bucket
413        }
414
415        let mut m: HandleHashMap<String, i32, ConstBuildHasher> =
416            HandleHashMap::with_hasher(ConstBuildHasher);
417        m.insert("a".to_string(), 1).unwrap();
418        m.insert("b".to_string(), 2).unwrap();
419
420        let ha = m.find(&"a".to_string()).expect("find a");
421        let hb = m.find(&"b".to_string()).expect("find b");
422        assert_ne!(ha, hb);
423        assert_eq!(ha.key(&m), Some(&"a".to_string()));
424        assert_eq!(hb.key(&m), Some(&"b".to_string()));
425    }
426
427    /// Invariant: After `remove`, the key is absent; reinserting the same key adds a
428    /// fresh entry with a potentially new handle and the new value is observed.
429    #[test]
430    fn remove_then_reinsert_same_key_yields_new_value() {
431        let mut m: HandleHashMap<String, i32> = HandleHashMap::new();
432        let h1 = m.insert("k".to_string(), 1).unwrap();
433
434        // Remove: key must disappear and handle becomes invalid
435        let (k_removed, v_removed) = m.remove(h1).expect("present for removal");
436        assert_eq!(k_removed, "k");
437        assert_eq!(v_removed, 1);
438        assert!(!m.contains_key("k"));
439        assert!(m.find(&"k".to_string()).is_none());
440        assert!(h1.value(&m).is_none());
441
442        // Reinsert same key with a different value
443        let h2 = m.insert("k".to_string(), 2).expect("reinsert allowed");
444        assert!(m.contains_key("k"));
445        let hf = m.find(&"k".to_string()).expect("find reinserted key");
446        assert_eq!(hf.value(&m), Some(&2));
447        assert_eq!(h2.value(&m), Some(&2));
448        assert_ne!(h1, h2, "old handle must not alias new entry");
449        assert!(h1.value(&m).is_none(), "stale handle stays invalid");
450    }
451
452    /// Invariant (debug-only): Re-entering `HandleHashMap` from within `K: Eq` during a
453    /// probe panics due to the reentrancy guard; in release builds, this test is skipped.
454    #[cfg(debug_assertions)]
455    #[test]
456    fn reentrancy_panics_from_eq_during_find() {
457        #[derive(Clone, Default)]
458        struct ConstBuildHasher;
459        struct ConstHasher;
460        impl BuildHasher for ConstBuildHasher {
461            type Hasher = ConstHasher;
462            fn build_hasher(&self) -> Self::Hasher {
463                ConstHasher
464            }
465        }
466        impl core::hash::Hasher for ConstHasher {
467            fn write(&mut self, _bytes: &[u8]) {}
468            fn finish(&self) -> u64 {
469                0
470            }
471        }
472
473        struct ReentryKey {
474            id: &'static str,
475            map: *const HandleHashMap<ReentryKey, i32, ConstBuildHasher>,
476            trigger: bool,
477        }
478        impl core::fmt::Debug for ReentryKey {
479            fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
480                f.write_str(self.id)
481            }
482        }
483        impl PartialEq for ReentryKey {
484            fn eq(&self, other: &Self) -> bool {
485                if self.id == other.id {
486                    return true;
487                }
488                if other.trigger {
489                    // Attempt to re-enter the same map during probing.
490                    unsafe {
491                        let m = &*other.map;
492                        let _ = m.contains_key(self.id);
493                    }
494                }
495                false
496            }
497        }
498        impl Eq for ReentryKey {}
499        impl Hash for ReentryKey {
500            fn hash<H: Hasher>(&self, state: &mut H) {
501                self.id.hash(state);
502            }
503        }
504        impl core::borrow::Borrow<str> for ReentryKey {
505            fn borrow(&self) -> &str {
506                self.id
507            }
508        }
509
510        let mut m: HandleHashMap<ReentryKey, i32, ConstBuildHasher> =
511            HandleHashMap::with_hasher(ConstBuildHasher);
512        let key = ReentryKey {
513            id: "a",
514            map: core::ptr::null(),
515            trigger: false,
516        };
517        // Set map pointer after creation
518        let key = ReentryKey {
519            map: &m as *const _,
520            ..key
521        };
522        m.insert(key, 1).unwrap();
523
524        let query = ReentryKey {
525            id: "b",
526            map: &m as *const _,
527            trigger: true,
528        };
529        let res = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
530            let _ = m.find(&query);
531        }));
532        assert!(res.is_err(), "expected reentrancy to panic in debug builds");
533    }
534
535    /// Invariant: `insert_with` only runs the default constructor on
536    /// successful insert; on duplicate it does not run and returns an error.
537    #[test]
538    fn insert_with_is_lazy_and_deduplicates() {
539        let mut m: HandleHashMap<String, String> = HandleHashMap::new();
540        let calls = Cell::new(0);
541
542        let r = m.insert_with("k".to_string(), || {
543            calls.set(calls.get() + 1);
544            "v".to_string()
545        });
546        assert!(r.is_ok());
547        assert_eq!(calls.get(), 1);
548
549        // Duplicate: must not run default closure
550        let r2 = m.insert_with("k".to_string(), || {
551            calls.set(calls.get() + 1);
552            "v2".to_string()
553        });
554        match r2 {
555            Err(InsertError::DuplicateKey) => {}
556            other => panic!("unexpected result: {:?}", other),
557        }
558        assert_eq!(calls.get(), 1, "default() must not run on duplicate");
559
560        // Value remains the original one
561        let h = m.find(&"k".to_string()).unwrap();
562        assert_eq!(h.value(&m), Some(&"v".to_string()));
563    }
564
565    /// Invariant: Values inserted via `insert` and `insert_with` are
566    /// equivalent for the same key/value; duplicates are rejected by both.
567    #[test]
568    fn insert_with_value_equivalence() {
569        let mut m1: HandleHashMap<&'static str, i32> = HandleHashMap::new();
570        let mut m2: HandleHashMap<&'static str, i32> = HandleHashMap::new();
571
572        let h1 = m1.insert("a", 1).unwrap();
573        let h2 = m2.insert_with("a", || 1).unwrap();
574
575        assert!(m1.contains_key(&"a"));
576        assert!(m2.contains_key(&"a"));
577        assert_eq!(h1.value(&m1), h2.value(&m2));
578
579        // insert_with rejects duplicate just like insert
580        assert!(m1.insert_with("a", || 2).is_err());
581        assert!(m2.insert_with("a", || 3).is_err());
582    }
583
584    /// Invariant: Handles referring to the same entry alias: mutating via one handle
585    /// is visible through the other obtained via lookup.
586    #[test]
587    fn handles_alias_same_entry_between_insert_and_find() {
588        let mut m: HandleHashMap<String, i32> = HandleHashMap::new();
589        let h_insert = m.insert("k".to_string(), 10).unwrap();
590
591        // Obtain another handle via lookup
592        let h_find = m.find("k").expect("key present");
593
594        // They should be equal handles for the same slot
595        assert_eq!(h_insert, h_find);
596
597        // Mutate through the first handle; observe via the second
598        *h_insert.value_mut(&mut m).expect("value_mut present") = 20;
599        assert_eq!(h_find.value(&m), Some(&20));
600
601        // Mutate through the second handle; observe via the first
602        *h_find.value_mut(&mut m).expect("value_mut present") = 30;
603        assert_eq!(h_insert.value(&m), Some(&30));
604    }
605
606    /// Invariant: `len()` and `is_empty()` reflect the number of live entries,
607    /// unaffected by failed duplicate inserts, and updated after removals.
608    #[test]
609    fn len_and_is_empty_behaviors() {
610        let mut m: HandleHashMap<String, i32> = HandleHashMap::new();
611        assert_eq!(m.len(), 0);
612        assert!(m.is_empty());
613
614        let h1 = m.insert("a".to_string(), 1).unwrap();
615        assert_eq!(m.len(), 1);
616        assert!(!m.is_empty());
617
618        // Duplicate insert must not change len/is_empty
619        match m.insert("a".to_string(), 2) {
620            Err(InsertError::DuplicateKey) => {}
621            other => panic!("unexpected result: {:?}", other),
622        }
623        assert_eq!(m.len(), 1);
624        assert!(!m.is_empty());
625
626        let h2 = m.insert("b".to_string(), 2).unwrap();
627        assert_eq!(m.len(), 2);
628        assert!(!m.is_empty());
629
630        let _ = m.remove(h1).unwrap();
631        assert_eq!(m.len(), 1);
632        assert!(!m.is_empty());
633
634        let _ = m.remove(h2).unwrap();
635        assert_eq!(m.len(), 0);
636        assert!(m.is_empty());
637    }
638}
rc_hashmap/handle_hash_map.rs

rc_hashmap/
handle_hash_map.rs
