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