urcu/collections/stack/
container.rs

1use std::marker::PhantomData;
2use std::ops::Deref;
3use std::ptr::NonNull;
4use std::sync::Arc;
5
6use crate::collections::stack::iterator::{Iter, IterRef};
7use crate::collections::stack::raw::{RawNode, RawStack};
8use crate::collections::stack::reference::Ref;
9use crate::rcu::default::RcuDefaultFlavor;
10use crate::rcu::flavor::RcuFlavor;
11use crate::rcu::guard::RcuGuard;
12use crate::utility::*;
13
14/// Defines a RCU wait-free stack.
15///
16/// This stack supports multiple concurrents readers and writers. It is guaranteed to
17/// never block on a call.
18///
19/// # Limitations
20///
21/// ##### Mutable References
22///
23/// Because there might always be readers borrowing a node's data, it is impossible
24/// to get a mutable references to the data inside the stack. You should design the
25/// type stored in the stack with [interior mutabillity] that can be shared between
26/// threads.
27///
28/// [interior mutabillity]: https://doc.rust-lang.org/reference/interior-mutability.html
29///
30/// ##### List Length
31///
32/// Because a writer might concurrently modify the stack, the amount of node might change
33/// at any moment. To prevent user error (e.g. allocate an array for each node), there is
34/// no `.len()` method.
35///
36/// # Safety
37///
38/// It is safe to send an `Arc<RcuStack<T>>` to a non-registered RCU thread. A non-registered
39/// thread may drop an `RcuStack<T>` without calling any RCU primitives since lifetime rules
40/// prevent any other thread from accessing a RCU reference.
41pub struct RcuStack<T, F = RcuDefaultFlavor> {
42    raw: RawStack<T>,
43    _unsend: PhantomUnsend<(T, F)>,
44    _unsync: PhantomUnsync<(T, F)>,
45}
46
47impl<T, F> RcuStack<T, F>
48where
49    F: RcuFlavor,
50{
51    /// Creates a new RCU stack.
52    pub fn new() -> Arc<Self> {
53        Arc::new(RcuStack {
54            // SAFETY: All node are pop'ed before dropping.
55            raw: unsafe { RawStack::new() },
56            _unsend: PhantomData,
57            _unsync: PhantomData,
58        })
59    }
60
61    /// Adds an element to the top of the stack.
62    pub fn push(&self, data: T) {
63        let node = RawNode::new(data);
64
65        self.raw.push(node);
66    }
67
68    /// Removes an element from the top of the stack.
69    pub fn pop<G>(&self, guard: &G) -> Option<Ref<T, F>>
70    where
71        T: Send,
72        G: RcuGuard<Flavor = F>,
73    {
74        let _ = guard;
75
76        // SAFETY: The RCU critical section is enforced.
77        // SAFETY: RCU grace period is enforced.
78        let node = unsafe { self.raw.pop() };
79
80        NonNull::new(node).map(Ref::new)
81    }
82
83    /// Removes all elements from the stack.
84    pub fn pop_all<G>(&self, _guard: &G) -> IterRef<T, F>
85    where
86        T: Send,
87        G: RcuGuard<Flavor = F>,
88    {
89        // SAFETY: The RCU critical section is enforced.
90        // SAFETY: RCU grace period is enforced.
91        IterRef::new(unsafe { self.raw.pop_all() })
92    }
93
94    /// Returns a reference to the element on top of the stack.
95    pub fn peek<'me, 'guard, G>(&'me self, _guard: &'guard G) -> Option<&'guard T>
96    where
97        'me: 'guard,
98        G: RcuGuard<Flavor = F>,
99    {
100        // SAFETY: The RCU critical section is enforced.
101        let node = unsafe { self.raw.head() };
102
103        // SAFETY: The pointer can be safely converted to reference.
104        unsafe { node.as_ref() }.map(|node| node.deref())
105    }
106
107    /// Returns an iterator over the stack.
108    ///
109    /// The iterator yields all items from top to bottom.
110    pub fn iter<'me, 'guard, G>(&'me self, guard: &'guard G) -> Iter<'guard, T, G>
111    where
112        'me: 'guard,
113        G: RcuGuard<Flavor = F>,
114    {
115        // SAFETY: The RCU critical section is enforced.
116        Iter::new(unsafe { self.raw.iter() }, guard)
117    }
118
119    /// Returns `true` if there is no node in the stack.
120    pub fn is_empty(&self) -> bool {
121        self.raw.empty()
122    }
123}
124
125/// #### Safety
126///
127/// An [`RcuStack`] can be used to send `T` to another thread.
128unsafe impl<T, F> Send for RcuStack<T, F>
129where
130    T: Send,
131    F: RcuFlavor,
132{
133}
134
135/// #### Safety
136///
137/// An [`RcuStack`] can be used to share `T` between threads.
138unsafe impl<T, F> Sync for RcuStack<T, F>
139where
140    T: Sync,
141    F: RcuFlavor,
142{
143}
144
145impl<T, F> Drop for RcuStack<T, F> {
146    fn drop(&mut self) {
147        // SAFETY: The RCU read-lock is not needed there are no other writers.
148        // SAFETY: The RCU grace period is not needed there are no other readers.
149        let mut iter = unsafe { self.raw.pop_all() };
150
151        // SAFETY: The RCU read-lock is not needed there are no other writers.
152        while let Some(ptr) = unsafe { iter.next().as_mut() } {
153            // SAFETY: The pointer is always non-null and valid.
154            drop(unsafe { Box::from_raw(ptr) });
155        }
156    }
157}
urcu/collections/stack/container.rs

urcu/collections/stack/
container.rs
