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