indexmap/rayon/
map.rs

1//! Parallel iterator types for `IndexMap` with [rayon](https://docs.rs/rayon/1.0/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//!
6//! Requires crate feature `"rayon"`
7
8use super::collect;
9use rayon::iter::plumbing::{Consumer, ProducerCallback, UnindexedConsumer};
10use rayon::prelude::*;
11
12use crate::vec::Vec;
13use core::cmp::Ordering;
14use core::fmt;
15use core::hash::{BuildHasher, Hash};
16
17use crate::Bucket;
18use crate::Entries;
19use crate::IndexMap;
20
21/// Requires crate feature `"rayon"`.
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
37/// A parallel owning iterator over the entries of a `IndexMap`.
38///
39/// This `struct` is created by the [`into_par_iter`] method on [`IndexMap`]
40/// (provided by rayon's `IntoParallelIterator` trait). See its documentation for more.
41///
42/// [`into_par_iter`]: ../struct.IndexMap.html#method.into_par_iter
43/// [`IndexMap`]: ../struct.IndexMap.html
44pub struct IntoParIter<K, V> {
45    entries: Vec<Bucket<K, V>>,
46}
47
48impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoParIter<K, V> {
49    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
50        let iter = self.entries.iter().map(Bucket::refs);
51        f.debug_list().entries(iter).finish()
52    }
53}
54
55impl<K: Send, V: Send> ParallelIterator for IntoParIter<K, V> {
56    type Item = (K, V);
57
58    parallel_iterator_methods!(Bucket::key_value);
59}
60
61impl<K: Send, V: Send> IndexedParallelIterator for IntoParIter<K, V> {
62    indexed_parallel_iterator_methods!(Bucket::key_value);
63}
64
65/// Requires crate feature `"rayon"`.
66impl<'a, K, V, S> IntoParallelIterator for &'a IndexMap<K, V, S>
67where
68    K: Sync,
69    V: Sync,
70{
71    type Item = (&'a K, &'a V);
72    type Iter = ParIter<'a, K, V>;
73
74    fn into_par_iter(self) -> Self::Iter {
75        ParIter {
76            entries: self.as_entries(),
77        }
78    }
79}
80
81/// A parallel iterator over the entries of a `IndexMap`.
82///
83/// This `struct` is created by the [`par_iter`] method on [`IndexMap`]
84/// (provided by rayon's `IntoParallelRefIterator` trait). See its documentation for more.
85///
86/// [`par_iter`]: ../struct.IndexMap.html#method.par_iter
87/// [`IndexMap`]: ../struct.IndexMap.html
88pub struct ParIter<'a, K, V> {
89    entries: &'a [Bucket<K, V>],
90}
91
92impl<K, V> Clone for ParIter<'_, K, V> {
93    fn clone(&self) -> Self {
94        ParIter { ..*self }
95    }
96}
97
98impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for ParIter<'_, K, V> {
99    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
100        let iter = self.entries.iter().map(Bucket::refs);
101        f.debug_list().entries(iter).finish()
102    }
103}
104
105impl<'a, K: Sync, V: Sync> ParallelIterator for ParIter<'a, K, V> {
106    type Item = (&'a K, &'a V);
107
108    parallel_iterator_methods!(Bucket::refs);
109}
110
111impl<K: Sync, V: Sync> IndexedParallelIterator for ParIter<'_, K, V> {
112    indexed_parallel_iterator_methods!(Bucket::refs);
113}
114
115/// Requires crate feature `"rayon"`.
116impl<'a, K, V, S> IntoParallelIterator for &'a mut IndexMap<K, V, S>
117where
118    K: Sync + Send,
119    V: Send,
120{
121    type Item = (&'a K, &'a mut V);
122    type Iter = ParIterMut<'a, K, V>;
123
124    fn into_par_iter(self) -> Self::Iter {
125        ParIterMut {
126            entries: self.as_entries_mut(),
127        }
128    }
129}
130
131/// A parallel mutable iterator over the entries of a `IndexMap`.
132///
133/// This `struct` is created by the [`par_iter_mut`] method on [`IndexMap`]
134/// (provided by rayon's `IntoParallelRefMutIterator` trait). See its documentation for more.
135///
136/// [`par_iter_mut`]: ../struct.IndexMap.html#method.par_iter_mut
137/// [`IndexMap`]: ../struct.IndexMap.html
138pub struct ParIterMut<'a, K, V> {
139    entries: &'a mut [Bucket<K, V>],
140}
141
142impl<'a, K: Sync + Send, V: Send> ParallelIterator for ParIterMut<'a, K, V> {
143    type Item = (&'a K, &'a mut V);
144
145    parallel_iterator_methods!(Bucket::ref_mut);
146}
147
148impl<K: Sync + Send, V: Send> IndexedParallelIterator for ParIterMut<'_, K, V> {
149    indexed_parallel_iterator_methods!(Bucket::ref_mut);
150}
151
152/// Parallel iterator methods and other parallel methods.
153///
154/// The following methods **require crate feature `"rayon"`**.
155///
156/// See also the `IntoParallelIterator` implementations.
157impl<K, V, S> IndexMap<K, V, S>
158where
159    K: Sync,
160    V: Sync,
161{
162    /// Return a parallel iterator over the keys of the map.
163    ///
164    /// While parallel iterators can process items in any order, their relative order
165    /// in the map is still preserved for operations like `reduce` and `collect`.
166    pub fn par_keys(&self) -> ParKeys<'_, K, V> {
167        ParKeys {
168            entries: self.as_entries(),
169        }
170    }
171
172    /// Return a parallel iterator over the values of the map.
173    ///
174    /// While parallel iterators can process items in any order, their relative order
175    /// in the map is still preserved for operations like `reduce` and `collect`.
176    pub fn par_values(&self) -> ParValues<'_, K, V> {
177        ParValues {
178            entries: self.as_entries(),
179        }
180    }
181}
182
183impl<K, V, S> IndexMap<K, V, S>
184where
185    K: Hash + Eq + Sync,
186    V: Sync,
187    S: BuildHasher,
188{
189    /// Returns `true` if `self` contains all of the same key-value pairs as `other`,
190    /// regardless of each map's indexed order, determined in parallel.
191    pub fn par_eq<V2, S2>(&self, other: &IndexMap<K, V2, S2>) -> bool
192    where
193        V: PartialEq<V2>,
194        V2: Sync,
195        S2: BuildHasher + Sync,
196    {
197        self.len() == other.len()
198            && self
199                .par_iter()
200                .all(move |(key, value)| other.get(key).map_or(false, |v| *value == *v))
201    }
202}
203
204/// A parallel iterator over the keys of a `IndexMap`.
205///
206/// This `struct` is created by the [`par_keys`] method on [`IndexMap`]. See its
207/// documentation for more.
208///
209/// [`par_keys`]: ../struct.IndexMap.html#method.par_keys
210/// [`IndexMap`]: ../struct.IndexMap.html
211pub struct ParKeys<'a, K, V> {
212    entries: &'a [Bucket<K, V>],
213}
214
215impl<K, V> Clone for ParKeys<'_, K, V> {
216    fn clone(&self) -> Self {
217        ParKeys { ..*self }
218    }
219}
220
221impl<K: fmt::Debug, V> fmt::Debug for ParKeys<'_, K, V> {
222    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
223        let iter = self.entries.iter().map(Bucket::key_ref);
224        f.debug_list().entries(iter).finish()
225    }
226}
227
228impl<'a, K: Sync, V: Sync> ParallelIterator for ParKeys<'a, K, V> {
229    type Item = &'a K;
230
231    parallel_iterator_methods!(Bucket::key_ref);
232}
233
234impl<K: Sync, V: Sync> IndexedParallelIterator for ParKeys<'_, K, V> {
235    indexed_parallel_iterator_methods!(Bucket::key_ref);
236}
237
238/// A parallel iterator over the values of a `IndexMap`.
239///
240/// This `struct` is created by the [`par_values`] method on [`IndexMap`]. See its
241/// documentation for more.
242///
243/// [`par_values`]: ../struct.IndexMap.html#method.par_values
244/// [`IndexMap`]: ../struct.IndexMap.html
245pub struct ParValues<'a, K, V> {
246    entries: &'a [Bucket<K, V>],
247}
248
249impl<K, V> Clone for ParValues<'_, K, V> {
250    fn clone(&self) -> Self {
251        ParValues { ..*self }
252    }
253}
254
255impl<K, V: fmt::Debug> fmt::Debug for ParValues<'_, K, V> {
256    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
257        let iter = self.entries.iter().map(Bucket::value_ref);
258        f.debug_list().entries(iter).finish()
259    }
260}
261
262impl<'a, K: Sync, V: Sync> ParallelIterator for ParValues<'a, K, V> {
263    type Item = &'a V;
264
265    parallel_iterator_methods!(Bucket::value_ref);
266}
267
268impl<K: Sync, V: Sync> IndexedParallelIterator for ParValues<'_, K, V> {
269    indexed_parallel_iterator_methods!(Bucket::value_ref);
270}
271
272/// Requires crate feature `"rayon"`.
273impl<K, V, S> IndexMap<K, V, S>
274where
275    K: Send,
276    V: Send,
277{
278    /// Return a parallel iterator over mutable references to the the values of the map
279    ///
280    /// While parallel iterators can process items in any order, their relative order
281    /// in the map is still preserved for operations like `reduce` and `collect`.
282    pub fn par_values_mut(&mut self) -> ParValuesMut<'_, K, V> {
283        ParValuesMut {
284            entries: self.as_entries_mut(),
285        }
286    }
287}
288
289impl<K, V, S> IndexMap<K, V, S>
290where
291    K: Hash + Eq + Send,
292    V: Send,
293    S: BuildHasher,
294{
295    /// Sort the map’s key-value pairs in parallel, by the default ordering of the keys.
296    pub fn par_sort_keys(&mut self)
297    where
298        K: Ord,
299    {
300        self.with_entries(|entries| {
301            entries.par_sort_by(|a, b| K::cmp(&a.key, &b.key));
302        });
303    }
304
305    /// Sort the map’s key-value pairs in place and in parallel, using the comparison
306    /// function `compare`.
307    ///
308    /// The comparison function receives two key and value pairs to compare (you
309    /// can sort by keys or values or their combination as needed).
310    pub fn par_sort_by<F>(&mut self, cmp: F)
311    where
312        F: Fn(&K, &V, &K, &V) -> Ordering + Sync,
313    {
314        self.with_entries(|entries| {
315            entries.par_sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
316        });
317    }
318
319    /// Sort the key-value pairs of the map in parallel and return a by value parallel
320    /// iterator of the key-value pairs with the result.
321    pub fn par_sorted_by<F>(self, cmp: F) -> IntoParIter<K, V>
322    where
323        F: Fn(&K, &V, &K, &V) -> Ordering + Sync,
324    {
325        let mut entries = self.into_entries();
326        entries.par_sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
327        IntoParIter { entries }
328    }
329}
330
331/// A parallel mutable iterator over the values of a `IndexMap`.
332///
333/// This `struct` is created by the [`par_values_mut`] method on [`IndexMap`]. See its
334/// documentation for more.
335///
336/// [`par_values_mut`]: ../struct.IndexMap.html#method.par_values_mut
337/// [`IndexMap`]: ../struct.IndexMap.html
338pub struct ParValuesMut<'a, K, V> {
339    entries: &'a mut [Bucket<K, V>],
340}
341
342impl<'a, K: Send, V: Send> ParallelIterator for ParValuesMut<'a, K, V> {
343    type Item = &'a mut V;
344
345    parallel_iterator_methods!(Bucket::value_mut);
346}
347
348impl<K: Send, V: Send> IndexedParallelIterator for ParValuesMut<'_, K, V> {
349    indexed_parallel_iterator_methods!(Bucket::value_mut);
350}
351
352/// Requires crate feature `"rayon"`.
353impl<K, V, S> FromParallelIterator<(K, V)> for IndexMap<K, V, S>
354where
355    K: Eq + Hash + Send,
356    V: Send,
357    S: BuildHasher + Default + Send,
358{
359    fn from_par_iter<I>(iter: I) -> Self
360    where
361        I: IntoParallelIterator<Item = (K, V)>,
362    {
363        let list = collect(iter);
364        let len = list.iter().map(Vec::len).sum();
365        let mut map = Self::with_capacity_and_hasher(len, S::default());
366        for vec in list {
367            map.extend(vec);
368        }
369        map
370    }
371}
372
373/// Requires crate feature `"rayon"`.
374impl<K, V, S> ParallelExtend<(K, V)> for IndexMap<K, V, S>
375where
376    K: Eq + Hash + Send,
377    V: Send,
378    S: BuildHasher + Send,
379{
380    fn par_extend<I>(&mut self, iter: I)
381    where
382        I: IntoParallelIterator<Item = (K, V)>,
383    {
384        for vec in collect(iter) {
385            self.extend(vec);
386        }
387    }
388}
389
390/// Requires crate feature `"rayon"`.
391impl<'a, K: 'a, V: 'a, S> ParallelExtend<(&'a K, &'a V)> for IndexMap<K, V, S>
392where
393    K: Copy + Eq + Hash + Send + Sync,
394    V: Copy + Send + Sync,
395    S: BuildHasher + Send,
396{
397    fn par_extend<I>(&mut self, iter: I)
398    where
399        I: IntoParallelIterator<Item = (&'a K, &'a V)>,
400    {
401        for vec in collect(iter) {
402            self.extend(vec);
403        }
404    }
405}
406
407#[cfg(test)]
408mod tests {
409    use super::*;
410    use std::string::String;
411
412    #[test]
413    fn insert_order() {
414        let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
415        let mut map = IndexMap::new();
416
417        for &elt in &insert {
418            map.insert(elt, ());
419        }
420
421        assert_eq!(map.par_keys().count(), map.len());
422        assert_eq!(map.par_keys().count(), insert.len());
423        insert.par_iter().zip(map.par_keys()).for_each(|(a, b)| {
424            assert_eq!(a, b);
425        });
426        (0..insert.len())
427            .into_par_iter()
428            .zip(map.par_keys())
429            .for_each(|(i, k)| {
430                assert_eq!(map.get_index(i).unwrap().0, k);
431            });
432    }
433
434    #[test]
435    fn partial_eq_and_eq() {
436        let mut map_a = IndexMap::new();
437        map_a.insert(1, "1");
438        map_a.insert(2, "2");
439        let mut map_b = map_a.clone();
440        assert!(map_a.par_eq(&map_b));
441        map_b.swap_remove(&1);
442        assert!(!map_a.par_eq(&map_b));
443        map_b.insert(3, "3");
444        assert!(!map_a.par_eq(&map_b));
445
446        let map_c: IndexMap<_, String> =
447            map_b.into_par_iter().map(|(k, v)| (k, v.into())).collect();
448        assert!(!map_a.par_eq(&map_c));
449        assert!(!map_c.par_eq(&map_a));
450    }
451
452    #[test]
453    fn extend() {
454        let mut map = IndexMap::new();
455        map.par_extend(vec![(&1, &2), (&3, &4)]);
456        map.par_extend(vec![(5, 6)]);
457        assert_eq!(
458            map.into_par_iter().collect::<Vec<_>>(),
459            vec![(1, 2), (3, 4), (5, 6)]
460        );
461    }
462
463    #[test]
464    fn keys() {
465        let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
466        let map: IndexMap<_, _> = vec.into_par_iter().collect();
467        let keys: Vec<_> = map.par_keys().cloned().collect();
468        assert_eq!(keys.len(), 3);
469        assert!(keys.contains(&1));
470        assert!(keys.contains(&2));
471        assert!(keys.contains(&3));
472    }
473
474    #[test]
475    fn values() {
476        let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
477        let map: IndexMap<_, _> = vec.into_par_iter().collect();
478        let values: Vec<_> = map.par_values().cloned().collect();
479        assert_eq!(values.len(), 3);
480        assert!(values.contains(&'a'));
481        assert!(values.contains(&'b'));
482        assert!(values.contains(&'c'));
483    }
484
485    #[test]
486    fn values_mut() {
487        let vec = vec![(1, 1), (2, 2), (3, 3)];
488        let mut map: IndexMap<_, _> = vec.into_par_iter().collect();
489        map.par_values_mut().for_each(|value| *value *= 2);
490        let values: Vec<_> = map.par_values().cloned().collect();
491        assert_eq!(values.len(), 3);
492        assert!(values.contains(&2));
493        assert!(values.contains(&4));
494        assert!(values.contains(&6));
495    }
496}
indexmap/rayon/map.rs

indexmap/rayon/
map.rs
