diff options
Diffstat (limited to 'vendor/hashbrown-0.12.3/src/external_trait_impls')
7 files changed, 1860 insertions, 0 deletions
diff --git a/vendor/hashbrown-0.12.3/src/external_trait_impls/mod.rs b/vendor/hashbrown-0.12.3/src/external_trait_impls/mod.rs new file mode 100644 index 000000000..ef497836c --- /dev/null +++ b/vendor/hashbrown-0.12.3/src/external_trait_impls/mod.rs @@ -0,0 +1,4 @@ +#[cfg(feature = "rayon")] +pub(crate) mod rayon; +#[cfg(feature = "serde")] +mod serde; diff --git a/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/helpers.rs b/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/helpers.rs new file mode 100644 index 000000000..070b08cd5 --- /dev/null +++ b/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/helpers.rs @@ -0,0 +1,27 @@ +use alloc::collections::LinkedList; +use alloc::vec::Vec; + +use rayon::iter::{IntoParallelIterator, ParallelIterator}; + +/// Helper for collecting parallel iterators to an intermediary +#[allow(clippy::linkedlist)] // yes, we need linked list here for efficient appending! +pub(super) fn collect<I: IntoParallelIterator>(iter: I) -> (LinkedList<Vec<I::Item>>, usize) { + let list = iter + .into_par_iter() + .fold(Vec::new, |mut vec, elem| { + vec.push(elem); + vec + }) + .map(|vec| { + let mut list = LinkedList::new(); + list.push_back(vec); + list + }) + .reduce(LinkedList::new, |mut list1, mut list2| { + list1.append(&mut list2); + list1 + }); + + let len = list.iter().map(Vec::len).sum(); + (list, len) +} diff --git a/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/map.rs b/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/map.rs new file mode 100644 index 000000000..14d91c220 --- /dev/null +++ b/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/map.rs @@ -0,0 +1,734 @@ +//! Rayon extensions for `HashMap`. + +use super::raw::{RawIntoParIter, RawParDrain, RawParIter}; +use crate::hash_map::HashMap; +use crate::raw::{Allocator, Global}; +use core::fmt; +use core::hash::{BuildHasher, Hash}; +use core::marker::PhantomData; +use rayon::iter::plumbing::UnindexedConsumer; +use rayon::iter::{FromParallelIterator, IntoParallelIterator, ParallelExtend, ParallelIterator}; + +/// Parallel iterator over shared references to entries in a map. +/// +/// This iterator is created by the [`par_iter`] method on [`HashMap`] +/// (provided by the [`IntoParallelRefIterator`] trait). +/// See its documentation for more. +/// +/// [`par_iter`]: /hashbrown/struct.HashMap.html#method.par_iter +/// [`HashMap`]: /hashbrown/struct.HashMap.html +/// [`IntoParallelRefIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelRefIterator.html +pub struct ParIter<'a, K, V> { + inner: RawParIter<(K, V)>, + marker: PhantomData<(&'a K, &'a V)>, +} + +impl<'a, K: Sync, V: Sync> ParallelIterator for ParIter<'a, K, V> { + type Item = (&'a K, &'a V); + + #[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 { + let r = x.as_ref(); + (&r.0, &r.1) + }) + .drive_unindexed(consumer) + } +} + +impl<K, V> Clone for ParIter<'_, K, V> { + #[cfg_attr(feature = "inline-more", inline)] + fn clone(&self) -> Self { + Self { + inner: self.inner.clone(), + marker: PhantomData, + } + } +} + +impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug> fmt::Debug for ParIter<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = unsafe { self.inner.iter() }.map(|x| unsafe { + let r = x.as_ref(); + (&r.0, &r.1) + }); + f.debug_list().entries(iter).finish() + } +} + +/// Parallel iterator over shared references to keys in a map. +/// +/// This iterator is created by the [`par_keys`] method on [`HashMap`]. +/// See its documentation for more. +/// +/// [`par_keys`]: /hashbrown/struct.HashMap.html#method.par_keys +/// [`HashMap`]: /hashbrown/struct.HashMap.html +pub struct ParKeys<'a, K, V> { + inner: RawParIter<(K, V)>, + marker: PhantomData<(&'a K, &'a V)>, +} + +impl<'a, K: Sync, V: Sync> ParallelIterator for ParKeys<'a, K, V> { + type Item = &'a K; + + #[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().0 }) + .drive_unindexed(consumer) + } +} + +impl<K, V> Clone for ParKeys<'_, K, V> { + #[cfg_attr(feature = "inline-more", inline)] + fn clone(&self) -> Self { + Self { + inner: self.inner.clone(), + marker: PhantomData, + } + } +} + +impl<K: fmt::Debug + Eq + Hash, V> fmt::Debug for ParKeys<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = unsafe { self.inner.iter() }.map(|x| unsafe { &x.as_ref().0 }); + f.debug_list().entries(iter).finish() + } +} + +/// Parallel iterator over shared references to values in a map. +/// +/// This iterator is created by the [`par_values`] method on [`HashMap`]. +/// See its documentation for more. +/// +/// [`par_values`]: /hashbrown/struct.HashMap.html#method.par_values +/// [`HashMap`]: /hashbrown/struct.HashMap.html +pub struct ParValues<'a, K, V> { + inner: RawParIter<(K, V)>, + marker: PhantomData<(&'a K, &'a V)>, +} + +impl<'a, K: Sync, V: Sync> ParallelIterator for ParValues<'a, K, V> { + type Item = &'a V; + + #[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().1 }) + .drive_unindexed(consumer) + } +} + +impl<K, V> Clone for ParValues<'_, K, V> { + #[cfg_attr(feature = "inline-more", inline)] + fn clone(&self) -> Self { + Self { + inner: self.inner.clone(), + marker: PhantomData, + } + } +} + +impl<K: Eq + Hash, V: fmt::Debug> fmt::Debug for ParValues<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let iter = unsafe { self.inner.iter() }.map(|x| unsafe { &x.as_ref().1 }); + 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 [`HashMap`] +/// (provided by the [`IntoParallelRefMutIterator`] trait). +/// See its documentation for more. +/// +/// [`par_iter_mut`]: /hashbrown/struct.HashMap.html#method.par_iter_mut +/// [`HashMap`]: /hashbrown/struct.HashMap.html +/// [`IntoParallelRefMutIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelRefMutIterator.html +pub struct ParIterMut<'a, K, V> { + inner: RawParIter<(K, V)>, + marker: PhantomData<(&'a K, &'a mut V)>, +} + +impl<'a, K: Sync, V: Send> ParallelIterator for ParIterMut<'a, K, V> { + type Item = (&'a K, &'a mut V); + + #[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 { + let r = x.as_mut(); + (&r.0, &mut r.1) + }) + .drive_unindexed(consumer) + } +} + +impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug> fmt::Debug for ParIterMut<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + ParIter { + inner: self.inner.clone(), + marker: PhantomData, + } + .fmt(f) + } +} + +/// Parallel iterator over mutable references to values in a map. +/// +/// This iterator is created by the [`par_values_mut`] method on [`HashMap`]. +/// See its documentation for more. +/// +/// [`par_values_mut`]: /hashbrown/struct.HashMap.html#method.par_values_mut +/// [`HashMap`]: /hashbrown/struct.HashMap.html +pub struct ParValuesMut<'a, K, V> { + inner: RawParIter<(K, V)>, + marker: PhantomData<(&'a K, &'a mut V)>, +} + +impl<'a, K: Sync, V: Send> ParallelIterator for ParValuesMut<'a, K, V> { + type Item = &'a mut V; + + #[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 { &mut x.as_mut().1 }) + .drive_unindexed(consumer) + } +} + +impl<K: Eq + Hash, V: fmt::Debug> fmt::Debug for ParValuesMut<'_, K, V> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + ParValues { + 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 [`HashMap`] +/// (provided by the [`IntoParallelIterator`] trait). +/// See its documentation for more. +/// +/// [`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> { + inner: RawIntoParIter<(K, V), A>, +} + +impl<K: Send, V: Send, A: Allocator + Clone + Send> ParallelIterator for IntoParIter<K, V, A> { + type Item = (K, V); + + #[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<K: fmt::Debug + Eq + Hash, V: fmt::Debug, A: Allocator + Clone> fmt::Debug + for IntoParIter<K, V, 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 [`HashMap`]. +/// See its documentation for more. +/// +/// [`par_drain`]: /hashbrown/struct.HashMap.html#method.par_drain +/// [`HashMap`]: /hashbrown/struct.HashMap.html +pub struct ParDrain<'a, K, V, A: Allocator + Clone = Global> { + inner: RawParDrain<'a, (K, V), A>, +} + +impl<K: Send, V: Send, A: Allocator + Clone + Sync> ParallelIterator for ParDrain<'_, K, V, A> { + type Item = (K, V); + + #[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<K: fmt::Debug + Eq + Hash, V: fmt::Debug, A: Allocator + Clone> fmt::Debug + for ParDrain<'_, K, V, A> +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + ParIter { + inner: unsafe { self.inner.par_iter() }, + marker: PhantomData, + } + .fmt(f) + } +} + +impl<K: Sync, V: Sync, S, A: Allocator + Clone> 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> { + ParKeys { + inner: unsafe { self.table.par_iter() }, + marker: PhantomData, + } + } + + /// Visits (potentially in parallel) immutably borrowed values in an arbitrary order. + #[cfg_attr(feature = "inline-more", inline)] + pub fn par_values(&self) -> ParValues<'_, K, V> { + ParValues { + inner: unsafe { self.table.par_iter() }, + marker: PhantomData, + } + } +} + +impl<K: Send, V: Send, S, A: Allocator + Clone> 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> { + ParValuesMut { + inner: unsafe { self.table.par_iter() }, + marker: PhantomData, + } + } + + /// 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<'_, K, V, A> { + ParDrain { + inner: self.table.par_drain(), + } + } +} + +impl<K, V, S, A> HashMap<K, V, S, A> +where + K: Eq + Hash + Sync, + V: PartialEq + Sync, + S: BuildHasher + Sync, + A: Allocator + Clone + Sync, +{ + /// Returns `true` if the map is equal to another, + /// i.e. both maps contain the same keys mapped to the same values. + /// + /// This method runs in a potentially parallel fashion. + pub fn par_eq(&self, other: &Self) -> bool { + self.len() == other.len() + && self + .into_par_iter() + .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v)) + } +} + +impl<K: Send, V: Send, S, A: Allocator + Clone + Send> IntoParallelIterator + for HashMap<K, V, S, A> +{ + type Item = (K, V); + type Iter = IntoParIter<K, V, A>; + + #[cfg_attr(feature = "inline-more", inline)] + fn into_par_iter(self) -> Self::Iter { + IntoParIter { + inner: self.table.into_par_iter(), + } + } +} + +impl<'a, K: Sync, V: Sync, S, A: Allocator + Clone> IntoParallelIterator + for &'a HashMap<K, V, S, A> +{ + type Item = (&'a K, &'a V); + type Iter = ParIter<'a, K, V>; + + #[cfg_attr(feature = "inline-more", inline)] + fn into_par_iter(self) -> Self::Iter { + ParIter { + inner: unsafe { self.table.par_iter() }, + marker: PhantomData, + } + } +} + +impl<'a, K: Sync, V: Send, S, A: Allocator + Clone> IntoParallelIterator + for &'a mut HashMap<K, V, S, A> +{ + type Item = (&'a K, &'a mut V); + type Iter = ParIterMut<'a, K, V>; + + #[cfg_attr(feature = "inline-more", inline)] + fn into_par_iter(self) -> Self::Iter { + ParIterMut { + inner: unsafe { self.table.par_iter() }, + marker: PhantomData, + } + } +} + +/// Collect (key, value) pairs from a parallel iterator into a +/// hashmap. If multiple pairs correspond to the same key, then the +/// ones produced earlier in the parallel iterator will be +/// overwritten, just as with a sequential iterator. +impl<K, V, S> FromParallelIterator<(K, V)> for HashMap<K, V, S, Global> +where + K: Eq + Hash + Send, + V: Send, + S: BuildHasher + Default, +{ + fn from_par_iter<P>(par_iter: P) -> Self + where + P: IntoParallelIterator<Item = (K, V)>, + { + let mut map = HashMap::default(); + map.par_extend(par_iter); + map + } +} + +/// Extend a hash map with items from a parallel iterator. +impl<K, V, S, A> ParallelExtend<(K, V)> for HashMap<K, V, S, A> +where + K: Eq + Hash + Send, + V: Send, + S: BuildHasher, + A: Allocator + Clone, +{ + fn par_extend<I>(&mut self, par_iter: I) + where + I: IntoParallelIterator<Item = (K, V)>, + { + extend(self, par_iter); + } +} + +/// Extend a hash map with copied items from a parallel iterator. +impl<'a, K, V, S, A> ParallelExtend<(&'a K, &'a V)> for HashMap<K, V, S, A> +where + K: Copy + Eq + Hash + Sync, + V: Copy + Sync, + S: BuildHasher, + A: Allocator + Clone, +{ + fn par_extend<I>(&mut self, par_iter: I) + where + I: IntoParallelIterator<Item = (&'a K, &'a V)>, + { + extend(self, par_iter); + } +} + +// This is equal to the normal `HashMap` -- no custom advantage. +fn extend<K, V, S, A, I>(map: &mut HashMap<K, V, S, A>, par_iter: I) +where + K: Eq + Hash, + S: BuildHasher, + I: IntoParallelIterator, + A: Allocator + Clone, + HashMap<K, V, S, A>: Extend<I::Item>, +{ + let (list, len) = super::helpers::collect(par_iter); + + // Keys may be already present or show multiple times in the iterator. + // Reserve the entire length if the map is empty. + // Otherwise reserve half the length (rounded up), so the map + // will only resize twice in the worst case. + let reserve = if map.is_empty() { len } else { (len + 1) / 2 }; + map.reserve(reserve); + for vec in list { + map.extend(vec); + } +} + +#[cfg(test)] +mod test_par_map { + use alloc::vec::Vec; + use core::hash::{Hash, Hasher}; + use core::sync::atomic::{AtomicUsize, Ordering}; + + use rayon::prelude::*; + + use crate::hash_map::HashMap; + + struct Dropable<'a> { + k: usize, + counter: &'a AtomicUsize, + } + + impl Dropable<'_> { + fn new(k: usize, counter: &AtomicUsize) -> Dropable<'_> { + counter.fetch_add(1, Ordering::Relaxed); + + Dropable { k, counter } + } + } + + impl Drop for Dropable<'_> { + fn drop(&mut self) { + self.counter.fetch_sub(1, Ordering::Relaxed); + } + } + + impl Clone for Dropable<'_> { + fn clone(&self) -> Self { + Dropable::new(self.k, self.counter) + } + } + + impl Hash for Dropable<'_> { + fn hash<H>(&self, state: &mut H) + where + H: Hasher, + { + self.k.hash(state); + } + } + + impl PartialEq for Dropable<'_> { + fn eq(&self, other: &Self) -> bool { + self.k == other.k + } + } + + impl Eq for Dropable<'_> {} + + #[test] + fn test_into_iter_drops() { + let key = AtomicUsize::new(0); + let value = AtomicUsize::new(0); + + let hm = { + let mut hm = HashMap::new(); + + assert_eq!(key.load(Ordering::Relaxed), 0); + assert_eq!(value.load(Ordering::Relaxed), 0); + + for i in 0..100 { + let d1 = Dropable::new(i, &key); + let d2 = Dropable::new(i + 100, &value); + hm.insert(d1, d2); + } + + assert_eq!(key.load(Ordering::Relaxed), 100); + assert_eq!(value.load(Ordering::Relaxed), 100); + + hm + }; + + // By the way, ensure that cloning doesn't screw up the dropping. + drop(hm.clone()); + + assert_eq!(key.load(Ordering::Relaxed), 100); + assert_eq!(value.load(Ordering::Relaxed), 100); + + // Ensure that dropping the iterator does not leak anything. + drop(hm.clone().into_par_iter()); + + { + assert_eq!(key.load(Ordering::Relaxed), 100); + assert_eq!(value.load(Ordering::Relaxed), 100); + + // retain only half + let _v: Vec<_> = hm + .into_par_iter() + .filter(|&(ref key, _)| key.k < 50) + .collect(); + + assert_eq!(key.load(Ordering::Relaxed), 50); + assert_eq!(value.load(Ordering::Relaxed), 50); + }; + + assert_eq!(key.load(Ordering::Relaxed), 0); + assert_eq!(value.load(Ordering::Relaxed), 0); + } + + #[test] + fn test_drain_drops() { + let key = AtomicUsize::new(0); + let value = AtomicUsize::new(0); + + let mut hm = { + let mut hm = HashMap::new(); + + assert_eq!(key.load(Ordering::Relaxed), 0); + assert_eq!(value.load(Ordering::Relaxed), 0); + + for i in 0..100 { + let d1 = Dropable::new(i, &key); + let d2 = Dropable::new(i + 100, &value); + hm.insert(d1, d2); + } + + assert_eq!(key.load(Ordering::Relaxed), 100); + assert_eq!(value.load(Ordering::Relaxed), 100); + + hm + }; + + // By the way, ensure that cloning doesn't screw up the dropping. + drop(hm.clone()); + + assert_eq!(key.load(Ordering::Relaxed), 100); + assert_eq!(value.load(Ordering::Relaxed), 100); + + // Ensure that dropping the drain iterator does not leak anything. + drop(hm.clone().par_drain()); + + { + assert_eq!(key.load(Ordering::Relaxed), 100); + assert_eq!(value.load(Ordering::Relaxed), 100); + + // retain only half + let _v: Vec<_> = hm.drain().filter(|&(ref key, _)| key.k < 50).collect(); + assert!(hm.is_empty()); + + assert_eq!(key.load(Ordering::Relaxed), 50); + assert_eq!(value.load(Ordering::Relaxed), 50); + }; + + assert_eq!(key.load(Ordering::Relaxed), 0); + assert_eq!(value.load(Ordering::Relaxed), 0); + } + + #[test] + fn test_empty_iter() { + let mut m: HashMap<isize, bool> = HashMap::new(); + assert_eq!(m.par_drain().count(), 0); + assert_eq!(m.par_keys().count(), 0); + assert_eq!(m.par_values().count(), 0); + assert_eq!(m.par_values_mut().count(), 0); + assert_eq!(m.par_iter().count(), 0); + assert_eq!(m.par_iter_mut().count(), 0); + assert_eq!(m.len(), 0); + assert!(m.is_empty()); + assert_eq!(m.into_par_iter().count(), 0); + } + + #[test] + fn test_iterate() { + let mut m = HashMap::with_capacity(4); + for i in 0..32 { + assert!(m.insert(i, i * 2).is_none()); + } + assert_eq!(m.len(), 32); + + let observed = AtomicUsize::new(0); + + m.par_iter().for_each(|(k, v)| { + assert_eq!(*v, *k * 2); + observed.fetch_or(1 << *k, Ordering::Relaxed); + }); + assert_eq!(observed.into_inner(), 0xFFFF_FFFF); + } + + #[test] + fn test_keys() { + let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; + let map: HashMap<_, _> = vec.into_par_iter().collect(); + let keys: Vec<_> = map.par_keys().cloned().collect(); + assert_eq!(keys.len(), 3); + assert!(keys.contains(&1)); + assert!(keys.contains(&2)); + assert!(keys.contains(&3)); + } + + #[test] + fn test_values() { + let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; + let map: HashMap<_, _> = vec.into_par_iter().collect(); + let values: Vec<_> = map.par_values().cloned().collect(); + assert_eq!(values.len(), 3); + assert!(values.contains(&'a')); + assert!(values.contains(&'b')); + assert!(values.contains(&'c')); + } + + #[test] + fn test_values_mut() { + let vec = vec![(1, 1), (2, 2), (3, 3)]; + let mut map: HashMap<_, _> = vec.into_par_iter().collect(); + map.par_values_mut().for_each(|value| *value *= 2); + let values: Vec<_> = map.par_values().cloned().collect(); + assert_eq!(values.len(), 3); + assert!(values.contains(&2)); + assert!(values.contains(&4)); + assert!(values.contains(&6)); + } + + #[test] + fn test_eq() { + let mut m1 = HashMap::new(); + m1.insert(1, 2); + m1.insert(2, 3); + m1.insert(3, 4); + + let mut m2 = HashMap::new(); + m2.insert(1, 2); + m2.insert(2, 3); + + assert!(!m1.par_eq(&m2)); + + m2.insert(3, 4); + + assert!(m1.par_eq(&m2)); + } + + #[test] + fn test_from_iter() { + let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; + + let map: HashMap<_, _> = xs.par_iter().cloned().collect(); + + for &(k, v) in &xs { + assert_eq!(map.get(&k), Some(&v)); + } + } + + #[test] + fn test_extend_ref() { + let mut a = HashMap::new(); + a.insert(1, "one"); + let mut b = HashMap::new(); + b.insert(2, "two"); + b.insert(3, "three"); + + a.par_extend(&b); + + assert_eq!(a.len(), 3); + assert_eq!(a[&1], "one"); + assert_eq!(a[&2], "two"); + assert_eq!(a[&3], "three"); + } +} diff --git a/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/mod.rs b/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/mod.rs new file mode 100644 index 000000000..99337a1ce --- /dev/null +++ b/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/mod.rs @@ -0,0 +1,4 @@ +mod helpers; +pub(crate) mod map; +pub(crate) mod raw; +pub(crate) mod set; diff --git a/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/raw.rs b/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/raw.rs new file mode 100644 index 000000000..883303e27 --- /dev/null +++ b/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/raw.rs @@ -0,0 +1,231 @@ +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; +use rayon::iter::{ + plumbing::{self, Folder, UnindexedConsumer, UnindexedProducer}, + ParallelIterator, +}; + +/// Parallel iterator which returns a raw pointer to every full bucket in the table. +pub struct RawParIter<T> { + iter: RawIterRange<T>, +} + +impl<T> RawParIter<T> { + #[cfg_attr(feature = "inline-more", inline)] + pub(super) unsafe fn iter(&self) -> RawIterRange<T> { + self.iter.clone() + } +} + +impl<T> Clone for RawParIter<T> { + #[cfg_attr(feature = "inline-more", inline)] + fn clone(&self) -> Self { + Self { + iter: self.iter.clone(), + } + } +} + +impl<T> From<RawIter<T>> for RawParIter<T> { + fn from(it: RawIter<T>) -> Self { + RawParIter { iter: it.iter } + } +} + +impl<T> ParallelIterator for RawParIter<T> { + type Item = Bucket<T>; + + #[cfg_attr(feature = "inline-more", inline)] + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + let producer = ParIterProducer { iter: self.iter }; + plumbing::bridge_unindexed(producer, consumer) + } +} + +/// Producer which returns a `Bucket<T>` for every element. +struct ParIterProducer<T> { + iter: RawIterRange<T>, +} + +impl<T> UnindexedProducer for ParIterProducer<T> { + type Item = Bucket<T>; + + #[cfg_attr(feature = "inline-more", inline)] + fn split(self) -> (Self, Option<Self>) { + let (left, right) = self.iter.split(); + let left = ParIterProducer { iter: left }; + let right = right.map(|right| ParIterProducer { iter: right }); + (left, right) + } + + #[cfg_attr(feature = "inline-more", inline)] + fn fold_with<F>(self, folder: F) -> F + where + F: Folder<Self::Item>, + { + folder.consume_iter(self.iter) + } +} + +/// Parallel iterator which consumes a table and returns elements. +pub struct RawIntoParIter<T, A: Allocator + Clone = Global> { + table: RawTable<T, A>, +} + +impl<T, A: Allocator + Clone> 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> { + type Item = T; + + #[cfg_attr(feature = "inline-more", inline)] + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + let iter = unsafe { self.table.iter().iter }; + let _guard = guard(self.table.into_allocation(), |alloc| { + if let Some((ptr, layout)) = *alloc { + unsafe { + dealloc(ptr.as_ptr(), layout); + } + } + }); + let producer = ParDrainProducer { iter }; + plumbing::bridge_unindexed(producer, consumer) + } +} + +/// Parallel iterator which consumes elements without freeing the table storage. +pub struct RawParDrain<'a, T, A: Allocator + Clone = 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> {} + +impl<T, A: Allocator + Clone> 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> { + type Item = T; + + #[cfg_attr(feature = "inline-more", inline)] + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + let _guard = guard(self.table, |table| unsafe { + table.as_mut().clear_no_drop(); + }); + let iter = unsafe { self.table.as_ref().iter().iter }; + mem::forget(self); + let producer = ParDrainProducer { iter }; + plumbing::bridge_unindexed(producer, consumer) + } +} + +impl<T, A: Allocator + Clone> Drop for RawParDrain<'_, T, A> { + fn drop(&mut self) { + // If drive_unindexed is not called then simply clear the table. + unsafe { + self.table.as_mut().clear(); + } + } +} + +/// Producer which will consume all elements in the range, even if it is dropped +/// halfway through. +struct ParDrainProducer<T> { + iter: RawIterRange<T>, +} + +impl<T: Send> UnindexedProducer for ParDrainProducer<T> { + type Item = T; + + #[cfg_attr(feature = "inline-more", inline)] + fn split(self) -> (Self, Option<Self>) { + let (left, right) = self.iter.clone().split(); + mem::forget(self); + let left = ParDrainProducer { iter: left }; + let right = right.map(|right| ParDrainProducer { iter: right }); + (left, right) + } + + #[cfg_attr(feature = "inline-more", inline)] + fn fold_with<F>(mut self, mut folder: F) -> F + where + F: Folder<Self::Item>, + { + // Make sure to modify the iterator in-place so that any remaining + // elements are processed in our Drop impl. + for item in &mut self.iter { + folder = folder.consume(unsafe { item.read() }); + if folder.full() { + return folder; + } + } + + // If we processed all elements then we don't need to run the drop. + mem::forget(self); + folder + } +} + +impl<T> Drop for ParDrainProducer<T> { + #[cfg_attr(feature = "inline-more", inline)] + fn drop(&mut self) { + // Drop all remaining elements + if mem::needs_drop::<T>() { + for item in &mut self.iter { + unsafe { + item.drop(); + } + } + } + } +} + +impl<T, A: Allocator + Clone> 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> { + RawParIter { + iter: self.iter().iter, + } + } + + /// Returns a parallel iterator over the elements in a `RawTable`. + #[cfg_attr(feature = "inline-more", inline)] + pub fn into_par_iter(self) -> RawIntoParIter<T, A> { + RawIntoParIter { table: self } + } + + /// Returns a parallel iterator which consumes all elements of a `RawTable` + /// without freeing its memory allocation. + #[cfg_attr(feature = "inline-more", inline)] + pub fn par_drain(&mut self) -> RawParDrain<'_, T, A> { + RawParDrain { + table: NonNull::from(self), + marker: PhantomData, + } + } +} diff --git a/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/set.rs b/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/set.rs new file mode 100644 index 000000000..ee4f6e669 --- /dev/null +++ b/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/set.rs @@ -0,0 +1,659 @@ +//! Rayon extensions for `HashSet`. + +use super::map; +use crate::hash_set::HashSet; +use crate::raw::{Allocator, Global}; +use core::hash::{BuildHasher, Hash}; +use rayon::iter::plumbing::UnindexedConsumer; +use rayon::iter::{FromParallelIterator, IntoParallelIterator, ParallelExtend, ParallelIterator}; + +/// Parallel iterator over elements of a consumed set. +/// +/// This iterator is created by the [`into_par_iter`] method on [`HashSet`] +/// (provided by the [`IntoParallelIterator`] trait). +/// See its documentation for more. +/// +/// [`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> { + inner: map::IntoParIter<T, (), A>, +} + +impl<T: Send, A: Allocator + Clone + Send> ParallelIterator for IntoParIter<T, A> { + type Item = T; + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.inner.map(|(k, _)| k).drive_unindexed(consumer) + } +} + +/// Parallel draining iterator over entries of a set. +/// +/// This iterator is created by the [`par_drain`] method on [`HashSet`]. +/// See its documentation for more. +/// +/// [`par_drain`]: /hashbrown/struct.HashSet.html#method.par_drain +/// [`HashSet`]: /hashbrown/struct.HashSet.html +pub struct ParDrain<'a, T, A: Allocator + Clone = Global> { + inner: map::ParDrain<'a, T, (), A>, +} + +impl<T: Send, A: Allocator + Clone + Send + Sync> ParallelIterator for ParDrain<'_, T, A> { + type Item = T; + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.inner.map(|(k, _)| k).drive_unindexed(consumer) + } +} + +/// Parallel iterator over shared references to elements in a set. +/// +/// This iterator is created by the [`par_iter`] method on [`HashSet`] +/// (provided by the [`IntoParallelRefIterator`] trait). +/// See its documentation for more. +/// +/// [`par_iter`]: /hashbrown/struct.HashSet.html#method.par_iter +/// [`HashSet`]: /hashbrown/struct.HashSet.html +/// [`IntoParallelRefIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelRefIterator.html +pub struct ParIter<'a, T> { + inner: map::ParKeys<'a, T, ()>, +} + +impl<'a, T: Sync> ParallelIterator for ParIter<'a, T> { + type Item = &'a T; + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.inner.drive_unindexed(consumer) + } +} + +/// Parallel iterator over shared references to elements in the difference of +/// sets. +/// +/// This iterator is created by the [`par_difference`] method on [`HashSet`]. +/// See its documentation for more. +/// +/// [`par_difference`]: /hashbrown/struct.HashSet.html#method.par_difference +/// [`HashSet`]: /hashbrown/struct.HashSet.html +pub struct ParDifference<'a, T, S, A: Allocator + Clone = Global> { + a: &'a HashSet<T, S, A>, + b: &'a HashSet<T, S, A>, +} + +impl<'a, T, S, A> ParallelIterator for ParDifference<'a, T, S, A> +where + T: Eq + Hash + Sync, + S: BuildHasher + Sync, + A: Allocator + Clone + Sync, +{ + type Item = &'a T; + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.a + .into_par_iter() + .filter(|&x| !self.b.contains(x)) + .drive_unindexed(consumer) + } +} + +/// Parallel iterator over shared references to elements in the symmetric +/// difference of sets. +/// +/// This iterator is created by the [`par_symmetric_difference`] method on +/// [`HashSet`]. +/// See its documentation for more. +/// +/// [`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> { + a: &'a HashSet<T, S, A>, + b: &'a HashSet<T, S, A>, +} + +impl<'a, T, S, A> ParallelIterator for ParSymmetricDifference<'a, T, S, A> +where + T: Eq + Hash + Sync, + S: BuildHasher + Sync, + A: Allocator + Clone + Sync, +{ + type Item = &'a T; + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.a + .par_difference(self.b) + .chain(self.b.par_difference(self.a)) + .drive_unindexed(consumer) + } +} + +/// Parallel iterator over shared references to elements in the intersection of +/// sets. +/// +/// This iterator is created by the [`par_intersection`] method on [`HashSet`]. +/// See its documentation for more. +/// +/// [`par_intersection`]: /hashbrown/struct.HashSet.html#method.par_intersection +/// [`HashSet`]: /hashbrown/struct.HashSet.html +pub struct ParIntersection<'a, T, S, A: Allocator + Clone = Global> { + a: &'a HashSet<T, S, A>, + b: &'a HashSet<T, S, A>, +} + +impl<'a, T, S, A> ParallelIterator for ParIntersection<'a, T, S, A> +where + T: Eq + Hash + Sync, + S: BuildHasher + Sync, + A: Allocator + Clone + Sync, +{ + type Item = &'a T; + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.a + .into_par_iter() + .filter(|&x| self.b.contains(x)) + .drive_unindexed(consumer) + } +} + +/// Parallel iterator over shared references to elements in the union of sets. +/// +/// This iterator is created by the [`par_union`] method on [`HashSet`]. +/// See its documentation for more. +/// +/// [`par_union`]: /hashbrown/struct.HashSet.html#method.par_union +/// [`HashSet`]: /hashbrown/struct.HashSet.html +pub struct ParUnion<'a, T, S, A: Allocator + Clone = Global> { + a: &'a HashSet<T, S, A>, + b: &'a HashSet<T, S, A>, +} + +impl<'a, T, S, A> ParallelIterator for ParUnion<'a, T, S, A> +where + T: Eq + Hash + Sync, + S: BuildHasher + Sync, + A: Allocator + Clone + Sync, +{ + type Item = &'a T; + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + // We'll iterate one set in full, and only the remaining difference from the other. + // Use the smaller set for the difference in order to reduce hash lookups. + let (smaller, larger) = if self.a.len() <= self.b.len() { + (self.a, self.b) + } else { + (self.b, self.a) + }; + larger + .into_par_iter() + .chain(smaller.par_difference(larger)) + .drive_unindexed(consumer) + } +} + +impl<T, S, A> HashSet<T, S, A> +where + T: Eq + Hash + Sync, + S: BuildHasher + Sync, + A: Allocator + Clone + Sync, +{ + /// Visits (potentially in parallel) the values representing the union, + /// i.e. all the values in `self` or `other`, without duplicates. + #[cfg_attr(feature = "inline-more", inline)] + pub fn par_union<'a>(&'a self, other: &'a Self) -> ParUnion<'a, T, S, A> { + ParUnion { a: self, b: other } + } + + /// Visits (potentially in parallel) the values representing the difference, + /// i.e. the values that are in `self` but not in `other`. + #[cfg_attr(feature = "inline-more", inline)] + pub fn par_difference<'a>(&'a self, other: &'a Self) -> ParDifference<'a, T, S, A> { + ParDifference { a: self, b: other } + } + + /// Visits (potentially in parallel) the values representing the symmetric + /// difference, i.e. the values that are in `self` or in `other` but not in both. + #[cfg_attr(feature = "inline-more", inline)] + pub fn par_symmetric_difference<'a>( + &'a self, + other: &'a Self, + ) -> ParSymmetricDifference<'a, T, S, A> { + ParSymmetricDifference { a: self, b: other } + } + + /// Visits (potentially in parallel) the values representing the + /// intersection, i.e. the values that are both in `self` and `other`. + #[cfg_attr(feature = "inline-more", inline)] + pub fn par_intersection<'a>(&'a self, other: &'a Self) -> ParIntersection<'a, T, S, A> { + ParIntersection { a: self, b: other } + } + + /// Returns `true` if `self` has no elements in common with `other`. + /// This is equivalent to checking for an empty intersection. + /// + /// This method runs in a potentially parallel fashion. + pub fn par_is_disjoint(&self, other: &Self) -> bool { + self.into_par_iter().all(|x| !other.contains(x)) + } + + /// Returns `true` if the set is a subset of another, + /// i.e. `other` contains at least all the values in `self`. + /// + /// This method runs in a potentially parallel fashion. + pub fn par_is_subset(&self, other: &Self) -> bool { + if self.len() <= other.len() { + self.into_par_iter().all(|x| other.contains(x)) + } else { + false + } + } + + /// Returns `true` if the set is a superset of another, + /// i.e. `self` contains at least all the values in `other`. + /// + /// This method runs in a potentially parallel fashion. + pub fn par_is_superset(&self, other: &Self) -> bool { + other.par_is_subset(self) + } + + /// Returns `true` if the set is equal to another, + /// i.e. both sets contain the same values. + /// + /// This method runs in a potentially parallel fashion. + pub fn par_eq(&self, other: &Self) -> bool { + self.len() == other.len() && self.par_is_subset(other) + } +} + +impl<T, S, A> HashSet<T, S, A> +where + T: Eq + Hash + Send, + A: Allocator + Clone + Send, +{ + /// Consumes (potentially in parallel) all values in an arbitrary order, + /// while preserving the set's allocated memory for reuse. + #[cfg_attr(feature = "inline-more", inline)] + pub fn par_drain(&mut self) -> ParDrain<'_, T, A> { + ParDrain { + inner: self.map.par_drain(), + } + } +} + +impl<T: Send, S, A: Allocator + Clone + Send> IntoParallelIterator for HashSet<T, S, 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.map.into_par_iter(), + } + } +} + +impl<'a, T: Sync, S, A: Allocator + Clone> IntoParallelIterator for &'a HashSet<T, S, 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: self.map.par_keys(), + } + } +} + +/// Collect values from a parallel iterator into a hashset. +impl<T, S> FromParallelIterator<T> for HashSet<T, S, Global> +where + T: Eq + Hash + Send, + S: BuildHasher + Default, +{ + fn from_par_iter<P>(par_iter: P) -> Self + where + P: IntoParallelIterator<Item = T>, + { + let mut set = HashSet::default(); + set.par_extend(par_iter); + set + } +} + +/// Extend a hash set with items from a parallel iterator. +impl<T, S> ParallelExtend<T> for HashSet<T, S, Global> +where + T: Eq + Hash + Send, + S: BuildHasher, +{ + fn par_extend<I>(&mut self, par_iter: I) + where + I: IntoParallelIterator<Item = T>, + { + extend(self, par_iter); + } +} + +/// Extend a hash set with copied items from a parallel iterator. +impl<'a, T, S> ParallelExtend<&'a T> for HashSet<T, S, Global> +where + T: 'a + Copy + Eq + Hash + Sync, + S: BuildHasher, +{ + fn par_extend<I>(&mut self, par_iter: I) + where + I: IntoParallelIterator<Item = &'a T>, + { + extend(self, par_iter); + } +} + +// This is equal to the normal `HashSet` -- no custom advantage. +fn extend<T, S, I, A>(set: &mut HashSet<T, S, A>, par_iter: I) +where + T: Eq + Hash, + S: BuildHasher, + A: Allocator + Clone, + I: IntoParallelIterator, + HashSet<T, S, A>: Extend<I::Item>, +{ + let (list, len) = super::helpers::collect(par_iter); + + // Values may be already present or show multiple times in the iterator. + // Reserve the entire length if the set is empty. + // Otherwise reserve half the length (rounded up), so the set + // will only resize twice in the worst case. + let reserve = if set.is_empty() { len } else { (len + 1) / 2 }; + set.reserve(reserve); + for vec in list { + set.extend(vec); + } +} + +#[cfg(test)] +mod test_par_set { + use alloc::vec::Vec; + use core::sync::atomic::{AtomicUsize, Ordering}; + + use rayon::prelude::*; + + use crate::hash_set::HashSet; + + #[test] + fn test_disjoint() { + let mut xs = HashSet::new(); + let mut ys = HashSet::new(); + assert!(xs.par_is_disjoint(&ys)); + assert!(ys.par_is_disjoint(&xs)); + assert!(xs.insert(5)); + assert!(ys.insert(11)); + assert!(xs.par_is_disjoint(&ys)); + assert!(ys.par_is_disjoint(&xs)); + assert!(xs.insert(7)); + assert!(xs.insert(19)); + assert!(xs.insert(4)); + assert!(ys.insert(2)); + assert!(ys.insert(-11)); + assert!(xs.par_is_disjoint(&ys)); + assert!(ys.par_is_disjoint(&xs)); + assert!(ys.insert(7)); + assert!(!xs.par_is_disjoint(&ys)); + assert!(!ys.par_is_disjoint(&xs)); + } + + #[test] + fn test_subset_and_superset() { + let mut a = HashSet::new(); + assert!(a.insert(0)); + assert!(a.insert(5)); + assert!(a.insert(11)); + assert!(a.insert(7)); + + let mut b = HashSet::new(); + assert!(b.insert(0)); + assert!(b.insert(7)); + assert!(b.insert(19)); + assert!(b.insert(250)); + assert!(b.insert(11)); + assert!(b.insert(200)); + + assert!(!a.par_is_subset(&b)); + assert!(!a.par_is_superset(&b)); + assert!(!b.par_is_subset(&a)); + assert!(!b.par_is_superset(&a)); + + assert!(b.insert(5)); + + assert!(a.par_is_subset(&b)); + assert!(!a.par_is_superset(&b)); + assert!(!b.par_is_subset(&a)); + assert!(b.par_is_superset(&a)); + } + + #[test] + fn test_iterate() { + let mut a = HashSet::new(); + for i in 0..32 { + assert!(a.insert(i)); + } + 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_intersection() { + let mut a = HashSet::new(); + let mut b = HashSet::new(); + + assert!(a.insert(11)); + assert!(a.insert(1)); + assert!(a.insert(3)); + assert!(a.insert(77)); + assert!(a.insert(103)); + assert!(a.insert(5)); + assert!(a.insert(-5)); + + assert!(b.insert(2)); + assert!(b.insert(11)); + assert!(b.insert(77)); + assert!(b.insert(-9)); + assert!(b.insert(-42)); + assert!(b.insert(5)); + assert!(b.insert(3)); + + let expected = [3, 5, 11, 77]; + let i = a + .par_intersection(&b) + .map(|x| { + assert!(expected.contains(x)); + 1 + }) + .sum::<usize>(); + assert_eq!(i, expected.len()); + } + + #[test] + fn test_difference() { + let mut a = HashSet::new(); + let mut b = HashSet::new(); + + assert!(a.insert(1)); + assert!(a.insert(3)); + assert!(a.insert(5)); + assert!(a.insert(9)); + assert!(a.insert(11)); + + assert!(b.insert(3)); + assert!(b.insert(9)); + + let expected = [1, 5, 11]; + let i = a + .par_difference(&b) + .map(|x| { + assert!(expected.contains(x)); + 1 + }) + .sum::<usize>(); + assert_eq!(i, expected.len()); + } + + #[test] + fn test_symmetric_difference() { + let mut a = HashSet::new(); + let mut b = HashSet::new(); + + assert!(a.insert(1)); + assert!(a.insert(3)); + assert!(a.insert(5)); + assert!(a.insert(9)); + assert!(a.insert(11)); + + assert!(b.insert(-2)); + assert!(b.insert(3)); + assert!(b.insert(9)); + assert!(b.insert(14)); + assert!(b.insert(22)); + + let expected = [-2, 1, 5, 11, 14, 22]; + let i = a + .par_symmetric_difference(&b) + .map(|x| { + assert!(expected.contains(x)); + 1 + }) + .sum::<usize>(); + assert_eq!(i, expected.len()); + } + + #[test] + fn test_union() { + let mut a = HashSet::new(); + let mut b = HashSet::new(); + + assert!(a.insert(1)); + assert!(a.insert(3)); + assert!(a.insert(5)); + assert!(a.insert(9)); + assert!(a.insert(11)); + assert!(a.insert(16)); + assert!(a.insert(19)); + assert!(a.insert(24)); + + assert!(b.insert(-2)); + assert!(b.insert(1)); + assert!(b.insert(5)); + assert!(b.insert(9)); + assert!(b.insert(13)); + assert!(b.insert(19)); + + let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]; + let i = a + .par_union(&b) + .map(|x| { + assert!(expected.contains(x)); + 1 + }) + .sum::<usize>(); + assert_eq!(i, expected.len()); + } + + #[test] + fn test_from_iter() { + let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9]; + + let set: HashSet<_> = xs.par_iter().cloned().collect(); + + for x in &xs { + assert!(set.contains(x)); + } + } + + #[test] + fn test_move_iter() { + let hs = { + let mut hs = HashSet::new(); + + hs.insert('a'); + hs.insert('b'); + + hs + }; + + let v = hs.into_par_iter().collect::<Vec<char>>(); + assert!(v == ['a', 'b'] || v == ['b', 'a']); + } + + #[test] + fn test_eq() { + // These constants once happened to expose a bug in insert(). + // I'm keeping them around to prevent a regression. + let mut s1 = HashSet::new(); + + s1.insert(1); + s1.insert(2); + s1.insert(3); + + let mut s2 = HashSet::new(); + + s2.insert(1); + s2.insert(2); + + assert!(!s1.par_eq(&s2)); + + s2.insert(3); + + assert!(s1.par_eq(&s2)); + } + + #[test] + fn test_extend_ref() { + let mut a = HashSet::new(); + a.insert(1); + + a.par_extend(&[2, 3, 4][..]); + + assert_eq!(a.len(), 4); + assert!(a.contains(&1)); + assert!(a.contains(&2)); + assert!(a.contains(&3)); + assert!(a.contains(&4)); + + let mut b = HashSet::new(); + b.insert(5); + b.insert(6); + + a.par_extend(&b); + + assert_eq!(a.len(), 6); + assert!(a.contains(&1)); + assert!(a.contains(&2)); + assert!(a.contains(&3)); + assert!(a.contains(&4)); + assert!(a.contains(&5)); + assert!(a.contains(&6)); + } +} diff --git a/vendor/hashbrown-0.12.3/src/external_trait_impls/serde.rs b/vendor/hashbrown-0.12.3/src/external_trait_impls/serde.rs new file mode 100644 index 000000000..4d62deeb7 --- /dev/null +++ b/vendor/hashbrown-0.12.3/src/external_trait_impls/serde.rs @@ -0,0 +1,201 @@ +mod size_hint { + use core::cmp; + + /// This presumably exists to prevent denial of service attacks. + /// + /// Original discussion: https://github.com/serde-rs/serde/issues/1114. + #[cfg_attr(feature = "inline-more", inline)] + pub(super) fn cautious(hint: Option<usize>) -> usize { + cmp::min(hint.unwrap_or(0), 4096) + } +} + +mod map { + use core::fmt; + use core::hash::{BuildHasher, Hash}; + use core::marker::PhantomData; + use serde::de::{Deserialize, Deserializer, MapAccess, Visitor}; + use serde::ser::{Serialize, Serializer}; + + use crate::hash_map::HashMap; + + use super::size_hint; + + impl<K, V, H> Serialize for HashMap<K, V, H> + where + K: Serialize + Eq + Hash, + V: Serialize, + H: BuildHasher, + { + #[cfg_attr(feature = "inline-more", inline)] + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + serializer.collect_map(self) + } + } + + impl<'de, K, V, S> Deserialize<'de> for HashMap<K, V, S> + where + K: Deserialize<'de> + Eq + Hash, + V: Deserialize<'de>, + S: BuildHasher + 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>>, + } + + impl<'de, K, V, S> Visitor<'de> for MapVisitor<K, V, S> + where + K: Deserialize<'de> + Eq + Hash, + V: Deserialize<'de>, + S: BuildHasher + Default, + { + type Value = HashMap<K, V, S>; + + 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> + where + A: MapAccess<'de>, + { + let mut values = HashMap::with_capacity_and_hasher( + size_hint::cautious(map.size_hint()), + S::default(), + ); + + while let Some((key, value)) = map.next_entry()? { + values.insert(key, value); + } + + Ok(values) + } + } + + let visitor = MapVisitor { + marker: PhantomData, + }; + deserializer.deserialize_map(visitor) + } + } +} + +mod set { + use core::fmt; + use core::hash::{BuildHasher, Hash}; + use core::marker::PhantomData; + use serde::de::{Deserialize, Deserializer, SeqAccess, Visitor}; + use serde::ser::{Serialize, Serializer}; + + use crate::hash_set::HashSet; + + use super::size_hint; + + impl<T, H> Serialize for HashSet<T, H> + where + T: Serialize + Eq + Hash, + H: BuildHasher, + { + #[cfg_attr(feature = "inline-more", inline)] + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + serializer.collect_seq(self) + } + } + + impl<'de, T, S> Deserialize<'de> for HashSet<T, S> + where + T: Deserialize<'de> + Eq + Hash, + S: BuildHasher + Default, + { + fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> + where + D: Deserializer<'de>, + { + struct SeqVisitor<T, S> { + marker: PhantomData<HashSet<T, S>>, + } + + impl<'de, T, S> Visitor<'de> for SeqVisitor<T, S> + where + T: Deserialize<'de> + Eq + Hash, + S: BuildHasher + Default, + { + type Value = HashSet<T, S>; + + 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> + where + A: SeqAccess<'de>, + { + let mut values = HashSet::with_capacity_and_hasher( + size_hint::cautious(seq.size_hint()), + S::default(), + ); + + while let Some(value) = seq.next_element()? { + values.insert(value); + } + + Ok(values) + } + } + + let visitor = SeqVisitor { + marker: PhantomData, + }; + deserializer.deserialize_seq(visitor) + } + + #[allow(clippy::missing_errors_doc)] + fn deserialize_in_place<D>(deserializer: D, place: &mut Self) -> Result<(), D::Error> + where + D: Deserializer<'de>, + { + struct SeqInPlaceVisitor<'a, T, S>(&'a mut HashSet<T, S>); + + impl<'a, 'de, T, S> Visitor<'de> for SeqInPlaceVisitor<'a, T, S> + where + T: Deserialize<'de> + Eq + Hash, + S: BuildHasher + Default, + { + type Value = (); + + 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> + where + A: SeqAccess<'de>, + { + self.0.clear(); + self.0.reserve(size_hint::cautious(seq.size_hint())); + + while let Some(value) = seq.next_element()? { + self.0.insert(value); + } + + Ok(()) + } + } + + deserializer.deserialize_seq(SeqInPlaceVisitor(place)) + } + } +} |