urcu/collections/hashmap/
container.rs

1use std::hash::Hash;
2use std::ptr::NonNull;
3use std::sync::Arc;
4
5use anyhow::Result;
6
7use crate::collections::hashmap::iterator::Iter;
8use crate::collections::hashmap::raw::RawMap;
9use crate::collections::hashmap::reference::Ref;
10use crate::rcu::default::RcuDefaultFlavor;
11use crate::rcu::flavor::RcuFlavor;
12use crate::{RcuGuard, RcuReadContext, RcuRef};
13
14/// Defines a RCU lock-free hashmap.
15///
16/// This hashmap supports multiple concurrents readers and writers. It is guaranteed
17/// to 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/// # Safety
31///
32/// It is safe to send an `Arc<RcuHashMap<T>>` to a non-registered RCU thread. A
33/// non-registered thread may drop an `RcuHashMap<T>` without calling any RCU
34/// primitives since lifetime rules prevent any other thread from accessing an
35/// RCU reference.
36pub struct RcuHashMap<K, V, F = RcuDefaultFlavor>(RawMap<K, V, F>)
37where
38    K: Send + 'static,
39    V: Send + 'static,
40    F: RcuFlavor + 'static;
41
42impl<K, V, F> RcuHashMap<K, V, F>
43where
44    K: Send,
45    V: Send,
46    F: RcuFlavor,
47{
48    /// Creates a new RCU hashmap.
49    pub fn new() -> Result<Arc<Self>> {
50        Ok(Arc::new(Self(RawMap::new()?)))
51    }
52
53    /// Inserts a key-value pair in the hashmap.
54    ///
55    /// If the hashmap did not have this key present, [`None`] is returned.
56    pub fn insert<G>(&self, key: K, value: V, guard: &G) -> Option<Ref<K, V, F>>
57    where
58        K: Send + Eq + Hash,
59        V: Send,
60        G: RcuGuard<Flavor = F>,
61    {
62        let _ = guard;
63
64        // SAFETY: The read-side RCU lock is taken.
65        // SAFETY: The RCU grace period is enforced through the RcuRef.
66        let node = unsafe { self.0.add_replace(key, value) };
67
68        NonNull::new(node).map(Ref::new)
69    }
70
71    /// Returns `true` if the hashmap contains a value for the specified key.
72    pub fn contains<G>(&self, key: &K, guard: &G) -> bool
73    where
74        K: Eq + Hash,
75        G: RcuGuard<Flavor = F>,
76    {
77        let _ = guard;
78
79        // SAFETY: The RCU read-side lock is taken.
80        let mut iter = unsafe { self.0.lookup(key) };
81
82        !iter.get().is_null()
83    }
84
85    /// Returns a reference to the value corresponding to the key.
86    pub fn get<'me, 'guard, G>(&'me self, key: &K, _guard: &'guard G) -> Option<&'guard V>
87    where
88        'me: 'guard,
89        K: Eq + Hash,
90        G: RcuGuard<Flavor = F>,
91    {
92        // SAFETY: The RCU read-side lock is taken.
93        let mut iter = unsafe { self.0.lookup(key) };
94
95        // SAFETY: The node pointer is convertible to a reference is non-null.
96        unsafe { iter.get().as_ref() }.map(|node| &node.value)
97    }
98
99    /// Removes a key from the hashmap, returning the key-value pair if successful.
100    pub fn remove<G>(&self, key: &K, guard: &G) -> Option<Ref<K, V, F>>
101    where
102        K: Send + Eq + Hash,
103        V: Send,
104        G: RcuGuard<Flavor = F>,
105    {
106        let _ = guard;
107
108        // SAFETY: The RCU read-side lock is taken.
109        let mut iter = unsafe { self.0.lookup(key) };
110
111        // SAFETY: The node pointer is convertible to a reference is non-null.
112        let node = match unsafe { iter.get().as_ref() } {
113            None => std::ptr::null_mut(),
114            Some(node) => {
115                // SAFETY: The RCU read-side lock is taken.
116                // SAFETY: The RCU grace period is enforced through RcuRef.
117                unsafe { self.0.del(node.into()) }
118            }
119        };
120
121        NonNull::new(node).map(Ref::new)
122    }
123
124    /// Returns an iterator visiting all key-value pairs in arbitrary order.
125    pub fn iter<'me, 'guard, G>(&'me self, guard: &'guard G) -> Iter<'guard, K, V, F>
126    where
127        'me: 'guard,
128        G: RcuGuard<Flavor = F>,
129    {
130        let _ = guard;
131
132        Iter::new(
133            // SAFETY: The read-side RCU lock is taken.
134            unsafe { self.0.iter() },
135        )
136    }
137}
138
139impl<K, V, F> Drop for RcuHashMap<K, V, F>
140where
141    K: Send + 'static,
142    V: Send + 'static,
143    F: RcuFlavor + 'static,
144{
145    fn drop(&mut self) {
146        let mut raw = self.0.clone();
147
148        F::rcu_cleanup_and_block(Box::new(move |context| {
149            let guard = context.rcu_read_lock();
150
151            // SAFETY: The read-side RCU lock is taken.
152            unsafe { raw.del_all() }
153                .iter()
154                .copied()
155                .map(Ref::<K, V, F>::new)
156                .collect::<Vec<_>>()
157                .safe_cleanup();
158
159            drop(guard);
160
161            // SAFETY: The read-side RCU lock is not taken.
162            // SAFETY: We are a registered RCU read-side thread.
163            unsafe { raw.destroy() };
164        }));
165    }
166}
urcu/collections/hashmap/container.rs

urcu/collections/hashmap/
container.rs
