Skip to main content

tuwunel_core/utils/set/
mod.rs

1//! Set operations on iterators and streams.
2//!
3//! Sorted variants require their inputs to be ascending under a total order
4//! and preserve multiplicity. The unsorted [`intersection`] runs in O(n*m)
5//! and is provided for convenience when sorting is unavailable.
6
7mod difference_sorted_stream2;
8mod intersection;
9mod intersection_sorted;
10mod intersection_sorted_stream2;
11
12use std::{borrow::Borrow, collections::BTreeSet, pin::Pin, task::ready};
13
14use futures::{
15	Stream,
16	task::{Context, Poll},
17};
18
19pub use self::{
20	difference_sorted_stream2::difference_sorted_stream2, intersection::intersection,
21	intersection_sorted::intersection_sorted,
22	intersection_sorted_stream2::intersection_sorted_stream2,
23};
24
25/// Reports whether `allowed` is empty or contains `item`.
26///
27/// An empty set acts as an unrestricted allowlist and selects every candidate.
28#[inline]
29#[must_use]
30pub fn is_empty_or_contains<T, Q>(allowed: &BTreeSet<T>, item: &Q) -> bool
31where
32	T: Borrow<Q> + Ord,
33	Q: Ord + ?Sized,
34{
35	allowed.is_empty() || allowed.contains(item)
36}
37
38/// Lazily fill the cached head of `stream` into `peeked` and return a borrow.
39///
40/// On entry, `Some(v)` in `peeked` is a previously-buffered head that has not
41/// yet been consumed; `None` means the head must be pulled from the stream.
42/// Returns `Ready(Some(&v))` when a head is available, `Ready(None)` once
43/// `stream` is exhausted, or `Pending` when waiting on the stream.
44fn poll_head<'p, S, T>(
45	stream: Pin<&mut S>,
46	peeked: &'p mut Option<T>,
47	cx: &mut Context<'_>,
48) -> Poll<Option<&'p T>>
49where
50	S: Stream<Item = T>,
51{
52	if peeked.is_none() {
53		*peeked = ready!(stream.poll_next(cx));
54	}
55
56	Poll::Ready(peeked.as_ref())
57}