#[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_map::{Drain, Entry, EntryRef, ExtractIf, HashMap, IterMut, OccupiedError, ValuesMut},
};
#[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 MaxLenHashMap<K, V, S = BuildIdentityHasher>(HashMap<K, V, S>, usize);
impl<K, V> MaxLenHashMap<K, V, BuildIdentityHasher> {
#[inline]
#[must_use]
pub fn new(max_len: usize) -> Self {
Self::with_hasher(max_len, BuildIdentityHasher)
}
}
impl<K, V, S> MaxLenHashMap<K, V, 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 values_mut(&mut self) -> ValuesMut<'_, K, V> {
self.0.values_mut()
}
#[expect(
clippy::iter_without_into_iter,
reason = "re-export all mutable methods of HashMap"
)]
#[inline]
pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
self.0.iter_mut()
}
#[inline]
pub fn clear(&mut self) {
self.0.clear();
}
#[inline]
pub fn drain(&mut self) -> Drain<'_, K, V> {
self.0.drain()
}
#[inline]
pub fn extract_if<F: FnMut(&K, &mut V) -> bool>(&mut self, f: F) -> ExtractIf<'_, K, V, F> {
self.0.extract_if(f)
}
#[expect(
clippy::expect_used,
reason = "purpose of this function is to panic if the hash map cannot be allocated"
)]
#[inline]
#[must_use]
pub fn with_hasher(max_len: usize, hasher: S) -> Self {
let map = HashMap::with_capacity_and_hasher(Self::requested_capacity(max_len).expect("HashMap::with_hasher must be passed a maximum length that does not exceed usize::MAX / 2"), hasher);
let len = map.capacity() >> 1u8;
Self(map, len)
}
#[inline]
pub fn retain<F: FnMut(&K, &mut V) -> bool>(&mut self, f: F) {
self.0.retain(f);
}
}
impl<K: TimedCeremony, V, S> MaxLenHashMap<K, V, 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(|k, _| {
let expiry = k.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(|k, _| {
let expiry = k.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(|k, _| {
let expiry = k.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(|k, _| {
let expiry = k.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<V> {
Success,
Previous(V),
CapacityFull,
}
#[derive(Debug)]
pub enum FullCapOccupiedErr<'a, K, V, S> {
Occupied(OccupiedError<'a, K, V, S>),
CapacityFull,
}
#[derive(Debug)]
pub enum FullCapRemoveExpiredOccupiedErr<'a, K, V, S> {
Occupied(OccupiedError<'a, K, V, 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),
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum InsertRemoveExpired<V> {
Success,
Previous(V),
#[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(Clone, Copy, Debug, Eq, PartialEq)]
pub enum EntryStatus<E> {
Success(E),
CapacityFull,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum EntryStatusRemoveExpired<E> {
Success(E),
#[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<K: Eq + Hash, V, S: BuildHasher> MaxLenHashMap<K, V, 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 = HashMap::with_hasher(hasher);
set.try_reserve(additional).map(|()| {
let len = set.capacity() >> 1u8;
Self(set, len)
})
})
}
#[inline]
pub fn get_mut<Q: Equivalent<K> + Hash + ?Sized>(&mut self, k: &Q) -> Option<&mut V> {
self.0.get_mut(k)
}
#[inline]
pub fn get_key_value_mut<Q: Equivalent<K> + Hash + ?Sized>(
&mut self,
k: &Q,
) -> Option<(&K, &mut V)> {
self.0.get_key_value_mut(k)
}
#[inline]
pub fn get_disjoint_mut<Q: Equivalent<K> + Hash + ?Sized, const N: usize>(
&mut self,
ks: [&Q; N],
) -> [Option<&mut V>; N] {
self.0.get_disjoint_mut(ks)
}
#[inline]
pub fn get_disjoint_key_value_mut<Q: Equivalent<K> + Hash + ?Sized, const N: usize>(
&mut self,
ks: [&Q; N],
) -> [Option<(&K, &mut V)>; N] {
self.0.get_disjoint_key_value_mut(ks)
}
#[inline]
pub fn remove<Q: Equivalent<K> + Hash + ?Sized>(&mut self, k: &Q) -> Option<V> {
self.0.remove(k)
}
#[inline]
pub fn remove_entry<Q: Equivalent<K> + Hash + ?Sized>(&mut self, k: &Q) -> Option<(K, V)> {
self.0.remove_entry(k)
}
#[inline]
pub fn try_insert(
&mut self,
key: K,
value: V,
) -> Result<&mut V, FullCapOccupiedErr<'_, K, V, S>> {
let full = self.0.len() == self.1;
match self.0.entry(key) {
Entry::Occupied(entry) => {
Err(FullCapOccupiedErr::Occupied(OccupiedError { entry, value }))
}
Entry::Vacant(ent) => {
if full {
Err(FullCapOccupiedErr::CapacityFull)
} else {
Ok(ent.insert(value))
}
}
}
}
#[inline]
pub fn insert(&mut self, k: K, v: V) -> Insert<V> {
let full = self.0.len() == self.1;
match self.0.entry(k) {
Entry::Occupied(mut ent) => Insert::Previous(ent.insert(v)),
Entry::Vacant(ent) => {
if full {
Insert::CapacityFull
} else {
_ = ent.insert(v);
Insert::Success
}
}
}
}
#[inline]
pub fn entry(&mut self, key: K) -> EntryStatus<Entry<'_, K, V, S>> {
let full = self.0.len() == self.1;
match self.0.entry(key) {
ent @ Entry::Occupied(_) => EntryStatus::Success(ent),
ent @ Entry::Vacant(_) => {
if full {
EntryStatus::CapacityFull
} else {
EntryStatus::Success(ent)
}
}
}
}
#[inline]
pub fn entry_ref<'a, 'b, Q: Equivalent<K> + Hash + ?Sized>(
&'a mut self,
key: &'b Q,
) -> EntryStatus<EntryRef<'a, 'b, K, Q, V, S>> {
let full = self.0.len() == self.1;
match self.0.entry_ref(key) {
ent @ EntryRef::Occupied(_) => EntryStatus::Success(ent),
ent @ EntryRef::Vacant(_) => {
if full {
EntryStatus::CapacityFull
} else {
EntryStatus::Success(ent)
}
}
}
}
}
impl<K: Eq + Hash + TimedCeremony, V, S: BuildHasher> MaxLenHashMap<K, V, S> {
#[inline]
pub fn try_insert_remove_expired(
&mut self,
key: K,
value: V,
) -> Result<&mut V, FullCapRemoveExpiredOccupiedErr<'_, K, V, S>> {
if self.0.len() == self.1 {
match self.remove_first_expired_ceremony() {
None => self
.0
.try_insert(key, value)
.map_err(FullCapRemoveExpiredOccupiedErr::Occupied),
Some(exp) => {
if let Entry::Occupied(entry) = self.0.entry(key) {
Err(FullCapRemoveExpiredOccupiedErr::Occupied(OccupiedError {
entry,
value,
}))
} else {
Err(FullCapRemoveExpiredOccupiedErr::CapacityFull(exp))
}
}
}
} else {
self.0
.try_insert(key, value)
.map_err(FullCapRemoveExpiredOccupiedErr::Occupied)
}
}
#[inline]
pub fn try_insert_remove_all_expired(
&mut self,
key: K,
value: V,
) -> Result<&mut V, FullCapRemoveExpiredOccupiedErr<'_, K, V, S>> {
if self.0.len() == self.1 {
match self.remove_expired_ceremonies() {
None => self
.0
.try_insert(key, value)
.map_err(FullCapRemoveExpiredOccupiedErr::Occupied),
Some(exp) => {
if let Entry::Occupied(entry) = self.0.entry(key) {
Err(FullCapRemoveExpiredOccupiedErr::Occupied(OccupiedError {
entry,
value,
}))
} else {
Err(FullCapRemoveExpiredOccupiedErr::CapacityFull(exp))
}
}
}
} else {
self.0
.try_insert(key, value)
.map_err(FullCapRemoveExpiredOccupiedErr::Occupied)
}
}
#[inline]
pub fn insert_remove_expired(&mut self, k: K, v: V) -> InsertRemoveExpired<V> {
if self.0.len() == self.1 {
match self.remove_first_expired_ceremony() {
None => self.0.insert(k, v).map_or_else(
|| InsertRemoveExpired::Success,
InsertRemoveExpired::Previous,
),
Some(exp) => {
if let Entry::Occupied(mut ent) = self.0.entry(k) {
InsertRemoveExpired::Previous(ent.insert(v))
} else {
InsertRemoveExpired::CapacityFull(exp)
}
}
}
} else {
self.0.insert(k, v).map_or_else(
|| InsertRemoveExpired::Success,
InsertRemoveExpired::Previous,
)
}
}
#[inline]
pub fn insert_remove_all_expired(&mut self, k: K, v: V) -> InsertRemoveExpired<V> {
if self.0.len() == self.1 {
match self.remove_expired_ceremonies() {
None => self.0.insert(k, v).map_or_else(
|| InsertRemoveExpired::Success,
InsertRemoveExpired::Previous,
),
Some(exp) => {
if let Entry::Occupied(mut ent) = self.0.entry(k) {
InsertRemoveExpired::Previous(ent.insert(v))
} else {
InsertRemoveExpired::CapacityFull(exp)
}
}
}
} else {
self.0.insert(k, v).map_or_else(
|| InsertRemoveExpired::Success,
InsertRemoveExpired::Previous,
)
}
}
#[inline]
pub fn entry_remove_expired(&mut self, key: K) -> EntryStatusRemoveExpired<Entry<'_, K, V, S>> {
if self.0.len() == self.1 {
match self.remove_first_expired_ceremony() {
None => EntryStatusRemoveExpired::Success(self.0.entry(key)),
Some(exp) => {
if let ent @ Entry::Occupied(_) = self.0.entry(key) {
EntryStatusRemoveExpired::Success(ent)
} else {
EntryStatusRemoveExpired::CapacityFull(exp)
}
}
}
} else {
EntryStatusRemoveExpired::Success(self.0.entry(key))
}
}
#[inline]
pub fn entry_remove_all_expired(
&mut self,
key: K,
) -> EntryStatusRemoveExpired<Entry<'_, K, V, S>> {
if self.0.len() == self.1 {
match self.remove_expired_ceremonies() {
None => EntryStatusRemoveExpired::Success(self.0.entry(key)),
Some(exp) => {
if let ent @ Entry::Occupied(_) = self.0.entry(key) {
EntryStatusRemoveExpired::Success(ent)
} else {
EntryStatusRemoveExpired::CapacityFull(exp)
}
}
}
} else {
EntryStatusRemoveExpired::Success(self.0.entry(key))
}
}
#[inline]
pub fn entry_ref_remove_expired<'a, 'b, Q: Equivalent<K> + Hash + ?Sized>(
&'a mut self,
key: &'b Q,
) -> EntryStatusRemoveExpired<EntryRef<'a, 'b, K, Q, V, S>> {
if self.0.len() == self.1 {
match self.remove_first_expired_ceremony() {
None => EntryStatusRemoveExpired::Success(self.0.entry_ref(key)),
Some(exp) => {
if let ent @ EntryRef::Occupied(_) = self.0.entry_ref(key) {
EntryStatusRemoveExpired::Success(ent)
} else {
EntryStatusRemoveExpired::CapacityFull(exp)
}
}
}
} else {
EntryStatusRemoveExpired::Success(self.0.entry_ref(key))
}
}
#[inline]
pub fn entry_ref_remove_all_expired<'a, 'b, Q: Equivalent<K> + Hash + ?Sized>(
&'a mut self,
key: &'b Q,
) -> EntryStatusRemoveExpired<EntryRef<'a, 'b, K, Q, V, S>> {
if self.0.len() == self.1 {
match self.remove_expired_ceremonies() {
None => EntryStatusRemoveExpired::Success(self.0.entry_ref(key)),
Some(exp) => {
if let ent @ EntryRef::Occupied(_) = self.0.entry_ref(key) {
EntryStatusRemoveExpired::Success(ent)
} else {
EntryStatusRemoveExpired::CapacityFull(exp)
}
}
}
} else {
EntryStatusRemoveExpired::Success(self.0.entry_ref(key))
}
}
}
impl<K, V, S> AsRef<HashMap<K, V, S>> for MaxLenHashMap<K, V, S> {
#[inline]
fn as_ref(&self) -> &HashMap<K, V, S> {
&self.0
}
}
impl<K, V, S> From<MaxLenHashMap<K, V, S>> for HashMap<K, V, S> {
#[inline]
fn from(value: MaxLenHashMap<K, V, S>) -> Self {
value.0
}
}