calc_lib/
cache.rs

1use 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.
5pub 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}
15impl<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.
33macro_rules! cache {
34    ( $( $x:literal),* ) => {
35        $(
36impl<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}
72impl<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.
83cache!(
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);
149impl<T, const N: usize> Cache<T, N>
150where
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}
163impl<T, const N: usize> Default for Cache<T, N>
164where
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)]
177mod 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}