cloyster/ds/
stack.rs

1/// A simple lock-free stack
2use crate::prelude::*;
3use either::Either;
4use std::{ops::Deref, sync::atomic::Ordering::*};
5
6type CasResult<'g, T> = Either<Shared<'g, Node<T>>, (Shared<'g, Node<T>>, Owned<Node<T>>)>;
7
8#[derive(Debug)]
9pub struct Node<T: Send + 'static> {
10    pub(crate) inner: T,
11    pub(crate) next: Atomic<Node<T>>,
12}
13
14impl<T: Send + 'static> Deref for Node<T> {
15    type Target = T;
16    fn deref(&self) -> &T {
17        &self.inner
18    }
19}
20
21impl<T: Send + 'static> Drop for Node<T> {
22    fn drop(&mut self) {
23        unsafe {
24            let next = self.next.load(Relaxed, unprotected());
25            if !next.as_raw().is_null() {
26                drop(next.into_owned());
27            }
28        }
29    }
30}
31
32#[derive(Debug)]
33pub struct Stack<T: Send + 'static> {
34    head: Atomic<Node<T>>,
35}
36
37impl<T: Send + 'static> Default for Stack<T> {
38    fn default() -> Self {
39        Self { head: Atomic::null() }
40    }
41}
42
43impl<T: Send + 'static> Drop for Stack<T> {
44    fn drop(&mut self) {
45        unsafe {
46            let curr = self.head.load(Relaxed, unprotected());
47            if !curr.as_raw().is_null() {
48                drop(curr.into_owned());
49            }
50        }
51    }
52}
53
54/// `compare_and_set` is equivalent to `compare_exchange`
55/// with the following mapping for memory orderings:
56///
57/// Original | Success | Failure
58/// -------- | ------- | -------
59/// Relaxed  | Relaxed | Relaxed
60/// Acquire  | Acquire | Acquire
61/// Release  | Release | Relaxed
62/// AcqRel   | AcqRel  | Acquire
63/// SeqCst   | SeqCst  | SeqCst
64impl<T: Clone + Send + Sync + 'static> Stack<T> {
65    /// return current head pointer of the stack
66    pub fn head<'g>(&self, guard: &'g Guard) -> Shared<'g, Node<T>> {
67        self.head.load(Acquire, guard)
68    }
69
70    pub fn push(&self, inner: T) {
71        let node = Owned::new(Node { inner, next: Atomic::null() });
72
73        unsafe {
74            let node = node.into_shared(unprotected());
75
76            loop {
77                let head = self.head(unprotected());
78                node.deref().next.store(head, Release);
79                if self
80                    .head
81                    .compare_exchange(
82                        // compare
83                        head,
84                        node,
85                        // orderings
86                        Release,
87                        Relaxed,
88                        // guard
89                        unprotected(),
90                    )
91                    .is_ok()
92                {
93                    return
94                }
95            }
96        }
97    }
98
99    // cas operation
100    pub fn cas<'g>(
101        &self,
102        old: Shared<'g, Node<T>>,
103        new: Owned<Node<T>>,
104        guard: &'g Guard,
105    ) -> CasResult<'g, T> {
106        let res = self.head.compare_exchange(old, new, AcqRel, Acquire, guard);
107        match res {
108            Ok(success) => {
109                if !old.is_null() {
110                    unsafe {
111                        // reclaim old data
112                        guard.defer_destroy(old);
113                    }
114                }
115                // a success cas operation
116                Either::Left(success)
117            }
118            Err(e) => {
119                // a failure cas operation
120                Either::Right((e.current, e.new))
121            }
122        }
123    }
124
125    // compare and push
126    pub fn cap<'g>(
127        &self,
128        old: Shared<'_, Node<T>>,
129        mut node: Owned<Node<T>>,
130        guard: &'g Guard,
131    ) -> CasResult<'g, T> {
132        // pushed node always keeps the prev pointer
133        node.next = Atomic::from(old);
134        let res = self.head.compare_exchange(old, node, AcqRel, Acquire, guard);
135
136        match res {
137            Ok(success) => Either::Left(success),
138            Err(e) => {
139                // we want to set next to null to prevent
140                // the current shared head from being
141                // dropped when we drop this node.
142                let mut returned = e.new;
143                returned.next = Atomic::null();
144                Either::Right((e.current, returned))
145            }
146        }
147    }
148}
cloyster/ds/stack.rs

cloyster/ds/
stack.rs
