vendor/indexmap/src/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
   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 use core::ops::RangeBounds;
  17
  18 use crate::Bucket;
  19 use crate::Entries;
  20 use crate::IndexMap;
  21
  22 /// Requires crate feature `"rayon"`.
  23 impl<K, V, S> IntoParallelIterator for IndexMap<K, V, S>
  24 where
  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
  45 pub struct IntoParIter<K, V> {
  46     entries: Vec<Bucket<K, V>>,
  47 }
  48
  49 impl<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
  56 impl<K: Send, V: Send> ParallelIterator for IntoParIter<K, V> {
  57     type Item = (K, V);
  58
  59     parallel_iterator_methods!(Bucket::key_value);
  60 }
  61
  62 impl<K: Send, V: Send> IndexedParallelIterator for IntoParIter<K, V> {
  63     indexed_parallel_iterator_methods!(Bucket::key_value);
  64 }
  65
  66 /// Requires crate feature `"rayon"`.
  67 impl<'a, K, V, S> IntoParallelIterator for &'a IndexMap<K, V, S>
  68 where
  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
  89 pub struct ParIter<'a, K, V> {
  90     entries: &'a [Bucket<K, V>],
  91 }
  92
  93 impl<K, V> Clone for ParIter<'_, K, V> {
  94     fn clone(&self) -> Self {
  95         ParIter { ..*self }
  96     }
  97 }
  98
  99 impl<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
 106 impl<'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
 112 impl<K: Sync, V: Sync> IndexedParallelIterator for ParIter<'_, K, V> {
 113     indexed_parallel_iterator_methods!(Bucket::refs);
 114 }
 115
 116 /// Requires crate feature `"rayon"`.
 117 impl<'a, K, V, S> IntoParallelIterator for &'a mut IndexMap<K, V, S>
 118 where
 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
 139 pub struct ParIterMut<'a, K, V> {
 140     entries: &'a mut [Bucket<K, V>],
 141 }
 142
 143 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for ParIterMut<'_, K, V> {
 144     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 145         let iter = self.entries.iter().map(Bucket::refs);
 146         f.debug_list().entries(iter).finish()
 147     }
 148 }
 149
 150 impl<'a, K: Sync + Send, V: Send> ParallelIterator for ParIterMut<'a, K, V> {
 151     type Item = (&'a K, &'a mut V);
 152
 153     parallel_iterator_methods!(Bucket::ref_mut);
 154 }
 155
 156 impl<K: Sync + Send, V: Send> IndexedParallelIterator for ParIterMut<'_, K, V> {
 157     indexed_parallel_iterator_methods!(Bucket::ref_mut);
 158 }
 159
 160 /// Requires crate feature `"rayon"`.
 161 impl<'a, K, V, S> ParallelDrainRange<usize> for &'a mut IndexMap<K, V, S>
 162 where
 163     K: Send,
 164     V: Send,
 165 {
 166     type Item = (K, V);
 167     type Iter = ParDrain<'a, K, V>;
 168
 169     fn par_drain<R: RangeBounds<usize>>(self, range: R) -> Self::Iter {
 170         ParDrain {
 171             entries: self.core.par_drain(range),
 172         }
 173     }
 174 }
 175
 176 /// A parallel draining iterator over the entries of a `IndexMap`.
 177 ///
 178 /// This `struct` is created by the [`par_drain`] method on [`IndexMap`]
 179 /// (provided by rayon's `ParallelDrainRange` trait). See its documentation for more.
 180 ///
 181 /// [`par_drain`]: ../struct.IndexMap.html#method.par_drain
 182 /// [`IndexMap`]: ../struct.IndexMap.html
 183 pub struct ParDrain<'a, K: Send, V: Send> {
 184     entries: rayon::vec::Drain<'a, Bucket<K, V>>,
 185 }
 186
 187 impl<K: Send, V: Send> ParallelIterator for ParDrain<'_, K, V> {
 188     type Item = (K, V);
 189
 190     parallel_iterator_methods!(Bucket::key_value);
 191 }
 192
 193 impl<K: Send, V: Send> IndexedParallelIterator for ParDrain<'_, K, V> {
 194     indexed_parallel_iterator_methods!(Bucket::key_value);
 195 }
 196
 197 /// Parallel iterator methods and other parallel methods.
 198 ///
 199 /// The following methods **require crate feature `"rayon"`**.
 200 ///
 201 /// See also the `IntoParallelIterator` implementations.
 202 impl<K, V, S> IndexMap<K, V, S>
 203 where
 204     K: Sync,
 205     V: Sync,
 206 {
 207     /// Return a parallel iterator over the keys of the map.
 208     ///
 209     /// While parallel iterators can process items in any order, their relative order
 210     /// in the map is still preserved for operations like `reduce` and `collect`.
 211     pub fn par_keys(&self) -> ParKeys<'_, K, V> {
 212         ParKeys {
 213             entries: self.as_entries(),
 214         }
 215     }
 216
 217     /// Return a parallel iterator over the values of the map.
 218     ///
 219     /// While parallel iterators can process items in any order, their relative order
 220     /// in the map is still preserved for operations like `reduce` and `collect`.
 221     pub fn par_values(&self) -> ParValues<'_, K, V> {
 222         ParValues {
 223             entries: self.as_entries(),
 224         }
 225     }
 226 }
 227
 228 impl<K, V, S> IndexMap<K, V, S>
 229 where
 230     K: Hash + Eq + Sync,
 231     V: Sync,
 232     S: BuildHasher,
 233 {
 234     /// Returns `true` if `self` contains all of the same key-value pairs as `other`,
 235     /// regardless of each map's indexed order, determined in parallel.
 236     pub fn par_eq<V2, S2>(&self, other: &IndexMap<K, V2, S2>) -> bool
 237     where
 238         V: PartialEq<V2>,
 239         V2: Sync,
 240         S2: BuildHasher + Sync,
 241     {
 242         self.len() == other.len()
 243             && self
 244                 .par_iter()
 245                 .all(move |(key, value)| other.get(key).map_or(false, |v| *value == *v))
 246     }
 247 }
 248
 249 /// A parallel iterator over the keys of a `IndexMap`.
 250 ///
 251 /// This `struct` is created by the [`par_keys`] method on [`IndexMap`]. See its
 252 /// documentation for more.
 253 ///
 254 /// [`par_keys`]: ../struct.IndexMap.html#method.par_keys
 255 /// [`IndexMap`]: ../struct.IndexMap.html
 256 pub struct ParKeys<'a, K, V> {
 257     entries: &'a [Bucket<K, V>],
 258 }
 259
 260 impl<K, V> Clone for ParKeys<'_, K, V> {
 261     fn clone(&self) -> Self {
 262         ParKeys { ..*self }
 263     }
 264 }
 265
 266 impl<K: fmt::Debug, V> fmt::Debug for ParKeys<'_, K, V> {
 267     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 268         let iter = self.entries.iter().map(Bucket::key_ref);
 269         f.debug_list().entries(iter).finish()
 270     }
 271 }
 272
 273 impl<'a, K: Sync, V: Sync> ParallelIterator for ParKeys<'a, K, V> {
 274     type Item = &'a K;
 275
 276     parallel_iterator_methods!(Bucket::key_ref);
 277 }
 278
 279 impl<K: Sync, V: Sync> IndexedParallelIterator for ParKeys<'_, K, V> {
 280     indexed_parallel_iterator_methods!(Bucket::key_ref);
 281 }
 282
 283 /// A parallel iterator over the values of a `IndexMap`.
 284 ///
 285 /// This `struct` is created by the [`par_values`] method on [`IndexMap`]. See its
 286 /// documentation for more.
 287 ///
 288 /// [`par_values`]: ../struct.IndexMap.html#method.par_values
 289 /// [`IndexMap`]: ../struct.IndexMap.html
 290 pub struct ParValues<'a, K, V> {
 291     entries: &'a [Bucket<K, V>],
 292 }
 293
 294 impl<K, V> Clone for ParValues<'_, K, V> {
 295     fn clone(&self) -> Self {
 296         ParValues { ..*self }
 297     }
 298 }
 299
 300 impl<K, V: fmt::Debug> fmt::Debug for ParValues<'_, K, V> {
 301     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 302         let iter = self.entries.iter().map(Bucket::value_ref);
 303         f.debug_list().entries(iter).finish()
 304     }
 305 }
 306
 307 impl<'a, K: Sync, V: Sync> ParallelIterator for ParValues<'a, K, V> {
 308     type Item = &'a V;
 309
 310     parallel_iterator_methods!(Bucket::value_ref);
 311 }
 312
 313 impl<K: Sync, V: Sync> IndexedParallelIterator for ParValues<'_, K, V> {
 314     indexed_parallel_iterator_methods!(Bucket::value_ref);
 315 }
 316
 317 /// Requires crate feature `"rayon"`.
 318 impl<K, V, S> IndexMap<K, V, S>
 319 where
 320     K: Send,
 321     V: Send,
 322 {
 323     /// Return a parallel iterator over mutable references to the values of the map
 324     ///
 325     /// While parallel iterators can process items in any order, their relative order
 326     /// in the map is still preserved for operations like `reduce` and `collect`.
 327     pub fn par_values_mut(&mut self) -> ParValuesMut<'_, K, V> {
 328         ParValuesMut {
 329             entries: self.as_entries_mut(),
 330         }
 331     }
 332 }
 333
 334 impl<K, V, S> IndexMap<K, V, S>
 335 where
 336     K: Hash + Eq + Send,
 337     V: Send,
 338     S: BuildHasher,
 339 {
 340     /// Sort the map’s key-value pairs in parallel, by the default ordering of the keys.
 341     pub fn par_sort_keys(&mut self)
 342     where
 343         K: Ord,
 344     {
 345         self.with_entries(|entries| {
 346             entries.par_sort_by(|a, b| K::cmp(&a.key, &b.key));
 347         });
 348     }
 349
 350     /// Sort the map’s key-value pairs in place and in parallel, using the comparison
 351     /// function `cmp`.
 352     ///
 353     /// The comparison function receives two key and value pairs to compare (you
 354     /// can sort by keys or values or their combination as needed).
 355     pub fn par_sort_by<F>(&mut self, cmp: F)
 356     where
 357         F: Fn(&K, &V, &K, &V) -> Ordering + Sync,
 358     {
 359         self.with_entries(|entries| {
 360             entries.par_sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
 361         });
 362     }
 363
 364     /// Sort the key-value pairs of the map in parallel and return a by-value parallel
 365     /// iterator of the key-value pairs with the result.
 366     pub fn par_sorted_by<F>(self, cmp: F) -> IntoParIter<K, V>
 367     where
 368         F: Fn(&K, &V, &K, &V) -> Ordering + Sync,
 369     {
 370         let mut entries = self.into_entries();
 371         entries.par_sort_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
 372         IntoParIter { entries }
 373     }
 374
 375     /// Sort the map's key-value pairs in parallel, by the default ordering of the keys.
 376     pub fn par_sort_unstable_keys(&mut self)
 377     where
 378         K: Ord,
 379     {
 380         self.with_entries(|entries| {
 381             entries.par_sort_unstable_by(|a, b| K::cmp(&a.key, &b.key));
 382         });
 383     }
 384
 385     /// Sort the map's key-value pairs in place and in parallel, using the comparison
 386     /// function `cmp`.
 387     ///
 388     /// The comparison function receives two key and value pairs to compare (you
 389     /// can sort by keys or values or their combination as needed).
 390     pub fn par_sort_unstable_by<F>(&mut self, cmp: F)
 391     where
 392         F: Fn(&K, &V, &K, &V) -> Ordering + Sync,
 393     {
 394         self.with_entries(|entries| {
 395             entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
 396         });
 397     }
 398
 399     /// Sort the key-value pairs of the map in parallel and return a by-value parallel
 400     /// iterator of the key-value pairs with the result.
 401     pub fn par_sorted_unstable_by<F>(self, cmp: F) -> IntoParIter<K, V>
 402     where
 403         F: Fn(&K, &V, &K, &V) -> Ordering + Sync,
 404     {
 405         let mut entries = self.into_entries();
 406         entries.par_sort_unstable_by(move |a, b| cmp(&a.key, &a.value, &b.key, &b.value));
 407         IntoParIter { entries }
 408     }
 409 }
 410
 411 /// A parallel mutable iterator over the values of a `IndexMap`.
 412 ///
 413 /// This `struct` is created by the [`par_values_mut`] method on [`IndexMap`]. See its
 414 /// documentation for more.
 415 ///
 416 /// [`par_values_mut`]: ../struct.IndexMap.html#method.par_values_mut
 417 /// [`IndexMap`]: ../struct.IndexMap.html
 418 pub struct ParValuesMut<'a, K, V> {
 419     entries: &'a mut [Bucket<K, V>],
 420 }
 421
 422 impl<K, V: fmt::Debug> fmt::Debug for ParValuesMut<'_, K, V> {
 423     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 424         let iter = self.entries.iter().map(Bucket::value_ref);
 425         f.debug_list().entries(iter).finish()
 426     }
 427 }
 428
 429 impl<'a, K: Send, V: Send> ParallelIterator for ParValuesMut<'a, K, V> {
 430     type Item = &'a mut V;
 431
 432     parallel_iterator_methods!(Bucket::value_mut);
 433 }
 434
 435 impl<K: Send, V: Send> IndexedParallelIterator for ParValuesMut<'_, K, V> {
 436     indexed_parallel_iterator_methods!(Bucket::value_mut);
 437 }
 438
 439 /// Requires crate feature `"rayon"`.
 440 impl<K, V, S> FromParallelIterator<(K, V)> for IndexMap<K, V, S>
 441 where
 442     K: Eq + Hash + Send,
 443     V: Send,
 444     S: BuildHasher + Default + Send,
 445 {
 446     fn from_par_iter<I>(iter: I) -> Self
 447     where
 448         I: IntoParallelIterator<Item = (K, V)>,
 449     {
 450         let list = collect(iter);
 451         let len = list.iter().map(Vec::len).sum();
 452         let mut map = Self::with_capacity_and_hasher(len, S::default());
 453         for vec in list {
 454             map.extend(vec);
 455         }
 456         map
 457     }
 458 }
 459
 460 /// Requires crate feature `"rayon"`.
 461 impl<K, V, S> ParallelExtend<(K, V)> for IndexMap<K, V, S>
 462 where
 463     K: Eq + Hash + Send,
 464     V: Send,
 465     S: BuildHasher + Send,
 466 {
 467     fn par_extend<I>(&mut self, iter: I)
 468     where
 469         I: IntoParallelIterator<Item = (K, V)>,
 470     {
 471         for vec in collect(iter) {
 472             self.extend(vec);
 473         }
 474     }
 475 }
 476
 477 /// Requires crate feature `"rayon"`.
 478 impl<'a, K: 'a, V: 'a, S> ParallelExtend<(&'a K, &'a V)> for IndexMap<K, V, S>
 479 where
 480     K: Copy + Eq + Hash + Send + Sync,
 481     V: Copy + Send + Sync,
 482     S: BuildHasher + Send,
 483 {
 484     fn par_extend<I>(&mut self, iter: I)
 485     where
 486         I: IntoParallelIterator<Item = (&'a K, &'a V)>,
 487     {
 488         for vec in collect(iter) {
 489             self.extend(vec);
 490         }
 491     }
 492 }
 493
 494 #[cfg(test)]
 495 mod tests {
 496     use super::*;
 497     use std::string::String;
 498
 499     #[test]
 500     fn insert_order() {
 501         let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
 502         let mut map = IndexMap::new();
 503
 504         for &elt in &insert {
 505             map.insert(elt, ());
 506         }
 507
 508         assert_eq!(map.par_keys().count(), map.len());
 509         assert_eq!(map.par_keys().count(), insert.len());
 510         insert.par_iter().zip(map.par_keys()).for_each(|(a, b)| {
 511             assert_eq!(a, b);
 512         });
 513         (0..insert.len())
 514             .into_par_iter()
 515             .zip(map.par_keys())
 516             .for_each(|(i, k)| {
 517                 assert_eq!(map.get_index(i).unwrap().0, k);
 518             });
 519     }
 520
 521     #[test]
 522     fn partial_eq_and_eq() {
 523         let mut map_a = IndexMap::new();
 524         map_a.insert(1, "1");
 525         map_a.insert(2, "2");
 526         let mut map_b = map_a.clone();
 527         assert!(map_a.par_eq(&map_b));
 528         map_b.swap_remove(&1);
 529         assert!(!map_a.par_eq(&map_b));
 530         map_b.insert(3, "3");
 531         assert!(!map_a.par_eq(&map_b));
 532
 533         let map_c: IndexMap<_, String> =
 534             map_b.into_par_iter().map(|(k, v)| (k, v.into())).collect();
 535         assert!(!map_a.par_eq(&map_c));
 536         assert!(!map_c.par_eq(&map_a));
 537     }
 538
 539     #[test]
 540     fn extend() {
 541         let mut map = IndexMap::new();
 542         map.par_extend(vec![(&1, &2), (&3, &4)]);
 543         map.par_extend(vec![(5, 6)]);
 544         assert_eq!(
 545             map.into_par_iter().collect::<Vec<_>>(),
 546             vec![(1, 2), (3, 4), (5, 6)]
 547         );
 548     }
 549
 550     #[test]
 551     fn keys() {
 552         let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
 553         let map: IndexMap<_, _> = vec.into_par_iter().collect();
 554         let keys: Vec<_> = map.par_keys().copied().collect();
 555         assert_eq!(keys.len(), 3);
 556         assert!(keys.contains(&1));
 557         assert!(keys.contains(&2));
 558         assert!(keys.contains(&3));
 559     }
 560
 561     #[test]
 562     fn values() {
 563         let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
 564         let map: IndexMap<_, _> = vec.into_par_iter().collect();
 565         let values: Vec<_> = map.par_values().copied().collect();
 566         assert_eq!(values.len(), 3);
 567         assert!(values.contains(&'a'));
 568         assert!(values.contains(&'b'));
 569         assert!(values.contains(&'c'));
 570     }
 571
 572     #[test]
 573     fn values_mut() {
 574         let vec = vec![(1, 1), (2, 2), (3, 3)];
 575         let mut map: IndexMap<_, _> = vec.into_par_iter().collect();
 576         map.par_values_mut().for_each(|value| *value *= 2);
 577         let values: Vec<_> = map.par_values().copied().collect();
 578         assert_eq!(values.len(), 3);
 579         assert!(values.contains(&2));
 580         assert!(values.contains(&4));
 581         assert!(values.contains(&6));
 582     }
 583 }