Last active
March 29, 2024 18:04
-
-
Save ttldtor/4a79bb2ba4f2732a2a354d02d8f29944 to your computer and use it in GitHub Desktop.
Lock-free LinkedList in Rust
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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