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
  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 {
 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`.
 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();
 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]
 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]
 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 }