locklessness/primitives/
prepend_list.rs

1/// PrependList is a low-level primitive supporting two safe operations:
2/// `push`, which prepends a node to the list, and `swap` which replaces the list with another
3
4use std::sync::atomic::{AtomicPtr, Ordering};
5use std::{ptr, mem};
6
7pub type NodePtr<T> = Option<Box<Node<T>>>;
8
9#[derive(Debug)]
10pub struct Node<T> {
11    pub value: T,
12    pub next: NodePtr<T>
13}
14
15#[derive(Debug)]
16pub struct PrependList<T>(AtomicPtr<Node<T>>);
17
18fn replace_forget<T>(dest: &mut T, value: T) {
19    mem::forget(mem::replace(dest, value))
20}
21
22impl<T> PrependList<T> {
23    fn into_raw(ptr: NodePtr<T>) -> *mut Node<T> {
24        match ptr {
25            Some(b) => Box::into_raw(b),
26            None => ptr::null_mut()
27        }
28    }
29    unsafe fn from_raw(ptr: *mut Node<T>) -> NodePtr<T> {
30        if ptr == ptr::null_mut() {
31            None
32        } else {
33            Some(Box::from_raw(ptr))
34        }
35    }
36
37    pub fn new(ptr: NodePtr<T>) -> Self {
38        PrependList(AtomicPtr::new(Self::into_raw(ptr)))
39    }
40    pub fn swap(&self, ptr: NodePtr<T>) -> NodePtr<T> {
41        unsafe {
42            Self::from_raw(self.0.swap(Self::into_raw(ptr), Ordering::AcqRel))
43        }
44    }
45    pub fn push(&self, mut node: Box<Node<T>>) {
46        let mut current = self.0.load(Ordering::Relaxed);
47        loop {
48            replace_forget(&mut node.next, unsafe { Self::from_raw(current) });
49            match self.0.compare_exchange_weak(current, &mut *node, Ordering::AcqRel, Ordering::Relaxed) {
50                Ok(_) => {
51                    mem::forget(node);
52                    return
53                },
54                Err(p) => current = p
55            }
56        }
57    }
58}
59
60impl<T> Drop for PrependList<T> {
61    fn drop(&mut self) {
62        unsafe { Self::from_raw(self.0.swap(ptr::null_mut(), Ordering::Relaxed)) };
63    }
64}
locklessness/primitives/prepend_list.rs

locklessness/primitives/
prepend_list.rs
