sparse_hash_map/
map.rs

1//! A memory-efficient open-addressing hash map.
2//!
3//! [`SparseMap`] stores each entry as a `(K, V)` pair inside sparse arrays. At
4//! low load factor it uses far less memory than a flat table because empty
5//! buckets cost about one bit each. Lookup stays fast.
6//!
7//! # Iterator value semantics
8//!
9//! Iteration yields `(&K, &V)`. The pair is never handed out mutably, so a key
10//! cannot change under the map. To mutate a value in place, use
11//! [`SparseMap::get_mut`], [`SparseMap::iter_mut`], or index assignment through
12//! [`SparseMap::get_mut`].
13//!
14//! # Iterator invalidation
15//!
16//! `clear`, `rehash`, and `reserve` invalidate outstanding references. `insert`
17//! and its relatives invalidate them only when an element is actually inserted.
18//! `remove` and `pop_front` always invalidate them.
19
20use core::borrow::Borrow;
21use core::hash::BuildHasher;
22use core::marker::PhantomData;
23
24use crate::growth_policy::{GrowthPolicy, LengthError, PowerOfTwo};
25use crate::hasher::{EqKey, HashKey, StdEq, StdHash};
26use crate::serialize::{Deserialize, DeserializeError, Deserializer, Serialize, Serializer};
27use crate::sparse_hash::{
28    KeySelect, SparseHash, DEFAULT_INIT_BUCKET_COUNT, DEFAULT_MAX_LOAD_FACTOR,
29};
30use crate::sparsity::{Medium, Sparsity};
31
32/// Reads the key from a stored `(K, V)` pair.
33pub struct PairKeySelect<K, V>(PhantomData<(K, V)>);
34
35impl<K, V> KeySelect<(K, V)> for PairKeySelect<K, V> {
36    type Key = K;
37    #[inline]
38    fn key(value: &(K, V)) -> &K {
39        &value.0
40    }
41}
42
43/// A hash map that trades a little insert speed for low memory use.
44///
45/// Type parameters:
46/// - `K`, `V`: key and value types.
47/// - `H`: the hasher. Defaults to [`StdHash`], which uses the standard
48///   [`BuildHasher`]. A hasher yields a `usize` directly.
49/// - `E`: the key comparator. Defaults to [`StdEq`].
50/// - `P`: the growth policy. Defaults to [`PowerOfTwo`] with factor 2.
51/// - `S`: the sparsity level. Defaults to [`Medium`].
52pub struct SparseMap<K, V, H = StdHash, E = StdEq, P = PowerOfTwo<2>, S = Medium> {
53    ht: SparseHash<(K, V), PairKeySelect<K, V>, H, E, P, S>,
54}
55
56impl<K, V> SparseMap<K, V, StdHash, StdEq, PowerOfTwo<2>, Medium> {
57    /// An empty map with no allocation.
58    ///
59    /// Construction places no bound on `K`. The `Hash` and `Eq` bounds belong
60    /// to the operations that hash or compare a key.
61    #[must_use]
62    pub fn new() -> Self {
63        Self::with_bucket_count(DEFAULT_INIT_BUCKET_COUNT)
64    }
65
66    /// An empty map sized for at least `bucket_count` buckets.
67    ///
68    /// # Panics
69    ///
70    /// Panics when `bucket_count` exceeds the policy maximum. Use
71    /// [`SparseMap::try_with_bucket_count`] for the fallible form.
72    #[must_use]
73    pub fn with_bucket_count(bucket_count: usize) -> Self {
74        Self::try_with_bucket_count(bucket_count).expect("bucket count within policy limit")
75    }
76
77    /// An empty map sized for at least `bucket_count` buckets, fallibly.
78    pub fn try_with_bucket_count(bucket_count: usize) -> Result<Self, LengthError> {
79        Ok(Self {
80            ht: SparseHash::new(
81                bucket_count,
82                StdHash::default(),
83                StdEq,
84                DEFAULT_MAX_LOAD_FACTOR,
85            )?,
86        })
87    }
88}
89
90impl<K, V, H, E, P, S> Default for SparseMap<K, V, H, E, P, S>
91where
92    H: Default,
93    E: Default,
94    P: GrowthPolicy,
95{
96    /// An empty map with default parts and no allocation.
97    ///
98    /// Available for any parameterization whose hasher, comparator, and policy
99    /// are themselves [`Default`]. Places no bound on `K`.
100    fn default() -> Self {
101        Self {
102            ht: SparseHash::new(
103                DEFAULT_INIT_BUCKET_COUNT,
104                H::default(),
105                E::default(),
106                DEFAULT_MAX_LOAD_FACTOR,
107            )
108            .expect("zero bucket count is within every policy limit"),
109        }
110    }
111}
112
113impl<K, V, B, P, S> SparseMap<K, V, StdHash<B>, StdEq, P, S>
114where
115    K: Eq,
116    B: BuildHasher + Default,
117    P: GrowthPolicy,
118    S: Sparsity,
119    StdHash<B>: HashKey<K>,
120{
121    /// An empty map that hashes with `B` and uses policy `P` and sparsity `S`.
122    ///
123    /// # Panics
124    ///
125    /// Panics when `bucket_count` exceeds the policy maximum.
126    #[must_use]
127    pub fn with_hasher_and_bucket_count(bucket_count: usize) -> Self {
128        Self {
129            ht: SparseHash::new(
130                bucket_count,
131                StdHash::default(),
132                StdEq,
133                DEFAULT_MAX_LOAD_FACTOR,
134            )
135            .expect("bucket count within policy limit"),
136        }
137    }
138}
139
140impl<K, V, H, E, P, S> SparseMap<K, V, H, E, P, S>
141where
142    H: HashKey<K> + Clone,
143    E: EqKey<K, K> + Clone,
144    P: GrowthPolicy,
145    S: Sparsity,
146{
147    /// Build a map from explicit hasher, comparator, policy, and sparsity.
148    ///
149    /// # Panics
150    ///
151    /// Panics when `bucket_count` exceeds the policy maximum.
152    #[must_use]
153    pub fn with_parts(bucket_count: usize, hash: H, key_eq: E) -> Self {
154        Self {
155            ht: SparseHash::new(bucket_count, hash, key_eq, DEFAULT_MAX_LOAD_FACTOR)
156                .expect("bucket count within policy limit"),
157        }
158    }
159
160    /// Build a map fallibly from explicit parts.
161    pub fn try_with_parts(bucket_count: usize, hash: H, key_eq: E) -> Result<Self, LengthError> {
162        Ok(Self {
163            ht: SparseHash::new(bucket_count, hash, key_eq, DEFAULT_MAX_LOAD_FACTOR)?,
164        })
165    }
166
167    /// Number of entries.
168    #[inline]
169    #[must_use]
170    pub fn len(&self) -> usize {
171        self.ht.len()
172    }
173
174    /// Whether the map holds no entries.
175    #[inline]
176    #[must_use]
177    pub fn is_empty(&self) -> bool {
178        self.ht.is_empty()
179    }
180
181    /// The largest number of entries the map can hold.
182    #[inline]
183    #[must_use]
184    pub fn max_size(&self) -> usize {
185        self.ht.max_size()
186    }
187
188    /// The logical bucket count. Zero for a fresh map.
189    #[inline]
190    #[must_use]
191    pub fn bucket_count(&self) -> usize {
192        self.ht.bucket_count()
193    }
194
195    /// The largest bucket count the map can hold.
196    #[inline]
197    #[must_use]
198    pub fn max_bucket_count(&self) -> usize {
199        self.ht.max_bucket_count()
200    }
201
202    /// Ratio of entries to buckets. Zero for an empty map.
203    #[inline]
204    #[must_use]
205    pub fn load_factor(&self) -> f32 {
206        self.ht.load_factor()
207    }
208
209    /// The maximum load factor before a grow.
210    #[inline]
211    #[must_use]
212    pub fn max_load_factor(&self) -> f32 {
213        self.ht.max_load_factor()
214    }
215
216    /// Set the maximum load factor, clamped to `[0.1, 0.8]`.
217    pub fn set_max_load_factor(&mut self, ml: f32) {
218        self.ht.set_max_load_factor(ml);
219    }
220
221    /// The hasher.
222    #[inline]
223    #[must_use]
224    pub fn hash_function(&self) -> &H {
225        self.ht.hash_function()
226    }
227
228    /// The key comparator.
229    #[inline]
230    #[must_use]
231    pub fn key_eq(&self) -> &E {
232        self.ht.key_eq()
233    }
234
235    /// Remove every entry. Keeps the bucket count.
236    pub fn clear(&mut self) {
237        self.ht.clear();
238    }
239
240    /// Grow so the map holds at least `count` buckets.
241    pub fn rehash(&mut self, count: usize) {
242        self.ht.rehash(count);
243    }
244
245    /// Reserve room for `count` entries without exceeding the load factor.
246    pub fn reserve(&mut self, count: usize) {
247        self.ht.reserve(count);
248    }
249
250    /// Insert `key` with `value`, keeping the existing value on a collision.
251    ///
252    /// Returns whether a new entry was created. `insert` never overwrites: when
253    /// `key` is already present the stored value stays and the passed `value` is
254    /// dropped. To keep the rejected value, use [`SparseMap::try_insert`]. To
255    /// overwrite, use [`SparseMap::insert_or_assign`].
256    pub fn insert(&mut self, key: K, value: V) -> bool {
257        self.ht.insert((key, value)).1
258    }
259
260    /// Insert `key` with `value` only when `key` is absent.
261    ///
262    /// Returns `Ok(&mut V)` with a reference to the newly stored value on a
263    /// fresh insert. Returns `Err((key, value))` with the rejected pair when
264    /// `key` is already present, so an expensive or move-only value is never
265    /// silently dropped. The stored value is left unchanged on collision.
266    pub fn try_insert(&mut self, key: K, value: V) -> Result<&mut V, (K, V)> {
267        let hash = self.ht.hash_function().hash_key(&key);
268        if self.ht.find_position(&key, hash).is_some() {
269            return Err((key, value));
270        }
271        let (pos, _inserted) = self.ht.insert_with_hash((key, value), hash);
272        let (_k, v) = self.ht.value_at_mut(pos);
273        Ok(v)
274    }
275
276    /// A reference to the value at `key`.
277    #[must_use]
278    pub fn get<Q>(&self, key: &Q) -> Option<&V>
279    where
280        K: Borrow<Q>,
281        Q: ?Sized,
282        H: HashKey<Q>,
283        E: EqKey<K, Q>,
284    {
285        let hash = self.ht.hash_function().hash_key(key);
286        self.ht.get(key, hash).map(|(_, v)| v)
287    }
288
289    /// A reference to the value at `key`, using a precomputed hash.
290    ///
291    /// The hash must equal `hash_function().hash_key(key)` or the result is
292    /// unspecified.
293    #[must_use]
294    pub fn get_precalc<Q>(&self, key: &Q, hash: usize) -> Option<&V>
295    where
296        K: Borrow<Q>,
297        Q: ?Sized,
298        H: HashKey<Q>,
299        E: EqKey<K, Q>,
300    {
301        self.ht.get(key, hash).map(|(_, v)| v)
302    }
303
304    /// A mutable reference to the value at `key`.
305    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
306    where
307        K: Borrow<Q>,
308        Q: ?Sized,
309        H: HashKey<Q>,
310        E: EqKey<K, Q>,
311    {
312        let hash = self.ht.hash_function().hash_key(key);
313        self.ht.get_mut(key, hash).map(|(_, v)| v)
314    }
315
316    /// A reference to the key-value pair at `key`.
317    #[must_use]
318    pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
319    where
320        K: Borrow<Q>,
321        Q: ?Sized,
322        H: HashKey<Q>,
323        E: EqKey<K, Q>,
324    {
325        let hash = self.ht.hash_function().hash_key(key);
326        self.ht.get(key, hash).map(|(k, v)| (k, v))
327    }
328
329    /// Whether `key` is present.
330    #[must_use]
331    pub fn contains_key<Q>(&self, key: &Q) -> bool
332    where
333        K: Borrow<Q>,
334        Q: ?Sized,
335        H: HashKey<Q>,
336        E: EqKey<K, Q>,
337    {
338        let hash = self.ht.hash_function().hash_key(key);
339        self.ht.contains(key, hash)
340    }
341
342    /// Whether `key` is present, using a precomputed hash.
343    #[must_use]
344    pub fn contains_key_precalc<Q>(&self, key: &Q, hash: usize) -> bool
345    where
346        K: Borrow<Q>,
347        Q: ?Sized,
348        H: HashKey<Q>,
349        E: EqKey<K, Q>,
350    {
351        self.ht.contains(key, hash)
352    }
353
354    /// 1 when `key` is present, 0 otherwise.
355    ///
356    /// Membership reads more directly through [`SparseMap::contains_key`]. This
357    /// count form mirrors the container contract where a key maps to at most one
358    /// element.
359    #[must_use]
360    pub fn count<Q>(&self, key: &Q) -> usize
361    where
362        K: Borrow<Q>,
363        Q: ?Sized,
364        H: HashKey<Q>,
365        E: EqKey<K, Q>,
366    {
367        usize::from(self.contains_key(key))
368    }
369
370    /// 1 when `key` is present, 0 otherwise, using a precomputed hash.
371    #[must_use]
372    pub fn count_precalc<Q>(&self, key: &Q, hash: usize) -> usize
373    where
374        K: Borrow<Q>,
375        Q: ?Sized,
376        H: HashKey<Q>,
377        E: EqKey<K, Q>,
378    {
379        usize::from(self.contains_key_precalc(key, hash))
380    }
381
382    /// The range of entries equal to `key`.
383    ///
384    /// A map holds at most one entry per key, so the range is empty or a single
385    /// entry. The returned iterator yields `(&K, &V)` and has length 0 or 1.
386    pub fn equal_range<Q>(&self, key: &Q) -> EqualRange<'_, K, V>
387    where
388        K: Borrow<Q>,
389        Q: ?Sized,
390        H: HashKey<Q>,
391        E: EqKey<K, Q>,
392    {
393        EqualRange {
394            item: self.get_key_value(key),
395        }
396    }
397
398    /// The range of entries equal to `key`, using a precomputed hash.
399    pub fn equal_range_precalc<Q>(&self, key: &Q, hash: usize) -> EqualRange<'_, K, V>
400    where
401        K: Borrow<Q>,
402        Q: ?Sized,
403        H: HashKey<Q>,
404        E: EqKey<K, Q>,
405    {
406        let item = self.ht.get(key, hash).map(|(k, v)| (k, v));
407        EqualRange { item }
408    }
409
410    /// A reference to the value at `key`, or a panic when absent.
411    ///
412    /// Indexing with `map[key]` is the idiomatic panic-on-missing form and reads
413    /// the same value. Use [`SparseMap::get`] to handle a missing key without
414    /// panicking.
415    ///
416    /// # Panics
417    ///
418    /// Panics when `key` is not present.
419    #[must_use]
420    pub fn at<Q>(&self, key: &Q) -> &V
421    where
422        K: Borrow<Q>,
423        Q: ?Sized,
424        H: HashKey<Q>,
425        E: EqKey<K, Q>,
426    {
427        self.get(key).expect("couldn't find key")
428    }
429
430    /// A reference to the value at `key`, using a precomputed hash.
431    ///
432    /// # Panics
433    ///
434    /// Panics when `key` is not present.
435    #[must_use]
436    pub fn at_precalc<Q>(&self, key: &Q, hash: usize) -> &V
437    where
438        K: Borrow<Q>,
439        Q: ?Sized,
440        H: HashKey<Q>,
441        E: EqKey<K, Q>,
442    {
443        self.get_precalc(key, hash).expect("couldn't find key")
444    }
445
446    /// Remove `key` and return its value.
447    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
448    where
449        K: Borrow<Q>,
450        Q: ?Sized,
451        H: HashKey<Q>,
452        E: EqKey<K, Q>,
453    {
454        let hash = self.ht.hash_function().hash_key(key);
455        self.ht.remove(key, hash).map(|(_, v)| v)
456    }
457
458    /// Remove `key`. Returns 1 when erased, 0 otherwise.
459    ///
460    /// Use [`SparseMap::remove`] to get the removed value back. `erase` skips
461    /// moving the value out, so it does no work beyond the tombstone.
462    pub fn erase<Q>(&mut self, key: &Q) -> usize
463    where
464        K: Borrow<Q>,
465        Q: ?Sized,
466        H: HashKey<Q>,
467        E: EqKey<K, Q>,
468    {
469        let hash = self.ht.hash_function().hash_key(key);
470        self.ht.erase(key, hash)
471    }
472
473    /// Remove `key` using a precomputed hash. Returns 1 when erased, 0 otherwise.
474    pub fn erase_precalc<Q>(&mut self, key: &Q, hash: usize) -> usize
475    where
476        K: Borrow<Q>,
477        Q: ?Sized,
478        H: HashKey<Q>,
479        E: EqKey<K, Q>,
480    {
481        self.ht.erase(key, hash)
482    }
483
484    /// Remove and return the first entry in iteration order.
485    pub fn pop_front(&mut self) -> Option<(K, V)> {
486        self.ht.remove_nth(0)
487    }
488
489    /// Remove `count` entries starting at iteration index `skip`.
490    ///
491    /// Entries are erased in iteration order. Erasing leaves a tombstone, which
492    /// the next grow or cleanup reclaims. The walk is a single forward pass.
493    pub fn erase_range(&mut self, skip: usize, count: usize) {
494        self.ht.erase_range(skip, count);
495    }
496
497    /// Remove every entry, leaving tombstones. Keeps the bucket count.
498    ///
499    /// Use [`SparseMap::clear`] to also reset the tombstones and counters.
500    pub fn erase_all(&mut self) {
501        self.ht.erase_all();
502    }
503}
504
505impl<K, V, H, E, P, S> SparseMap<K, V, H, E, P, S>
506where
507    H: HashKey<K> + Clone,
508    E: EqKey<K, K> + Clone,
509    P: GrowthPolicy,
510    S: Sparsity,
511{
512    /// The value at `key`, inserting `V::default()` when absent.
513    ///
514    /// This is the index-access behavior of a map that default-inserts.
515    pub fn entry_or_default(&mut self, key: K) -> &mut V
516    where
517        V: Default,
518    {
519        self.try_emplace(key, V::default).0
520    }
521
522    /// Insert only when `key` is absent, building the value on demand.
523    ///
524    /// Returns a reference to the value and whether it was newly inserted. The
525    /// value closure runs only when the key is absent, so a redundant call does
526    /// not build or consume a value.
527    pub fn try_emplace<F>(&mut self, key: K, make: F) -> (&mut V, bool)
528    where
529        F: FnOnce() -> V,
530    {
531        let hash = self.ht.hash_function().hash_key(&key);
532        if let Some(pos) = self.ht.find_position(&key, hash) {
533            let (_k, v) = self.ht.value_at_mut(pos);
534            return (v, false);
535        }
536        let value = make();
537        let (pos, _inserted) = self.ht.insert_with_hash((key, value), hash);
538        let (_k, v) = self.ht.value_at_mut(pos);
539        (v, true)
540    }
541
542    /// Insert `value` at `key`, or overwrite the existing value.
543    ///
544    /// Returns a reference to the value and whether it was newly inserted.
545    pub fn insert_or_assign(&mut self, key: K, value: V) -> (&mut V, bool) {
546        let hash = self.ht.hash_function().hash_key(&key);
547        if let Some(pos) = self.ht.find_position(&key, hash) {
548            let (_k, v) = self.ht.value_at_mut(pos);
549            *v = value;
550            return (v, false);
551        }
552        let (pos, _inserted) = self.ht.insert_with_hash((key, value), hash);
553        let (_k, v) = self.ht.value_at_mut(pos);
554        (v, true)
555    }
556
557    /// Keep only the entries for which `keep` returns true.
558    ///
559    /// The key is shared and the value is mutable. Removed entries become
560    /// tombstones. Each sparse array is scanned once.
561    pub fn retain<F>(&mut self, mut keep: F)
562    where
563        F: FnMut(&K, &mut V) -> bool,
564    {
565        self.ht.retain(|(k, v)| keep(k, v));
566    }
567}
568
569// Iteration.
570
571impl<K, V, H, E, P, S> SparseMap<K, V, H, E, P, S> {
572    /// A forward iterator over `(&K, &V)` pairs.
573    #[must_use]
574    pub fn iter(&self) -> Iter<'_, K, V> {
575        Iter {
576            inner: self.ht.iter(),
577        }
578    }
579
580    /// A forward iterator over `(&K, &mut V)` pairs.
581    ///
582    /// The key stays shared so it cannot change under the map.
583    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
584        IterMut {
585            inner: self.ht.iter_mut(),
586        }
587    }
588
589    /// A forward iterator over keys.
590    #[must_use]
591    pub fn keys(&self) -> Keys<'_, K, V> {
592        Keys {
593            inner: self.ht.iter(),
594        }
595    }
596
597    /// A forward iterator over shared value references.
598    #[must_use]
599    pub fn values(&self) -> Values<'_, K, V> {
600        Values {
601            inner: self.ht.iter(),
602        }
603    }
604}
605
606/// Iterator over `(&K, &V)` pairs of a [`SparseMap`].
607pub struct Iter<'a, K, V> {
608    inner: crate::sparse_hash::Iter<'a, (K, V)>,
609}
610
611impl<'a, K, V> Iterator for Iter<'a, K, V> {
612    type Item = (&'a K, &'a V);
613    fn next(&mut self) -> Option<Self::Item> {
614        self.inner.next().map(|(k, v)| (k, v))
615    }
616}
617
618/// Iterator over `(&K, &mut V)` pairs of a [`SparseMap`].
619pub struct IterMut<'a, K, V> {
620    inner: crate::sparse_hash::IterMut<'a, (K, V)>,
621}
622
623impl<'a, K, V> Iterator for IterMut<'a, K, V> {
624    type Item = (&'a K, &'a mut V);
625    fn next(&mut self) -> Option<Self::Item> {
626        self.inner.next().map(|(k, v)| (&*k, v))
627    }
628}
629
630/// Iterator over keys of a [`SparseMap`].
631pub struct Keys<'a, K, V> {
632    inner: crate::sparse_hash::Iter<'a, (K, V)>,
633}
634
635impl<'a, K, V> Iterator for Keys<'a, K, V> {
636    type Item = &'a K;
637    fn next(&mut self) -> Option<Self::Item> {
638        self.inner.next().map(|(k, _)| k)
639    }
640}
641
642/// Range of entries equal to a key. Length 0 or 1.
643///
644/// A [`SparseMap`] holds at most one entry per key. The range from
645/// [`SparseMap::equal_range`] yields that entry once, or nothing.
646pub struct EqualRange<'a, K, V> {
647    item: Option<(&'a K, &'a V)>,
648}
649
650impl<'a, K, V> Iterator for EqualRange<'a, K, V> {
651    type Item = (&'a K, &'a V);
652    fn next(&mut self) -> Option<Self::Item> {
653        self.item.take()
654    }
655}
656
657impl<K, V> ExactSizeIterator for EqualRange<'_, K, V> {
658    fn len(&self) -> usize {
659        usize::from(self.item.is_some())
660    }
661}
662
663/// Iterator over values of a [`SparseMap`].
664pub struct Values<'a, K, V> {
665    inner: crate::sparse_hash::Iter<'a, (K, V)>,
666}
667
668impl<'a, K, V> Iterator for Values<'a, K, V> {
669    type Item = &'a V;
670    fn next(&mut self) -> Option<Self::Item> {
671        self.inner.next().map(|(_, v)| v)
672    }
673}
674
675impl<'a, K, V, H, E, P, S> IntoIterator for &'a SparseMap<K, V, H, E, P, S> {
676    type Item = (&'a K, &'a V);
677    type IntoIter = Iter<'a, K, V>;
678    fn into_iter(self) -> Self::IntoIter {
679        self.iter()
680    }
681}
682
683impl<'a, K, V, H, E, P, S> IntoIterator for &'a mut SparseMap<K, V, H, E, P, S> {
684    type Item = (&'a K, &'a mut V);
685    type IntoIter = IterMut<'a, K, V>;
686    fn into_iter(self) -> Self::IntoIter {
687        self.iter_mut()
688    }
689}
690
691/// Owning iterator over `(K, V)` pairs of a [`SparseMap`].
692pub struct IntoIter<K, V> {
693    inner: crate::sparse_hash::IntoIter<(K, V)>,
694}
695
696impl<K, V> Iterator for IntoIter<K, V> {
697    type Item = (K, V);
698    fn next(&mut self) -> Option<(K, V)> {
699        self.inner.next()
700    }
701}
702
703impl<K, V, H, E, P, S> IntoIterator for SparseMap<K, V, H, E, P, S> {
704    type Item = (K, V);
705    type IntoIter = IntoIter<K, V>;
706    fn into_iter(self) -> Self::IntoIter {
707        IntoIter {
708            inner: self.ht.into_values(),
709        }
710    }
711}
712
713impl<K, V, H, E, P, S> Extend<(K, V)> for SparseMap<K, V, H, E, P, S>
714where
715    H: HashKey<K> + Clone,
716    E: EqKey<K, K> + Clone,
717    P: GrowthPolicy,
718    S: Sparsity,
719{
720    /// Insert every pair from `iter`. A key already present keeps its value.
721    fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
722        let iter = iter.into_iter();
723        let (lower, _) = iter.size_hint();
724        self.reserve(self.len() + lower);
725        for (k, v) in iter {
726            self.insert(k, v);
727        }
728    }
729}
730
731// Equality. Order-independent. Compares keys through lookup and values with `==`.
732
733impl<K, V, H, E, P, S> PartialEq for SparseMap<K, V, H, E, P, S>
734where
735    V: PartialEq,
736    H: HashKey<K> + Clone,
737    E: EqKey<K, K> + Clone,
738    P: GrowthPolicy,
739    S: Sparsity,
740{
741    fn eq(&self, other: &Self) -> bool {
742        if self.len() != other.len() {
743            return false;
744        }
745        for (k, v) in self.iter() {
746            match other.get(k) {
747                Some(ov) if ov == v => {}
748                _ => return false,
749            }
750        }
751        true
752    }
753}
754
755impl<K, V, H, E, P, S> Eq for SparseMap<K, V, H, E, P, S>
756where
757    V: Eq,
758    H: HashKey<K> + Clone,
759    E: EqKey<K, K> + Clone,
760    P: GrowthPolicy,
761    S: Sparsity,
762{
763}
764
765impl<K, V, H, E, P, S> core::fmt::Debug for SparseMap<K, V, H, E, P, S>
766where
767    K: core::fmt::Debug,
768    V: core::fmt::Debug,
769{
770    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
771        f.debug_map().entries(self.iter()).finish()
772    }
773}
774
775impl<K, V, H, E, P, S, Q> core::ops::Index<&Q> for SparseMap<K, V, H, E, P, S>
776where
777    K: Borrow<Q>,
778    Q: ?Sized,
779    H: HashKey<K> + HashKey<Q> + Clone,
780    E: EqKey<K, K> + EqKey<K, Q> + Clone,
781    P: GrowthPolicy,
782    S: Sparsity,
783{
784    type Output = V;
785
786    /// The value at `key`.
787    ///
788    /// # Panics
789    ///
790    /// Panics when `key` is not present.
791    fn index(&self, key: &Q) -> &V {
792        self.at(key)
793    }
794}
795
796impl<K, V, H, E, P, S> Clone for SparseMap<K, V, H, E, P, S>
797where
798    (K, V): Clone,
799    H: Clone,
800    E: Clone,
801    P: Clone,
802{
803    fn clone(&self) -> Self {
804        Self {
805            ht: self.ht.clone(),
806        }
807    }
808}
809
810// Serialization.
811
812impl<K, V, H, E, P, S> SparseMap<K, V, H, E, P, S>
813where
814    (K, V): Serialize,
815{
816    /// Write the map through `serializer` in protocol order.
817    pub fn serialize<Sz: Serializer>(&self, serializer: &mut Sz) {
818        self.ht.serialize(serializer);
819    }
820}
821
822impl<K, V, H, E, P, S> SparseMap<K, V, H, E, P, S>
823where
824    H: HashKey<K> + Clone,
825    E: EqKey<K, K> + Clone,
826    P: GrowthPolicy,
827    S: Sparsity,
828    (K, V): Serialize + Deserialize,
829{
830    /// Read a map written by [`SparseMap::serialize`].
831    ///
832    /// See the engine docs for the meaning of `hash_compatible`.
833    pub fn deserialize_with<D: Deserializer>(
834        deserializer: &mut D,
835        hash_compatible: bool,
836        hash: H,
837        key_eq: E,
838    ) -> Result<Self, DeserializeError> {
839        Ok(Self {
840            ht: SparseHash::deserialize(deserializer, hash_compatible, hash, key_eq)?,
841        })
842    }
843}
sparse_hash_map/map.rs

sparse_hash_map/
map.rs
