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.
5#[derive(Debug)]
6pub 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}
16impl<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.
34macro_rules! cache {
35    ( $( $x:literal),* ) => {
36        $(
37impl<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}
73impl<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.
84cache!(
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);
150impl<T, const N: usize> Cache<T, N>
151where
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}
164impl<T, const N: usize> Default for Cache<T, N>
165where
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)]
178mod 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}
calc_lib/cache.rs

calc_lib/
cache.rs
