1 //! A doubly-linked list where callers are in charge of memory allocation 2 //! of the nodes in the list. 3 4 #[cfg(test)] 5 mod tests; 6 7 use crate::std::mem; 8 use crate::std::ptr::NonNull; 9 10 pub struct UnsafeListEntry<T> { 11 next: NonNull<UnsafeListEntry<T>>, 12 prev: NonNull<UnsafeListEntry<T>>, 13 value: Option<T>, 14 } 15 16 impl<T> UnsafeListEntry<T> { 17 fn dummy() -> Self { 18 UnsafeListEntry { 19 next: NonNull::dangling(), 20 prev: NonNull::dangling(), 21 value: None, 22 } 23 } 24 25 pub fn new(value: T) -> Self { 26 UnsafeListEntry { 27 value: Some(value), 28 ..Self::dummy() 29 } 30 } 31 } 32 33 // WARNING: self-referential struct! 34 pub struct UnsafeList<T> { 35 head_tail: NonNull<UnsafeListEntry<T>>, 36 head_tail_entry: Option<UnsafeListEntry<T>>, 37 } 38 39 impl<T> UnsafeList<T> { 40 pub const fn new() -> Self { 41 unsafe { 42 UnsafeList { 43 head_tail: NonNull::new_unchecked(1 as _), 44 head_tail_entry: None, 45 } 46 } 47 } 48 49 /// # Safety 50 unsafe fn init(&mut self) { 51 if self.head_tail_entry.is_none() { 52 self.head_tail_entry = Some(UnsafeListEntry::dummy()); 53 // SAFETY: `head_tail_entry` must be non-null, which it is because we assign it above. 54 self.head_tail = 55 unsafe { NonNull::new_unchecked(self.head_tail_entry.as_mut().unwrap()) }; 56 // SAFETY: `self.head_tail` must meet all requirements for a mutable reference. 57 unsafe { self.head_tail.as_mut() }.next = self.head_tail; 58 unsafe { self.head_tail.as_mut() }.prev = self.head_tail; 59 } 60 } 61 62 pub fn is_empty(&self) -> bool { 63 if self.head_tail_entry.is_some() { 64 let first = unsafe { self.head_tail.as_ref() }.next; 65 if first == self.head_tail { 66 // ,-------> /---------\ next ---, 67 // | |head_tail| | 68 // `--- prev \---------/ <-------` 69 // SAFETY: `self.head_tail` must meet all requirements for a reference. 70 unsafe { rtassert!(self.head_tail.as_ref().prev == first) }; 71 true 72 } else { 73 false 74 } 75 } else { 76 true 77 } 78 } 79 80 /// Pushes an entry onto the back of the list. 81 /// 82 /// # Safety 83 /// 84 /// The entry must remain allocated until the entry is removed from the 85 /// list AND the caller who popped is done using the entry. Special 86 /// care must be taken in the caller of `push` to ensure unwinding does 87 /// not destroy the stack frame containing the entry. 88 pub unsafe fn push<'a>(&mut self, entry: &'a mut UnsafeListEntry<T>) -> &'a T { 89 unsafe { self.init() }; 90 91 // BEFORE: 92 // /---------\ next ---> /---------\ 93 // ... |prev_tail| |head_tail| ... 94 // \---------/ <--- prev \---------/ 95 // 96 // AFTER: 97 // /---------\ next ---> /-----\ next ---> /---------\ 98 // ... |prev_tail| |entry| |head_tail| ... 99 // \---------/ <--- prev \-----/ <--- prev \---------/ 100 let mut entry = unsafe { NonNull::new_unchecked(entry) }; 101 let mut prev_tail = mem::replace(&mut unsafe { self.head_tail.as_mut() }.prev, entry); 102 // SAFETY: `entry` must meet all requirements for a mutable reference. 103 unsafe { entry.as_mut() }.prev = prev_tail; 104 unsafe { entry.as_mut() }.next = self.head_tail; 105 // SAFETY: `prev_tail` must meet all requirements for a mutable reference. 106 unsafe { prev_tail.as_mut() }.next = entry; 107 // unwrap ok: always `Some` on non-dummy entries 108 unsafe { (*entry.as_ptr()).value.as_ref() }.unwrap() 109 } 110 111 /// Pops an entry from the front of the list. 112 /// 113 /// # Safety 114 /// 115 /// The caller must make sure to synchronize ending the borrow of the 116 /// return value and deallocation of the containing entry. 117 pub unsafe fn pop<'a>(&mut self) -> Option<&'a T> { 118 unsafe { self.init() }; 119 120 if self.is_empty() { 121 None 122 } else { 123 // BEFORE: 124 // /---------\ next ---> /-----\ next ---> /------\ 125 // ... |head_tail| |first| |second| ... 126 // \---------/ <--- prev \-----/ <--- prev \------/ 127 // 128 // AFTER: 129 // /---------\ next ---> /------\ 130 // ... |head_tail| |second| ... 131 // \---------/ <--- prev \------/ 132 let mut first = unsafe { self.head_tail.as_mut() }.next; 133 let mut second = unsafe { first.as_mut() }.next; 134 unsafe { self.head_tail.as_mut() }.next = second; 135 unsafe { second.as_mut() }.prev = self.head_tail; 136 unsafe { first.as_mut() }.next = NonNull::dangling(); 137 unsafe { first.as_mut() }.prev = NonNull::dangling(); 138 // unwrap ok: always `Some` on non-dummy entries 139 Some(unsafe { (*first.as_ptr()).value.as_ref() }.unwrap()) 140 } 141 } 142 143 /// Removes an entry from the list. 144 /// 145 /// # Safety 146 /// 147 /// The caller must ensure that `entry` has been pushed onto `self` 148 /// prior to this call and has not moved since then. 149 pub unsafe fn remove(&mut self, entry: &mut UnsafeListEntry<T>) { 150 rtassert!(!self.is_empty()); 151 // BEFORE: 152 // /----\ next ---> /-----\ next ---> /----\ 153 // ... |prev| |entry| |next| ... 154 // \----/ <--- prev \-----/ <--- prev \----/ 155 // 156 // AFTER: 157 // /----\ next ---> /----\ 158 // ... |prev| |next| ... 159 // \----/ <--- prev \----/ 160 let mut prev = entry.prev; 161 let mut next = entry.next; 162 // SAFETY: `prev` and `next` must meet all requirements for a mutable reference.entry 163 unsafe { prev.as_mut() }.next = next; 164 unsafe { next.as_mut() }.prev = prev; 165 entry.next = NonNull::dangling(); 166 entry.prev = NonNull::dangling(); 167 } 168 } 169