projects/linux·blob master · refs

168 lines · 4.3 KiB

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
6use core::{
7 cell::Cell,
8 marker::PhantomPinned,
9 pin::Pin,
10 ptr::{self, NonNull},
11};
12
13use pin_init::*;
14
15#[allow(unused_attributes)]
16mod error;
17#[allow(unused_imports)]
18use error::Error;
19
20#[pin_data(PinnedDrop)]
21#[repr(C)]
22#[derive(Debug)]
23pub struct ListHead {
24 next: Link,
25 prev: Link,
26 #[pin]
27 pin: PhantomPinned,
28}
29
30impl 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]
81impl 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)]
95struct Link(Cell<NonNull<ListHead>>);
96
97impl 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")))]
143fn main() {}
144
145#[allow(dead_code)]
146#[cfg_attr(test, test)]
147#[cfg(any(feature = "std", feature = "alloc"))]
148fn 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}