sparse_hash_map/
set.rs

1//! A memory-efficient open-addressing hash set.
2//!
3//! [`SparseSet`] stores each key inside sparse arrays, sharing the engine with
4//! [`crate::SparseMap`]. It uses far less memory than a flat table at low load
5//! factor. The API mirrors the map minus the value-side operations.
6
7use core::borrow::Borrow;
8use core::hash::BuildHasher;
9use core::marker::PhantomData;
10
11use crate::growth_policy::{GrowthPolicy, LengthError, PowerOfTwo};
12use crate::hasher::{EqKey, HashKey, StdEq, StdHash};
13use crate::serialize::{Deserialize, DeserializeError, Deserializer, Serialize, Serializer};
14use crate::sparse_hash::{
15    KeySelect, SparseHash, DEFAULT_INIT_BUCKET_COUNT, DEFAULT_MAX_LOAD_FACTOR,
16};
17use crate::sparsity::{Medium, Sparsity};
18
19/// Reads the key from a stored key, which is the key itself.
20pub struct IdentityKeySelect<K>(PhantomData<K>);
21
22impl<K> KeySelect<K> for IdentityKeySelect<K> {
23    type Key = K;
24    #[inline]
25    fn key(value: &K) -> &K {
26        value
27    }
28}
29
30/// A hash set that trades a little insert speed for low memory use.
31///
32/// Type parameters match [`crate::SparseMap`] without the value type.
33pub struct SparseSet<K, H = StdHash, E = StdEq, P = PowerOfTwo<2>, S = Medium> {
34    ht: SparseHash<K, IdentityKeySelect<K>, H, E, P, S>,
35}
36
37impl<K> SparseSet<K, StdHash, StdEq, PowerOfTwo<2>, Medium> {
38    /// An empty set with no allocation.
39    ///
40    /// Construction places no bound on `K`. The `Hash` and `Eq` bounds belong
41    /// to the operations that hash or compare a key.
42    #[must_use]
43    pub fn new() -> Self {
44        Self::with_bucket_count(DEFAULT_INIT_BUCKET_COUNT)
45    }
46
47    /// An empty set sized for at least `bucket_count` buckets.
48    ///
49    /// # Panics
50    ///
51    /// Panics when `bucket_count` exceeds the policy maximum.
52    #[must_use]
53    pub fn with_bucket_count(bucket_count: usize) -> Self {
54        Self::try_with_bucket_count(bucket_count).expect("bucket count within policy limit")
55    }
56
57    /// An empty set sized for at least `bucket_count` buckets, fallibly.
58    pub fn try_with_bucket_count(bucket_count: usize) -> Result<Self, LengthError> {
59        Ok(Self {
60            ht: SparseHash::new(
61                bucket_count,
62                StdHash::default(),
63                StdEq,
64                DEFAULT_MAX_LOAD_FACTOR,
65            )?,
66        })
67    }
68}
69
70impl<K, H, E, P, S> Default for SparseSet<K, H, E, P, S>
71where
72    H: Default,
73    E: Default,
74    P: GrowthPolicy,
75{
76    /// An empty set with default parts and no allocation.
77    ///
78    /// Available when the hasher and comparator are [`Default`] and the policy
79    /// can build a zero-bucket table. Places no bound on `K`.
80    fn default() -> Self {
81        Self {
82            ht: SparseHash::new(
83                DEFAULT_INIT_BUCKET_COUNT,
84                H::default(),
85                E::default(),
86                DEFAULT_MAX_LOAD_FACTOR,
87            )
88            .expect("zero bucket count is within every policy limit"),
89        }
90    }
91}
92
93impl<K, B, P, S> SparseSet<K, StdHash<B>, StdEq, P, S>
94where
95    K: Eq,
96    B: BuildHasher + Default,
97    P: GrowthPolicy,
98    S: Sparsity,
99    StdHash<B>: HashKey<K>,
100{
101    /// An empty set that hashes with `B` and uses policy `P` and sparsity `S`.
102    ///
103    /// # Panics
104    ///
105    /// Panics when `bucket_count` exceeds the policy maximum.
106    #[must_use]
107    pub fn with_hasher_and_bucket_count(bucket_count: usize) -> Self {
108        Self {
109            ht: SparseHash::new(
110                bucket_count,
111                StdHash::default(),
112                StdEq,
113                DEFAULT_MAX_LOAD_FACTOR,
114            )
115            .expect("bucket count within policy limit"),
116        }
117    }
118}
119
120impl<K, H, E, P, S> SparseSet<K, H, E, P, S>
121where
122    H: HashKey<K> + Clone,
123    E: EqKey<K, K> + Clone,
124    P: GrowthPolicy,
125    S: Sparsity,
126{
127    /// Build a set from explicit hasher, comparator, policy, and sparsity.
128    ///
129    /// # Panics
130    ///
131    /// Panics when `bucket_count` exceeds the policy maximum.
132    #[must_use]
133    pub fn with_parts(bucket_count: usize, hash: H, key_eq: E) -> Self {
134        Self {
135            ht: SparseHash::new(bucket_count, hash, key_eq, DEFAULT_MAX_LOAD_FACTOR)
136                .expect("bucket count within policy limit"),
137        }
138    }
139
140    /// Number of keys.
141    #[inline]
142    #[must_use]
143    pub fn len(&self) -> usize {
144        self.ht.len()
145    }
146
147    /// Whether the set holds no keys.
148    #[inline]
149    #[must_use]
150    pub fn is_empty(&self) -> bool {
151        self.ht.is_empty()
152    }
153
154    /// The logical bucket count. Zero for a fresh set.
155    #[inline]
156    #[must_use]
157    pub fn bucket_count(&self) -> usize {
158        self.ht.bucket_count()
159    }
160
161    /// The largest bucket count the set can hold.
162    #[inline]
163    #[must_use]
164    pub fn max_bucket_count(&self) -> usize {
165        self.ht.max_bucket_count()
166    }
167
168    /// The largest number of keys the set can hold.
169    #[inline]
170    #[must_use]
171    pub fn max_size(&self) -> usize {
172        self.ht.max_size()
173    }
174
175    /// Ratio of keys to buckets. Zero for an empty set.
176    #[inline]
177    #[must_use]
178    pub fn load_factor(&self) -> f32 {
179        self.ht.load_factor()
180    }
181
182    /// The maximum load factor before a grow.
183    #[inline]
184    #[must_use]
185    pub fn max_load_factor(&self) -> f32 {
186        self.ht.max_load_factor()
187    }
188
189    /// Set the maximum load factor, clamped to `[0.1, 0.8]`.
190    pub fn set_max_load_factor(&mut self, ml: f32) {
191        self.ht.set_max_load_factor(ml);
192    }
193
194    /// The hasher.
195    #[inline]
196    #[must_use]
197    pub fn hash_function(&self) -> &H {
198        self.ht.hash_function()
199    }
200
201    /// The key comparator.
202    #[inline]
203    #[must_use]
204    pub fn key_eq(&self) -> &E {
205        self.ht.key_eq()
206    }
207
208    /// Remove every key. Keeps the bucket count.
209    pub fn clear(&mut self) {
210        self.ht.clear();
211    }
212
213    /// Grow so the set holds at least `count` buckets.
214    pub fn rehash(&mut self, count: usize) {
215        self.ht.rehash(count);
216    }
217
218    /// Reserve room for `count` keys without exceeding the load factor.
219    pub fn reserve(&mut self, count: usize) {
220        self.ht.reserve(count);
221    }
222
223    /// Insert `key`. Returns whether it was newly inserted.
224    pub fn insert(&mut self, key: K) -> bool {
225        self.ht.insert(key).1
226    }
227
228    /// Whether `key` is present.
229    #[must_use]
230    pub fn contains<Q>(&self, key: &Q) -> bool
231    where
232        K: Borrow<Q>,
233        Q: ?Sized,
234        H: HashKey<Q>,
235        E: EqKey<K, Q>,
236    {
237        let hash = self.ht.hash_function().hash_key(key);
238        self.ht.contains(key, hash)
239    }
240
241    /// Whether `key` is present, using a precomputed hash.
242    #[must_use]
243    pub fn contains_precalc<Q>(&self, key: &Q, hash: usize) -> bool
244    where
245        K: Borrow<Q>,
246        Q: ?Sized,
247        H: HashKey<Q>,
248        E: EqKey<K, Q>,
249    {
250        self.ht.contains(key, hash)
251    }
252
253    /// 1 when `key` is present, 0 otherwise.
254    #[must_use]
255    pub fn count<Q>(&self, key: &Q) -> usize
256    where
257        K: Borrow<Q>,
258        Q: ?Sized,
259        H: HashKey<Q>,
260        E: EqKey<K, Q>,
261    {
262        usize::from(self.contains(key))
263    }
264
265    /// 1 when `key` is present, 0 otherwise, using a precomputed hash.
266    #[must_use]
267    pub fn count_precalc<Q>(&self, key: &Q, hash: usize) -> usize
268    where
269        K: Borrow<Q>,
270        Q: ?Sized,
271        H: HashKey<Q>,
272        E: EqKey<K, Q>,
273    {
274        usize::from(self.contains_precalc(key, hash))
275    }
276
277    /// The range of keys equal to `key`.
278    ///
279    /// A set holds at most one key per value, so the range is empty or a single
280    /// key. The returned iterator yields `&K` and has length 0 or 1.
281    pub fn equal_range<Q>(&self, key: &Q) -> EqualRange<'_, K>
282    where
283        K: Borrow<Q>,
284        Q: ?Sized,
285        H: HashKey<Q>,
286        E: EqKey<K, Q>,
287    {
288        EqualRange {
289            item: self.get(key),
290        }
291    }
292
293    /// The range of keys equal to `key`, using a precomputed hash.
294    pub fn equal_range_precalc<Q>(&self, key: &Q, hash: usize) -> EqualRange<'_, K>
295    where
296        K: Borrow<Q>,
297        Q: ?Sized,
298        H: HashKey<Q>,
299        E: EqKey<K, Q>,
300    {
301        EqualRange {
302            item: self.ht.get(key, hash),
303        }
304    }
305
306    /// A reference to the stored key equal to `key`.
307    #[must_use]
308    pub fn get<Q>(&self, key: &Q) -> Option<&K>
309    where
310        K: Borrow<Q>,
311        Q: ?Sized,
312        H: HashKey<Q>,
313        E: EqKey<K, Q>,
314    {
315        let hash = self.ht.hash_function().hash_key(key);
316        self.ht.get(key, hash)
317    }
318
319    /// Remove `key`. Returns 1 when erased, 0 otherwise.
320    pub fn erase<Q>(&mut self, key: &Q) -> usize
321    where
322        K: Borrow<Q>,
323        Q: ?Sized,
324        H: HashKey<Q>,
325        E: EqKey<K, Q>,
326    {
327        let hash = self.ht.hash_function().hash_key(key);
328        self.ht.erase(key, hash)
329    }
330
331    /// Remove and return the stored key equal to `key`.
332    pub fn take<Q>(&mut self, key: &Q) -> Option<K>
333    where
334        K: Borrow<Q>,
335        Q: ?Sized,
336        H: HashKey<Q>,
337        E: EqKey<K, Q>,
338    {
339        let hash = self.ht.hash_function().hash_key(key);
340        self.ht.remove(key, hash)
341    }
342
343    /// Remove and return the first key in iteration order.
344    pub fn pop_front(&mut self) -> Option<K> {
345        self.ht.remove_nth(0)
346    }
347
348    /// Remove `count` keys starting at iteration index `skip`.
349    ///
350    /// Erasing leaves a tombstone. The walk is a single forward pass.
351    pub fn erase_range(&mut self, skip: usize, count: usize) {
352        self.ht.erase_range(skip, count);
353    }
354
355    /// Remove every key, leaving tombstones. Keeps the bucket count.
356    ///
357    /// Use [`SparseSet::clear`] to also reset the tombstones and counters.
358    pub fn erase_all(&mut self) {
359        self.ht.erase_all();
360    }
361
362    /// Keep only the keys for which `keep` returns true.
363    ///
364    /// Removed keys become tombstones. Each sparse array is scanned once.
365    pub fn retain<F>(&mut self, mut keep: F)
366    where
367        F: FnMut(&K) -> bool,
368    {
369        self.ht.retain(|k| keep(k));
370    }
371}
372
373// Equality. Order-independent membership check.
374
375impl<K, H, E, P, S> PartialEq for SparseSet<K, H, E, P, S>
376where
377    H: HashKey<K> + Clone,
378    E: EqKey<K, K> + Clone,
379    P: GrowthPolicy,
380    S: Sparsity,
381{
382    fn eq(&self, other: &Self) -> bool {
383        if self.len() != other.len() {
384            return false;
385        }
386        self.iter().all(|k| other.contains(k))
387    }
388}
389
390impl<K, H, E, P, S> Eq for SparseSet<K, H, E, P, S>
391where
392    H: HashKey<K> + Clone,
393    E: EqKey<K, K> + Clone,
394    P: GrowthPolicy,
395    S: Sparsity,
396{
397}
398
399impl<K, H, E, P, S> core::fmt::Debug for SparseSet<K, H, E, P, S>
400where
401    K: core::fmt::Debug,
402{
403    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
404        f.debug_set().entries(self.iter()).finish()
405    }
406}
407
408impl<K, H, E, P, S> Clone for SparseSet<K, H, E, P, S>
409where
410    K: Clone,
411    H: Clone,
412    E: Clone,
413    P: Clone,
414{
415    fn clone(&self) -> Self {
416        Self {
417            ht: self.ht.clone(),
418        }
419    }
420}
421
422// Iteration.
423
424impl<K, H, E, P, S> SparseSet<K, H, E, P, S> {
425    /// A forward iterator over keys.
426    #[must_use]
427    pub fn iter(&self) -> Iter<'_, K> {
428        Iter {
429            inner: self.ht.iter(),
430        }
431    }
432}
433
434/// Range of keys equal to a lookup key. Length 0 or 1.
435///
436/// A [`SparseSet`] holds at most one matching key. The range from
437/// [`SparseSet::equal_range`] yields that key once, or nothing.
438pub struct EqualRange<'a, K> {
439    item: Option<&'a K>,
440}
441
442impl<'a, K> Iterator for EqualRange<'a, K> {
443    type Item = &'a K;
444    fn next(&mut self) -> Option<&'a K> {
445        self.item.take()
446    }
447}
448
449impl<K> ExactSizeIterator for EqualRange<'_, K> {
450    fn len(&self) -> usize {
451        usize::from(self.item.is_some())
452    }
453}
454
455/// Iterator over keys of a [`SparseSet`].
456pub struct Iter<'a, K> {
457    inner: crate::sparse_hash::Iter<'a, K>,
458}
459
460impl<'a, K> Iterator for Iter<'a, K> {
461    type Item = &'a K;
462    fn next(&mut self) -> Option<&'a K> {
463        self.inner.next()
464    }
465}
466
467impl<'a, K, H, E, P, S> IntoIterator for &'a SparseSet<K, H, E, P, S> {
468    type Item = &'a K;
469    type IntoIter = Iter<'a, K>;
470    fn into_iter(self) -> Self::IntoIter {
471        self.iter()
472    }
473}
474
475/// Owning iterator over keys of a [`SparseSet`].
476pub struct IntoIter<K> {
477    inner: crate::sparse_hash::IntoIter<K>,
478}
479
480impl<K> Iterator for IntoIter<K> {
481    type Item = K;
482    fn next(&mut self) -> Option<K> {
483        self.inner.next()
484    }
485}
486
487impl<K, H, E, P, S> IntoIterator for SparseSet<K, H, E, P, S> {
488    type Item = K;
489    type IntoIter = IntoIter<K>;
490    fn into_iter(self) -> Self::IntoIter {
491        IntoIter {
492            inner: self.ht.into_values(),
493        }
494    }
495}
496
497impl<K, H, E, P, S> Extend<K> for SparseSet<K, H, E, P, S>
498where
499    H: HashKey<K> + Clone,
500    E: EqKey<K, K> + Clone,
501    P: GrowthPolicy,
502    S: Sparsity,
503{
504    /// Insert every key from `iter`. Keys already present are ignored.
505    fn extend<I: IntoIterator<Item = K>>(&mut self, iter: I) {
506        let iter = iter.into_iter();
507        let (lower, _) = iter.size_hint();
508        self.reserve(self.len() + lower);
509        for k in iter {
510            self.insert(k);
511        }
512    }
513}
514
515// Serialization.
516
517impl<K, H, E, P, S> SparseSet<K, H, E, P, S>
518where
519    K: Serialize,
520{
521    /// Write the set through `serializer` in protocol order.
522    pub fn serialize<Sz: Serializer>(&self, serializer: &mut Sz) {
523        self.ht.serialize(serializer);
524    }
525}
526
527impl<K, H, E, P, S> SparseSet<K, H, E, P, S>
528where
529    H: HashKey<K> + Clone,
530    E: EqKey<K, K> + Clone,
531    P: GrowthPolicy,
532    S: Sparsity,
533    K: Serialize + Deserialize,
534{
535    /// Read a set written by [`SparseSet::serialize`].
536    pub fn deserialize_with<D: Deserializer>(
537        deserializer: &mut D,
538        hash_compatible: bool,
539        hash: H,
540        key_eq: E,
541    ) -> Result<Self, DeserializeError> {
542        Ok(Self {
543            ht: SparseHash::deserialize(deserializer, hash_compatible, hash, key_eq)?,
544        })
545    }
546}
sparse_hash_map/set.rs

sparse_hash_map/
set.rs
