rcu_list 0.1.1

a lockless concurrent list implementation
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

use core::sync::atomic::{AtomicUsize, Ordering};

#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum TryLockErr {
    Removed,
    Retry,
}

#[derive(Debug, Default)]
pub struct VersionLock {
    version: AtomicUsize,
}

impl VersionLock {
    /// Create a new VersionLock
    pub const fn new() -> Self {
        Self {
            version: AtomicUsize::new(0),
        }
    }

    #[inline]
    fn version_generation(&self, version: usize) -> usize {
        // first bit means node is removed
        // second bit means node is locked
        // valid generations are 0, 4, 8, 12...
        if version & 2 == 0 {
            // not locked, use current generation
            version
        } else {
            // locked, use next generation to try
            version + 2
        }
    }

    /// try lock and return current version
    /// if the node is removed, return Err(NodeTryLockErr::Removed)
    #[inline]
    pub fn try_lock(&self) -> Result<usize, TryLockErr> {
        let version = self.version.load(Ordering::Relaxed);
        if version & 1 == 1 {
            return Err(TryLockErr::Removed);
        }

        let version = self.version_generation(version);
        match self.version.compare_exchange(
            version,
            version + 2,
            Ordering::Acquire,
            Ordering::Relaxed,
        ) {
            Ok(v) => Ok(v),
            Err(v) => {
                if v & 1 == 1 {
                    Err(TryLockErr::Removed)
                } else {
                    Err(TryLockErr::Retry)
                }
            }
        }
    }

    /// lock and return current version
    /// if the node is removed, return Err(NodeTryLockErr::Removed)
    /// valid version is returned in 0, 4, 8, 12...
    #[inline]
    pub fn lock(&self) -> Result<usize, TryLockErr> {
        let backoff = crossbeam_utils::Backoff::new();

        let version = self.version.load(Ordering::Relaxed);
        if version & 1 == 1 {
            return Err(TryLockErr::Removed);
        }

        let mut version = self.version_generation(version);
        while let Err(v) = self.version.compare_exchange_weak(
            version,
            version + 2,
            Ordering::Acquire,
            Ordering::Relaxed,
        ) {
            if v & 1 == 1 {
                return Err(TryLockErr::Removed);
            }
            version = self.version_generation(v);
            backoff.snooze();
        }

        Ok(version)
    }

    #[inline]
    /// unlock to allow other threads to lock
    pub fn unlock(&self) {
        let version = self.version.load(Ordering::Relaxed);
        self.version.store(version + 2, Ordering::Release);
    }

    #[inline]
    /// unlock as removed
    pub fn unlock_remove(&self) {
        let version = self.version.load(Ordering::Relaxed);
        self.version.store(version + 3, Ordering::Release);
    }

    #[inline]
    /// Check if the lock is mark as removed
    pub fn is_removed(&self) -> bool {
        self.version.load(Ordering::Relaxed) & 1 == 1
    }

    // #[inline]
    // /// Check if the lock is unlocked and not removed
    // pub fn is_ready(&self) -> bool {
    //     self.version.load(Ordering::Relaxed) & 3 == 0
    // }
}

#[cfg(test)]
mod tests {
    #[test]
    fn version_lock_test() {
        let lock = super::VersionLock::new();
        assert_eq!(lock.try_lock(), Ok(0));
        assert_eq!(lock.try_lock(), Err(super::TryLockErr::Retry));
        lock.unlock();
        assert_eq!(lock.try_lock(), Ok(4));
        lock.unlock_remove();
        assert_eq!(lock.try_lock(), Err(super::TryLockErr::Removed));
        assert!(lock.is_removed());
        // assert!(!lock.is_ready());
    }
}