Skip to content

Instantly share code, notes, and snippets.

@ttldtor
Last active March 29, 2024 18:04
Show Gist options
  • Save ttldtor/4a79bb2ba4f2732a2a354d02d8f29944 to your computer and use it in GitHub Desktop.
Save ttldtor/4a79bb2ba4f2732a2a354d02d8f29944 to your computer and use it in GitHub Desktop.
Lock-free LinkedList in Rust
use std::sync::{Arc, atomic::{AtomicPtr, Ordering}};
use std::ptr;
struct Node<T> {
data: T,
next: AtomicPtr<Node<T>>,
}
pub struct LockFreeLinkedList<T> {
head: AtomicPtr<Node<T>>,
}
impl<T> LockFreeLinkedList<T> {
pub fn new() -> Self {
LockFreeLinkedList {
head: AtomicPtr::new(ptr::null_mut()),
}
}
pub fn push(&self, data: T) {
let new_node = Box::new(Node {
data,
next: AtomicPtr::new(ptr::null_mut()),
});
let new_node_ptr = Box::into_raw(new_node);
loop {
let current_head = self.head.load(Ordering::Relaxed);
unsafe {
(*new_node_ptr).next.store(current_head, Ordering::Relaxed);
}
if self.head.compare_exchange(current_head, new_node_ptr, Ordering::AcqRel, Ordering::Relaxed).is_ok() {
break;
}
}
}
pub fn pop(&self) -> Option<T> {
loop {
let current_head = self.head.load(Ordering::Acquire);
if current_head.is_null() {
return None;
}
let next_node = unsafe { (*current_head).next.load(Ordering::Acquire) };
if self.head.compare_exchange(current_head, next_node, Ordering::AcqRel, Ordering::Relaxed).is_ok() {
unsafe {
let boxed_node = Box::from_raw(current_head);
return Some(boxed_node.data);
}
}
}
}
pub fn is_empty(&self) -> bool {
self.head.load(Ordering::Acquire).is_null()
}
pub fn into_iter(&self) -> impl Iterator<Item = T> + '_ {
std::iter::from_fn(move || self.pop())
}
}
fn main() {
let list = Arc::new(LockFreeLinkedList::new());
let list_ref = Arc::clone(&list);
let handle = std::thread::spawn(move || {
for i in 0..10 {
list_ref.push(i); // используем копию Arc
}
});
handle.join().unwrap();
for value in list.into_iter() {
println!("Popped value: {}", value);
}
}
Running lfll.exe
Popped value: 9
Popped value: 8
Popped value: 7
Popped value: 6
Popped value: 5
Popped value: 4
Popped value: 3
Popped value: 2
Popped value: 1
Popped value: 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment