linked_list.rs

  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
  7use core::{
  8    cell::Cell,
  9    convert::Infallible,
 10    marker::PhantomPinned,
 11    pin::Pin,
 12    ptr::{self, NonNull},
 13};
 14
 15use pin_init::*;
 16
 17#[allow(unused_attributes)]
 18mod error;
 19#[allow(unused_imports)]
 20use error::Error;
 21
 22#[pin_data(PinnedDrop)]
 23#[repr(C)]
 24#[derive(Debug)]
 25pub struct ListHead {
 26    next: Link,
 27    prev: Link,
 28    #[pin]
 29    pin: PhantomPinned,
 30}
 31
 32impl ListHead {
 33    #[inline]
 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)]
 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]
 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]
 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)]
 71    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]
 83impl PinnedDrop for ListHead {
 84    //#[inline]
 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)]
 97struct Link(Cell<NonNull<ListHead>>);
 98
 99impl 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]
107    unsafe fn new_unchecked(ptr: NonNull<ListHead>) -> Self {
108        Self(Cell::new(ptr))
109    }
110
111    #[inline]
112    fn next(&self) -> &Link {
113        unsafe { &(*self.0.get().as_ptr()).next }
114    }
115
116    #[inline]
117    #[allow(dead_code)]
118    fn prev(&self) -> &Link {
119        unsafe { &(*self.0.get().as_ptr()).prev }
120    }
121
122    #[allow(dead_code)]
123    fn cur(&self) -> &ListHead {
124        unsafe { &*self.0.get().as_ptr() }
125    }
126
127    #[inline]
128    fn replace(&self, other: Link) -> Link {
129        unsafe { Link::new_unchecked(self.0.replace(other.0.get())) }
130    }
131
132    #[inline]
133    fn as_ptr(&self) -> *const ListHead {
134        self.0.get().as_ptr()
135    }
136
137    #[inline]
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")))]
145fn main() {}
146
147#[allow(dead_code)]
148#[cfg_attr(test, test)]
149#[cfg(any(feature = "std", feature = "alloc"))]
150fn 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}