diff options
Diffstat (limited to 'third_party/rust/hashbrown/src/external_trait_impls')
10 files changed, 591 insertions, 81 deletions
diff --git a/third_party/rust/hashbrown/src/external_trait_impls/mod.rs b/third_party/rust/hashbrown/src/external_trait_impls/mod.rs index ef497836cb..01d386b046 100644 --- a/third_party/rust/hashbrown/src/external_trait_impls/mod.rs +++ b/third_party/rust/hashbrown/src/external_trait_impls/mod.rs @@ -1,4 +1,6 @@ #[cfg(feature = "rayon")] pub(crate) mod rayon; +#[cfg(feature = "rkyv")] +mod rkyv; #[cfg(feature = "serde")] mod serde; 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']); + } +} diff --git a/third_party/rust/hashbrown/src/external_trait_impls/rkyv/hash_map.rs b/third_party/rust/hashbrown/src/external_trait_impls/rkyv/hash_map.rs new file mode 100644 index 0000000000..fae7f76763 --- /dev/null +++ b/third_party/rust/hashbrown/src/external_trait_impls/rkyv/hash_map.rs @@ -0,0 +1,125 @@ +use crate::HashMap; +use core::{ + borrow::Borrow, + hash::{BuildHasher, Hash}, +}; +use rkyv::{ + collections::hash_map::{ArchivedHashMap, HashMapResolver}, + ser::{ScratchSpace, Serializer}, + Archive, Deserialize, Fallible, Serialize, +}; + +impl<K: Archive + Hash + Eq, V: Archive, S> Archive for HashMap<K, V, S> +where + K::Archived: Hash + Eq, +{ + type Archived = ArchivedHashMap<K::Archived, V::Archived>; + type Resolver = HashMapResolver; + + #[inline] + unsafe fn resolve(&self, pos: usize, resolver: Self::Resolver, out: *mut Self::Archived) { + ArchivedHashMap::resolve_from_len(self.len(), pos, resolver, out); + } +} + +impl<K, V, S, RandomState> Serialize<S> for HashMap<K, V, RandomState> +where + K: Serialize<S> + Hash + Eq, + K::Archived: Hash + Eq, + V: Serialize<S>, + S: Serializer + ScratchSpace + ?Sized, +{ + #[inline] + fn serialize(&self, serializer: &mut S) -> Result<Self::Resolver, S::Error> { + unsafe { ArchivedHashMap::serialize_from_iter(self.iter(), serializer) } + } +} + +impl<K: Archive + Hash + Eq, V: Archive, D: Fallible + ?Sized, S: Default + BuildHasher> + Deserialize<HashMap<K, V, S>, D> for ArchivedHashMap<K::Archived, V::Archived> +where + K::Archived: Deserialize<K, D> + Hash + Eq, + V::Archived: Deserialize<V, D>, +{ + #[inline] + fn deserialize(&self, deserializer: &mut D) -> Result<HashMap<K, V, S>, D::Error> { + let mut result = HashMap::with_capacity_and_hasher(self.len(), S::default()); + for (k, v) in self.iter() { + result.insert(k.deserialize(deserializer)?, v.deserialize(deserializer)?); + } + Ok(result) + } +} + +impl<K: Hash + Eq + Borrow<AK>, V, AK: Hash + Eq, AV: PartialEq<V>, S: BuildHasher> + PartialEq<HashMap<K, V, S>> for ArchivedHashMap<AK, AV> +{ + #[inline] + fn eq(&self, other: &HashMap<K, V, S>) -> bool { + if self.len() != other.len() { + false + } else { + self.iter() + .all(|(key, value)| other.get(key).map_or(false, |v| value.eq(v))) + } + } +} + +impl<K: Hash + Eq + Borrow<AK>, V, AK: Hash + Eq, AV: PartialEq<V>> + PartialEq<ArchivedHashMap<AK, AV>> for HashMap<K, V> +{ + #[inline] + fn eq(&self, other: &ArchivedHashMap<AK, AV>) -> bool { + other.eq(self) + } +} + +#[cfg(test)] +mod tests { + use crate::HashMap; + use alloc::string::String; + use rkyv::{ + archived_root, check_archived_root, + ser::{serializers::AllocSerializer, Serializer}, + Deserialize, Infallible, + }; + + #[test] + fn index_map() { + let mut value = HashMap::new(); + value.insert(String::from("foo"), 10); + value.insert(String::from("bar"), 20); + value.insert(String::from("baz"), 40); + value.insert(String::from("bat"), 80); + + let mut serializer = AllocSerializer::<4096>::default(); + serializer.serialize_value(&value).unwrap(); + let result = serializer.into_serializer().into_inner(); + let archived = unsafe { archived_root::<HashMap<String, i32>>(result.as_ref()) }; + + assert_eq!(value.len(), archived.len()); + for (k, v) in value.iter() { + let (ak, av) = archived.get_key_value(k.as_str()).unwrap(); + assert_eq!(k, ak); + assert_eq!(v, av); + } + + let deserialized: HashMap<String, i32> = archived.deserialize(&mut Infallible).unwrap(); + assert_eq!(value, deserialized); + } + + #[test] + fn validate_index_map() { + let mut value = HashMap::new(); + value.insert(String::from("foo"), 10); + value.insert(String::from("bar"), 20); + value.insert(String::from("baz"), 40); + value.insert(String::from("bat"), 80); + + let mut serializer = AllocSerializer::<4096>::default(); + serializer.serialize_value(&value).unwrap(); + let result = serializer.into_serializer().into_inner(); + check_archived_root::<HashMap<String, i32>>(result.as_ref()) + .expect("failed to validate archived index map"); + } +} diff --git a/third_party/rust/hashbrown/src/external_trait_impls/rkyv/hash_set.rs b/third_party/rust/hashbrown/src/external_trait_impls/rkyv/hash_set.rs new file mode 100644 index 0000000000..c8a69cf4fc --- /dev/null +++ b/third_party/rust/hashbrown/src/external_trait_impls/rkyv/hash_set.rs @@ -0,0 +1,123 @@ +use crate::HashSet; +use core::{ + borrow::Borrow, + hash::{BuildHasher, Hash}, +}; +use rkyv::{ + collections::hash_set::{ArchivedHashSet, HashSetResolver}, + ser::{ScratchSpace, Serializer}, + Archive, Deserialize, Fallible, Serialize, +}; + +impl<K: Archive + Hash + Eq, S> Archive for HashSet<K, S> +where + K::Archived: Hash + Eq, +{ + type Archived = ArchivedHashSet<K::Archived>; + type Resolver = HashSetResolver; + + #[inline] + unsafe fn resolve(&self, pos: usize, resolver: Self::Resolver, out: *mut Self::Archived) { + ArchivedHashSet::<K::Archived>::resolve_from_len(self.len(), pos, resolver, out); + } +} + +impl<K, S, RS> Serialize<S> for HashSet<K, RS> +where + K::Archived: Hash + Eq, + K: Serialize<S> + Hash + Eq, + S: ScratchSpace + Serializer + ?Sized, +{ + #[inline] + fn serialize(&self, serializer: &mut S) -> Result<Self::Resolver, S::Error> { + unsafe { ArchivedHashSet::serialize_from_iter(self.iter(), serializer) } + } +} + +impl<K, D, S> Deserialize<HashSet<K, S>, D> for ArchivedHashSet<K::Archived> +where + K: Archive + Hash + Eq, + K::Archived: Deserialize<K, D> + Hash + Eq, + D: Fallible + ?Sized, + S: Default + BuildHasher, +{ + #[inline] + fn deserialize(&self, deserializer: &mut D) -> Result<HashSet<K, S>, D::Error> { + let mut result = HashSet::with_hasher(S::default()); + for k in self.iter() { + result.insert(k.deserialize(deserializer)?); + } + Ok(result) + } +} + +impl<K: Hash + Eq + Borrow<AK>, AK: Hash + Eq, S: BuildHasher> PartialEq<HashSet<K, S>> + for ArchivedHashSet<AK> +{ + #[inline] + fn eq(&self, other: &HashSet<K, S>) -> bool { + if self.len() != other.len() { + false + } else { + self.iter().all(|key| other.get(key).is_some()) + } + } +} + +impl<K: Hash + Eq + Borrow<AK>, AK: Hash + Eq, S: BuildHasher> PartialEq<ArchivedHashSet<AK>> + for HashSet<K, S> +{ + #[inline] + fn eq(&self, other: &ArchivedHashSet<AK>) -> bool { + other.eq(self) + } +} + +#[cfg(test)] +mod tests { + use crate::HashSet; + use alloc::string::String; + use rkyv::{ + archived_root, check_archived_root, + ser::{serializers::AllocSerializer, Serializer}, + Deserialize, Infallible, + }; + + #[test] + fn index_set() { + let mut value = HashSet::new(); + value.insert(String::from("foo")); + value.insert(String::from("bar")); + value.insert(String::from("baz")); + value.insert(String::from("bat")); + + let mut serializer = AllocSerializer::<4096>::default(); + serializer.serialize_value(&value).unwrap(); + let result = serializer.into_serializer().into_inner(); + let archived = unsafe { archived_root::<HashSet<String>>(result.as_ref()) }; + + assert_eq!(value.len(), archived.len()); + for k in value.iter() { + let ak = archived.get(k.as_str()).unwrap(); + assert_eq!(k, ak); + } + + let deserialized: HashSet<String> = archived.deserialize(&mut Infallible).unwrap(); + assert_eq!(value, deserialized); + } + + #[test] + fn validate_index_set() { + let mut value = HashSet::new(); + value.insert(String::from("foo")); + value.insert(String::from("bar")); + value.insert(String::from("baz")); + value.insert(String::from("bat")); + + let mut serializer = AllocSerializer::<4096>::default(); + serializer.serialize_value(&value).unwrap(); + let result = serializer.into_serializer().into_inner(); + check_archived_root::<HashSet<String>>(result.as_ref()) + .expect("failed to validate archived index set"); + } +} diff --git a/third_party/rust/hashbrown/src/external_trait_impls/rkyv/mod.rs b/third_party/rust/hashbrown/src/external_trait_impls/rkyv/mod.rs new file mode 100644 index 0000000000..2bde6a0653 --- /dev/null +++ b/third_party/rust/hashbrown/src/external_trait_impls/rkyv/mod.rs @@ -0,0 +1,2 @@ +mod hash_map; +mod hash_set; diff --git a/third_party/rust/hashbrown/src/external_trait_impls/serde.rs b/third_party/rust/hashbrown/src/external_trait_impls/serde.rs index 4d62deeb7a..0a76dbec25 100644 --- a/third_party/rust/hashbrown/src/external_trait_impls/serde.rs +++ b/third_party/rust/hashbrown/src/external_trait_impls/serde.rs @@ -11,6 +11,7 @@ mod size_hint { } mod map { + use crate::raw::Allocator; use core::fmt; use core::hash::{BuildHasher, Hash}; use core::marker::PhantomData; @@ -21,11 +22,12 @@ mod map { use super::size_hint; - impl<K, V, H> Serialize for HashMap<K, V, H> + impl<K, V, H, A> Serialize for HashMap<K, V, H, A> where K: Serialize + Eq + Hash, V: Serialize, H: BuildHasher, + A: Allocator, { #[cfg_attr(feature = "inline-more", inline)] fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> @@ -36,40 +38,46 @@ mod map { } } - impl<'de, K, V, S> Deserialize<'de> for HashMap<K, V, S> + impl<'de, K, V, S, A> Deserialize<'de> for HashMap<K, V, S, A> where K: Deserialize<'de> + Eq + Hash, V: Deserialize<'de>, S: BuildHasher + Default, + A: Allocator + Default, { fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'de>, { - struct MapVisitor<K, V, S> { - marker: PhantomData<HashMap<K, V, S>>, + struct MapVisitor<K, V, S, A> + where + A: Allocator, + { + marker: PhantomData<HashMap<K, V, S, A>>, } - impl<'de, K, V, S> Visitor<'de> for MapVisitor<K, V, S> + impl<'de, K, V, S, A> Visitor<'de> for MapVisitor<K, V, S, A> where K: Deserialize<'de> + Eq + Hash, V: Deserialize<'de>, S: BuildHasher + Default, + A: Allocator + Default, { - type Value = HashMap<K, V, S>; + type Value = HashMap<K, V, S, A>; fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result { formatter.write_str("a map") } #[cfg_attr(feature = "inline-more", inline)] - fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error> + fn visit_map<M>(self, mut map: M) -> Result<Self::Value, M::Error> where - A: MapAccess<'de>, + M: MapAccess<'de>, { - let mut values = HashMap::with_capacity_and_hasher( + let mut values = HashMap::with_capacity_and_hasher_in( size_hint::cautious(map.size_hint()), S::default(), + A::default(), ); while let Some((key, value)) = map.next_entry()? { @@ -89,6 +97,7 @@ mod map { } mod set { + use crate::raw::Allocator; use core::fmt; use core::hash::{BuildHasher, Hash}; use core::marker::PhantomData; @@ -99,10 +108,11 @@ mod set { use super::size_hint; - impl<T, H> Serialize for HashSet<T, H> + impl<T, H, A> Serialize for HashSet<T, H, A> where T: Serialize + Eq + Hash, H: BuildHasher, + A: Allocator, { #[cfg_attr(feature = "inline-more", inline)] fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> @@ -113,38 +123,44 @@ mod set { } } - impl<'de, T, S> Deserialize<'de> for HashSet<T, S> + impl<'de, T, S, A> Deserialize<'de> for HashSet<T, S, A> where T: Deserialize<'de> + Eq + Hash, S: BuildHasher + Default, + A: Allocator + Default, { fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'de>, { - struct SeqVisitor<T, S> { - marker: PhantomData<HashSet<T, S>>, + struct SeqVisitor<T, S, A> + where + A: Allocator, + { + marker: PhantomData<HashSet<T, S, A>>, } - impl<'de, T, S> Visitor<'de> for SeqVisitor<T, S> + impl<'de, T, S, A> Visitor<'de> for SeqVisitor<T, S, A> where T: Deserialize<'de> + Eq + Hash, S: BuildHasher + Default, + A: Allocator + Default, { - type Value = HashSet<T, S>; + type Value = HashSet<T, S, A>; fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result { formatter.write_str("a sequence") } #[cfg_attr(feature = "inline-more", inline)] - fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error> + fn visit_seq<M>(self, mut seq: M) -> Result<Self::Value, M::Error> where - A: SeqAccess<'de>, + M: SeqAccess<'de>, { - let mut values = HashSet::with_capacity_and_hasher( + let mut values = HashSet::with_capacity_and_hasher_in( size_hint::cautious(seq.size_hint()), S::default(), + A::default(), ); while let Some(value) = seq.next_element()? { @@ -166,12 +182,15 @@ mod set { where D: Deserializer<'de>, { - struct SeqInPlaceVisitor<'a, T, S>(&'a mut HashSet<T, S>); + struct SeqInPlaceVisitor<'a, T, S, A>(&'a mut HashSet<T, S, A>) + where + A: Allocator; - impl<'a, 'de, T, S> Visitor<'de> for SeqInPlaceVisitor<'a, T, S> + impl<'a, 'de, T, S, A> Visitor<'de> for SeqInPlaceVisitor<'a, T, S, A> where T: Deserialize<'de> + Eq + Hash, S: BuildHasher + Default, + A: Allocator, { type Value = (); @@ -180,9 +199,9 @@ mod set { } #[cfg_attr(feature = "inline-more", inline)] - fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error> + fn visit_seq<M>(self, mut seq: M) -> Result<Self::Value, M::Error> where - A: SeqAccess<'de>, + M: SeqAccess<'de>, { self.0.clear(); self.0.reserve(size_hint::cautious(seq.size_hint())); |