cache.rs (9105B)
1 use core::ops::Index; 2 /// A cache of `N` `T`s. When the cache is filled up, 3 /// a new entry overwrites the oldest entry. `Cache<T, N>` 4 /// cannot be expanded or shrunk. 5 #[derive(Debug)] 6 pub struct Cache<T, const N: usize> { 7 /// The cache of `T`s. 8 vals: [T; N], 9 /// The number of `T`s in our cache. Once 10 /// `N` number of `T`s have been cached, this will 11 /// always be `N`. 12 len: usize, 13 /// The index position of the next insert. 14 next_head: usize, 15 } 16 impl<T, const N: usize> Cache<T, N> { 17 /// Returns the number of items cached. 18 /// This will always return `N` once at least 19 /// `N` items have been cached. 20 #[inline] 21 pub const fn len(&self) -> usize { 22 self.len 23 } 24 /// Returns true iff no items have been cached. 25 #[inline] 26 pub const fn is_empty(&self) -> bool { 27 self.len == 0 28 } 29 } 30 /// Implements the functions `get`, `get_unsafe`, and `push` as well as `Index<usize, Output = T>` 31 /// for each of the passed usize literals. 32 /// Only powers of two are allowed to be passed due to how the above functions are implemented. 33 /// If any other value is passed, the implementation of those functions will be wrong. 34 macro_rules! cache { 35 ( $( $x:literal),* ) => { 36 $( 37 impl<T> Cache<T, $x> { 38 /// Returns `Some(&T)` iff there is an item located 39 /// at index `idx`. Indexing begins at the newest 40 /// entry (i.e., `self.get(0)` will return the most recent entry 41 /// iff at least one item has been cached). 42 #[inline] 43 pub fn get(&self, idx: usize) -> Option<&T> { 44 (idx < self.len).then(|| self.vals.index(self.next_head.wrapping_sub(1).wrapping_sub(idx) & ($x - 1))) 45 } 46 /// Returns a `&T` at index position `idx % N`. In the event 47 /// `(idx % N) >= self.len()`, then `&T` references the 48 /// default value of `T` that was inserted at creation but *not* 49 /// actually inserted via `push`. 50 /// 51 /// # Correctness 52 /// 53 /// `idx < self.len()`; otherwise a value that was not actually inserted will be returned. 54 #[inline] 55 pub fn get_unchecked(&self, idx: usize) -> &T { 56 self.vals.index(self.next_head.wrapping_sub(1).wrapping_sub(idx) & ($x - 1)) 57 } 58 /// Adds `val` to the cache. In the event `N` values have already been cached, 59 /// the oldest entry is overwritten. 60 #[expect(clippy::arithmetic_side_effects, reason = "must, and overflow is not possible")] 61 #[expect(clippy::indexing_slicing, reason = "wont panic since next_head is always correct")] 62 #[inline] 63 pub fn push(&mut self, val: T) { 64 if self.len < $x { 65 self.len += 1; 66 } 67 // next_head is always less than or equal to N since we only implement 68 // this function when N is a power of 2. 69 self.vals[self.next_head] = val; 70 self.next_head = (self.next_head + 1) & ($x - 1); 71 } 72 } 73 impl<T> Index<usize> for Cache<T, $x> { 74 type Output = T; 75 #[inline] 76 fn index(&self, index: usize) -> &Self::Output { 77 self.get(index).unwrap() 78 } 79 } 80 )* 81 }; 82 } 83 // MUST only pass powers of two! Anything else will lead to wrong code. 84 cache!( 85 0x1, 86 0x2, 87 0x4, 88 0x8, 89 0x10, 90 0x20, 91 0x40, 92 0x80, 93 0x100, 94 0x200, 95 0x400, 96 0x800, 97 0x1000, 98 0x2000, 99 0x4000, 100 0x8000, 101 0x0001_0000, 102 0x0002_0000, 103 0x0004_0000, 104 0x0008_0000, 105 0x0010_0000, 106 0x0020_0000, 107 0x0040_0000, 108 0x0080_0000, 109 0x0100_0000, 110 0x0200_0000, 111 0x0400_0000, 112 0x0800_0000, 113 0x1000_0000, 114 0x2000_0000, 115 0x4000_0000, 116 0x8000_0000, 117 0x0001_0000_0000, 118 0x0002_0000_0000, 119 0x0004_0000_0000, 120 0x0008_0000_0000, 121 0x0010_0000_0000, 122 0x0020_0000_0000, 123 0x0040_0000_0000, 124 0x0080_0000_0000, 125 0x0100_0000_0000, 126 0x0200_0000_0000, 127 0x0400_0000_0000, 128 0x0800_0000_0000, 129 0x1000_0000_0000, 130 0x2000_0000_0000, 131 0x4000_0000_0000, 132 0x8000_0000_0000, 133 0x0001_0000_0000_0000, 134 0x0002_0000_0000_0000, 135 0x0004_0000_0000_0000, 136 0x0008_0000_0000_0000, 137 0x0010_0000_0000_0000, 138 0x0020_0000_0000_0000, 139 0x0040_0000_0000_0000, 140 0x0080_0000_0000_0000, 141 0x0100_0000_0000_0000, 142 0x0200_0000_0000_0000, 143 0x0400_0000_0000_0000, 144 0x0800_0000_0000_0000, 145 0x1000_0000_0000_0000, 146 0x2000_0000_0000_0000, 147 0x4000_0000_0000_0000, 148 0x8000_0000_0000_0000 149 ); 150 impl<T, const N: usize> Cache<T, N> 151 where 152 [T; N]: Default, 153 { 154 /// Returns an instance of itself pre-loaded with 155 /// the `N` instances of the default value of `T`. 156 /// Note these default instances are treated as though 157 /// they don't exist (i.e., `self.is_empty()` will return true). 158 #[inline] 159 #[must_use] 160 pub fn new() -> Self { 161 Self::default() 162 } 163 } 164 impl<T, const N: usize> Default for Cache<T, N> 165 where 166 [T; N]: Default, 167 { 168 #[inline] 169 fn default() -> Self { 170 Self { 171 vals: Default::default(), 172 len: 0, 173 next_head: 0, 174 } 175 } 176 } 177 #[cfg(test)] 178 mod tests { 179 use super::Cache; 180 #[test] 181 fn len() { 182 let mut c = Cache::<bool, 1>::new(); 183 assert_eq!(0, c.len()); 184 c.push(false); 185 assert_eq!(1, c.len()); 186 c.push(false); 187 assert_eq!(1, c.len()); 188 } 189 #[test] 190 fn is_empty() { 191 let mut c = Cache::<bool, 1>::new(); 192 assert!(c.is_empty()); 193 c.push(false); 194 assert!(!c.is_empty()); 195 } 196 #[expect(clippy::cognitive_complexity, reason = "a lot to test")] 197 #[test] 198 fn get() { 199 let mut c = Cache::<bool, 4>::new(); 200 assert_eq!(c.get(0), None); 201 assert_eq!(c.get(1), None); 202 assert_eq!(c.get(2), None); 203 assert_eq!(c.get(3), None); 204 assert_eq!(c.get(4), None); 205 assert_eq!(c.get(5), None); 206 assert_eq!(c.get(usize::MAX), None); 207 c.push(true); 208 assert_eq!(c.get(0), Some(&true)); 209 assert_eq!(c.get(1), None); 210 assert_eq!(c.get(2), None); 211 assert_eq!(c.get(3), None); 212 assert_eq!(c.get(4), None); 213 assert_eq!(c.get(5), None); 214 assert_eq!(c.get(usize::MAX), None); 215 c.push(false); 216 assert_eq!(c.get(0), Some(&false)); 217 assert_eq!(c.get(1), Some(&true)); 218 assert_eq!(c.get(2), None); 219 assert_eq!(c.get(3), None); 220 assert_eq!(c.get(4), None); 221 assert_eq!(c.get(5), None); 222 assert_eq!(c.get(usize::MAX), None); 223 c.push(false); 224 assert_eq!(c.get(0), Some(&false)); 225 assert_eq!(c.get(1), Some(&false)); 226 assert_eq!(c.get(2), Some(&true)); 227 assert_eq!(c.get(3), None); 228 assert_eq!(c.get(4), None); 229 assert_eq!(c.get(5), None); 230 assert_eq!(c.get(usize::MAX), None); 231 c.push(true); 232 assert_eq!(c.get(0), Some(&true)); 233 assert_eq!(c.get(1), Some(&false)); 234 assert_eq!(c.get(2), Some(&false)); 235 assert_eq!(c.get(3), Some(&true)); 236 assert_eq!(c.get(4), None); 237 assert_eq!(c.get(5), None); 238 assert_eq!(c.get(usize::MAX), None); 239 c.push(true); 240 assert_eq!(c.get(0), Some(&true)); 241 assert_eq!(c.get(1), Some(&true)); 242 assert_eq!(c.get(2), Some(&false)); 243 assert_eq!(c.get(3), Some(&false)); 244 assert_eq!(c.get(4), None); 245 assert_eq!(c.get(5), None); 246 assert_eq!(c.get(usize::MAX), None); 247 } 248 #[test] 249 fn get_unsafe() { 250 let mut c = Cache::<bool, 4>::new(); 251 assert!(!c.get_unchecked(0)); 252 assert!(!c.get_unchecked(1)); 253 assert!(!c.get_unchecked(2)); 254 assert!(!c.get_unchecked(3)); 255 assert!(!c.get_unchecked(4)); 256 c.push(true); 257 assert!(c.get_unchecked(0)); 258 assert!(!c.get_unchecked(1)); 259 assert!(!c.get_unchecked(2)); 260 assert!(!c.get_unchecked(3)); 261 assert!(c.get_unchecked(4)); 262 } 263 #[expect(clippy::indexing_slicing, reason = "comment justifies correctness")] 264 #[test] 265 fn index() { 266 let mut c = Cache::<bool, 4>::new(); 267 c.push(true); 268 // `c.len() > 0`. 269 assert!(c[0]); 270 } 271 #[expect(clippy::indexing_slicing, reason = "comment justifies correctness")] 272 #[test] 273 #[should_panic(expected = "called `Option::unwrap()` on a `None` value")] 274 fn index_panic() { 275 let c = Cache::<bool, 4>::new(); 276 // `c.len() > 0`. 277 assert!(c[0]); 278 } 279 #[expect(clippy::indexing_slicing, reason = "comments justify correctness")] 280 #[test] 281 fn push() { 282 let mut c = Cache::<bool, 4>::new(); 283 c.push(true); 284 // `c.len() > 0`. 285 assert!(c[0]); 286 c.push(true); 287 // `c.len() > 0`. 288 assert!(c[0]); 289 c.push(false); 290 // `c.len() > 0`. 291 assert!(!c[0]); 292 c.push(true); 293 // `c.len() > 0`. 294 assert!(c[0]); 295 c.push(false); 296 // `c.len() > 0`. 297 assert!(!c[0]); 298 c.push(false); 299 // `c.len() > 0`. 300 assert!(!c[0]); 301 } 302 #[test] 303 fn new() { 304 _ = Cache::<bool, 0>::new(); 305 _ = Cache::<bool, 32>::new(); 306 _ = Cache::<bool, 31>::new(); 307 } 308 }