frame-alloc 0.1.0

use crate::util::lock::Lock;
use crate::{InterruptControl, NoInterruptControl};
use core::cell::UnsafeCell;

/// A bounded LIFO cache of base-frame addresses.
///
/// The `len`/`buf` cells are only ever touched while the embedded `lock` is held.
/// [`Lifo::lock`] acquires the lock and hands back a [`LifoGuard`]; every read or
/// write goes through that guard, which keeps the single `unsafe` cell-access
/// pattern in one place. Each `Lifo` is meant to live behind a
/// [`CachePadded`](crate::util::cache::CachePadded) so neighbouring caches never share a
/// cache line.
pub(crate) struct Lifo<const N: usize, I: InterruptControl = NoInterruptControl> {
    lock: Lock<I>,
    len: UnsafeCell<usize>,
    buf: UnsafeCell<[usize; N]>,
}

impl<const N: usize, I: InterruptControl> Lifo<N, I> {
    pub(crate) const fn new() -> Self {
        Self {
            lock: Lock::new(),
            len: UnsafeCell::new(0),
            buf: UnsafeCell::new([0; N]),
        }
    }

    /// Acquire the lock, returning a guard with exclusive access to the buffer.
    /// The lock is released when the guard is dropped.
    #[inline]
    pub(crate) fn lock(&self) -> LifoGuard<'_, N, I> {
        self.lock.acquire();
        LifoGuard { lifo: self }
    }
}

/// RAII-scoped exclusive access to a [`Lifo`]'s contents. Holding one proves the
/// lock is held, so the buffer accesses below are sound; dropping it releases the
/// lock, which means every early return frees it automatically.
pub(crate) struct LifoGuard<'a, const N: usize, I: InterruptControl> {
    lifo: &'a Lifo<N, I>,
}

impl<const N: usize, I: InterruptControl> LifoGuard<'_, N, I> {
    /// Frames currently cached.
    #[inline]
    pub(crate) fn len(&self) -> usize {
        // SAFETY: the guard proves the lock is held, so `len` is ours alone.
        unsafe { *self.lifo.len.get() }
    }

    /// `true` once the buffer is at capacity.
    #[inline]
    pub(crate) fn is_full(&self) -> bool {
        self.len() >= N
    }

    /// Pop the most-recently-pushed frame, or `None` if empty.
    #[inline]
    pub(crate) fn pop(&mut self) -> Option<usize> {
        // SAFETY: the guard proves the lock is held.
        let len = unsafe { &mut *self.lifo.len.get() };
        if *len == 0 {
            return None;
        }
        *len -= 1;
        // SAFETY: same; `*len < N` so the index is in bounds.
        Some(unsafe { (*self.lifo.buf.get())[*len] })
    }

    /// Push one frame. The caller must ensure there is room (`!is_full()`).
    #[inline]
    pub(crate) fn push(&mut self, addr: usize) {
        // SAFETY: the guard proves the lock is held.
        let len = unsafe { &mut *self.lifo.len.get() };
        debug_assert!(*len < N, "push into a full Lifo");
        // SAFETY: same; the caller guarantees `*len < N`, so the index is in bounds.
        unsafe { (*self.lifo.buf.get())[*len] = addr };
        *len += 1;
    }

    /// Push as many of `src` as fit, returning the number accepted.
    #[inline]
    pub(crate) fn push_slice(&mut self, src: &[usize]) -> usize {
        // SAFETY: the guard proves the lock is held.
        let len = unsafe { &mut *self.lifo.len.get() };
        let buf = unsafe { &mut *self.lifo.buf.get() };
        let take = (N - *len).min(src.len());
        for &addr in src.iter().take(take) {
            buf[*len] = addr;
            *len += 1;
        }
        take
    }

    /// Remove the top `n` frames and return them as a slice (oldest first). The
    /// caller must ensure `n <= len()`.
    #[inline]
    pub(crate) fn take_top(&mut self, n: usize) -> &[usize] {
        // SAFETY: the guard proves the lock is held.
        let len = unsafe { &mut *self.lifo.len.get() };
        debug_assert!(n <= *len, "take_top past len");
        let start = *len - n;
        *len = start;
        // SAFETY: same; slots [start, start + n) keep their values until a later
        // push overwrites them, which cannot happen before this borrow ends.
        let buf = unsafe { &*self.lifo.buf.get() };
        &buf[start..start + n]
    }
}

impl<const N: usize, I: InterruptControl> Drop for LifoGuard<'_, N, I> {
    #[inline]
    fn drop(&mut self) {
        self.lifo.lock.release();
    }
}