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