once_list/
lib.rs

1use std::sync::OnceLock;
2
3/// ```
4/// use std::sync::{atomic::{AtomicU32, Ordering}};
5/// use std::thread;
6/// use once_list::OnceList;
7///
8/// // Let's exercise this new Sync append-only list by doing a little counting
9/// static LIST: OnceList<u32> = OnceList::new();
10/// static COUNTER: AtomicU32 = AtomicU32::new(0);
11///
12/// let vec = (0..thread::available_parallelism().unwrap().get()).map(|_| thread::spawn(|| {
13///     while let i @ 0..1000 = COUNTER.fetch_add(1, Ordering::Relaxed) {
14///         LIST.push(i);
15///     }
16/// })).collect::<Vec<thread::JoinHandle<_>>>();
17/// vec.into_iter().for_each(|handle| handle.join().unwrap());
18///
19/// for i in 0..1000 {
20///     assert!(LIST.contains(&i));
21/// }
22/// ```
23#[derive(Clone, Debug, PartialEq, Eq)]
24pub struct OnceList<T> {
25    data: OnceLock<T>,
26    next: OnceLock<Box<OnceList<T>>>,
27}
28impl<T> Default for OnceList<T> {
29    fn default() -> Self {
30        OnceList::new()
31    }
32}
33impl<T> OnceList<T> {
34    pub const fn new() -> OnceList<T> {
35        OnceList { data: OnceLock::new(), next: OnceLock::new() }
36    }
37    pub fn push(&self, value: T) {
38        // FIXME: this impl is concise, but is also slow for long lists or many threads.
39        // as an exercise, consider how you might improve on it while preserving the behavior
40        if let Err(value) = self.data.set(value) {
41            let next = self.next.get_or_init(|| Box::new(OnceList::new()));
42            next.push(value)
43        };
44    }
45    pub fn contains(&self, example: &T) -> bool
46    where
47        T: PartialEq,
48    {
49        self.data
50            .get()
51            .and_then(|item| (item == example).then_some(true))
52            .unwrap_or_else(|| self.next.get().map(|next| next.contains(example)).unwrap_or(false))
53    }
54}
once_list/lib.rs

once_list/
lib.rs
