flat_multimap/
map.rs

1#[cfg(feature = "rayon")]
2pub use crate::rayon::map as rayon;
3
4use hashbrown::raw::{RawDrain, RawIntoIter, RawIter, RawTable};
5use hashbrown::TryReserveError;
6use std::borrow::Borrow;
7use std::collections::hash_map::RandomState;
8use std::fmt::{self, Debug};
9use std::hash::{BuildHasher, Hash, Hasher};
10use std::iter::FusedIterator;
11use std::marker::PhantomData;
12
13/// Multimap implementation where entries are stored as a flattened hash map.
14///
15/// # Examples
16///
17/// ```
18/// use flat_multimap::FlatMultimap;
19///
20/// let mut map = FlatMultimap::new();
21/// map.insert(1, 1);
22/// map.insert(1, 2);
23/// map.insert(2, 3);
24///
25/// assert_eq!(map.len(), 3);
26/// ```
27#[derive(Clone)]
28pub struct FlatMultimap<K, V, S = RandomState> {
29    hash_builder: S,
30    pub(crate) table: RawTable<(K, V)>,
31}
32
33impl<K, V> FlatMultimap<K, V, RandomState> {
34    /// Creates an empty `FlatMultimap` with a capacity of 0,
35    /// so it will not allocate until it is first inserted into.
36    ///
37    /// # Examples
38    ///
39    /// ```
40    /// use flat_multimap::FlatMultimap;
41    ///
42    /// let mut map: FlatMultimap<&str, i32> = FlatMultimap::new();
43    ///
44    /// assert_eq!(map.capacity(), 0);
45    /// ```
46    #[must_use]
47    pub fn new() -> Self {
48        Self::with_hasher(RandomState::default())
49    }
50
51    /// Creates an empty `FlatMultimap` with at least the specified capacity.
52    #[must_use]
53    pub fn with_capacity(capacity: usize) -> Self {
54        Self::with_capacity_and_hasher(capacity, RandomState::default())
55    }
56}
57
58impl<K, V, S> FlatMultimap<K, V, S> {
59    /// Creates an empty `FlatMultimap` with default capacity which will use the given hash builder to hash keys.
60    pub const fn with_hasher(hash_builder: S) -> Self {
61        Self {
62            hash_builder,
63            table: RawTable::new(),
64        }
65    }
66
67    /// Creates an empty `FlatMultimap` with at least the specified capacity, using the given hash builder to hash keys.
68    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
69        Self {
70            hash_builder,
71            table: RawTable::with_capacity(capacity),
72        }
73    }
74
75    /// Returns the number of elements the map can hold without reallocating.
76    pub fn capacity(&self) -> usize {
77        self.table.capacity()
78    }
79
80    /// Returns a reference to the map’s [`BuildHasher`].    
81    pub const fn hasher(&self) -> &S {
82        &self.hash_builder
83    }
84
85    /// Returns the number of elements in the map.
86    pub fn len(&self) -> usize {
87        self.table.len()
88    }
89
90    /// Returns `true` if the map contains no elements.
91    pub fn is_empty(&self) -> bool {
92        self.table.is_empty()
93    }
94
95    /// Clears the map, returning all key-value pairs as an iterator.
96    pub fn drain(&mut self) -> Drain<'_, K, V> {
97        Drain {
98            inner: self.table.drain(),
99        }
100    }
101
102    /// Retains only the elements specified by the predicate.
103    pub fn retain<F>(&mut self, mut f: F)
104    where
105        F: FnMut(&K, &mut V) -> bool,
106    {
107        unsafe {
108            for item in self.table.iter() {
109                let &mut (ref key, ref mut value) = item.as_mut();
110
111                if !f(key, value) {
112                    self.table.erase(item);
113                }
114            }
115        }
116    }
117
118    /// Clears the map, removing all key-value pairs. Keeps the allocated memory for reuse.
119    pub fn clear(&mut self) {
120        self.table.clear();
121    }
122
123    /// An iterator visiting all key-value pairs in arbitrary order. The iterator element type is `(&'a K, &'a V)`.
124    pub fn iter(&self) -> Iter<'_, K, V> {
125        unsafe {
126            Iter {
127                iter: self.table.iter(),
128                phantom: PhantomData,
129            }
130        }
131    }
132
133    /// An iterator visiting all key-value pairs in arbitrary order, with mutable references to the values.
134    /// The iterator element type is (&'a K, &'a mut V).
135    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
136        unsafe {
137            IterMut {
138                iter: self.table.iter(),
139                phantom: PhantomData,
140            }
141        }
142    }
143
144    /// An iterator visiting all keys in arbitrary order. The iterator element type is `&'a K`.
145    ///
146    /// # Examples
147    ///
148    /// ```
149    /// use flat_multimap::FlatMultimap;
150    ///
151    /// let mut map = FlatMultimap::new();
152    /// map.insert(1, 1);
153    /// map.insert(1, 2);
154    /// map.insert(2, 3);
155    ///
156    /// let mut keys: Vec<_> = map.keys().collect();
157    /// keys.sort_unstable(); // Sort since the keys are visited in arbitrary order.
158    ///
159    /// assert_eq!(keys, [&1, &1, &2]);
160    /// ```
161    pub fn keys(&self) -> Keys<'_, K, V> {
162        Keys { iter: self.iter() }
163    }
164
165    /// Creates a consuming iterator visiting all the keys in arbitrary order.
166    /// The map cannot be used after calling this. The iterator element type is `K`.
167    pub fn into_keys(self) -> IntoKeys<K, V> {
168        IntoKeys {
169            iter: self.into_iter(),
170        }
171    }
172
173    /// An iterator visiting all values in arbitrary order. The iterator element type is `&'a V`.
174    pub fn values(&self) -> Values<'_, K, V> {
175        Values { iter: self.iter() }
176    }
177
178    /// An iterator visiting all values mutably in arbitrary order. The iterator element type is `&'a mut V`.
179    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
180        ValuesMut {
181            iter: self.iter_mut(),
182        }
183    }
184
185    /// Creates a consuming iterator visiting all the values in arbitrary order.
186    /// The map cannot be used after calling this. The iterator element type is `V`.
187    pub fn into_values(self) -> IntoValues<K, V> {
188        IntoValues {
189            iter: self.into_iter(),
190        }
191    }
192}
193
194impl<K, V, S> FlatMultimap<K, V, S>
195where
196    K: Eq + Hash,
197    S: BuildHasher,
198{
199    /// Reserves capacity for at least additional more elements to be inserted in the `FlatMultimap`.
200    pub fn reserve(&mut self, additional: usize) {
201        self.table
202            .reserve(additional, make_hasher(&self.hash_builder));
203    }
204
205    /// Tries to reserve capacity for at least additional more elements to be inserted in the `FlatMultimap`.
206    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
207        self.table
208            .try_reserve(additional, make_hasher(&self.hash_builder))
209    }
210
211    /// Shrinks the capacity of the map as much as possible.
212    pub fn shrink_to_fit(&mut self) {
213        self.table.shrink_to(0, make_hasher(&self.hash_builder));
214    }
215
216    /// Shrinks the capacity of the map with a lower limit.
217    pub fn shrink_to(&mut self, min_capacity: usize) {
218        self.table
219            .shrink_to(min_capacity, make_hasher(&self.hash_builder));
220    }
221
222    /// Inserts a key-value pair into the map.
223    pub fn insert(&mut self, key: K, value: V) {
224        let hash = make_hash(&self.hash_builder, &key);
225
226        self.table
227            .insert(hash, (key, value), make_hasher(&self.hash_builder));
228    }
229
230    /// Removes an arbitrary value with the given key from the map, returning the removed value if there was a value at the key.
231    ///
232    /// # Examples
233    ///
234    /// ```
235    /// use flat_multimap::FlatMultimap;
236    ///
237    /// let mut map = FlatMultimap::new();
238    /// map.insert(1, 1);
239    /// map.insert(1, 2);
240    ///
241    /// assert!(map.remove(&1).is_some()); // Could be either Some(1) or Some(2).
242    /// assert!(map.remove(&1).is_some()); // Could be either Some(1) or Some(2), depending on the previous remove.
243    /// assert!(map.remove(&1).is_none());
244    /// ```
245    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
246    where
247        K: Borrow<Q>,
248        Q: ?Sized + Hash + Eq,
249    {
250        let hash = make_hash(&self.hash_builder, key);
251
252        self.table
253            .remove_entry(hash, equivalent_key(key))
254            .map(|(_, value)| value)
255    }
256
257    /// Returns `true` if the map contains at least a single value for the specified key.
258    pub fn contains_key<Q>(&self, key: &Q) -> bool
259    where
260        K: Borrow<Q>,
261        Q: ?Sized + Hash + Eq,
262    {
263        let hash = make_hash(&self.hash_builder, key);
264
265        self.table.find(hash, equivalent_key(key)).is_some()
266    }
267}
268
269impl<K, V, S> FromIterator<(K, V)> for FlatMultimap<K, V, S>
270where
271    K: Eq + Hash,
272    S: BuildHasher + Default,
273{
274    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
275        let iter = iter.into_iter();
276        let mut map = Self::with_capacity_and_hasher(iter.size_hint().0, S::default());
277        iter.for_each(|(k, v)| {
278            map.insert(k, v);
279        });
280        map
281    }
282}
283
284impl<K, V, S> Extend<(K, V)> for FlatMultimap<K, V, S>
285where
286    K: Eq + Hash,
287    S: BuildHasher,
288{
289    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
290        let iter = iter.into_iter();
291        self.reserve(iter.size_hint().0);
292        iter.for_each(move |(k, v)| {
293            self.insert(k, v);
294        });
295    }
296}
297
298impl<'a, K, V, S> Extend<(&'a K, &'a V)> for FlatMultimap<K, V, S>
299where
300    K: Eq + Hash + Copy,
301    V: Copy,
302    S: BuildHasher,
303{
304    fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
305        self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
306    }
307}
308
309impl<'a, K, V, S> Extend<&'a (K, V)> for FlatMultimap<K, V, S>
310where
311    K: Eq + Hash + Copy,
312    V: Copy,
313    S: BuildHasher,
314{
315    fn extend<T: IntoIterator<Item = &'a (K, V)>>(&mut self, iter: T) {
316        self.extend(iter.into_iter().map(|&(key, value)| (key, value)));
317    }
318}
319
320impl<'a, K, V, S> IntoIterator for &'a FlatMultimap<K, V, S> {
321    type Item = (&'a K, &'a V);
322    type IntoIter = Iter<'a, K, V>;
323
324    fn into_iter(self) -> Iter<'a, K, V> {
325        self.iter()
326    }
327}
328
329impl<'a, K, V, S> IntoIterator for &'a mut FlatMultimap<K, V, S> {
330    type Item = (&'a K, &'a mut V);
331    type IntoIter = IterMut<'a, K, V>;
332
333    fn into_iter(self) -> IterMut<'a, K, V> {
334        self.iter_mut()
335    }
336}
337
338impl<K, V, S> IntoIterator for FlatMultimap<K, V, S> {
339    type Item = (K, V);
340    type IntoIter = IntoIter<K, V>;
341
342    fn into_iter(self) -> IntoIter<K, V> {
343        IntoIter {
344            iter: self.table.into_iter(),
345        }
346    }
347}
348
349impl<K, V, S> Default for FlatMultimap<K, V, S>
350where
351    S: Default,
352{
353    fn default() -> Self {
354        FlatMultimap {
355            hash_builder: Default::default(),
356            table: RawTable::new(),
357        }
358    }
359}
360
361impl<K, V, S> Debug for FlatMultimap<K, V, S>
362where
363    K: Debug,
364    V: Debug,
365{
366    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
367        f.debug_map().entries(self.iter()).finish()
368    }
369}
370
371impl<K, V, const N: usize> From<[(K, V); N]> for FlatMultimap<K, V, RandomState>
372where
373    K: Eq + Hash,
374{
375    fn from(arr: [(K, V); N]) -> Self {
376        arr.into_iter().collect()
377    }
378}
379
380/// A draining iterator over the entries of a `FlatMultimap`.
381pub struct Drain<'a, K, V> {
382    inner: RawDrain<'a, (K, V)>,
383}
384
385impl<K, V> Drain<'_, K, V> {
386    pub(crate) fn iter(&self) -> Iter<'_, K, V> {
387        Iter {
388            iter: self.inner.iter(),
389            phantom: PhantomData,
390        }
391    }
392}
393
394impl<'a, K, V> Iterator for Drain<'a, K, V> {
395    type Item = (K, V);
396
397    fn next(&mut self) -> Option<(K, V)> {
398        self.inner.next()
399    }
400
401    fn size_hint(&self) -> (usize, Option<usize>) {
402        self.inner.size_hint()
403    }
404}
405
406impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
407    fn len(&self) -> usize {
408        self.inner.len()
409    }
410}
411
412impl<K, V> FusedIterator for Drain<'_, K, V> {}
413
414impl<K, V> Debug for Drain<'_, K, V>
415where
416    K: Debug,
417    V: Debug,
418{
419    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
420        f.debug_list().entries(self.iter()).finish()
421    }
422}
423
424/// An iterator over the entries of a `FlatMultimap`.
425pub struct Iter<'a, K, V> {
426    iter: RawIter<(K, V)>,
427    phantom: PhantomData<(&'a K, &'a V)>,
428}
429
430impl<K, V> Clone for Iter<'_, K, V> {
431    fn clone(&self) -> Self {
432        Self {
433            iter: self.iter.clone(),
434            phantom: self.phantom,
435        }
436    }
437}
438
439impl<'a, K, V> Iterator for Iter<'a, K, V> {
440    type Item = (&'a K, &'a V);
441
442    fn next(&mut self) -> Option<(&'a K, &'a V)> {
443        self.iter.next().map(|bucket| unsafe {
444            let bucket = bucket.as_ref();
445            (&bucket.0, &bucket.1)
446        })
447    }
448
449    fn size_hint(&self) -> (usize, Option<usize>) {
450        self.iter.size_hint()
451    }
452}
453
454impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
455    fn len(&self) -> usize {
456        self.iter.len()
457    }
458}
459
460impl<K, V> FusedIterator for Iter<'_, K, V> {}
461
462impl<K: Debug, V: Debug> Debug for Iter<'_, K, V> {
463    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
464        f.debug_list().entries(self.clone()).finish()
465    }
466}
467
468/// A mutable iterator over the entries of a `FlatMultimap`.
469pub struct IterMut<'a, K, V> {
470    iter: RawIter<(K, V)>,
471    phantom: PhantomData<(&'a K, &'a mut V)>,
472}
473
474impl<'a, K, V> IterMut<'a, K, V> {
475    fn iter(&self) -> Iter<'a, K, V> {
476        Iter {
477            iter: self.iter.clone(),
478            phantom: PhantomData,
479        }
480    }
481}
482
483impl<'a, K, V> Iterator for IterMut<'a, K, V> {
484    type Item = (&'a K, &'a mut V);
485
486    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
487        self.iter.next().map(|bucket| unsafe {
488            let bucket = bucket.as_mut();
489            (&bucket.0, &mut bucket.1)
490        })
491    }
492
493    fn size_hint(&self) -> (usize, Option<usize>) {
494        self.iter.size_hint()
495    }
496}
497
498impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
499    fn len(&self) -> usize {
500        self.iter.len()
501    }
502}
503
504impl<K, V> FusedIterator for IterMut<'_, K, V> {}
505
506impl<K, V> Debug for IterMut<'_, K, V>
507where
508    K: Debug,
509    V: Debug,
510{
511    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
512        f.debug_list().entries(self.iter()).finish()
513    }
514}
515
516/// An owning iterator over the entries of a `FlatMultimap`.
517pub struct IntoIter<K, V> {
518    iter: RawIntoIter<(K, V)>,
519}
520
521impl<K, V> IntoIter<K, V> {
522    fn iter(&self) -> Iter<'_, K, V> {
523        Iter {
524            iter: self.iter.iter(),
525            phantom: PhantomData,
526        }
527    }
528}
529
530impl<K, V> Iterator for IntoIter<K, V> {
531    type Item = (K, V);
532
533    fn next(&mut self) -> Option<(K, V)> {
534        self.iter.next()
535    }
536
537    fn size_hint(&self) -> (usize, Option<usize>) {
538        self.iter.size_hint()
539    }
540}
541
542impl<K, V> ExactSizeIterator for IntoIter<K, V> {
543    fn len(&self) -> usize {
544        self.iter.len()
545    }
546}
547
548impl<K, V> FusedIterator for IntoIter<K, V> {}
549
550impl<K: Debug, V: Debug> fmt::Debug for IntoIter<K, V> {
551    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
552        f.debug_list().entries(self.iter()).finish()
553    }
554}
555
556/// An iterator over the keys of a `FlatMultimap`.
557pub struct Keys<'a, K, V> {
558    iter: Iter<'a, K, V>,
559}
560
561impl<K, V> Clone for Keys<'_, K, V> {
562    fn clone(&self) -> Self {
563        Self {
564            iter: self.iter.clone(),
565        }
566    }
567}
568
569impl<'a, K, V> Iterator for Keys<'a, K, V> {
570    type Item = &'a K;
571
572    fn next(&mut self) -> Option<&'a K> {
573        self.iter.next().map(|(key, _)| key)
574    }
575
576    fn size_hint(&self) -> (usize, Option<usize>) {
577        self.iter.size_hint()
578    }
579}
580
581impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
582    fn len(&self) -> usize {
583        self.iter.len()
584    }
585}
586
587impl<K, V> FusedIterator for Keys<'_, K, V> {}
588
589impl<K: Debug, V> Debug for Keys<'_, K, V> {
590    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
591        f.debug_list().entries(self.clone()).finish()
592    }
593}
594
595/// An owning iterator over the keys of a `FlatMultimap`.
596pub struct IntoKeys<K, V> {
597    iter: IntoIter<K, V>,
598}
599
600impl<K, V> IntoKeys<K, V> {
601    pub(crate) fn iter(&self) -> Keys<'_, K, V> {
602        Keys {
603            iter: self.iter.iter(),
604        }
605    }
606}
607
608impl<K, V> Iterator for IntoKeys<K, V> {
609    type Item = K;
610
611    fn next(&mut self) -> Option<K> {
612        self.iter.next().map(|(key, _)| key)
613    }
614
615    fn size_hint(&self) -> (usize, Option<usize>) {
616        self.iter.size_hint()
617    }
618}
619
620impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
621    fn len(&self) -> usize {
622        self.iter.len()
623    }
624}
625
626impl<K, V> FusedIterator for IntoKeys<K, V> {}
627
628impl<K: Debug, V: Debug> Debug for IntoKeys<K, V> {
629    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
630        f.debug_list()
631            .entries(self.iter.iter().map(|(k, _)| k))
632            .finish()
633    }
634}
635
636/// An iterator over the values of a `FlatMultimap`.
637pub struct Values<'a, K, V> {
638    iter: Iter<'a, K, V>,
639}
640
641impl<K, V> Clone for Values<'_, K, V> {
642    fn clone(&self) -> Self {
643        Self {
644            iter: self.iter.clone(),
645        }
646    }
647}
648
649impl<'a, K, V> Iterator for Values<'a, K, V> {
650    type Item = &'a V;
651
652    fn next(&mut self) -> Option<&'a V> {
653        self.iter.next().map(|(_, value)| value)
654    }
655
656    fn size_hint(&self) -> (usize, Option<usize>) {
657        self.iter.size_hint()
658    }
659}
660
661impl<K, V> ExactSizeIterator for Values<'_, K, V> {
662    fn len(&self) -> usize {
663        self.iter.len()
664    }
665}
666
667impl<K, V> FusedIterator for Values<'_, K, V> {}
668
669impl<K, V: Debug> Debug for Values<'_, K, V> {
670    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
671        f.debug_list().entries(self.clone()).finish()
672    }
673}
674
675/// A mutable iterator over the values of a `FlatMultimap`.
676pub struct ValuesMut<'a, K, V> {
677    iter: IterMut<'a, K, V>,
678}
679
680impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
681    type Item = &'a mut V;
682
683    fn next(&mut self) -> Option<&'a mut V> {
684        self.iter.next().map(|(_, value)| value)
685    }
686
687    fn size_hint(&self) -> (usize, Option<usize>) {
688        self.iter.size_hint()
689    }
690}
691
692impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
693    fn len(&self) -> usize {
694        self.iter.len()
695    }
696}
697
698impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
699
700impl<K, V: Debug> fmt::Debug for ValuesMut<'_, K, V> {
701    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
702        f.debug_list()
703            .entries(self.iter.iter().map(|(_, val)| val))
704            .finish()
705    }
706}
707
708/// An owning iterator over the values of a `FlatMultimap`.
709pub struct IntoValues<K, V> {
710    iter: IntoIter<K, V>,
711}
712
713impl<K, V> Iterator for IntoValues<K, V> {
714    type Item = V;
715
716    fn next(&mut self) -> Option<V> {
717        self.iter.next().map(|(_, value)| value)
718    }
719
720    fn size_hint(&self) -> (usize, Option<usize>) {
721        self.iter.size_hint()
722    }
723}
724
725impl<K, V> ExactSizeIterator for IntoValues<K, V> {
726    fn len(&self) -> usize {
727        self.iter.len()
728    }
729}
730
731impl<K, V> FusedIterator for IntoValues<K, V> {}
732
733impl<K, V: Debug> Debug for IntoValues<K, V> {
734    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
735        f.debug_list()
736            .entries(self.iter.iter().map(|(_, v)| v))
737            .finish()
738    }
739}
740
741fn equivalent_key<Q, K, V>(k: &Q) -> impl Fn(&(K, V)) -> bool + '_
742where
743    K: Borrow<Q>,
744    Q: ?Sized + Hash + Eq,
745{
746    move |x| k == x.0.borrow()
747}
748
749fn make_hash<T, S>(hash_builder: &S, value: &T) -> u64
750where
751    T: ?Sized + Hash,
752    S: BuildHasher,
753{
754    let mut state = hash_builder.build_hasher();
755    value.hash(&mut state);
756    state.finish()
757}
758
759fn make_hasher<K, V, S>(hash_builder: &S) -> impl Fn(&(K, V)) -> u64 + '_
760where
761    K: Hash,
762    S: BuildHasher,
763{
764    move |val| make_hash(hash_builder, &val.0)
765}
flat_multimap/map.rs

flat_multimap/
map.rs
