1 //! Parallel iterator types for [standard collections][std::collections] 2 //! 3 //! You will rarely need to interact with this module directly unless you need 4 //! to name one of the iterator types. 5 //! 6 //! [std::collections]: https://doc.rust-lang.org/stable/std/collections/ 7 8 /// Convert an iterable collection into a parallel iterator by first 9 /// collecting into a temporary `Vec`, then iterating that. 10 macro_rules! into_par_vec { 11 ($t:ty => $iter:ident<$($i:tt),*>, impl $($args:tt)*) => { 12 impl $($args)* IntoParallelIterator for $t { 13 type Item = <$t as IntoIterator>::Item; 14 type Iter = $iter<$($i),*>; 15 16 fn into_par_iter(self) -> Self::Iter { 17 use std::iter::FromIterator; 18 $iter { inner: Vec::from_iter(self).into_par_iter() } 19 } 20 } 21 }; 22 } 23 24 pub mod binary_heap; 25 pub mod btree_map; 26 pub mod btree_set; 27 pub mod hash_map; 28 pub mod hash_set; 29 pub mod linked_list; 30 pub mod vec_deque; 31 32 use self::drain_guard::DrainGuard; 33 34 mod drain_guard { 35 use crate::iter::ParallelDrainRange; 36 use std::mem; 37 use std::ops::RangeBounds; 38 39 /// A proxy for draining a collection by converting to a `Vec` and back. 40 /// 41 /// This is used for draining `BinaryHeap` and `VecDeque`, which both have 42 /// zero-allocation conversions to/from `Vec`, though not zero-cost: 43 /// - `BinaryHeap` will heapify from `Vec`, but at least that will be empty. 44 /// - `VecDeque` has to shift items to offset 0 when converting to `Vec`. 45 #[allow(missing_debug_implementations)] 46 pub(super) struct DrainGuard<'a, T, C: From<Vec<T>>> { 47 collection: &'a mut C, 48 vec: Vec<T>, 49 } 50 51 impl<'a, T, C> DrainGuard<'a, T, C> 52 where 53 C: Default + From<Vec<T>>, 54 Vec<T>: From<C>, 55 { new(collection: &'a mut C) -> Self56 pub(super) fn new(collection: &'a mut C) -> Self { 57 Self { 58 // Temporarily steal the inner `Vec` so we can drain in place. 59 vec: Vec::from(mem::take(collection)), 60 collection, 61 } 62 } 63 } 64 65 impl<'a, T, C: From<Vec<T>>> Drop for DrainGuard<'a, T, C> { drop(&mut self)66 fn drop(&mut self) { 67 // Restore the collection from the `Vec` with its original capacity. 68 *self.collection = C::from(mem::take(&mut self.vec)); 69 } 70 } 71 72 impl<'a, T, C> ParallelDrainRange<usize> for &'a mut DrainGuard<'_, T, C> 73 where 74 T: Send, 75 C: From<Vec<T>>, 76 { 77 type Iter = crate::vec::Drain<'a, T>; 78 type Item = T; 79 par_drain<R: RangeBounds<usize>>(self, range: R) -> Self::Iter80 fn par_drain<R: RangeBounds<usize>>(self, range: R) -> Self::Iter { 81 self.vec.par_drain(range) 82 } 83 } 84 } 85