weak_table/
weak_hash_set.rs

1//! A hash set where the elements are held by weak pointers and compared by value.
2
3use crate::common::*;
4use crate::compat::*;
5use crate::inner;
6
7use super::traits::*;
8use super::weak_key_hash_map as base;
9
10pub use super::WeakHashSet;
11
12universal_hashless_members! {
13    WeakHashSet ("`WeakHashSet`", a "set")
14    base::WeakKeyHashMap::with_capacity_and_hasher
15    {T}
16}
17
18impl<T: WeakKey, S: BuildHasher> WeakHashSet<T, S> {
19    universal_key_independent_members! {"elements"}
20
21    // TODO: Non-ptr WeakHashSet should probably have `get` method.
22
23    /// Returns true if the set contains the specified key.
24    ///
25    /// expected *O*(1) time; worst-case *O*(*p*) time
26    pub fn contains<Q>(&self, key: &Q) -> bool
27    where
28        Q: ?Sized + Eq + Hash,
29        T::Key: Borrow<Q>,
30    {
31        self.0.contains_key(key)
32    }
33
34    /// Gets a strong reference to the given key, if found.
35    ///
36    /// # Examples
37    ///
38    /// ```
39    /// use weak_table::WeakHashSet;
40    /// use std::rc::{Rc, Weak};
41    /// use std::ops::Deref;
42    /// # fn x() {
43    /// # type WeakHashSet<T> = weak_table::WeakHashSet<T, ahash::RandomState>;
44    ///
45    /// let mut set: WeakHashSet<Weak<String>> = WeakHashSet::default();
46    ///
47    /// let a = Rc::new("a".to_owned());
48    /// set.insert(a.clone());
49    ///
50    /// let also_a = set.get("a").unwrap();
51    ///
52    /// assert!(Rc::ptr_eq( &a, &also_a ));
53    /// # }
54    /// # x();
55    /// ```
56    ///
57    /// expected *O*(1) time; worst-case *O*(*p*) time
58    pub fn get<Q>(&self, key: &Q) -> Option<T::Strong>
59    where
60        Q: ?Sized + Eq + Hash,
61        T::Key: Borrow<Q>,
62    {
63        self.0.get_key(key)
64    }
65
66    /// Unconditionally inserts `key` into this set,
67    /// replacing any previous matching entry.
68    ///
69    /// Returns true if the key was absent before, and false otherwise.
70    ///
71    /// (Note that unlike `HashSet::insert`, this insert method always replaces
72    /// the key.)
73    ///
74    /// expected *O*(1) time; worst-case *O*(*p*) time
75    pub fn insert(&mut self, key: T::Strong) -> bool {
76        self.0.insert(key, ()).is_some()
77    }
78
79    /// Removes the entry matching the given key, if it exists.
80    ///
81    /// Returns true if an entry was removed.
82    ///
83    /// expected *O*(1) time; worst-case *O*(*p*) time
84    pub fn remove<Q>(&mut self, key: &Q) -> bool
85    where
86        Q: ?Sized + Eq + Hash,
87        T::Key: Borrow<Q>,
88    {
89        self.0.remove(key).is_some()
90    }
91
92    /// Removes the entry matching the given key, if it exists, and return the it.
93    ///
94    /// expected *O*(1) time; worst-case *O*(*p*) time
95    pub fn take<Q>(&mut self, key: &Q) -> Option<T::Strong>
96    where
97        Q: ?Sized + Eq + Hash,
98        T::Key: Borrow<Q>,
99    {
100        self.0.remove_entry(key).map(|(k, ())| k)
101    }
102
103    /// Removes all elements not satisfying the given predicate.
104    ///
105    /// Also removes any expired elements.
106    ///
107    /// *O*(*n*) time
108    pub fn retain<F>(&mut self, mut f: F)
109    where
110        F: FnMut(T::Strong) -> bool,
111    {
112        self.0.retain(|k, _| f(k));
113    }
114
115    /// Is self a subset of other?
116    ///
117    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
118    /// `self.capacity()` and *q* is the length of the probe sequences
119    /// in `other`)
120    pub fn is_subset<S1>(&self, other: &WeakHashSet<T, S1>) -> bool
121    where
122        S1: BuildHasher,
123    {
124        self.0.domain_is_subset(&other.0)
125    }
126
127    /// Helper: return true if 'self' contains 'item'.
128    fn contains_strong(&self, item: &T::Strong) -> bool {
129        T::with_key(item, |k| self.contains(k))
130    }
131
132    set_op_methods! {WeakHashSet}
133    set_relationships! {WeakHashSet}
134}
135
136/// An iterator over the elements of a set.
137pub struct Iter<'a, T: 'a>(base::Keys<'a, T, ()>);
138
139impl<'a, T: WeakElement> Iterator for Iter<'a, T> {
140    type Item = T::Strong;
141
142    fn next(&mut self) -> Option<Self::Item> {
143        self.0.next()
144    }
145
146    fn size_hint(&self) -> (usize, Option<usize>) {
147        self.0.size_hint()
148    }
149}
150
151/// A consuming iterator over the elements of a set.
152pub struct IntoIter<T>(base::IntoIter<T, ()>);
153
154impl<T: WeakElement> Iterator for IntoIter<T> {
155    type Item = T::Strong;
156
157    fn next(&mut self) -> Option<Self::Item> {
158        self.0.next().map(|pair| pair.0)
159    }
160
161    fn size_hint(&self) -> (usize, Option<usize>) {
162        self.0.size_hint()
163    }
164}
165
166/// A draining iterator over the elements of a set.
167///
168/// Once this iterator is dropped, all elements are removed from the set,
169/// whether the iterator itself was drained or not.
170pub struct Drain<'a, T: 'a>(base::Drain<'a, T, ()>);
171
172impl<'a, T: WeakElement> Iterator for Drain<'a, T> {
173    type Item = T::Strong;
174
175    fn next(&mut self) -> Option<Self::Item> {
176        self.0.next().map(|pair| pair.0)
177    }
178
179    fn size_hint(&self) -> (usize, Option<usize>) {
180        self.0.size_hint()
181    }
182}
183
184impl<T: WeakElement, S> WeakHashSet<T, S> {
185    /// Gets an iterator over the elements of this set.
186    ///
187    /// *O*(1) time
188    pub fn iter(&self) -> Iter<'_, T> {
189        Iter(self.0.keys())
190    }
191
192    /// Gets a draining iterator, which removes all the elements but retains the storage.
193    ///
194    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
195    pub fn drain(&mut self) -> Drain<'_, T> {
196        Drain(self.0.drain())
197    }
198
199    /// Gets an iterator that removes and returns elements matching a given predicate.
200    ///
201    /// Expired elements are also removed.
202    ///
203    /// If this iterator is dropped before it is completed, then no further
204    /// elements are removed.
205    /// (This is in contrast to the behavior of [`drain`](Self::drain)).
206    ///
207    /// *O*(1) time
208    pub fn extract_if<'a, F>(&'a mut self, mut f: F) -> ExtractIf<'a, T, F>
209    where
210        F: FnMut(T::Strong) -> bool + 'a,
211    {
212        ExtractIf {
213            inner: self.0 .0.extract_if(move |e| {
214                if let Some(k) = e.0.val.view() {
215                    f(k)
216                } else {
217                    true
218                }
219            }),
220            _phantom: PhantomData,
221        }
222    }
223}
224
225/// An iterator that removes members that match a given predicate.
226#[must_use = "iterators do nothing unless consumed; \
227    consider using `retain` instead"]
228pub struct ExtractIf<'a, T: WeakElement, F> {
229    /// The underlying iterator.
230    inner: inner::ExtractIf<'a, inner::WeakK<T>, inner::Owned<()>>,
231    /// A marker so that F does not appear unused.
232    _phantom: PhantomData<F>,
233}
234
235impl<'a, T: WeakElement, F> Iterator for ExtractIf<'a, T, F> {
236    type Item = T::Strong;
237
238    fn next(&mut self) -> Option<Self::Item> {
239        self.inner.next().map(|(k, ())| k)
240    }
241
242    fn size_hint(&self) -> (usize, Option<usize>) {
243        self.inner.size_hint()
244    }
245}
246
247set_op_types! {WeakHashSet where {T: WeakKey}}
248set_operators! {WeakHashSet where {T: WeakKey}}
249
250impl<T, S, S1> PartialEq<WeakHashSet<T, S1>> for WeakHashSet<T, S>
251where
252    T: WeakKey,
253    S: BuildHasher,
254    S1: BuildHasher,
255{
256    fn eq(&self, other: &WeakHashSet<T, S1>) -> bool {
257        self.0 == other.0
258    }
259}
260
261impl<T: WeakKey, S: BuildHasher> Eq for WeakHashSet<T, S> where T::Key: Eq {}
262
263impl<T, S> FromIterator<T::Strong> for WeakHashSet<T, S>
264where
265    T: WeakKey,
266    S: BuildHasher + Default,
267{
268    fn from_iter<I: IntoIterator<Item = T::Strong>>(iter: I) -> Self {
269        WeakHashSet(base::WeakKeyHashMap::<T, (), S>::from_iter(
270            iter.into_iter().map(|k| (k, ())),
271        ))
272    }
273}
274
275#[cfg(any(test, feature = "std", feature = "ahash"))]
276impl<T: WeakKey, const N: usize> From<[T::Strong; N]> for WeakHashSet<T, RandomState> {
277    /// Converts an array of elements into a set.
278    ///
279    /// If any entries in the array are equal,
280    /// all but one of the corresponding values will be dropped.
281    fn from(value: [T::Strong; N]) -> Self {
282        Self::from_iter(value)
283    }
284}
285
286impl<T: WeakKey, S: BuildHasher> Extend<T::Strong> for WeakHashSet<T, S> {
287    fn extend<I: IntoIterator<Item = T::Strong>>(&mut self, iter: I) {
288        self.0.extend(iter.into_iter().map(|k| (k, ())));
289    }
290}
291
292impl<T: WeakElement, S> Debug for WeakHashSet<T, S>
293where
294    T::Strong: Debug,
295{
296    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
297        f.debug_set().entries(self.iter()).finish()
298    }
299}
300
301impl<T: WeakElement, S> IntoIterator for WeakHashSet<T, S> {
302    type Item = T::Strong;
303    type IntoIter = IntoIter<T>;
304
305    /// Creates an owning iterator from `self`.
306    ///
307    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
308    fn into_iter(self) -> Self::IntoIter {
309        IntoIter(self.0.into_iter())
310    }
311}
312
313impl<'a, T: WeakElement, S> IntoIterator for &'a WeakHashSet<T, S> {
314    type Item = T::Strong;
315    type IntoIter = Iter<'a, T>;
316
317    /// Creates a borrowing iterator from `self`.
318    ///
319    /// *O*(1) time
320    fn into_iter(self) -> Self::IntoIter {
321        Iter(self.0.keys())
322    }
323}
324
325/// Helper: Given two references to sets, return them in ascending order of
326/// len().
327fn sort_by_size<'a, T: WeakKey, S: BuildHasher>(
328    a: &'a WeakHashSet<T, S>,
329    b: &'a WeakHashSet<T, S>,
330) -> (&'a WeakHashSet<T, S>, &'a WeakHashSet<T, S>) {
331    if a.len() < b.len() {
332        (a, b)
333    } else {
334        (b, a)
335    }
336}
337
338#[cfg(test)]
339mod test {
340    // TODO 050: remove.
341    #![cfg_attr(feature = "ahash", allow(deprecated))]
342
343    use super::*;
344    use crate::{
345        compat::rc::{Rc, Weak},
346        tests::util::VecDebugAsSet,
347    };
348
349    crate::tests::common::empty_constructor_tests! {WeakHashSet<Weak<u8>>}
350    crate::tests::set_operations::set_operation_tests! {WeakHashSet, 0}
351
352    // Regression check for https://github.com/tov/weak-table-rs/issues/22
353    #[test]
354    fn test_retain_regresion() {
355        // Run multiple iterations, since this was a heisenbug.
356        for _ in 0..20 {
357            let mut set: WeakHashSet<Weak<u8>> = WeakHashSet::default();
358            let mut preserve_vals = Vec::new();
359
360            const N: u8 = 50;
361
362            for i in 0..N {
363                let rc = Rc::new(i);
364                preserve_vals.push(rc.clone());
365                set.insert(rc);
366            }
367
368            let rc_n = Rc::new(N);
369            set.insert(rc_n.clone());
370
371            drop(preserve_vals);
372
373            let mut retain_called_on = Vec::new();
374            set.retain(|val| {
375                retain_called_on.push(val);
376                false
377            });
378
379            assert_eq!(retain_called_on, vec![rc_n]);
380        }
381    }
382
383    #[test]
384    fn test_take() {
385        let s = [Rc::new(1), Rc::new(2), Rc::new(3)];
386        let mut set: WeakHashSet<Weak<u32>> = s.clone().into();
387        assert_eq!(set.iter().count(), 3);
388
389        let v = set.take(&2);
390        assert_eq!(v, Some(Rc::new(2)));
391        assert_eq!(set.iter().count(), 2);
392        assert!(Rc::ptr_eq(&v.expect("absent suddenly!"), &s[1]));
393
394        let v = set.take(&2);
395        assert!(v.is_none());
396    }
397
398    #[test]
399    fn test_debug() {
400        let s = [Rc::new(1), Rc::new(2)];
401        let set: WeakHashSet<Weak<u32>> = s.clone().into();
402        let v: VecDebugAsSet<_> = set.iter().collect();
403        assert_eq!(format!("{v:?}"), format!("{set:?}"));
404    }
405}
weak_table/weak_hash_set.rs

weak_table/
weak_hash_set.rs
