cs431_homework/elim_stack/
base.rs

1use core::marker::PhantomData;
2use core::mem::ManuallyDrop;
3use core::ops::Deref;
4use std::time;
5
6use crossbeam_epoch::{Atomic, Guard, Owned, pin};
7use rand::{self, Rng};
8
9pub(crate) const ELIM_SIZE: usize = 16;
10pub(crate) const ELIM_DELAY: time::Duration = time::Duration::from_millis(10);
11
12#[inline]
13pub(crate) fn get_random_elim_index() -> usize {
14    (rand::rng().random::<u64>() as usize) % ELIM_SIZE
15}
16
17/// Concurrent stack types.
18pub trait Stack<T>: Default {
19    /// Push request type.
20    type PushReq: From<T> + Deref<Target = ManuallyDrop<T>>;
21
22    /// Tries to push a value to the stack.
23    ///
24    /// Returns `Ok(())` if the push request is served; `Err(req)` is CAS failed.
25    fn try_push(
26        &self,
27        req: Owned<Self::PushReq>,
28        guard: &Guard,
29    ) -> Result<(), Owned<Self::PushReq>>;
30
31    /// Tries to pop a value from the stack.
32    ///
33    /// Returns `Ok(Some(v))` if `v` is popped; `Ok(None)` if the stack is empty; and `Err(())` if
34    /// CAS failed.
35    fn try_pop(&self, guard: &Guard) -> Result<Option<T>, ()>;
36
37    /// Returns `true` if the stack is empty.
38    fn is_empty(&self, guard: &Guard) -> bool;
39
40    /// Pushes a value to the stack.
41    fn push(&self, t: T) {
42        let mut req = Owned::new(t.into());
43        let guard = pin();
44        while let Err(r) = self.try_push(req, &guard) {
45            req = r;
46        }
47    }
48
49    /// Pops a value from the stack.
50    ///
51    /// Returns `Some(v)` if `v` is popped; `None` if the stack is empty.
52    fn pop(&self) -> Option<T> {
53        let guard = pin();
54        loop {
55            if let Ok(result) = self.try_pop(&guard) {
56                return result;
57            }
58        }
59    }
60}
61
62#[derive(Debug)]
63pub struct ElimStack<T, S: Stack<T>> {
64    pub(crate) inner: S,
65    // slot tags:
66    // - 0: no request
67    // - 1: push request
68    // - 2: pop request
69    // - 3: request acknowledged
70    pub(crate) slots: [Atomic<S::PushReq>; ELIM_SIZE],
71}
72
73impl<T, S: Stack<T>> Default for ElimStack<T, S> {
74    fn default() -> Self {
75        Self {
76            inner: Default::default(),
77            slots: Default::default(),
78        }
79    }
80}
cs431_homework/elim_stack/base.rs

cs431_homework/elim_stack/
base.rs
