#![allow(clippy::new_without_default, clippy::missing_safety_doc)]
use core::cell::UnsafeCell;
use core::fmt;
use core::marker::{PhantomData, PhantomPinned};
use core::mem::ManuallyDrop;
use core::ptr::{self, NonNull};
pub struct LinkedList<L, T> {
head: Option<NonNull<T>>,
_marker: PhantomData<*const L>,
}
unsafe impl<L: Link> Send for LinkedList<L, L::Target> where L::Target: Send {}
unsafe impl<L: Link> Sync for LinkedList<L, L::Target> where L::Target: Sync {}
pub unsafe trait Link {
type Handle;
type Target;
#[allow(clippy::wrong_self_convention)]
fn as_raw(handle: &Self::Handle) -> NonNull<Self::Target>;
unsafe fn from_raw(ptr: NonNull<Self::Target>) -> Self::Handle;
unsafe fn pointers(target: NonNull<Self::Target>) -> NonNull<Pointers<Self::Target>>;
}
pub struct Pointers<T> {
inner: UnsafeCell<PointersInner<T>>,
}
#[repr(C)]
struct PointersInner<T> {
#[allow(dead_code)]
prev: Option<NonNull<T>>,
#[allow(dead_code)]
next: Option<NonNull<T>>,
_pin: PhantomPinned,
}
unsafe impl<T: Send> Send for PointersInner<T> {}
unsafe impl<T: Sync> Sync for PointersInner<T> {}
unsafe impl<T: Send> Send for Pointers<T> {}
unsafe impl<T: Sync> Sync for Pointers<T> {}
impl<L, T> LinkedList<L, T> {
pub const fn new() -> LinkedList<L, T> {
LinkedList {
head: None,
_marker: PhantomData,
}
}
}
impl<L: Link> LinkedList<L, L::Target> {
pub fn push_front(&mut self, val: L::Handle) {
let val = ManuallyDrop::new(val);
let ptr = L::as_raw(&val);
assert_ne!(self.head, Some(ptr));
unsafe {
L::pointers(ptr).as_mut().set_next(self.head);
L::pointers(ptr).as_mut().set_prev(None);
if let Some(head) = self.head {
L::pointers(head).as_mut().set_prev(Some(ptr));
}
self.head = Some(ptr);
}
}
pub fn is_empty(&self) -> bool {
self.head.is_none()
}
pub unsafe fn remove(&mut self, node: NonNull<L::Target>) -> Option<L::Handle> {
if let Some(prev) = L::pointers(node).as_ref().get_prev() {
debug_assert_eq!(L::pointers(prev).as_ref().get_next(), Some(node));
L::pointers(prev)
.as_mut()
.set_next(L::pointers(node).as_ref().get_next());
} else {
if self.head != Some(node) {
return None;
}
self.head = L::pointers(node).as_ref().get_next();
}
if let Some(next) = L::pointers(node).as_ref().get_next() {
debug_assert_eq!(L::pointers(next).as_ref().get_prev(), Some(node));
L::pointers(next)
.as_mut()
.set_prev(L::pointers(node).as_ref().get_prev());
} else {
}
L::pointers(node).as_mut().set_next(None);
L::pointers(node).as_mut().set_prev(None);
Some(L::from_raw(node))
}
pub fn iter(&self) -> impl Iterator<Item = &L::Target> {
std::iter::successors(self.head, |node| unsafe {
L::pointers(*node).as_ref().get_next()
})
.map(|ptr| unsafe { ptr.as_ref() })
}
}
impl<L: Link> fmt::Debug for LinkedList<L, L::Target> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("LinkedList")
.field("head", &self.head)
.finish()
}
}
impl<L: Link> Default for LinkedList<L, L::Target> {
fn default() -> Self {
Self::new()
}
}
pub struct DrainFilter<'a, T: Link, F> {
list: &'a mut LinkedList<T, T::Target>,
filter: F,
curr: Option<NonNull<T::Target>>,
}
impl<T: Link> LinkedList<T, T::Target> {
pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F>
where
F: FnMut(&mut T::Target) -> bool,
{
let curr = self.head;
DrainFilter {
curr,
filter,
list: self,
}
}
}
impl<'a, T, F> Iterator for DrainFilter<'a, T, F>
where
T: Link,
F: FnMut(&mut T::Target) -> bool,
{
type Item = T::Handle;
fn next(&mut self) -> Option<Self::Item> {
while let Some(curr) = self.curr {
self.curr = unsafe { T::pointers(curr).as_ref() }.get_next();
if (self.filter)(unsafe { &mut *curr.as_ptr() }) {
return unsafe { self.list.remove(curr) };
}
}
None
}
}
impl<T> Pointers<T> {
pub fn new() -> Pointers<T> {
Pointers {
inner: UnsafeCell::new(PointersInner {
prev: None,
next: None,
_pin: PhantomPinned,
}),
}
}
fn get_prev(&self) -> Option<NonNull<T>> {
unsafe {
let inner = self.inner.get();
let prev = inner as *const Option<NonNull<T>>;
ptr::read(prev)
}
}
fn get_next(&self) -> Option<NonNull<T>> {
unsafe {
let inner = self.inner.get();
let prev = inner as *const Option<NonNull<T>>;
let next = prev.add(1);
ptr::read(next)
}
}
fn set_prev(&mut self, value: Option<NonNull<T>>) {
unsafe {
let inner = self.inner.get();
let prev = inner as *mut Option<NonNull<T>>;
ptr::write(prev, value);
}
}
fn set_next(&mut self, value: Option<NonNull<T>>) {
unsafe {
let inner = self.inner.get();
let prev = inner as *mut Option<NonNull<T>>;
let next = prev.add(1);
ptr::write(next, value);
}
}
}
impl<T> fmt::Debug for Pointers<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let prev = self.get_prev();
let next = self.get_next();
f.debug_struct("Pointers")
.field("prev", &prev)
.field("next", &next)
.finish()
}
}