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

weak_table/
weak_hash_set.rs
