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 marker::PhantomPinned, 9 pin::Pin, 10 ptr::{self, NonNull}, 11 }; 12 13 use pin_init::*; 14 15 #[allow(unused_attributes)] 16 mod error; 17 #[allow(unused_imports)] 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> { 33 pin_init!(&this in Self { 34 next: unsafe { Link::new_unchecked(this) }, 35 prev: unsafe { Link::new_unchecked(this) }, 36 pin: PhantomPinned, 37 }) 38 } 39 40 #[inline] 41 #[allow(dead_code)] 42 pub fn insert_next(list: &ListHead) -> impl PinInit<Self> + '_ { 43 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 }) 48 } 49 50 #[inline] 51 pub fn insert_prev(list: &ListHead) -> impl PinInit<Self> + '_ { 52 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 }) 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 #[allow(dead_code)] 116 fn prev(&self) -> &Link { 117 unsafe { &(*self.0.get().as_ptr()).prev } 118 } 119 120 #[allow(dead_code)] 121 fn cur(&self) -> &ListHead { 122 unsafe { &*self.0.get().as_ptr() } 123 } 124 125 #[inline] 126 fn replace(&self, other: Link) -> Link { 127 unsafe { Link::new_unchecked(self.0.replace(other.0.get())) } 128 } 129 130 #[inline] 131 fn as_ptr(&self) -> *const ListHead { 132 self.0.get().as_ptr() 133 } 134 135 #[inline] 136 fn set(&self, val: &Link) { 137 self.0.set(val.0.get()); 138 } 139 } 140 141 #[allow(dead_code)] 142 #[cfg(not(any(feature = "std", feature = "alloc")))] 143 fn main() {} 144 145 #[allow(dead_code)] 146 #[cfg_attr(test, test)] 147 #[cfg(any(feature = "std", feature = "alloc"))] 148 fn main() -> Result<(), Error> { 149 let a = Box::pin_init(ListHead::new())?; 150 stack_pin_init!(let b = ListHead::insert_next(&a)); 151 stack_pin_init!(let c = ListHead::insert_next(&a)); 152 stack_pin_init!(let d = ListHead::insert_next(&b)); 153 let e = Box::pin_init(ListHead::insert_next(&b))?; 154 println!("a ({a:p}): {a:?}"); 155 println!("b ({b:p}): {b:?}"); 156 println!("c ({c:p}): {c:?}"); 157 println!("d ({d:p}): {d:?}"); 158 println!("e ({e:p}): {e:?}"); 159 let mut inspect = &*a; 160 while let Some(next) = inspect.next() { 161 println!("({inspect:p}): {inspect:?}"); 162 inspect = unsafe { &*next.as_ptr() }; 163 if core::ptr::eq(inspect, &*a) { 164 break; 165 } 166 } 167 Ok(()) 168 } 169