src/vendor/rayon/src/range.rs

   1 //! Parallel iterator types for [ranges][std::range],
   2 //! the type for values created by `a..b` expressions
   3 //!
   4 //! You will rarely need to interact with this module directly unless you have
   5 //! need to name one of the iterator types.
   6 //!
   7 //! ```
   8 //! use rayon::prelude::*;
   9 //!
  10 //! let r = (0..100u64).into_par_iter()
  11 //!                    .sum();
  12 //!
  13 //! // compare result with sequential calculation
  14 //! assert_eq!((0..100).sum::<u64>(), r);
  15 //! ```
  16 //!
  17 //! [std::range]: https://doc.rust-lang.org/core/ops/struct.Range.html
  18
  19 use iter::*;
  20 use iter::plumbing::*;
  21 use std::ops::Range;
  22
  23 /// Parallel iterator over a range, implemented for all integer types.
  24 ///
  25 /// **Note:** The `zip` operation requires `IndexedParallelIterator`
  26 /// which is not implemented for `u64` or `i64`.
  27 ///
  28 /// ```
  29 /// use rayon::prelude::*;
  30 ///
  31 /// let p = (0..25usize).into_par_iter()
  32 ///                   .zip(0..25usize)
  33 ///                   .filter(|&(x, y)| x % 5 == 0 || y % 5 == 0)
  34 ///                   .map(|(x, y)| x * y)
  35 ///                   .sum::<usize>();
  36 ///
  37 /// let s = (0..25usize).zip(0..25)
  38 ///                   .filter(|&(x, y)| x % 5 == 0 || y % 5 == 0)
  39 ///                   .map(|(x, y)| x * y)
  40 ///                   .sum();
  41 ///
  42 /// assert_eq!(p, s);
  43 /// ```
  44 #[derive(Debug, Clone)]
  45 pub struct Iter<T> {
  46     range: Range<T>,
  47 }
  48
  49 impl<T> IntoParallelIterator for Range<T>
  50     where Iter<T>: ParallelIterator
  51 {
  52     type Item = <Iter<T> as ParallelIterator>::Item;
  53     type Iter = Iter<T>;
  54
  55     fn into_par_iter(self) -> Self::Iter {
  56         Iter { range: self }
  57     }
  58 }
  59
  60 struct IterProducer<T> {
  61     range: Range<T>,
  62 }
  63
  64 impl<T> IntoIterator for IterProducer<T>
  65     where Range<T>: Iterator
  66 {
  67     type Item = <Range<T> as Iterator>::Item;
  68     type IntoIter = Range<T>;
  69
  70     fn into_iter(self) -> Self::IntoIter {
  71         self.range
  72     }
  73 }
  74
  75 macro_rules! indexed_range_impl {
  76     ( $t:ty ) => {
  77         impl ParallelIterator for Iter<$t> {
  78             type Item = $t;
  79
  80             fn drive_unindexed<C>(self, consumer: C) -> C::Result
  81                 where C: UnindexedConsumer<Self::Item>
  82             {
  83                 bridge(self, consumer)
  84             }
  85
  86             fn opt_len(&self) -> Option<usize> {
  87                 Some(self.len())
  88             }
  89         }
  90
  91         impl IndexedParallelIterator for Iter<$t> {
  92             fn drive<C>(self, consumer: C) -> C::Result
  93                 where C: Consumer<Self::Item>
  94             {
  95                 bridge(self, consumer)
  96             }
  97
  98             fn len(&self) -> usize {
  99                 self.range.len()
 100             }
 101
 102             fn with_producer<CB>(self, callback: CB) -> CB::Output
 103                 where CB: ProducerCallback<Self::Item>
 104             {
 105                 callback.callback(IterProducer { range: self.range })
 106             }
 107         }
 108
 109         impl Producer for IterProducer<$t> {
 110
 111             type Item = <Range<$t> as Iterator>::Item;
 112             type IntoIter = Range<$t>;
 113             fn into_iter(self) -> Self::IntoIter {
 114                 self.range
 115             }
 116
 117             fn split_at(self, index: usize) -> (Self, Self) {
 118                 assert!(index <= self.range.len());
 119                 // For signed $t, the length and requested index could be greater than $t::MAX, and
 120                 // then `index as $t` could wrap to negative, so wrapping_add is necessary.
 121                 let mid = self.range.start.wrapping_add(index as $t);
 122                 let left = self.range.start .. mid;
 123                 let right = mid .. self.range.end;
 124                 (IterProducer { range: left }, IterProducer { range: right })
 125             }
 126         }
 127     }
 128 }
 129
 130 macro_rules! unindexed_range_impl {
 131     ( $t:ty ) => {
 132         impl IterProducer<$t> {
 133             fn len(&self) -> u64 {
 134                 let Range { start, end } = self.range;
 135                 if end > start {
 136                     end.wrapping_sub(start) as u64
 137                 } else {
 138                     0
 139                 }
 140             }
 141         }
 142
 143         impl ParallelIterator for Iter<$t> {
 144             type Item = $t;
 145
 146             fn drive_unindexed<C>(self, consumer: C) -> C::Result
 147                 where C: UnindexedConsumer<Self::Item>
 148             {
 149                 bridge_unindexed(IterProducer { range: self.range }, consumer)
 150             }
 151         }
 152
 153         impl UnindexedProducer for IterProducer<$t> {
 154             type Item = $t;
 155
 156             fn split(mut self) -> (Self, Option<Self>) {
 157                 let index = self.len() / 2;
 158                 if index > 0 {
 159                     let mid = self.range.start.wrapping_add(index as $t);
 160                     let right = mid .. self.range.end;
 161                     self.range.end = mid;
 162                     (self, Some(IterProducer { range: right }))
 163                 } else {
 164                     (self, None)
 165                 }
 166             }
 167
 168             fn fold_with<F>(self, folder: F) -> F
 169                 where F: Folder<Self::Item>
 170             {
 171                 folder.consume_iter(self)
 172             }
 173         }
 174     }
 175 }
 176
 177 // all Range<T> with ExactSizeIterator
 178 indexed_range_impl!{u8}
 179 indexed_range_impl!{u16}
 180 indexed_range_impl!{u32}
 181 indexed_range_impl!{usize}
 182 indexed_range_impl!{i8}
 183 indexed_range_impl!{i16}
 184 indexed_range_impl!{i32}
 185 indexed_range_impl!{isize}
 186
 187 // other Range<T> with just Iterator
 188 unindexed_range_impl!{u64}
 189 unindexed_range_impl!{i64}
 190
 191
 192 #[test]
 193 pub fn check_range_split_at_overflow() {
 194     // Note, this split index overflows i8!
 195     let producer = IterProducer { range: -100i8..100 };
 196     let (left, right) = producer.split_at(150);
 197     let r1: i32 = left.range.map(|i| i as i32).sum();
 198     let r2: i32 = right.range.map(|i| i as i32).sum();
 199     assert_eq!(r1 + r2, -100);
 200 }