hash_map.rs (30557B)
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(any(doc, 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 /// 125 /// `None` is returned iff at least one expired ceremony was removed; otherwise returns the earliest 126 /// expiration. 127 /// 128 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is returned instead. 129 #[cfg_attr(docsrs, doc(auto_cfg = false))] 130 #[cfg(any(doc, not(feature = "serializable_server_state")))] 131 #[inline] 132 pub fn remove_expired_ceremonies(&mut self) -> Option<Instant> { 133 // Even though it's more accurate to check the current `Instant` for each ceremony, we elect to capture 134 // the `Instant` we begin iteration for performance reasons. It's unlikely an appreciable amount of 135 // additional ceremonies would be removed. 136 let now = Instant::now(); 137 let mut some = true; 138 let mut expiry_min = None; 139 self.retain(|k, _| { 140 let expiry = k.expiration(); 141 if expiry >= now { 142 match expiry_min { 143 None => expiry_min = Some(expiry), 144 Some(ref mut e) if expiry < *e => *e = expiry, 145 _ => {} 146 } 147 true 148 } else { 149 some = false; 150 false 151 } 152 }); 153 if some { expiry_min } else { None } 154 } 155 /// Removes all expired ceremonies. 156 /// 157 /// `None` is returned iff at least one expired ceremony was removed; otherwise returns the earliest 158 /// expiration. 159 /// 160 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is returned instead. 161 #[cfg(all(not(doc), feature = "serializable_server_state"))] 162 #[inline] 163 pub fn remove_expired_ceremonies(&mut self) -> Option<SystemTime> { 164 // Even though it's more accurate to check the current `SystemTime` for each ceremony, we elect to capture 165 // the `SystemTime` we begin iteration for performance reasons. It's unlikely an appreciable amount of 166 // additional ceremonies would be removed. 167 let now = SystemTime::now(); 168 let mut some = true; 169 let mut expiry_min = None; 170 self.retain(|k, _| { 171 let expiry = k.expiration(); 172 if expiry >= now { 173 match expiry_min { 174 None => expiry_min = Some(expiry), 175 Some(ref mut e) if expiry < *e => *e = expiry, 176 _ => {} 177 } 178 true 179 } else { 180 some = false; 181 false 182 } 183 }); 184 if some { expiry_min } else { None } 185 } 186 /// Removes the first encountered expired ceremony. 187 /// 188 /// `None` is returned iff an expired ceremony was removed; otherwise returns the earliest 189 /// expiration. 190 /// 191 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is returned instead. 192 #[cfg_attr(docsrs, doc(auto_cfg = false))] 193 #[cfg(any(doc, not(feature = "serializable_server_state")))] 194 #[inline] 195 pub fn remove_first_expired_ceremony(&mut self) -> Option<Instant> { 196 // Even though it's more accurate to check the current `Instant` for each ceremony, we elect to capture 197 // the `Instant` we begin iteration for performance reasons. It's unlikely an appreciable amount of 198 // additional ceremonies would be removed. 199 let now = Instant::now(); 200 let mut expiry_min = None; 201 self.0 202 .extract_if(|k, _| { 203 let expiry = k.expiration(); 204 if expiry < now { 205 true 206 } else { 207 match expiry_min { 208 None => expiry_min = Some(expiry), 209 Some(ref mut e) if expiry < *e => *e = expiry, 210 _ => {} 211 } 212 false 213 } 214 }) 215 .next() 216 .map_or(expiry_min, |_| None) 217 } 218 /// Removes the first encountered expired ceremony. 219 /// 220 /// `None` is returned iff an expired ceremony was removed; otherwise returns the earliest 221 /// expiration. 222 /// 223 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is returned instead. 224 #[cfg(all(not(doc), feature = "serializable_server_state"))] 225 #[inline] 226 pub fn remove_first_expired_ceremony(&mut self) -> Option<SystemTime> { 227 // Even though it's more accurate to check the current `SystemTime` for each ceremony, we elect to capture 228 // the `SystemTime` we begin iteration for performance reasons. It's unlikely an appreciable amount of 229 // additional ceremonies would be removed. 230 let now = SystemTime::now(); 231 let mut expiry_min = None; 232 self.0 233 .extract_if(|k, _| { 234 let expiry = k.expiration(); 235 if expiry < now { 236 true 237 } else { 238 match expiry_min { 239 None => expiry_min = Some(expiry), 240 Some(ref mut e) if expiry < *e => *e = expiry, 241 _ => {} 242 } 243 false 244 } 245 }) 246 .next() 247 .map_or(expiry_min, |_| None) 248 } 249 } 250 /// Signifies the consequences of [`MaxLenHashMap::insert`]. 251 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 252 pub enum Insert<V> { 253 /// The entry was successfully inserted. 254 Success, 255 /// The value replaced the contained value. 256 Previous(V), 257 /// The key does not exist, but there was no available capacity to insert the entry. 258 CapacityFull, 259 } 260 /// Error returned from [`MaxLenHashMap::try_insert`]. 261 #[derive(Debug)] 262 pub enum FullCapOccupiedErr<'a, K, V, S> { 263 /// Error when the key already exists. 264 Occupied(OccupiedError<'a, K, V, S>), 265 /// Error when there is no available capacity and the key does not exist. 266 CapacityFull, 267 } 268 /// Error returned from [`MaxLenHashMap::try_insert_remove_expired`] and 269 /// [`MaxLenHashMap::try_insert_remove_all_expired`]. 270 #[derive(Debug)] 271 pub enum FullCapRemoveExpiredOccupiedErr<'a, K, V, S> { 272 /// Error when the key already exists. 273 Occupied(OccupiedError<'a, K, V, S>), 274 /// Error when there was is no available capacity to insert the entry and no expired 275 /// [`TimedCeremony`]s could be removed. 276 /// 277 /// The contained `Instant` is the earliest expiration. 278 /// 279 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is contained instead. 280 #[cfg_attr(docsrs, doc(auto_cfg = false))] 281 #[cfg(any(doc, not(feature = "serializable_server_state")))] 282 CapacityFull(Instant), 283 /// Error when there was is no available capacity to insert the entry and no expired 284 /// [`TimedCeremony`]s could be removed. 285 /// 286 /// The contained `Instant` is the earliest expiration. 287 /// 288 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is contained instead. 289 #[cfg(all(not(doc), feature = "serializable_server_state"))] 290 CapacityFull(SystemTime), 291 } 292 /// Signifies the consequences of [`MaxLenHashMap::insert_remove_expired`] and 293 /// [`MaxLenHashMap::insert_remove_all_expired`]. 294 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 295 pub enum InsertRemoveExpired<V> { 296 /// The entry was successfully inserted. 297 Success, 298 /// The value replaced the contained value. 299 Previous(V), 300 /// The key does not exist, but there was no available capacity to insert the entry and no expired 301 /// [`TimedCeremony`]s could be removed. 302 /// 303 /// The contained `Instant` is the earliest expiration. 304 /// 305 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is contained instead. 306 #[cfg_attr(docsrs, doc(auto_cfg = false))] 307 #[cfg(any(doc, not(feature = "serializable_server_state")))] 308 CapacityFull(Instant), 309 /// The value does not exist, but there was no available capacity to insert it and no expired 310 /// [`TimedCeremony`]s that could be removed. 311 /// 312 /// The contained `Instant` is the earliest expiration. 313 /// 314 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is contained instead. 315 #[cfg(all(not(doc), feature = "serializable_server_state"))] 316 CapacityFull(SystemTime), 317 } 318 /// Signifies the consequences of [`MaxLenHashMap::entry`] and [`MaxLenHashMap::entry_ref`]. 319 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 320 pub enum EntryStatus<E> { 321 /// The entry was successfully grabbed. 322 Success(E), 323 /// The capacity was full, and there was no value where the entry would be. 324 CapacityFull, 325 } 326 /// Signifies the consequences of [`MaxLenHashMap::entry_remove_expired`] and 327 /// [`MaxLenHashMap::entry_remove_all_expired`]. 328 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 329 pub enum EntryStatusRemoveExpired<E> { 330 /// The entry was successfully grabbed. 331 Success(E), 332 /// The capacity was full, and there was no value where the entry would be. 333 /// 334 /// The contained `Instant` is the earliest expiration. 335 /// 336 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is contained instead. 337 #[cfg_attr(docsrs, doc(auto_cfg = false))] 338 #[cfg(any(doc, not(feature = "serializable_server_state")))] 339 CapacityFull(Instant), 340 /// The capacity was full, and there was no value where the entry would be. 341 /// 342 /// The contained `Instant` is the earliest expiration. 343 /// 344 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is contained instead. 345 #[cfg(all(not(doc), feature = "serializable_server_state"))] 346 CapacityFull(SystemTime), 347 } 348 impl<K: Eq + Hash, V, S: BuildHasher> MaxLenHashMap<K, V, S> { 349 /// [`HashMap::with_hasher`] using `hasher` followed by [`HashMap::try_reserve`] using `2 * max_len`. 350 /// 351 /// Note since the actual capacity allocated may exceed the requested capacity, [`Self::max_len`] may exceed 352 /// `max_len`. 353 /// 354 /// # Errors 355 /// 356 /// Errors iff `max_len > usize::MAX / 2` or [`HashMap::try_reserve`] does. 357 #[inline] 358 pub fn try_with_hasher(max_len: usize, hasher: S) -> Result<Self, TryReserveError> { 359 Self::requested_capacity(max_len).and_then(|additional| { 360 let mut set = HashMap::with_hasher(hasher); 361 set.try_reserve(additional).map(|()| { 362 let len = set.capacity() >> 1u8; 363 Self(set, len) 364 }) 365 }) 366 } 367 /// [`HashMap::get_mut`]. 368 #[inline] 369 pub fn get_mut<Q: Equivalent<K> + Hash + ?Sized>(&mut self, k: &Q) -> Option<&mut V> { 370 self.0.get_mut(k) 371 } 372 /// [`HashMap::get_key_value_mut`]. 373 #[inline] 374 pub fn get_key_value_mut<Q: Equivalent<K> + Hash + ?Sized>( 375 &mut self, 376 k: &Q, 377 ) -> Option<(&K, &mut V)> { 378 self.0.get_key_value_mut(k) 379 } 380 /// [`HashMap::get_disjoint_mut`]. 381 #[inline] 382 pub fn get_disjoint_mut<Q: Equivalent<K> + Hash + ?Sized, const N: usize>( 383 &mut self, 384 ks: [&Q; N], 385 ) -> [Option<&mut V>; N] { 386 self.0.get_disjoint_mut(ks) 387 } 388 /// [`HashMap::get_disjoint_key_value_mut`]. 389 #[inline] 390 pub fn get_disjoint_key_value_mut<Q: Equivalent<K> + Hash + ?Sized, const N: usize>( 391 &mut self, 392 ks: [&Q; N], 393 ) -> [Option<(&K, &mut V)>; N] { 394 self.0.get_disjoint_key_value_mut(ks) 395 } 396 /// [`HashMap::remove`]. 397 #[inline] 398 pub fn remove<Q: Equivalent<K> + Hash + ?Sized>(&mut self, k: &Q) -> Option<V> { 399 self.0.remove(k) 400 } 401 /// [`HashMap::remove_entry`]. 402 #[inline] 403 pub fn remove_entry<Q: Equivalent<K> + Hash + ?Sized>(&mut self, k: &Q) -> Option<(K, V)> { 404 self.0.remove_entry(k) 405 } 406 /// [`HashMap::try_insert`]. 407 /// 408 /// # Errors 409 /// 410 /// Errors iff [`HashMap::try_insert`] does or there is no available capacity to insert the entry. 411 #[inline] 412 pub fn try_insert( 413 &mut self, 414 key: K, 415 value: V, 416 ) -> Result<&mut V, FullCapOccupiedErr<'_, K, V, S>> { 417 let full = self.0.len() == self.1; 418 match self.0.entry(key) { 419 Entry::Occupied(entry) => { 420 Err(FullCapOccupiedErr::Occupied(OccupiedError { entry, value })) 421 } 422 Entry::Vacant(ent) => { 423 if full { 424 Err(FullCapOccupiedErr::CapacityFull) 425 } else { 426 Ok(ent.insert(value)) 427 } 428 } 429 } 430 } 431 /// [`HashMap::insert`]. 432 #[inline] 433 pub fn insert(&mut self, k: K, v: V) -> Insert<V> { 434 let full = self.0.len() == self.1; 435 match self.0.entry(k) { 436 Entry::Occupied(mut ent) => Insert::Previous(ent.insert(v)), 437 Entry::Vacant(ent) => { 438 if full { 439 Insert::CapacityFull 440 } else { 441 _ = ent.insert(v); 442 Insert::Success 443 } 444 } 445 } 446 } 447 /// [`HashMap::entry`]. 448 #[inline] 449 pub fn entry(&mut self, key: K) -> EntryStatus<Entry<'_, K, V, S>> { 450 let full = self.0.len() == self.1; 451 match self.0.entry(key) { 452 ent @ Entry::Occupied(_) => EntryStatus::Success(ent), 453 ent @ Entry::Vacant(_) => { 454 if full { 455 EntryStatus::CapacityFull 456 } else { 457 EntryStatus::Success(ent) 458 } 459 } 460 } 461 } 462 /// [`HashMap::entry_ref`]. 463 #[inline] 464 pub fn entry_ref<'a, 'b, Q: Equivalent<K> + Hash + ?Sized>( 465 &'a mut self, 466 key: &'b Q, 467 ) -> EntryStatus<EntryRef<'a, 'b, K, Q, V, S>> { 468 let full = self.0.len() == self.1; 469 match self.0.entry_ref(key) { 470 ent @ EntryRef::Occupied(_) => EntryStatus::Success(ent), 471 ent @ EntryRef::Vacant(_) => { 472 if full { 473 EntryStatus::CapacityFull 474 } else { 475 EntryStatus::Success(ent) 476 } 477 } 478 } 479 } 480 } 481 impl<K: Eq + Hash + TimedCeremony, V, S: BuildHasher> MaxLenHashMap<K, V, S> { 482 /// [`Self::try_insert`] except the first encountered expired ceremony is removed in the event [`Self::max_len`] 483 /// entries have been added. 484 /// 485 /// # Errors 486 /// 487 /// Errors iff [`HashMap::try_insert`] does after removing the first expired ceremony. 488 #[inline] 489 pub fn try_insert_remove_expired( 490 &mut self, 491 key: K, 492 value: V, 493 ) -> Result<&mut V, FullCapRemoveExpiredOccupiedErr<'_, K, V, S>> { 494 if self.0.len() == self.1 { 495 match self.remove_first_expired_ceremony() { 496 None => self 497 .0 498 .try_insert(key, value) 499 .map_err(FullCapRemoveExpiredOccupiedErr::Occupied), 500 Some(exp) => { 501 if let Entry::Occupied(entry) = self.0.entry(key) { 502 Err(FullCapRemoveExpiredOccupiedErr::Occupied(OccupiedError { 503 entry, 504 value, 505 })) 506 } else { 507 Err(FullCapRemoveExpiredOccupiedErr::CapacityFull(exp)) 508 } 509 } 510 } 511 } else { 512 self.0 513 .try_insert(key, value) 514 .map_err(FullCapRemoveExpiredOccupiedErr::Occupied) 515 } 516 } 517 /// [`Self::try_insert`] except all expired ceremonies are removed in the event [`Self::max_len`] entries have 518 /// been added. 519 /// 520 /// # Errors 521 /// 522 /// Errors iff [`HashMap::try_insert`] does after removing all expired ceremonies. 523 #[inline] 524 pub fn try_insert_remove_all_expired( 525 &mut self, 526 key: K, 527 value: V, 528 ) -> Result<&mut V, FullCapRemoveExpiredOccupiedErr<'_, K, V, S>> { 529 if self.0.len() == self.1 { 530 match self.remove_expired_ceremonies() { 531 None => self 532 .0 533 .try_insert(key, value) 534 .map_err(FullCapRemoveExpiredOccupiedErr::Occupied), 535 Some(exp) => { 536 if let Entry::Occupied(entry) = self.0.entry(key) { 537 Err(FullCapRemoveExpiredOccupiedErr::Occupied(OccupiedError { 538 entry, 539 value, 540 })) 541 } else { 542 Err(FullCapRemoveExpiredOccupiedErr::CapacityFull(exp)) 543 } 544 } 545 } 546 } else { 547 self.0 548 .try_insert(key, value) 549 .map_err(FullCapRemoveExpiredOccupiedErr::Occupied) 550 } 551 } 552 /// [`Self::insert`] except the first encountered expired ceremony is removed in the event [`Self::max_len`] 553 /// entries have been added. 554 #[inline] 555 pub fn insert_remove_expired(&mut self, k: K, v: V) -> InsertRemoveExpired<V> { 556 if self.0.len() == self.1 { 557 match self.remove_first_expired_ceremony() { 558 None => self.0.insert(k, v).map_or_else( 559 || InsertRemoveExpired::Success, 560 InsertRemoveExpired::Previous, 561 ), 562 Some(exp) => { 563 if let Entry::Occupied(mut ent) = self.0.entry(k) { 564 InsertRemoveExpired::Previous(ent.insert(v)) 565 } else { 566 InsertRemoveExpired::CapacityFull(exp) 567 } 568 } 569 } 570 } else { 571 self.0.insert(k, v).map_or_else( 572 || InsertRemoveExpired::Success, 573 InsertRemoveExpired::Previous, 574 ) 575 } 576 } 577 /// [`Self::insert`] except all expired ceremonies are removed in the event [`Self::max_len`] entries have 578 /// been added. 579 #[inline] 580 pub fn insert_remove_all_expired(&mut self, k: K, v: V) -> InsertRemoveExpired<V> { 581 if self.0.len() == self.1 { 582 match self.remove_expired_ceremonies() { 583 None => self.0.insert(k, v).map_or_else( 584 || InsertRemoveExpired::Success, 585 InsertRemoveExpired::Previous, 586 ), 587 Some(exp) => { 588 if let Entry::Occupied(mut ent) = self.0.entry(k) { 589 InsertRemoveExpired::Previous(ent.insert(v)) 590 } else { 591 InsertRemoveExpired::CapacityFull(exp) 592 } 593 } 594 } 595 } else { 596 self.0.insert(k, v).map_or_else( 597 || InsertRemoveExpired::Success, 598 InsertRemoveExpired::Previous, 599 ) 600 } 601 } 602 /// [`Self::entry`] except the first encountered expired ceremony is removed in the event [`Self::max_len`] 603 /// entries have been added. 604 #[inline] 605 pub fn entry_remove_expired(&mut self, key: K) -> EntryStatusRemoveExpired<Entry<'_, K, V, S>> { 606 if self.0.len() == self.1 { 607 match self.remove_first_expired_ceremony() { 608 None => EntryStatusRemoveExpired::Success(self.0.entry(key)), 609 Some(exp) => { 610 if let ent @ Entry::Occupied(_) = self.0.entry(key) { 611 EntryStatusRemoveExpired::Success(ent) 612 } else { 613 EntryStatusRemoveExpired::CapacityFull(exp) 614 } 615 } 616 } 617 } else { 618 EntryStatusRemoveExpired::Success(self.0.entry(key)) 619 } 620 } 621 /// [`Self::entry`] except all expired ceremonies are removed in the event [`Self::max_len`] entries have 622 /// been added. 623 #[inline] 624 pub fn entry_remove_all_expired( 625 &mut self, 626 key: K, 627 ) -> EntryStatusRemoveExpired<Entry<'_, K, V, S>> { 628 if self.0.len() == self.1 { 629 match self.remove_expired_ceremonies() { 630 None => EntryStatusRemoveExpired::Success(self.0.entry(key)), 631 Some(exp) => { 632 if let ent @ Entry::Occupied(_) = self.0.entry(key) { 633 EntryStatusRemoveExpired::Success(ent) 634 } else { 635 EntryStatusRemoveExpired::CapacityFull(exp) 636 } 637 } 638 } 639 } else { 640 EntryStatusRemoveExpired::Success(self.0.entry(key)) 641 } 642 } 643 /// [`Self::entry_ref`] except the first encoutered expired ceremony is removed in the event [`Self::max_len`] 644 /// entries have been added. 645 #[inline] 646 pub fn entry_ref_remove_expired<'a, 'b, Q: Equivalent<K> + Hash + ?Sized>( 647 &'a mut self, 648 key: &'b Q, 649 ) -> EntryStatusRemoveExpired<EntryRef<'a, 'b, K, Q, V, S>> { 650 if self.0.len() == self.1 { 651 match self.remove_first_expired_ceremony() { 652 None => EntryStatusRemoveExpired::Success(self.0.entry_ref(key)), 653 Some(exp) => { 654 if let ent @ EntryRef::Occupied(_) = self.0.entry_ref(key) { 655 EntryStatusRemoveExpired::Success(ent) 656 } else { 657 EntryStatusRemoveExpired::CapacityFull(exp) 658 } 659 } 660 } 661 } else { 662 EntryStatusRemoveExpired::Success(self.0.entry_ref(key)) 663 } 664 } 665 /// [`Self::entry_ref`] except all expired ceremonies are removed in the event [`Self::max_len`] entries have 666 /// been added. 667 #[inline] 668 pub fn entry_ref_remove_all_expired<'a, 'b, Q: Equivalent<K> + Hash + ?Sized>( 669 &'a mut self, 670 key: &'b Q, 671 ) -> EntryStatusRemoveExpired<EntryRef<'a, 'b, K, Q, V, S>> { 672 if self.0.len() == self.1 { 673 match self.remove_expired_ceremonies() { 674 None => EntryStatusRemoveExpired::Success(self.0.entry_ref(key)), 675 Some(exp) => { 676 if let ent @ EntryRef::Occupied(_) = self.0.entry_ref(key) { 677 EntryStatusRemoveExpired::Success(ent) 678 } else { 679 EntryStatusRemoveExpired::CapacityFull(exp) 680 } 681 } 682 } 683 } else { 684 EntryStatusRemoveExpired::Success(self.0.entry_ref(key)) 685 } 686 } 687 } 688 impl<K, V, S> AsRef<HashMap<K, V, S>> for MaxLenHashMap<K, V, S> { 689 #[inline] 690 fn as_ref(&self) -> &HashMap<K, V, S> { 691 &self.0 692 } 693 } 694 impl<K, V, S> From<MaxLenHashMap<K, V, S>> for HashMap<K, V, S> { 695 #[inline] 696 fn from(value: MaxLenHashMap<K, V, S>) -> Self { 697 value.0 698 } 699 } 700 #[cfg(test)] 701 mod tests { 702 use super::{Equivalent, Insert, InsertRemoveExpired, MaxLenHashMap, TimedCeremony}; 703 use core::hash::{Hash, Hasher}; 704 #[cfg(not(feature = "serializable_server_state"))] 705 use std::time::Instant; 706 #[cfg(feature = "serializable_server_state")] 707 use std::time::SystemTime; 708 #[derive(Clone, Copy)] 709 struct Ceremony { 710 id: usize, 711 #[cfg(not(feature = "serializable_server_state"))] 712 exp: Instant, 713 #[cfg(feature = "serializable_server_state")] 714 exp: SystemTime, 715 } 716 impl Default for Ceremony { 717 fn default() -> Self { 718 Self { 719 id: 0, 720 #[cfg(not(feature = "serializable_server_state"))] 721 exp: Instant::now(), 722 #[cfg(feature = "serializable_server_state")] 723 exp: SystemTime::now(), 724 } 725 } 726 } 727 impl PartialEq for Ceremony { 728 fn eq(&self, other: &Self) -> bool { 729 self.id == other.id 730 } 731 } 732 impl Eq for Ceremony {} 733 impl Hash for Ceremony { 734 fn hash<H: Hasher>(&self, state: &mut H) { 735 self.id.hash(state); 736 } 737 } 738 impl TimedCeremony for Ceremony { 739 #[cfg(not(feature = "serializable_server_state"))] 740 fn expiration(&self) -> Instant { 741 self.exp 742 } 743 #[cfg(feature = "serializable_server_state")] 744 fn expiration(&self) -> SystemTime { 745 self.exp 746 } 747 } 748 impl Equivalent<Ceremony> for usize { 749 #[inline] 750 fn equivalent(&self, key: &Ceremony) -> bool { 751 *self == key.id 752 } 753 } 754 #[test] 755 fn hash_map_insert_removed() { 756 const REQ_MAX_LEN: usize = 8; 757 let mut map = MaxLenHashMap::new(REQ_MAX_LEN); 758 let cap = map.as_ref().capacity(); 759 let max_len = map.max_len(); 760 assert_eq!(cap >> 1u8, max_len); 761 assert!(max_len >= REQ_MAX_LEN); 762 let mut cer = Ceremony::default(); 763 for i in 0..max_len { 764 assert!(map.as_ref().capacity() <= cap); 765 cer.id = i; 766 assert_eq!(map.insert(cer, i), Insert::Success); 767 } 768 assert!(map.as_ref().capacity() <= cap); 769 assert_eq!(map.as_ref().len(), max_len); 770 for i in 0..max_len { 771 assert!(map.as_ref().contains_key(&i)); 772 } 773 cer.id = cap; 774 assert_eq!( 775 map.insert_remove_expired(cer, 10), 776 InsertRemoveExpired::Success 777 ); 778 assert!(map.as_ref().capacity() <= cap); 779 assert_eq!(map.as_ref().len(), max_len); 780 let mut counter = 0; 781 for i in 0..max_len { 782 counter += usize::from(map.as_ref().contains_key(&i)); 783 } 784 assert_eq!(counter, max_len - 1); 785 assert!(map.as_ref().contains_key(&(max_len - 1))); 786 } 787 }