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 into_par_iter(self) -> Self::Iter30 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> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result49 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 into_par_iter(self) -> Self::Iter74 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> { clone(&self) -> Self93 fn clone(&self) -> Self { 94 ParIter { ..*self } 95 } 96 } 97 98 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for ParIter<'_, K, V> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result99 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 into_par_iter(self) -> Self::Iter124 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`. par_keys(&self) -> ParKeys<'_, K, V>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`. par_values(&self) -> ParValues<'_, K, V>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. par_eq<V2, S2>(&self, other: &IndexMap<K, V2, S2>) -> bool where V: PartialEq<V2>, V2: Sync, S2: BuildHasher + Sync,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> { clone(&self) -> Self216 fn clone(&self) -> Self { 217 ParKeys { ..*self } 218 } 219 } 220 221 impl<K: fmt::Debug, V> fmt::Debug for ParKeys<'_, K, V> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result222 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> { clone(&self) -> Self250 fn clone(&self) -> Self { 251 ParValues { ..*self } 252 } 253 } 254 255 impl<K, V: fmt::Debug> fmt::Debug for ParValues<'_, K, V> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result256 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 { 278 /// Return a parallel iterator over mutable references to 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`. par_values_mut(&mut self) -> ParValuesMut<'_, K, V>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. par_sort_keys(&mut self) where K: Ord,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). par_sort_by<F>(&mut self, cmp: F) where F: Fn(&K, &V, &K, &V) -> Ordering + Sync,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. par_sorted_by<F>(self, cmp: F) -> IntoParIter<K, V> where F: Fn(&K, &V, &K, &V) -> Ordering + Sync,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 { from_par_iter<I>(iter: I) -> Self where I: IntoParallelIterator<Item = (K, V)>,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 { par_extend<I>(&mut self, iter: I) where I: IntoParallelIterator<Item = (K, V)>,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 { par_extend<I>(&mut self, iter: I) where I: IntoParallelIterator<Item = (&'a K, &'a V)>,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] insert_order()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] partial_eq_and_eq()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] extend()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] keys()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().copied().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] values()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().copied().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] values_mut()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().copied().collect(); 491 assert_eq!(values.len(), 3); 492 assert!(values.contains(&2)); 493 assert!(values.contains(&4)); 494 assert!(values.contains(&6)); 495 } 496 } 497