diff options
Diffstat (limited to 'third_party/rust/hashbrown/src/external_trait_impls/rayon')
5 files changed, 298 insertions, 59 deletions
diff --git a/third_party/rust/hashbrown/src/external_trait_impls/rayon/map.rs b/third_party/rust/hashbrown/src/external_trait_impls/rayon/map.rs index 14d91c220c..2534dc9b2b 100644 --- a/third_party/rust/hashbrown/src/external_trait_impls/rayon/map.rs +++ b/third_party/rust/hashbrown/src/external_trait_impls/rayon/map.rs @@ -232,11 +232,11 @@ impl<K: Eq + Hash, V: fmt::Debug> fmt::Debug for ParValuesMut<'_, K, V> { /// [`into_par_iter`]: /hashbrown/struct.HashMap.html#method.into_par_iter /// [`HashMap`]: /hashbrown/struct.HashMap.html /// [`IntoParallelIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelIterator.html -pub struct IntoParIter<K, V, A: Allocator + Clone = Global> { +pub struct IntoParIter<K, V, A: Allocator = Global> { inner: RawIntoParIter<(K, V), A>, } -impl<K: Send, V: Send, A: Allocator + Clone + Send> ParallelIterator for IntoParIter<K, V, A> { +impl<K: Send, V: Send, A: Allocator + Send> ParallelIterator for IntoParIter<K, V, A> { type Item = (K, V); #[cfg_attr(feature = "inline-more", inline)] @@ -248,9 +248,7 @@ impl<K: Send, V: Send, A: Allocator + Clone + Send> ParallelIterator for IntoPar } } -impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, A: Allocator + Clone> fmt::Debug - for IntoParIter<K, V, A> -{ +impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, A: Allocator> fmt::Debug for IntoParIter<K, V, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { ParIter { inner: unsafe { self.inner.par_iter() }, @@ -267,11 +265,11 @@ impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, A: Allocator + Clone> fmt::Debug /// /// [`par_drain`]: /hashbrown/struct.HashMap.html#method.par_drain /// [`HashMap`]: /hashbrown/struct.HashMap.html -pub struct ParDrain<'a, K, V, A: Allocator + Clone = Global> { +pub struct ParDrain<'a, K, V, A: Allocator = Global> { inner: RawParDrain<'a, (K, V), A>, } -impl<K: Send, V: Send, A: Allocator + Clone + Sync> ParallelIterator for ParDrain<'_, K, V, A> { +impl<K: Send, V: Send, A: Allocator + Sync> ParallelIterator for ParDrain<'_, K, V, A> { type Item = (K, V); #[cfg_attr(feature = "inline-more", inline)] @@ -283,9 +281,7 @@ impl<K: Send, V: Send, A: Allocator + Clone + Sync> ParallelIterator for ParDrai } } -impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, A: Allocator + Clone> fmt::Debug - for ParDrain<'_, K, V, A> -{ +impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, A: Allocator> fmt::Debug for ParDrain<'_, K, V, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { ParIter { inner: unsafe { self.inner.par_iter() }, @@ -295,7 +291,7 @@ impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, A: Allocator + Clone> fmt::Debug } } -impl<K: Sync, V: Sync, S, A: Allocator + Clone> HashMap<K, V, S, A> { +impl<K: Sync, V: Sync, S, A: Allocator> HashMap<K, V, S, A> { /// Visits (potentially in parallel) immutably borrowed keys in an arbitrary order. #[cfg_attr(feature = "inline-more", inline)] pub fn par_keys(&self) -> ParKeys<'_, K, V> { @@ -315,7 +311,7 @@ impl<K: Sync, V: Sync, S, A: Allocator + Clone> HashMap<K, V, S, A> { } } -impl<K: Send, V: Send, S, A: Allocator + Clone> HashMap<K, V, S, A> { +impl<K: Send, V: Send, S, A: Allocator> HashMap<K, V, S, A> { /// Visits (potentially in parallel) mutably borrowed values in an arbitrary order. #[cfg_attr(feature = "inline-more", inline)] pub fn par_values_mut(&mut self) -> ParValuesMut<'_, K, V> { @@ -340,7 +336,7 @@ where K: Eq + Hash + Sync, V: PartialEq + Sync, S: BuildHasher + Sync, - A: Allocator + Clone + Sync, + A: Allocator + Sync, { /// Returns `true` if the map is equal to another, /// i.e. both maps contain the same keys mapped to the same values. @@ -354,9 +350,7 @@ where } } -impl<K: Send, V: Send, S, A: Allocator + Clone + Send> IntoParallelIterator - for HashMap<K, V, S, A> -{ +impl<K: Send, V: Send, S, A: Allocator + Send> IntoParallelIterator for HashMap<K, V, S, A> { type Item = (K, V); type Iter = IntoParIter<K, V, A>; @@ -368,9 +362,7 @@ impl<K: Send, V: Send, S, A: Allocator + Clone + Send> IntoParallelIterator } } -impl<'a, K: Sync, V: Sync, S, A: Allocator + Clone> IntoParallelIterator - for &'a HashMap<K, V, S, A> -{ +impl<'a, K: Sync, V: Sync, S, A: Allocator> IntoParallelIterator for &'a HashMap<K, V, S, A> { type Item = (&'a K, &'a V); type Iter = ParIter<'a, K, V>; @@ -383,9 +375,7 @@ impl<'a, K: Sync, V: Sync, S, A: Allocator + Clone> IntoParallelIterator } } -impl<'a, K: Sync, V: Send, S, A: Allocator + Clone> IntoParallelIterator - for &'a mut HashMap<K, V, S, A> -{ +impl<'a, K: Sync, V: Send, S, A: Allocator> IntoParallelIterator for &'a mut HashMap<K, V, S, A> { type Item = (&'a K, &'a mut V); type Iter = ParIterMut<'a, K, V>; @@ -424,7 +414,7 @@ where K: Eq + Hash + Send, V: Send, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { fn par_extend<I>(&mut self, par_iter: I) where @@ -440,7 +430,7 @@ where K: Copy + Eq + Hash + Sync, V: Copy + Sync, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { fn par_extend<I>(&mut self, par_iter: I) where @@ -456,7 +446,7 @@ where K: Eq + Hash, S: BuildHasher, I: IntoParallelIterator, - A: Allocator + Clone, + A: Allocator, HashMap<K, V, S, A>: Extend<I::Item>, { let (list, len) = super::helpers::collect(par_iter); @@ -561,10 +551,7 @@ mod test_par_map { assert_eq!(value.load(Ordering::Relaxed), 100); // retain only half - let _v: Vec<_> = hm - .into_par_iter() - .filter(|&(ref key, _)| key.k < 50) - .collect(); + let _v: Vec<_> = hm.into_par_iter().filter(|(key, _)| key.k < 50).collect(); assert_eq!(key.load(Ordering::Relaxed), 50); assert_eq!(value.load(Ordering::Relaxed), 50); @@ -611,7 +598,7 @@ mod test_par_map { assert_eq!(value.load(Ordering::Relaxed), 100); // retain only half - let _v: Vec<_> = hm.drain().filter(|&(ref key, _)| key.k < 50).collect(); + let _v: Vec<_> = hm.drain().filter(|(key, _)| key.k < 50).collect(); assert!(hm.is_empty()); assert_eq!(key.load(Ordering::Relaxed), 50); diff --git a/third_party/rust/hashbrown/src/external_trait_impls/rayon/mod.rs b/third_party/rust/hashbrown/src/external_trait_impls/rayon/mod.rs index 99337a1ce3..61ca69b61d 100644 --- a/third_party/rust/hashbrown/src/external_trait_impls/rayon/mod.rs +++ b/third_party/rust/hashbrown/src/external_trait_impls/rayon/mod.rs @@ -2,3 +2,4 @@ mod helpers; pub(crate) mod map; pub(crate) mod raw; pub(crate) mod set; +pub(crate) mod table; diff --git a/third_party/rust/hashbrown/src/external_trait_impls/rayon/raw.rs b/third_party/rust/hashbrown/src/external_trait_impls/rayon/raw.rs index 883303e278..612be47a55 100644 --- a/third_party/rust/hashbrown/src/external_trait_impls/rayon/raw.rs +++ b/third_party/rust/hashbrown/src/external_trait_impls/rayon/raw.rs @@ -1,7 +1,6 @@ use crate::raw::Bucket; use crate::raw::{Allocator, Global, RawIter, RawIterRange, RawTable}; use crate::scopeguard::guard; -use alloc::alloc::dealloc; use core::marker::PhantomData; use core::mem; use core::ptr::NonNull; @@ -76,18 +75,18 @@ impl<T> UnindexedProducer for ParIterProducer<T> { } /// Parallel iterator which consumes a table and returns elements. -pub struct RawIntoParIter<T, A: Allocator + Clone = Global> { +pub struct RawIntoParIter<T, A: Allocator = Global> { table: RawTable<T, A>, } -impl<T, A: Allocator + Clone> RawIntoParIter<T, A> { +impl<T, A: Allocator> RawIntoParIter<T, A> { #[cfg_attr(feature = "inline-more", inline)] pub(super) unsafe fn par_iter(&self) -> RawParIter<T> { self.table.par_iter() } } -impl<T: Send, A: Allocator + Clone + Send> ParallelIterator for RawIntoParIter<T, A> { +impl<T: Send, A: Allocator + Send> ParallelIterator for RawIntoParIter<T, A> { type Item = T; #[cfg_attr(feature = "inline-more", inline)] @@ -97,9 +96,9 @@ impl<T: Send, A: Allocator + Clone + Send> ParallelIterator for RawIntoParIter<T { let iter = unsafe { self.table.iter().iter }; let _guard = guard(self.table.into_allocation(), |alloc| { - if let Some((ptr, layout)) = *alloc { + if let Some((ptr, layout, ref alloc)) = *alloc { unsafe { - dealloc(ptr.as_ptr(), layout); + alloc.deallocate(ptr, layout); } } }); @@ -109,23 +108,23 @@ impl<T: Send, A: Allocator + Clone + Send> ParallelIterator for RawIntoParIter<T } /// Parallel iterator which consumes elements without freeing the table storage. -pub struct RawParDrain<'a, T, A: Allocator + Clone = Global> { +pub struct RawParDrain<'a, T, A: Allocator = Global> { // We don't use a &'a mut RawTable<T> because we want RawParDrain to be // covariant over T. table: NonNull<RawTable<T, A>>, marker: PhantomData<&'a RawTable<T, A>>, } -unsafe impl<T: Send, A: Allocator + Clone> Send for RawParDrain<'_, T, A> {} +unsafe impl<T: Send, A: Allocator> Send for RawParDrain<'_, T, A> {} -impl<T, A: Allocator + Clone> RawParDrain<'_, T, A> { +impl<T, A: Allocator> RawParDrain<'_, T, A> { #[cfg_attr(feature = "inline-more", inline)] pub(super) unsafe fn par_iter(&self) -> RawParIter<T> { self.table.as_ref().par_iter() } } -impl<T: Send, A: Allocator + Clone> ParallelIterator for RawParDrain<'_, T, A> { +impl<T: Send, A: Allocator> ParallelIterator for RawParDrain<'_, T, A> { type Item = T; #[cfg_attr(feature = "inline-more", inline)] @@ -143,7 +142,7 @@ impl<T: Send, A: Allocator + Clone> ParallelIterator for RawParDrain<'_, T, A> { } } -impl<T, A: Allocator + Clone> Drop for RawParDrain<'_, T, A> { +impl<T, A: Allocator> Drop for RawParDrain<'_, T, A> { fn drop(&mut self) { // If drive_unindexed is not called then simply clear the table. unsafe { @@ -204,7 +203,7 @@ impl<T> Drop for ParDrainProducer<T> { } } -impl<T, A: Allocator + Clone> RawTable<T, A> { +impl<T, A: Allocator> RawTable<T, A> { /// Returns a parallel iterator over the elements in a `RawTable`. #[cfg_attr(feature = "inline-more", inline)] pub unsafe fn par_iter(&self) -> RawParIter<T> { diff --git a/third_party/rust/hashbrown/src/external_trait_impls/rayon/set.rs b/third_party/rust/hashbrown/src/external_trait_impls/rayon/set.rs index ee4f6e6693..3de98fccb8 100644 --- a/third_party/rust/hashbrown/src/external_trait_impls/rayon/set.rs +++ b/third_party/rust/hashbrown/src/external_trait_impls/rayon/set.rs @@ -16,11 +16,11 @@ use rayon::iter::{FromParallelIterator, IntoParallelIterator, ParallelExtend, Pa /// [`into_par_iter`]: /hashbrown/struct.HashSet.html#method.into_par_iter /// [`HashSet`]: /hashbrown/struct.HashSet.html /// [`IntoParallelIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelIterator.html -pub struct IntoParIter<T, A: Allocator + Clone = Global> { +pub struct IntoParIter<T, A: Allocator = Global> { inner: map::IntoParIter<T, (), A>, } -impl<T: Send, A: Allocator + Clone + Send> ParallelIterator for IntoParIter<T, A> { +impl<T: Send, A: Allocator + Send> ParallelIterator for IntoParIter<T, A> { type Item = T; fn drive_unindexed<C>(self, consumer: C) -> C::Result @@ -38,11 +38,11 @@ impl<T: Send, A: Allocator + Clone + Send> ParallelIterator for IntoParIter<T, A /// /// [`par_drain`]: /hashbrown/struct.HashSet.html#method.par_drain /// [`HashSet`]: /hashbrown/struct.HashSet.html -pub struct ParDrain<'a, T, A: Allocator + Clone = Global> { +pub struct ParDrain<'a, T, A: Allocator = Global> { inner: map::ParDrain<'a, T, (), A>, } -impl<T: Send, A: Allocator + Clone + Send + Sync> ParallelIterator for ParDrain<'_, T, A> { +impl<T: Send, A: Allocator + Send + Sync> ParallelIterator for ParDrain<'_, T, A> { type Item = T; fn drive_unindexed<C>(self, consumer: C) -> C::Result @@ -85,7 +85,7 @@ impl<'a, T: Sync> ParallelIterator for ParIter<'a, T> { /// /// [`par_difference`]: /hashbrown/struct.HashSet.html#method.par_difference /// [`HashSet`]: /hashbrown/struct.HashSet.html -pub struct ParDifference<'a, T, S, A: Allocator + Clone = Global> { +pub struct ParDifference<'a, T, S, A: Allocator = Global> { a: &'a HashSet<T, S, A>, b: &'a HashSet<T, S, A>, } @@ -94,7 +94,7 @@ impl<'a, T, S, A> ParallelIterator for ParDifference<'a, T, S, A> where T: Eq + Hash + Sync, S: BuildHasher + Sync, - A: Allocator + Clone + Sync, + A: Allocator + Sync, { type Item = &'a T; @@ -118,7 +118,7 @@ where /// /// [`par_symmetric_difference`]: /hashbrown/struct.HashSet.html#method.par_symmetric_difference /// [`HashSet`]: /hashbrown/struct.HashSet.html -pub struct ParSymmetricDifference<'a, T, S, A: Allocator + Clone = Global> { +pub struct ParSymmetricDifference<'a, T, S, A: Allocator = Global> { a: &'a HashSet<T, S, A>, b: &'a HashSet<T, S, A>, } @@ -127,7 +127,7 @@ impl<'a, T, S, A> ParallelIterator for ParSymmetricDifference<'a, T, S, A> where T: Eq + Hash + Sync, S: BuildHasher + Sync, - A: Allocator + Clone + Sync, + A: Allocator + Sync, { type Item = &'a T; @@ -150,7 +150,7 @@ where /// /// [`par_intersection`]: /hashbrown/struct.HashSet.html#method.par_intersection /// [`HashSet`]: /hashbrown/struct.HashSet.html -pub struct ParIntersection<'a, T, S, A: Allocator + Clone = Global> { +pub struct ParIntersection<'a, T, S, A: Allocator = Global> { a: &'a HashSet<T, S, A>, b: &'a HashSet<T, S, A>, } @@ -159,7 +159,7 @@ impl<'a, T, S, A> ParallelIterator for ParIntersection<'a, T, S, A> where T: Eq + Hash + Sync, S: BuildHasher + Sync, - A: Allocator + Clone + Sync, + A: Allocator + Sync, { type Item = &'a T; @@ -181,7 +181,7 @@ where /// /// [`par_union`]: /hashbrown/struct.HashSet.html#method.par_union /// [`HashSet`]: /hashbrown/struct.HashSet.html -pub struct ParUnion<'a, T, S, A: Allocator + Clone = Global> { +pub struct ParUnion<'a, T, S, A: Allocator = Global> { a: &'a HashSet<T, S, A>, b: &'a HashSet<T, S, A>, } @@ -190,7 +190,7 @@ impl<'a, T, S, A> ParallelIterator for ParUnion<'a, T, S, A> where T: Eq + Hash + Sync, S: BuildHasher + Sync, - A: Allocator + Clone + Sync, + A: Allocator + Sync, { type Item = &'a T; @@ -216,7 +216,7 @@ impl<T, S, A> HashSet<T, S, A> where T: Eq + Hash + Sync, S: BuildHasher + Sync, - A: Allocator + Clone + Sync, + A: Allocator + Sync, { /// Visits (potentially in parallel) the values representing the union, /// i.e. all the values in `self` or `other`, without duplicates. @@ -289,7 +289,7 @@ where impl<T, S, A> HashSet<T, S, A> where T: Eq + Hash + Send, - A: Allocator + Clone + Send, + A: Allocator + Send, { /// Consumes (potentially in parallel) all values in an arbitrary order, /// while preserving the set's allocated memory for reuse. @@ -301,7 +301,7 @@ where } } -impl<T: Send, S, A: Allocator + Clone + Send> IntoParallelIterator for HashSet<T, S, A> { +impl<T: Send, S, A: Allocator + Send> IntoParallelIterator for HashSet<T, S, A> { type Item = T; type Iter = IntoParIter<T, A>; @@ -313,7 +313,7 @@ impl<T: Send, S, A: Allocator + Clone + Send> IntoParallelIterator for HashSet<T } } -impl<'a, T: Sync, S, A: Allocator + Clone> IntoParallelIterator for &'a HashSet<T, S, A> { +impl<'a, T: Sync, S, A: Allocator> IntoParallelIterator for &'a HashSet<T, S, A> { type Item = &'a T; type Iter = ParIter<'a, T>; @@ -374,7 +374,7 @@ fn extend<T, S, I, A>(set: &mut HashSet<T, S, A>, par_iter: I) where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, I: IntoParallelIterator, HashSet<T, S, A>: Extend<I::Item>, { diff --git a/third_party/rust/hashbrown/src/external_trait_impls/rayon/table.rs b/third_party/rust/hashbrown/src/external_trait_impls/rayon/table.rs new file mode 100644 index 0000000000..e8e50944ad --- /dev/null +++ b/third_party/rust/hashbrown/src/external_trait_impls/rayon/table.rs @@ -0,0 +1,252 @@ +//! Rayon extensions for `HashTable`. + +use super::raw::{RawIntoParIter, RawParDrain, RawParIter}; +use crate::hash_table::HashTable; +use crate::raw::{Allocator, Global}; +use core::fmt; +use core::marker::PhantomData; +use rayon::iter::plumbing::UnindexedConsumer; +use rayon::iter::{IntoParallelIterator, ParallelIterator}; + +/// Parallel iterator over shared references to entries in a map. +/// +/// This iterator is created by the [`par_iter`] method on [`HashTable`] +/// (provided by the [`IntoParallelRefIterator`] trait). +/// See its documentation for more. +/// +/// [`par_iter`]: /hashbrown/struct.HashTable.html#method.par_iter +/// [`HashTable`]: /hashbrown/struct.HashTable.html +/// [`IntoParallelRefIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelRefIterator.html +pub struct ParIter<'a, T> { + inner: RawParIter<T>, + marker: PhantomData<&'a T>, +} + +impl<'a, T: Sync> ParallelIterator for ParIter<'a, T> { + type Item = &'a T; + + #[cfg_attr(feature = "inline-more", inline)] + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.inner + .map(|x| unsafe { x.as_ref() }) + .drive_unindexed(consumer) + } +} + +impl<T> Clone for ParIter<'_, T> { + #[cfg_attr(feature = "inline-more", inline)] + fn clone(&self) -> Self { + Self { + inner: self.inner.clone(), + marker: PhantomData, + } + } +} + +impl<T: fmt::Debug> fmt::Debug for ParIter<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = unsafe { self.inner.iter() }.map(|x| unsafe { x.as_ref() }); + f.debug_list().entries(iter).finish() + } +} + +/// Parallel iterator over mutable references to entries in a map. +/// +/// This iterator is created by the [`par_iter_mut`] method on [`HashTable`] +/// (provided by the [`IntoParallelRefMutIterator`] trait). +/// See its documentation for more. +/// +/// [`par_iter_mut`]: /hashbrown/struct.HashTable.html#method.par_iter_mut +/// [`HashTable`]: /hashbrown/struct.HashTable.html +/// [`IntoParallelRefMutIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelRefMutIterator.html +pub struct ParIterMut<'a, T> { + inner: RawParIter<T>, + marker: PhantomData<&'a mut T>, +} + +impl<'a, T: Send> ParallelIterator for ParIterMut<'a, T> { + type Item = &'a mut T; + + #[cfg_attr(feature = "inline-more", inline)] + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.inner + .map(|x| unsafe { x.as_mut() }) + .drive_unindexed(consumer) + } +} + +impl<T: fmt::Debug> fmt::Debug for ParIterMut<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + ParIter { + inner: self.inner.clone(), + marker: PhantomData, + } + .fmt(f) + } +} + +/// Parallel iterator over entries of a consumed map. +/// +/// This iterator is created by the [`into_par_iter`] method on [`HashTable`] +/// (provided by the [`IntoParallelIterator`] trait). +/// See its documentation for more. +/// +/// [`into_par_iter`]: /hashbrown/struct.HashTable.html#method.into_par_iter +/// [`HashTable`]: /hashbrown/struct.HashTable.html +/// [`IntoParallelIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelIterator.html +pub struct IntoParIter<T, A: Allocator = Global> { + inner: RawIntoParIter<T, A>, +} + +impl<T: Send, A: Allocator + Send> ParallelIterator for IntoParIter<T, A> { + type Item = T; + + #[cfg_attr(feature = "inline-more", inline)] + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.inner.drive_unindexed(consumer) + } +} + +impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoParIter<T, A> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + ParIter { + inner: unsafe { self.inner.par_iter() }, + marker: PhantomData, + } + .fmt(f) + } +} + +/// Parallel draining iterator over entries of a map. +/// +/// This iterator is created by the [`par_drain`] method on [`HashTable`]. +/// See its documentation for more. +/// +/// [`par_drain`]: /hashbrown/struct.HashTable.html#method.par_drain +/// [`HashTable`]: /hashbrown/struct.HashTable.html +pub struct ParDrain<'a, T, A: Allocator = Global> { + inner: RawParDrain<'a, T, A>, +} + +impl<T: Send, A: Allocator + Sync> ParallelIterator for ParDrain<'_, T, A> { + type Item = T; + + #[cfg_attr(feature = "inline-more", inline)] + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.inner.drive_unindexed(consumer) + } +} + +impl<T: fmt::Debug, A: Allocator> fmt::Debug for ParDrain<'_, T, A> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + ParIter { + inner: unsafe { self.inner.par_iter() }, + marker: PhantomData, + } + .fmt(f) + } +} + +impl<T: Send, A: Allocator> HashTable<T, A> { + /// Consumes (potentially in parallel) all values in an arbitrary order, + /// while preserving the map's allocated memory for reuse. + #[cfg_attr(feature = "inline-more", inline)] + pub fn par_drain(&mut self) -> ParDrain<'_, T, A> { + ParDrain { + inner: self.raw.par_drain(), + } + } +} + +impl<T: Send, A: Allocator + Send> IntoParallelIterator for HashTable<T, A> { + type Item = T; + type Iter = IntoParIter<T, A>; + + #[cfg_attr(feature = "inline-more", inline)] + fn into_par_iter(self) -> Self::Iter { + IntoParIter { + inner: self.raw.into_par_iter(), + } + } +} + +impl<'a, T: Sync, A: Allocator> IntoParallelIterator for &'a HashTable<T, A> { + type Item = &'a T; + type Iter = ParIter<'a, T>; + + #[cfg_attr(feature = "inline-more", inline)] + fn into_par_iter(self) -> Self::Iter { + ParIter { + inner: unsafe { self.raw.par_iter() }, + marker: PhantomData, + } + } +} + +impl<'a, T: Send, A: Allocator> IntoParallelIterator for &'a mut HashTable<T, A> { + type Item = &'a mut T; + type Iter = ParIterMut<'a, T>; + + #[cfg_attr(feature = "inline-more", inline)] + fn into_par_iter(self) -> Self::Iter { + ParIterMut { + inner: unsafe { self.raw.par_iter() }, + marker: PhantomData, + } + } +} + +#[cfg(test)] +mod test_par_table { + use alloc::vec::Vec; + use core::sync::atomic::{AtomicUsize, Ordering}; + + use rayon::prelude::*; + + use crate::{ + hash_map::{make_hash, DefaultHashBuilder}, + hash_table::HashTable, + }; + + #[test] + fn test_iterate() { + let hasher = DefaultHashBuilder::default(); + let mut a = HashTable::new(); + for i in 0..32 { + a.insert_unique(make_hash(&hasher, &i), i, |x| make_hash(&hasher, x)); + } + let observed = AtomicUsize::new(0); + a.par_iter().for_each(|k| { + observed.fetch_or(1 << *k, Ordering::Relaxed); + }); + assert_eq!(observed.into_inner(), 0xFFFF_FFFF); + } + + #[test] + fn test_move_iter() { + let hasher = DefaultHashBuilder::default(); + let hs = { + let mut hs = HashTable::new(); + + hs.insert_unique(make_hash(&hasher, &'a'), 'a', |x| make_hash(&hasher, x)); + hs.insert_unique(make_hash(&hasher, &'b'), 'b', |x| make_hash(&hasher, x)); + + hs + }; + + let v = hs.into_par_iter().collect::<Vec<char>>(); + assert!(v == ['a', 'b'] || v == ['b', 'a']); + } +} |