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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
//! A doubly-linked list where callers are in charge of memory allocation
//! of the nodes in the list.
#[cfg(test)]
mod tests;
use crate::mem;
use crate::ptr::NonNull;
pub struct UnsafeListEntry<T> {
next: NonNull<UnsafeListEntry<T>>,
prev: NonNull<UnsafeListEntry<T>>,
value: Option<T>,
}
impl<T> UnsafeListEntry<T> {
fn dummy() -> Self {
UnsafeListEntry { next: NonNull::dangling(), prev: NonNull::dangling(), value: None }
}
pub fn new(value: T) -> Self {
UnsafeListEntry { value: Some(value), ..Self::dummy() }
}
}
// WARNING: self-referential struct!
pub struct UnsafeList<T> {
head_tail: NonNull<UnsafeListEntry<T>>,
head_tail_entry: Option<UnsafeListEntry<T>>,
}
impl<T> UnsafeList<T> {
pub const fn new() -> Self {
unsafe { UnsafeList { head_tail: NonNull::new_unchecked(1 as _), head_tail_entry: None } }
}
/// # Safety
unsafe fn init(&mut self) {
if self.head_tail_entry.is_none() {
self.head_tail_entry = Some(UnsafeListEntry::dummy());
// SAFETY: `head_tail_entry` must be non-null, which it is because we assign it above.
self.head_tail =
unsafe { NonNull::new_unchecked(self.head_tail_entry.as_mut().unwrap()) };
// SAFETY: `self.head_tail` must meet all requirements for a mutable reference.
unsafe { self.head_tail.as_mut() }.next = self.head_tail;
unsafe { self.head_tail.as_mut() }.prev = self.head_tail;
}
}
pub fn is_empty(&self) -> bool {
if self.head_tail_entry.is_some() {
let first = unsafe { self.head_tail.as_ref() }.next;
if first == self.head_tail {
// ,-------> /---------\ next ---,
// | |head_tail| |
// `--- prev \---------/ <-------`
// SAFETY: `self.head_tail` must meet all requirements for a reference.
unsafe { rtassert!(self.head_tail.as_ref().prev == first) };
true
} else {
false
}
} else {
true
}
}
/// Pushes an entry onto the back of the list.
///
/// # Safety
///
/// The entry must remain allocated until the entry is removed from the
/// list AND the caller who popped is done using the entry. Special
/// care must be taken in the caller of `push` to ensure unwinding does
/// not destroy the stack frame containing the entry.
pub unsafe fn push<'a>(&mut self, entry: &'a mut UnsafeListEntry<T>) -> &'a T {
unsafe { self.init() };
// BEFORE:
// /---------\ next ---> /---------\
// ... |prev_tail| |head_tail| ...
// \---------/ <--- prev \---------/
//
// AFTER:
// /---------\ next ---> /-----\ next ---> /---------\
// ... |prev_tail| |entry| |head_tail| ...
// \---------/ <--- prev \-----/ <--- prev \---------/
let mut entry = unsafe { NonNull::new_unchecked(entry) };
let mut prev_tail = mem::replace(&mut unsafe { self.head_tail.as_mut() }.prev, entry);
// SAFETY: `entry` must meet all requirements for a mutable reference.
unsafe { entry.as_mut() }.prev = prev_tail;
unsafe { entry.as_mut() }.next = self.head_tail;
// SAFETY: `prev_tail` must meet all requirements for a mutable reference.
unsafe { prev_tail.as_mut() }.next = entry;
// unwrap ok: always `Some` on non-dummy entries
unsafe { (*entry.as_ptr()).value.as_ref() }.unwrap()
}
/// Pops an entry from the front of the list.
///
/// # Safety
///
/// The caller must make sure to synchronize ending the borrow of the
/// return value and deallocation of the containing entry.
pub unsafe fn pop<'a>(&mut self) -> Option<&'a T> {
unsafe { self.init() };
if self.is_empty() {
None
} else {
// BEFORE:
// /---------\ next ---> /-----\ next ---> /------\
// ... |head_tail| |first| |second| ...
// \---------/ <--- prev \-----/ <--- prev \------/
//
// AFTER:
// /---------\ next ---> /------\
// ... |head_tail| |second| ...
// \---------/ <--- prev \------/
let mut first = unsafe { self.head_tail.as_mut() }.next;
let mut second = unsafe { first.as_mut() }.next;
unsafe { self.head_tail.as_mut() }.next = second;
unsafe { second.as_mut() }.prev = self.head_tail;
unsafe { first.as_mut() }.next = NonNull::dangling();
unsafe { first.as_mut() }.prev = NonNull::dangling();
// unwrap ok: always `Some` on non-dummy entries
Some(unsafe { (*first.as_ptr()).value.as_ref() }.unwrap())
}
}
/// Removes an entry from the list.
///
/// # Safety
///
/// The caller must ensure that `entry` has been pushed onto `self`
/// prior to this call and has not moved since then.
pub unsafe fn remove(&mut self, entry: &mut UnsafeListEntry<T>) {
rtassert!(!self.is_empty());
// BEFORE:
// /----\ next ---> /-----\ next ---> /----\
// ... |prev| |entry| |next| ...
// \----/ <--- prev \-----/ <--- prev \----/
//
// AFTER:
// /----\ next ---> /----\
// ... |prev| |next| ...
// \----/ <--- prev \----/
let mut prev = entry.prev;
let mut next = entry.next;
// SAFETY: `prev` and `next` must meet all requirements for a mutable reference.entry
unsafe { prev.as_mut() }.next = next;
unsafe { next.as_mut() }.prev = prev;
entry.next = NonNull::dangling();
entry.prev = NonNull::dangling();
}
}
|
