idr_ebr/lib.rs
1#![doc = include_str!("../README.md")]
2#![warn(missing_docs)]
3
4use std::fmt;
5
6use self::{config::ConfigPrivate, control::PageControl, key::PageNo, page::Page};
7
8mod config;
9mod control;
10mod handles;
11mod key;
12mod loom;
13mod page;
14mod slot;
15
16pub use self::{
17 config::{Config, DefaultConfig},
18 handles::{BorrowedEntry, Iter, OwnedEntry, VacantEntry},
19 key::Key,
20};
21
22// === Idr ===
23
24/// An IDR (IDentifier Resolver) provides a way to efficiently and concurrently
25/// map integer IDs to references to objects. It's particularly useful in
26/// scenarios where you need to quickly find objects based on their ID. This
27/// structure is designed to be highly efficient in terms of both speed and
28/// memory usage.
29pub struct Idr<T, C = DefaultConfig> {
30 // TODO: flatten
31 pages: Box<[Page<T, C>]>,
32 // Used to synchronize page allocations.
33 page_control: PageControl,
34}
35
36impl<T: 'static> Default for Idr<T> {
37 fn default() -> Self {
38 Self::new()
39 }
40}
41
42impl<T: 'static, C: Config> Idr<T, C> {
43 /// The number of bits in each key which are used by the IDR.
44 ///
45 /// If other data is packed into the keys returned by [`Idr::insert()`],
46 /// user code is free to use any bits higher than the `USED_BITS`-th bit.
47 ///
48 /// This is determined by the [`Config`] type that configures the IDR's
49 /// parameters. By default, all bits are used; this can be changed by
50 /// overriding the [`Config::RESERVED_BITS`] constant.
51 pub const USED_BITS: u32 = C::USED_BITS;
52
53 /// Returns a new IDR with the provided configuration parameters.
54 pub fn new() -> Self {
55 // Perform compile-time postmono checks.
56 assert!(C::ENSURE_VALID);
57
58 Self {
59 pages: (0..C::MAX_PAGES).map(PageNo::new).map(Page::new).collect(),
60 page_control: PageControl::default(),
61 }
62 }
63
64 /// Inserts a value into the IDR, returning the key at which that
65 /// value was inserted. This key can then be used to access the entry.
66 ///
67 /// This method is, usually, lock-free. However, it can block if a new page
68 /// should be allocated. Thus, it can block max [`Config::MAX_PAGES`] times.
69 /// Once allocated, the page is never deallocated until the IDR is dropped.
70 ///
71 /// Returns `None` if there is no more space in the IDR,
72 /// and no items can be added until some are removed.
73 ///
74 /// # Panics
75 ///
76 /// If a new page should be allocated, but the allocator fails.
77 ///
78 /// # Example
79 ///
80 /// ```
81 /// use idr_ebr::{Idr, EbrGuard};
82 ///
83 /// let idr = Idr::default();
84 /// let key = idr.insert("foo").unwrap();
85 /// assert_eq!(idr.get(key, &EbrGuard::new()).unwrap(), "foo");
86 /// ```
87 #[inline]
88 pub fn insert(&self, value: T) -> Option<Key> {
89 self.vacant_entry().map(|entry| {
90 let key = entry.key();
91 entry.insert(value);
92 key
93 })
94 }
95
96 /// Returns a handle to a vacant entry allowing for further manipulation.
97 ///
98 /// This method is, usually, lock-free. However, it can block if a new page
99 /// should be allocated. Thus, it can block max [`Config::MAX_PAGES`] times.
100 /// Once allocated, the page is never deallocated until the IDR is dropped.
101 ///
102 /// This method is useful when creating values that must contain their
103 /// IDR key. The returned [`VacantEntry`] reserves a slot in the IDR and
104 /// is able to return the key of the entry.
105 ///
106 /// Returns `None` if there is no more space in the IDR,
107 /// and no items can be added until some are removed.
108 ///
109 /// # Panics
110 ///
111 /// If a new page should be allocated, but the allocator fails.
112 ///
113 /// # Example
114 ///
115 /// ```
116 /// use idr_ebr::{Idr, EbrGuard};
117 ///
118 /// let idr = Idr::default();
119 ///
120 /// let key = {
121 /// let entry = idr.vacant_entry().unwrap();
122 /// let key = entry.key();
123 /// entry.insert((key, "foo"));
124 /// key
125 /// };
126 ///
127 /// assert_eq!(idr.get(key, &EbrGuard::new()).unwrap().0, key);
128 /// assert_eq!(idr.get(key, &EbrGuard::new()).unwrap().1, "foo");
129 /// ```
130 #[inline]
131 pub fn vacant_entry(&self) -> Option<VacantEntry<'_, T, C>> {
132 self.page_control.choose(&self.pages, |page| {
133 page.reserve(&self.page_control)
134 .map(|(key, slot)| VacantEntry::new(page, slot, key))
135 })
136 }
137
138 /// Removes the entry at the given key in the IDR, returning `true` if a
139 /// value was present at the moment of the removal.
140 ///
141 /// This method is lock-free.
142 ///
143 /// The removed entry becomes unreachable for getting instantly,
144 /// but it still can be accessed using existing handles.
145 ///
146 /// An object behind the entry is not actually dropped until all handles are
147 /// dropped and EBR garbage is cleaned up.
148 ///
149 /// # Example
150 ///
151 /// ```
152 /// use idr_ebr::{Idr, EbrGuard};
153 ///
154 /// let idr = Idr::default();
155 /// let key = idr.insert("foo").unwrap();
156 ///
157 /// let guard = EbrGuard::new();
158 /// let entry = idr.get(key, &guard).unwrap();
159 ///
160 /// // Remove the entry from the IDR.
161 /// assert!(idr.remove(key));
162 ///
163 /// // Repeat removal will return false.
164 /// assert!(!idr.remove(key));
165 ///
166 /// // Now, the entry is unrechable using IDR.
167 /// assert!(!idr.contains(key));
168 ///
169 /// // However, it still can be accessed using the handle.
170 /// assert_eq!(entry, "foo");
171 ///
172 /// // An object behind the entry is not dropped until all handles are dropped.
173 /// // The real destruction of the object can be delayed according to EBR.
174 /// drop(guard);
175 /// ```
176 #[inline]
177 pub fn remove(&self, key: Key) -> bool {
178 let page_no = key.page_no::<C>();
179 self.pages
180 .get(page_no.to_usize())
181 .is_some_and(|page| page.remove(key))
182 }
183
184 /// Returns a borrowed handle to the entry associated with the given key,
185 /// or `None` if the IDR contains no entry for the given key.
186 ///
187 /// This method is wait-free.
188 ///
189 /// While the handle exists, it indicates to the IDR that the entry the
190 /// handle references is currently being accessed. If the entry is
191 /// removed from the IDR while a handle exists, it's still accessible via
192 /// the handle.
193 ///
194 /// This method **doesn't modify memory**, thus it creates no contention on
195 /// it at all. This is the whole point of the EBR pattern and the reason
196 /// why it's used here.
197 ///
198 /// The returned handle cannot be send to another thread.
199 /// Also, it means it cannot be hold over `.await` points.
200 ///
201 /// # Example
202 ///
203 /// ```
204 /// use idr_ebr::{Idr, EbrGuard, Key};
205 ///
206 /// let idr = Idr::default();
207 /// let key = idr.insert("foo").unwrap();
208 ///
209 /// let guard = EbrGuard::new();
210 /// let entry = idr.get(key, &guard).unwrap();
211 /// assert_eq!(entry, "foo");
212 ///
213 /// // If the entry is removed, the handle is still valid.
214 /// assert!(idr.remove(key));
215 /// assert_eq!(entry, "foo");
216 ///
217 /// // Getting entry for an unknown key produces None.
218 /// assert!(idr.get(Key::try_from(12345).unwrap(), &guard).is_none());
219 /// ```
220 #[inline]
221 pub fn get<'g>(&self, key: Key, guard: &'g EbrGuard) -> Option<BorrowedEntry<'g, T>> {
222 let page_no = key.page_no::<C>();
223 let page = self.pages.get(page_no.to_usize())?;
224 page.get(key, guard)
225 }
226
227 /// Returns a owned handle to the entry associated with the given key,
228 /// or `None` if the IDR contains no entry for the given key.
229 ///
230 /// This method is lock-free.
231 ///
232 /// While the handle exists, it indicates to the IDR that the entry the
233 /// handle references is currently being accessed. If the entry is
234 /// removed from the IDR while a handle exists, it's still accessible via
235 /// the handle.
236 ///
237 /// Unlike [`Idr::get()`], which borrows the IDR, this method holds a strong
238 /// reference to the object itself:
239 /// * It modify the memory and, therefore, creates contention on it.
240 /// * The IDR can be dropped while the handle exists.
241 /// * It can be send to another thread.
242 /// * It can be hold over `.await` points.
243 ///
244 /// # Example
245 ///
246 /// ```
247 /// use idr_ebr::Idr;
248 ///
249 /// let idr = Idr::default();
250 /// let key = idr.insert("foo").unwrap();
251 ///
252 /// let entry = idr.get_owned(key).unwrap();
253 ///
254 /// // The IDR can be dropped.
255 /// drop(idr);
256 ///
257 /// // The handle can be send to another thread.
258 /// std::thread::spawn(move || {
259 /// assert_eq!(entry, "foo");
260 /// }).join().unwrap();
261 /// ```
262 #[inline]
263 pub fn get_owned(&self, key: Key) -> Option<OwnedEntry<T>> {
264 self.get(key, &EbrGuard::new())?.to_owned()
265 }
266
267 /// Returns `true` if the IDR contains an entry for the given key.
268 ///
269 /// This method is wait-free.
270 ///
271 /// # Example
272 ///
273 /// ```
274 /// use idr_ebr::Idr;
275 ///
276 /// let idr = Idr::default();
277 ///
278 /// let key = idr.insert("foo").unwrap();
279 /// assert!(idr.contains(key));
280 ///
281 /// idr.remove(key);
282 /// assert!(!idr.contains(key));
283 /// ```
284 #[inline]
285 pub fn contains(&self, key: Key) -> bool {
286 self.get(key, &EbrGuard::new()).is_some()
287 }
288
289 /// Returns a fused iterator over all occupied entries in the IDR.
290 /// An order of iteration is not guaranteed. Added during iteration entries
291 /// can be observed via the iterator, but it depends on the current position
292 /// of the iterator.
293 ///
294 /// This method is wait-free and [`Iter::next()`] is also wait-free.
295 ///
296 /// While the handle exists, it indicates to the IDR that the entry the
297 /// handle references is currently being accessed. If the entry is
298 /// removed from the IDR while a handle exists, it's still accessible via
299 /// the handle.
300 ///
301 /// This method **doesn't modify memory**, thus it creates no contention on
302 /// it at all. This is the whole point of the EBR pattern and the reason
303 /// why it's used here.
304 ///
305 /// The returned iterator cannot be send to another thread.
306 /// Also, it means it cannot be hold over `.await` points.
307 ///
308 /// # Example
309 ///
310 /// ```
311 /// use idr_ebr::{Idr, EbrGuard};
312 ///
313 /// let idr = Idr::default();
314 /// let foo_key = idr.insert("foo").unwrap();
315 /// let bar_key = idr.insert("bar").unwrap();
316 ///
317 /// let guard = EbrGuard::new();
318 /// let mut iter = idr.iter(&guard);
319 ///
320 /// let (key, entry) = iter.next().unwrap();
321 /// assert_eq!(key, foo_key);
322 /// assert_eq!(entry, "foo");
323 ///
324 /// let (key, entry) = iter.next().unwrap();
325 /// assert_eq!(key, bar_key);
326 /// assert_eq!(entry, "bar");
327 ///
328 /// let baz_key = idr.insert("baz").unwrap();
329 /// let (key, entry) = iter.next().unwrap();
330 /// assert_eq!(key, baz_key);
331 /// assert_eq!(entry, "baz");
332 /// ```
333 #[inline]
334 pub fn iter<'g>(&self, guard: &'g EbrGuard) -> Iter<'g, '_, T, C> {
335 Iter::new(&self.pages, guard)
336 }
337}
338
339impl<T, C: Config> fmt::Debug for Idr<T, C> {
340 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
341 f.debug_struct("Idr")
342 .field("allocated_pages", &self.page_control.allocated())
343 .field("config", &C::debug())
344 .finish_non_exhaustive()
345 }
346}
347
348// === EbrGuard ===
349
350/// [`EbrGuard`] allows to access entries of [`Idr`].
351///
352/// Wraps [`sdd::Guard`] in order to avoid potential breaking changes.
353#[derive(Default)]
354#[must_use]
355pub struct EbrGuard(sdd::Guard);
356
357impl EbrGuard {
358 /// Creates a new [`EbrGuard`].
359 ///
360 /// # Panics
361 ///
362 /// The maximum number of [`EbrGuard`] instances in a thread is limited to
363 /// `u32::MAX`; a thread panics when the number of [`EbrGuard`]
364 /// instances in the thread exceeds the limit.
365 ///
366 /// # Examples
367 ///
368 /// ```
369 /// use idr_ebr::EbrGuard;
370 ///
371 /// let guard = EbrGuard::new();
372 /// ```
373 #[inline]
374 pub fn new() -> Self {
375 Self(sdd::Guard::new())
376 }
377}
378
379impl fmt::Debug for EbrGuard {
380 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
381 f.debug_struct("EbrGuard").finish()
382 }
383}