kovan_map/hopscotch/
std_traits.rs

1//! The `std::collections::HashMap`-shaped trait set: `Default`, `Debug`, `Clone`, `Extend`,
2//! `PartialEq` and `Eq`, each with std's own bounds where an honest concurrent implementation can
3//! give them, built entirely on `HopscotchMap`'s public API (`iter`, `get`, `len`,
4//! `with_capacity_and_hasher`, `insert`). None of it touches a write path's own body.
5//!
6//! `Clone` and `Extend<(K, V)>` also ask `K: MaybeSend, V: MaybeSend` (`Send` where threads share
7//! memory, see [`MaybeSend`]), as `FromIterator` does: an entry
8//! their inserts replace is retired, and kovan may run a retired entry's destructor on another
9//! thread (the contract of `kovan::retire`), which a `!Send` key or value must never meet.
10//! `Extend<(&K, &V)>` needs no `Send`: its `Copy` keys and values have no destructor.
11//!
12//! `FromIterator` and both `IntoIterator` impls live in `iter.rs`, next to the iterator types
13//! they return; `Send`/`Sync`/`Drop` stay in the main module, next to the field layout they
14//! reason about.
15
16use super::HopscotchMap;
17use crate::MaybeSend;
18use core::fmt;
19use core::hash::{BuildHasher, Hash};
20
21/// Creates an empty map with `S`'s default hasher and the default capacity, bounded by exactly
22/// what `std::collections::HashMap`'s `Default` needs: `S: Default` (construction never hashes,
23/// so `K`/`V` carry only the struct's own `'static`, and `S` needs no `BuildHasher` either). Not
24/// `#[cfg(feature = "std")]`: unlike [`HopscotchMap::new`] (which needs `foldhash::fast::FixedState`'s
25/// `std`-only default), this is generic over the caller's own `S`.
26impl<K: 'static, V: 'static, S: Default> Default for HopscotchMap<K, V, S> {
27    fn default() -> Self {
28        Self::with_hasher(S::default())
29    }
30}
31
32/// A snapshot of the map's entries, as `std::collections::HashMap`'s `Debug` prints its own.
33/// Bounded by what the walk needs (owned clones, keys compared to skip one met twice), never by
34/// `Hash` or `S: BuildHasher`: printing hashes nothing.
35impl<K, V, S> fmt::Debug for HopscotchMap<K, V, S>
36where
37    K: Eq + Clone + fmt::Debug + 'static,
38    V: Clone + fmt::Debug + 'static,
39{
40    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
41        f.debug_map().entries(self.iter()).finish()
42    }
43}
44
45/// A snapshot copy: a new map with the same capacity and a clone of the hasher, populated by
46/// inserting a clone of every entry this map held at some point during the walk. Like `iter`, a
47/// concurrent write to `self` during the clone may or may not be reflected in the result.
48impl<K, V, S> Clone for HopscotchMap<K, V, S>
49where
50    K: Hash + Eq + Clone + MaybeSend + 'static,
51    V: Clone + MaybeSend + 'static,
52    S: BuildHasher + Clone,
53{
54    fn clone(&self) -> Self {
55        let cloned = Self::with_capacity_and_hasher(self.capacity(), self.hasher().clone());
56        for (k, v) in self.iter() {
57            cloned.insert(k, v);
58        }
59        cloned
60    }
61}
62
63/// Inserts every pair, through the same write path [`HopscotchMap::extend`] (`&self`) uses: a
64/// `&mut self` receiver only because [`Extend`] requires one, never taken as exclusive access to
65/// the map's own writers.
66impl<K, V, S> Extend<(K, V)> for HopscotchMap<K, V, S>
67where
68    K: Hash + Eq + Clone + MaybeSend + 'static,
69    V: Clone + MaybeSend + 'static,
70    S: BuildHasher,
71{
72    fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
73        HopscotchMap::extend(&*self, iter);
74    }
75}
76
77/// As `std::collections::HashMap`'s `Extend<(&K, &V)>`: `K` and `V` copied out of the borrowed
78/// pairs, then inserted the same way as the owned-pair impl above.
79impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HopscotchMap<K, V, S>
80where
81    K: Hash + Eq + Copy + MaybeSend + 'static,
82    V: Copy + MaybeSend + 'static,
83    S: BuildHasher,
84{
85    fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
86        HopscotchMap::extend(&*self, iter.into_iter().map(|(k, v)| (*k, *v)));
87    }
88}
89
90/// Content equality of a snapshot of each map: the same length and, for every pair this map's
91/// walk found, the other map holding that key with an equal value. Exact at quiescence and
92/// best-effort under a concurrent write to either map, the same honesty [`HopscotchMap::len`]
93/// documents; a lock-free map cannot hold both maps still for the comparison the way an
94/// exclusively-borrowed `std::collections::HashMap` can.
95impl<K, V, S> PartialEq for HopscotchMap<K, V, S>
96where
97    K: Hash + Eq + Clone + MaybeSend + 'static,
98    V: Clone + PartialEq + MaybeSend + 'static,
99    S: BuildHasher,
100{
101    fn eq(&self, other: &Self) -> bool {
102        self.len() == other.len()
103            && self
104                .iter()
105                .all(|(k, v)| other.get(&k).is_some_and(|ov| ov == v))
106    }
107}
108
109/// `V: Eq` makes the snapshot comparison above reflexive, symmetric and transitive at
110/// quiescence, as `std::collections::HashMap`'s `Eq` is.
111impl<K, V, S> Eq for HopscotchMap<K, V, S>
112where
113    K: Hash + Eq + Clone + MaybeSend + 'static,
114    V: Clone + Eq + MaybeSend + 'static,
115    S: BuildHasher,
116{
117}
kovan_map/hopscotch/std_traits.rs

kovan_map/hopscotch/
std_traits.rs
