diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
commit | 26a029d407be480d791972afb5975cf62c9360a6 (patch) | |
tree | f435a8308119effd964b339f76abb83a57c29483 /third_party/rust/rayon/src/collections | |
parent | Initial commit. (diff) | |
download | firefox-26a029d407be480d791972afb5975cf62c9360a6.tar.xz firefox-26a029d407be480d791972afb5975cf62c9360a6.zip |
Adding upstream version 124.0.1.upstream/124.0.1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'third_party/rust/rayon/src/collections')
-rw-r--r-- | third_party/rust/rayon/src/collections/binary_heap.rs | 120 | ||||
-rw-r--r-- | third_party/rust/rayon/src/collections/btree_map.rs | 66 | ||||
-rw-r--r-- | third_party/rust/rayon/src/collections/btree_set.rs | 52 | ||||
-rw-r--r-- | third_party/rust/rayon/src/collections/hash_map.rs | 96 | ||||
-rw-r--r-- | third_party/rust/rayon/src/collections/hash_set.rs | 80 | ||||
-rw-r--r-- | third_party/rust/rayon/src/collections/linked_list.rs | 66 | ||||
-rw-r--r-- | third_party/rust/rayon/src/collections/mod.rs | 84 | ||||
-rw-r--r-- | third_party/rust/rayon/src/collections/vec_deque.rs | 159 |
8 files changed, 723 insertions, 0 deletions
diff --git a/third_party/rust/rayon/src/collections/binary_heap.rs b/third_party/rust/rayon/src/collections/binary_heap.rs new file mode 100644 index 0000000000..fa903121af --- /dev/null +++ b/third_party/rust/rayon/src/collections/binary_heap.rs @@ -0,0 +1,120 @@ +//! This module contains the parallel iterator types for heaps +//! (`BinaryHeap<T>`). 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<T: Ord + Send> { + inner: vec::IntoIter<T>, +} + +impl<T: Ord + Send> IntoParallelIterator for BinaryHeap<T> { + type Item = T; + type Iter = IntoIter<T>; + + fn into_par_iter(self) -> Self::Iter { + IntoIter { + inner: Vec::from(self).into_par_iter(), + } + } +} + +delegate_indexed_iterator! { + IntoIter<T> => T, + impl<T: Ord + Send> +} + +/// 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<T> => 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<T>, +} + +impl<'a, T: Ord + Send> ParallelDrainFull for &'a mut BinaryHeap<T> { + 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<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + bridge(self, consumer) + } + + fn opt_len(&self) -> Option<usize> { + Some(self.len()) + } +} + +impl<'a, T: Ord + Send> IndexedParallelIterator for Drain<'a, T> { + fn drive<C>(self, consumer: C) -> C::Result + where + C: Consumer<Self::Item>, + { + bridge(self, consumer) + } + + fn len(&self) -> usize { + self.heap.len() + } + + fn with_producer<CB>(self, callback: CB) -> CB::Output + where + CB: ProducerCallback<Self::Item>, + { + 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/third_party/rust/rayon/src/collections/btree_map.rs b/third_party/rust/rayon/src/collections/btree_map.rs new file mode 100644 index 0000000000..12436dca1c --- /dev/null +++ b/third_party/rust/rayon/src/collections/btree_map.rs @@ -0,0 +1,66 @@ +//! This module contains the parallel iterator types for B-Tree maps +//! (`BTreeMap<K, V>`). 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<K: Ord + Send, V: Send> { + inner: vec::IntoIter<(K, V)>, +} + +into_par_vec! { + BTreeMap<K, V> => IntoIter<K, V>, + impl<K: Ord + Send, V: Send> +} + +delegate_iterator! { + IntoIter<K, V> => (K, V), + impl<K: Ord + Send, V: Send> +} + +/// 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<K, V> => 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<K, V> => 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/third_party/rust/rayon/src/collections/btree_set.rs b/third_party/rust/rayon/src/collections/btree_set.rs new file mode 100644 index 0000000000..061d37c7ea --- /dev/null +++ b/third_party/rust/rayon/src/collections/btree_set.rs @@ -0,0 +1,52 @@ +//! This module contains the parallel iterator types for B-Tree sets +//! (`BTreeSet<T>`). 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<T: Ord + Send> { + inner: vec::IntoIter<T>, +} + +into_par_vec! { + BTreeSet<T> => IntoIter<T>, + impl<T: Ord + Send> +} + +delegate_iterator! { + IntoIter<T> => T, + impl<T: Ord + Send> +} + +/// 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<T> => 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/third_party/rust/rayon/src/collections/hash_map.rs b/third_party/rust/rayon/src/collections/hash_map.rs new file mode 100644 index 0000000000..b657851d89 --- /dev/null +++ b/third_party/rust/rayon/src/collections/hash_map.rs @@ -0,0 +1,96 @@ +//! This module contains the parallel iterator types for hash maps +//! (`HashMap<K, V>`). 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<K: Hash + Eq + Send, V: Send> { + inner: vec::IntoIter<(K, V)>, +} + +into_par_vec! { + HashMap<K, V, S> => IntoIter<K, V>, + impl<K: Hash + Eq + Send, V: Send, S: BuildHasher> +} + +delegate_iterator! { + IntoIter<K, V> => (K, V), + impl<K: Hash + Eq + Send, V: Send> +} + +/// 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<K, V, S> => 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<K, V, S> => 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<K, V>>, +} + +impl<'a, K: Hash + Eq + Send, V: Send, S: BuildHasher> ParallelDrainFull + for &'a mut HashMap<K, V, S> +{ + 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<K: Hash + Eq + Send, V: Send> +} diff --git a/third_party/rust/rayon/src/collections/hash_set.rs b/third_party/rust/rayon/src/collections/hash_set.rs new file mode 100644 index 0000000000..b6ee1c1109 --- /dev/null +++ b/third_party/rust/rayon/src/collections/hash_set.rs @@ -0,0 +1,80 @@ +//! This module contains the parallel iterator types for hash sets +//! (`HashSet<T>`). 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<T: Hash + Eq + Send> { + inner: vec::IntoIter<T>, +} + +into_par_vec! { + HashSet<T, S> => IntoIter<T>, + impl<T: Hash + Eq + Send, S: BuildHasher> +} + +delegate_iterator! { + IntoIter<T> => T, + impl<T: Hash + Eq + Send> +} + +/// 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<T, S> => 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<T>, + marker: PhantomData<&'a mut HashSet<T>>, +} + +impl<'a, T: Hash + Eq + Send, S: BuildHasher> ParallelDrainFull for &'a mut HashSet<T, S> { + 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<T: Hash + Eq + Send> +} diff --git a/third_party/rust/rayon/src/collections/linked_list.rs b/third_party/rust/rayon/src/collections/linked_list.rs new file mode 100644 index 0000000000..bddd2b0fce --- /dev/null +++ b/third_party/rust/rayon/src/collections/linked_list.rs @@ -0,0 +1,66 @@ +//! This module contains the parallel iterator types for linked lists +//! (`LinkedList<T>`). 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<T: Send> { + inner: vec::IntoIter<T>, +} + +into_par_vec! { + LinkedList<T> => IntoIter<T>, + impl<T: Send> +} + +delegate_iterator! { + IntoIter<T> => T, + impl<T: Send> +} + +/// 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<T> => 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<T> => IterMut<'a, T>, + impl<'a, T: Send> +} + +delegate_iterator! { + IterMut<'a, T> => &'a mut T, + impl<'a, T: Send + 'a> +} diff --git a/third_party/rust/rayon/src/collections/mod.rs b/third_party/rust/rayon/src/collections/mod.rs new file mode 100644 index 0000000000..3c99f32c4a --- /dev/null +++ b/third_party/rust/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<Vec<T>>> { + collection: &'a mut C, + vec: Vec<T>, + } + + impl<'a, T, C> DrainGuard<'a, T, C> + where + C: Default + From<Vec<T>>, + Vec<T>: From<C>, + { + 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::take(collection)), + collection, + } + } + } + + impl<'a, T, C: From<Vec<T>>> 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::take(&mut self.vec)); + } + } + + impl<'a, T, C> ParallelDrainRange<usize> for &'a mut DrainGuard<'_, T, C> + where + T: Send, + C: From<Vec<T>>, + { + type Iter = crate::vec::Drain<'a, T>; + type Item = T; + + fn par_drain<R: RangeBounds<usize>>(self, range: R) -> Self::Iter { + self.vec.par_drain(range) + } + } +} diff --git a/third_party/rust/rayon/src/collections/vec_deque.rs b/third_party/rust/rayon/src/collections/vec_deque.rs new file mode 100644 index 0000000000..f87ce6b185 --- /dev/null +++ b/third_party/rust/rayon/src/collections/vec_deque.rs @@ -0,0 +1,159 @@ +//! This module contains the parallel iterator types for double-ended queues +//! (`VecDeque<T>`). 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<T: Send> { + inner: vec::IntoIter<T>, +} + +impl<T: Send> IntoParallelIterator for VecDeque<T> { + type Item = T; + type Iter = IntoIter<T>; + + 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> => T, + impl<T: Send> +} + +/// 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>, 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<T> { + 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>, slice::IterMut<'a, T>>, +} + +impl<'a, T: Send> IntoParallelIterator for &'a mut VecDeque<T> { + 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<T>, + range: Range<usize>, + orig_len: usize, +} + +impl<'a, T: Send> ParallelDrainRange<usize> for &'a mut VecDeque<T> { + type Iter = Drain<'a, T>; + type Item = T; + + fn par_drain<R: RangeBounds<usize>>(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<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + bridge(self, consumer) + } + + fn opt_len(&self) -> Option<usize> { + Some(self.len()) + } +} + +impl<'a, T: Send> IndexedParallelIterator for Drain<'a, T> { + fn drive<C>(self, consumer: C) -> C::Result + where + C: Consumer<Self::Item>, + { + bridge(self, consumer) + } + + fn len(&self) -> usize { + self.range.len() + } + + fn with_producer<CB>(self, callback: CB) -> CB::Output + where + CB: ProducerCallback<Self::Item>, + { + // 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()); + } + } +} |