rayon/range_inclusive.rs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381
//! Parallel iterator types for [inclusive ranges][std::range],
//! the type for values created by `a..=b` expressions
//!
//! You will rarely need to interact with this module directly unless you have
//! need to name one of the iterator types.
//!
//! ```
//! use rayon::prelude::*;
//!
//! let r = (0..=100u64).into_par_iter()
//! .sum();
//!
//! // compare result with sequential calculation
//! assert_eq!((0..=100).sum::<u64>(), r);
//! ```
//!
//! [std::range]: https://doc.rust-lang.org/core/ops/struct.RangeInclusive.html
use crate::iter::plumbing::*;
use crate::iter::*;
use std::ops::RangeInclusive;
/// Parallel iterator over an inclusive range, implemented for all integer types and `char`.
///
/// **Note:** The `zip` operation requires `IndexedParallelIterator`
/// which is only implemented for `u8`, `i8`, `u16`, `i16`, and `char`.
///
/// ```
/// use rayon::prelude::*;
///
/// let p = (0..=25u16).into_par_iter()
/// .zip(0..=25u16)
/// .filter(|&(x, y)| x % 5 == 0 || y % 5 == 0)
/// .map(|(x, y)| x * y)
/// .sum::<u16>();
///
/// let s = (0..=25u16).zip(0..=25u16)
/// .filter(|&(x, y)| x % 5 == 0 || y % 5 == 0)
/// .map(|(x, y)| x * y)
/// .sum();
///
/// assert_eq!(p, s);
/// ```
#[derive(Debug, Clone)]
pub struct Iter<T> {
range: RangeInclusive<T>,
}
impl<T> Iter<T>
where
RangeInclusive<T>: Eq,
T: Ord + Copy,
{
/// Returns `Some((start, end))` for `start..=end`, or `None` if it is exhausted.
///
/// Note that `RangeInclusive` does not specify the bounds of an exhausted iterator,
/// so this is a way for us to figure out what we've got. Thankfully, all of the
/// integer types we care about can be trivially cloned.
fn bounds(&self) -> Option<(T, T)> {
let start = *self.range.start();
let end = *self.range.end();
if start <= end && self.range == (start..=end) {
// If the range is still nonempty, this is obviously true
// If the range is exhausted, either start > end or
// the range does not equal start..=end.
Some((start, end))
} else {
None
}
}
}
/// Implemented for ranges of all primitive integer types and `char`.
impl<T> IntoParallelIterator for RangeInclusive<T>
where
Iter<T>: ParallelIterator,
{
type Item = <Iter<T> as ParallelIterator>::Item;
type Iter = Iter<T>;
fn into_par_iter(self) -> Self::Iter {
Iter { range: self }
}
}
/// These traits help drive integer type inference. Without them, an unknown `{integer}` type only
/// has constraints on `Iter<{integer}>`, which will probably give up and use `i32`. By adding
/// these traits on the item type, the compiler can see a more direct constraint to infer like
/// `{integer}: RangeInteger`, which works better. See `test_issue_833` for an example.
///
/// They have to be `pub` since they're seen in the public `impl ParallelIterator` constraints, but
/// we put them in a private modules so they're not actually reachable in our public API.
mod private {
use super::*;
/// Implementation details of `ParallelIterator for Iter<Self>`
pub trait RangeInteger: Sized + Send {
private_decl! {}
fn drive_unindexed<C>(iter: Iter<Self>, consumer: C) -> C::Result
where
C: UnindexedConsumer<Self>;
fn opt_len(iter: &Iter<Self>) -> Option<usize>;
}
/// Implementation details of `IndexedParallelIterator for Iter<Self>`
pub trait IndexedRangeInteger: RangeInteger {
private_decl! {}
fn drive<C>(iter: Iter<Self>, consumer: C) -> C::Result
where
C: Consumer<Self>;
fn len(iter: &Iter<Self>) -> usize;
fn with_producer<CB>(iter: Iter<Self>, callback: CB) -> CB::Output
where
CB: ProducerCallback<Self>;
}
}
use private::{IndexedRangeInteger, RangeInteger};
impl<T: RangeInteger> ParallelIterator for Iter<T> {
type Item = T;
fn drive_unindexed<C>(self, consumer: C) -> C::Result
where
C: UnindexedConsumer<T>,
{
T::drive_unindexed(self, consumer)
}
#[inline]
fn opt_len(&self) -> Option<usize> {
T::opt_len(self)
}
}
impl<T: IndexedRangeInteger> IndexedParallelIterator for Iter<T> {
fn drive<C>(self, consumer: C) -> C::Result
where
C: Consumer<T>,
{
T::drive(self, consumer)
}
#[inline]
fn len(&self) -> usize {
T::len(self)
}
fn with_producer<CB>(self, callback: CB) -> CB::Output
where
CB: ProducerCallback<T>,
{
T::with_producer(self, callback)
}
}
macro_rules! convert {
( $iter:ident . $method:ident ( $( $arg:expr ),* ) ) => {
if let Some((start, end)) = $iter.bounds() {
if let Some(end) = end.checked_add(1) {
(start..end).into_par_iter().$method($( $arg ),*)
} else {
(start..end).into_par_iter().chain(once(end)).$method($( $arg ),*)
}
} else {
empty::<Self>().$method($( $arg ),*)
}
};
}
macro_rules! parallel_range_impl {
( $t:ty ) => {
impl RangeInteger for $t {
private_impl! {}
fn drive_unindexed<C>(iter: Iter<$t>, consumer: C) -> C::Result
where
C: UnindexedConsumer<$t>,
{
convert!(iter.drive_unindexed(consumer))
}
fn opt_len(iter: &Iter<$t>) -> Option<usize> {
convert!(iter.opt_len())
}
}
};
}
macro_rules! indexed_range_impl {
( $t:ty ) => {
parallel_range_impl! { $t }
impl IndexedRangeInteger for $t {
private_impl! {}
fn drive<C>(iter: Iter<$t>, consumer: C) -> C::Result
where
C: Consumer<$t>,
{
convert!(iter.drive(consumer))
}
fn len(iter: &Iter<$t>) -> usize {
iter.range.len()
}
fn with_producer<CB>(iter: Iter<$t>, callback: CB) -> CB::Output
where
CB: ProducerCallback<$t>,
{
convert!(iter.with_producer(callback))
}
}
};
}
// all RangeInclusive<T> with ExactSizeIterator
indexed_range_impl! {u8}
indexed_range_impl! {u16}
indexed_range_impl! {i8}
indexed_range_impl! {i16}
// other RangeInclusive<T> with just Iterator
parallel_range_impl! {usize}
parallel_range_impl! {isize}
parallel_range_impl! {u32}
parallel_range_impl! {i32}
parallel_range_impl! {u64}
parallel_range_impl! {i64}
parallel_range_impl! {u128}
parallel_range_impl! {i128}
// char is special
macro_rules! convert_char {
( $self:ident . $method:ident ( $( $arg:expr ),* ) ) => {
if let Some((start, end)) = $self.bounds() {
let start = start as u32;
let end = end as u32;
if start < 0xD800 && 0xE000 <= end {
// chain the before and after surrogate range fragments
(start..0xD800)
.into_par_iter()
.chain(0xE000..end + 1) // cannot use RangeInclusive, so add one to end
.map(|codepoint| unsafe { char::from_u32_unchecked(codepoint) })
.$method($( $arg ),*)
} else {
// no surrogate range to worry about
(start..end + 1) // cannot use RangeInclusive, so add one to end
.into_par_iter()
.map(|codepoint| unsafe { char::from_u32_unchecked(codepoint) })
.$method($( $arg ),*)
}
} else {
empty::<char>().$method($( $arg ),*)
}
};
}
impl ParallelIterator for Iter<char> {
type Item = char;
fn drive_unindexed<C>(self, consumer: C) -> C::Result
where
C: UnindexedConsumer<Self::Item>,
{
convert_char!(self.drive(consumer))
}
fn opt_len(&self) -> Option<usize> {
Some(self.len())
}
}
// Range<u32> is broken on 16 bit platforms, may as well benefit from it
impl IndexedParallelIterator for Iter<char> {
// Split at the surrogate range first if we're allowed to
fn drive<C>(self, consumer: C) -> C::Result
where
C: Consumer<Self::Item>,
{
convert_char!(self.drive(consumer))
}
fn len(&self) -> usize {
if let Some((start, end)) = self.bounds() {
// Taken from <char as Step>::steps_between
let start = start as u32;
let end = end as u32;
let mut count = end - start;
if start < 0xD800 && 0xE000 <= end {
count -= 0x800
}
(count + 1) as usize // add one for inclusive
} else {
0
}
}
fn with_producer<CB>(self, callback: CB) -> CB::Output
where
CB: ProducerCallback<Self::Item>,
{
convert_char!(self.with_producer(callback))
}
}
#[test]
#[cfg(target_pointer_width = "64")]
fn test_u32_opt_len() {
assert_eq!(Some(101), (0..=100u32).into_par_iter().opt_len());
assert_eq!(
Some(u32::MAX as usize),
(0..=u32::MAX - 1).into_par_iter().opt_len()
);
assert_eq!(
Some(u32::MAX as usize + 1),
(0..=u32::MAX).into_par_iter().opt_len()
);
}
#[test]
fn test_u64_opt_len() {
assert_eq!(Some(101), (0..=100u64).into_par_iter().opt_len());
assert_eq!(
Some(usize::MAX),
(0..=usize::MAX as u64 - 1).into_par_iter().opt_len()
);
assert_eq!(None, (0..=usize::MAX as u64).into_par_iter().opt_len());
assert_eq!(None, (0..=u64::MAX).into_par_iter().opt_len());
}
#[test]
fn test_u128_opt_len() {
assert_eq!(Some(101), (0..=100u128).into_par_iter().opt_len());
assert_eq!(
Some(usize::MAX),
(0..=usize::MAX as u128 - 1).into_par_iter().opt_len()
);
assert_eq!(None, (0..=usize::MAX as u128).into_par_iter().opt_len());
assert_eq!(None, (0..=u128::MAX).into_par_iter().opt_len());
}
// `usize as i64` can overflow, so make sure to wrap it appropriately
// when using the `opt_len` "indexed" mode.
#[test]
#[cfg(target_pointer_width = "64")]
fn test_usize_i64_overflow() {
use crate::ThreadPoolBuilder;
let iter = (-2..=i64::MAX).into_par_iter();
assert_eq!(iter.opt_len(), Some(i64::MAX as usize + 3));
// always run with multiple threads to split into, or this will take forever...
let pool = ThreadPoolBuilder::new().num_threads(8).build().unwrap();
pool.install(|| assert_eq!(iter.find_last(|_| true), Some(i64::MAX)));
}
#[test]
fn test_issue_833() {
fn is_even(n: i64) -> bool {
n % 2 == 0
}
// The integer type should be inferred from `is_even`
let v: Vec<_> = (1..=100).into_par_iter().filter(|&x| is_even(x)).collect();
assert!(v.into_iter().eq((2..=100).step_by(2)));
// Try examples with indexed iterators too
let pos = (0..=100).into_par_iter().position_any(|x| x == 50i16);
assert_eq!(pos, Some(50usize));
assert!((0..=100)
.into_par_iter()
.zip(0..=100)
.all(|(a, b)| i16::eq(&a, &b)));
}