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