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

kovan_map/hashmap/
std_traits.rs
