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]
new() -> impl PinInit<Self, Infallible>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]
insert_next(list: &ListHead) -> impl PinInit<Self, Infallible> + '_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]
insert_prev(list: &ListHead) -> impl PinInit<Self, Infallible> + '_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]
next(&self) -> Option<NonNull<Self>>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)]
size(&self) -> usize69 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]
drop(self: Pin<&mut Self>)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]
new_unchecked(ptr: NonNull<ListHead>) -> Self105 unsafe fn new_unchecked(ptr: NonNull<ListHead>) -> Self {
106 Self(Cell::new(ptr))
107 }
108
109 #[inline]
next(&self) -> &Link110 fn next(&self) -> &Link {
111 unsafe { &(*self.0.get().as_ptr()).next }
112 }
113
114 #[inline]
prev(&self) -> &Link115 fn prev(&self) -> &Link {
116 unsafe { &(*self.0.get().as_ptr()).prev }
117 }
118
119 #[allow(dead_code)]
cur(&self) -> &ListHead120 fn cur(&self) -> &ListHead {
121 unsafe { &*self.0.get().as_ptr() }
122 }
123
124 #[inline]
replace(&self, other: Link) -> Link125 fn replace(&self, other: Link) -> Link {
126 unsafe { Link::new_unchecked(self.0.replace(other.0.get())) }
127 }
128
129 #[inline]
as_ptr(&self) -> *const ListHead130 fn as_ptr(&self) -> *const ListHead {
131 self.0.get().as_ptr()
132 }
133
134 #[inline]
set(&self, val: &Link)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)]
main() -> Result<(), Error>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