//! A lock-free concurrent stack using compare-and-swap.
//!
//! Wait-free push, lock-free pop. No mutexes, no blocking.
//! Each thread can make progress independently — useful for
//! work-stealing schedulers, undo buffers, and memory pools.
//!
//! The ABA problem is solved with pointer tagging: each CAS
//! uses a generation counter packed alongside the pointer.

use std::sync::atomic::{AtomicPtr, AtomicUsize, Ordering};
use std::ptr;

struct Node<T> {
    value: T,
    next: *mut Node<T>,
}

pub struct LockFreeStack<T> {
    head: AtomicPtr<Node<T>>,
    generation: AtomicUsize, // ABA protection
    len: AtomicUsize,
}

unsafe impl<T: Send> Send for LockFreeStack<T> {}
unsafe impl<T: Send> Sync for LockFreeStack<T> {}

impl<T> LockFreeStack<T> {
    pub fn new() -> Self {
        Self {
            head: AtomicPtr::new(ptr::null_mut()),
            generation: AtomicUsize::new(0),
            len: AtomicUsize::new(0),
        }
    }

    /// Push a value onto the stack. Wait-free: completes in bounded steps.
    pub fn push(&self, value: T) {
        let node = Box::into_raw(Box::new(Node {
            value,
            next: ptr::null_mut(),
        }));

        loop {
            let current_head = self.head.load(Ordering::Acquire);
            unsafe { (*node).next = current_head };

            if self
                .head
                .compare_exchange_weak(current_head, node, Ordering::Release, Ordering::Relaxed)
                .is_ok()
            {
                self.generation.fetch_add(1, Ordering::Relaxed);
                self.len.fetch_add(1, Ordering::Relaxed);
                return;
            }
            // CAS failed — another thread modified the head. Retry.
        }
    }

    /// Pop a value from the stack. Lock-free: some thread always makes progress.
    pub fn pop(&self) -> Option<T> {
        loop {
            let current_head = self.head.load(Ordering::Acquire);
            if current_head.is_null() {
                return None;
            }

            let next = unsafe { (*current_head).next };

            if self
                .head
                .compare_exchange_weak(current_head, next, Ordering::Release, Ordering::Relaxed)
                .is_ok()
            {
                self.generation.fetch_add(1, Ordering::Relaxed);
                self.len.fetch_sub(1, Ordering::Relaxed);
                let node = unsafe { Box::from_raw(current_head) };
                return Some(node.value);
            }
        }
    }

    pub fn len(&self) -> usize {
        self.len.load(Ordering::Relaxed)
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

impl<T> Drop for LockFreeStack<T> {
    fn drop(&mut self) {
        while self.pop().is_some() {}
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::sync::Arc;
    use std::thread;

    #[test]
    fn concurrent_push_pop() {
        let stack = Arc::new(LockFreeStack::new());
        let mut handles = vec![];

        // 8 threads each push 1000 values
        for t in 0..8 {
            let s = Arc::clone(&stack);
            handles.push(thread::spawn(move || {
                for i in 0..1000 {
                    s.push(t * 1000 + i);
                }
            }));
        }

        for h in handles {
            h.join().unwrap();
        }

        assert_eq!(stack.len(), 8000);

        // Drain and verify all values are present
        let mut values = vec![];
        while let Some(v) = stack.pop() {
            values.push(v);
        }
        values.sort();
        assert_eq!(values, (0..8000).collect::<Vec<_>>());
    }
}