papaya/set.rs
1use crate::raw::utils::MapGuard;
2use crate::raw::{self, InsertResult};
3use crate::Equivalent;
4use seize::{Collector, Guard, LocalGuard, OwnedGuard};
5
6use crate::map::ResizeMode;
7use std::collections::hash_map::RandomState;
8use std::fmt;
9use std::hash::{BuildHasher, Hash};
10use std::marker::PhantomData;
11
12/// A concurrent hash set.
13///
14/// Most hash set operations require a [`Guard`](crate::Guard), which can be acquired through
15/// [`HashSet::guard`] or using the [`HashSet::pin`] API. See the [crate-level documentation](crate#usage)
16/// for details.
17pub struct HashSet<K, S = RandomState> {
18 raw: raw::HashMap<K, (), S>,
19}
20
21// Safety: We only ever hand out &K through shared references to the map,
22// so normal Send/Sync rules apply. We never expose owned or mutable references
23// to keys or values.
24unsafe impl<K: Send, S: Send> Send for HashSet<K, S> {}
25unsafe impl<K: Sync, S: Sync> Sync for HashSet<K, S> {}
26
27/// A builder for a [`HashSet`].
28///
29/// # Examples
30///
31/// ```rust
32/// use papaya::{HashSet, ResizeMode};
33/// use seize::Collector;
34/// use std::collections::hash_map::RandomState;
35///
36/// let set: HashSet<i32> = HashSet::builder()
37/// // Set the initial capacity.
38/// .capacity(2048)
39/// // Set the hasher.
40/// .hasher(RandomState::new())
41/// // Set the resize mode.
42/// .resize_mode(ResizeMode::Blocking)
43/// // Set a custom garbage collector.
44/// .collector(Collector::new().batch_size(128))
45/// // Construct the hash set.
46/// .build();
47/// ```
48pub struct HashSetBuilder<K, S = RandomState> {
49 hasher: S,
50 capacity: usize,
51 collector: Collector,
52 resize_mode: ResizeMode,
53 _kv: PhantomData<K>,
54}
55
56impl<K> HashSetBuilder<K> {
57 /// Set the hash builder used to hash keys.
58 ///
59 /// Warning: `hash_builder` is normally randomly generated, and is designed
60 /// to allow HashSets to be resistant to attacks that cause many collisions
61 /// and very poor performance. Setting it manually using this function can
62 /// expose a DoS attack vector.
63 ///
64 /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
65 /// the HashSet to be useful, see its documentation for details.
66 pub fn hasher<S>(self, hasher: S) -> HashSetBuilder<K, S> {
67 HashSetBuilder {
68 hasher,
69 capacity: self.capacity,
70 collector: self.collector,
71 resize_mode: self.resize_mode,
72 _kv: PhantomData,
73 }
74 }
75}
76
77impl<K, S> HashSetBuilder<K, S> {
78 /// Set the initial capacity of the set.
79 ///
80 /// The set should be able to hold at least `capacity` elements before resizing.
81 /// However, the capacity is an estimate, and the set may prematurely resize due
82 /// to poor hash distribution. If `capacity` is 0, the hash set will not allocate.
83 pub fn capacity(self, capacity: usize) -> HashSetBuilder<K, S> {
84 HashSetBuilder {
85 capacity,
86 hasher: self.hasher,
87 collector: self.collector,
88 resize_mode: self.resize_mode,
89 _kv: PhantomData,
90 }
91 }
92
93 /// Set the resizing mode of the set. See [`ResizeMode`] for details.
94 pub fn resize_mode(self, resize_mode: ResizeMode) -> Self {
95 HashSetBuilder {
96 resize_mode,
97 hasher: self.hasher,
98 capacity: self.capacity,
99 collector: self.collector,
100 _kv: PhantomData,
101 }
102 }
103
104 /// Set the [`seize::Collector`] used for garbage collection.
105 ///
106 /// This method may be useful when you want more control over garbage collection.
107 ///
108 /// Note that all `Guard` references used to access the set must be produced by
109 /// the provided `collector`.
110 pub fn collector(self, collector: Collector) -> Self {
111 HashSetBuilder {
112 collector,
113 hasher: self.hasher,
114 capacity: self.capacity,
115 resize_mode: self.resize_mode,
116 _kv: PhantomData,
117 }
118 }
119
120 /// Construct a [`HashSet`] from the builder, using the configured options.
121 pub fn build(self) -> HashSet<K, S> {
122 HashSet {
123 raw: raw::HashMap::new(self.capacity, self.hasher, self.collector, self.resize_mode),
124 }
125 }
126}
127
128impl<K, S> fmt::Debug for HashSetBuilder<K, S> {
129 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
130 f.debug_struct("HashSetBuilder")
131 .field("capacity", &self.capacity)
132 .field("collector", &self.collector)
133 .field("resize_mode", &self.resize_mode)
134 .finish()
135 }
136}
137
138impl<K> HashSet<K> {
139 /// Creates an empty `HashSet`.
140 ///
141 /// The hash map is initially created with a capacity of 0, so it will not allocate
142 /// until it is first inserted into.
143 ///
144 /// # Examples
145 ///
146 /// ```
147 /// use papaya::HashSet;
148 /// let map: HashSet<&str> = HashSet::new();
149 /// ```
150 pub fn new() -> HashSet<K> {
151 HashSet::with_capacity_and_hasher(0, RandomState::new())
152 }
153
154 /// Creates an empty `HashSet` with the specified capacity.
155 ///
156 /// The set should be able to hold at least `capacity` elements before resizing.
157 /// However, the capacity is an estimate, and the set may prematurely resize due
158 /// to poor hash distribution. If `capacity` is 0, the hash set will not allocate.
159 ///
160 /// # Examples
161 ///
162 /// ```
163 /// use papaya::HashSet;
164 /// let set: HashSet<&str> = HashSet::with_capacity(10);
165 /// ```
166 pub fn with_capacity(capacity: usize) -> HashSet<K> {
167 HashSet::with_capacity_and_hasher(capacity, RandomState::new())
168 }
169
170 /// Returns a builder for a `HashSet`.
171 ///
172 /// The builder can be used for more complex configuration, such as using
173 /// a custom [`Collector`], or [`ResizeMode`].
174 pub fn builder() -> HashSetBuilder<K> {
175 HashSetBuilder {
176 capacity: 0,
177 hasher: RandomState::default(),
178 collector: Collector::new(),
179 resize_mode: ResizeMode::default(),
180 _kv: PhantomData,
181 }
182 }
183}
184
185impl<K, S> Default for HashSet<K, S>
186where
187 S: Default,
188{
189 fn default() -> Self {
190 HashSet::with_hasher(S::default())
191 }
192}
193
194impl<K, S> HashSet<K, S> {
195 /// Creates an empty `HashSet` which will use the given hash builder to hash
196 /// keys.
197 ///
198 /// Warning: `hash_builder` is normally randomly generated, and is designed
199 /// to allow HashSets to be resistant to attacks that cause many collisions
200 /// and very poor performance. Setting it manually using this function can
201 /// expose a DoS attack vector.
202 ///
203 /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
204 /// the HashSet to be useful, see its documentation for details.
205 ///
206 /// # Examples
207 ///
208 /// ```
209 /// use papaya::HashSet;
210 /// use std::hash::RandomState;
211 ///
212 /// let s = RandomState::new();
213 /// let set = HashSet::with_hasher(s);
214 /// set.pin().insert(1);
215 /// ```
216 pub fn with_hasher(hash_builder: S) -> HashSet<K, S> {
217 HashSet::with_capacity_and_hasher(0, hash_builder)
218 }
219
220 /// Creates an empty `HashSet` with at least the specified capacity, using
221 /// `hash_builder` to hash the keys.
222 ///
223 /// The set should be able to hold at least `capacity` elements before resizing.
224 /// However, the capacity is an estimate, and the set may prematurely resize due
225 /// to poor hash distribution. If `capacity` is 0, the hash set will not allocate.
226 ///
227 /// Warning: `hash_builder` is normally randomly generated, and is designed
228 /// to allow HashSets to be resistant to attacks that cause many collisions
229 /// and very poor performance. Setting it manually using this function can
230 /// expose a DoS attack vector.
231 ///
232 /// The `hasher` passed should implement the [`BuildHasher`] trait for
233 /// the HashSet to be useful, see its documentation for details.
234 ///
235 /// # Examples
236 ///
237 /// ```
238 /// use papaya::HashSet;
239 /// use std::hash::RandomState;
240 ///
241 /// let s = RandomState::new();
242 /// let set = HashSet::with_capacity_and_hasher(10, s);
243 /// set.pin().insert(1);
244 /// ```
245 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> HashSet<K, S> {
246 HashSet {
247 raw: raw::HashMap::new(
248 capacity,
249 hash_builder,
250 Collector::default(),
251 ResizeMode::default(),
252 ),
253 }
254 }
255
256 /// Returns a pinned reference to the set.
257 ///
258 /// The returned reference manages a guard internally, preventing garbage collection
259 /// for as long as it is held. See the [crate-level documentation](crate#usage) for details.
260 #[inline]
261 pub fn pin(&self) -> HashSetRef<'_, K, S, LocalGuard<'_>> {
262 HashSetRef {
263 guard: self.raw.guard(),
264 set: self,
265 }
266 }
267
268 /// Returns a pinned reference to the set.
269 ///
270 /// Unlike [`HashSet::pin`], the returned reference implements `Send` and `Sync`,
271 /// allowing it to be held across `.await` points in work-stealing schedulers.
272 /// This is especially useful for iterators.
273 ///
274 /// The returned reference manages a guard internally, preventing garbage collection
275 /// for as long as it is held. See the [crate-level documentation](crate#usage) for details.
276 #[inline]
277 pub fn pin_owned(&self) -> HashSetRef<'_, K, S, OwnedGuard<'_>> {
278 HashSetRef {
279 guard: self.raw.owned_guard(),
280 set: self,
281 }
282 }
283
284 /// Returns a guard for use with this set.
285 ///
286 /// Note that holding on to a guard prevents garbage collection.
287 /// See the [crate-level documentation](crate#usage) for details.
288 #[inline]
289 pub fn guard(&self) -> LocalGuard<'_> {
290 self.raw.collector().enter()
291 }
292
293 /// Returns an owned guard for use with this set.
294 ///
295 /// Owned guards implement `Send` and `Sync`, allowing them to be held across
296 /// `.await` points in work-stealing schedulers. This is especially useful
297 /// for iterators.
298 ///
299 /// Note that holding on to a guard prevents garbage collection.
300 /// See the [crate-level documentation](crate#usage) for details.
301 #[inline]
302 pub fn owned_guard(&self) -> OwnedGuard<'_> {
303 self.raw.collector().enter_owned()
304 }
305}
306
307impl<K, S> HashSet<K, S>
308where
309 K: Hash + Eq,
310 S: BuildHasher,
311{
312 /// Returns the number of entries in the set.
313 ///
314 /// # Examples
315 ///
316 /// ```
317 /// use papaya::HashSet;
318 ///
319 /// let set = HashSet::new();
320 ///
321 /// set.pin().insert(1);
322 /// set.pin().insert(2);
323 /// assert!(set.len() == 2);
324 /// ```
325 #[inline]
326 pub fn len(&self) -> usize {
327 self.raw.len()
328 }
329
330 /// Returns `true` if the set is empty. Otherwise returns `false`.
331 ///
332 /// # Examples
333 ///
334 /// ```
335 /// use papaya::HashSet;
336 ///
337 /// let set = HashSet::new();
338 /// assert!(set.is_empty());
339 /// set.pin().insert("a");
340 /// assert!(!set.is_empty());
341 /// ```
342 #[inline]
343 pub fn is_empty(&self) -> bool {
344 self.len() == 0
345 }
346
347 /// Returns `true` if the set contains a value for the specified key.
348 ///
349 /// The key may be any borrowed form of the set's key type, but
350 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
351 /// the key type.
352 ///
353 /// [`Eq`]: std::cmp::Eq
354 /// [`Hash`]: std::hash::Hash
355 ///
356 ///
357 /// # Examples
358 ///
359 /// ```
360 /// use papaya::HashSet;
361 ///
362 /// let set = HashSet::new();
363 /// set.pin().insert(1);
364 /// assert_eq!(set.pin().contains(&1), true);
365 /// assert_eq!(set.pin().contains(&2), false);
366 /// ```
367 #[inline]
368 pub fn contains<Q>(&self, key: &Q, guard: &impl Guard) -> bool
369 where
370 Q: Equivalent<K> + Hash + ?Sized,
371 {
372 self.get(key, self.raw.verify(guard)).is_some()
373 }
374
375 /// Returns a reference to the value corresponding to the key.
376 ///
377 /// The key may be any borrowed form of the set's key type, but
378 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
379 /// the key type.
380 ///
381 /// [`Eq`]: std::cmp::Eq
382 /// [`Hash`]: std::hash::Hash
383 ///
384 /// # Examples
385 ///
386 /// ```
387 /// use papaya::HashSet;
388 ///
389 /// let set = HashSet::new();
390 /// set.pin().insert(1);
391 /// assert_eq!(set.pin().get(&1), Some(&1));
392 /// assert_eq!(set.pin().get(&2), None);
393 /// ```
394 #[inline]
395 pub fn get<'g, Q>(&self, key: &Q, guard: &'g impl Guard) -> Option<&'g K>
396 where
397 Q: Equivalent<K> + Hash + ?Sized,
398 {
399 match self.raw.get(key, self.raw.verify(guard)) {
400 Some((key, _)) => Some(key),
401 None => None,
402 }
403 }
404
405 /// Inserts a value into the set.
406 ///
407 /// If the set did not have this key present, `true` is returned.
408 ///
409 /// If the set did have this key present, `false` is returned and the old
410 /// value is not updated. This matters for types that can be `==` without
411 /// being identical. See the [standard library documentation] for details.
412 ///
413 /// [standard library documentation]: https://doc.rust-lang.org/std/collections/index.html#insert-and-complex-keys
414 ///
415 /// # Examples
416 ///
417 /// ```
418 /// use papaya::HashSet;
419 ///
420 /// let set = HashSet::new();
421 /// assert_eq!(set.pin().insert(37), true);
422 /// assert_eq!(set.pin().is_empty(), false);
423 ///
424 /// set.pin().insert(37);
425 /// assert_eq!(set.pin().insert(37), false);
426 /// assert_eq!(set.pin().get(&37), Some(&37));
427 /// ```
428 #[inline]
429 pub fn insert(&self, key: K, guard: &impl Guard) -> bool {
430 match self.raw.insert(key, (), true, self.raw.verify(guard)) {
431 InsertResult::Inserted(_) => true,
432 InsertResult::Replaced(_) => false,
433 InsertResult::Error { .. } => unreachable!(),
434 }
435 }
436
437 /// Removes a key from the set, returning the value at the key if the key
438 /// was previously in the set.
439 ///
440 /// The key may be any borrowed form of the set's key type, but
441 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
442 /// the key type.
443 ///
444 /// # Examples
445 ///
446 /// ```
447 /// use papaya::HashSet;
448 ///
449 /// let set = HashSet::new();
450 /// set.pin().insert(1);
451 /// assert_eq!(set.pin().remove(&1), true);
452 /// assert_eq!(set.pin().remove(&1), false);
453 /// ```
454 #[inline]
455 pub fn remove<Q>(&self, key: &Q, guard: &impl Guard) -> bool
456 where
457 Q: Equivalent<K> + Hash + ?Sized,
458 {
459 match self.raw.remove(key, self.raw.verify(guard)) {
460 Some((_, _)) => true,
461 None => false,
462 }
463 }
464
465 /// Tries to reserve capacity for `additional` more elements to be inserted
466 /// in the `HashSet`.
467 ///
468 /// After calling this method, the set should be able to hold at least `capacity` elements
469 /// before resizing. However, the capacity is an estimate, and the set may prematurely resize
470 /// due to poor hash distribution. The collection may also reserve more space to avoid frequent
471 /// reallocations.
472 ///
473 /// # Panics
474 ///
475 /// Panics if the new allocation size overflows `usize`.
476 ///
477 /// # Examples
478 ///
479 /// ```
480 /// use papaya::HashSet;
481 ///
482 /// let set: HashSet<&str> = HashSet::new();
483 /// set.pin().reserve(10);
484 /// ```
485 #[inline]
486 pub fn reserve(&self, additional: usize, guard: &impl Guard) {
487 self.raw.reserve(additional, self.raw.verify(guard))
488 }
489
490 /// Clears the set, removing all values.
491 ///
492 /// Note that this method will block until any in-progress resizes are
493 /// completed before proceeding. See the [consistency](crate#consistency)
494 /// section for details.
495 ///
496 /// # Examples
497 ///
498 /// ```
499 /// use papaya::HashSet;
500 ///
501 /// let set = HashSet::new();
502 ///
503 /// set.pin().insert(1);
504 /// set.pin().clear();
505 /// assert!(set.pin().is_empty());
506 /// ```
507 #[inline]
508 pub fn clear(&self, guard: &impl Guard) {
509 self.raw.clear(self.raw.verify(guard))
510 }
511
512 /// Retains only the elements specified by the predicate.
513 ///
514 /// In other words, remove all values `v` for which `f(&v)` returns `false`.
515 /// The elements are visited in unsorted (and unspecified) order.
516 ///
517 /// Note the function may be called more than once for a given key if its value is
518 /// concurrently modified during removal.
519 ///
520 /// Additionally, this method will block until any in-progress resizes are
521 /// completed before proceeding. See the [consistency](crate#consistency)
522 /// section for details.
523 ///
524 /// # Examples
525 ///
526 /// ```
527 /// use papaya::HashSet;
528 ///
529 /// let mut set: HashSet<i32> = (0..8).collect();
530 /// set.pin().retain(|&v| v % 2 == 0);
531 /// assert_eq!(set.len(), 4);
532 /// assert_eq!(set.pin().contains(&1), false);
533 /// assert_eq!(set.pin().contains(&2), true);
534 /// ```
535 #[inline]
536 pub fn retain<F>(&mut self, mut f: F, guard: &impl Guard)
537 where
538 F: FnMut(&K) -> bool,
539 {
540 self.raw.retain(|k, _| f(k), self.raw.verify(guard))
541 }
542
543 /// An iterator visiting all values in arbitrary order.
544 ///
545 /// Note that this method will block until any in-progress resizes are
546 /// completed before proceeding. See the [consistency](crate#consistency)
547 /// section for details.
548 ///
549 /// # Examples
550 ///
551 /// ```
552 /// use papaya::HashSet;
553 ///
554 /// let set = HashSet::from([
555 /// "a",
556 /// "b",
557 /// "c"
558 /// ]);
559 ///
560 /// for val in set.pin().iter() {
561 /// println!("val: {val}");
562 /// }
563 #[inline]
564 pub fn iter<'g, G>(&self, guard: &'g G) -> Iter<'g, K, G>
565 where
566 G: Guard,
567 {
568 Iter {
569 raw: self.raw.iter(self.raw.verify(guard)),
570 }
571 }
572}
573
574impl<K, S> PartialEq for HashSet<K, S>
575where
576 K: Hash + Eq,
577 S: BuildHasher,
578{
579 fn eq(&self, other: &Self) -> bool {
580 if self.len() != other.len() {
581 return false;
582 }
583
584 let (guard1, guard2) = (&self.guard(), &other.guard());
585
586 let mut iter = self.iter(guard1);
587 iter.all(|key| other.get(key, guard2).is_some())
588 }
589}
590
591impl<K, S> Eq for HashSet<K, S>
592where
593 K: Hash + Eq,
594 S: BuildHasher,
595{
596}
597
598impl<K, S> fmt::Debug for HashSet<K, S>
599where
600 K: Hash + Eq + fmt::Debug,
601 S: BuildHasher,
602{
603 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
604 let guard = self.guard();
605 f.debug_set().entries(self.iter(&guard)).finish()
606 }
607}
608
609impl<K, S> Extend<K> for &HashSet<K, S>
610where
611 K: Hash + Eq,
612 S: BuildHasher,
613{
614 fn extend<T: IntoIterator<Item = K>>(&mut self, iter: T) {
615 // from `hashbrown::HashSet::extend`:
616 // Keys may be already present or show multiple times in the iterator.
617 // Reserve the entire hint lower bound if the set is empty.
618 // Otherwise reserve half the hint (rounded up), so the set
619 // will only resize twice in the worst case.
620 let iter = iter.into_iter();
621 let reserve = if self.is_empty() {
622 iter.size_hint().0
623 } else {
624 (iter.size_hint().0 + 1) / 2
625 };
626
627 let guard = self.guard();
628 self.reserve(reserve, &guard);
629
630 for key in iter {
631 self.insert(key, &guard);
632 }
633 }
634}
635
636impl<'a, K, S> Extend<&'a K> for &HashSet<K, S>
637where
638 K: Copy + Hash + Eq + 'a,
639 S: BuildHasher,
640{
641 fn extend<T: IntoIterator<Item = &'a K>>(&mut self, iter: T) {
642 self.extend(iter.into_iter().copied());
643 }
644}
645
646impl<K, const N: usize> From<[K; N]> for HashSet<K, RandomState>
647where
648 K: Hash + Eq,
649{
650 fn from(arr: [K; N]) -> Self {
651 HashSet::from_iter(arr)
652 }
653}
654
655impl<K, S> FromIterator<K> for HashSet<K, S>
656where
657 K: Hash + Eq,
658 S: BuildHasher + Default,
659{
660 fn from_iter<T: IntoIterator<Item = K>>(iter: T) -> Self {
661 let mut iter = iter.into_iter();
662
663 if let Some(key) = iter.next() {
664 let (lower, _) = iter.size_hint();
665 let set = HashSet::with_capacity_and_hasher(lower.saturating_add(1), S::default());
666
667 // Ideally we could use an unprotected guard here. However, `insert`
668 // returns references to values that were replaced and retired, so
669 // we need a "real" guard. A `raw_insert` method that strictly returns
670 // pointers would fix this.
671 {
672 let set = set.pin();
673 set.insert(key);
674 for key in iter {
675 set.insert(key);
676 }
677 }
678
679 set
680 } else {
681 Self::default()
682 }
683 }
684}
685
686impl<K, S> Clone for HashSet<K, S>
687where
688 K: Clone + Hash + Eq,
689 S: BuildHasher + Clone,
690{
691 fn clone(&self) -> HashSet<K, S> {
692 let other = HashSet::builder()
693 .capacity(self.len())
694 .hasher(self.raw.hasher.clone())
695 .collector(self.raw.collector().clone())
696 .build();
697
698 {
699 let (guard1, guard2) = (&self.guard(), &other.guard());
700 for key in self.iter(guard1) {
701 other.insert(key.clone(), guard2);
702 }
703 }
704
705 other
706 }
707}
708
709/// A pinned reference to a [`HashSet`].
710///
711/// This type is created with [`HashSet::pin`] and can be used to easily access a [`HashSet`]
712/// without explicitly managing a guard. See the [crate-level documentation](crate#usage) for details.
713pub struct HashSetRef<'set, K, S, G> {
714 guard: MapGuard<G>,
715 set: &'set HashSet<K, S>,
716}
717
718impl<'set, K, S, G> HashSetRef<'set, K, S, G>
719where
720 K: Hash + Eq,
721 S: BuildHasher,
722 G: Guard,
723{
724 /// Returns a reference to the inner [`HashSet`].
725 #[inline]
726 pub fn set(&self) -> &'set HashSet<K, S> {
727 self.set
728 }
729
730 /// Returns the number of entries in the set.
731 ///
732 /// See [`HashSet::len`] for details.
733 #[inline]
734 pub fn len(&self) -> usize {
735 self.set.raw.len()
736 }
737
738 /// Returns `true` if the set is empty. Otherwise returns `false`.
739 ///
740 /// See [`HashSet::is_empty`] for details.
741 #[inline]
742 pub fn is_empty(&self) -> bool {
743 self.len() == 0
744 }
745
746 /// Returns `true` if the set contains a value for the specified key.
747 ///
748 /// See [`HashSet::contains`] for details.
749 #[inline]
750 pub fn contains<Q>(&self, key: &Q) -> bool
751 where
752 Q: Equivalent<K> + Hash + ?Sized,
753 {
754 self.get(key).is_some()
755 }
756
757 /// Returns a reference to the value corresponding to the key.
758 ///
759 /// See [`HashSet::get`] for details.
760 #[inline]
761 pub fn get<Q>(&self, key: &Q) -> Option<&K>
762 where
763 Q: Equivalent<K> + Hash + ?Sized,
764 {
765 match self.set.raw.get(key, &self.guard) {
766 Some((k, _)) => Some(k),
767 None => None,
768 }
769 }
770
771 /// Inserts a key-value pair into the set.
772 ///
773 /// See [`HashSet::insert`] for details.
774 #[inline]
775 pub fn insert(&self, key: K) -> bool {
776 match self.set.raw.insert(key, (), true, &self.guard) {
777 InsertResult::Inserted(_) => true,
778 InsertResult::Replaced(_) => false,
779 InsertResult::Error { .. } => unreachable!(),
780 }
781 }
782
783 /// Removes a key from the set, returning the value at the key if the key
784 /// was previously in the set.
785 ///
786 /// See [`HashSet::remove`] for details.
787 #[inline]
788 pub fn remove<Q>(&self, key: &Q) -> bool
789 where
790 Q: Equivalent<K> + Hash + ?Sized,
791 {
792 match self.set.raw.remove(key, &self.guard) {
793 Some((_, _)) => true,
794 None => false,
795 }
796 }
797
798 /// Clears the set, removing all values.
799 ///
800 /// See [`HashSet::clear`] for details.
801 #[inline]
802 pub fn clear(&self) {
803 self.set.raw.clear(&self.guard)
804 }
805
806 /// Retains only the elements specified by the predicate.
807 ///
808 /// See [`HashSet::retain`] for details.
809 #[inline]
810 pub fn retain<F>(&mut self, mut f: F)
811 where
812 F: FnMut(&K) -> bool,
813 {
814 self.set.raw.retain(|k, _| f(k), &self.guard)
815 }
816
817 /// Tries to reserve capacity for `additional` more elements to be inserted
818 /// in the set.
819 ///
820 /// See [`HashSet::reserve`] for details.
821 #[inline]
822 pub fn reserve(&self, additional: usize) {
823 self.set.raw.reserve(additional, &self.guard)
824 }
825
826 /// An iterator visiting all values in arbitrary order.
827 /// The iterator element type is `(&K, &V)`.
828 ///
829 /// See [`HashSet::iter`] for details.
830 #[inline]
831 pub fn iter(&self) -> Iter<'_, K, G> {
832 Iter {
833 raw: self.set.raw.iter(&self.guard),
834 }
835 }
836}
837
838impl<K, S, G> fmt::Debug for HashSetRef<'_, K, S, G>
839where
840 K: Hash + Eq + fmt::Debug,
841 S: BuildHasher,
842 G: Guard,
843{
844 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
845 f.debug_set().entries(self.iter()).finish()
846 }
847}
848
849impl<'a, K, S, G> IntoIterator for &'a HashSetRef<'_, K, S, G>
850where
851 K: Hash + Eq,
852 S: BuildHasher,
853 G: Guard,
854{
855 type Item = &'a K;
856 type IntoIter = Iter<'a, K, G>;
857
858 fn into_iter(self) -> Self::IntoIter {
859 self.iter()
860 }
861}
862
863/// An iterator over a set's entries.
864///
865/// This struct is created by the [`iter`](HashSet::iter) method on [`HashSet`]. See its documentation for details.
866pub struct Iter<'g, K, G> {
867 raw: raw::Iter<'g, K, (), MapGuard<G>>,
868}
869
870impl<'g, K: 'g, G> Iterator for Iter<'g, K, G>
871where
872 G: Guard,
873{
874 type Item = &'g K;
875
876 #[inline]
877 fn next(&mut self) -> Option<Self::Item> {
878 self.raw.next().map(|(k, _)| k)
879 }
880}
881
882impl<K, G> fmt::Debug for Iter<'_, K, G>
883where
884 K: fmt::Debug,
885 G: Guard,
886{
887 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
888 f.debug_list()
889 .entries(Iter {
890 raw: self.raw.clone(),
891 })
892 .finish()
893 }
894}