#[cfg(test)]
mod tests;
use super::{super::request::TimedCeremony, BuildIdentityHasher};
#[cfg(doc)]
use core::hash::Hasher;
use core::hash::{BuildHasher, Hash};
use hashbrown::{
Equivalent, TryReserveError,
hash_set::{Drain, Entry, ExtractIf, HashSet},
};
#[cfg(any(doc, not(feature = "serializable_server_state")))]
use std::time::Instant;
#[cfg(feature = "serializable_server_state")]
use std::time::SystemTime;
#[derive(Debug)]
pub struct MaxLenHashSet<T, S = BuildIdentityHasher>(HashSet<T, S>, usize);
impl<T> MaxLenHashSet<T, BuildIdentityHasher> {
#[inline]
#[must_use]
pub fn new(max_len: usize) -> Self {
Self::with_hasher(max_len, BuildIdentityHasher)
}
}
impl<T, S> MaxLenHashSet<T, S> {
const fn requested_capacity(max_len: usize) -> Result<usize, TryReserveError> {
if max_len <= usize::MAX >> 1u8 {
Ok(max_len << 1u8)
} else {
Err(TryReserveError::CapacityOverflow)
}
}
#[inline]
pub const fn max_len(&self) -> usize {
self.1
}
#[inline]
pub fn clear(&mut self) {
self.0.clear();
}
#[inline]
pub fn drain(&mut self) -> Drain<'_, T> {
self.0.drain()
}
#[inline]
pub fn extract_if<F: FnMut(&T) -> bool>(&mut self, f: F) -> ExtractIf<'_, T, F> {
self.0.extract_if(f)
}
#[expect(
clippy::expect_used,
reason = "purpose of this function is to panic if the hash set cannot be allocated"
)]
#[inline]
#[must_use]
pub fn with_hasher(max_len: usize, hasher: S) -> Self {
let set = HashSet::with_capacity_and_hasher(Self::requested_capacity(max_len).expect("HashSet::with_hasher must be passed a maximum length that does not exceed usize::MAX / 2"), hasher);
let len = set.capacity() >> 1u8;
Self(set, len)
}
#[inline]
pub fn retain<F: FnMut(&T) -> bool>(&mut self, f: F) {
self.0.retain(f);
}
}
impl<T: TimedCeremony, S> MaxLenHashSet<T, S> {
#[cfg_attr(docsrs, doc(auto_cfg = false))]
#[cfg(any(doc, not(feature = "serializable_server_state")))]
#[inline]
pub fn remove_expired_ceremonies(&mut self) -> Option<Instant> {
let now = Instant::now();
let mut some = true;
let mut expiry_min = None;
self.retain(|v| {
let expiry = v.expiration();
if expiry >= now {
match expiry_min {
None => expiry_min = Some(expiry),
Some(ref mut e) if expiry < *e => *e = expiry,
_ => (),
}
true
} else {
some = false;
false
}
});
if some { expiry_min } else { None }
}
#[cfg(all(not(doc), feature = "serializable_server_state"))]
#[inline]
pub fn remove_expired_ceremonies(&mut self) -> Option<SystemTime> {
let now = SystemTime::now();
let mut some = true;
let mut expiry_min = None;
self.retain(|v| {
let expiry = v.expiration();
if expiry >= now {
match expiry_min {
None => expiry_min = Some(expiry),
Some(ref mut e) if expiry < *e => *e = expiry,
_ => (),
}
true
} else {
some = false;
false
}
});
if some { expiry_min } else { None }
}
#[cfg_attr(docsrs, doc(auto_cfg = false))]
#[cfg(any(doc, not(feature = "serializable_server_state")))]
#[inline]
pub fn remove_first_expired_ceremony(&mut self) -> Option<Instant> {
let now = Instant::now();
let mut expiry_min = None;
self.0
.extract_if(|v| {
let expiry = v.expiration();
if expiry < now {
true
} else {
match expiry_min {
None => expiry_min = Some(expiry),
Some(ref mut e) if expiry < *e => *e = expiry,
_ => (),
}
false
}
})
.next()
.map_or(expiry_min, |_| None)
}
#[cfg(all(not(doc), feature = "serializable_server_state"))]
#[inline]
pub fn remove_first_expired_ceremony(&mut self) -> Option<SystemTime> {
let now = SystemTime::now();
let mut expiry_min = None;
self.0
.extract_if(|v| {
let expiry = v.expiration();
if expiry < now {
true
} else {
match expiry_min {
None => expiry_min = Some(expiry),
Some(ref mut e) if expiry < *e => *e = expiry,
_ => (),
}
false
}
})
.next()
.map_or(expiry_min, |_| None)
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Insert {
Success,
Duplicate,
CapacityFull,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Replace<T> {
Insert,
Previous(T),
CapacityFull,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum InsertRemoveExpired {
Success,
Duplicate,
#[cfg_attr(docsrs, doc(auto_cfg = false))]
#[cfg(any(doc, not(feature = "serializable_server_state")))]
CapacityFull(Instant),
#[cfg(all(not(doc), feature = "serializable_server_state"))]
CapacityFull(SystemTime),
}
#[derive(Debug)]
pub enum EntryStatus<'a, T, S> {
Success(Entry<'a, T, S>),
CapacityFull,
}
#[derive(Debug)]
pub enum EntryStatusRemoveExpired<'a, T, S> {
Success(Entry<'a, T, S>),
#[cfg_attr(docsrs, doc(auto_cfg = false))]
#[cfg(any(doc, not(feature = "serializable_server_state")))]
CapacityFull(Instant),
#[cfg(all(not(doc), feature = "serializable_server_state"))]
CapacityFull(SystemTime),
}
impl<T: Eq + Hash, S: BuildHasher> MaxLenHashSet<T, S> {
#[inline]
pub fn try_with_hasher(max_len: usize, hasher: S) -> Result<Self, TryReserveError> {
Self::requested_capacity(max_len).and_then(|additional| {
let mut set = HashSet::with_hasher(hasher);
set.try_reserve(additional).map(|()| {
let len = set.capacity() >> 1u8;
Self(set, len)
})
})
}
#[inline]
pub fn get_or_insert(&mut self, value: T) -> Option<&T> {
if self.0.len() == self.1 {
self.0.get(&value)
} else {
Some(self.0.get_or_insert(value))
}
}
#[inline]
pub fn get_or_insert_with<Q: Equivalent<T> + Hash + ?Sized, F: FnOnce(&Q) -> T>(
&mut self,
value: &Q,
f: F,
) -> Option<&T> {
if self.0.len() == self.1 {
self.0.get(value)
} else {
Some(self.0.get_or_insert_with(value, f))
}
}
#[inline]
pub fn remove<Q: Equivalent<T> + Hash + ?Sized>(&mut self, value: &Q) -> bool {
self.0.remove(value)
}
#[inline]
pub fn take<Q: Equivalent<T> + Hash + ?Sized>(&mut self, value: &Q) -> Option<T> {
self.0.take(value)
}
#[inline]
pub fn insert(&mut self, value: T) -> Insert {
let full = self.0.len() == self.1;
if let Entry::Vacant(ent) = self.0.entry(value) {
if full {
Insert::CapacityFull
} else {
_ = ent.insert();
Insert::Success
}
} else {
Insert::Duplicate
}
}
#[expect(clippy::unreachable, reason = "want to crash when there is a bug")]
#[inline]
pub fn replace(&mut self, value: T) -> Replace<T> {
if self.0.contains(&value) {
Replace::Previous(
self.0
.replace(value)
.unwrap_or_else(|| unreachable!("there is a bug in HashSet::replace")),
)
} else if self.0.len() == self.1 {
Replace::CapacityFull
} else {
_ = self.0.insert(value);
Replace::Insert
}
}
#[inline]
pub fn entry(&mut self, value: T) -> EntryStatus<'_, T, S> {
let full = self.0.len() == self.1;
match self.0.entry(value) {
ent @ Entry::Occupied(_) => EntryStatus::Success(ent),
ent @ Entry::Vacant(_) => {
if full {
EntryStatus::CapacityFull
} else {
EntryStatus::Success(ent)
}
}
}
}
}
impl<T: Eq + Hash + TimedCeremony, S: BuildHasher> MaxLenHashSet<T, S> {
#[inline]
pub fn insert_remove_expired(&mut self, value: T) -> InsertRemoveExpired {
if self.0.len() == self.1 {
match self.remove_first_expired_ceremony() {
None => {
if self.0.insert(value) {
InsertRemoveExpired::Success
} else {
InsertRemoveExpired::Duplicate
}
}
Some(exp) => {
if self.0.contains(&value) {
InsertRemoveExpired::Duplicate
} else {
InsertRemoveExpired::CapacityFull(exp)
}
}
}
} else if self.0.insert(value) {
InsertRemoveExpired::Success
} else {
InsertRemoveExpired::Duplicate
}
}
#[inline]
pub fn insert_remove_all_expired(&mut self, value: T) -> InsertRemoveExpired {
if self.0.len() == self.1 {
match self.remove_expired_ceremonies() {
None => {
if self.0.insert(value) {
InsertRemoveExpired::Success
} else {
InsertRemoveExpired::Duplicate
}
}
Some(exp) => {
if self.0.contains(&value) {
InsertRemoveExpired::Duplicate
} else {
InsertRemoveExpired::CapacityFull(exp)
}
}
}
} else if self.0.insert(value) {
InsertRemoveExpired::Success
} else {
InsertRemoveExpired::Duplicate
}
}
#[inline]
pub fn entry_remove_expired(&mut self, value: T) -> EntryStatusRemoveExpired<'_, T, S> {
if self.0.len() == self.1 {
match self.remove_first_expired_ceremony() {
None => EntryStatusRemoveExpired::Success(self.0.entry(value)),
Some(exp) => {
if let ent @ Entry::Occupied(_) = self.0.entry(value) {
EntryStatusRemoveExpired::Success(ent)
} else {
EntryStatusRemoveExpired::CapacityFull(exp)
}
}
}
} else {
EntryStatusRemoveExpired::Success(self.0.entry(value))
}
}
#[inline]
pub fn entry_remove_all_expired(&mut self, value: T) -> EntryStatusRemoveExpired<'_, T, S> {
if self.0.len() == self.1 {
match self.remove_expired_ceremonies() {
None => EntryStatusRemoveExpired::Success(self.0.entry(value)),
Some(exp) => {
if let ent @ Entry::Occupied(_) = self.0.entry(value) {
EntryStatusRemoveExpired::Success(ent)
} else {
EntryStatusRemoveExpired::CapacityFull(exp)
}
}
}
} else {
EntryStatusRemoveExpired::Success(self.0.entry(value))
}
}
}
impl<T, S> AsRef<HashSet<T, S>> for MaxLenHashSet<T, S> {
#[inline]
fn as_ref(&self) -> &HashSet<T, S> {
&self.0
}
}
impl<T, S> From<MaxLenHashSet<T, S>> for HashSet<T, S> {
#[inline]
fn from(value: MaxLenHashSet<T, S>) -> Self {
value.0
}
}