hash_map.rs - webauthn_rp | Philomathic Life

hash_map.rs (15812B)
      1 use super::{super::request::TimedCeremony, BuildIdentityHasher};
      2 #[cfg(doc)]
      3 use core::hash::Hasher;
      4 use core::hash::{BuildHasher, Hash};
      5 use hashbrown::{
      6     Equivalent, TryReserveError,
      7     hash_map::{Drain, Entry, EntryRef, ExtractIf, HashMap, IterMut, OccupiedError, ValuesMut},
      8 };
      9 #[cfg(not(feature = "serializable_server_state"))]
     10 use std::time::Instant;
     11 #[cfg(feature = "serializable_server_state")]
     12 use std::time::SystemTime;
     13 /// [`HashMap`] that has maximum [`HashMap::capacity`] and length and allocates exactly once.
     14 ///
     15 /// Note due to how `HashMap` removes entries, it's possible to insert an entry after removing an entry and cause
     16 /// a new allocation. To avoid this, we ensure that the allocated capacity is at least twice the size of
     17 /// the requested maximum length.
     18 ///
     19 /// This is useful in situations when the underlying entries are expected to be removed, and one wants to ensure the
     20 /// map does not grow unbounded. When `K` is a [`TimedCeremony`], helper methods (e.g.,
     21 /// [`Self::insert_remove_all_expired`]) are provided that will automatically remove expired entries. Note the
     22 /// intended use case is for `K` to be based on a server-side randomly generated value; thus the default [`Hasher`]
     23 /// is [`BuildIdentityHasher`]. In the event this is not true, one MUST use a more appropriate `Hasher`.
     24 ///
     25 /// Only the mutable methods of `HashMap` are re-defined in order to ensure [`Self::max_len`] is never exceeded.
     26 /// For all other methods, first call [`Self::as_ref`] or [`Self::into`].
     27 ///
     28 /// [`Self::into`]: struct.MaxLenHashMap.html#impl-Into<U>-for-T
     29 #[derive(Debug)]
     30 pub struct MaxLenHashMap<K, V, S = BuildIdentityHasher>(HashMap<K, V, S>, usize);
     31 impl<K, V> MaxLenHashMap<K, V, BuildIdentityHasher> {
     32     /// [`HashMap::with_capacity_and_hasher`] using `2 * max_len` and `BuildIdentityHasher`.
     33     ///
     34     /// Note since the actual capacity allocated may exceed the requested capacity, [`Self::max_len`] may exceed
     35     /// `max_len`.
     36     ///
     37     /// # Panics
     38     ///
     39     /// `panic`s if `max_len > usize::MAX / 2`. Note since [`HashMap::with_capacity_and_hasher`] `panic`s
     40     /// for much smaller values than `usize::MAX / 2`—even when `K` and `V` are zero-sized types (ZSTs)—this is not
     41     /// an additional `panic` than what would already occur. The only difference is the message reported.
     42     #[inline]
     43     #[must_use]
     44     pub fn new(max_len: usize) -> Self {
     45         Self::with_hasher(max_len, BuildIdentityHasher)
     46     }
     47 }
     48 impl<K, V, S> MaxLenHashMap<K, V, S> {
     49     /// Capacity we allocate.
     50     ///
     51     /// # Errors
     52     ///
     53     /// Errors iff `max_len > usize::MAX / 2`.
     54     const fn requested_capacity(max_len: usize) -> Result<usize, TryReserveError> {
     55         if max_len <= usize::MAX >> 1u8 {
     56             Ok(max_len << 1u8)
     57         } else {
     58             Err(TryReserveError::CapacityOverflow)
     59         }
     60     }
     61     /// Returns the immutable maximum length allowed by `self`.
     62     #[inline]
     63     pub const fn max_len(&self) -> usize {
     64         self.1
     65     }
     66     /// [`HashMap::values_mut`].
     67     #[inline]
     68     pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
     69         self.0.values_mut()
     70     }
     71     /// [`HashMap::iter_mut`].
     72     #[expect(
     73         clippy::iter_without_into_iter,
     74         reason = "re-export all mutable methods of HashMap"
     75     )]
     76     #[inline]
     77     pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
     78         self.0.iter_mut()
     79     }
     80     /// [`HashMap::clear`].
     81     #[inline]
     82     pub fn clear(&mut self) {
     83         self.0.clear();
     84     }
     85     /// [`HashMap::drain`].
     86     #[inline]
     87     pub fn drain(&mut self) -> Drain<'_, K, V> {
     88         self.0.drain()
     89     }
     90     /// [`HashMap::extract_if`].
     91     #[inline]
     92     pub fn extract_if<F: FnMut(&K, &mut V) -> bool>(&mut self, f: F) -> ExtractIf<'_, K, V, F> {
     93         self.0.extract_if(f)
     94     }
     95     /// [`HashMap::with_capacity_and_hasher`] using `2 * max_len` and `hasher`.
     96     ///
     97     /// Note since the actual capacity allocated may exceed the requested capacity, [`Self::max_len`] may exceed
     98     /// `max_len`.
     99     ///
    100     /// # Panics
    101     ///
    102     /// `panic`s if `max_len > usize::MAX / 2`. Note since [`HashMap::with_capacity_and_hasher`] `panic`s
    103     /// for much smaller values than `usize::MAX / 2`—even when `K` and `V` are zero-sized types (ZSTs)—this is not
    104     /// an additional `panic` than what would already occur. The only difference is the message reported.
    105     #[expect(
    106         clippy::expect_used,
    107         reason = "purpose of this function is to panic if the hash map cannot be allocated"
    108     )]
    109     #[inline]
    110     #[must_use]
    111     pub fn with_hasher(max_len: usize, hasher: S) -> Self {
    112         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);
    113         let len = map.capacity() >> 1u8;
    114         Self(map, len)
    115     }
    116     /// [`HashMap::retain`].
    117     #[inline]
    118     pub fn retain<F: FnMut(&K, &mut V) -> bool>(&mut self, f: F) {
    119         self.0.retain(f);
    120     }
    121 }
    122 impl<K: TimedCeremony, V, S> MaxLenHashMap<K, V, S> {
    123     /// Removes all expired ceremonies.
    124     #[inline]
    125     pub fn remove_expired_ceremonies(&mut self) {
    126         // Even though it's more accurate to check the current `Instant` for each ceremony, we elect to capture
    127         // the `Instant` we begin iteration for performance reasons. It's unlikely an appreciable amount of
    128         // additional ceremonies would be removed.
    129         #[cfg(not(feature = "serializable_server_state"))]
    130         let now = Instant::now();
    131         #[cfg(feature = "serializable_server_state")]
    132         let now = SystemTime::now();
    133         self.retain(|v, _| v.expiration() >= now);
    134     }
    135     /// Removes the first encountered expired ceremony.
    136     #[inline]
    137     pub fn remove_first_expired_ceremony(&mut self) {
    138         #[cfg(not(feature = "serializable_server_state"))]
    139         let now = Instant::now();
    140         #[cfg(feature = "serializable_server_state")]
    141         let now = SystemTime::now();
    142         drop(self.0.extract_if(|k, _| k.expiration() < now).next());
    143     }
    144 }
    145 impl<K: Eq + Hash, V, S: BuildHasher> MaxLenHashMap<K, V, S> {
    146     /// [`HashMap::with_hasher`] using `hasher` followed by [`HashMap::try_reserve`] using `2 * max_len`.
    147     ///
    148     /// Note since the actual capacity allocated may exceed the requested capacity, [`Self::max_len`] may exceed
    149     /// `max_len`.
    150     ///
    151     /// # Errors
    152     ///
    153     /// Errors iff `max_len > usize::MAX / 2` or [`HashMap::try_reserve`] does.
    154     #[inline]
    155     pub fn try_with_hasher(max_len: usize, hasher: S) -> Result<Self, TryReserveError> {
    156         Self::requested_capacity(max_len).and_then(|additional| {
    157             let mut set = HashMap::with_hasher(hasher);
    158             set.try_reserve(additional).map(|()| {
    159                 let len = set.capacity() >> 1u8;
    160                 Self(set, len)
    161             })
    162         })
    163     }
    164     /// [`HashMap::get_mut`].
    165     #[inline]
    166     pub fn get_mut<Q: Equivalent<K> + Hash + ?Sized>(&mut self, k: &Q) -> Option<&mut V> {
    167         self.0.get_mut(k)
    168     }
    169     /// [`HashMap::get_key_value_mut`].
    170     #[inline]
    171     pub fn get_key_value_mut<Q: Equivalent<K> + Hash + ?Sized>(
    172         &mut self,
    173         k: &Q,
    174     ) -> Option<(&K, &mut V)> {
    175         self.0.get_key_value_mut(k)
    176     }
    177     /// [`HashMap::get_disjoint_mut`].
    178     #[inline]
    179     pub fn get_disjoint_mut<Q: Equivalent<K> + Hash + ?Sized, const N: usize>(
    180         &mut self,
    181         ks: [&Q; N],
    182     ) -> [Option<&mut V>; N] {
    183         self.0.get_disjoint_mut(ks)
    184     }
    185     /// [`HashMap::get_disjoint_key_value_mut`].
    186     #[inline]
    187     pub fn get_disjoint_key_value_mut<Q: Equivalent<K> + Hash + ?Sized, const N: usize>(
    188         &mut self,
    189         ks: [&Q; N],
    190     ) -> [Option<(&K, &mut V)>; N] {
    191         self.0.get_disjoint_key_value_mut(ks)
    192     }
    193     /// [`HashMap::remove`].
    194     #[inline]
    195     pub fn remove<Q: Equivalent<K> + Hash + ?Sized>(&mut self, k: &Q) -> Option<V> {
    196         self.0.remove(k)
    197     }
    198     /// [`HashMap::remove_entry`].
    199     #[inline]
    200     pub fn remove_entry<Q: Equivalent<K> + Hash + ?Sized>(&mut self, k: &Q) -> Option<(K, V)> {
    201         self.0.remove_entry(k)
    202     }
    203     /// [`HashMap::try_insert`].
    204     ///
    205     /// `Ok(None)` is returned iff [`HashMap::len`] `==` [`Self::max_len`] and `key` does not already exist in
    206     /// the map.
    207     ///
    208     /// # Errors
    209     ///
    210     /// Errors iff [`HashMap::insert`] does.
    211     #[inline]
    212     pub fn try_insert(
    213         &mut self,
    214         key: K,
    215         value: V,
    216     ) -> Result<Option<&mut V>, OccupiedError<'_, K, V, S>> {
    217         let full = self.0.len() == self.1;
    218         match self.0.entry(key) {
    219             Entry::Occupied(entry) => Err(OccupiedError { entry, value }),
    220             Entry::Vacant(ent) => {
    221                 if full {
    222                     Ok(None)
    223                 } else {
    224                     Ok(Some(ent.insert(value)))
    225                 }
    226             }
    227         }
    228     }
    229     /// [`HashMap::insert`].
    230     ///
    231     /// `None` is returned iff [`HashMap::len`] `==` [`Self::max_len`] and `key` does not already exist in the
    232     /// map.
    233     #[inline]
    234     pub fn insert(&mut self, k: K, v: V) -> Option<Option<V>> {
    235         let full = self.0.len() == self.1;
    236         match self.0.entry(k) {
    237             Entry::Occupied(mut ent) => Some(Some(ent.insert(v))),
    238             Entry::Vacant(ent) => {
    239                 if full {
    240                     None
    241                 } else {
    242                     _ = ent.insert(v);
    243                     Some(None)
    244                 }
    245             }
    246         }
    247     }
    248     /// [`HashMap::entry`].
    249     ///
    250     /// `None` is returned iff [`HashMap::len`] `==` [`Self::max_len`] and `key` does not already exist in the
    251     /// map.
    252     #[inline]
    253     pub fn entry(&mut self, key: K) -> Option<Entry<'_, K, V, S>> {
    254         let full = self.0.len() == self.1;
    255         match self.0.entry(key) {
    256             ent @ Entry::Occupied(_) => Some(ent),
    257             ent @ Entry::Vacant(_) => {
    258                 if full {
    259                     None
    260                 } else {
    261                     Some(ent)
    262                 }
    263             }
    264         }
    265     }
    266     /// [`HashMap::entry_ref`].
    267     ///
    268     /// `None` is returned iff [`HashMap::len`] `==` [`Self::max_len`] and `key` does not already exist in the
    269     /// map.
    270     #[inline]
    271     pub fn entry_ref<'a, 'b, Q: Equivalent<K> + Hash + ?Sized>(
    272         &'a mut self,
    273         key: &'b Q,
    274     ) -> Option<EntryRef<'a, 'b, K, Q, V, S>> {
    275         let full = self.0.len() == self.1;
    276         match self.0.entry_ref(key) {
    277             ent @ EntryRef::Occupied(_) => Some(ent),
    278             ent @ EntryRef::Vacant(_) => {
    279                 if full {
    280                     None
    281                 } else {
    282                     Some(ent)
    283                 }
    284             }
    285         }
    286     }
    287 }
    288 impl<K: Eq + Hash + TimedCeremony, V, S: BuildHasher> MaxLenHashMap<K, V, S> {
    289     /// [`Self::insert`] except the first encountered expired ceremony is removed in the event [`Self::max_len`]
    290     /// entries have been added.
    291     #[inline]
    292     pub fn insert_remove_expired(&mut self, k: K, v: V) -> Option<Option<V>> {
    293         if self.0.len() == self.1 {
    294             #[cfg(not(feature = "serializable_server_state"))]
    295             let now = Instant::now();
    296             #[cfg(feature = "serializable_server_state")]
    297             let now = SystemTime::now();
    298             if self
    299                 .0
    300                 .extract_if(|exp, _| exp.expiration() < now)
    301                 .next()
    302                 .is_some()
    303             {
    304                 Some(self.0.insert(k, v))
    305             } else if let Entry::Occupied(mut ent) = self.0.entry(k) {
    306                 Some(Some(ent.insert(v)))
    307             } else {
    308                 None
    309             }
    310         } else {
    311             Some(self.0.insert(k, v))
    312         }
    313     }
    314     /// [`Self::insert`] except all expired ceremonies are removed in the event [`Self::max_len`] entries have
    315     /// been added.
    316     #[inline]
    317     pub fn insert_remove_all_expired(&mut self, k: K, v: V) -> Option<Option<V>> {
    318         if self.0.len() == self.1 {
    319             self.remove_expired_ceremonies();
    320         }
    321         if self.0.len() == self.1 {
    322             if let Entry::Occupied(mut ent) = self.0.entry(k) {
    323                 Some(Some(ent.insert(v)))
    324             } else {
    325                 None
    326             }
    327         } else {
    328             Some(self.0.insert(k, v))
    329         }
    330     }
    331     /// [`Self::entry`] except the first encountered expired ceremony is removed in the event [`Self::max_len`]
    332     /// entries have been added.
    333     #[inline]
    334     pub fn entry_remove_expired(&mut self, key: K) -> Option<Entry<'_, K, V, S>> {
    335         if self.0.len() == self.1 {
    336             #[cfg(not(feature = "serializable_server_state"))]
    337             let now = Instant::now();
    338             #[cfg(feature = "serializable_server_state")]
    339             let now = SystemTime::now();
    340             if self
    341                 .0
    342                 .extract_if(|v, _| v.expiration() < now)
    343                 .next()
    344                 .is_some()
    345             {
    346                 Some(self.0.entry(key))
    347             } else if let ent @ Entry::Occupied(_) = self.0.entry(key) {
    348                 Some(ent)
    349             } else {
    350                 None
    351             }
    352         } else {
    353             Some(self.0.entry(key))
    354         }
    355     }
    356     /// [`Self::entry`] except all expired ceremonies are removed in the event [`Self::max_len`] entries have
    357     /// been added.
    358     #[inline]
    359     pub fn entry_remove_all_expired(&mut self, key: K) -> Option<Entry<'_, K, V, S>> {
    360         if self.0.len() == self.1 {
    361             self.remove_expired_ceremonies();
    362         }
    363         if self.0.len() == self.1 {
    364             if let ent @ Entry::Occupied(_) = self.0.entry(key) {
    365                 Some(ent)
    366             } else {
    367                 None
    368             }
    369         } else {
    370             Some(self.0.entry(key))
    371         }
    372     }
    373     /// [`Self::entry_ref`] except the first encoutered expired ceremony is removed in the event [`Self::max_len`]
    374     /// entries have been added.
    375     #[inline]
    376     pub fn entry_ref_remove_expired<'a, 'b, Q: Equivalent<K> + Hash + ?Sized>(
    377         &'a mut self,
    378         key: &'b Q,
    379     ) -> Option<EntryRef<'a, 'b, K, Q, V, S>> {
    380         if self.0.len() == self.1 {
    381             #[cfg(not(feature = "serializable_server_state"))]
    382             let now = Instant::now();
    383             #[cfg(feature = "serializable_server_state")]
    384             let now = SystemTime::now();
    385             if self
    386                 .0
    387                 .extract_if(|v, _| v.expiration() < now)
    388                 .next()
    389                 .is_some()
    390             {
    391                 Some(self.0.entry_ref(key))
    392             } else if let ent @ EntryRef::Occupied(_) = self.0.entry_ref(key) {
    393                 Some(ent)
    394             } else {
    395                 None
    396             }
    397         } else {
    398             Some(self.0.entry_ref(key))
    399         }
    400     }
    401     /// [`Self::entry_ref`] except all expired ceremonies are removed in the event [`Self::max_len`] entries have
    402     /// been added.
    403     #[inline]
    404     pub fn entry_ref_remove_all_expired<'a, 'b, Q: Equivalent<K> + Hash + ?Sized>(
    405         &'a mut self,
    406         key: &'b Q,
    407     ) -> Option<EntryRef<'a, 'b, K, Q, V, S>> {
    408         if self.0.len() == self.1 {
    409             self.remove_expired_ceremonies();
    410         }
    411         if self.0.len() == self.1 {
    412             if let ent @ EntryRef::Occupied(_) = self.0.entry_ref(key) {
    413                 Some(ent)
    414             } else {
    415                 None
    416             }
    417         } else {
    418             Some(self.0.entry_ref(key))
    419         }
    420     }
    421 }
    422 impl<K, V, S> AsRef<HashMap<K, V, S>> for MaxLenHashMap<K, V, S> {
    423     #[inline]
    424     fn as_ref(&self) -> &HashMap<K, V, S> {
    425         &self.0
    426     }
    427 }
    428 impl<K, V, S> From<MaxLenHashMap<K, V, S>> for HashMap<K, V, S> {
    429     #[inline]
    430     fn from(value: MaxLenHashMap<K, V, S>) -> Self {
    431         value.0
    432     }
    433 }
	webauthn_rp WebAuthn Level 3 RP library.
	git clone https://git.philomathiclife.com/repos/webauthn_rp
	Log \| Files \| Refs \| README