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