frame-alloc 0.1.0

extern crate std;

use crate::util::lifo::Lifo;
use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::{Arc, Mutex};
use std::thread;
use std::time::Duration;
use std::vec::Vec;

#[test]
fn push_pop_is_lifo() {
    let lifo = Lifo::<4>::new();
    let mut g = lifo.lock();
    assert_eq!(g.len(), 0);
    g.push(10);
    g.push(20);
    g.push(30);
    assert_eq!(g.len(), 3);
    assert_eq!(g.pop(), Some(30));
    assert_eq!(g.pop(), Some(20));
    assert_eq!(g.pop(), Some(10));
    assert_eq!(g.pop(), None, "popping past empty yields None");
    assert_eq!(g.len(), 0);
}

#[test]
fn is_full_tracks_capacity_boundary() {
    let lifo = Lifo::<3>::new();
    let mut g = lifo.lock();
    assert!(!g.is_full());
    g.push(1);
    g.push(2);
    assert!(!g.is_full(), "not full at len < CAP");
    g.push(3);
    assert!(g.is_full(), "full at exactly CAP");
    assert_eq!(g.len(), 3);
}

#[test]
fn push_slice_accepts_only_what_fits() {
    let lifo = Lifo::<4>::new();
    let mut g = lifo.lock();
    g.push(1);

    // src is larger than the remaining room: only three are accepted.
    let taken = g.push_slice(&[10, 20, 30, 40, 50]);
    assert_eq!(taken, 3, "push_slice caps at remaining capacity");
    assert!(g.is_full());
    assert_eq!(g.len(), 4);

    // Buffer is [1, 10, 20, 30] from the bottom, so LIFO pops them top-first.
    assert_eq!(g.pop(), Some(30));
    assert_eq!(g.pop(), Some(20));
    assert_eq!(g.pop(), Some(10));
    assert_eq!(g.pop(), Some(1));
}

#[test]
fn push_slice_into_full_takes_nothing() {
    let lifo = Lifo::<2>::new();
    let mut g = lifo.lock();
    g.push(1);
    g.push(2);
    assert_eq!(g.push_slice(&[3, 4]), 0, "no room, nothing accepted");
    assert_eq!(g.len(), 2);
}

#[test]
fn take_top_returns_oldest_first_and_frees_slots() {
    let lifo = Lifo::<8>::new();
    let mut g = lifo.lock();
    for v in [10, 20, 30, 40, 50, 60] {
        g.push(v);
    }

    // The two most-recently-pushed frames, returned oldest-first.
    let top = g.take_top(2);
    assert_eq!(top, &[50, 60]);
    // `top` is no longer used past here, so the guard is free to mutate again.

    assert_eq!(g.len(), 4, "take_top shrank the buffer by n");

    // The freed slots are reusable: a fresh push lands where 50 was and the
    // older frames below are untouched.
    g.push(99);
    assert_eq!(g.pop(), Some(99));
    assert_eq!(g.pop(), Some(40));
    assert_eq!(g.pop(), Some(30));
}

#[test]
fn take_top_zero_is_an_empty_slice() {
    let lifo = Lifo::<4>::new();
    let mut g = lifo.lock();
    g.push(1);
    g.push(2);
    assert_eq!(g.take_top(0), &[] as &[usize]);
    assert_eq!(g.len(), 2, "take_top(0) leaves the buffer alone");
}

/// A `Lifo` made shareable across threads. The wrapper asserts that `Lifo`
/// serialises all access to its cells through its own lock — the same invariant
/// the magazine/depot allocators rely on. If that fails, the tests below see torn
/// state (lost or doubled frames).
struct SharedLifo<const N: usize>(Lifo<N>);
// SAFETY: `Lifo`'s cells are only ever touched while its internal lock is held,
// so concurrent access is fully serialised.
unsafe impl<const N: usize> Sync for SharedLifo<N> {}

impl<const N: usize> SharedLifo<N> {
    fn new() -> Self {
        SharedLifo(Lifo::new())
    }
}

#[cfg_attr(audit, ignore = "audit builds are sequential-only")]
#[test]
fn guard_drop_releases_the_lock() {
    let shared = Arc::new(SharedLifo::<4>::new());
    let flag = Arc::new(AtomicBool::new(false));

    // Hold the lock via a live guard.
    let g = shared.0.lock();

    let s = shared.clone();
    let f = flag.clone();
    let handle = thread::spawn(move || {
        // Blocks until the main thread's guard is dropped.
        let mut g2 = s.0.lock();
        g2.push(7);
        f.store(true, Ordering::SeqCst);
    });

    thread::sleep(Duration::from_millis(50));
    assert!(
        !flag.load(Ordering::SeqCst),
        "another thread acquired the lock while a guard was still alive"
    );

    drop(g); // release happens in Drop
    handle.join().unwrap();
    assert!(
        flag.load(Ordering::SeqCst),
        "thread should proceed once the guard is dropped"
    );

    // The other thread's push is visible through the released-then-reacquired lock.
    let mut g3 = shared.0.lock();
    assert_eq!(g3.pop(), Some(7));
}

#[cfg_attr(audit, ignore = "audit builds are sequential-only")]
#[test]
fn concurrent_pushes_keep_every_frame() {
    const THREADS: usize = if cfg!(miri) { 4 } else { 8 };
    const PER: usize = if cfg!(miri) { 8 } else { 512 };
    const CAP: usize = THREADS * PER;

    let shared = Arc::new(SharedLifo::<CAP>::new());
    let mut handles = Vec::new();
    for t in 0..THREADS {
        let s = shared.clone();
        handles.push(thread::spawn(move || {
            for i in 0..PER {
                // Every push across all threads uses a distinct, non-zero value.
                let v = t * PER + i + 1;
                s.0.lock().push(v);
            }
        }));
    }
    for h in handles {
        h.join().unwrap();
    }

    let mut seen = Vec::new();
    let mut g = shared.0.lock();
    assert_eq!(g.len(), CAP, "a concurrent push was lost");
    while let Some(v) = g.pop() {
        seen.push(v);
    }
    seen.sort_unstable();
    let expected: Vec<usize> = (1..=CAP).collect();
    assert_eq!(
        seen, expected,
        "a concurrent push was lost or clobbered another"
    );
}

#[cfg_attr(audit, ignore = "audit builds are sequential-only")]
#[test]
fn concurrent_pops_hand_out_each_frame_once() {
    const THREADS: usize = if cfg!(miri) { 4 } else { 8 };
    const CAP: usize = if cfg!(miri) { 32 } else { 4096 };

    let shared = Arc::new(SharedLifo::<CAP>::new());
    {
        let mut g = shared.0.lock();
        for v in 1..=CAP {
            g.push(v);
        }
    }

    let collected = Arc::new(Mutex::new(Vec::new()));
    let mut handles = Vec::new();
    for _ in 0..THREADS {
        let s = shared.clone();
        let c = collected.clone();
        handles.push(thread::spawn(move || {
            let mut local = Vec::new();
            loop {
                let popped = s.0.lock().pop();
                match popped {
                    Some(v) => local.push(v),
                    None => break,
                }
            }
            c.lock().unwrap().extend(local);
        }));
    }
    for h in handles {
        h.join().unwrap();
    }

    let mut all = Arc::try_unwrap(collected).unwrap().into_inner().unwrap();
    all.sort_unstable();
    let expected: Vec<usize> = (1..=CAP).collect();
    assert_eq!(
        all, expected,
        "a frame was popped twice or lost under contention"
    );
    assert_eq!(shared.0.lock().pop(), None, "lifo should be drained");
}