hash_map.rs (12715B)
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, 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 /// `newtype` around [`HashMap`] that has maximum [`HashMap::capacity`]. 14 /// 15 /// This is useful in situations when the underlying entries are expected to be removed, and one wants to ensure the 16 /// map does not grow unbounded. When `K` is a [`TimedCeremony`], helper methods (e.g., 17 /// [`Self::insert_remove_all_expired`]) are provided that will automatically remove expired entries. Note the 18 /// intended use case is for `K` to be based on a server-side randomly generated value; thus the default [`Hasher`] 19 /// is [`BuildIdentityHasher`]. In the event this is not true, one MUST use a more appropriate `Hasher`. 20 /// 21 /// Only the mutable methods of `HashMap` are re-defined in order to ensure the capacity never grows. For all 22 /// other methods, first call [`Self::as_ref`] or [`Self::into`]. 23 /// 24 /// [`Self::into`]: struct.FixedCapHashMap.html#impl-Into<U>-for-T 25 #[derive(Debug)] 26 pub struct FixedCapHashMap<K, V, S = BuildIdentityHasher>(HashMap<K, V, S>); 27 impl<K, V> FixedCapHashMap<K, V, BuildIdentityHasher> { 28 /// [`HashMap::with_capacity_and_hasher`] using `capacity` and `BuildIdentityHasher`. 29 #[inline] 30 #[must_use] 31 pub fn new(capacity: usize) -> Self { 32 Self(HashMap::with_capacity_and_hasher( 33 capacity, 34 BuildIdentityHasher, 35 )) 36 } 37 } 38 impl<K, V, S> FixedCapHashMap<K, V, S> { 39 /// [`HashMap::values_mut`]. 40 #[inline] 41 pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> { 42 self.0.values_mut() 43 } 44 /// [`HashMap::iter_mut`]. 45 #[expect( 46 clippy::iter_without_into_iter, 47 reason = "re-export all mutable methods of HashMap" 48 )] 49 #[inline] 50 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { 51 self.0.iter_mut() 52 } 53 /// [`HashMap::clear`]. 54 #[inline] 55 pub fn clear(&mut self) { 56 self.0.clear(); 57 } 58 /// [`HashMap::drain`]. 59 #[inline] 60 pub fn drain(&mut self) -> Drain<'_, K, V> { 61 self.0.drain() 62 } 63 /// [`HashMap::extract_if`]. 64 #[inline] 65 pub fn extract_if<F: FnMut(&K, &mut V) -> bool>(&mut self, f: F) -> ExtractIf<'_, K, V, F> { 66 self.0.extract_if(f) 67 } 68 /// [`HashMap::with_capacity_and_hasher`]. 69 #[inline] 70 #[must_use] 71 pub fn with_hasher(capacity: usize, hasher: S) -> Self { 72 Self(HashMap::with_capacity_and_hasher(capacity, hasher)) 73 } 74 /// [`HashMap::retain`]. 75 #[inline] 76 pub fn retain<F: FnMut(&K, &mut V) -> bool>(&mut self, f: F) { 77 self.0.retain(f); 78 } 79 } 80 impl<K: TimedCeremony, V, S> FixedCapHashMap<K, V, S> { 81 /// Removes all expired ceremonies. 82 #[inline] 83 pub fn remove_expired_ceremonies(&mut self) { 84 // Even though it's more accurate to check the current `Instant` for each ceremony, we elect to capture 85 // the `Instant` we begin iteration for performance reasons. It's unlikely an appreciable amount of 86 // additional ceremonies would be removed. 87 #[cfg(not(feature = "serializable_server_state"))] 88 let now = Instant::now(); 89 #[cfg(feature = "serializable_server_state")] 90 let now = SystemTime::now(); 91 self.retain(|v, _| v.expiration() >= now); 92 } 93 } 94 impl<K: Eq + Hash, V, S: BuildHasher> FixedCapHashMap<K, V, S> { 95 /// [`HashMap::get_mut`]. 96 #[inline] 97 pub fn get_mut<Q: Equivalent<K> + Hash + ?Sized>(&mut self, k: &Q) -> Option<&mut V> { 98 self.0.get_mut(k) 99 } 100 /// [`HashMap::get_key_value_mut`]. 101 #[inline] 102 pub fn get_key_value_mut<Q: Equivalent<K> + Hash + ?Sized>( 103 &mut self, 104 k: &Q, 105 ) -> Option<(&K, &mut V)> { 106 self.0.get_key_value_mut(k) 107 } 108 /// [`HashMap::get_many_mut`]. 109 #[inline] 110 pub fn get_many_mut<Q: Equivalent<K> + Hash + ?Sized, const N: usize>( 111 &mut self, 112 ks: [&Q; N], 113 ) -> [Option<&mut V>; N] { 114 self.0.get_many_mut(ks) 115 } 116 /// [`HashMap::get_many_key_value_mut`]. 117 #[inline] 118 pub fn get_many_key_value_mut<Q: Equivalent<K> + Hash + ?Sized, const N: usize>( 119 &mut self, 120 ks: [&Q; N], 121 ) -> [Option<(&K, &mut V)>; N] { 122 self.0.get_many_key_value_mut(ks) 123 } 124 /// [`HashMap::remove`]. 125 #[inline] 126 pub fn remove<Q: Equivalent<K> + Hash + ?Sized>(&mut self, k: &Q) -> Option<V> { 127 self.0.remove(k) 128 } 129 /// [`HashMap::remove_entry`]. 130 #[inline] 131 pub fn remove_entry<Q: Equivalent<K> + Hash + ?Sized>(&mut self, k: &Q) -> Option<(K, V)> { 132 self.0.remove_entry(k) 133 } 134 /// [`HashMap::try_insert`]. 135 /// 136 /// `Ok(None)` is returned iff [`HashMap::len`] `==` [`HashMap::capacity`] and `key` does not already exist in 137 /// the map. 138 /// 139 /// # Errors 140 /// 141 /// Errors iff [`HashMap::insert`] does. 142 #[inline] 143 pub fn try_insert( 144 &mut self, 145 key: K, 146 value: V, 147 ) -> Result<Option<&mut V>, OccupiedError<'_, K, V, S>> { 148 let full = self.0.len() == self.0.capacity(); 149 match self.0.entry(key) { 150 Entry::Occupied(entry) => Err(OccupiedError { entry, value }), 151 Entry::Vacant(ent) => { 152 if full { 153 Ok(None) 154 } else { 155 Ok(Some(ent.insert(value))) 156 } 157 } 158 } 159 } 160 /// [`HashMap::insert`]. 161 /// 162 /// `None` is returned iff [`HashMap::len`] `==` [`HashMap::capacity`] and `key` does not already exist in the 163 /// map. 164 #[inline] 165 pub fn insert(&mut self, k: K, v: V) -> Option<Option<V>> { 166 let full = self.0.len() == self.0.capacity(); 167 match self.0.entry(k) { 168 Entry::Occupied(mut ent) => Some(Some(ent.insert(v))), 169 Entry::Vacant(ent) => { 170 if full { 171 None 172 } else { 173 _ = ent.insert(v); 174 Some(None) 175 } 176 } 177 } 178 } 179 /// [`HashMap::entry`]. 180 /// 181 /// `None` is returned iff [`HashMap::len`] `==` [`HashMap::capacity`] and `key` does not already exist in the 182 /// map. 183 #[inline] 184 pub fn entry(&mut self, key: K) -> Option<Entry<'_, K, V, S>> { 185 let full = self.0.len() == self.0.capacity(); 186 match self.0.entry(key) { 187 ent @ Entry::Occupied(_) => Some(ent), 188 ent @ Entry::Vacant(_) => { 189 if full { 190 None 191 } else { 192 Some(ent) 193 } 194 } 195 } 196 } 197 /// [`HashMap::entry_ref`]. 198 /// 199 /// `None` is returned iff [`HashMap::len`] `==` [`HashMap::capacity`] and `key` does not already exist in the 200 /// map. 201 #[inline] 202 pub fn entry_ref<'a, 'b, Q: Equivalent<K> + Hash + ?Sized>( 203 &'a mut self, 204 key: &'b Q, 205 ) -> Option<EntryRef<'a, 'b, K, Q, V, S>> { 206 let full = self.0.len() == self.0.capacity(); 207 match self.0.entry_ref(key) { 208 ent @ EntryRef::Occupied(_) => Some(ent), 209 ent @ EntryRef::Vacant(_) => { 210 if full { 211 None 212 } else { 213 Some(ent) 214 } 215 } 216 } 217 } 218 } 219 impl<K: Eq + Hash + TimedCeremony, V, S: BuildHasher> FixedCapHashMap<K, V, S> { 220 /// [`Self::insert`] except the first expired ceremony is removed in the event there is no available capacity. 221 #[inline] 222 pub fn insert_remove_expired(&mut self, k: K, v: V) -> Option<Option<V>> { 223 if self.0.len() == self.0.capacity() { 224 #[cfg(not(feature = "serializable_server_state"))] 225 let now = Instant::now(); 226 #[cfg(feature = "serializable_server_state")] 227 let now = SystemTime::now(); 228 if self 229 .0 230 .extract_if(|exp, _| exp.expiration() < now) 231 .next() 232 .is_some() 233 { 234 Some(self.0.insert(k, v)) 235 } else if let Entry::Occupied(mut ent) = self.0.entry(k) { 236 Some(Some(ent.insert(v))) 237 } else { 238 None 239 } 240 } else { 241 Some(self.0.insert(k, v)) 242 } 243 } 244 /// [`Self::insert`] except all expired ceremones are removed in the event there is no available capacity. 245 #[inline] 246 pub fn insert_remove_all_expired(&mut self, k: K, v: V) -> Option<Option<V>> { 247 if self.0.len() == self.0.capacity() { 248 self.remove_expired_ceremonies(); 249 } 250 if self.0.len() == self.0.capacity() { 251 if let Entry::Occupied(mut ent) = self.0.entry(k) { 252 Some(Some(ent.insert(v))) 253 } else { 254 None 255 } 256 } else { 257 Some(self.0.insert(k, v)) 258 } 259 } 260 /// [`Self::entry`] except the first expired ceremony is removed in the event there is no available capacity. 261 #[inline] 262 pub fn entry_remove_expired(&mut self, key: K) -> Option<Entry<'_, K, V, S>> { 263 if self.0.len() == self.0.capacity() { 264 #[cfg(not(feature = "serializable_server_state"))] 265 let now = Instant::now(); 266 #[cfg(feature = "serializable_server_state")] 267 let now = SystemTime::now(); 268 if self 269 .0 270 .extract_if(|v, _| v.expiration() < now) 271 .next() 272 .is_some() 273 { 274 Some(self.0.entry(key)) 275 } else if let ent @ Entry::Occupied(_) = self.0.entry(key) { 276 Some(ent) 277 } else { 278 None 279 } 280 } else { 281 Some(self.0.entry(key)) 282 } 283 } 284 /// [`Self::entry`] except all expired ceremones are removed in the event there is no available capacity. 285 #[inline] 286 pub fn entry_remove_all_expired(&mut self, key: K) -> Option<Entry<'_, K, V, S>> { 287 if self.0.len() == self.0.capacity() { 288 self.remove_expired_ceremonies(); 289 } 290 if self.0.len() == self.0.capacity() { 291 if let ent @ Entry::Occupied(_) = self.0.entry(key) { 292 Some(ent) 293 } else { 294 None 295 } 296 } else { 297 Some(self.0.entry(key)) 298 } 299 } 300 /// [`Self::entry_ref`] except the first expired ceremony is removed in the event there is no available capacity. 301 #[inline] 302 pub fn entry_ref_remove_expired<'a, 'b, Q: Equivalent<K> + Hash + ?Sized>( 303 &'a mut self, 304 key: &'b Q, 305 ) -> Option<EntryRef<'a, 'b, K, Q, V, S>> { 306 if self.0.len() == self.0.capacity() { 307 #[cfg(not(feature = "serializable_server_state"))] 308 let now = Instant::now(); 309 #[cfg(feature = "serializable_server_state")] 310 let now = SystemTime::now(); 311 if self 312 .0 313 .extract_if(|v, _| v.expiration() < now) 314 .next() 315 .is_some() 316 { 317 Some(self.0.entry_ref(key)) 318 } else if let ent @ EntryRef::Occupied(_) = self.0.entry_ref(key) { 319 Some(ent) 320 } else { 321 None 322 } 323 } else { 324 Some(self.0.entry_ref(key)) 325 } 326 } 327 /// [`Self::entry_ref`] except all expired ceremones are removed in the event there is no available capacity. 328 #[inline] 329 pub fn entry_ref_remove_all_expired<'a, 'b, Q: Equivalent<K> + Hash + ?Sized>( 330 &'a mut self, 331 key: &'b Q, 332 ) -> Option<EntryRef<'a, 'b, K, Q, V, S>> { 333 if self.0.len() == self.0.capacity() { 334 self.remove_expired_ceremonies(); 335 } 336 if self.0.len() == self.0.capacity() { 337 if let ent @ EntryRef::Occupied(_) = self.0.entry_ref(key) { 338 Some(ent) 339 } else { 340 None 341 } 342 } else { 343 Some(self.0.entry_ref(key)) 344 } 345 } 346 } 347 impl<K, V, S> AsRef<HashMap<K, V, S>> for FixedCapHashMap<K, V, S> { 348 #[inline] 349 fn as_ref(&self) -> &HashMap<K, V, S> { 350 &self.0 351 } 352 } 353 impl<K, V, S> From<FixedCapHashMap<K, V, S>> for HashMap<K, V, S> { 354 #[inline] 355 fn from(value: FixedCapHashMap<K, V, S>) -> Self { 356 value.0 357 } 358 } 359 impl<K, V, S> From<HashMap<K, V, S>> for FixedCapHashMap<K, V, S> { 360 #[inline] 361 fn from(value: HashMap<K, V, S>) -> Self { 362 Self(value) 363 } 364 }