diff options
Diffstat (limited to 'vendor/hashbrown-0.12.3/src/external_trait_impls')
7 files changed, 0 insertions, 1860 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 deleted file mode 100644 index ef497836c..000000000 --- a/vendor/hashbrown-0.12.3/src/external_trait_impls/mod.rs +++ /dev/null @@ -1,4 +0,0 @@ -#[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 deleted file mode 100644 index 070b08cd5..000000000 --- a/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/helpers.rs +++ /dev/null @@ -1,27 +0,0 @@ -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 deleted file mode 100644 index 14d91c220..000000000 --- a/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/map.rs +++ /dev/null @@ -1,734 +0,0 @@ -//! 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 deleted file mode 100644 index 99337a1ce..000000000 --- a/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/mod.rs +++ /dev/null @@ -1,4 +0,0 @@ -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 deleted file mode 100644 index 883303e27..000000000 --- a/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/raw.rs +++ /dev/null @@ -1,231 +0,0 @@ -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 deleted file mode 100644 index ee4f6e669..000000000 --- a/vendor/hashbrown-0.12.3/src/external_trait_impls/rayon/set.rs +++ /dev/null @@ -1,659 +0,0 @@ -//! 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 deleted file mode 100644 index 4d62deeb7..000000000 --- a/vendor/hashbrown-0.12.3/src/external_trait_impls/serde.rs +++ /dev/null @@ -1,201 +0,0 @@ -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)) - } - } -} |