hash_set.rs (23558B)
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_set::{Drain, Entry, ExtractIf, HashSet}, 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 /// [`HashSet`] that has maximum [`HashSet::capacity`] and length and allocates exactly once. 14 /// 15 /// Note due to how `HashSet` removes values, it's possible to insert a value after removing a value 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 values are expected to be removed, and one wants to ensure the 20 /// set does not grow unbounded. When `T` is a [`TimedCeremony`], helper methods (e.g., 21 /// [`Self::insert_remove_all_expired`]) are provided that will automatically remove expired values. Note the 22 /// intended use case is for `T` 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 `HashSet` 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.MaxLenHashSet.html#impl-Into<U>-for-T 29 #[derive(Debug)] 30 pub struct MaxLenHashSet<T, S = BuildIdentityHasher>(HashSet<T, S>, usize); 31 impl<T> MaxLenHashSet<T, BuildIdentityHasher> { 32 /// [`HashSet::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 [`HashSet::with_capacity_and_hasher`] `panic`s 40 /// for much smaller values than `usize::MAX / 2`—even when `T` is a zero-sized type (ZST)—this is not an 41 /// 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<T, S> MaxLenHashSet<T, 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 /// [`HashSet::clear`]. 67 #[inline] 68 pub fn clear(&mut self) { 69 self.0.clear(); 70 } 71 /// [`HashSet::drain`]. 72 #[inline] 73 pub fn drain(&mut self) -> Drain<'_, T> { 74 self.0.drain() 75 } 76 /// [`HashSet::extract_if`]. 77 #[inline] 78 pub fn extract_if<F: FnMut(&T) -> bool>(&mut self, f: F) -> ExtractIf<'_, T, F> { 79 self.0.extract_if(f) 80 } 81 /// [`HashSet::with_capacity_and_hasher`] using `2 * max_len` and `hasher`. 82 /// 83 /// Note since the actual capacity allocated may exceed the requested capacity, [`Self::max_len`] may exceed 84 /// `max_len`. 85 /// 86 /// # Panics 87 /// 88 /// `panic`s if `max_len > usize::MAX / 2`. Note since [`HashSet::with_capacity_and_hasher`] `panic`s 89 /// for much smaller values than `usize::MAX / 2`—even when `T` is a zero-sized type (ZST)—this is not an 90 /// additional `panic` than what would already occur. The only difference is the message reported. 91 #[expect( 92 clippy::expect_used, 93 reason = "purpose of this function is to panic if the hash set cannot be allocated" 94 )] 95 #[inline] 96 #[must_use] 97 pub fn with_hasher(max_len: usize, hasher: S) -> Self { 98 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); 99 let len = set.capacity() >> 1u8; 100 Self(set, len) 101 } 102 /// [`HashSet::retain`]. 103 #[inline] 104 pub fn retain<F: FnMut(&T) -> bool>(&mut self, f: F) { 105 self.0.retain(f); 106 } 107 } 108 impl<T: TimedCeremony, S> MaxLenHashSet<T, S> { 109 /// Removes all expired ceremonies. 110 /// 111 /// `None` is returned iff at least one expired ceremony was removed; otherwise returns the earliest 112 /// expiration. 113 /// 114 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is returned instead. 115 #[cfg_attr(docsrs, doc(auto_cfg = false))] 116 #[cfg(any(doc, not(feature = "serializable_server_state")))] 117 #[inline] 118 pub fn remove_expired_ceremonies(&mut self) -> Option<Instant> { 119 // Even though it's more accurate to check the current `Instant` for each ceremony, we elect to capture 120 // the `Instant` we begin iteration for performance reasons. It's unlikely an appreciable amount of 121 // additional ceremonies would be removed. 122 let now = Instant::now(); 123 let mut some = true; 124 let mut expiry_min = None; 125 self.retain(|v| { 126 let expiry = v.expiration(); 127 if expiry >= now { 128 match expiry_min { 129 None => expiry_min = Some(expiry), 130 Some(ref mut e) if expiry < *e => *e = expiry, 131 _ => (), 132 } 133 true 134 } else { 135 some = false; 136 false 137 } 138 }); 139 if some { expiry_min } else { None } 140 } 141 /// Removes all expired ceremonies. 142 /// 143 /// `None` is returned iff at least one expired ceremony was removed; otherwise returns the earliest 144 /// expiration. 145 /// 146 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is returned instead. 147 #[cfg(all(not(doc), feature = "serializable_server_state"))] 148 #[inline] 149 pub fn remove_expired_ceremonies(&mut self) -> Option<SystemTime> { 150 // Even though it's more accurate to check the current `SystemTime` for each ceremony, we elect to capture 151 // the `SystemTime` we begin iteration for performance reasons. It's unlikely an appreciable amount of 152 // additional ceremonies would be removed. 153 let now = SystemTime::now(); 154 let mut some = true; 155 let mut expiry_min = None; 156 self.retain(|v| { 157 let expiry = v.expiration(); 158 if expiry >= now { 159 match expiry_min { 160 None => expiry_min = Some(expiry), 161 Some(ref mut e) if expiry < *e => *e = expiry, 162 _ => (), 163 } 164 true 165 } else { 166 some = false; 167 false 168 } 169 }); 170 if some { expiry_min } else { None } 171 } 172 /// Removes the first encountered expired ceremony. 173 /// 174 /// `None` is returned iff an expired ceremony was removed; otherwise returns the earliest 175 /// expiration. 176 /// 177 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is returned instead. 178 #[cfg_attr(docsrs, doc(auto_cfg = false))] 179 #[cfg(any(doc, not(feature = "serializable_server_state")))] 180 #[inline] 181 pub fn remove_first_expired_ceremony(&mut self) -> Option<Instant> { 182 // Even though it's more accurate to check the current `Instant` for each ceremony, we elect to capture 183 // the `Instant` we begin iteration for performance reasons. It's unlikely an appreciable amount of 184 // additional ceremonies would be removed. 185 let now = Instant::now(); 186 let mut expiry_min = None; 187 self.0 188 .extract_if(|v| { 189 let expiry = v.expiration(); 190 if expiry < now { 191 true 192 } else { 193 match expiry_min { 194 None => expiry_min = Some(expiry), 195 Some(ref mut e) if expiry < *e => *e = expiry, 196 _ => (), 197 } 198 false 199 } 200 }) 201 .next() 202 .map_or(expiry_min, |_| None) 203 } 204 /// Removes the first encountered expired ceremony. 205 /// 206 /// `None` is returned iff an expired ceremony was removed; otherwise returns the earliest 207 /// expiration. 208 /// 209 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is returned instead. 210 #[cfg(all(not(doc), feature = "serializable_server_state"))] 211 #[inline] 212 pub fn remove_first_expired_ceremony(&mut self) -> Option<SystemTime> { 213 // Even though it's more accurate to check the current `SystemTime` for each ceremony, we elect to capture 214 // the `SystemTime` we begin iteration for performance reasons. It's unlikely an appreciable amount of 215 // additional ceremonies would be removed. 216 let now = SystemTime::now(); 217 let mut expiry_min = None; 218 self.0 219 .extract_if(|v| { 220 let expiry = v.expiration(); 221 if expiry < now { 222 true 223 } else { 224 match expiry_min { 225 None => expiry_min = Some(expiry), 226 Some(ref mut e) if expiry < *e => *e = expiry, 227 _ => (), 228 } 229 false 230 } 231 }) 232 .next() 233 .map_or(expiry_min, |_| None) 234 } 235 } 236 /// Signifies the consequences of [`MaxLenHashSet::insert`]. 237 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 238 pub enum Insert { 239 /// The value was successfully inserted. 240 Success, 241 /// The value was not inserted since it already existed. 242 Duplicate, 243 /// The value does not exist, but there was no available capacity to insert it. 244 CapacityFull, 245 } 246 /// Signifies the consequences of [`MaxLenHashSet::replace`]. 247 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 248 pub enum Replace<T> { 249 /// The value was inserted. 250 Insert, 251 /// The value replaced the contained value. 252 Previous(T), 253 /// The value does not exist, but there was no available capacity to insert it. 254 CapacityFull, 255 } 256 /// Signifies the consequences of [`MaxLenHashSet::insert_remove_expired`] and 257 /// [`MaxLenHashSet::insert_remove_all_expired`]. 258 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 259 pub enum InsertRemoveExpired { 260 /// The value was successfully inserted. 261 Success, 262 /// The value was not inserted since it already existed. 263 Duplicate, 264 /// The value does not exist, but there was no available capacity to insert it and no expired 265 /// [`TimedCeremony`]s that could be removed. 266 /// 267 /// The contained `Instant` is the earliest expiration. 268 /// 269 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is contained instead. 270 #[cfg_attr(docsrs, doc(auto_cfg = false))] 271 #[cfg(any(doc, not(feature = "serializable_server_state")))] 272 CapacityFull(Instant), 273 /// The value does not exist, but there was no available capacity to insert it and no expired 274 /// [`TimedCeremony`]s could be removed. 275 /// 276 /// The contained `Instant` is the earliest expiration. 277 /// 278 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is contained instead. 279 #[cfg(all(not(doc), feature = "serializable_server_state"))] 280 CapacityFull(SystemTime), 281 } 282 /// Signifies the consequences of [`MaxLenHashSet::entry`]. 283 #[derive(Debug)] 284 pub enum EntryStatus<'a, T, S> { 285 /// The `Entry` was successfully grabbed. 286 Success(Entry<'a, T, S>), 287 /// The capacity was full, and there was no value where the `Entry` would be. 288 CapacityFull, 289 } 290 /// Signifies the consequences of [`MaxLenHashSet::entry_remove_expired`] and 291 /// [`MaxLenHashSet::entry_remove_all_expired`]. 292 #[derive(Debug)] 293 pub enum EntryStatusRemoveExpired<'a, T, S> { 294 /// The `Entry` was successfully grabbed. 295 Success(Entry<'a, T, S>), 296 /// The capacity was full, and there was no value where the `Entry` would be. 297 /// 298 /// The contained `Instant` is the earliest expiration. 299 /// 300 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is contained instead. 301 #[cfg_attr(docsrs, doc(auto_cfg = false))] 302 #[cfg(any(doc, not(feature = "serializable_server_state")))] 303 CapacityFull(Instant), 304 /// The capacity was full, and there was no value where the `Entry` would be. 305 /// 306 /// The contained `Instant` is the earliest expiration. 307 /// 308 /// Note when `serializable_server_state` is enabled, [`SystemTime`] is contained instead. 309 #[cfg(all(not(doc), feature = "serializable_server_state"))] 310 CapacityFull(SystemTime), 311 } 312 impl<T: Eq + Hash, S: BuildHasher> MaxLenHashSet<T, S> { 313 /// [`HashSet::with_hasher`] using `hasher` followed by [`HashSet::try_reserve`] using `2 * max_len`. 314 /// 315 /// Note since the actual capacity allocated may exceed the requested capacity, [`Self::max_len`] may exceed 316 /// `max_len`. 317 /// 318 /// # Errors 319 /// 320 /// Errors iff `max_len > usize::MAX / 2` or [`HashSet::try_reserve`] does. 321 #[inline] 322 pub fn try_with_hasher(max_len: usize, hasher: S) -> Result<Self, TryReserveError> { 323 Self::requested_capacity(max_len).and_then(|additional| { 324 let mut set = HashSet::with_hasher(hasher); 325 set.try_reserve(additional).map(|()| { 326 let len = set.capacity() >> 1u8; 327 Self(set, len) 328 }) 329 }) 330 } 331 /// [`HashSet::get_or_insert`]. 332 /// 333 /// `None` is returned iff [`HashSet::len`] `==` [`Self::max_len`] and `value` does not already exist in the 334 /// set. 335 #[inline] 336 pub fn get_or_insert(&mut self, value: T) -> Option<&T> { 337 if self.0.len() == self.1 { 338 self.0.get(&value) 339 } else { 340 Some(self.0.get_or_insert(value)) 341 } 342 } 343 /// [`HashSet::get_or_insert_with`]. 344 /// 345 /// `None` is returned iff [`HashSet::len`] `==` [`Self::max_len`] and `value` does not already exist in the 346 /// set. 347 #[inline] 348 pub fn get_or_insert_with<Q: Equivalent<T> + Hash + ?Sized, F: FnOnce(&Q) -> T>( 349 &mut self, 350 value: &Q, 351 f: F, 352 ) -> Option<&T> { 353 if self.0.len() == self.1 { 354 self.0.get(value) 355 } else { 356 Some(self.0.get_or_insert_with(value, f)) 357 } 358 } 359 /// [`HashSet::remove`]. 360 #[inline] 361 pub fn remove<Q: Equivalent<T> + Hash + ?Sized>(&mut self, value: &Q) -> bool { 362 self.0.remove(value) 363 } 364 /// [`HashSet::take`]. 365 #[inline] 366 pub fn take<Q: Equivalent<T> + Hash + ?Sized>(&mut self, value: &Q) -> Option<T> { 367 self.0.take(value) 368 } 369 /// [`HashSet::insert`]. 370 #[inline] 371 pub fn insert(&mut self, value: T) -> Insert { 372 let full = self.0.len() == self.1; 373 if let Entry::Vacant(ent) = self.0.entry(value) { 374 if full { 375 Insert::CapacityFull 376 } else { 377 _ = ent.insert(); 378 Insert::Success 379 } 380 } else { 381 Insert::Duplicate 382 } 383 } 384 /// [`HashSet::replace`]. 385 #[expect(clippy::unreachable, reason = "want to crash when there is a bug")] 386 #[inline] 387 pub fn replace(&mut self, value: T) -> Replace<T> { 388 // Ideally we would use the Entry API to avoid searching multiple times, but one can't while also using 389 // `replace` since there is no `OccupiedEntry::replace`. 390 if self.0.contains(&value) { 391 Replace::Previous( 392 self.0 393 .replace(value) 394 .unwrap_or_else(|| unreachable!("there is a bug in HashSet::replace")), 395 ) 396 } else if self.0.len() == self.1 { 397 Replace::CapacityFull 398 } else { 399 _ = self.0.insert(value); 400 Replace::Insert 401 } 402 } 403 /// [`HashSet::entry`]. 404 #[inline] 405 pub fn entry(&mut self, value: T) -> EntryStatus<'_, T, S> { 406 let full = self.0.len() == self.1; 407 match self.0.entry(value) { 408 ent @ Entry::Occupied(_) => EntryStatus::Success(ent), 409 ent @ Entry::Vacant(_) => { 410 if full { 411 EntryStatus::CapacityFull 412 } else { 413 EntryStatus::Success(ent) 414 } 415 } 416 } 417 } 418 } 419 impl<T: Eq + Hash + TimedCeremony, S: BuildHasher> MaxLenHashSet<T, S> { 420 /// [`Self::insert`] except the first encountered expired ceremony is removed in the event [`Self::max_len`] 421 /// items have been added. 422 #[inline] 423 pub fn insert_remove_expired(&mut self, value: T) -> InsertRemoveExpired { 424 if self.0.len() == self.1 { 425 match self.remove_first_expired_ceremony() { 426 None => { 427 if self.0.insert(value) { 428 InsertRemoveExpired::Success 429 } else { 430 InsertRemoveExpired::Duplicate 431 } 432 } 433 Some(exp) => { 434 if self.0.contains(&value) { 435 InsertRemoveExpired::Duplicate 436 } else { 437 InsertRemoveExpired::CapacityFull(exp) 438 } 439 } 440 } 441 } else if self.0.insert(value) { 442 InsertRemoveExpired::Success 443 } else { 444 InsertRemoveExpired::Duplicate 445 } 446 } 447 /// [`Self::insert`] except all expired ceremones are removed in the event [`Self::max_len`] items have 448 /// been added. 449 #[inline] 450 pub fn insert_remove_all_expired(&mut self, value: T) -> InsertRemoveExpired { 451 if self.0.len() == self.1 { 452 match self.remove_expired_ceremonies() { 453 None => { 454 if self.0.insert(value) { 455 InsertRemoveExpired::Success 456 } else { 457 InsertRemoveExpired::Duplicate 458 } 459 } 460 Some(exp) => { 461 if self.0.contains(&value) { 462 InsertRemoveExpired::Duplicate 463 } else { 464 InsertRemoveExpired::CapacityFull(exp) 465 } 466 } 467 } 468 } else if self.0.insert(value) { 469 InsertRemoveExpired::Success 470 } else { 471 InsertRemoveExpired::Duplicate 472 } 473 } 474 /// [`Self::entry`] except the first encountered expired ceremony is removed in the event [`Self::max_len`] 475 /// items have been added. 476 #[inline] 477 pub fn entry_remove_expired(&mut self, value: T) -> EntryStatusRemoveExpired<'_, T, S> { 478 if self.0.len() == self.1 { 479 match self.remove_first_expired_ceremony() { 480 None => EntryStatusRemoveExpired::Success(self.0.entry(value)), 481 Some(exp) => { 482 if let ent @ Entry::Occupied(_) = self.0.entry(value) { 483 EntryStatusRemoveExpired::Success(ent) 484 } else { 485 EntryStatusRemoveExpired::CapacityFull(exp) 486 } 487 } 488 } 489 } else { 490 EntryStatusRemoveExpired::Success(self.0.entry(value)) 491 } 492 } 493 /// [`Self::entry`] except all expired ceremones are removed in the event [`Self::max_len`] items have 494 /// been added. 495 #[inline] 496 pub fn entry_remove_all_expired(&mut self, value: T) -> EntryStatusRemoveExpired<'_, T, S> { 497 if self.0.len() == self.1 { 498 match self.remove_expired_ceremonies() { 499 None => EntryStatusRemoveExpired::Success(self.0.entry(value)), 500 Some(exp) => { 501 if let ent @ Entry::Occupied(_) = self.0.entry(value) { 502 EntryStatusRemoveExpired::Success(ent) 503 } else { 504 EntryStatusRemoveExpired::CapacityFull(exp) 505 } 506 } 507 } 508 } else { 509 EntryStatusRemoveExpired::Success(self.0.entry(value)) 510 } 511 } 512 } 513 impl<T, S> AsRef<HashSet<T, S>> for MaxLenHashSet<T, S> { 514 #[inline] 515 fn as_ref(&self) -> &HashSet<T, S> { 516 &self.0 517 } 518 } 519 impl<T, S> From<MaxLenHashSet<T, S>> for HashSet<T, S> { 520 #[inline] 521 fn from(value: MaxLenHashSet<T, S>) -> Self { 522 value.0 523 } 524 } 525 #[cfg(test)] 526 mod tests { 527 use super::{Equivalent, Insert, InsertRemoveExpired, MaxLenHashSet, TimedCeremony}; 528 use core::hash::{Hash, Hasher}; 529 #[cfg(not(feature = "serializable_server_state"))] 530 use std::time::Instant; 531 #[cfg(feature = "serializable_server_state")] 532 use std::time::SystemTime; 533 #[derive(Clone, Copy)] 534 struct Ceremony { 535 id: usize, 536 #[cfg(not(feature = "serializable_server_state"))] 537 exp: Instant, 538 #[cfg(feature = "serializable_server_state")] 539 exp: SystemTime, 540 } 541 impl Default for Ceremony { 542 fn default() -> Self { 543 Self { 544 id: 0, 545 #[cfg(not(feature = "serializable_server_state"))] 546 exp: Instant::now(), 547 #[cfg(feature = "serializable_server_state")] 548 exp: SystemTime::now(), 549 } 550 } 551 } 552 impl PartialEq for Ceremony { 553 fn eq(&self, other: &Self) -> bool { 554 self.id == other.id 555 } 556 } 557 impl Eq for Ceremony {} 558 impl Hash for Ceremony { 559 fn hash<H: Hasher>(&self, state: &mut H) { 560 self.id.hash(state); 561 } 562 } 563 impl TimedCeremony for Ceremony { 564 #[cfg(not(feature = "serializable_server_state"))] 565 fn expiration(&self) -> Instant { 566 self.exp 567 } 568 #[cfg(feature = "serializable_server_state")] 569 fn expiration(&self) -> SystemTime { 570 self.exp 571 } 572 } 573 impl Equivalent<Ceremony> for usize { 574 #[inline] 575 fn equivalent(&self, key: &Ceremony) -> bool { 576 *self == key.id 577 } 578 } 579 #[test] 580 fn hash_set_insert_removed() { 581 const REQ_MAX_LEN: usize = 8; 582 let mut set = MaxLenHashSet::new(REQ_MAX_LEN); 583 let cap = set.as_ref().capacity(); 584 let max_len = set.max_len(); 585 assert_eq!(cap >> 1u8, max_len); 586 assert!(max_len >= REQ_MAX_LEN); 587 let mut cer = Ceremony::default(); 588 for i in 0..max_len { 589 assert!(set.as_ref().capacity() <= cap); 590 cer.id = i; 591 assert_eq!(set.insert(cer), Insert::Success); 592 } 593 assert!(set.as_ref().capacity() <= cap); 594 assert_eq!(set.as_ref().len(), max_len); 595 for i in 0..max_len { 596 assert!(set.as_ref().contains(&i)); 597 } 598 cer.id = cap; 599 assert_eq!(set.insert_remove_expired(cer), InsertRemoveExpired::Success); 600 assert!(set.as_ref().capacity() <= cap); 601 assert_eq!(set.as_ref().len(), max_len); 602 let mut counter = 0; 603 for i in 0..max_len { 604 counter += usize::from(set.as_ref().contains(&i)); 605 } 606 assert_eq!(counter, max_len - 1); 607 assert!(set.as_ref().contains(&(max_len - 1))); 608 } 609 }