aboutsummaryrefslogtreecommitdiff
path: root/src/range_inclusive.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/range_inclusive.rs')
-rw-r--r--src/range_inclusive.rs288
1 files changed, 288 insertions, 0 deletions
diff --git a/src/range_inclusive.rs b/src/range_inclusive.rs
new file mode 100644
index 0000000..c802b6c
--- /dev/null
+++ b/src/range_inclusive.rs
@@ -0,0 +1,288 @@
+//! 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::char;
+use std::ops::RangeInclusive;
+
+/// Parallel iterator over an inclusive range, implemented for all integer types.
+///
+/// **Note:** The `zip` operation requires `IndexedParallelIterator`
+/// which is only implemented for `u8`, `i8`, `u16`, and `i16`.
+///
+/// ```
+/// 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
+ }
+ }
+}
+
+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 }
+ }
+}
+
+macro_rules! convert {
+ ( $self:ident . $method:ident ( $( $arg:expr ),* ) ) => {
+ if let Some((start, end)) = $self.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::Item>().$method($( $arg ),*)
+ }
+ };
+}
+
+macro_rules! parallel_range_impl {
+ ( $t:ty ) => {
+ impl ParallelIterator for Iter<$t> {
+ type Item = $t;
+
+ fn drive_unindexed<C>(self, consumer: C) -> C::Result
+ where
+ C: UnindexedConsumer<Self::Item>,
+ {
+ convert!(self.drive_unindexed(consumer))
+ }
+
+ fn opt_len(&self) -> Option<usize> {
+ convert!(self.opt_len())
+ }
+ }
+ };
+}
+
+macro_rules! indexed_range_impl {
+ ( $t:ty ) => {
+ parallel_range_impl! { $t }
+
+ impl IndexedParallelIterator for Iter<$t> {
+ fn drive<C>(self, consumer: C) -> C::Result
+ where
+ C: Consumer<Self::Item>,
+ {
+ convert!(self.drive(consumer))
+ }
+
+ fn len(&self) -> usize {
+ self.range.len()
+ }
+
+ fn with_producer<CB>(self, callback: CB) -> CB::Output
+ where
+ CB: ProducerCallback<Self::Item>,
+ {
+ convert!(self.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().into_par_iter().$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() {
+ use std::u32;
+ 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() {
+ use std::{u64, usize};
+ 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() {
+ use std::{u128, usize};
+ 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;
+ use std::i64;
+
+ 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)));
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-14 05:02:42 +0000