rust / expert
Snippet
Implementing Lock-Free Concurrent Stack Insertion Using Atomic Compare-Exchange
Lock-free structures rely on atomic CAS (Compare-And-Swap) operations. This concurrent stack uses compare_exchange_weak inside a loop to update the stack's head pointer without locking, ensuring safe data visibility across threads.
snippet.rs
rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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,}}}}
Breakdown
1
Box::into_raw(Box::new(...))
Converts a safe Box into a raw pointer to prevent automatic cleanup and allow manual raw memory manipulation.
2
self.head.compare_exchange_weak(current, new_node, Ordering::Release, Ordering::Relaxed)
Atomically updates head if it matches current, using Release ordering to publish the contents of the new node.
3
Err(actual) => current = actual,
Updates the current head pointer with the actual value returned on CAS failure, preparing for retry.