Implementing Lock-Free Concurrent Stack Insertion Using Atomic Compare-Exchange

use std::sync::atomic::{AtomicPtr, Ordering};
use std::ptr;
 
struct Node<T> {
    data: T,
    next: *mut Node<T>,
}
 
pub struct LockFreeStack<T> {
    head: AtomicPtr<Node<T>>,
}
 
impl<T> LockFreeStack<T> {
    pub fn new() -> Self {
        Self { head: AtomicPtr::new(ptr::null_mut()) }
    } 
 
    pub fn push(&self, data: T) {
        let new_node = Box::into_raw(Box::new(Node {
            data,
            next: ptr::null_mut(),
        }));
        let mut current = self.head.load(Ordering::Relaxed);
        loop {
            unsafe { (*new_node).next = current; }
            match self.head.compare_exchange_weak(
                current,
                new_node,
                Ordering::Release,
                Ordering::Relaxed,
            ) {
                Ok(_) => break,
                Err(actual) => current = actual,
            }
        }
    }
}