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

indexmap_amortized/rayon/
map.rs
