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();
}
}