blob: 1dbd6b0f3a320288a956031030fc5ad2e9bb63d1 [file] [log] [blame]
extern crate crossbeam_epoch as epoch;
extern crate crossbeam_utils as utils;
use std::mem::ManuallyDrop;
use std::ptr;
use std::sync::atomic::Ordering::{Acquire, Relaxed, Release};
use epoch::{Atomic, Owned};
use utils::thread::scope;
/// Treiber's lock-free stack.
///
/// Usable with any number of producers and consumers.
#[derive(Debug)]
pub struct TreiberStack<T> {
head: Atomic<Node<T>>,
}
#[derive(Debug)]
struct Node<T> {
data: ManuallyDrop<T>,
next: Atomic<Node<T>>,
}
impl<T> TreiberStack<T> {
/// Creates a new, empty stack.
pub fn new() -> TreiberStack<T> {
TreiberStack {
head: Atomic::null(),
}
}
/// Pushes a value on top of the stack.
pub fn push(&self, t: T) {
let mut n = Owned::new(Node {
data: ManuallyDrop::new(t),
next: Atomic::null(),
});
let guard = epoch::pin();
loop {
let head = self.head.load(Relaxed, &guard);
n.next.store(head, Relaxed);
match self.head.compare_and_set(head, n, Release, &guard) {
Ok(_) => break,
Err(e) => n = e.new,
}
}
}
/// Attempts to pop the top element from the stack.
///
/// Returns `None` if the stack is empty.
pub fn pop(&self) -> Option<T> {
let guard = epoch::pin();
loop {
let head = self.head.load(Acquire, &guard);
match unsafe { head.as_ref() } {
Some(h) => {
let next = h.next.load(Relaxed, &guard);
if self
.head
.compare_and_set(head, next, Release, &guard)
.is_ok()
{
unsafe {
guard.defer_destroy(head);
return Some(ManuallyDrop::into_inner(ptr::read(&(*h).data)));
}
}
}
None => return None,
}
}
}
/// Returns `true` if the stack is empty.
pub fn is_empty(&self) -> bool {
let guard = epoch::pin();
self.head.load(Acquire, &guard).is_null()
}
}
impl<T> Drop for TreiberStack<T> {
fn drop(&mut self) {
while self.pop().is_some() {}
}
}
fn main() {
let stack = TreiberStack::new();
scope(|scope| {
for _ in 0..10 {
scope.spawn(|_| {
for i in 0..10_000 {
stack.push(i);
assert!(stack.pop().is_some());
}
});
}
}).unwrap();
assert!(stack.pop().is_none());
}