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

use std::ops::{Deref, DerefMut};

#[cfg(test)]
mod tests;

/// Provides mutually exclusive access to a shared object using Dekker's algorithm.
pub struct Dekker<T> {
    shared: T,
    turn: usize,
    wants_to_enter: [bool; 2],
    processes: u8,
}

impl<T> Dekker<T> {
    /// Allocates a new shared object and returns two processes to access it.
    pub fn new(shared: T) -> (Process<T>, Process<T>) {
        let dekker = Dekker {
            shared,
            turn: 0,
            wants_to_enter: [false; 2],
            processes: 2,
        };

        let dekker = Box::leak(Box::new(dekker));

        (Process::new(0, dekker), Process::new(1, dekker))
    }
}

/// Used to access the critical section from one of two concurrent processes.
pub struct Process<T> {
    index: usize,
    owner: *mut Dekker<T>,
    locked: bool,
}

unsafe impl<T> Send for Process<T> {}

impl<T> Process<T> {
    fn new(index: usize, owner: *mut Dekker<T>) -> Process<T> {
        Process {
            index,
            owner,
            locked: false,
        }
    }

    /// Acquire the lock for the critical section.
    pub fn lock(&mut self) -> Guard<T> {
        unsafe {
            (*self.owner).wants_to_enter[self.index] = true;
            while (*self.owner).wants_to_enter[1 - self.index] {
                if (*self.owner).turn != self.index {
                    (*self.owner).wants_to_enter[self.index] = false;
                    while (*self.owner).turn != self.index {}
                    (*self.owner).wants_to_enter[self.index] = true;
                }
            }
        }

        self.locked = true;

        Guard::new(self as *mut Process<T>)
    }
}

impl<T> Drop for Process<T> {
    // We can deallocate if both processes are finished.
    fn drop(&mut self) {
        let guard = self.lock();

        unsafe {
            (*self.owner).processes -= 1;
            if (*self.owner).processes == 0 {
                let dekker = Box::from_raw(self.owner);
                drop(dekker);
            }
        }

        drop(guard);
    }
}

/// Holds the lock until dropped.
pub struct Guard<T> {
    owner: *mut Process<T>,
}

impl<T> Guard<T> {
    fn new(owner: *mut Process<T>) -> Guard<T> {
        Guard {
            owner,
        }
    }
}

impl<T> Deref for Guard<T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        unsafe {
            &(*(*self.owner).owner).shared
        }
    }
}

impl<T> DerefMut for Guard<T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe {
            &mut (*(*self.owner).owner).shared
        }
    }
}

impl<T> Drop for Guard<T> {
    // Let other process enter the critical section if guard is dropped.
    fn drop(&mut self) {
        unsafe {
            (*self.owner).locked = false;
            (*(*self.owner).owner).turn = 1 - (*self.owner).index;
            (*(*self.owner).owner).wants_to_enter[(*self.owner).index] = false;
        }
    }
}