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]
new() -> impl PinInit<Self, Infallible>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]
insert_next(list: &ListHead) -> impl PinInit<Self, Infallible> + '_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]
insert_prev(list: &ListHead) -> impl PinInit<Self, Infallible> + '_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]
next(&self) -> Option<NonNull<Self>>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)]
size(&self) -> usize68 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]
drop(self: Pin<&mut Self>)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]
new_unchecked(ptr: NonNull<ListHead>) -> Self104 unsafe fn new_unchecked(ptr: NonNull<ListHead>) -> Self {
105 Self(Cell::new(ptr))
106 }
107
108 #[inline]
next(&self) -> &Link109 fn next(&self) -> &Link {
110 unsafe { &(*self.0.get().as_ptr()).next }
111 }
112
113 #[inline]
prev(&self) -> &Link114 fn prev(&self) -> &Link {
115 unsafe { &(*self.0.get().as_ptr()).prev }
116 }
117
118 #[allow(dead_code)]
cur(&self) -> &ListHead119 fn cur(&self) -> &ListHead {
120 unsafe { &*self.0.get().as_ptr() }
121 }
122
123 #[inline]
replace(&self, other: Link) -> Link124 fn replace(&self, other: Link) -> Link {
125 unsafe { Link::new_unchecked(self.0.replace(other.0.get())) }
126 }
127
128 #[inline]
as_ptr(&self) -> *const ListHead129 fn as_ptr(&self) -> *const ListHead {
130 self.0.get().as_ptr()
131 }
132
133 #[inline]
set(&self, val: &Link)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)]
main() -> Result<(), Error>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