diff options
Diffstat (limited to 'vendor/hashbrown/src/set.rs')
-rw-r--r-- | vendor/hashbrown/src/set.rs | 154 |
1 files changed, 76 insertions, 78 deletions
diff --git a/vendor/hashbrown/src/set.rs b/vendor/hashbrown/src/set.rs index 52f6fdaf2..09b45fd9f 100644 --- a/vendor/hashbrown/src/set.rs +++ b/vendor/hashbrown/src/set.rs @@ -7,8 +7,8 @@ use core::hash::{BuildHasher, Hash}; use core::iter::{Chain, FromIterator, FusedIterator}; use core::ops::{BitAnd, BitOr, BitXor, Sub}; -use super::map::{self, DefaultHashBuilder, ExtractIfInner, HashMap, Keys}; -use crate::raw::{Allocator, Global}; +use super::map::{self, DefaultHashBuilder, HashMap, Keys}; +use crate::raw::{Allocator, Global, RawExtractIf}; // Future Optimization (FIXME!) // ============================= @@ -112,7 +112,7 @@ use crate::raw::{Allocator, Global}; /// [`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<T, S = DefaultHashBuilder, A: Allocator + Clone = Global> { +pub struct HashSet<T, S = DefaultHashBuilder, A: Allocator = Global> { pub(crate) map: HashMap<T, (), S, A>, } @@ -193,7 +193,7 @@ impl<T> HashSet<T, DefaultHashBuilder> { } #[cfg(feature = "ahash")] -impl<T: Hash + Eq, A: Allocator + Clone> HashSet<T, DefaultHashBuilder, A> { +impl<T: Hash + Eq, A: Allocator> HashSet<T, DefaultHashBuilder, A> { /// Creates an empty `HashSet`. /// /// The hash set is initially created with a capacity of 0, so it will not allocate until it @@ -256,7 +256,7 @@ impl<T: Hash + Eq, A: Allocator + Clone> HashSet<T, DefaultHashBuilder, A> { } } -impl<T, S, A: Allocator + Clone> HashSet<T, S, A> { +impl<T, S, A: Allocator> HashSet<T, S, A> { /// Returns the number of elements the set can hold without reallocating. /// /// # Examples @@ -383,6 +383,8 @@ impl<T, S, A: Allocator + Clone> HashSet<T, S, A> { /// or the iteration short-circuits, then the remaining elements will be retained. /// Use [`retain()`] with a negated predicate if you do not need the returned iterator. /// + /// [`retain()`]: HashSet::retain + /// /// # Examples /// /// ``` @@ -406,7 +408,7 @@ impl<T, S, A: Allocator + Clone> HashSet<T, S, A> { { ExtractIf { f, - inner: ExtractIfInner { + inner: RawExtractIf { iter: unsafe { self.map.table.iter() }, table: &mut self.map.table, }, @@ -511,7 +513,7 @@ impl<T, S> HashSet<T, S, Global> { impl<T, S, A> HashSet<T, S, A> where - A: Allocator + Clone, + A: Allocator, { /// Returns a reference to the underlying allocator. #[inline] @@ -619,7 +621,7 @@ impl<T, S, A> HashSet<T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { /// Reserves capacity for at least `additional` more elements to be inserted /// in the `HashSet`. The collection may reserve more space to avoid @@ -1223,7 +1225,7 @@ where } } -impl<T, S, A: Allocator + Clone> HashSet<T, S, A> { +impl<T, S, A: Allocator> HashSet<T, S, A> { /// Returns a reference to the [`RawTable`] used underneath [`HashSet`]. /// This function is only available if the `raw` feature of the crate is enabled. /// @@ -1269,7 +1271,7 @@ impl<T, S, A> PartialEq for HashSet<T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { fn eq(&self, other: &Self) -> bool { if self.len() != other.len() { @@ -1284,14 +1286,14 @@ impl<T, S, A> Eq for HashSet<T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { } impl<T, S, A> fmt::Debug for HashSet<T, S, A> where T: fmt::Debug, - A: Allocator + Clone, + A: Allocator, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_set().entries(self.iter()).finish() @@ -1300,7 +1302,7 @@ where impl<T, S, A> From<HashMap<T, (), S, A>> for HashSet<T, S, A> where - A: Allocator + Clone, + A: Allocator, { fn from(map: HashMap<T, (), S, A>) -> Self { Self { map } @@ -1311,7 +1313,7 @@ impl<T, S, A> FromIterator<T> for HashSet<T, S, A> where T: Eq + Hash, S: BuildHasher + Default, - A: Default + Allocator + Clone, + A: Default + Allocator, { #[cfg_attr(feature = "inline-more", inline)] fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { @@ -1326,7 +1328,7 @@ where impl<T, A, const N: usize> From<[T; N]> for HashSet<T, DefaultHashBuilder, A> where T: Eq + Hash, - A: Default + Allocator + Clone, + A: Default + Allocator, { /// # Examples /// @@ -1346,7 +1348,7 @@ impl<T, S, A> Extend<T> for HashSet<T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { #[cfg_attr(feature = "inline-more", inline)] fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { @@ -1370,7 +1372,7 @@ impl<'a, T, S, A> Extend<&'a T> for HashSet<T, S, A> where T: 'a + Eq + Hash + Copy, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { #[cfg_attr(feature = "inline-more", inline)] fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { @@ -1393,7 +1395,7 @@ where impl<T, S, A> Default for HashSet<T, S, A> where S: Default, - A: Default + Allocator + Clone, + A: Default + Allocator, { /// Creates an empty `HashSet<T, S>` with the `Default` value for the hasher. #[cfg_attr(feature = "inline-more", inline)] @@ -1408,7 +1410,7 @@ impl<T, S, A> BitOr<&HashSet<T, S, A>> for &HashSet<T, S, A> where T: Eq + Hash + Clone, S: BuildHasher + Default, - A: Allocator + Clone, + A: Allocator, { type Output = HashSet<T, S>; @@ -1441,7 +1443,7 @@ impl<T, S, A> BitAnd<&HashSet<T, S, A>> for &HashSet<T, S, A> where T: Eq + Hash + Clone, S: BuildHasher + Default, - A: Allocator + Clone, + A: Allocator, { type Output = HashSet<T, S>; @@ -1552,7 +1554,7 @@ pub struct Iter<'a, K> { /// /// [`HashSet`]: struct.HashSet.html /// [`into_iter`]: struct.HashSet.html#method.into_iter -pub struct IntoIter<K, A: Allocator + Clone = Global> { +pub struct IntoIter<K, A: Allocator = Global> { iter: map::IntoIter<K, (), A>, } @@ -1563,7 +1565,7 @@ pub struct IntoIter<K, A: Allocator + Clone = Global> { /// /// [`HashSet`]: struct.HashSet.html /// [`drain`]: struct.HashSet.html#method.drain -pub struct Drain<'a, K, A: Allocator + Clone = Global> { +pub struct Drain<'a, K, A: Allocator = Global> { iter: map::Drain<'a, K, (), A>, } @@ -1575,12 +1577,12 @@ pub struct Drain<'a, K, A: Allocator + Clone = Global> { /// [`extract_if`]: struct.HashSet.html#method.extract_if /// [`HashSet`]: struct.HashSet.html #[must_use = "Iterators are lazy unless consumed"] -pub struct ExtractIf<'a, K, F, A: Allocator + Clone = Global> +pub struct ExtractIf<'a, K, F, A: Allocator = Global> where F: FnMut(&K) -> bool, { f: F, - inner: ExtractIfInner<'a, K, (), A>, + inner: RawExtractIf<'a, (K, ()), A>, } /// A lazy iterator producing elements in the intersection of `HashSet`s. @@ -1590,7 +1592,7 @@ where /// /// [`HashSet`]: struct.HashSet.html /// [`intersection`]: struct.HashSet.html#method.intersection -pub struct Intersection<'a, T, S, A: Allocator + Clone = Global> { +pub struct Intersection<'a, T, S, A: Allocator = Global> { // iterator of the first set iter: Iter<'a, T>, // the second set @@ -1604,7 +1606,7 @@ pub struct Intersection<'a, T, S, A: Allocator + Clone = Global> { /// /// [`HashSet`]: struct.HashSet.html /// [`difference`]: struct.HashSet.html#method.difference -pub struct Difference<'a, T, S, A: Allocator + Clone = Global> { +pub struct Difference<'a, T, S, A: Allocator = Global> { // iterator of the first set iter: Iter<'a, T>, // the second set @@ -1618,7 +1620,7 @@ pub struct Difference<'a, T, S, A: Allocator + Clone = Global> { /// /// [`HashSet`]: struct.HashSet.html /// [`symmetric_difference`]: struct.HashSet.html#method.symmetric_difference -pub struct SymmetricDifference<'a, T, S, A: Allocator + Clone = Global> { +pub struct SymmetricDifference<'a, T, S, A: Allocator = Global> { iter: Chain<Difference<'a, T, S, A>, Difference<'a, T, S, A>>, } @@ -1629,11 +1631,11 @@ pub struct SymmetricDifference<'a, T, S, A: Allocator + Clone = Global> { /// /// [`HashSet`]: struct.HashSet.html /// [`union`]: struct.HashSet.html#method.union -pub struct Union<'a, T, S, A: Allocator + Clone = Global> { +pub struct Union<'a, T, S, A: Allocator = Global> { iter: Chain<Iter<'a, T>, Difference<'a, T, S, A>>, } -impl<'a, T, S, A: Allocator + Clone> IntoIterator for &'a HashSet<T, S, A> { +impl<'a, T, S, A: Allocator> IntoIterator for &'a HashSet<T, S, A> { type Item = &'a T; type IntoIter = Iter<'a, T>; @@ -1643,7 +1645,7 @@ impl<'a, T, S, A: Allocator + Clone> IntoIterator for &'a HashSet<T, S, A> { } } -impl<T, S, A: Allocator + Clone> IntoIterator for HashSet<T, S, A> { +impl<T, S, A: Allocator> IntoIterator for HashSet<T, S, A> { type Item = T; type IntoIter = IntoIter<T, A>; @@ -1709,7 +1711,7 @@ impl<K: fmt::Debug> fmt::Debug for Iter<'_, K> { } } -impl<K, A: Allocator + Clone> Iterator for IntoIter<K, A> { +impl<K, A: Allocator> Iterator for IntoIter<K, A> { type Item = K; #[cfg_attr(feature = "inline-more", inline)] @@ -1725,22 +1727,22 @@ impl<K, A: Allocator + Clone> Iterator for IntoIter<K, A> { self.iter.size_hint() } } -impl<K, A: Allocator + Clone> ExactSizeIterator for IntoIter<K, A> { +impl<K, A: Allocator> ExactSizeIterator for IntoIter<K, A> { #[cfg_attr(feature = "inline-more", inline)] fn len(&self) -> usize { self.iter.len() } } -impl<K, A: Allocator + Clone> FusedIterator for IntoIter<K, A> {} +impl<K, A: Allocator> FusedIterator for IntoIter<K, A> {} -impl<K: fmt::Debug, A: Allocator + Clone> fmt::Debug for IntoIter<K, A> { +impl<K: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<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<K, A: Allocator + Clone> Iterator for Drain<'_, K, A> { +impl<K, A: Allocator> Iterator for Drain<'_, K, A> { type Item = K; #[cfg_attr(feature = "inline-more", inline)] @@ -1756,22 +1758,22 @@ impl<K, A: Allocator + Clone> Iterator for Drain<'_, K, A> { self.iter.size_hint() } } -impl<K, A: Allocator + Clone> ExactSizeIterator for Drain<'_, K, A> { +impl<K, A: Allocator> ExactSizeIterator for Drain<'_, K, A> { #[cfg_attr(feature = "inline-more", inline)] fn len(&self) -> usize { self.iter.len() } } -impl<K, A: Allocator + Clone> FusedIterator for Drain<'_, K, A> {} +impl<K, A: Allocator> FusedIterator for Drain<'_, K, A> {} -impl<K: fmt::Debug, A: Allocator + Clone> fmt::Debug for Drain<'_, K, A> { +impl<K: fmt::Debug, A: Allocator> 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<K, F, A: Allocator + Clone> Iterator for ExtractIf<'_, K, F, A> +impl<K, F, A: Allocator> Iterator for ExtractIf<'_, K, F, A> where F: FnMut(&K) -> bool, { @@ -1779,9 +1781,9 @@ where #[cfg_attr(feature = "inline-more", inline)] fn next(&mut self) -> Option<Self::Item> { - let f = &mut self.f; - let (k, _) = self.inner.next(&mut |k, _| f(k))?; - Some(k) + self.inner + .next(|&mut (ref k, ())| (self.f)(k)) + .map(|(k, ())| k) } #[inline] @@ -1790,9 +1792,9 @@ where } } -impl<K, F, A: Allocator + Clone> FusedIterator for ExtractIf<'_, K, F, A> where F: FnMut(&K) -> bool {} +impl<K, F, A: Allocator> FusedIterator for ExtractIf<'_, K, F, A> where F: FnMut(&K) -> bool {} -impl<T, S, A: Allocator + Clone> Clone for Intersection<'_, T, S, A> { +impl<T, S, A: Allocator> Clone for Intersection<'_, T, S, A> { #[cfg_attr(feature = "inline-more", inline)] fn clone(&self) -> Self { Intersection { @@ -1806,7 +1808,7 @@ impl<'a, T, S, A> Iterator for Intersection<'a, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { type Item = &'a T; @@ -1831,7 +1833,7 @@ impl<T, S, A> fmt::Debug for Intersection<'_, T, S, A> where T: fmt::Debug + Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.clone()).finish() @@ -1842,11 +1844,11 @@ impl<T, S, A> FusedIterator for Intersection<'_, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { } -impl<T, S, A: Allocator + Clone> Clone for Difference<'_, T, S, A> { +impl<T, S, A: Allocator> Clone for Difference<'_, T, S, A> { #[cfg_attr(feature = "inline-more", inline)] fn clone(&self) -> Self { Difference { @@ -1860,7 +1862,7 @@ impl<'a, T, S, A> Iterator for Difference<'a, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { type Item = &'a T; @@ -1885,7 +1887,7 @@ impl<T, S, A> FusedIterator for Difference<'_, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { } @@ -1893,14 +1895,14 @@ impl<T, S, A> fmt::Debug for Difference<'_, T, S, A> where T: fmt::Debug + Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.clone()).finish() } } -impl<T, S, A: Allocator + Clone> Clone for SymmetricDifference<'_, T, S, A> { +impl<T, S, A: Allocator> Clone for SymmetricDifference<'_, T, S, A> { #[cfg_attr(feature = "inline-more", inline)] fn clone(&self) -> Self { SymmetricDifference { @@ -1913,7 +1915,7 @@ impl<'a, T, S, A> Iterator for SymmetricDifference<'a, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { type Item = &'a T; @@ -1931,7 +1933,7 @@ impl<T, S, A> FusedIterator for SymmetricDifference<'_, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { } @@ -1939,14 +1941,14 @@ impl<T, S, A> fmt::Debug for SymmetricDifference<'_, T, S, A> where T: fmt::Debug + Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.clone()).finish() } } -impl<T, S, A: Allocator + Clone> Clone for Union<'_, T, S, A> { +impl<T, S, A: Allocator> Clone for Union<'_, T, S, A> { #[cfg_attr(feature = "inline-more", inline)] fn clone(&self) -> Self { Union { @@ -1959,7 +1961,7 @@ impl<T, S, A> FusedIterator for Union<'_, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { } @@ -1967,7 +1969,7 @@ impl<T, S, A> fmt::Debug for Union<'_, T, S, A> where T: fmt::Debug + Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.clone()).finish() @@ -1978,7 +1980,7 @@ impl<'a, T, S, A> Iterator for Union<'a, T, S, A> where T: Eq + Hash, S: BuildHasher, - A: Allocator + Clone, + A: Allocator, { type Item = &'a T; @@ -2030,7 +2032,7 @@ where /// ``` pub enum Entry<'a, T, S, A = Global> where - A: Allocator + Clone, + A: Allocator, { /// An occupied entry. /// @@ -2063,7 +2065,7 @@ where Vacant(VacantEntry<'a, T, S, A>), } -impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for Entry<'_, T, S, A> { +impl<T: fmt::Debug, S, A: Allocator> fmt::Debug for Entry<'_, T, S, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { match *self { Entry::Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(), @@ -2108,11 +2110,11 @@ impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for Entry<'_, T, S, A> { /// assert_eq!(set.get(&"c"), None); /// assert_eq!(set.len(), 2); /// ``` -pub struct OccupiedEntry<'a, T, S, A: Allocator + Clone = Global> { +pub struct OccupiedEntry<'a, T, S, A: Allocator = Global> { inner: map::OccupiedEntry<'a, T, (), S, A>, } -impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for OccupiedEntry<'_, T, S, A> { +impl<T: fmt::Debug, S, A: Allocator> fmt::Debug for OccupiedEntry<'_, T, S, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_struct("OccupiedEntry") .field("value", self.get()) @@ -2146,17 +2148,17 @@ impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for OccupiedEntry<'_, T, /// } /// assert!(set.contains("b") && set.len() == 2); /// ``` -pub struct VacantEntry<'a, T, S, A: Allocator + Clone = Global> { +pub struct VacantEntry<'a, T, S, A: Allocator = Global> { inner: map::VacantEntry<'a, T, (), S, A>, } -impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for VacantEntry<'_, T, S, A> { +impl<T: fmt::Debug, S, A: Allocator> fmt::Debug for VacantEntry<'_, T, S, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_tuple("VacantEntry").field(self.get()).finish() } } -impl<'a, T, S, A: Allocator + Clone> Entry<'a, T, S, A> { +impl<'a, T, S, A: Allocator> Entry<'a, T, S, A> { /// Sets the value of the entry, and returns an OccupiedEntry. /// /// # Examples @@ -2233,7 +2235,7 @@ impl<'a, T, S, A: Allocator + Clone> Entry<'a, T, S, A> { } } -impl<T, S, A: Allocator + Clone> OccupiedEntry<'_, T, S, A> { +impl<T, S, A: Allocator> OccupiedEntry<'_, T, S, A> { /// Gets a reference to the value in the entry. /// /// # Examples @@ -2320,7 +2322,7 @@ impl<T, S, A: Allocator + Clone> OccupiedEntry<'_, T, S, A> { } } -impl<'a, T, S, A: Allocator + Clone> VacantEntry<'a, T, S, A> { +impl<'a, T, S, A: Allocator> VacantEntry<'a, T, S, A> { /// Gets a reference to the value that would be used when inserting /// through the `VacantEntry`. /// @@ -2400,34 +2402,30 @@ fn assert_covariance() { fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> { v } - fn into_iter<'new, A: Allocator + Clone>( - v: IntoIter<&'static str, A>, - ) -> IntoIter<&'new str, A> { + fn into_iter<'new, A: Allocator>(v: IntoIter<&'static str, A>) -> IntoIter<&'new str, A> { v } - fn difference<'a, 'new, A: Allocator + Clone>( + fn difference<'a, 'new, A: Allocator>( v: Difference<'a, &'static str, DefaultHashBuilder, A>, ) -> Difference<'a, &'new str, DefaultHashBuilder, A> { v } - fn symmetric_difference<'a, 'new, A: Allocator + Clone>( + fn symmetric_difference<'a, 'new, A: Allocator>( v: SymmetricDifference<'a, &'static str, DefaultHashBuilder, A>, ) -> SymmetricDifference<'a, &'new str, DefaultHashBuilder, A> { v } - fn intersection<'a, 'new, A: Allocator + Clone>( + fn intersection<'a, 'new, A: Allocator>( v: Intersection<'a, &'static str, DefaultHashBuilder, A>, ) -> Intersection<'a, &'new str, DefaultHashBuilder, A> { v } - fn union<'a, 'new, A: Allocator + Clone>( + fn union<'a, 'new, A: Allocator>( v: Union<'a, &'static str, DefaultHashBuilder, A>, ) -> Union<'a, &'new str, DefaultHashBuilder, A> { v } - fn drain<'new, A: Allocator + Clone>( - d: Drain<'static, &'static str, A>, - ) -> Drain<'new, &'new str, A> { + fn drain<'new, A: Allocator>(d: Drain<'static, &'static str, A>) -> Drain<'new, &'new str, A> { d } } |