1 //! Rayon extensions for `HashSet`.
4 use crate::hash_set
::HashSet
;
5 use crate::raw
::{Allocator, Global}
;
6 use core
::hash
::{BuildHasher, Hash}
;
7 use rayon
::iter
::plumbing
::UnindexedConsumer
;
8 use rayon
::iter
::{FromParallelIterator, IntoParallelIterator, ParallelExtend, ParallelIterator}
;
10 /// Parallel iterator over elements of a consumed set.
12 /// This iterator is created by the [`into_par_iter`] method on [`HashSet`]
13 /// (provided by the [`IntoParallelIterator`] trait).
14 /// See its documentation for more.
16 /// [`into_par_iter`]: /hashbrown/struct.HashSet.html#method.into_par_iter
17 /// [`HashSet`]: /hashbrown/struct.HashSet.html
18 /// [`IntoParallelIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelIterator.html
19 pub struct IntoParIter
<T
, A
: Allocator
= Global
> {
20 inner
: map
::IntoParIter
<T
, (), A
>,
23 impl<T
: Send
, A
: Allocator
+ Send
> ParallelIterator
for IntoParIter
<T
, A
> {
26 fn drive_unindexed
<C
>(self, consumer
: C
) -> C
::Result
28 C
: UnindexedConsumer
<Self::Item
>,
30 self.inner
.map(|(k
, _
)| k
).drive_unindexed(consumer
)
34 /// Parallel draining iterator over entries of a set.
36 /// This iterator is created by the [`par_drain`] method on [`HashSet`].
37 /// See its documentation for more.
39 /// [`par_drain`]: /hashbrown/struct.HashSet.html#method.par_drain
40 /// [`HashSet`]: /hashbrown/struct.HashSet.html
41 pub struct ParDrain
<'a
, T
, A
: Allocator
= Global
> {
42 inner
: map
::ParDrain
<'a
, T
, (), A
>,
45 impl<T
: Send
, A
: Allocator
+ Send
+ Sync
> ParallelIterator
for ParDrain
<'_
, T
, A
> {
48 fn drive_unindexed
<C
>(self, consumer
: C
) -> C
::Result
50 C
: UnindexedConsumer
<Self::Item
>,
52 self.inner
.map(|(k
, _
)| k
).drive_unindexed(consumer
)
56 /// Parallel iterator over shared references to elements in a set.
58 /// This iterator is created by the [`par_iter`] method on [`HashSet`]
59 /// (provided by the [`IntoParallelRefIterator`] trait).
60 /// See its documentation for more.
62 /// [`par_iter`]: /hashbrown/struct.HashSet.html#method.par_iter
63 /// [`HashSet`]: /hashbrown/struct.HashSet.html
64 /// [`IntoParallelRefIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelRefIterator.html
65 pub struct ParIter
<'a
, T
> {
66 inner
: map
::ParKeys
<'a
, T
, ()>,
69 impl<'a
, T
: Sync
> ParallelIterator
for ParIter
<'a
, T
> {
72 fn drive_unindexed
<C
>(self, consumer
: C
) -> C
::Result
74 C
: UnindexedConsumer
<Self::Item
>,
76 self.inner
.drive_unindexed(consumer
)
80 /// Parallel iterator over shared references to elements in the difference of
83 /// This iterator is created by the [`par_difference`] method on [`HashSet`].
84 /// See its documentation for more.
86 /// [`par_difference`]: /hashbrown/struct.HashSet.html#method.par_difference
87 /// [`HashSet`]: /hashbrown/struct.HashSet.html
88 pub struct ParDifference
<'a
, T
, S
, A
: Allocator
= Global
> {
89 a
: &'a HashSet
<T
, S
, A
>,
90 b
: &'a HashSet
<T
, S
, A
>,
93 impl<'a
, T
, S
, A
> ParallelIterator
for ParDifference
<'a
, T
, S
, A
>
96 S
: BuildHasher
+ Sync
,
101 fn drive_unindexed
<C
>(self, consumer
: C
) -> C
::Result
103 C
: UnindexedConsumer
<Self::Item
>,
107 .filter(|&x
| !self.b
.contains(x
))
108 .drive_unindexed(consumer
)
112 /// Parallel iterator over shared references to elements in the symmetric
113 /// difference of sets.
115 /// This iterator is created by the [`par_symmetric_difference`] method on
117 /// See its documentation for more.
119 /// [`par_symmetric_difference`]: /hashbrown/struct.HashSet.html#method.par_symmetric_difference
120 /// [`HashSet`]: /hashbrown/struct.HashSet.html
121 pub struct ParSymmetricDifference
<'a
, T
, S
, A
: Allocator
= Global
> {
122 a
: &'a HashSet
<T
, S
, A
>,
123 b
: &'a HashSet
<T
, S
, A
>,
126 impl<'a
, T
, S
, A
> ParallelIterator
for ParSymmetricDifference
<'a
, T
, S
, A
>
129 S
: BuildHasher
+ Sync
,
134 fn drive_unindexed
<C
>(self, consumer
: C
) -> C
::Result
136 C
: UnindexedConsumer
<Self::Item
>,
139 .par_difference(self.b
)
140 .chain(self.b
.par_difference(self.a
))
141 .drive_unindexed(consumer
)
145 /// Parallel iterator over shared references to elements in the intersection of
148 /// This iterator is created by the [`par_intersection`] method on [`HashSet`].
149 /// See its documentation for more.
151 /// [`par_intersection`]: /hashbrown/struct.HashSet.html#method.par_intersection
152 /// [`HashSet`]: /hashbrown/struct.HashSet.html
153 pub struct ParIntersection
<'a
, T
, S
, A
: Allocator
= Global
> {
154 a
: &'a HashSet
<T
, S
, A
>,
155 b
: &'a HashSet
<T
, S
, A
>,
158 impl<'a
, T
, S
, A
> ParallelIterator
for ParIntersection
<'a
, T
, S
, A
>
161 S
: BuildHasher
+ Sync
,
166 fn drive_unindexed
<C
>(self, consumer
: C
) -> C
::Result
168 C
: UnindexedConsumer
<Self::Item
>,
172 .filter(|&x
| self.b
.contains(x
))
173 .drive_unindexed(consumer
)
177 /// Parallel iterator over shared references to elements in the union of sets.
179 /// This iterator is created by the [`par_union`] method on [`HashSet`].
180 /// See its documentation for more.
182 /// [`par_union`]: /hashbrown/struct.HashSet.html#method.par_union
183 /// [`HashSet`]: /hashbrown/struct.HashSet.html
184 pub struct ParUnion
<'a
, T
, S
, A
: Allocator
= Global
> {
185 a
: &'a HashSet
<T
, S
, A
>,
186 b
: &'a HashSet
<T
, S
, A
>,
189 impl<'a
, T
, S
, A
> ParallelIterator
for ParUnion
<'a
, T
, S
, A
>
192 S
: BuildHasher
+ Sync
,
197 fn drive_unindexed
<C
>(self, consumer
: C
) -> C
::Result
199 C
: UnindexedConsumer
<Self::Item
>,
201 // We'll iterate one set in full, and only the remaining difference from the other.
202 // Use the smaller set for the difference in order to reduce hash lookups.
203 let (smaller
, larger
) = if self.a
.len() <= self.b
.len() {
210 .chain(smaller
.par_difference(larger
))
211 .drive_unindexed(consumer
)
215 impl<T
, S
, A
> HashSet
<T
, S
, A
>
218 S
: BuildHasher
+ Sync
,
221 /// Visits (potentially in parallel) the values representing the union,
222 /// i.e. all the values in `self` or `other`, without duplicates.
223 #[cfg_attr(feature = "inline-more", inline)]
224 pub fn par_union
<'a
>(&'a
self, other
: &'a
Self) -> ParUnion
<'a
, T
, S
, A
> {
225 ParUnion { a: self, b: other }
228 /// Visits (potentially in parallel) the values representing the difference,
229 /// i.e. the values that are in `self` but not in `other`.
230 #[cfg_attr(feature = "inline-more", inline)]
231 pub fn par_difference
<'a
>(&'a
self, other
: &'a
Self) -> ParDifference
<'a
, T
, S
, A
> {
232 ParDifference { a: self, b: other }
235 /// Visits (potentially in parallel) the values representing the symmetric
236 /// difference, i.e. the values that are in `self` or in `other` but not in both.
237 #[cfg_attr(feature = "inline-more", inline)]
238 pub fn par_symmetric_difference
<'a
>(
241 ) -> ParSymmetricDifference
<'a
, T
, S
, A
> {
242 ParSymmetricDifference { a: self, b: other }
245 /// Visits (potentially in parallel) the values representing the
246 /// intersection, i.e. the values that are both in `self` and `other`.
247 #[cfg_attr(feature = "inline-more", inline)]
248 pub fn par_intersection
<'a
>(&'a
self, other
: &'a
Self) -> ParIntersection
<'a
, T
, S
, A
> {
249 ParIntersection { a: self, b: other }
252 /// Returns `true` if `self` has no elements in common with `other`.
253 /// This is equivalent to checking for an empty intersection.
255 /// This method runs in a potentially parallel fashion.
256 pub fn par_is_disjoint(&self, other
: &Self) -> bool
{
257 self.into_par_iter().all(|x
| !other
.contains(x
))
260 /// Returns `true` if the set is a subset of another,
261 /// i.e. `other` contains at least all the values in `self`.
263 /// This method runs in a potentially parallel fashion.
264 pub fn par_is_subset(&self, other
: &Self) -> bool
{
265 if self.len() <= other
.len() {
266 self.into_par_iter().all(|x
| other
.contains(x
))
272 /// Returns `true` if the set is a superset of another,
273 /// i.e. `self` contains at least all the values in `other`.
275 /// This method runs in a potentially parallel fashion.
276 pub fn par_is_superset(&self, other
: &Self) -> bool
{
277 other
.par_is_subset(self)
280 /// Returns `true` if the set is equal to another,
281 /// i.e. both sets contain the same values.
283 /// This method runs in a potentially parallel fashion.
284 pub fn par_eq(&self, other
: &Self) -> bool
{
285 self.len() == other
.len() && self.par_is_subset(other
)
289 impl<T
, S
, A
> HashSet
<T
, S
, A
>
294 /// Consumes (potentially in parallel) all values in an arbitrary order,
295 /// while preserving the set's allocated memory for reuse.
296 #[cfg_attr(feature = "inline-more", inline)]
297 pub fn par_drain(&mut self) -> ParDrain
<'_
, T
, A
> {
299 inner
: self.map
.par_drain(),
304 impl<T
: Send
, S
, A
: Allocator
+ Send
> IntoParallelIterator
for HashSet
<T
, S
, A
> {
306 type Iter
= IntoParIter
<T
, A
>;
308 #[cfg_attr(feature = "inline-more", inline)]
309 fn into_par_iter(self) -> Self::Iter
{
311 inner
: self.map
.into_par_iter(),
316 impl<'a
, T
: Sync
, S
, A
: Allocator
> IntoParallelIterator
for &'a HashSet
<T
, S
, A
> {
318 type Iter
= ParIter
<'a
, T
>;
320 #[cfg_attr(feature = "inline-more", inline)]
321 fn into_par_iter(self) -> Self::Iter
{
323 inner
: self.map
.par_keys(),
328 /// Collect values from a parallel iterator into a hashset.
329 impl<T
, S
> FromParallelIterator
<T
> for HashSet
<T
, S
, Global
>
332 S
: BuildHasher
+ Default
,
334 fn from_par_iter
<P
>(par_iter
: P
) -> Self
336 P
: IntoParallelIterator
<Item
= T
>,
338 let mut set
= HashSet
::default();
339 set
.par_extend(par_iter
);
344 /// Extend a hash set with items from a parallel iterator.
345 impl<T
, S
> ParallelExtend
<T
> for HashSet
<T
, S
, Global
>
350 fn par_extend
<I
>(&mut self, par_iter
: I
)
352 I
: IntoParallelIterator
<Item
= T
>,
354 extend(self, par_iter
);
358 /// Extend a hash set with copied items from a parallel iterator.
359 impl<'a
, T
, S
> ParallelExtend
<&'a T
> for HashSet
<T
, S
, Global
>
361 T
: 'a
+ Copy
+ Eq
+ Hash
+ Sync
,
364 fn par_extend
<I
>(&mut self, par_iter
: I
)
366 I
: IntoParallelIterator
<Item
= &'a T
>,
368 extend(self, par_iter
);
372 // This is equal to the normal `HashSet` -- no custom advantage.
373 fn extend
<T
, S
, I
, A
>(set
: &mut HashSet
<T
, S
, A
>, par_iter
: I
)
378 I
: IntoParallelIterator
,
379 HashSet
<T
, S
, A
>: Extend
<I
::Item
>,
381 let (list
, len
) = super::helpers
::collect(par_iter
);
383 // Values may be already present or show multiple times in the iterator.
384 // Reserve the entire length if the set is empty.
385 // Otherwise reserve half the length (rounded up), so the set
386 // will only resize twice in the worst case.
387 let reserve
= if set
.is_empty() { len }
else { (len + 1) / 2 }
;
388 set
.reserve(reserve
);
397 use core
::sync
::atomic
::{AtomicUsize, Ordering}
;
399 use rayon
::prelude
::*;
401 use crate::hash_set
::HashSet
;
405 let mut xs
= HashSet
::new();
406 let mut ys
= HashSet
::new();
407 assert
!(xs
.par_is_disjoint(&ys
));
408 assert
!(ys
.par_is_disjoint(&xs
));
409 assert
!(xs
.insert(5));
410 assert
!(ys
.insert(11));
411 assert
!(xs
.par_is_disjoint(&ys
));
412 assert
!(ys
.par_is_disjoint(&xs
));
413 assert
!(xs
.insert(7));
414 assert
!(xs
.insert(19));
415 assert
!(xs
.insert(4));
416 assert
!(ys
.insert(2));
417 assert
!(ys
.insert(-11));
418 assert
!(xs
.par_is_disjoint(&ys
));
419 assert
!(ys
.par_is_disjoint(&xs
));
420 assert
!(ys
.insert(7));
421 assert
!(!xs
.par_is_disjoint(&ys
));
422 assert
!(!ys
.par_is_disjoint(&xs
));
426 fn test_subset_and_superset() {
427 let mut a
= HashSet
::new();
428 assert
!(a
.insert(0));
429 assert
!(a
.insert(5));
430 assert
!(a
.insert(11));
431 assert
!(a
.insert(7));
433 let mut b
= HashSet
::new();
434 assert
!(b
.insert(0));
435 assert
!(b
.insert(7));
436 assert
!(b
.insert(19));
437 assert
!(b
.insert(250));
438 assert
!(b
.insert(11));
439 assert
!(b
.insert(200));
441 assert
!(!a
.par_is_subset(&b
));
442 assert
!(!a
.par_is_superset(&b
));
443 assert
!(!b
.par_is_subset(&a
));
444 assert
!(!b
.par_is_superset(&a
));
446 assert
!(b
.insert(5));
448 assert
!(a
.par_is_subset(&b
));
449 assert
!(!a
.par_is_superset(&b
));
450 assert
!(!b
.par_is_subset(&a
));
451 assert
!(b
.par_is_superset(&a
));
456 let mut a
= HashSet
::new();
458 assert
!(a
.insert(i
));
460 let observed
= AtomicUsize
::new(0);
461 a
.par_iter().for_each(|k
| {
462 observed
.fetch_or(1 << *k
, Ordering
::Relaxed
);
464 assert_eq
!(observed
.into_inner(), 0xFFFF_FFFF);
468 fn test_intersection() {
469 let mut a
= HashSet
::new();
470 let mut b
= HashSet
::new();
472 assert
!(a
.insert(11));
473 assert
!(a
.insert(1));
474 assert
!(a
.insert(3));
475 assert
!(a
.insert(77));
476 assert
!(a
.insert(103));
477 assert
!(a
.insert(5));
478 assert
!(a
.insert(-5));
480 assert
!(b
.insert(2));
481 assert
!(b
.insert(11));
482 assert
!(b
.insert(77));
483 assert
!(b
.insert(-9));
484 assert
!(b
.insert(-42));
485 assert
!(b
.insert(5));
486 assert
!(b
.insert(3));
488 let expected
= [3, 5, 11, 77];
490 .par_intersection(&b
)
492 assert
!(expected
.contains(x
));
496 assert_eq
!(i
, expected
.len());
500 fn test_difference() {
501 let mut a
= HashSet
::new();
502 let mut b
= HashSet
::new();
504 assert
!(a
.insert(1));
505 assert
!(a
.insert(3));
506 assert
!(a
.insert(5));
507 assert
!(a
.insert(9));
508 assert
!(a
.insert(11));
510 assert
!(b
.insert(3));
511 assert
!(b
.insert(9));
513 let expected
= [1, 5, 11];
517 assert
!(expected
.contains(x
));
521 assert_eq
!(i
, expected
.len());
525 fn test_symmetric_difference() {
526 let mut a
= HashSet
::new();
527 let mut b
= HashSet
::new();
529 assert
!(a
.insert(1));
530 assert
!(a
.insert(3));
531 assert
!(a
.insert(5));
532 assert
!(a
.insert(9));
533 assert
!(a
.insert(11));
535 assert
!(b
.insert(-2));
536 assert
!(b
.insert(3));
537 assert
!(b
.insert(9));
538 assert
!(b
.insert(14));
539 assert
!(b
.insert(22));
541 let expected
= [-2, 1, 5, 11, 14, 22];
543 .par_symmetric_difference(&b
)
545 assert
!(expected
.contains(x
));
549 assert_eq
!(i
, expected
.len());
554 let mut a
= HashSet
::new();
555 let mut b
= HashSet
::new();
557 assert
!(a
.insert(1));
558 assert
!(a
.insert(3));
559 assert
!(a
.insert(5));
560 assert
!(a
.insert(9));
561 assert
!(a
.insert(11));
562 assert
!(a
.insert(16));
563 assert
!(a
.insert(19));
564 assert
!(a
.insert(24));
566 assert
!(b
.insert(-2));
567 assert
!(b
.insert(1));
568 assert
!(b
.insert(5));
569 assert
!(b
.insert(9));
570 assert
!(b
.insert(13));
571 assert
!(b
.insert(19));
573 let expected
= [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
577 assert
!(expected
.contains(x
));
581 assert_eq
!(i
, expected
.len());
585 fn test_from_iter() {
586 let xs
= [1, 2, 3, 4, 5, 6, 7, 8, 9];
588 let set
: HashSet
<_
> = xs
.par_iter().cloned().collect();
591 assert
!(set
.contains(x
));
596 fn test_move_iter() {
598 let mut hs
= HashSet
::new();
606 let v
= hs
.into_par_iter().collect
::<Vec
<char>>();
607 assert
!(v
== ['a'
, 'b'
] || v
== ['b'
, 'a'
]);
612 // These constants once happened to expose a bug in insert().
613 // I'm keeping them around to prevent a regression.
614 let mut s1
= HashSet
::new();
620 let mut s2
= HashSet
::new();
625 assert
!(!s1
.par_eq(&s2
));
629 assert
!(s1
.par_eq(&s2
));
633 fn test_extend_ref() {
634 let mut a
= HashSet
::new();
637 a
.par_extend(&[2, 3, 4][..]);
639 assert_eq
!(a
.len(), 4);
640 assert
!(a
.contains(&1));
641 assert
!(a
.contains(&2));
642 assert
!(a
.contains(&3));
643 assert
!(a
.contains(&4));
645 let mut b
= HashSet
::new();
651 assert_eq
!(a
.len(), 6);
652 assert
!(a
.contains(&1));
653 assert
!(a
.contains(&2));
654 assert
!(a
.contains(&3));
655 assert
!(a
.contains(&4));
656 assert
!(a
.contains(&5));
657 assert
!(a
.contains(&6));