calc_lib/

cache.rs

use core::ops::Index;
/// A cache of `N` `T`s. When the cache is filled up,
/// a new entry overwrites the oldest entry. `Cache<T, N>`
/// cannot be expanded or shrunk.
#[derive(Debug)]
pub struct Cache<T, const N: usize> {
    /// The cache of `T`s.
    vals: [T; N],
    /// The number of `T`s in our cache. Once
    /// `N` number of `T`s have been cached, this will
    /// always be `N`.
    len: usize,
    /// The index position of the next insert.
    next_head: usize,
}
impl<T, const N: usize> Cache<T, N> {
    /// Returns the number of items cached.
    /// This will always return `N` once at least
    /// `N` items have been cached.
    #[inline]
    pub const fn len(&self) -> usize {
        self.len
    }
    /// Returns true iff no items have been cached.
    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }
}
/// Implements the functions `get`, `get_unsafe`, and `push` as well as `Index<usize, Output = T>`
/// for each of the passed usize literals.
/// Only powers of two are allowed to be passed due to how the above functions are implemented.
/// If any other value is passed, the implementation of those functions will be wrong.
macro_rules! cache {
    ( $( $x:literal),* ) => {
        $(
impl<T> Cache<T, $x> {
    /// Returns `Some(&T)` iff there is an item located
    /// at index `idx`. Indexing begins at the newest
    /// entry (i.e., `self.get(0)` will return the most recent entry
    /// iff at least one item has been cached).
    #[inline]
    pub fn get(&self, idx: usize) -> Option<&T> {
        (idx < self.len).then(|| self.vals.index(self.next_head.wrapping_sub(1).wrapping_sub(idx) & ($x - 1)))
    }
    /// Returns a `&T` at index position `idx % N`. In the event
    /// `(idx % N) >= self.len()`, then `&T` references the
    /// default value of `T` that was inserted at creation but *not*
    /// actually inserted via `push`.
    ///
    /// # Correctness
    ///
    /// `idx < self.len()`; otherwise a value that was not actually inserted will be returned.
    #[inline]
    pub fn get_unchecked(&self, idx: usize) -> &T {
        self.vals.index(self.next_head.wrapping_sub(1).wrapping_sub(idx) & ($x - 1))
    }
    /// Adds `val` to the cache. In the event `N` values have already been cached,
    /// the oldest entry is overwritten.
    #[expect(clippy::arithmetic_side_effects, reason = "must, and overflow is not possible")]
    #[expect(clippy::indexing_slicing, reason = "wont panic since next_head is always correct")]
    #[inline]
    pub fn push(&mut self, val: T) {
        if self.len < $x {
            self.len += 1;
        }
        // next_head is always less than or equal to N since we only implement
        // this function when N is a power of 2.
        self.vals[self.next_head] = val;
        self.next_head = (self.next_head + 1) & ($x - 1);
    }
}
impl<T> Index<usize> for Cache<T, $x> {
    type Output = T;
    #[inline]
    fn index(&self, index: usize) -> &Self::Output {
        self.get(index).unwrap()
    }
}
        )*
    };
}
// MUST only pass powers of two! Anything else will lead to wrong code.
cache!(
    0x1,
    0x2,
    0x4,
    0x8,
    0x10,
    0x20,
    0x40,
    0x80,
    0x100,
    0x200,
    0x400,
    0x800,
    0x1000,
    0x2000,
    0x4000,
    0x8000,
    0x0001_0000,
    0x0002_0000,
    0x0004_0000,
    0x0008_0000,
    0x0010_0000,
    0x0020_0000,
    0x0040_0000,
    0x0080_0000,
    0x0100_0000,
    0x0200_0000,
    0x0400_0000,
    0x0800_0000,
    0x1000_0000,
    0x2000_0000,
    0x4000_0000,
    0x8000_0000,
    0x0001_0000_0000,
    0x0002_0000_0000,
    0x0004_0000_0000,
    0x0008_0000_0000,
    0x0010_0000_0000,
    0x0020_0000_0000,
    0x0040_0000_0000,
    0x0080_0000_0000,
    0x0100_0000_0000,
    0x0200_0000_0000,
    0x0400_0000_0000,
    0x0800_0000_0000,
    0x1000_0000_0000,
    0x2000_0000_0000,
    0x4000_0000_0000,
    0x8000_0000_0000,
    0x0001_0000_0000_0000,
    0x0002_0000_0000_0000,
    0x0004_0000_0000_0000,
    0x0008_0000_0000_0000,
    0x0010_0000_0000_0000,
    0x0020_0000_0000_0000,
    0x0040_0000_0000_0000,
    0x0080_0000_0000_0000,
    0x0100_0000_0000_0000,
    0x0200_0000_0000_0000,
    0x0400_0000_0000_0000,
    0x0800_0000_0000_0000,
    0x1000_0000_0000_0000,
    0x2000_0000_0000_0000,
    0x4000_0000_0000_0000,
    0x8000_0000_0000_0000
);
impl<T, const N: usize> Cache<T, N>
where
    [T; N]: Default,
{
    /// Returns an instance of itself pre-loaded with
    /// the `N` instances of the default value of `T`.
    /// Note these default instances are treated as though
    /// they don't exist (i.e., `self.is_empty()` will return true).
    #[inline]
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }
}
impl<T, const N: usize> Default for Cache<T, N>
where
    [T; N]: Default,
{
    #[inline]
    fn default() -> Self {
        Self {
            vals: Default::default(),
            len: 0,
            next_head: 0,
        }
    }
}
#[cfg(test)]
mod tests {
    use super::Cache;
    #[test]
    fn test_len() {
        let mut c = Cache::<bool, 1>::new();
        assert_eq!(0, c.len());
        c.push(false);
        assert_eq!(1, c.len());
        c.push(false);
        assert_eq!(1, c.len());
    }
    #[test]
    fn test_is_empty() {
        let mut c = Cache::<bool, 1>::new();
        assert!(c.is_empty());
        c.push(false);
        assert!(!c.is_empty());
    }
    #[test]
    fn test_get() {
        let mut c = Cache::<bool, 4>::new();
        assert!(c.get(0).is_none());
        assert!(c.get(1).is_none());
        assert!(c.get(2).is_none());
        assert!(c.get(3).is_none());
        assert!(c.get(4).is_none());
        assert!(c.get(5).is_none());
        assert!(c.get(usize::MAX).is_none());
        c.push(true);
        assert!(c.get(0).unwrap());
        assert!(c.get(1).is_none());
        assert!(c.get(2).is_none());
        assert!(c.get(3).is_none());
        assert!(c.get(4).is_none());
        assert!(c.get(5).is_none());
        assert!(c.get(usize::MAX).is_none());
        c.push(false);
        assert!(!c.get(0).unwrap());
        assert!(c.get(1).unwrap());
        assert!(c.get(2).is_none());
        assert!(c.get(3).is_none());
        assert!(c.get(4).is_none());
        assert!(c.get(5).is_none());
        assert!(c.get(usize::MAX).is_none());
        c.push(false);
        assert!(!c.get(0).unwrap());
        assert!(!c.get(1).unwrap());
        assert!(c.get(2).unwrap());
        assert!(c.get(3).is_none());
        assert!(c.get(4).is_none());
        assert!(c.get(5).is_none());
        assert!(c.get(usize::MAX).is_none());
        c.push(true);
        assert!(c.get(0).unwrap());
        assert!(!c.get(1).unwrap());
        assert!(!c.get(2).unwrap());
        assert!(c.get(3).unwrap());
        assert!(c.get(4).is_none());
        assert!(c.get(5).is_none());
        assert!(c.get(usize::MAX).is_none());
        c.push(true);
        assert!(c.get(0).unwrap());
        assert!(c.get(1).unwrap());
        assert!(!c.get(2).unwrap());
        assert!(!c.get(3).unwrap());
        assert!(c.get(4).is_none());
        assert!(c.get(5).is_none());
        assert!(c.get(usize::MAX).is_none());
    }
    #[test]
    fn test_get_unsafe() {
        let mut c = Cache::<bool, 4>::new();
        assert!(!c.get_unchecked(0));
        assert!(!c.get_unchecked(1));
        assert!(!c.get_unchecked(2));
        assert!(!c.get_unchecked(3));
        assert!(!c.get_unchecked(4));
        c.push(true);
        assert!(c.get_unchecked(0));
        assert!(!c.get_unchecked(1));
        assert!(!c.get_unchecked(2));
        assert!(!c.get_unchecked(3));
        assert!(c.get_unchecked(4));
    }
    #[test]
    fn test_index() {
        let mut c = Cache::<bool, 4>::new();
        c.push(true);
        assert!(c[0]);
    }
    #[test]
    #[should_panic]
    fn test_index_panic() {
        let c = Cache::<bool, 4>::new();
        assert!(c[0]);
    }
    #[test]
    fn test_push() {
        let mut c = Cache::<bool, 4>::new();
        c.push(true);
        assert!(c[0]);
        c.push(true);
        assert!(c[0]);
        c.push(false);
        assert!(!c[0]);
        c.push(true);
        assert!(c[0]);
        c.push(false);
        assert!(!c[0]);
        c.push(false);
        assert!(!c[0]);
    }
    #[test]
    fn test_new() {
        _ = Cache::<bool, 0>::new();
        _ = Cache::<bool, 32>::new();
        _ = Cache::<bool, 31>::new();
    }
}