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