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

indexmap/rayon/
map.rs
