rustc_data_structures/sso/
set.rs

1use std::fmt;
2use std::hash::Hash;
3
4use super::map::SsoHashMap;
5
6/// Small-storage-optimized implementation of a set.
7///
8/// Stores elements in a small array up to a certain length
9/// and switches to `HashSet` when that length is exceeded.
10//
11// FIXME: Implements subset of HashSet API.
12//
13// Missing HashSet API:
14//   all hasher-related
15//   try_reserve
16//   shrink_to (unstable)
17//   drain_filter (unstable)
18//   replace
19//   get_or_insert/get_or_insert_owned/get_or_insert_with (unstable)
20//   difference/symmetric_difference/intersection/union
21//   is_disjoint/is_subset/is_superset
22//   PartialEq/Eq (requires SsoHashMap implementation)
23//   BitOr/BitAnd/BitXor/Sub
24#[derive(Clone)]
25pub struct SsoHashSet<T> {
26    map: SsoHashMap<T, ()>,
27}
28
29/// Adapter function used to return
30/// result if SsoHashMap functions into
31/// result SsoHashSet should return.
32#[inline(always)]
33fn entry_to_key<K, V>((k, _v): (K, V)) -> K {
34    k
35}
36
37impl<T> SsoHashSet<T> {
38    /// Creates an empty `SsoHashSet`.
39    #[inline]
40    pub fn new() -> Self {
41        Self { map: SsoHashMap::new() }
42    }
43
44    /// Creates an empty `SsoHashSet` with the specified capacity.
45    #[inline]
46    pub fn with_capacity(cap: usize) -> Self {
47        Self { map: SsoHashMap::with_capacity(cap) }
48    }
49
50    /// Clears the set, removing all values.
51    #[inline]
52    pub fn clear(&mut self) {
53        self.map.clear()
54    }
55
56    /// Returns the number of elements the set can hold without reallocating.
57    #[inline]
58    pub fn capacity(&self) -> usize {
59        self.map.capacity()
60    }
61
62    /// Returns the number of elements in the set.
63    #[inline]
64    pub fn len(&self) -> usize {
65        self.map.len()
66    }
67
68    /// Returns `true` if the set contains no elements.
69    #[inline]
70    pub fn is_empty(&self) -> bool {
71        self.map.is_empty()
72    }
73
74    /// An iterator visiting all elements in arbitrary order.
75    /// The iterator element type is `&'a T`.
76    #[inline]
77    pub fn iter(&self) -> impl Iterator<Item = &T> {
78        self.into_iter()
79    }
80
81    /// Clears the set, returning all elements in an iterator.
82    #[inline]
83    pub fn drain(&mut self) -> impl Iterator<Item = T> {
84        self.map.drain().map(entry_to_key)
85    }
86}
87
88impl<T: Eq + Hash> SsoHashSet<T> {
89    /// Reserves capacity for at least `additional` more elements to be inserted
90    /// in the `SsoHashSet`. The collection may reserve more space to avoid
91    /// frequent reallocations.
92    #[inline]
93    pub fn reserve(&mut self, additional: usize) {
94        self.map.reserve(additional)
95    }
96
97    /// Shrinks the capacity of the set as much as possible. It will drop
98    /// down as much as possible while maintaining the internal rules
99    /// and possibly leaving some space in accordance with the resize policy.
100    #[inline]
101    pub fn shrink_to_fit(&mut self) {
102        self.map.shrink_to_fit()
103    }
104
105    /// Retains only the elements specified by the predicate.
106    #[inline]
107    pub fn retain<F>(&mut self, mut f: F)
108    where
109        F: FnMut(&T) -> bool,
110    {
111        self.map.retain(|k, _v| f(k))
112    }
113
114    /// Removes and returns the value in the set, if any, that is equal to the given one.
115    #[inline]
116    pub fn take(&mut self, value: &T) -> Option<T> {
117        self.map.remove_entry(value).map(entry_to_key)
118    }
119
120    /// Returns a reference to the value in the set, if any, that is equal to the given value.
121    #[inline]
122    pub fn get(&self, value: &T) -> Option<&T> {
123        self.map.get_key_value(value).map(entry_to_key)
124    }
125
126    /// Adds a value to the set.
127    ///
128    /// Returns whether the value was newly inserted. That is:
129    ///
130    /// - If the set did not previously contain this value, `true` is returned.
131    /// - If the set already contained this value, `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
151impl<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
159impl<T> Default for SsoHashSet<T> {
160    #[inline]
161    fn default() -> Self {
162        Self::new()
163    }
164}
165
166impl<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
187impl<'a, T> Extend<&'a T> for SsoHashSet<T>
188where
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
207impl<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
217impl<'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
230impl<T> fmt::Debug for SsoHashSet<T>
231where
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}
rustc_data_structures/sso/set.rs

rustc_data_structures/sso/
set.rs
