indexmap/rayon/
map.rs

1//! Parallel iterator types for [`IndexMap`] with [`rayon`][::rayon].
2//!
3//! You will rarely need to interact with this module directly unless you need to name one of the
4//! iterator types.
5
6use super::collect;
7use rayon::iter::plumbing::{Consumer, ProducerCallback, UnindexedConsumer};
8use rayon::prelude::*;
9
10use crate::vec::Vec;
11use alloc::boxed::Box;
12use core::cmp::Ordering;
13use core::fmt;
14use core::hash::{BuildHasher, Hash};
15use core::ops::RangeBounds;
16
17use crate::map::Slice;
18use crate::Bucket;
19use crate::Entries;
20use crate::IndexMap;
21
22impl<K, V, S> IntoParallelIterator for IndexMap<K, V, S>
23where
24    K: Send,
25    V: Send,
26{
27    type Item = (K, V);
28    type Iter = IntoParIter<K, V>;
29
30    fn into_par_iter(self) -> Self::Iter {
31        IntoParIter {
32            entries: self.into_entries(),
33        }
34    }
35}
36
37impl<K, V> IntoParallelIterator for Box<Slice<K, V>>
38where
39    K: Send,
40    V: Send,
41{
42    type Item = (K, V);
43    type Iter = IntoParIter<K, V>;
44
45    fn into_par_iter(self) -> Self::Iter {
46        IntoParIter {
47            entries: self.into_entries(),
48        }
49    }
50}
51
52/// A parallel owning iterator over the entries of an [`IndexMap`].
53///
54/// This `struct` is created by the [`IndexMap::into_par_iter`] method
55/// (provided by rayon's [`IntoParallelIterator`] trait). See its documentation for more.
56pub struct IntoParIter<K, V> {
57    entries: Vec<Bucket<K, V>>,
58}
59
60impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoParIter<K, V> {
61    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
62        let iter = self.entries.iter().map(Bucket::refs);
63        f.debug_list().entries(iter).finish()
64    }
65}
66
67impl<K: Send, V: Send> ParallelIterator for IntoParIter<K, V> {
68    type Item = (K, V);
69
70    parallel_iterator_methods!(Bucket::key_value);
71}
72
73impl<K: Send, V: Send> IndexedParallelIterator for IntoParIter<K, V> {
74    indexed_parallel_iterator_methods!(Bucket::key_value);
75}
76
77impl<'a, K, V, S> IntoParallelIterator for &'a IndexMap<K, V, S>
78where
79    K: Sync,
80    V: Sync,
81{
82    type Item = (&'a K, &'a V);
83    type Iter = ParIter<'a, K, V>;
84
85    fn into_par_iter(self) -> Self::Iter {
86        ParIter {
87            entries: self.as_entries(),
88        }
89    }
90}
91
92impl<'a, K, V> IntoParallelIterator for &'a Slice<K, V>
93where
94    K: Sync,
95    V: Sync,
96{
97    type Item = (&'a K, &'a V);
98    type Iter = ParIter<'a, K, V>;
99
100    fn into_par_iter(self) -> Self::Iter {
101        ParIter {
102            entries: &self.entries,
103        }
104    }
105}
106
107/// A parallel iterator over the entries of an [`IndexMap`].
108///
109/// This `struct` is created by the [`IndexMap::par_iter`] method
110/// (provided by rayon's [`IntoParallelRefIterator`] trait). See its documentation for more.
111///
112/// [`IndexMap::par_iter`]: ../struct.IndexMap.html#method.par_iter
113pub struct ParIter<'a, K, V> {
114    entries: &'a [Bucket<K, V>],
115}
116
117impl<K, V> Clone for ParIter<'_, K, V> {
118    fn clone(&self) -> Self {
119        ParIter { ..*self }
120    }
121}
122
123impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for ParIter<'_, K, V> {
124    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
125        let iter = self.entries.iter().map(Bucket::refs);
126        f.debug_list().entries(iter).finish()
127    }
128}
129
130impl<'a, K: Sync, V: Sync> ParallelIterator for ParIter<'a, K, V> {
131    type Item = (&'a K, &'a V);
132
133    parallel_iterator_methods!(Bucket::refs);
134}
135
136impl<K: Sync, V: Sync> IndexedParallelIterator for ParIter<'_, K, V> {
137    indexed_parallel_iterator_methods!(Bucket::refs);
138}
139
140impl<'a, K, V, S> IntoParallelIterator for &'a mut IndexMap<K, V, S>
141where
142    K: Sync + Send,
143    V: Send,
144{
145    type Item = (&'a K, &'a mut V);
146    type Iter = ParIterMut<'a, K, V>;
147
148    fn into_par_iter(self) -> Self::Iter {
149        ParIterMut {
150            entries: self.as_entries_mut(),
151        }
152    }
153}
154
155impl<'a, K, V> IntoParallelIterator for &'a mut Slice<K, V>
156where
157    K: Sync + Send,
158    V: Send,
159{
160    type Item = (&'a K, &'a mut V);
161    type Iter = ParIterMut<'a, K, V>;
162
163    fn into_par_iter(self) -> Self::Iter {
164        ParIterMut {
165            entries: &mut self.entries,
166        }
167    }
168}
169
170/// A parallel mutable iterator over the entries of an [`IndexMap`].
171///
172/// This `struct` is created by the [`IndexMap::par_iter_mut`] method
173/// (provided by rayon's [`IntoParallelRefMutIterator`] trait). See its documentation for more.
174///
175/// [`IndexMap::par_iter_mut`]: ../struct.IndexMap.html#method.par_iter_mut
176pub struct ParIterMut<'a, K, V> {
177    entries: &'a mut [Bucket<K, V>],
178}
179
180impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for ParIterMut<'_, K, V> {
181    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
182        let iter = self.entries.iter().map(Bucket::refs);
183        f.debug_list().entries(iter).finish()
184    }
185}
186
187impl<'a, K: Sync + Send, V: Send> ParallelIterator for ParIterMut<'a, K, V> {
188    type Item = (&'a K, &'a mut V);
189
190    parallel_iterator_methods!(Bucket::ref_mut);
191}
192
193impl<K: Sync + Send, V: Send> IndexedParallelIterator for ParIterMut<'_, K, V> {
194    indexed_parallel_iterator_methods!(Bucket::ref_mut);
195}
196
197impl<'a, K, V, S> ParallelDrainRange<usize> for &'a mut IndexMap<K, V, S>
198where
199    K: Send,
200    V: Send,
201{
202    type Item = (K, V);
203    type Iter = ParDrain<'a, K, V>;
204
205    fn par_drain<R: RangeBounds<usize>>(self, range: R) -> Self::Iter {
206        ParDrain {
207            entries: self.core.par_drain(range),
208        }
209    }
210}
211
212/// A parallel draining iterator over the entries of an [`IndexMap`].
213///
214/// This `struct` is created by the [`IndexMap::par_drain`] method
215/// (provided by rayon's [`ParallelDrainRange`] trait). See its documentation for more.
216///
217/// [`IndexMap::par_drain`]: ../struct.IndexMap.html#method.par_drain
218pub struct ParDrain<'a, K: Send, V: Send> {
219    entries: rayon::vec::Drain<'a, Bucket<K, V>>,
220}
221
222impl<K: Send, V: Send> ParallelIterator for ParDrain<'_, K, V> {
223    type Item = (K, V);
224
225    parallel_iterator_methods!(Bucket::key_value);
226}
227
228impl<K: Send, V: Send> IndexedParallelIterator for ParDrain<'_, K, V> {
229    indexed_parallel_iterator_methods!(Bucket::key_value);
230}
231
232/// Parallel iterator methods and other parallel methods.
233///
234/// The following methods **require crate feature `"rayon"`**.
235///
236/// See also the `IntoParallelIterator` implementations.
237impl<K, V, S> IndexMap<K, V, S>
238where
239    K: Sync,
240    V: Sync,
241{
242    /// Return a parallel iterator over the keys of the map.
243    ///
244    /// While parallel iterators can process items in any order, their relative order
245    /// in the map is still preserved for operations like `reduce` and `collect`.
246    pub fn par_keys(&self) -> ParKeys<'_, K, V> {
247        ParKeys {
248            entries: self.as_entries(),
249        }
250    }
251
252    /// Return a parallel iterator over the values of the map.
253    ///
254    /// While parallel iterators can process items in any order, their relative order
255    /// in the map is still preserved for operations like `reduce` and `collect`.
256    pub fn par_values(&self) -> ParValues<'_, K, V> {
257        ParValues {
258            entries: self.as_entries(),
259        }
260    }
261}
262
263/// Parallel iterator methods and other parallel methods.
264///
265/// The following methods **require crate feature `"rayon"`**.
266///
267/// See also the `IntoParallelIterator` implementations.
268impl<K, V> Slice<K, V>
269where
270    K: Sync,
271    V: Sync,
272{
273    /// Return a parallel iterator over the keys of the map slice.
274    ///
275    /// While parallel iterators can process items in any order, their relative order
276    /// in the slice is still preserved for operations like `reduce` and `collect`.
277    pub fn par_keys(&self) -> ParKeys<'_, K, V> {
278        ParKeys {
279            entries: &self.entries,
280        }
281    }
282
283    /// Return a parallel iterator over the values of the map slice.
284    ///
285    /// While parallel iterators can process items in any order, their relative order
286    /// in the slice is still preserved for operations like `reduce` and `collect`.
287    pub fn par_values(&self) -> ParValues<'_, K, V> {
288        ParValues {
289            entries: &self.entries,
290        }
291    }
292}
293
294impl<K, V, S> IndexMap<K, V, S>
295where
296    K: Hash + Eq + Sync,
297    V: Sync,
298    S: BuildHasher,
299{
300    /// Returns `true` if `self` contains all of the same key-value pairs as `other`,
301    /// regardless of each map's indexed order, determined in parallel.
302    pub fn par_eq<V2, S2>(&self, other: &IndexMap<K, V2, S2>) -> bool
303    where
304        V: PartialEq<V2>,
305        V2: Sync,
306        S2: BuildHasher + Sync,
307    {
308        self.len() == other.len()
309            && self
310                .par_iter()
311                .all(move |(key, value)| other.get(key).map_or(false, |v| *value == *v))
312    }
313}
314
315/// A parallel iterator over the keys of an [`IndexMap`].
316///
317/// This `struct` is created by the [`IndexMap::par_keys`] method.
318/// See its documentation for more.
319pub struct ParKeys<'a, K, V> {
320    entries: &'a [Bucket<K, V>],
321}
322
323impl<K, V> Clone for ParKeys<'_, K, V> {
324    fn clone(&self) -> Self {
325        ParKeys { ..*self }
326    }
327}
328
329impl<K: fmt::Debug, V> fmt::Debug for ParKeys<'_, K, V> {
330    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
331        let iter = self.entries.iter().map(Bucket::key_ref);
332        f.debug_list().entries(iter).finish()
333    }
334}
335
336impl<'a, K: Sync, V: Sync> ParallelIterator for ParKeys<'a, K, V> {
337    type Item = &'a K;
338
339    parallel_iterator_methods!(Bucket::key_ref);
340}
341
342impl<K: Sync, V: Sync> IndexedParallelIterator for ParKeys<'_, K, V> {
343    indexed_parallel_iterator_methods!(Bucket::key_ref);
344}
345
346/// A parallel iterator over the values of an [`IndexMap`].
347///
348/// This `struct` is created by the [`IndexMap::par_values`] method.
349/// See its documentation for more.
350pub struct ParValues<'a, K, V> {
351    entries: &'a [Bucket<K, V>],
352}
353
354impl<K, V> Clone for ParValues<'_, K, V> {
355    fn clone(&self) -> Self {
356        ParValues { ..*self }
357    }
358}
359
360impl<K, V: fmt::Debug> fmt::Debug for ParValues<'_, K, V> {
361    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
362        let iter = self.entries.iter().map(Bucket::value_ref);
363        f.debug_list().entries(iter).finish()
364    }
365}
366
367impl<'a, K: Sync, V: Sync> ParallelIterator for ParValues<'a, K, V> {
368    type Item = &'a V;
369
370    parallel_iterator_methods!(Bucket::value_ref);
371}
372
373impl<K: Sync, V: Sync> IndexedParallelIterator for ParValues<'_, K, V> {
374    indexed_parallel_iterator_methods!(Bucket::value_ref);
375}
376
377impl<K, V, S> IndexMap<K, V, S>
378where
379    K: Send,
380    V: Send,
381{
382    /// Return a parallel iterator over mutable references to the values of the map
383    ///
384    /// While parallel iterators can process items in any order, their relative order
385    /// in the map is still preserved for operations like `reduce` and `collect`.
386    pub fn par_values_mut(&mut self) -> ParValuesMut<'_, K, V> {
387        ParValuesMut {
388            entries: self.as_entries_mut(),
389        }
390    }
391}
392
393impl<K, V> Slice<K, V>
394where
395    K: Send,
396    V: Send,
397{
398    /// Return a parallel iterator over mutable references to the the values of the map slice.
399    ///
400    /// While parallel iterators can process items in any order, their relative order
401    /// in the slice is still preserved for operations like `reduce` and `collect`.
402    pub fn par_values_mut(&mut self) -> ParValuesMut<'_, K, V> {
403        ParValuesMut {
404            entries: &mut self.entries,
405        }
406    }
407}
408
409impl<K, V, S> IndexMap<K, V, S>
410where
411    K: Send,
412    V: Send,
413{
414    /// Sort the map’s key-value pairs in parallel, by the default ordering of the keys.
415    pub fn par_sort_keys(&mut self)
416    where
417        K: Ord,
418    {
419        self.with_entries(|entries| {
420            entries.par_sort_by(|a, b| K::cmp(&a.key, &b.key));
421        });
422    }
423
424    /// Sort the map’s key-value pairs in place and in parallel, using the comparison
425    /// function `cmp`.
426    ///
427    /// The comparison function receives two key and value pairs to compare (you
428    /// can sort by keys or values or their combination as needed).
429    pub fn par_sort_by<F>(&mut self, cmp: F)
430    where
431        F: Fn(&K, &V, &K, &V) -> Ordering + Sync,
432    {
433        self.with_entries(|entries| {
434            entries.par_sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
435        });
436    }
437
438    /// Sort the key-value pairs of the map in parallel and return a by-value parallel
439    /// iterator of the key-value pairs with the result.
440    pub fn par_sorted_by<F>(self, cmp: F) -> IntoParIter<K, V>
441    where
442        F: Fn(&K, &V, &K, &V) -> Ordering + Sync,
443    {
444        let mut entries = self.into_entries();
445        entries.par_sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
446        IntoParIter { entries }
447    }
448
449    /// Sort the map's key-value pairs in parallel, by the default ordering of the keys.
450    pub fn par_sort_unstable_keys(&mut self)
451    where
452        K: Ord,
453    {
454        self.with_entries(|entries| {
455            entries.par_sort_unstable_by(|a, b| K::cmp(&a.key, &b.key));
456        });
457    }
458
459    /// Sort the map's key-value pairs in place and in parallel, using the comparison
460    /// function `cmp`.
461    ///
462    /// The comparison function receives two key and value pairs to compare (you
463    /// can sort by keys or values or their combination as needed).
464    pub fn par_sort_unstable_by<F>(&mut self, cmp: F)
465    where
466        F: Fn(&K, &V, &K, &V) -> Ordering + Sync,
467    {
468        self.with_entries(|entries| {
469            entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
470        });
471    }
472
473    /// Sort the key-value pairs of the map in parallel and return a by-value parallel
474    /// iterator of the key-value pairs with the result.
475    pub fn par_sorted_unstable_by<F>(self, cmp: F) -> IntoParIter<K, V>
476    where
477        F: Fn(&K, &V, &K, &V) -> Ordering + Sync,
478    {
479        let mut entries = self.into_entries();
480        entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
481        IntoParIter { entries }
482    }
483
484    /// Sort the map’s key-value pairs in place and in parallel, using a sort-key extraction
485    /// function.
486    pub fn par_sort_by_cached_key<T, F>(&mut self, sort_key: F)
487    where
488        T: Ord + Send,
489        F: Fn(&K, &V) -> T + Sync,
490    {
491        self.with_entries(move |entries| {
492            entries.par_sort_by_cached_key(move |a| sort_key(&a.key, &a.value));
493        });
494    }
495}
496
497/// A parallel mutable iterator over the values of an [`IndexMap`].
498///
499/// This `struct` is created by the [`IndexMap::par_values_mut`] method.
500/// See its documentation for more.
501pub struct ParValuesMut<'a, K, V> {
502    entries: &'a mut [Bucket<K, V>],
503}
504
505impl<K, V: fmt::Debug> fmt::Debug for ParValuesMut<'_, K, V> {
506    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
507        let iter = self.entries.iter().map(Bucket::value_ref);
508        f.debug_list().entries(iter).finish()
509    }
510}
511
512impl<'a, K: Send, V: Send> ParallelIterator for ParValuesMut<'a, K, V> {
513    type Item = &'a mut V;
514
515    parallel_iterator_methods!(Bucket::value_mut);
516}
517
518impl<K: Send, V: Send> IndexedParallelIterator for ParValuesMut<'_, K, V> {
519    indexed_parallel_iterator_methods!(Bucket::value_mut);
520}
521
522impl<K, V, S> FromParallelIterator<(K, V)> for IndexMap<K, V, S>
523where
524    K: Eq + Hash + Send,
525    V: Send,
526    S: BuildHasher + Default + Send,
527{
528    fn from_par_iter<I>(iter: I) -> Self
529    where
530        I: IntoParallelIterator<Item = (K, V)>,
531    {
532        let list = collect(iter);
533        let len = list.iter().map(Vec::len).sum();
534        let mut map = Self::with_capacity_and_hasher(len, S::default());
535        for vec in list {
536            map.extend(vec);
537        }
538        map
539    }
540}
541
542impl<K, V, S> ParallelExtend<(K, V)> for IndexMap<K, V, S>
543where
544    K: Eq + Hash + Send,
545    V: Send,
546    S: BuildHasher + Send,
547{
548    fn par_extend<I>(&mut self, iter: I)
549    where
550        I: IntoParallelIterator<Item = (K, V)>,
551    {
552        for vec in collect(iter) {
553            self.extend(vec);
554        }
555    }
556}
557
558impl<'a, K: 'a, V: 'a, S> ParallelExtend<(&'a K, &'a V)> for IndexMap<K, V, S>
559where
560    K: Copy + Eq + Hash + Send + Sync,
561    V: Copy + Send + Sync,
562    S: BuildHasher + Send,
563{
564    fn par_extend<I>(&mut self, iter: I)
565    where
566        I: IntoParallelIterator<Item = (&'a K, &'a V)>,
567    {
568        for vec in collect(iter) {
569            self.extend(vec);
570        }
571    }
572}
573
574#[cfg(test)]
575mod tests {
576    use super::*;
577    use std::string::String;
578
579    #[test]
580    fn insert_order() {
581        let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
582        let mut map = IndexMap::new();
583
584        for &elt in &insert {
585            map.insert(elt, ());
586        }
587
588        assert_eq!(map.par_keys().count(), map.len());
589        assert_eq!(map.par_keys().count(), insert.len());
590        insert.par_iter().zip(map.par_keys()).for_each(|(a, b)| {
591            assert_eq!(a, b);
592        });
593        (0..insert.len())
594            .into_par_iter()
595            .zip(map.par_keys())
596            .for_each(|(i, k)| {
597                assert_eq!(map.get_index(i).unwrap().0, k);
598            });
599    }
600
601    #[test]
602    fn partial_eq_and_eq() {
603        let mut map_a = IndexMap::new();
604        map_a.insert(1, "1");
605        map_a.insert(2, "2");
606        let mut map_b = map_a.clone();
607        assert!(map_a.par_eq(&map_b));
608        map_b.swap_remove(&1);
609        assert!(!map_a.par_eq(&map_b));
610        map_b.insert(3, "3");
611        assert!(!map_a.par_eq(&map_b));
612
613        let map_c: IndexMap<_, String> =
614            map_b.into_par_iter().map(|(k, v)| (k, v.into())).collect();
615        assert!(!map_a.par_eq(&map_c));
616        assert!(!map_c.par_eq(&map_a));
617    }
618
619    #[test]
620    fn extend() {
621        let mut map = IndexMap::new();
622        map.par_extend(vec![(&1, &2), (&3, &4)]);
623        map.par_extend(vec![(5, 6)]);
624        assert_eq!(
625            map.into_par_iter().collect::<Vec<_>>(),
626            vec![(1, 2), (3, 4), (5, 6)]
627        );
628    }
629
630    #[test]
631    fn keys() {
632        let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
633        let map: IndexMap<_, _> = vec.into_par_iter().collect();
634        let keys: Vec<_> = map.par_keys().copied().collect();
635        assert_eq!(keys.len(), 3);
636        assert!(keys.contains(&1));
637        assert!(keys.contains(&2));
638        assert!(keys.contains(&3));
639    }
640
641    #[test]
642    fn values() {
643        let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
644        let map: IndexMap<_, _> = vec.into_par_iter().collect();
645        let values: Vec<_> = map.par_values().copied().collect();
646        assert_eq!(values.len(), 3);
647        assert!(values.contains(&'a'));
648        assert!(values.contains(&'b'));
649        assert!(values.contains(&'c'));
650    }
651
652    #[test]
653    fn values_mut() {
654        let vec = vec![(1, 1), (2, 2), (3, 3)];
655        let mut map: IndexMap<_, _> = vec.into_par_iter().collect();
656        map.par_values_mut().for_each(|value| *value *= 2);
657        let values: Vec<_> = map.par_values().copied().collect();
658        assert_eq!(values.len(), 3);
659        assert!(values.contains(&2));
660        assert!(values.contains(&4));
661        assert!(values.contains(&6));
662    }
663}
indexmap/rayon/map.rs

indexmap/rayon/
map.rs
