Jakub Kotur | fc1672b | 2020-12-21 17:28:14 +0100 | [diff] [blame^] | 1 | use std::mem::ManuallyDrop; |
| 2 | use std::ptr; |
| 3 | use std::sync::atomic::Ordering::{Acquire, Relaxed, Release}; |
| 4 | |
| 5 | use crossbeam_epoch::{self as epoch, Atomic, Owned}; |
| 6 | use crossbeam_utils::thread::scope; |
| 7 | |
| 8 | /// Treiber's lock-free stack. |
| 9 | /// |
| 10 | /// Usable with any number of producers and consumers. |
| 11 | #[derive(Debug)] |
| 12 | pub struct TreiberStack<T> { |
| 13 | head: Atomic<Node<T>>, |
| 14 | } |
| 15 | |
| 16 | #[derive(Debug)] |
| 17 | struct Node<T> { |
| 18 | data: ManuallyDrop<T>, |
| 19 | next: Atomic<Node<T>>, |
| 20 | } |
| 21 | |
| 22 | impl<T> TreiberStack<T> { |
| 23 | /// Creates a new, empty stack. |
| 24 | pub fn new() -> TreiberStack<T> { |
| 25 | TreiberStack { |
| 26 | head: Atomic::null(), |
| 27 | } |
| 28 | } |
| 29 | |
| 30 | /// Pushes a value on top of the stack. |
| 31 | pub fn push(&self, t: T) { |
| 32 | let mut n = Owned::new(Node { |
| 33 | data: ManuallyDrop::new(t), |
| 34 | next: Atomic::null(), |
| 35 | }); |
| 36 | |
| 37 | let guard = epoch::pin(); |
| 38 | |
| 39 | loop { |
| 40 | let head = self.head.load(Relaxed, &guard); |
| 41 | n.next.store(head, Relaxed); |
| 42 | |
| 43 | match self.head.compare_and_set(head, n, Release, &guard) { |
| 44 | Ok(_) => break, |
| 45 | Err(e) => n = e.new, |
| 46 | } |
| 47 | } |
| 48 | } |
| 49 | |
| 50 | /// Attempts to pop the top element from the stack. |
| 51 | /// |
| 52 | /// Returns `None` if the stack is empty. |
| 53 | pub fn pop(&self) -> Option<T> { |
| 54 | let guard = epoch::pin(); |
| 55 | loop { |
| 56 | let head = self.head.load(Acquire, &guard); |
| 57 | |
| 58 | match unsafe { head.as_ref() } { |
| 59 | Some(h) => { |
| 60 | let next = h.next.load(Relaxed, &guard); |
| 61 | |
| 62 | if self |
| 63 | .head |
| 64 | .compare_and_set(head, next, Relaxed, &guard) |
| 65 | .is_ok() |
| 66 | { |
| 67 | unsafe { |
| 68 | guard.defer_destroy(head); |
| 69 | return Some(ManuallyDrop::into_inner(ptr::read(&(*h).data))); |
| 70 | } |
| 71 | } |
| 72 | } |
| 73 | None => return None, |
| 74 | } |
| 75 | } |
| 76 | } |
| 77 | |
| 78 | /// Returns `true` if the stack is empty. |
| 79 | pub fn is_empty(&self) -> bool { |
| 80 | let guard = epoch::pin(); |
| 81 | self.head.load(Acquire, &guard).is_null() |
| 82 | } |
| 83 | } |
| 84 | |
| 85 | impl<T> Drop for TreiberStack<T> { |
| 86 | fn drop(&mut self) { |
| 87 | while self.pop().is_some() {} |
| 88 | } |
| 89 | } |
| 90 | |
| 91 | fn main() { |
| 92 | let stack = TreiberStack::new(); |
| 93 | |
| 94 | scope(|scope| { |
| 95 | for _ in 0..10 { |
| 96 | scope.spawn(|_| { |
| 97 | for i in 0..10_000 { |
| 98 | stack.push(i); |
| 99 | assert!(stack.pop().is_some()); |
| 100 | } |
| 101 | }); |
| 102 | } |
| 103 | }) |
| 104 | .unwrap(); |
| 105 | |
| 106 | assert!(stack.pop().is_none()); |
| 107 | } |