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
use std::collections::BinaryHeap;
use std::mem;
use std::ops::{Deref, DerefMut};
use std::sync::{self, PoisonError, TryLockError};
use std::thread;
use token::*;
use types::*;
#[derive(Debug)]
pub struct Mutex<T> {
bookkeeping: sync::Mutex<Bookkeeping>,
data: sync::Mutex<T>,
}
#[derive(Debug)]
struct Bookkeeping {
heap: BinaryHeap<PV<usize, WakeToken>>,
free: bool,
}
impl<T> Mutex<T> {
pub fn new(data: T) -> Mutex<T> {
Mutex {
bookkeeping: sync::Mutex::new(Bookkeeping { heap: BinaryHeap::new(), free: true }),
data: sync::Mutex::new(data),
}
}
pub fn lock(&self, prio: usize) -> sync::LockResult<MutexGuard<T>> {
let mut bk = self.bookkeeping.lock().unwrap();
if bk.free {
bk.free = false;
return self.spin_lock_data();
}
let (sleep_token, wake_token) = create_tokens();
bk.heap.push(PV { p: prio, v: wake_token });
mem::drop(bk);
sleep_token.sleep();
self.spin_lock_data()
}
pub fn try_lock(&self) -> sync::TryLockResult<MutexGuard<T>> {
let mut bk = self.bookkeeping.lock().unwrap();
if bk.free {
bk.free = false;
self.spin_lock_data().map_err(TryLockError::Poisoned)
} else {
Err(TryLockError::WouldBlock)
}
}
fn spin_lock_data(&self) -> sync::LockResult<MutexGuard<T>> {
loop {
match self.data.try_lock() {
Ok(guard) =>
return Ok(MutexGuard(guard, self)),
Err(TryLockError::WouldBlock) =>
thread::yield_now(),
Err(TryLockError::Poisoned(pe)) =>
return Err(PoisonError::new(MutexGuard(pe.into_inner(), self))),
}
}
}
}
pub struct MutexGuard<'a, T: 'a>(sync::MutexGuard<'a, T>, &'a Mutex<T>);
impl<'a, T> Drop for MutexGuard<'a, T> {
fn drop(&mut self) {
let mut bk = self.1.bookkeeping.lock().unwrap();
if let Some(x) = bk.heap.pop() {
x.v.wake();
} else {
bk.free = true;
}
}
}
impl<'a, T> Deref for MutexGuard<'a, T> {
type Target = T;
fn deref(&self) -> &T {
&*self.0
}
}
impl<'a, T> DerefMut for MutexGuard<'a, T> {
fn deref_mut(&mut self) -> &mut T {
&mut *self.0
}
}