1 // SPDX-License-Identifier: Apache-2.0 OR MIT 2 3 #![allow(clippy::undocumented_unsafe_blocks)] 4 #![cfg_attr(feature = "alloc", feature(allocator_api))] 5 #![cfg_attr(not(RUSTC_LINT_REASONS_IS_STABLE), feature(lint_reasons))] 6 7 use core::{ 8 cell::Cell, 9 convert::Infallible, 10 marker::PhantomPinned, 11 pin::Pin, 12 ptr::{self, NonNull}, 13 }; 14 15 use pin_init::*; 16 17 #[allow(unused_attributes)] 18 mod error; 19 #[allow(unused_imports)] 20 use error::Error; 21 22 #[pin_data(PinnedDrop)] 23 #[repr(C)] 24 #[derive(Debug)] 25 pub struct ListHead { 26 next: Link, 27 prev: Link, 28 #[pin] 29 pin: PhantomPinned, 30 } 31 32 impl ListHead { 33 #[inline] 34 pub fn new() -> impl PinInit<Self, Infallible> { 35 try_pin_init!(&this in Self { 36 next: unsafe { Link::new_unchecked(this) }, 37 prev: unsafe { Link::new_unchecked(this) }, 38 pin: PhantomPinned, 39 }? Infallible) 40 } 41 42 #[inline] 43 #[allow(dead_code)] 44 pub fn insert_next(list: &ListHead) -> impl PinInit<Self, Infallible> + '_ { 45 try_pin_init!(&this in Self { 46 prev: list.next.prev().replace(unsafe { Link::new_unchecked(this)}), 47 next: list.next.replace(unsafe { Link::new_unchecked(this)}), 48 pin: PhantomPinned, 49 }? Infallible) 50 } 51 52 #[inline] 53 pub fn insert_prev(list: &ListHead) -> impl PinInit<Self, Infallible> + '_ { 54 try_pin_init!(&this in Self { 55 next: list.prev.next().replace(unsafe { Link::new_unchecked(this)}), 56 prev: list.prev.replace(unsafe { Link::new_unchecked(this)}), 57 pin: PhantomPinned, 58 }? Infallible) 59 } 60 61 #[inline] 62 pub fn next(&self) -> Option<NonNull<Self>> { 63 if ptr::eq(self.next.as_ptr(), self) { 64 None 65 } else { 66 Some(unsafe { NonNull::new_unchecked(self.next.as_ptr() as *mut Self) }) 67 } 68 } 69 70 #[allow(dead_code)] 71 pub fn size(&self) -> usize { 72 let mut size = 1; 73 let mut cur = self.next.clone(); 74 while !ptr::eq(self, cur.cur()) { 75 cur = cur.next().clone(); 76 size += 1; 77 } 78 size 79 } 80 } 81 82 #[pinned_drop] 83 impl PinnedDrop for ListHead { 84 //#[inline] 85 fn drop(self: Pin<&mut Self>) { 86 if !ptr::eq(self.next.as_ptr(), &*self) { 87 let next = unsafe { &*self.next.as_ptr() }; 88 let prev = unsafe { &*self.prev.as_ptr() }; 89 next.prev.set(&self.prev); 90 prev.next.set(&self.next); 91 } 92 } 93 } 94 95 #[repr(transparent)] 96 #[derive(Clone, Debug)] 97 struct Link(Cell<NonNull<ListHead>>); 98 99 impl Link { 100 /// # Safety 101 /// 102 /// The contents of the pointer should form a consistent circular 103 /// linked list; for example, a "next" link should be pointed back 104 /// by the target `ListHead`'s "prev" link and a "prev" link should be 105 /// pointed back by the target `ListHead`'s "next" link. 106 #[inline] 107 unsafe fn new_unchecked(ptr: NonNull<ListHead>) -> Self { 108 Self(Cell::new(ptr)) 109 } 110 111 #[inline] 112 fn next(&self) -> &Link { 113 unsafe { &(*self.0.get().as_ptr()).next } 114 } 115 116 #[inline] 117 #[allow(dead_code)] 118 fn prev(&self) -> &Link { 119 unsafe { &(*self.0.get().as_ptr()).prev } 120 } 121 122 #[allow(dead_code)] 123 fn cur(&self) -> &ListHead { 124 unsafe { &*self.0.get().as_ptr() } 125 } 126 127 #[inline] 128 fn replace(&self, other: Link) -> Link { 129 unsafe { Link::new_unchecked(self.0.replace(other.0.get())) } 130 } 131 132 #[inline] 133 fn as_ptr(&self) -> *const ListHead { 134 self.0.get().as_ptr() 135 } 136 137 #[inline] 138 fn set(&self, val: &Link) { 139 self.0.set(val.0.get()); 140 } 141 } 142 143 #[allow(dead_code)] 144 #[cfg(not(any(feature = "std", feature = "alloc")))] 145 fn main() {} 146 147 #[allow(dead_code)] 148 #[cfg_attr(test, test)] 149 #[cfg(any(feature = "std", feature = "alloc"))] 150 fn main() -> Result<(), Error> { 151 let a = Box::pin_init(ListHead::new())?; 152 stack_pin_init!(let b = ListHead::insert_next(&a)); 153 stack_pin_init!(let c = ListHead::insert_next(&a)); 154 stack_pin_init!(let d = ListHead::insert_next(&b)); 155 let e = Box::pin_init(ListHead::insert_next(&b))?; 156 println!("a ({a:p}): {a:?}"); 157 println!("b ({b:p}): {b:?}"); 158 println!("c ({c:p}): {c:?}"); 159 println!("d ({d:p}): {d:?}"); 160 println!("e ({e:p}): {e:?}"); 161 let mut inspect = &*a; 162 while let Some(next) = inspect.next() { 163 println!("({inspect:p}): {inspect:?}"); 164 inspect = unsafe { &*next.as_ptr() }; 165 if core::ptr::eq(inspect, &*a) { 166 break; 167 } 168 } 169 Ok(()) 170 } 171