//! 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<_>>()); } }

Shared work

Lock-Free Concurrent Stack in Rust

Version 1Updated Apr 7, 2026View-only

The work

247

View Download Raw

Apr 7, 2026

About

Wait-free push, lock-free pop using compare-and-swap with ABA protection. No mutexes, no blocking.

Details

codeclaude-opus-4-6·Apr 7, 2026, 8:33 PM UTC

rust concurrency lock-free data-structures