1use std::{
2 ptr,
3 sync::atomic::{AtomicPtr, Ordering as AtomicOrdering},
4};
5
6/// Linked list of entries.
7///
8/// This is implemented in a thread-safe way despite the fact that constructors
9/// are run single-threaded.
10pub struct EntryList<T: 'static> {
11 entry: Option<&'static T>,
12 next: AtomicPtr<Self>,
13}
14
15impl<T> EntryList<T> {
16 pub(crate) const fn root() -> Self {
17 Self { entry: None, next: AtomicPtr::new(ptr::null_mut()) }
18 }
19
20 /// Dereferences the `next` pointer.
21 #[inline]
22 fn next(&self) -> Option<&Self> {
23 // SAFETY: `next` is only assigned by `push`, which always receives a
24 // 'static lifetime.
25 unsafe { self.next.load(order:AtomicOrdering::Relaxed).as_ref() }
26 }
27}
28
29// Externally used by macros or tests.
30#[allow(missing_docs)]
31impl<T> EntryList<T> {
32 #[inline]
33 pub const fn new(entry: &'static T) -> Self {
34 Self { entry: Some(entry), next: AtomicPtr::new(ptr::null_mut()) }
35 }
36
37 /// Creates an iterator over entries in `self`.
38 #[inline]
39 pub fn iter(&self) -> impl Iterator<Item = &T> {
40 let mut list = Some(self);
41 std::iter::from_fn(move || -> Option<Option<&T>> {
42 let current = list?;
43 list = current.next();
44 Some(current.entry.as_ref().copied())
45 })
46 .flatten()
47 }
48
49 /// Inserts `other` to the front of the list.
50 ///
51 /// # Safety
52 ///
53 /// This function must be safe to call before `main`.
54 #[inline]
55 pub fn push(&'static self, other: &'static Self) {
56 let mut old_next = self.next.load(AtomicOrdering::Relaxed);
57 loop {
58 // Each publicly-created instance has `list.next` be null, so we can
59 // simply store `self.next` there.
60 other.next.store(old_next, AtomicOrdering::Release);
61
62 // SAFETY: The content of `other` can already be seen, so we don't
63 // need to strongly order reads into it.
64 let other = other as *const Self as *mut Self;
65 match self.next.compare_exchange_weak(
66 old_next,
67 other,
68 AtomicOrdering::AcqRel,
69 AtomicOrdering::Acquire,
70 ) {
71 // Successfully wrote our thread's value to the list.
72 Ok(_) => return,
73
74 // Lost the race, store winner's value in `other.next`.
75 Err(new) => old_next = new,
76 }
77 }
78 }
79}
80