From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/rayon/src/collections/binary_heap.rs | 120 +++++++++++++++++++++ vendor/rayon/src/collections/btree_map.rs | 66 ++++++++++++ vendor/rayon/src/collections/btree_set.rs | 52 +++++++++ vendor/rayon/src/collections/hash_map.rs | 96 +++++++++++++++++ vendor/rayon/src/collections/hash_set.rs | 80 ++++++++++++++ vendor/rayon/src/collections/linked_list.rs | 66 ++++++++++++ vendor/rayon/src/collections/mod.rs | 84 +++++++++++++++ vendor/rayon/src/collections/vec_deque.rs | 159 ++++++++++++++++++++++++++++ 8 files changed, 723 insertions(+) create mode 100644 vendor/rayon/src/collections/binary_heap.rs create mode 100644 vendor/rayon/src/collections/btree_map.rs create mode 100644 vendor/rayon/src/collections/btree_set.rs create mode 100644 vendor/rayon/src/collections/hash_map.rs create mode 100644 vendor/rayon/src/collections/hash_set.rs create mode 100644 vendor/rayon/src/collections/linked_list.rs create mode 100644 vendor/rayon/src/collections/mod.rs create mode 100644 vendor/rayon/src/collections/vec_deque.rs (limited to 'vendor/rayon/src/collections') diff --git a/vendor/rayon/src/collections/binary_heap.rs b/vendor/rayon/src/collections/binary_heap.rs new file mode 100644 index 000000000..fa903121a --- /dev/null +++ b/vendor/rayon/src/collections/binary_heap.rs @@ -0,0 +1,120 @@ +//! This module contains the parallel iterator types for heaps +//! (`BinaryHeap`). You will rarely need to interact with it directly +//! unless you have need to name one of the iterator types. + +use std::collections::BinaryHeap; + +use crate::iter::plumbing::*; +use crate::iter::*; + +use crate::vec; + +/// Parallel iterator over a binary heap +#[derive(Debug, Clone)] +pub struct IntoIter { + inner: vec::IntoIter, +} + +impl IntoParallelIterator for BinaryHeap { + type Item = T; + type Iter = IntoIter; + + fn into_par_iter(self) -> Self::Iter { + IntoIter { + inner: Vec::from(self).into_par_iter(), + } + } +} + +delegate_indexed_iterator! { + IntoIter => T, + impl +} + +/// Parallel iterator over an immutable reference to a binary heap +#[derive(Debug)] +pub struct Iter<'a, T: Ord + Sync> { + inner: vec::IntoIter<&'a T>, +} + +impl<'a, T: Ord + Sync> Clone for Iter<'a, T> { + fn clone(&self) -> Self { + Iter { + inner: self.inner.clone(), + } + } +} + +into_par_vec! { + &'a BinaryHeap => Iter<'a, T>, + impl<'a, T: Ord + Sync> +} + +delegate_indexed_iterator! { + Iter<'a, T> => &'a T, + impl<'a, T: Ord + Sync + 'a> +} + +// `BinaryHeap` doesn't have a mutable `Iterator` + +/// Draining parallel iterator that moves out of a binary heap, +/// but keeps the total capacity. +#[derive(Debug)] +pub struct Drain<'a, T: Ord + Send> { + heap: &'a mut BinaryHeap, +} + +impl<'a, T: Ord + Send> ParallelDrainFull for &'a mut BinaryHeap { + type Iter = Drain<'a, T>; + type Item = T; + + fn par_drain(self) -> Self::Iter { + Drain { heap: self } + } +} + +impl<'a, T: Ord + Send> ParallelIterator for Drain<'a, T> { + type Item = T; + + fn drive_unindexed(self, consumer: C) -> C::Result + where + C: UnindexedConsumer, + { + bridge(self, consumer) + } + + fn opt_len(&self) -> Option { + Some(self.len()) + } +} + +impl<'a, T: Ord + Send> IndexedParallelIterator for Drain<'a, T> { + fn drive(self, consumer: C) -> C::Result + where + C: Consumer, + { + bridge(self, consumer) + } + + fn len(&self) -> usize { + self.heap.len() + } + + fn with_producer(self, callback: CB) -> CB::Output + where + CB: ProducerCallback, + { + super::DrainGuard::new(self.heap) + .par_drain(..) + .with_producer(callback) + } +} + +impl<'a, T: Ord + Send> Drop for Drain<'a, T> { + fn drop(&mut self) { + if !self.heap.is_empty() { + // We must not have produced, so just call a normal drain to remove the items. + self.heap.drain(); + } + } +} diff --git a/vendor/rayon/src/collections/btree_map.rs b/vendor/rayon/src/collections/btree_map.rs new file mode 100644 index 000000000..12436dca1 --- /dev/null +++ b/vendor/rayon/src/collections/btree_map.rs @@ -0,0 +1,66 @@ +//! This module contains the parallel iterator types for B-Tree maps +//! (`BTreeMap`). You will rarely need to interact with it directly +//! unless you have need to name one of the iterator types. + +use std::collections::BTreeMap; + +use crate::iter::plumbing::*; +use crate::iter::*; + +use crate::vec; + +/// Parallel iterator over a B-Tree map +#[derive(Debug)] // std doesn't Clone +pub struct IntoIter { + inner: vec::IntoIter<(K, V)>, +} + +into_par_vec! { + BTreeMap => IntoIter, + impl +} + +delegate_iterator! { + IntoIter => (K, V), + impl +} + +/// Parallel iterator over an immutable reference to a B-Tree map +#[derive(Debug)] +pub struct Iter<'a, K: Ord + Sync, V: Sync> { + inner: vec::IntoIter<(&'a K, &'a V)>, +} + +impl<'a, K: Ord + Sync, V: Sync> Clone for Iter<'a, K, V> { + fn clone(&self) -> Self { + Iter { + inner: self.inner.clone(), + } + } +} + +into_par_vec! { + &'a BTreeMap => Iter<'a, K, V>, + impl<'a, K: Ord + Sync, V: Sync> +} + +delegate_iterator! { + Iter<'a, K, V> => (&'a K, &'a V), + impl<'a, K: Ord + Sync + 'a, V: Sync + 'a> +} + +/// Parallel iterator over a mutable reference to a B-Tree map +#[derive(Debug)] +pub struct IterMut<'a, K: Ord + Sync, V: Send> { + inner: vec::IntoIter<(&'a K, &'a mut V)>, +} + +into_par_vec! { + &'a mut BTreeMap => IterMut<'a, K, V>, + impl<'a, K: Ord + Sync, V: Send> +} + +delegate_iterator! { + IterMut<'a, K, V> => (&'a K, &'a mut V), + impl<'a, K: Ord + Sync + 'a, V: Send + 'a> +} diff --git a/vendor/rayon/src/collections/btree_set.rs b/vendor/rayon/src/collections/btree_set.rs new file mode 100644 index 000000000..061d37c7e --- /dev/null +++ b/vendor/rayon/src/collections/btree_set.rs @@ -0,0 +1,52 @@ +//! This module contains the parallel iterator types for B-Tree sets +//! (`BTreeSet`). You will rarely need to interact with it directly +//! unless you have need to name one of the iterator types. + +use std::collections::BTreeSet; + +use crate::iter::plumbing::*; +use crate::iter::*; + +use crate::vec; + +/// Parallel iterator over a B-Tree set +#[derive(Debug)] // std doesn't Clone +pub struct IntoIter { + inner: vec::IntoIter, +} + +into_par_vec! { + BTreeSet => IntoIter, + impl +} + +delegate_iterator! { + IntoIter => T, + impl +} + +/// Parallel iterator over an immutable reference to a B-Tree set +#[derive(Debug)] +pub struct Iter<'a, T: Ord + Sync> { + inner: vec::IntoIter<&'a T>, +} + +impl<'a, T: Ord + Sync + 'a> Clone for Iter<'a, T> { + fn clone(&self) -> Self { + Iter { + inner: self.inner.clone(), + } + } +} + +into_par_vec! { + &'a BTreeSet => Iter<'a, T>, + impl<'a, T: Ord + Sync> +} + +delegate_iterator! { + Iter<'a, T> => &'a T, + impl<'a, T: Ord + Sync + 'a> +} + +// `BTreeSet` doesn't have a mutable `Iterator` diff --git a/vendor/rayon/src/collections/hash_map.rs b/vendor/rayon/src/collections/hash_map.rs new file mode 100644 index 000000000..b657851d8 --- /dev/null +++ b/vendor/rayon/src/collections/hash_map.rs @@ -0,0 +1,96 @@ +//! This module contains the parallel iterator types for hash maps +//! (`HashMap`). You will rarely need to interact with it directly +//! unless you have need to name one of the iterator types. + +use std::collections::HashMap; +use std::hash::{BuildHasher, Hash}; +use std::marker::PhantomData; + +use crate::iter::plumbing::*; +use crate::iter::*; + +use crate::vec; + +/// Parallel iterator over a hash map +#[derive(Debug)] // std doesn't Clone +pub struct IntoIter { + inner: vec::IntoIter<(K, V)>, +} + +into_par_vec! { + HashMap => IntoIter, + impl +} + +delegate_iterator! { + IntoIter => (K, V), + impl +} + +/// Parallel iterator over an immutable reference to a hash map +#[derive(Debug)] +pub struct Iter<'a, K: Hash + Eq + Sync, V: Sync> { + inner: vec::IntoIter<(&'a K, &'a V)>, +} + +impl<'a, K: Hash + Eq + Sync, V: Sync> Clone for Iter<'a, K, V> { + fn clone(&self) -> Self { + Iter { + inner: self.inner.clone(), + } + } +} + +into_par_vec! { + &'a HashMap => Iter<'a, K, V>, + impl<'a, K: Hash + Eq + Sync, V: Sync, S: BuildHasher> +} + +delegate_iterator! { + Iter<'a, K, V> => (&'a K, &'a V), + impl<'a, K: Hash + Eq + Sync + 'a, V: Sync + 'a> +} + +/// Parallel iterator over a mutable reference to a hash map +#[derive(Debug)] +pub struct IterMut<'a, K: Hash + Eq + Sync, V: Send> { + inner: vec::IntoIter<(&'a K, &'a mut V)>, +} + +into_par_vec! { + &'a mut HashMap => IterMut<'a, K, V>, + impl<'a, K: Hash + Eq + Sync, V: Send, S: BuildHasher> +} + +delegate_iterator! { + IterMut<'a, K, V> => (&'a K, &'a mut V), + impl<'a, K: Hash + Eq + Sync + 'a, V: Send + 'a> +} + +/// Draining parallel iterator that moves out of a hash map, +/// but keeps the total capacity. +#[derive(Debug)] +pub struct Drain<'a, K: Hash + Eq + Send, V: Send> { + inner: vec::IntoIter<(K, V)>, + marker: PhantomData<&'a mut HashMap>, +} + +impl<'a, K: Hash + Eq + Send, V: Send, S: BuildHasher> ParallelDrainFull + for &'a mut HashMap +{ + type Iter = Drain<'a, K, V>; + type Item = (K, V); + + fn par_drain(self) -> Self::Iter { + let vec: Vec<_> = self.drain().collect(); + Drain { + inner: vec.into_par_iter(), + marker: PhantomData, + } + } +} + +delegate_iterator! { + Drain<'_, K, V> => (K, V), + impl +} diff --git a/vendor/rayon/src/collections/hash_set.rs b/vendor/rayon/src/collections/hash_set.rs new file mode 100644 index 000000000..b6ee1c110 --- /dev/null +++ b/vendor/rayon/src/collections/hash_set.rs @@ -0,0 +1,80 @@ +//! This module contains the parallel iterator types for hash sets +//! (`HashSet`). You will rarely need to interact with it directly +//! unless you have need to name one of the iterator types. + +use std::collections::HashSet; +use std::hash::{BuildHasher, Hash}; +use std::marker::PhantomData; + +use crate::iter::plumbing::*; +use crate::iter::*; + +use crate::vec; + +/// Parallel iterator over a hash set +#[derive(Debug)] // std doesn't Clone +pub struct IntoIter { + inner: vec::IntoIter, +} + +into_par_vec! { + HashSet => IntoIter, + impl +} + +delegate_iterator! { + IntoIter => T, + impl +} + +/// Parallel iterator over an immutable reference to a hash set +#[derive(Debug)] +pub struct Iter<'a, T: Hash + Eq + Sync> { + inner: vec::IntoIter<&'a T>, +} + +impl<'a, T: Hash + Eq + Sync> Clone for Iter<'a, T> { + fn clone(&self) -> Self { + Iter { + inner: self.inner.clone(), + } + } +} + +into_par_vec! { + &'a HashSet => Iter<'a, T>, + impl<'a, T: Hash + Eq + Sync, S: BuildHasher> +} + +delegate_iterator! { + Iter<'a, T> => &'a T, + impl<'a, T: Hash + Eq + Sync + 'a> +} + +// `HashSet` doesn't have a mutable `Iterator` + +/// Draining parallel iterator that moves out of a hash set, +/// but keeps the total capacity. +#[derive(Debug)] +pub struct Drain<'a, T: Hash + Eq + Send> { + inner: vec::IntoIter, + marker: PhantomData<&'a mut HashSet>, +} + +impl<'a, T: Hash + Eq + Send, S: BuildHasher> ParallelDrainFull for &'a mut HashSet { + type Iter = Drain<'a, T>; + type Item = T; + + fn par_drain(self) -> Self::Iter { + let vec: Vec<_> = self.drain().collect(); + Drain { + inner: vec.into_par_iter(), + marker: PhantomData, + } + } +} + +delegate_iterator! { + Drain<'_, T> => T, + impl +} diff --git a/vendor/rayon/src/collections/linked_list.rs b/vendor/rayon/src/collections/linked_list.rs new file mode 100644 index 000000000..bddd2b0fc --- /dev/null +++ b/vendor/rayon/src/collections/linked_list.rs @@ -0,0 +1,66 @@ +//! This module contains the parallel iterator types for linked lists +//! (`LinkedList`). You will rarely need to interact with it directly +//! unless you have need to name one of the iterator types. + +use std::collections::LinkedList; + +use crate::iter::plumbing::*; +use crate::iter::*; + +use crate::vec; + +/// Parallel iterator over a linked list +#[derive(Debug, Clone)] +pub struct IntoIter { + inner: vec::IntoIter, +} + +into_par_vec! { + LinkedList => IntoIter, + impl +} + +delegate_iterator! { + IntoIter => T, + impl +} + +/// Parallel iterator over an immutable reference to a linked list +#[derive(Debug)] +pub struct Iter<'a, T: Sync> { + inner: vec::IntoIter<&'a T>, +} + +impl<'a, T: Sync> Clone for Iter<'a, T> { + fn clone(&self) -> Self { + Iter { + inner: self.inner.clone(), + } + } +} + +into_par_vec! { + &'a LinkedList => Iter<'a, T>, + impl<'a, T: Sync> +} + +delegate_iterator! { + Iter<'a, T> => &'a T, + impl<'a, T: Sync + 'a> +} + +/// Parallel iterator over a mutable reference to a linked list +#[derive(Debug)] +pub struct IterMut<'a, T: Send> { + inner: vec::IntoIter<&'a mut T>, +} + +into_par_vec! { + &'a mut LinkedList => IterMut<'a, T>, + impl<'a, T: Send> +} + +delegate_iterator! { + IterMut<'a, T> => &'a mut T, + impl<'a, T: Send + 'a> +} diff --git a/vendor/rayon/src/collections/mod.rs b/vendor/rayon/src/collections/mod.rs new file mode 100644 index 000000000..d9b7988da --- /dev/null +++ b/vendor/rayon/src/collections/mod.rs @@ -0,0 +1,84 @@ +//! Parallel iterator types for [standard collections][std::collections] +//! +//! You will rarely need to interact with this module directly unless you need +//! to name one of the iterator types. +//! +//! [std::collections]: https://doc.rust-lang.org/stable/std/collections/ + +/// Convert an iterable collection into a parallel iterator by first +/// collecting into a temporary `Vec`, then iterating that. +macro_rules! into_par_vec { + ($t:ty => $iter:ident<$($i:tt),*>, impl $($args:tt)*) => { + impl $($args)* IntoParallelIterator for $t { + type Item = <$t as IntoIterator>::Item; + type Iter = $iter<$($i),*>; + + fn into_par_iter(self) -> Self::Iter { + use std::iter::FromIterator; + $iter { inner: Vec::from_iter(self).into_par_iter() } + } + } + }; +} + +pub mod binary_heap; +pub mod btree_map; +pub mod btree_set; +pub mod hash_map; +pub mod hash_set; +pub mod linked_list; +pub mod vec_deque; + +use self::drain_guard::DrainGuard; + +mod drain_guard { + use crate::iter::ParallelDrainRange; + use std::mem; + use std::ops::RangeBounds; + + /// A proxy for draining a collection by converting to a `Vec` and back. + /// + /// This is used for draining `BinaryHeap` and `VecDeque`, which both have + /// zero-allocation conversions to/from `Vec`, though not zero-cost: + /// - `BinaryHeap` will heapify from `Vec`, but at least that will be empty. + /// - `VecDeque` has to shift items to offset 0 when converting to `Vec`. + #[allow(missing_debug_implementations)] + pub(super) struct DrainGuard<'a, T, C: From>> { + collection: &'a mut C, + vec: Vec, + } + + impl<'a, T, C> DrainGuard<'a, T, C> + where + C: Default + From>, + Vec: From, + { + pub(super) fn new(collection: &'a mut C) -> Self { + Self { + // Temporarily steal the inner `Vec` so we can drain in place. + vec: Vec::from(mem::replace(collection, C::default())), + collection, + } + } + } + + impl<'a, T, C: From>> Drop for DrainGuard<'a, T, C> { + fn drop(&mut self) { + // Restore the collection from the `Vec` with its original capacity. + *self.collection = C::from(mem::replace(&mut self.vec, Vec::new())); + } + } + + impl<'a, T, C> ParallelDrainRange for &'a mut DrainGuard<'_, T, C> + where + T: Send, + C: From>, + { + type Iter = crate::vec::Drain<'a, T>; + type Item = T; + + fn par_drain>(self, range: R) -> Self::Iter { + self.vec.par_drain(range) + } + } +} diff --git a/vendor/rayon/src/collections/vec_deque.rs b/vendor/rayon/src/collections/vec_deque.rs new file mode 100644 index 000000000..f87ce6b18 --- /dev/null +++ b/vendor/rayon/src/collections/vec_deque.rs @@ -0,0 +1,159 @@ +//! This module contains the parallel iterator types for double-ended queues +//! (`VecDeque`). You will rarely need to interact with it directly +//! unless you have need to name one of the iterator types. + +use std::collections::VecDeque; +use std::ops::{Range, RangeBounds}; + +use crate::iter::plumbing::*; +use crate::iter::*; +use crate::math::simplify_range; + +use crate::slice; +use crate::vec; + +/// Parallel iterator over a double-ended queue +#[derive(Debug, Clone)] +pub struct IntoIter { + inner: vec::IntoIter, +} + +impl IntoParallelIterator for VecDeque { + type Item = T; + type Iter = IntoIter; + + fn into_par_iter(self) -> Self::Iter { + // NOTE: requires data movement if the deque doesn't start at offset 0. + let inner = Vec::from(self).into_par_iter(); + IntoIter { inner } + } +} + +delegate_indexed_iterator! { + IntoIter => T, + impl +} + +/// Parallel iterator over an immutable reference to a double-ended queue +#[derive(Debug)] +pub struct Iter<'a, T: Sync> { + inner: Chain, slice::Iter<'a, T>>, +} + +impl<'a, T: Sync> Clone for Iter<'a, T> { + fn clone(&self) -> Self { + Iter { + inner: self.inner.clone(), + } + } +} + +impl<'a, T: Sync> IntoParallelIterator for &'a VecDeque { + type Item = &'a T; + type Iter = Iter<'a, T>; + + fn into_par_iter(self) -> Self::Iter { + let (a, b) = self.as_slices(); + Iter { + inner: a.into_par_iter().chain(b), + } + } +} + +delegate_indexed_iterator! { + Iter<'a, T> => &'a T, + impl<'a, T: Sync + 'a> +} + +/// Parallel iterator over a mutable reference to a double-ended queue +#[derive(Debug)] +pub struct IterMut<'a, T: Send> { + inner: Chain, slice::IterMut<'a, T>>, +} + +impl<'a, T: Send> IntoParallelIterator for &'a mut VecDeque { + type Item = &'a mut T; + type Iter = IterMut<'a, T>; + + fn into_par_iter(self) -> Self::Iter { + let (a, b) = self.as_mut_slices(); + IterMut { + inner: a.into_par_iter().chain(b), + } + } +} + +delegate_indexed_iterator! { + IterMut<'a, T> => &'a mut T, + impl<'a, T: Send + 'a> +} + +/// Draining parallel iterator that moves a range out of a double-ended queue, +/// but keeps the total capacity. +#[derive(Debug)] +pub struct Drain<'a, T: Send> { + deque: &'a mut VecDeque, + range: Range, + orig_len: usize, +} + +impl<'a, T: Send> ParallelDrainRange for &'a mut VecDeque { + type Iter = Drain<'a, T>; + type Item = T; + + fn par_drain>(self, range: R) -> Self::Iter { + Drain { + orig_len: self.len(), + range: simplify_range(range, self.len()), + deque: self, + } + } +} + +impl<'a, T: Send> ParallelIterator for Drain<'a, T> { + type Item = T; + + fn drive_unindexed(self, consumer: C) -> C::Result + where + C: UnindexedConsumer, + { + bridge(self, consumer) + } + + fn opt_len(&self) -> Option { + Some(self.len()) + } +} + +impl<'a, T: Send> IndexedParallelIterator for Drain<'a, T> { + fn drive(self, consumer: C) -> C::Result + where + C: Consumer, + { + bridge(self, consumer) + } + + fn len(&self) -> usize { + self.range.len() + } + + fn with_producer(self, callback: CB) -> CB::Output + where + CB: ProducerCallback, + { + // NOTE: requires data movement if the deque doesn't start at offset 0. + super::DrainGuard::new(self.deque) + .par_drain(self.range.clone()) + .with_producer(callback) + } +} + +impl<'a, T: Send> Drop for Drain<'a, T> { + fn drop(&mut self) { + if self.deque.len() != self.orig_len - self.range.len() { + // We must not have produced, so just call a normal drain to remove the items. + assert_eq!(self.deque.len(), self.orig_len); + self.deque.drain(self.range.clone()); + } + } +} -- cgit v1.2.3