lockless 0.2.0

Composable, lock-free, allocation-light data structures
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

use std::sync::atomic::{AtomicPtr, Ordering};
use std::cell::Cell;
use std::sync::Arc;
use std::ptr;
use std::mem;


// Helper functions for allocation in stable rust
fn allocate<T>() -> *mut T {
    let mut v = Vec::with_capacity(1);
    let result = v.as_mut_ptr();
    mem::forget(v);
    result
}

unsafe fn free<T>(ptr: *mut T) {
    Vec::from_raw_parts(ptr, 0, 1);
}

// Shared part of an AtomicCell
#[derive(Debug)]
struct Inner<T> {
    value: AtomicPtr<T>,
}

impl<T> Inner<T> {
    fn new(value: T) -> Inner<T> {
        let p = allocate();
        unsafe {
            ptr::write(p, value);
        }
        Inner {
            value: AtomicPtr::new(p)
        }
    }
    fn unwrap(self) -> T {
        let p = self.value.load(Ordering::Relaxed);
        unsafe {
            let result = ptr::read(p);
            free(p);
            result
        }
    }
    fn get_mut(&mut self) -> &mut T {
        unsafe { &mut *self.value.load(Ordering::Relaxed) }
    }
}

impl<T> Drop for Inner<T> {
    fn drop(&mut self) {
        let p = self.value.load(Ordering::Relaxed);
        unsafe {
            ptr::read(p);
            free(p);
        }
    }
}

// Manages heap space for a T - may or may not contain an initialized T
#[derive(Debug)]
struct StorageCell<T>(Cell<*mut T>);

impl<T> StorageCell<T> {
    fn new() -> Self {
        StorageCell(Cell::new(allocate()))
    }
    fn write(&self, value: T) {
        unsafe {
            ptr::write(self.0.get(), value);
        }
    }
    unsafe fn read(&self) -> T {
        ptr::read(self.0.get())
    }
    fn get(&self) -> *mut T {
        self.0.get()
    }
    unsafe fn set(&self, p: *mut T) {
        self.0.set(p)
    }
}

impl<T> Drop for StorageCell<T> {
    fn drop(&mut self) {
        unsafe {
            free(self.get())
        }
    }
}

unsafe impl<T: Send> Send for StorageCell<T> {}

/// Lock-free concurrent cell supporting an atomic "swap" operation
#[derive(Debug)]
pub struct AtomicCell<T> {
    space: StorageCell<T>,
    inner: Arc<Inner<T>>
}

impl<T> AtomicCell<T> {
    pub fn new(value: T) -> Self {
        AtomicCell {
            space: StorageCell::new(),
            inner: Arc::new(Inner::new(value))
        }
    }
    pub fn swap(&self, value: T) -> T {
        unsafe {
            // Store the value into the space we own
            self.space.write(value);
            // Swap our space with the shared space atomically
            self.space.set(self.inner.value.swap(self.space.get(), Ordering::Relaxed));
            // Retrieve the value from the returned space
            self.space.read()
        }
    }
    pub fn try_unwrap(self) -> Result<T, Self> {
        match Arc::try_unwrap(self.inner) {
            Ok(inner) => Ok(inner.unwrap()),
            Err(inner) => Err(AtomicCell { space: self.space, inner: inner })
        }
    }
    pub fn get_mut(&mut self) -> Option<&mut T> {
        Arc::get_mut(&mut self.inner).map(|inner| inner.get_mut())
    }
}

impl<T> Clone for AtomicCell<T> {
    fn clone(&self) -> Self {
        AtomicCell {
            space: StorageCell::new(),
            inner: self.inner.clone()
        }
    }
}