2 files changed, 179 insertions, 0 deletions
diff --git a/third_party/rust/crossbeam-epoch-0.8.0/examples/sanitize.rs b/third_party/rust/crossbeam-epoch-0.8.0/examples/sanitize.rs
new file mode 100644
index 0000000000..12f1263122
--- /dev/null
+++ b/third_party/rust/crossbeam-epoch-0.8.0/examples/sanitize.rs
@@ -0,0 +1,69 @@
+extern crate crossbeam_epoch as epoch;
+extern crate rand;
+
+use std::sync::atomic::AtomicUsize;
+use std::sync::atomic::Ordering::{AcqRel, Acquire, Relaxed};
+use std::sync::Arc;
+use std::thread;
+use std::time::{Duration, Instant};
+
+use epoch::{Atomic, Collector, LocalHandle, Owned, Shared};
+use rand::Rng;
+
+fn worker(a: Arc<Atomic<AtomicUsize>>, handle: LocalHandle) -> usize {
+    let mut rng = rand::thread_rng();
+    let mut sum = 0;
+
+    if rng.gen() {
+        thread::sleep(Duration::from_millis(1));
+    }
+    let timeout = Duration::from_millis(rng.gen_range(0, 10));
+    let now = Instant::now();
+
+    while now.elapsed() < timeout {
+        for _ in 0..100 {
+            let guard = &handle.pin();
+            guard.flush();
+
+            let val = if rng.gen() {
+                let p = a.swap(Owned::new(AtomicUsize::new(sum)), AcqRel, guard);
+                unsafe {
+                    guard.defer_destroy(p);
+                    guard.flush();
+                    p.deref().load(Relaxed)
+                }
+            } else {
+                let p = a.load(Acquire, guard);
+                unsafe { p.deref().fetch_add(sum, Relaxed) }
+            };
+
+            sum = sum.wrapping_add(val);
+        }
+    }
+
+    sum
+}
+
+fn main() {
+    for _ in 0..100 {
+        let collector = Collector::new();
+        let a = Arc::new(Atomic::new(AtomicUsize::new(777)));
+
+        let threads = (0..16)
+            .map(|_| {
+                let a = a.clone();
+                let c = collector.clone();
+                thread::spawn(move || worker(a, c.register()))
+            })
+            .collect::<Vec<_>>();
+
+        for t in threads {
+            t.join().unwrap();
+        }
+
+        unsafe {
+            a.swap(Shared::null(), AcqRel, epoch::unprotected())
+                .into_owned();
+        }
+    }
+}
diff --git a/third_party/rust/crossbeam-epoch-0.8.0/examples/treiber_stack.rs b/third_party/rust/crossbeam-epoch-0.8.0/examples/treiber_stack.rs
new file mode 100644
index 0000000000..cc15c0dbd6
--- /dev/null
+++ b/third_party/rust/crossbeam-epoch-0.8.0/examples/treiber_stack.rs
@@ -0,0 +1,110 @@
+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());
+}