hash_set.rs (9290B)
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_set::{Drain, Entry, ExtractIf, HashSet}, 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 [`HashSet`] that maximum [`HashSet::capacity`]. 14 /// 15 /// This is useful in situations when the underlying values are expected to be removed, and one wants to ensure the 16 /// set does not grow unbounded. When `T` is a [`TimedCeremony`], helper methods (e.g., 17 /// [`Self::insert_remove_all_expired`]) are provided that will automatically remove expired values. Note the 18 /// intended use case is for `T` 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 `HashSet` 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.FixedCapHashSet.html#impl-Into<U>-for-T 25 #[derive(Debug)] 26 pub struct FixedCapHashSet<T, S = BuildIdentityHasher>(HashSet<T, S>); 27 impl<T> FixedCapHashSet<T, BuildIdentityHasher> { 28 /// [`HashSet::with_capacity_and_hasher`] using `capacity` and `BuildIdentityHasher`. 29 #[inline] 30 #[must_use] 31 pub fn new(capacity: usize) -> Self { 32 Self(HashSet::with_capacity_and_hasher( 33 capacity, 34 BuildIdentityHasher, 35 )) 36 } 37 } 38 impl<T, S> FixedCapHashSet<T, S> { 39 /// [`HashSet::clear`]. 40 #[inline] 41 pub fn clear(&mut self) { 42 self.0.clear(); 43 } 44 /// [`HashSet::drain`]. 45 #[inline] 46 pub fn drain(&mut self) -> Drain<'_, T> { 47 self.0.drain() 48 } 49 /// [`HashSet::extract_if`]. 50 #[inline] 51 pub fn extract_if<F: FnMut(&T) -> bool>(&mut self, f: F) -> ExtractIf<'_, T, F> { 52 self.0.extract_if(f) 53 } 54 /// [`HashSet::with_capacity_and_hasher`]. 55 #[inline] 56 #[must_use] 57 pub fn with_hasher(capacity: usize, hasher: S) -> Self { 58 Self(HashSet::with_capacity_and_hasher(capacity, hasher)) 59 } 60 /// [`HashSet::retain`]. 61 #[inline] 62 pub fn retain<F: FnMut(&T) -> bool>(&mut self, f: F) { 63 self.0.retain(f); 64 } 65 } 66 impl<T: TimedCeremony, S> FixedCapHashSet<T, S> { 67 /// Removes all expired ceremonies. 68 #[inline] 69 pub fn remove_expired_ceremonies(&mut self) { 70 // Even though it's more accurate to check the current `Instant` for each ceremony, we elect to capture 71 // the `Instant` we begin iteration for performance reasons. It's unlikely an appreciable amount of 72 // additional ceremonies would be removed. 73 #[cfg(not(feature = "serializable_server_state"))] 74 let now = Instant::now(); 75 #[cfg(feature = "serializable_server_state")] 76 let now = SystemTime::now(); 77 self.retain(|v| v.expiration() >= now); 78 } 79 } 80 impl<T: Eq + Hash, S: BuildHasher> FixedCapHashSet<T, S> { 81 /// [`HashSet::get_or_insert`]. 82 /// 83 /// `None` is returned iff [`HashSet::len`] `==` [`HashSet::capacity`] and `value` does not already exist in the 84 /// set. 85 #[inline] 86 pub fn get_or_insert(&mut self, value: T) -> Option<&T> { 87 if self.0.len() == self.0.capacity() { 88 self.0.get(&value) 89 } else { 90 Some(self.0.get_or_insert(value)) 91 } 92 } 93 /// [`HashSet::get_or_insert_with`]. 94 /// 95 /// `None` is returned iff [`HashSet::len`] `==` [`HashSet::capacity`] and `value` does not already exist in the 96 /// set. 97 #[inline] 98 pub fn get_or_insert_with<Q: Equivalent<T> + Hash + ?Sized, F: FnOnce(&Q) -> T>( 99 &mut self, 100 value: &Q, 101 f: F, 102 ) -> Option<&T> { 103 if self.0.len() == self.0.capacity() { 104 self.0.get(value) 105 } else { 106 Some(self.0.get_or_insert_with(value, f)) 107 } 108 } 109 /// [`HashSet::remove`]. 110 #[inline] 111 pub fn remove<Q: Equivalent<T> + Hash + ?Sized>(&mut self, value: &Q) -> bool { 112 self.0.remove(value) 113 } 114 /// [`HashSet::take`]. 115 #[inline] 116 pub fn take<Q: Equivalent<T> + Hash + ?Sized>(&mut self, value: &Q) -> Option<T> { 117 self.0.take(value) 118 } 119 /// [`HashSet::insert`]. 120 /// 121 /// `None` is returned iff [`HashSet::len`] `==` [`HashSet::capacity`] and `value` does not already exist in the 122 /// set. 123 #[inline] 124 pub fn insert(&mut self, value: T) -> Option<bool> { 125 let full = self.0.len() == self.0.capacity(); 126 if let Entry::Vacant(ent) = self.0.entry(value) { 127 if full { 128 None 129 } else { 130 _ = ent.insert(); 131 Some(true) 132 } 133 } else { 134 Some(false) 135 } 136 } 137 /// [`HashSet::replace`]. 138 /// 139 /// `None` is returned iff [`HashSet::len`] `==` [`HashSet::capacity`] and `value` does not already exist in the 140 /// set. 141 #[inline] 142 pub fn replace(&mut self, value: T) -> Option<Option<T>> { 143 // Ideally we would use the Entry API to avoid searching multiple times, but one can't while also using 144 // `replace` since there is no `OccupiedEntry::replace`. 145 if self.0.contains(&value) { 146 Some(self.0.replace(value)) 147 } else if self.0.len() == self.0.capacity() { 148 None 149 } else { 150 _ = self.0.insert(value); 151 Some(None) 152 } 153 } 154 /// [`HashSet::entry`]. 155 /// 156 /// `None` is returned iff [`HashSet::len`] `==` [`HashSet::capacity`] and `value` does not already exist in the 157 /// set. 158 #[inline] 159 pub fn entry(&mut self, value: T) -> Option<Entry<'_, T, S>> { 160 let full = self.0.len() == self.0.capacity(); 161 match self.0.entry(value) { 162 ent @ Entry::Occupied(_) => Some(ent), 163 ent @ Entry::Vacant(_) => { 164 if full { 165 None 166 } else { 167 Some(ent) 168 } 169 } 170 } 171 } 172 } 173 impl<T: Eq + Hash + TimedCeremony, S: BuildHasher> FixedCapHashSet<T, S> { 174 /// [`Self::insert`] except the first expired ceremony is removed in the event there is no available capacity. 175 #[inline] 176 pub fn insert_remove_expired(&mut self, value: T) -> Option<bool> { 177 if self.0.len() == self.0.capacity() { 178 #[cfg(not(feature = "serializable_server_state"))] 179 let now = Instant::now(); 180 #[cfg(feature = "serializable_server_state")] 181 let now = SystemTime::now(); 182 if self.0.extract_if(|v| v.expiration() < now).next().is_some() { 183 Some(self.0.insert(value)) 184 } else { 185 self.0.contains(&value).then_some(false) 186 } 187 } else { 188 Some(self.0.insert(value)) 189 } 190 } 191 /// [`Self::insert`] except all expired ceremones are removed in the event there is no available capacity. 192 #[inline] 193 pub fn insert_remove_all_expired(&mut self, value: T) -> Option<bool> { 194 if self.0.len() == self.0.capacity() { 195 self.remove_expired_ceremonies(); 196 } 197 if self.0.len() == self.0.capacity() { 198 self.0.contains(&value).then_some(false) 199 } else { 200 Some(self.0.insert(value)) 201 } 202 } 203 /// [`Self::entry`] except the first expired ceremony is removed in the event there is no available capacity. 204 #[inline] 205 pub fn entry_remove_expired(&mut self, value: T) -> Option<Entry<'_, T, S>> { 206 if self.0.len() == self.0.capacity() { 207 #[cfg(not(feature = "serializable_server_state"))] 208 let now = Instant::now(); 209 #[cfg(feature = "serializable_server_state")] 210 let now = SystemTime::now(); 211 if self.0.extract_if(|v| v.expiration() < now).next().is_some() { 212 Some(self.0.entry(value)) 213 } else if let ent @ Entry::Occupied(_) = self.0.entry(value) { 214 Some(ent) 215 } else { 216 None 217 } 218 } else { 219 Some(self.0.entry(value)) 220 } 221 } 222 /// [`Self::entry`] except all expired ceremones are removed in the event there is no available capacity. 223 #[inline] 224 pub fn entry_remove_all_expired(&mut self, value: T) -> Option<Entry<'_, T, S>> { 225 if self.0.len() == self.0.capacity() { 226 self.remove_expired_ceremonies(); 227 } 228 if self.0.len() == self.0.capacity() { 229 if let ent @ Entry::Occupied(_) = self.0.entry(value) { 230 Some(ent) 231 } else { 232 None 233 } 234 } else { 235 Some(self.0.entry(value)) 236 } 237 } 238 } 239 impl<T, S> AsRef<HashSet<T, S>> for FixedCapHashSet<T, S> { 240 #[inline] 241 fn as_ref(&self) -> &HashSet<T, S> { 242 &self.0 243 } 244 } 245 impl<T, S> From<FixedCapHashSet<T, S>> for HashSet<T, S> { 246 #[inline] 247 fn from(value: FixedCapHashSet<T, S>) -> Self { 248 value.0 249 } 250 } 251 impl<T, S> From<HashSet<T, S>> for FixedCapHashSet<T, S> { 252 #[inline] 253 fn from(value: HashSet<T, S>) -> Self { 254 Self(value) 255 } 256 }