Upgrade rust/crates/hashbrown to 0.11.2android-s-beta-2android-s-beta-1

Test: make
Change-Id: I635dccc3bc3cd89b50a49c08f6c7010d0a883e70

3 files changed, 265 insertions, 154 deletions

diff --git a/src/external_trait_impls/rayon/map.rs b/src/external_trait_impls/rayon/map.rs
index 334f8bb..61b7380 100644
--- a/src/external_trait_impls/rayon/map.rs
+++ b/src/external_trait_impls/rayon/map.rs
@@ -1,8 +1,11 @@
 //! 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};
 
@@ -15,11 +18,12 @@ use rayon::iter::{FromParallelIterator, IntoParallelIterator, ParallelExtend, Pa
 /// [`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, S> {
-    map: &'a HashMap<K, V, S>,
+pub struct ParIter<'a, K, V> {
+    inner: RawParIter<(K, V)>,
+    marker: PhantomData<(&'a K, &'a V)>,
 }
 
-impl<'a, K: Sync, V: Sync, S: Sync> ParallelIterator for ParIter<'a, K, V, S> {
+impl<'a, K: Sync, V: Sync> ParallelIterator for ParIter<'a, K, V> {
     type Item = (&'a K, &'a V);
 
     #[cfg_attr(feature = "inline-more", inline)]
@@ -27,7 +31,7 @@ impl<'a, K: Sync, V: Sync, S: Sync> ParallelIterator for ParIter<'a, K, V, S> {
     where
         C: UnindexedConsumer<Self::Item>,
     {
-        unsafe { self.map.table.par_iter() }
+        self.inner
             .map(|x| unsafe {
                 let r = x.as_ref();
                 (&r.0, &r.1)
@@ -36,16 +40,23 @@ impl<'a, K: Sync, V: Sync, S: Sync> ParallelIterator for ParIter<'a, K, V, S> {
     }
 }
 
-impl<K, V, S> Clone for ParIter<'_, K, V, S> {
+impl<K, V> Clone for ParIter<'_, K, V> {
     #[cfg_attr(feature = "inline-more", inline)]
     fn clone(&self) -> Self {
-        ParIter { map: self.map }
+        Self {
+            inner: self.inner.clone(),
+            marker: PhantomData,
+        }
     }
 }
 
-impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for ParIter<'_, K, V, S> {
+impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug> fmt::Debug for ParIter<'_, K, V> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        self.map.iter().fmt(f)
+        let iter = unsafe { self.inner.iter() }.map(|x| unsafe {
+            let r = x.as_ref();
+            (&r.0, &r.1)
+        });
+        f.debug_list().entries(iter).finish()
     }
 }
 
@@ -56,11 +67,12 @@ impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for Pa
 ///
 /// [`par_keys`]: /hashbrown/struct.HashMap.html#method.par_keys
 /// [`HashMap`]: /hashbrown/struct.HashMap.html
-pub struct ParKeys<'a, K, V, S> {
-    map: &'a HashMap<K, V, S>,
+pub struct ParKeys<'a, K, V> {
+    inner: RawParIter<(K, V)>,
+    marker: PhantomData<(&'a K, &'a V)>,
 }
 
-impl<'a, K: Sync, V: Sync, S: Sync> ParallelIterator for ParKeys<'a, K, V, S> {
+impl<'a, K: Sync, V: Sync> ParallelIterator for ParKeys<'a, K, V> {
     type Item = &'a K;
 
     #[cfg_attr(feature = "inline-more", inline)]
@@ -68,22 +80,26 @@ impl<'a, K: Sync, V: Sync, S: Sync> ParallelIterator for ParKeys<'a, K, V, S> {
     where
         C: UnindexedConsumer<Self::Item>,
     {
-        unsafe { self.map.table.par_iter() }
+        self.inner
             .map(|x| unsafe { &x.as_ref().0 })
             .drive_unindexed(consumer)
     }
 }
 
-impl<K, V, S> Clone for ParKeys<'_, K, V, S> {
+impl<K, V> Clone for ParKeys<'_, K, V> {
     #[cfg_attr(feature = "inline-more", inline)]
     fn clone(&self) -> Self {
-        ParKeys { map: self.map }
+        Self {
+            inner: self.inner.clone(),
+            marker: PhantomData,
+        }
     }
 }
 
-impl<K: fmt::Debug + Eq + Hash, V, S: BuildHasher> fmt::Debug for ParKeys<'_, K, V, S> {
+impl<K: fmt::Debug + Eq + Hash, V> fmt::Debug for ParKeys<'_, K, V> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        self.map.keys().fmt(f)
+        let iter = unsafe { self.inner.iter() }.map(|x| unsafe { &x.as_ref().0 });
+        f.debug_list().entries(iter).finish()
     }
 }
 
@@ -94,11 +110,12 @@ impl<K: fmt::Debug + Eq + Hash, V, S: BuildHasher> fmt::Debug for ParKeys<'_, K,
 ///
 /// [`par_values`]: /hashbrown/struct.HashMap.html#method.par_values
 /// [`HashMap`]: /hashbrown/struct.HashMap.html
-pub struct ParValues<'a, K, V, S> {
-    map: &'a HashMap<K, V, S>,
+pub struct ParValues<'a, K, V> {
+    inner: RawParIter<(K, V)>,
+    marker: PhantomData<(&'a K, &'a V)>,
 }
 
-impl<'a, K: Sync, V: Sync, S: Sync> ParallelIterator for ParValues<'a, K, V, S> {
+impl<'a, K: Sync, V: Sync> ParallelIterator for ParValues<'a, K, V> {
     type Item = &'a V;
 
     #[cfg_attr(feature = "inline-more", inline)]
@@ -106,22 +123,26 @@ impl<'a, K: Sync, V: Sync, S: Sync> ParallelIterator for ParValues<'a, K, V, S>
     where
         C: UnindexedConsumer<Self::Item>,
     {
-        unsafe { self.map.table.par_iter() }
+        self.inner
             .map(|x| unsafe { &x.as_ref().1 })
             .drive_unindexed(consumer)
     }
 }
 
-impl<K, V, S> Clone for ParValues<'_, K, V, S> {
+impl<K, V> Clone for ParValues<'_, K, V> {
     #[cfg_attr(feature = "inline-more", inline)]
     fn clone(&self) -> Self {
-        ParValues { map: self.map }
+        Self {
+            inner: self.inner.clone(),
+            marker: PhantomData,
+        }
     }
 }
 
-impl<K: Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for ParValues<'_, K, V, S> {
+impl<K: Eq + Hash, V: fmt::Debug> fmt::Debug for ParValues<'_, K, V> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        self.map.values().fmt(f)
+        let iter = unsafe { self.inner.iter() }.map(|x| unsafe { &x.as_ref().1 });
+        f.debug_list().entries(iter).finish()
     }
 }
 
@@ -134,11 +155,12 @@ impl<K: Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for ParValues<'_, K
 /// [`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, S> {
-    map: &'a mut HashMap<K, V, S>,
+pub struct ParIterMut<'a, K, V> {
+    inner: RawParIter<(K, V)>,
+    marker: PhantomData<(&'a K, &'a mut V)>,
 }
 
-impl<'a, K: Send + Sync, V: Send, S: Send> ParallelIterator for ParIterMut<'a, K, V, S> {
+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)]
@@ -146,7 +168,7 @@ impl<'a, K: Send + Sync, V: Send, S: Send> ParallelIterator for ParIterMut<'a, K
     where
         C: UnindexedConsumer<Self::Item>,
     {
-        unsafe { self.map.table.par_iter() }
+        self.inner
             .map(|x| unsafe {
                 let r = x.as_mut();
                 (&r.0, &mut r.1)
@@ -155,11 +177,13 @@ impl<'a, K: Send + Sync, V: Send, S: Send> ParallelIterator for ParIterMut<'a, K
     }
 }
 
-impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug
-    for ParIterMut<'_, K, V, S>
-{
+impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug> fmt::Debug for ParIterMut<'_, K, V> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        self.map.iter().fmt(f)
+        ParIter {
+            inner: self.inner.clone(),
+            marker: PhantomData,
+        }
+        .fmt(f)
     }
 }
 
@@ -170,11 +194,12 @@ impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug
 ///
 /// [`par_values_mut`]: /hashbrown/struct.HashMap.html#method.par_values_mut
 /// [`HashMap`]: /hashbrown/struct.HashMap.html
-pub struct ParValuesMut<'a, K, V, S> {
-    map: &'a mut HashMap<K, V, S>,
+pub struct ParValuesMut<'a, K, V> {
+    inner: RawParIter<(K, V)>,
+    marker: PhantomData<(&'a K, &'a mut V)>,
 }
 
-impl<'a, K: Send, V: Send, S: Send> ParallelIterator for ParValuesMut<'a, K, V, S> {
+impl<'a, K: Sync, V: Send> ParallelIterator for ParValuesMut<'a, K, V> {
     type Item = &'a mut V;
 
     #[cfg_attr(feature = "inline-more", inline)]
@@ -182,15 +207,19 @@ impl<'a, K: Send, V: Send, S: Send> ParallelIterator for ParValuesMut<'a, K, V,
     where
         C: UnindexedConsumer<Self::Item>,
     {
-        unsafe { self.map.table.par_iter() }
+        self.inner
             .map(|x| unsafe { &mut x.as_mut().1 })
             .drive_unindexed(consumer)
     }
 }
 
-impl<K: Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for ParValuesMut<'_, K, V, S> {
+impl<K: Eq + Hash, V: fmt::Debug> fmt::Debug for ParValuesMut<'_, K, V> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        self.map.values().fmt(f)
+        ParValues {
+            inner: self.inner.clone(),
+            marker: PhantomData,
+        }
+        .fmt(f)
     }
 }
 
@@ -203,11 +232,11 @@ impl<K: Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for ParValuesMut<'_
 /// [`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, S> {
-    map: HashMap<K, V, S>,
+pub struct IntoParIter<K, V, A: Allocator + Clone = Global> {
+    inner: RawIntoParIter<(K, V), A>,
 }
 
-impl<K: Send, V: Send, S: Send> ParallelIterator for IntoParIter<K, V, S> {
+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)]
@@ -215,13 +244,19 @@ impl<K: Send, V: Send, S: Send> ParallelIterator for IntoParIter<K, V, S> {
     where
         C: UnindexedConsumer<Self::Item>,
     {
-        self.map.table.into_par_iter().drive_unindexed(consumer)
+        self.inner.drive_unindexed(consumer)
     }
 }
 
-impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for IntoParIter<K, V, S> {
+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 {
-        self.map.iter().fmt(f)
+        ParIter {
+            inner: unsafe { self.inner.par_iter() },
+            marker: PhantomData,
+        }
+        .fmt(f)
     }
 }
 
@@ -232,11 +267,11 @@ impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for In
 ///
 /// [`par_drain`]: /hashbrown/struct.HashMap.html#method.par_drain
 /// [`HashMap`]: /hashbrown/struct.HashMap.html
-pub struct ParDrain<'a, K, V, S> {
-    map: &'a mut HashMap<K, V, S>,
+pub struct ParDrain<'a, K, V, A: Allocator + Clone = Global> {
+    inner: RawParDrain<'a, (K, V), A>,
 }
 
-impl<K: Send, V: Send, S: Send> ParallelIterator for ParDrain<'_, K, V, S> {
+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)]
@@ -244,52 +279,68 @@ impl<K: Send, V: Send, S: Send> ParallelIterator for ParDrain<'_, K, V, S> {
     where
         C: UnindexedConsumer<Self::Item>,
     {
-        self.map.table.par_drain().drive_unindexed(consumer)
+        self.inner.drive_unindexed(consumer)
     }
 }
 
-impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug
-    for ParDrain<'_, K, V, S>
+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 {
-        self.map.iter().fmt(f)
+        ParIter {
+            inner: unsafe { self.inner.par_iter() },
+            marker: PhantomData,
+        }
+        .fmt(f)
     }
 }
 
-impl<K: Sync, V: Sync, S: Sync> HashMap<K, V, S> {
+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, S> {
-        ParKeys { map: self }
+    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, S> {
-        ParValues { map: self }
+    pub fn par_values(&self) -> ParValues<'_, K, V> {
+        ParValues {
+            inner: unsafe { self.table.par_iter() },
+            marker: PhantomData,
+        }
     }
 }
 
-impl<K: Send, V: Send, S: Send> HashMap<K, V, S> {
+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, S> {
-        ParValuesMut { map: self }
+    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, S> {
-        ParDrain { map: self }
+    pub fn par_drain(&mut self) -> ParDrain<'_, K, V, A> {
+        ParDrain {
+            inner: self.table.par_drain(),
+        }
     }
 }
 
-impl<K, V, S> HashMap<K, V, S>
+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.
@@ -303,33 +354,47 @@ where
     }
 }
 
-impl<K: Send, V: Send, S: Send> IntoParallelIterator for HashMap<K, V, S> {
+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, S>;
+    type Iter = IntoParIter<K, V, A>;
 
     #[cfg_attr(feature = "inline-more", inline)]
     fn into_par_iter(self) -> Self::Iter {
-        IntoParIter { map: self }
+        IntoParIter {
+            inner: self.table.into_par_iter(),
+        }
     }
 }
 
-impl<'a, K: Sync, V: Sync, S: Sync> IntoParallelIterator for &'a HashMap<K, V, S> {
+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, S>;
+    type Iter = ParIter<'a, K, V>;
 
     #[cfg_attr(feature = "inline-more", inline)]
     fn into_par_iter(self) -> Self::Iter {
-        ParIter { map: self }
+        ParIter {
+            inner: unsafe { self.table.par_iter() },
+            marker: PhantomData,
+        }
     }
 }
 
-impl<'a, K: Send + Sync, V: Send, S: Send> IntoParallelIterator for &'a mut HashMap<K, V, S> {
+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, S>;
+    type Iter = ParIterMut<'a, K, V>;
 
     #[cfg_attr(feature = "inline-more", inline)]
     fn into_par_iter(self) -> Self::Iter {
-        ParIterMut { map: self }
+        ParIterMut {
+            inner: unsafe { self.table.par_iter() },
+            marker: PhantomData,
+        }
     }
 }
 
@@ -337,7 +402,7 @@ impl<'a, K: Send + Sync, V: Send, S: Send> IntoParallelIterator for &'a mut Hash
 /// 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>
+impl<K, V, S> FromParallelIterator<(K, V)> for HashMap<K, V, S, Global>
 where
     K: Eq + Hash + Send,
     V: Send,
@@ -354,11 +419,12 @@ where
 }
 
 /// Extend a hash map with items from a parallel iterator.
-impl<K, V, S> ParallelExtend<(K, V)> for HashMap<K, V, S>
+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
@@ -369,11 +435,12 @@ where
 }
 
 /// Extend a hash map with copied items from a parallel iterator.
-impl<'a, K, V, S> ParallelExtend<(&'a K, &'a V)> for HashMap<K, V, S>
+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
@@ -384,12 +451,13 @@ where
 }
 
 // This is equal to the normal `HashMap` -- no custom advantage.
-fn extend<K, V, S, I>(map: &mut HashMap<K, V, S>, par_iter: I)
+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,
-    HashMap<K, V, S>: Extend<I::Item>,
+    A: Allocator + Clone,
+    HashMap<K, V, S, A>: Extend<I::Item>,
 {
     let (list, len) = super::helpers::collect(par_iter);
 
diff --git a/src/external_trait_impls/rayon/raw.rs b/src/external_trait_impls/rayon/raw.rs
index 1bd2c17..18da1ea 100644
--- a/src/external_trait_impls/rayon/raw.rs
+++ b/src/external_trait_impls/rayon/raw.rs
@@ -1,5 +1,5 @@
 use crate::raw::Bucket;
-use crate::raw::{RawIter, RawIterRange, RawTable};
+use crate::raw::{Allocator, Global, RawIter, RawIterRange, RawTable};
 use crate::scopeguard::guard;
 use alloc::alloc::dealloc;
 use core::marker::PhantomData;
@@ -15,6 +15,22 @@ 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 }
@@ -60,11 +76,18 @@ impl<T> UnindexedProducer for ParIterProducer<T> {
 }
 
 /// Parallel iterator which consumes a table and returns elements.
-pub struct RawIntoParIter<T> {
-    table: RawTable<T>,
+pub struct RawIntoParIter<T, A: Allocator + Clone = Global> {
+    table: RawTable<T, A>,
 }
 
-impl<T: Send> ParallelIterator for RawIntoParIter<T> {
+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> ParallelIterator for RawIntoParIter<T, A> {
     type Item = T;
 
     #[cfg_attr(feature = "inline-more", inline)]
@@ -73,7 +96,7 @@ impl<T: Send> ParallelIterator for RawIntoParIter<T> {
         C: UnindexedConsumer<Self::Item>,
     {
         let iter = unsafe { self.table.iter().iter };
-        let _guard = guard(self.table.into_alloc(), |alloc| {
+        let _guard = guard(self.table.into_allocation(), |alloc| {
             if let Some((ptr, layout)) = *alloc {
                 unsafe {
                     dealloc(ptr.as_ptr(), layout);
@@ -86,16 +109,23 @@ impl<T: Send> ParallelIterator for RawIntoParIter<T> {
 }
 
 /// Parallel iterator which consumes elements without freeing the table storage.
-pub struct RawParDrain<'a, T> {
+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>>,
-    marker: PhantomData<&'a RawTable<T>>,
+    table: NonNull<RawTable<T, A>>,
+    marker: PhantomData<&'a RawTable<T, A>>,
 }
 
-unsafe impl<T> Send for RawParDrain<'_, T> {}
+unsafe impl<T, 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> ParallelIterator for RawParDrain<'_, T> {
+impl<T: Send, A: Allocator + Clone> ParallelIterator for RawParDrain<'_, T, A> {
     type Item = T;
 
     #[cfg_attr(feature = "inline-more", inline)]
@@ -113,7 +143,7 @@ impl<T: Send> ParallelIterator for RawParDrain<'_, T> {
     }
 }
 
-impl<T> Drop for RawParDrain<'_, T> {
+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() }
@@ -172,7 +202,7 @@ impl<T> Drop for ParDrainProducer<T> {
     }
 }
 
-impl<T> RawTable<T> {
+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> {
@@ -183,14 +213,14 @@ impl<T> RawTable<T> {
 
     /// Returns a parallel iterator over the elements in a `RawTable`.
     #[cfg_attr(feature = "inline-more", inline)]
-    pub fn into_par_iter(self) -> RawIntoParIter<T> {
+    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> {
+    pub fn par_drain(&mut self) -> RawParDrain<'_, T, A> {
         RawParDrain {
             table: NonNull::from(self),
             marker: PhantomData,
diff --git a/src/external_trait_impls/rayon/set.rs b/src/external_trait_impls/rayon/set.rs
index 53d2660..ee4f6e6 100644
--- a/src/external_trait_impls/rayon/set.rs
+++ b/src/external_trait_impls/rayon/set.rs
@@ -1,6 +1,8 @@
 //! 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};
@@ -14,22 +16,18 @@ use rayon::iter::{FromParallelIterator, IntoParallelIterator, ParallelExtend, Pa
 /// [`into_par_iter`]: /hashbrown/struct.HashSet.html#method.into_par_iter
 /// [`HashSet`]: /hashbrown/struct.HashSet.html
 /// [`IntoParallelIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelIterator.html
-pub struct IntoParIter<T, S> {
-    set: HashSet<T, S>,
+pub struct IntoParIter<T, A: Allocator + Clone = Global> {
+    inner: map::IntoParIter<T, (), A>,
 }
 
-impl<T: Send, S: Send> ParallelIterator for IntoParIter<T, S> {
+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.set
-            .map
-            .into_par_iter()
-            .map(|(k, _)| k)
-            .drive_unindexed(consumer)
+        self.inner.map(|(k, _)| k).drive_unindexed(consumer)
     }
 }
 
@@ -40,22 +38,18 @@ impl<T: Send, S: Send> ParallelIterator for IntoParIter<T, S> {
 ///
 /// [`par_drain`]: /hashbrown/struct.HashSet.html#method.par_drain
 /// [`HashSet`]: /hashbrown/struct.HashSet.html
-pub struct ParDrain<'a, T, S> {
-    set: &'a mut HashSet<T, S>,
+pub struct ParDrain<'a, T, A: Allocator + Clone = Global> {
+    inner: map::ParDrain<'a, T, (), A>,
 }
 
-impl<T: Send, S: Send> ParallelIterator for ParDrain<'_, T, S> {
+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.set
-            .map
-            .par_drain()
-            .map(|(k, _)| k)
-            .drive_unindexed(consumer)
+        self.inner.map(|(k, _)| k).drive_unindexed(consumer)
     }
 }
 
@@ -68,18 +62,18 @@ impl<T: Send, S: Send> ParallelIterator for ParDrain<'_, T, S> {
 /// [`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, S> {
-    set: &'a HashSet<T, S>,
+pub struct ParIter<'a, T> {
+    inner: map::ParKeys<'a, T, ()>,
 }
 
-impl<'a, T: Sync, S: Sync> ParallelIterator for ParIter<'a, T, S> {
+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.set.map.par_keys().drive_unindexed(consumer)
+        self.inner.drive_unindexed(consumer)
     }
 }
 
@@ -91,15 +85,16 @@ impl<'a, T: Sync, S: Sync> ParallelIterator for ParIter<'a, T, S> {
 ///
 /// [`par_difference`]: /hashbrown/struct.HashSet.html#method.par_difference
 /// [`HashSet`]: /hashbrown/struct.HashSet.html
-pub struct ParDifference<'a, T, S> {
-    a: &'a HashSet<T, S>,
-    b: &'a HashSet<T, S>,
+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> ParallelIterator for ParDifference<'a, T, S>
+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;
 
@@ -123,15 +118,16 @@ where
 ///
 /// [`par_symmetric_difference`]: /hashbrown/struct.HashSet.html#method.par_symmetric_difference
 /// [`HashSet`]: /hashbrown/struct.HashSet.html
-pub struct ParSymmetricDifference<'a, T, S> {
-    a: &'a HashSet<T, S>,
-    b: &'a HashSet<T, S>,
+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> ParallelIterator for ParSymmetricDifference<'a, T, S>
+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;
 
@@ -154,15 +150,16 @@ where
 ///
 /// [`par_intersection`]: /hashbrown/struct.HashSet.html#method.par_intersection
 /// [`HashSet`]: /hashbrown/struct.HashSet.html
-pub struct ParIntersection<'a, T, S> {
-    a: &'a HashSet<T, S>,
-    b: &'a HashSet<T, S>,
+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> ParallelIterator for ParIntersection<'a, T, S>
+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;
 
@@ -184,15 +181,16 @@ where
 ///
 /// [`par_union`]: /hashbrown/struct.HashSet.html#method.par_union
 /// [`HashSet`]: /hashbrown/struct.HashSet.html
-pub struct ParUnion<'a, T, S> {
-    a: &'a HashSet<T, S>,
-    b: &'a HashSet<T, S>,
+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> ParallelIterator for ParUnion<'a, T, S>
+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;
 
@@ -200,22 +198,37 @@ where
     where
         C: UnindexedConsumer<Self::Item>,
     {
-        self.a
+        // 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(self.b.par_difference(self.a))
+            .chain(smaller.par_difference(larger))
             .drive_unindexed(consumer)
     }
 }
 
-impl<T, S> HashSet<T, S>
+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> {
+    pub fn par_difference<'a>(&'a self, other: &'a Self) -> ParDifference<'a, T, S, A> {
         ParDifference { a: self, b: other }
     }
 
@@ -225,24 +238,17 @@ where
     pub fn par_symmetric_difference<'a>(
         &'a self,
         other: &'a Self,
-    ) -> ParSymmetricDifference<'a, T, S> {
+    ) -> 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> {
+    pub fn par_intersection<'a>(&'a self, other: &'a Self) -> ParIntersection<'a, T, S, A> {
         ParIntersection { a: self, b: other }
     }
 
-    /// 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> {
-        ParUnion { a: self, b: other }
-    }
-
     /// Returns `true` if `self` has no elements in common with `other`.
     /// This is equivalent to checking for an empty intersection.
     ///
@@ -280,41 +286,47 @@ where
     }
 }
 
-impl<T, S> HashSet<T, S>
+impl<T, S, A> HashSet<T, S, A>
 where
     T: Eq + Hash + Send,
-    S: BuildHasher + 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, S> {
-        ParDrain { set: self }
+    pub fn par_drain(&mut self) -> ParDrain<'_, T, A> {
+        ParDrain {
+            inner: self.map.par_drain(),
+        }
     }
 }
 
-impl<T: Send, S: Send> IntoParallelIterator for HashSet<T, S> {
+impl<T: Send, S, A: Allocator + Clone + Send> IntoParallelIterator for HashSet<T, S, A> {
     type Item = T;
-    type Iter = IntoParIter<T, S>;
+    type Iter = IntoParIter<T, A>;
 
     #[cfg_attr(feature = "inline-more", inline)]
     fn into_par_iter(self) -> Self::Iter {
-        IntoParIter { set: self }
+        IntoParIter {
+            inner: self.map.into_par_iter(),
+        }
     }
 }
 
-impl<'a, T: Sync, S: Sync> IntoParallelIterator for &'a HashSet<T, S> {
+impl<'a, T: Sync, S, A: Allocator + Clone> IntoParallelIterator for &'a HashSet<T, S, A> {
     type Item = &'a T;
-    type Iter = ParIter<'a, T, S>;
+    type Iter = ParIter<'a, T>;
 
     #[cfg_attr(feature = "inline-more", inline)]
     fn into_par_iter(self) -> Self::Iter {
-        ParIter { set: self }
+        ParIter {
+            inner: self.map.par_keys(),
+        }
     }
 }
 
 /// Collect values from a parallel iterator into a hashset.
-impl<T, S> FromParallelIterator<T> for HashSet<T, S>
+impl<T, S> FromParallelIterator<T> for HashSet<T, S, Global>
 where
     T: Eq + Hash + Send,
     S: BuildHasher + Default,
@@ -330,7 +342,7 @@ where
 }
 
 /// Extend a hash set with items from a parallel iterator.
-impl<T, S> ParallelExtend<T> for HashSet<T, S>
+impl<T, S> ParallelExtend<T> for HashSet<T, S, Global>
 where
     T: Eq + Hash + Send,
     S: BuildHasher,
@@ -344,7 +356,7 @@ where
 }
 
 /// Extend a hash set with copied items from a parallel iterator.
-impl<'a, T, S> ParallelExtend<&'a T> for HashSet<T, S>
+impl<'a, T, S> ParallelExtend<&'a T> for HashSet<T, S, Global>
 where
     T: 'a + Copy + Eq + Hash + Sync,
     S: BuildHasher,
@@ -358,12 +370,13 @@ where
 }
 
 // This is equal to the normal `HashSet` -- no custom advantage.
-fn extend<T, S, I>(set: &mut HashSet<T, S>, par_iter: I)
+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>: Extend<I::Item>,
+    HashSet<T, S, A>: Extend<I::Item>,
 {
     let (list, len) = super::helpers::collect(par_iter);