compiler/rustc_data_structures/src/sso/set.rs

   1 use std::fmt;
   2 use std::hash::Hash;
   3 use std::iter::FromIterator;
   4
   5 use super::map::SsoHashMap;
   6
   7 /// Small-storage-optimized implementation of a set.
   8 ///
   9 /// Stores elements in a small array up to a certain length
  10 /// and switches to `HashSet` when that length is exceeded.
  11 //
  12 // FIXME: Implements subset of HashSet API.
  13 //
  14 // Missing HashSet API:
  15 //   all hasher-related
  16 //   try_reserve
  17 //   shrink_to (unstable)
  18 //   drain_filter (unstable)
  19 //   replace
  20 //   get_or_insert/get_or_insert_owned/get_or_insert_with (unstable)
  21 //   difference/symmetric_difference/intersection/union
  22 //   is_disjoint/is_subset/is_superset
  23 //   PartialEq/Eq (requires SsoHashMap implementation)
  24 //   BitOr/BitAnd/BitXor/Sub
  25 #[derive(Clone)]
  26 pub struct SsoHashSet<T> {
  27     map: SsoHashMap<T, ()>,
  28 }
  29
  30 /// Adapter function used ot return
  31 /// result if SsoHashMap functions into
  32 /// result SsoHashSet should return.
  33 #[inline(always)]
  34 fn entry_to_key<K, V>((k, _v): (K, V)) -> K {
  35     k
  36 }
  37
  38 impl<T> SsoHashSet<T> {
  39     /// Creates an empty `SsoHashSet`.
  40     #[inline]
  41     pub fn new() -> Self {
  42         Self { map: SsoHashMap::new() }
  43     }
  44
  45     /// Creates an empty `SsoHashSet` with the specified capacity.
  46     #[inline]
  47     pub fn with_capacity(cap: usize) -> Self {
  48         Self { map: SsoHashMap::with_capacity(cap) }
  49     }
  50
  51     /// Clears the set, removing all values.
  52     #[inline]
  53     pub fn clear(&mut self) {
  54         self.map.clear()
  55     }
  56
  57     /// Returns the number of elements the set can hold without reallocating.
  58     #[inline]
  59     pub fn capacity(&self) -> usize {
  60         self.map.capacity()
  61     }
  62
  63     /// Returns the number of elements in the set.
  64     #[inline]
  65     pub fn len(&self) -> usize {
  66         self.map.len()
  67     }
  68
  69     /// Returns `true` if the set contains no elements.
  70     #[inline]
  71     pub fn is_empty(&self) -> bool {
  72         self.map.is_empty()
  73     }
  74
  75     /// An iterator visiting all elements in arbitrary order.
  76     /// The iterator element type is `&'a T`.
  77     #[inline]
  78     pub fn iter(&'a self) -> impl Iterator<Item = &'a T> {
  79         self.into_iter()
  80     }
  81
  82     /// Clears the set, returning all elements in an iterator.
  83     #[inline]
  84     pub fn drain(&mut self) -> impl Iterator<Item = T> + '_ {
  85         self.map.drain().map(entry_to_key)
  86     }
  87 }
  88
  89 impl<T: Eq + Hash> SsoHashSet<T> {
  90     /// Reserves capacity for at least `additional` more elements to be inserted
  91     /// in the `SsoHashSet`. The collection may reserve more space to avoid
  92     /// frequent reallocations.
  93     #[inline]
  94     pub fn reserve(&mut self, additional: usize) {
  95         self.map.reserve(additional)
  96     }
  97
  98     /// Shrinks the capacity of the set as much as possible. It will drop
  99     /// down as much as possible while maintaining the internal rules
 100     /// and possibly leaving some space in accordance with the resize policy.
 101     #[inline]
 102     pub fn shrink_to_fit(&mut self) {
 103         self.map.shrink_to_fit()
 104     }
 105
 106     /// Retains only the elements specified by the predicate.
 107     #[inline]
 108     pub fn retain<F>(&mut self, mut f: F)
 109     where
 110         F: FnMut(&T) -> bool,
 111     {
 112         self.map.retain(|k, _v| f(k))
 113     }
 114
 115     /// Removes and returns the value in the set, if any, that is equal to the given one.
 116     #[inline]
 117     pub fn take(&mut self, value: &T) -> Option<T> {
 118         self.map.remove_entry(value).map(entry_to_key)
 119     }
 120
 121     /// Returns a reference to the value in the set, if any, that is equal to the given value.
 122     #[inline]
 123     pub fn get(&self, value: &T) -> Option<&T> {
 124         self.map.get_key_value(value).map(entry_to_key)
 125     }
 126
 127     /// Adds a value to the set.
 128     ///
 129     /// If the set did not have this value present, `true` is returned.
 130     ///
 131     /// If the set did have this value present, `false` is returned.
 132     #[inline]
 133     pub fn insert(&mut self, elem: T) -> bool {
 134         self.map.insert(elem, ()).is_none()
 135     }
 136
 137     /// Removes a value from the set. Returns whether the value was
 138     /// present in the set.
 139     #[inline]
 140     pub fn remove(&mut self, value: &T) -> bool {
 141         self.map.remove(value).is_some()
 142     }
 143
 144     /// Returns `true` if the set contains a value.
 145     #[inline]
 146     pub fn contains(&self, value: &T) -> bool {
 147         self.map.contains_key(value)
 148     }
 149 }
 150
 151 impl<T: Eq + Hash> FromIterator<T> for SsoHashSet<T> {
 152     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> SsoHashSet<T> {
 153         let mut set: SsoHashSet<T> = Default::default();
 154         set.extend(iter);
 155         set
 156     }
 157 }
 158
 159 impl<T> Default for SsoHashSet<T> {
 160     #[inline]
 161     fn default() -> Self {
 162         Self::new()
 163     }
 164 }
 165
 166 impl<T: Eq + Hash> Extend<T> for SsoHashSet<T> {
 167     fn extend<I>(&mut self, iter: I)
 168     where
 169         I: IntoIterator<Item = T>,
 170     {
 171         for val in iter.into_iter() {
 172             self.insert(val);
 173         }
 174     }
 175
 176     #[inline]
 177     fn extend_one(&mut self, item: T) {
 178         self.insert(item);
 179     }
 180
 181     #[inline]
 182     fn extend_reserve(&mut self, additional: usize) {
 183         self.map.extend_reserve(additional)
 184     }
 185 }
 186
 187 impl<'a, T> Extend<&'a T> for SsoHashSet<T>
 188 where
 189     T: 'a + Eq + Hash + Copy,
 190 {
 191     #[inline]
 192     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
 193         self.extend(iter.into_iter().cloned());
 194     }
 195
 196     #[inline]
 197     fn extend_one(&mut self, &item: &'a T) {
 198         self.insert(item);
 199     }
 200
 201     #[inline]
 202     fn extend_reserve(&mut self, additional: usize) {
 203         Extend::<T>::extend_reserve(self, additional)
 204     }
 205 }
 206
 207 impl<T> IntoIterator for SsoHashSet<T> {
 208     type IntoIter = std::iter::Map<<SsoHashMap<T, ()> as IntoIterator>::IntoIter, fn((T, ())) -> T>;
 209     type Item = <Self::IntoIter as Iterator>::Item;
 210
 211     #[inline]
 212     fn into_iter(self) -> Self::IntoIter {
 213         self.map.into_iter().map(entry_to_key)
 214     }
 215 }
 216
 217 impl<'a, T> IntoIterator for &'a SsoHashSet<T> {
 218     type IntoIter = std::iter::Map<
 219         <&'a SsoHashMap<T, ()> as IntoIterator>::IntoIter,
 220         fn((&'a T, &'a ())) -> &'a T,
 221     >;
 222     type Item = <Self::IntoIter as Iterator>::Item;
 223
 224     #[inline]
 225     fn into_iter(self) -> Self::IntoIter {
 226         self.map.iter().map(entry_to_key)
 227     }
 228 }
 229
 230 impl<T> fmt::Debug for SsoHashSet<T>
 231 where
 232     T: fmt::Debug,
 233 {
 234     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 235         f.debug_set().entries(self.iter()).finish()
 236     }
 237 }