]>
Commit | Line | Data |
---|---|---|
3dfed10e XL |
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 | ||
8 | use super::collect; | |
9 | use rayon::iter::plumbing::{Consumer, ProducerCallback, UnindexedConsumer}; | |
10 | use rayon::prelude::*; | |
11 | ||
12 | use crate::vec::Vec; | |
13 | use core::cmp::Ordering; | |
14 | use core::fmt; | |
15 | use core::hash::{BuildHasher, Hash}; | |
16 | ||
17 | use crate::Bucket; | |
18 | use crate::Entries; | |
19 | use crate::IndexMap; | |
20 | ||
21 | /// Requires crate feature `"rayon"`. | |
22 | impl<K, V, S> IntoParallelIterator for IndexMap<K, V, S> | |
23 | where | |
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 | |
44 | pub struct IntoParIter<K, V> { | |
45 | entries: Vec<Bucket<K, V>>, | |
46 | } | |
47 | ||
48 | impl<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 | ||
55 | impl<K: Send, V: Send> ParallelIterator for IntoParIter<K, V> { | |
56 | type Item = (K, V); | |
57 | ||
58 | parallel_iterator_methods!(Bucket::key_value); | |
59 | } | |
60 | ||
61 | impl<K: Send, V: Send> IndexedParallelIterator for IntoParIter<K, V> { | |
62 | indexed_parallel_iterator_methods!(Bucket::key_value); | |
63 | } | |
64 | ||
65 | /// Requires crate feature `"rayon"`. | |
66 | impl<'a, K, V, S> IntoParallelIterator for &'a IndexMap<K, V, S> | |
67 | where | |
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 | |
88 | pub struct ParIter<'a, K, V> { | |
89 | entries: &'a [Bucket<K, V>], | |
90 | } | |
91 | ||
92 | impl<K, V> Clone for ParIter<'_, K, V> { | |
93 | fn clone(&self) -> Self { | |
94 | ParIter { ..*self } | |
95 | } | |
96 | } | |
97 | ||
98 | impl<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 | ||
105 | impl<'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 | ||
111 | impl<K: Sync, V: Sync> IndexedParallelIterator for ParIter<'_, K, V> { | |
112 | indexed_parallel_iterator_methods!(Bucket::refs); | |
113 | } | |
114 | ||
115 | /// Requires crate feature `"rayon"`. | |
116 | impl<'a, K, V, S> IntoParallelIterator for &'a mut IndexMap<K, V, S> | |
117 | where | |
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 | |
138 | pub struct ParIterMut<'a, K, V> { | |
139 | entries: &'a mut [Bucket<K, V>], | |
140 | } | |
141 | ||
142 | impl<'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 | ||
148 | impl<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. | |
157 | impl<K, V, S> IndexMap<K, V, S> | |
158 | where | |
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 | ||
183 | impl<K, V, S> IndexMap<K, V, S> | |
184 | where | |
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 | |
211 | pub struct ParKeys<'a, K, V> { | |
212 | entries: &'a [Bucket<K, V>], | |
213 | } | |
214 | ||
215 | impl<K, V> Clone for ParKeys<'_, K, V> { | |
216 | fn clone(&self) -> Self { | |
217 | ParKeys { ..*self } | |
218 | } | |
219 | } | |
220 | ||
221 | impl<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 | ||
228 | impl<'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 | ||
234 | impl<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 | |
245 | pub struct ParValues<'a, K, V> { | |
246 | entries: &'a [Bucket<K, V>], | |
247 | } | |
248 | ||
249 | impl<K, V> Clone for ParValues<'_, K, V> { | |
250 | fn clone(&self) -> Self { | |
251 | ParValues { ..*self } | |
252 | } | |
253 | } | |
254 | ||
255 | impl<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 | ||
262 | impl<'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 | ||
268 | impl<K: Sync, V: Sync> IndexedParallelIterator for ParValues<'_, K, V> { | |
269 | indexed_parallel_iterator_methods!(Bucket::value_ref); | |
270 | } | |
271 | ||
272 | /// Requires crate feature `"rayon"`. | |
273 | impl<K, V, S> IndexMap<K, V, S> | |
274 | where | |
275 | K: Send, | |
276 | V: Send, | |
277 | { | |
136023e0 | 278 | /// Return a parallel iterator over mutable references to the values of the map |
3dfed10e XL |
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 | ||
289 | impl<K, V, S> IndexMap<K, V, S> | |
290 | where | |
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 | |
338 | pub struct ParValuesMut<'a, K, V> { | |
339 | entries: &'a mut [Bucket<K, V>], | |
340 | } | |
341 | ||
342 | impl<'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 | ||
348 | impl<K: Send, V: Send> IndexedParallelIterator for ParValuesMut<'_, K, V> { | |
349 | indexed_parallel_iterator_methods!(Bucket::value_mut); | |
350 | } | |
351 | ||
352 | /// Requires crate feature `"rayon"`. | |
353 | impl<K, V, S> FromParallelIterator<(K, V)> for IndexMap<K, V, S> | |
354 | where | |
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"`. | |
374 | impl<K, V, S> ParallelExtend<(K, V)> for IndexMap<K, V, S> | |
375 | where | |
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"`. | |
391 | impl<'a, K: 'a, V: 'a, S> ParallelExtend<(&'a K, &'a V)> for IndexMap<K, V, S> | |
392 | where | |
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)] | |
408 | mod 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(); | |
136023e0 | 467 | let keys: Vec<_> = map.par_keys().copied().collect(); |
3dfed10e XL |
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(); | |
136023e0 | 478 | let values: Vec<_> = map.par_values().copied().collect(); |
3dfed10e XL |
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); | |
136023e0 | 490 | let values: Vec<_> = map.par_values().copied().collect(); |
3dfed10e XL |
491 | assert_eq!(values.len(), 3); |
492 | assert!(values.contains(&2)); | |
493 | assert!(values.contains(&4)); | |
494 | assert!(values.contains(&6)); | |
495 | } | |
496 | } |