lock_free_stack/
lock_free_stack.rs

1use std::ptr;
2use std::sync::atomic::{AtomicPtr, Ordering};
3
4#[allow(dead_code)]
5struct Node<K> {
6    size: usize,
7    next: *mut Node<K>,
8    payload: K
9}
10
11#[allow(dead_code)]
12pub struct StackTailIterator<M> {
13    top: *mut Node<M>
14}
15
16#[allow(dead_code)]
17pub struct Stack<T> {
18    top: AtomicPtr<Node<T>>
19}
20
21impl<T> Stack<T> {
22    #[allow(dead_code)]
23    pub fn new() -> Stack<T> {
24        Stack { top: AtomicPtr::new(ptr::null_mut()) }
25    }
26
27    #[allow(dead_code)]
28    pub fn size(&self) -> usize {
29        let top_ptr = self.top.load(Ordering::Relaxed);
30        if top_ptr.is_null() {
31            0
32        } else {
33            unsafe { (&*top_ptr).size }
34        }
35    }
36
37    #[allow(dead_code)]
38    pub fn add(&self, value: T) -> usize {
39        let mut top_ptr = self.top.load(Ordering::Relaxed);
40
41        let new_top = Box::into_raw(Box::new(
42            Node { size: 0, next: ptr::null_mut(), payload: value }
43        ));
44
45        loop {
46            let new_size = if top_ptr.is_null() { 1 } else { unsafe { (&*top_ptr).size + 1 } };
47            unsafe {
48                (&mut *new_top).size = new_size;
49                (&mut *new_top).next = top_ptr;
50            };
51
52            let previous_top = self.top.compare_and_swap(
53                top_ptr,
54                new_top,
55                Ordering::Relaxed
56            );
57
58            if previous_top == top_ptr {
59                return new_size;
60            } else {
61                top_ptr = previous_top;
62            }
63        }
64    }
65
66    #[allow(dead_code)]
67    pub fn remove_all(&self) -> StackTailIterator<T> {
68        let mut top_ptr = self.top.load(Ordering::Relaxed);
69
70        loop {
71            let previous_top = self.top.compare_and_swap(
72                top_ptr,
73                ptr::null_mut(),
74                Ordering::Relaxed
75            );
76
77            if previous_top == top_ptr {
78                return StackTailIterator { top: top_ptr }
79            } else {
80                top_ptr = previous_top;
81            }
82        }
83    }
84}
85
86impl<T> Drop for Stack<T> {
87    fn drop(&mut self) {
88        let _ = self.remove_all();
89    }
90}
91
92impl<M> Iterator for StackTailIterator<M> {
93    type Item = M;
94
95    fn next(&mut self) -> Option<M> {
96        if self.top.is_null() {
97            None
98        } else {
99            let boxed_node = unsafe { Box::from_raw(self.top) };
100            self.top = boxed_node.next;
101
102            Some(boxed_node.payload)
103        }
104    }
105}
106
107impl<M> Drop for StackTailIterator<M> {
108    fn drop(&mut self) {
109        for _ in self {}
110    }
111}
lock_free_stack/lock_free_stack.rs

lock_free_stack/
lock_free_stack.rs
