From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_data_structures/src/sso/set.rs | 238 ++++++++++++++++++++++++++ 1 file changed, 238 insertions(+) create mode 100644 compiler/rustc_data_structures/src/sso/set.rs (limited to 'compiler/rustc_data_structures/src/sso/set.rs') diff --git a/compiler/rustc_data_structures/src/sso/set.rs b/compiler/rustc_data_structures/src/sso/set.rs new file mode 100644 index 000000000..4fda3adb7 --- /dev/null +++ b/compiler/rustc_data_structures/src/sso/set.rs @@ -0,0 +1,238 @@ +use std::fmt; +use std::hash::Hash; +use std::iter::FromIterator; + +use super::map::SsoHashMap; + +/// Small-storage-optimized implementation of a set. +/// +/// Stores elements in a small array up to a certain length +/// and switches to `HashSet` when that length is exceeded. +// +// FIXME: Implements subset of HashSet API. +// +// Missing HashSet API: +// all hasher-related +// try_reserve +// shrink_to (unstable) +// drain_filter (unstable) +// replace +// get_or_insert/get_or_insert_owned/get_or_insert_with (unstable) +// difference/symmetric_difference/intersection/union +// is_disjoint/is_subset/is_superset +// PartialEq/Eq (requires SsoHashMap implementation) +// BitOr/BitAnd/BitXor/Sub +#[derive(Clone)] +pub struct SsoHashSet { + map: SsoHashMap, +} + +/// Adapter function used ot return +/// result if SsoHashMap functions into +/// result SsoHashSet should return. +#[inline(always)] +fn entry_to_key((k, _v): (K, V)) -> K { + k +} + +impl SsoHashSet { + /// Creates an empty `SsoHashSet`. + #[inline] + pub fn new() -> Self { + Self { map: SsoHashMap::new() } + } + + /// Creates an empty `SsoHashSet` with the specified capacity. + #[inline] + pub fn with_capacity(cap: usize) -> Self { + Self { map: SsoHashMap::with_capacity(cap) } + } + + /// Clears the set, removing all values. + #[inline] + pub fn clear(&mut self) { + self.map.clear() + } + + /// Returns the number of elements the set can hold without reallocating. + #[inline] + pub fn capacity(&self) -> usize { + self.map.capacity() + } + + /// Returns the number of elements in the set. + #[inline] + pub fn len(&self) -> usize { + self.map.len() + } + + /// Returns `true` if the set contains no elements. + #[inline] + pub fn is_empty(&self) -> bool { + self.map.is_empty() + } + + /// An iterator visiting all elements in arbitrary order. + /// The iterator element type is `&'a T`. + #[inline] + pub fn iter(&self) -> impl Iterator { + self.into_iter() + } + + /// Clears the set, returning all elements in an iterator. + #[inline] + pub fn drain(&mut self) -> impl Iterator + '_ { + self.map.drain().map(entry_to_key) + } +} + +impl SsoHashSet { + /// Reserves capacity for at least `additional` more elements to be inserted + /// in the `SsoHashSet`. The collection may reserve more space to avoid + /// frequent reallocations. + #[inline] + pub fn reserve(&mut self, additional: usize) { + self.map.reserve(additional) + } + + /// Shrinks the capacity of the set as much as possible. It will drop + /// down as much as possible while maintaining the internal rules + /// and possibly leaving some space in accordance with the resize policy. + #[inline] + pub fn shrink_to_fit(&mut self) { + self.map.shrink_to_fit() + } + + /// Retains only the elements specified by the predicate. + #[inline] + pub fn retain(&mut self, mut f: F) + where + F: FnMut(&T) -> bool, + { + self.map.retain(|k, _v| f(k)) + } + + /// Removes and returns the value in the set, if any, that is equal to the given one. + #[inline] + pub fn take(&mut self, value: &T) -> Option { + self.map.remove_entry(value).map(entry_to_key) + } + + /// Returns a reference to the value in the set, if any, that is equal to the given value. + #[inline] + pub fn get(&self, value: &T) -> Option<&T> { + self.map.get_key_value(value).map(entry_to_key) + } + + /// Adds a value to the set. + /// + /// Returns whether the value was newly inserted. That is: + /// + /// - If the set did not previously contain this value, `true` is returned. + /// - If the set already contained this value, `false` is returned. + #[inline] + pub fn insert(&mut self, elem: T) -> bool { + self.map.insert(elem, ()).is_none() + } + + /// Removes a value from the set. Returns whether the value was + /// present in the set. + #[inline] + pub fn remove(&mut self, value: &T) -> bool { + self.map.remove(value).is_some() + } + + /// Returns `true` if the set contains a value. + #[inline] + pub fn contains(&self, value: &T) -> bool { + self.map.contains_key(value) + } +} + +impl FromIterator for SsoHashSet { + fn from_iter>(iter: I) -> SsoHashSet { + let mut set: SsoHashSet = Default::default(); + set.extend(iter); + set + } +} + +impl Default for SsoHashSet { + #[inline] + fn default() -> Self { + Self::new() + } +} + +impl Extend for SsoHashSet { + fn extend(&mut self, iter: I) + where + I: IntoIterator, + { + for val in iter.into_iter() { + self.insert(val); + } + } + + #[inline] + fn extend_one(&mut self, item: T) { + self.insert(item); + } + + #[inline] + fn extend_reserve(&mut self, additional: usize) { + self.map.extend_reserve(additional) + } +} + +impl<'a, T> Extend<&'a T> for SsoHashSet +where + T: 'a + Eq + Hash + Copy, +{ + #[inline] + fn extend>(&mut self, iter: I) { + self.extend(iter.into_iter().cloned()); + } + + #[inline] + fn extend_one(&mut self, &item: &'a T) { + self.insert(item); + } + + #[inline] + fn extend_reserve(&mut self, additional: usize) { + Extend::::extend_reserve(self, additional) + } +} + +impl IntoIterator for SsoHashSet { + type IntoIter = std::iter::Map< as IntoIterator>::IntoIter, fn((T, ())) -> T>; + type Item = ::Item; + + #[inline] + fn into_iter(self) -> Self::IntoIter { + self.map.into_iter().map(entry_to_key) + } +} + +impl<'a, T> IntoIterator for &'a SsoHashSet { + type IntoIter = std::iter::Map< + <&'a SsoHashMap as IntoIterator>::IntoIter, + fn((&'a T, &'a ())) -> &'a T, + >; + type Item = ::Item; + + #[inline] + fn into_iter(self) -> Self::IntoIter { + self.map.iter().map(entry_to_key) + } +} + +impl fmt::Debug for SsoHashSet +where + T: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_set().entries(self.iter()).finish() + } +} -- cgit v1.2.3