From 486b32152e6c9035ed032b4ba6d1f1dddcd06478 Mon Sep 17 00:00:00 2001 From: Joel Galenson Date: Thu, 1 Apr 2021 16:55:16 -0700 Subject: Upgrade rust/crates/hashbrown to 0.11.2 Test: make Change-Id: I635dccc3bc3cd89b50a49c08f6c7010d0a883e70 --- src/set.rs | 428 +++++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 304 insertions(+), 124 deletions(-) (limited to 'src/set.rs') diff --git a/src/set.rs b/src/set.rs index b8460fd..d59183b 100644 --- a/src/set.rs +++ b/src/set.rs @@ -8,6 +8,7 @@ use core::mem; use core::ops::{BitAnd, BitOr, BitXor, Sub}; use super::map::{self, ConsumeAllOnDrop, DefaultHashBuilder, DrainFilterInner, HashMap, Keys}; +use crate::raw::{Allocator, Global}; // Future Optimization (FIXME!) // ============================= @@ -71,7 +72,7 @@ use super::map::{self, ConsumeAllOnDrop, DefaultHashBuilder, DrainFilterInner, H /// ``` /// /// The easiest way to use `HashSet` with a custom type is to derive -/// [`Eq`] and [`Hash`]. We must also derive [`PartialEq`], this will in the +/// [`Eq`] and [`Hash`]. We must also derive [`PartialEq`]. This will in the /// future be implied by [`Eq`]. /// /// ``` @@ -111,11 +112,11 @@ use super::map::{self, ConsumeAllOnDrop, DefaultHashBuilder, DrainFilterInner, H /// [`HashMap`]: struct.HashMap.html /// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html /// [`RefCell`]: https://doc.rust-lang.org/std/cell/struct.RefCell.html -pub struct HashSet { - pub(crate) map: HashMap, +pub struct HashSet { + pub(crate) map: HashMap, } -impl Clone for HashSet { +impl Clone for HashSet { fn clone(&self) -> Self { HashSet { map: self.map.clone(), @@ -167,73 +168,47 @@ impl HashSet { } } -impl HashSet { - /// Creates a new empty hash set which will use the given hasher to hash - /// keys. - /// - /// The hash set is also created with the default initial capacity. - /// - /// Warning: `hasher` is normally randomly generated, and - /// is designed to allow `HashSet`s to be resistant to attacks that - /// cause many collisions and very poor performance. Setting it - /// manually using this function can expose a DoS attack vector. - /// - /// The `hash_builder` passed should implement the [`BuildHasher`] trait for - /// the HashMap to be useful, see its documentation for details. +#[cfg(feature = "ahash")] +impl HashSet { + /// Creates an empty `HashSet`. /// + /// The hash set is initially created with a capacity of 0, so it will not allocate until it + /// is first inserted into. /// /// # Examples /// /// ``` /// use hashbrown::HashSet; - /// use hashbrown::hash_map::DefaultHashBuilder; - /// - /// let s = DefaultHashBuilder::default(); - /// let mut set = HashSet::with_hasher(s); - /// set.insert(2); + /// let set: HashSet = HashSet::new(); /// ``` - /// - /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html #[cfg_attr(feature = "inline-more", inline)] - pub const fn with_hasher(hasher: S) -> Self { + pub fn new_in(alloc: A) -> Self { Self { - map: HashMap::with_hasher(hasher), + map: HashMap::new_in(alloc), } } - /// Creates an empty `HashSet` with the specified capacity, using - /// `hasher` to hash the keys. + /// Creates an empty `HashSet` with the specified capacity. /// /// The hash set will be able to hold at least `capacity` elements without /// reallocating. If `capacity` is 0, the hash set will not allocate. /// - /// Warning: `hasher` is normally randomly generated, and - /// is designed to allow `HashSet`s to be resistant to attacks that - /// cause many collisions and very poor performance. Setting it - /// manually using this function can expose a DoS attack vector. - /// - /// The `hash_builder` passed should implement the [`BuildHasher`] trait for - /// the HashMap to be useful, see its documentation for details. - /// /// # Examples /// /// ``` /// use hashbrown::HashSet; - /// use hashbrown::hash_map::DefaultHashBuilder; - /// - /// let s = DefaultHashBuilder::default(); - /// let mut set = HashSet::with_capacity_and_hasher(10, s); - /// set.insert(1); + /// let set: HashSet = HashSet::with_capacity(10); + /// assert!(set.capacity() >= 10); /// ``` - /// - /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html #[cfg_attr(feature = "inline-more", inline)] - pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self { + pub fn with_capacity_in(capacity: usize, alloc: A) -> Self { Self { - map: HashMap::with_capacity_and_hasher(capacity, hasher), + map: HashMap::with_capacity_in(capacity, alloc), } } +} +impl HashSet { /// Returns the number of elements the set can hold without reallocating. /// /// # Examples @@ -323,7 +298,7 @@ impl HashSet { /// assert!(set.is_empty()); /// ``` #[cfg_attr(feature = "inline-more", inline)] - pub fn drain(&mut self) -> Drain<'_, T> { + pub fn drain(&mut self) -> Drain<'_, T, A> { Drain { iter: self.map.drain(), } @@ -376,7 +351,7 @@ impl HashSet { /// assert_eq!(odds, vec![1, 3, 5, 7]); /// ``` #[cfg_attr(feature = "inline-more", inline)] - pub fn drain_filter(&mut self, f: F) -> DrainFilter<'_, T, F> + pub fn drain_filter(&mut self, f: F) -> DrainFilter<'_, T, F, A> where F: FnMut(&T) -> bool, { @@ -405,6 +380,134 @@ impl HashSet { pub fn clear(&mut self) { self.map.clear() } +} + +impl HashSet { + /// Creates a new empty hash set which will use the given hasher to hash + /// keys. + /// + /// The hash set is also created with the default initial capacity. + /// + /// Warning: `hasher` is normally randomly generated, and + /// is designed to allow `HashSet`s to be resistant to attacks that + /// cause many collisions and very poor performance. Setting it + /// manually using this function can expose a DoS attack vector. + /// + /// The `hash_builder` passed should implement the [`BuildHasher`] trait for + /// the HashMap to be useful, see its documentation for details. + /// + /// + /// # Examples + /// + /// ``` + /// use hashbrown::HashSet; + /// use hashbrown::hash_map::DefaultHashBuilder; + /// + /// let s = DefaultHashBuilder::default(); + /// let mut set = HashSet::with_hasher(s); + /// set.insert(2); + /// ``` + /// + /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html + #[cfg_attr(feature = "inline-more", inline)] + pub const fn with_hasher(hasher: S) -> Self { + Self { + map: HashMap::with_hasher(hasher), + } + } + + /// Creates an empty `HashSet` with the specified capacity, using + /// `hasher` to hash the keys. + /// + /// The hash set will be able to hold at least `capacity` elements without + /// reallocating. If `capacity` is 0, the hash set will not allocate. + /// + /// Warning: `hasher` is normally randomly generated, and + /// is designed to allow `HashSet`s to be resistant to attacks that + /// cause many collisions and very poor performance. Setting it + /// manually using this function can expose a DoS attack vector. + /// + /// The `hash_builder` passed should implement the [`BuildHasher`] trait for + /// the HashMap to be useful, see its documentation for details. + /// + /// # Examples + /// + /// ``` + /// use hashbrown::HashSet; + /// use hashbrown::hash_map::DefaultHashBuilder; + /// + /// let s = DefaultHashBuilder::default(); + /// let mut set = HashSet::with_capacity_and_hasher(10, s); + /// set.insert(1); + /// ``` + /// + /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html + #[cfg_attr(feature = "inline-more", inline)] + pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self { + Self { + map: HashMap::with_capacity_and_hasher(capacity, hasher), + } + } +} + +impl HashSet +where + A: Allocator + Clone, +{ + /// Creates a new empty hash set which will use the given hasher to hash + /// keys. + /// + /// The hash set is also created with the default initial capacity. + /// + /// Warning: `hasher` is normally randomly generated, and + /// is designed to allow `HashSet`s to be resistant to attacks that + /// cause many collisions and very poor performance. Setting it + /// manually using this function can expose a DoS attack vector. + /// + /// # Examples + /// + /// ``` + /// use hashbrown::HashSet; + /// use hashbrown::hash_map::DefaultHashBuilder; + /// + /// let s = DefaultHashBuilder::default(); + /// let mut set = HashSet::with_hasher(s); + /// set.insert(2); + /// ``` + #[cfg_attr(feature = "inline-more", inline)] + pub fn with_hasher_in(hasher: S, alloc: A) -> Self { + Self { + map: HashMap::with_hasher_in(hasher, alloc), + } + } + + /// Creates an empty `HashSet` with the specified capacity, using + /// `hasher` to hash the keys. + /// + /// The hash set will be able to hold at least `capacity` elements without + /// reallocating. If `capacity` is 0, the hash set will not allocate. + /// + /// Warning: `hasher` is normally randomly generated, and + /// is designed to allow `HashSet`s to be resistant to attacks that + /// cause many collisions and very poor performance. Setting it + /// manually using this function can expose a DoS attack vector. + /// + /// # Examples + /// + /// ``` + /// use hashbrown::HashSet; + /// use hashbrown::hash_map::DefaultHashBuilder; + /// + /// let s = DefaultHashBuilder::default(); + /// let mut set = HashSet::with_capacity_and_hasher(10, s); + /// set.insert(1); + /// ``` + #[cfg_attr(feature = "inline-more", inline)] + pub fn with_capacity_and_hasher_in(capacity: usize, hasher: S, alloc: A) -> Self { + Self { + map: HashMap::with_capacity_and_hasher_in(capacity, hasher, alloc), + } + } /// Returns a reference to the set's [`BuildHasher`]. /// @@ -426,10 +529,11 @@ impl HashSet { } } -impl HashSet +impl HashSet where T: Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { /// Reserves capacity for at least `additional` more elements to be inserted /// in the `HashSet`. The collection may reserve more space to avoid @@ -544,7 +648,7 @@ where /// assert_eq!(diff, [4].iter().collect()); /// ``` #[cfg_attr(feature = "inline-more", inline)] - pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T, S> { + pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T, S, A> { Difference { iter: self.iter(), other, @@ -573,7 +677,7 @@ where /// assert_eq!(diff1, [1, 4].iter().collect()); /// ``` #[cfg_attr(feature = "inline-more", inline)] - pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T, S> { + pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T, S, A> { SymmetricDifference { iter: self.difference(other).chain(other.difference(self)), } @@ -598,7 +702,7 @@ where /// assert_eq!(intersection, [2, 3].iter().collect()); /// ``` #[cfg_attr(feature = "inline-more", inline)] - pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T, S> { + pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T, S, A> { let (smaller, larger) = if self.len() <= other.len() { (self, other) } else { @@ -629,8 +733,10 @@ where /// assert_eq!(union, [1, 2, 3, 4].iter().collect()); /// ``` #[cfg_attr(feature = "inline-more", inline)] - pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T, S> { - let (smaller, larger) = if self.len() >= other.len() { + pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T, S, 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.len() <= other.len() { (self, other) } else { (other, self) @@ -967,10 +1073,11 @@ where } } -impl PartialEq for HashSet +impl PartialEq for HashSet where T: Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { fn eq(&self, other: &Self) -> bool { if self.len() != other.len() { @@ -981,40 +1088,53 @@ where } } -impl Eq for HashSet +impl Eq for HashSet where T: Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { } -impl fmt::Debug for HashSet +impl fmt::Debug for HashSet where T: Eq + Hash + fmt::Debug, S: BuildHasher, + A: Allocator + Clone, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_set().entries(self.iter()).finish() } } -impl FromIterator for HashSet +impl From> for HashSet +where + A: Allocator + Clone, +{ + fn from(map: HashMap) -> Self { + Self { map } + } +} + +impl FromIterator for HashSet where T: Eq + Hash, S: BuildHasher + Default, + A: Default + Allocator + Clone, { #[cfg_attr(feature = "inline-more", inline)] fn from_iter>(iter: I) -> Self { - let mut set = Self::with_hasher(Default::default()); + let mut set = Self::with_hasher_in(Default::default(), Default::default()); set.extend(iter); set } } -impl Extend for HashSet +impl Extend for HashSet where T: Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { #[cfg_attr(feature = "inline-more", inline)] fn extend>(&mut self, iter: I) { @@ -1034,10 +1154,11 @@ where } } -impl<'a, T, S> Extend<&'a T> for HashSet +impl<'a, T, S, A> Extend<&'a T> for HashSet where T: 'a + Eq + Hash + Copy, S: BuildHasher, + A: Allocator + Clone, { #[cfg_attr(feature = "inline-more", inline)] fn extend>(&mut self, iter: I) { @@ -1057,9 +1178,10 @@ where } } -impl Default for HashSet +impl Default for HashSet where S: Default, + A: Default + Allocator + Clone, { /// Creates an empty `HashSet` with the `Default` value for the hasher. #[cfg_attr(feature = "inline-more", inline)] @@ -1070,10 +1192,11 @@ where } } -impl BitOr<&HashSet> for &HashSet +impl BitOr<&HashSet> for &HashSet where T: Eq + Hash + Clone, S: BuildHasher + Default, + A: Allocator + Clone, { type Output = HashSet; @@ -1097,15 +1220,16 @@ where /// } /// assert_eq!(i, expected.len()); /// ``` - fn bitor(self, rhs: &HashSet) -> HashSet { + fn bitor(self, rhs: &HashSet) -> HashSet { self.union(rhs).cloned().collect() } } -impl BitAnd<&HashSet> for &HashSet +impl BitAnd<&HashSet> for &HashSet where T: Eq + Hash + Clone, S: BuildHasher + Default, + A: Allocator + Clone, { type Output = HashSet; @@ -1129,7 +1253,7 @@ where /// } /// assert_eq!(i, expected.len()); /// ``` - fn bitand(self, rhs: &HashSet) -> HashSet { + fn bitand(self, rhs: &HashSet) -> HashSet { self.intersection(rhs).cloned().collect() } } @@ -1216,8 +1340,8 @@ pub struct Iter<'a, K> { /// /// [`HashSet`]: struct.HashSet.html /// [`into_iter`]: struct.HashSet.html#method.into_iter -pub struct IntoIter { - iter: map::IntoIter, +pub struct IntoIter { + iter: map::IntoIter, } /// A draining iterator over the items of a `HashSet`. @@ -1227,8 +1351,8 @@ pub struct IntoIter { /// /// [`HashSet`]: struct.HashSet.html /// [`drain`]: struct.HashSet.html#method.drain -pub struct Drain<'a, K> { - iter: map::Drain<'a, K, ()>, +pub struct Drain<'a, K, A: Allocator + Clone = Global> { + iter: map::Drain<'a, K, (), A>, } /// A draining iterator over entries of a `HashSet` which don't satisfy the predicate `f`. @@ -1238,12 +1362,12 @@ pub struct Drain<'a, K> { /// /// [`drain_filter`]: struct.HashSet.html#method.drain_filter /// [`HashSet`]: struct.HashSet.html -pub struct DrainFilter<'a, K, F> +pub struct DrainFilter<'a, K, F, A: Allocator + Clone = Global> where F: FnMut(&K) -> bool, { f: F, - inner: DrainFilterInner<'a, K, ()>, + inner: DrainFilterInner<'a, K, (), A>, } /// A lazy iterator producing elements in the intersection of `HashSet`s. @@ -1253,11 +1377,11 @@ where /// /// [`HashSet`]: struct.HashSet.html /// [`intersection`]: struct.HashSet.html#method.intersection -pub struct Intersection<'a, T, S> { +pub struct Intersection<'a, T, S, A: Allocator + Clone = Global> { // iterator of the first set iter: Iter<'a, T>, // the second set - other: &'a HashSet, + other: &'a HashSet, } /// A lazy iterator producing elements in the difference of `HashSet`s. @@ -1267,11 +1391,11 @@ pub struct Intersection<'a, T, S> { /// /// [`HashSet`]: struct.HashSet.html /// [`difference`]: struct.HashSet.html#method.difference -pub struct Difference<'a, T, S> { +pub struct Difference<'a, T, S, A: Allocator + Clone = Global> { // iterator of the first set iter: Iter<'a, T>, // the second set - other: &'a HashSet, + other: &'a HashSet, } /// A lazy iterator producing elements in the symmetric difference of `HashSet`s. @@ -1281,8 +1405,8 @@ pub struct Difference<'a, T, S> { /// /// [`HashSet`]: struct.HashSet.html /// [`symmetric_difference`]: struct.HashSet.html#method.symmetric_difference -pub struct SymmetricDifference<'a, T, S> { - iter: Chain, Difference<'a, T, S>>, +pub struct SymmetricDifference<'a, T, S, A: Allocator + Clone = Global> { + iter: Chain, Difference<'a, T, S, A>>, } /// A lazy iterator producing elements in the union of `HashSet`s. @@ -1292,11 +1416,11 @@ pub struct SymmetricDifference<'a, T, S> { /// /// [`HashSet`]: struct.HashSet.html /// [`union`]: struct.HashSet.html#method.union -pub struct Union<'a, T, S> { - iter: Chain, Difference<'a, T, S>>, +pub struct Union<'a, T, S, A: Allocator + Clone = Global> { + iter: Chain, Difference<'a, T, S, A>>, } -impl<'a, T, S> IntoIterator for &'a HashSet { +impl<'a, T, S, A: Allocator + Clone> IntoIterator for &'a HashSet { type Item = &'a T; type IntoIter = Iter<'a, T>; @@ -1306,9 +1430,9 @@ impl<'a, T, S> IntoIterator for &'a HashSet { } } -impl IntoIterator for HashSet { +impl IntoIterator for HashSet { type Item = T; - type IntoIter = IntoIter; + type IntoIter = IntoIter; /// Creates a consuming iterator, that is, one that moves each value out /// of the set in arbitrary order. The set cannot be used after calling @@ -1331,7 +1455,7 @@ impl IntoIterator for HashSet { /// } /// ``` #[cfg_attr(feature = "inline-more", inline)] - fn into_iter(self) -> IntoIter { + fn into_iter(self) -> IntoIter { IntoIter { iter: self.map.into_iter(), } @@ -1372,7 +1496,7 @@ impl fmt::Debug for Iter<'_, K> { } } -impl Iterator for IntoIter { +impl Iterator for IntoIter { type Item = K; #[cfg_attr(feature = "inline-more", inline)] @@ -1388,22 +1512,22 @@ impl Iterator for IntoIter { self.iter.size_hint() } } -impl ExactSizeIterator for IntoIter { +impl ExactSizeIterator for IntoIter { #[cfg_attr(feature = "inline-more", inline)] fn len(&self) -> usize { self.iter.len() } } -impl FusedIterator for IntoIter {} +impl FusedIterator for IntoIter {} -impl fmt::Debug for IntoIter { +impl fmt::Debug for IntoIter { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { let entries_iter = self.iter.iter().map(|(k, _)| k); f.debug_list().entries(entries_iter).finish() } } -impl Iterator for Drain<'_, K> { +impl Iterator for Drain<'_, K, A> { type Item = K; #[cfg_attr(feature = "inline-more", inline)] @@ -1419,22 +1543,22 @@ impl Iterator for Drain<'_, K> { self.iter.size_hint() } } -impl ExactSizeIterator for Drain<'_, K> { +impl ExactSizeIterator for Drain<'_, K, A> { #[cfg_attr(feature = "inline-more", inline)] fn len(&self) -> usize { self.iter.len() } } -impl FusedIterator for Drain<'_, K> {} +impl FusedIterator for Drain<'_, K, A> {} -impl fmt::Debug for Drain<'_, K> { +impl fmt::Debug for Drain<'_, K, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { let entries_iter = self.iter.iter().map(|(k, _)| k); f.debug_list().entries(entries_iter).finish() } } -impl<'a, K, F> Drop for DrainFilter<'a, K, F> +impl<'a, K, F, A: Allocator + Clone> Drop for DrainFilter<'a, K, F, A> where F: FnMut(&K) -> bool, { @@ -1448,7 +1572,7 @@ where } } -impl Iterator for DrainFilter<'_, K, F> +impl Iterator for DrainFilter<'_, K, F, A> where F: FnMut(&K) -> bool, { @@ -1467,9 +1591,12 @@ where } } -impl FusedIterator for DrainFilter<'_, K, F> where F: FnMut(&K) -> bool {} +impl FusedIterator for DrainFilter<'_, K, F, A> where + F: FnMut(&K) -> bool +{ +} -impl Clone for Intersection<'_, T, S> { +impl Clone for Intersection<'_, T, S, A> { #[cfg_attr(feature = "inline-more", inline)] fn clone(&self) -> Self { Intersection { @@ -1479,10 +1606,11 @@ impl Clone for Intersection<'_, T, S> { } } -impl<'a, T, S> Iterator for Intersection<'a, T, S> +impl<'a, T, S, A> Iterator for Intersection<'a, T, S, A> where T: Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { type Item = &'a T; @@ -1503,24 +1631,26 @@ where } } -impl fmt::Debug for Intersection<'_, T, S> +impl fmt::Debug for Intersection<'_, T, S, A> where T: fmt::Debug + Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.clone()).finish() } } -impl FusedIterator for Intersection<'_, T, S> +impl FusedIterator for Intersection<'_, T, S, A> where T: Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { } -impl Clone for Difference<'_, T, S> { +impl Clone for Difference<'_, T, S, A> { #[cfg_attr(feature = "inline-more", inline)] fn clone(&self) -> Self { Difference { @@ -1530,10 +1660,11 @@ impl Clone for Difference<'_, T, S> { } } -impl<'a, T, S> Iterator for Difference<'a, T, S> +impl<'a, T, S, A> Iterator for Difference<'a, T, S, A> where T: Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { type Item = &'a T; @@ -1554,24 +1685,26 @@ where } } -impl FusedIterator for Difference<'_, T, S> +impl FusedIterator for Difference<'_, T, S, A> where T: Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { } -impl fmt::Debug for Difference<'_, T, S> +impl fmt::Debug for Difference<'_, T, S, A> where T: fmt::Debug + Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.clone()).finish() } } -impl Clone for SymmetricDifference<'_, T, S> { +impl Clone for SymmetricDifference<'_, T, S, A> { #[cfg_attr(feature = "inline-more", inline)] fn clone(&self) -> Self { SymmetricDifference { @@ -1580,10 +1713,11 @@ impl Clone for SymmetricDifference<'_, T, S> { } } -impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S> +impl<'a, T, S, A> Iterator for SymmetricDifference<'a, T, S, A> where T: Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { type Item = &'a T; @@ -1597,24 +1731,26 @@ where } } -impl FusedIterator for SymmetricDifference<'_, T, S> +impl FusedIterator for SymmetricDifference<'_, T, S, A> where T: Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { } -impl fmt::Debug for SymmetricDifference<'_, T, S> +impl fmt::Debug for SymmetricDifference<'_, T, S, A> where T: fmt::Debug + Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.clone()).finish() } } -impl Clone for Union<'_, T, S> { +impl Clone for Union<'_, T, S, A> { #[cfg_attr(feature = "inline-more", inline)] fn clone(&self) -> Self { Union { @@ -1623,27 +1759,30 @@ impl Clone for Union<'_, T, S> { } } -impl FusedIterator for Union<'_, T, S> +impl FusedIterator for Union<'_, T, S, A> where T: Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { } -impl fmt::Debug for Union<'_, T, S> +impl fmt::Debug for Union<'_, T, S, A> where T: fmt::Debug + Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.clone()).finish() } } -impl<'a, T, S> Iterator for Union<'a, T, S> +impl<'a, T, S, A> Iterator for Union<'a, T, S, A> where T: Eq + Hash, S: BuildHasher, + A: Allocator + Clone, { type Item = &'a T; @@ -1665,30 +1804,34 @@ fn assert_covariance() { fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> { v } - fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> { + fn into_iter<'new, A: Allocator + Clone>( + v: IntoIter<&'static str, A>, + ) -> IntoIter<&'new str, A> { v } - fn difference<'a, 'new>( - v: Difference<'a, &'static str, DefaultHashBuilder>, - ) -> Difference<'a, &'new str, DefaultHashBuilder> { + fn difference<'a, 'new, A: Allocator + Clone>( + v: Difference<'a, &'static str, DefaultHashBuilder, A>, + ) -> Difference<'a, &'new str, DefaultHashBuilder, A> { v } - fn symmetric_difference<'a, 'new>( - v: SymmetricDifference<'a, &'static str, DefaultHashBuilder>, - ) -> SymmetricDifference<'a, &'new str, DefaultHashBuilder> { + fn symmetric_difference<'a, 'new, A: Allocator + Clone>( + v: SymmetricDifference<'a, &'static str, DefaultHashBuilder, A>, + ) -> SymmetricDifference<'a, &'new str, DefaultHashBuilder, A> { v } - fn intersection<'a, 'new>( - v: Intersection<'a, &'static str, DefaultHashBuilder>, - ) -> Intersection<'a, &'new str, DefaultHashBuilder> { + fn intersection<'a, 'new, A: Allocator + Clone>( + v: Intersection<'a, &'static str, DefaultHashBuilder, A>, + ) -> Intersection<'a, &'new str, DefaultHashBuilder, A> { v } - fn union<'a, 'new>( - v: Union<'a, &'static str, DefaultHashBuilder>, - ) -> Union<'a, &'new str, DefaultHashBuilder> { + fn union<'a, 'new, A: Allocator + Clone>( + v: Union<'a, &'static str, DefaultHashBuilder, A>, + ) -> Union<'a, &'new str, DefaultHashBuilder, A> { v } - fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> { + fn drain<'new, A: Allocator + Clone>( + d: Drain<'static, &'static str, A>, + ) -> Drain<'new, &'new str, A> { d } } @@ -1904,6 +2047,23 @@ mod test_set { assert_eq!(i, expected.len()); } + #[test] + fn test_from_map() { + let mut a = crate::HashMap::new(); + a.insert(1, ()); + a.insert(2, ()); + a.insert(3, ()); + a.insert(4, ()); + + let a: HashSet<_> = a.into(); + + assert_eq!(a.len(), 4); + assert!(a.contains(&1)); + assert!(a.contains(&2)); + assert!(a.contains(&3)); + assert!(a.contains(&4)); + } + #[test] fn test_from_iter() { let xs = [1, 2, 2, 3, 4, 5, 6, 7, 8, 9]; @@ -2116,4 +2276,24 @@ mod test_set { set.insert(19); assert!(set.contains(&19)); } + + #[test] + fn rehash_in_place() { + let mut set = HashSet::new(); + + for i in 0..224 { + set.insert(i); + } + + assert_eq!( + set.capacity(), + 224, + "The set must be at or close to capacity to trigger a re hashing" + ); + + for i in 100..1400 { + set.remove(&(i - 100)); + set.insert(i); + } + } } -- cgit v1.2.3