258 lines
6.2 KiB
Rust
258 lines
6.2 KiB
Rust
|
use std::cell::Cell;
|
||
|
use std::ptr;
|
||
|
|
||
|
#[doc(hidden)]
|
||
|
#[derive(Debug)]
|
||
|
pub struct LocalDLHead {
|
||
|
prev: Cell<*const LocalDLHead>,
|
||
|
next: Cell<*const LocalDLHead>,
|
||
|
}
|
||
|
|
||
|
impl LocalDLHead {
|
||
|
// only internal use, no need for Default trait
|
||
|
pub const fn new() -> Self {
|
||
|
Self {
|
||
|
prev: Cell::new(ptr::null()),
|
||
|
next: Cell::new(ptr::null()),
|
||
|
}
|
||
|
}
|
||
|
|
||
|
pub fn init(&self) {
|
||
|
if self.next.get().is_null() {
|
||
|
self.next.set(self);
|
||
|
self.prev.set(self);
|
||
|
}
|
||
|
}
|
||
|
|
||
|
pub fn is_unlinked(&self) -> bool {
|
||
|
self.next.get().is_null() || self.next.get() == (self as _)
|
||
|
}
|
||
|
|
||
|
pub unsafe fn unlink(&self) {
|
||
|
if !self.is_unlinked() {
|
||
|
/* unsafe */ { &*self.prev.get() }.next.set(self.next.get());
|
||
|
/* unsafe */ { &*self.next.get() }.prev.set(self.prev.get());
|
||
|
}
|
||
|
self.next.set(ptr::null());
|
||
|
self.prev.set(ptr::null());
|
||
|
}
|
||
|
|
||
|
pub unsafe fn insert_after(&self, node: &Self) {
|
||
|
debug_assert!(node.is_unlinked());
|
||
|
assert_ne!(self as *const _, node as *const _);
|
||
|
self.init();
|
||
|
node.next.set(self.next.get());
|
||
|
node.prev.set(self);
|
||
|
/* unsafe */ { &*node.next.get() }.prev.set(node);
|
||
|
self.next.set(node);
|
||
|
}
|
||
|
|
||
|
pub unsafe fn insert_before(&self, node: &Self) {
|
||
|
debug_assert!(node.is_unlinked());
|
||
|
assert_ne!(self as *const _, node as *const _);
|
||
|
self.init();
|
||
|
node.next.set(self);
|
||
|
node.prev.set(self.prev.get());
|
||
|
/* unsafe */ { &*node.prev.get() }.next.set(node);
|
||
|
self.prev.set(node);
|
||
|
}
|
||
|
|
||
|
pub unsafe fn next(&self) -> Option<*const Self> {
|
||
|
if self.is_unlinked() {
|
||
|
return None;
|
||
|
}
|
||
|
let node = self.next.get();
|
||
|
Some(node)
|
||
|
}
|
||
|
|
||
|
pub unsafe fn pop_front(&self) -> Option<*const Self> {
|
||
|
if self.is_unlinked() {
|
||
|
return None;
|
||
|
}
|
||
|
let node = self.next.get();
|
||
|
/* unsafe */ { &*node }.unlink();
|
||
|
Some(node)
|
||
|
}
|
||
|
|
||
|
pub unsafe fn prev(&self) -> Option<*const Self> {
|
||
|
if self.is_unlinked() {
|
||
|
return None;
|
||
|
}
|
||
|
let node = self.prev.get();
|
||
|
Some(node)
|
||
|
}
|
||
|
|
||
|
pub unsafe fn pop_back(&self) -> Option<*const Self> {
|
||
|
if self.is_unlinked() {
|
||
|
return None;
|
||
|
}
|
||
|
let node = self.prev.get();
|
||
|
/* unsafe */ { &*node }.unlink();
|
||
|
Some(node)
|
||
|
}
|
||
|
|
||
|
pub unsafe fn take_from(&mut self, other: &Self) {
|
||
|
debug_assert!(self.is_unlinked());
|
||
|
if !other.is_unlinked() {
|
||
|
other.insert_after(self);
|
||
|
other.unlink();
|
||
|
}
|
||
|
}
|
||
|
}
|
||
|
|
||
|
impl Default for LocalDLHead {
|
||
|
fn default() -> Self {
|
||
|
Self::new()
|
||
|
}
|
||
|
}
|
||
|
|
||
|
impl Drop for LocalDLHead {
|
||
|
fn drop(&mut self) {
|
||
|
assert!(self.is_unlinked());
|
||
|
}
|
||
|
}
|
||
|
|
||
|
macro_rules! local_dl_list {
|
||
|
(mod $($tt:tt)*) => {
|
||
|
_local_dl_list! {
|
||
|
[pub(self)] [pub(super)] mod $($tt)*
|
||
|
}
|
||
|
};
|
||
|
(pub mod $($tt:tt)*) => {
|
||
|
_local_dl_list! {
|
||
|
[pub] [pub] mod $($tt)*
|
||
|
}
|
||
|
};
|
||
|
(pub(crate) mod $($tt:tt)*) => {
|
||
|
_local_dl_list! {
|
||
|
[pub(crate)] [pub(crate)] mod $($tt)*
|
||
|
}
|
||
|
};
|
||
|
}
|
||
|
|
||
|
#[doc(hidden)]
|
||
|
macro_rules! _local_dl_list {
|
||
|
([$vis:vis] [$innervis:vis] mod $modname:ident {
|
||
|
link $link_name:ident;
|
||
|
head $head_name:ident;
|
||
|
member $member:ident of $parent:ident;
|
||
|
}) => {
|
||
|
mod $modname {
|
||
|
use super::$parent;
|
||
|
use $crate::utils::local_dl_list::LocalDLHead;
|
||
|
use core::marker::PhantomData;
|
||
|
|
||
|
#[derive(Debug)]
|
||
|
$innervis struct $link_name<T> {
|
||
|
head: LocalDLHead,
|
||
|
_mark: PhantomData<T>,
|
||
|
}
|
||
|
|
||
|
#[allow(dead_code)]
|
||
|
impl<T> $link_name<T> {
|
||
|
fn __base_from_node(ptr: *const LocalDLHead) -> *const $parent<T> {
|
||
|
let member_offset: usize = {
|
||
|
let p = core::ptr::NonNull::<$parent<T>>::dangling();
|
||
|
let $parent::<T> { $member: member, .. } = unsafe { &*p.as_ptr() };
|
||
|
let head: &LocalDLHead = &member.head;
|
||
|
(head as *const _ as usize) - (p.as_ptr() as *const _ as usize)
|
||
|
};
|
||
|
unsafe { (ptr as *const u8).sub(member_offset) as *const $parent<T> }
|
||
|
}
|
||
|
|
||
|
$innervis const fn new() -> Self {
|
||
|
Self {
|
||
|
head: LocalDLHead::new(),
|
||
|
_mark: PhantomData,
|
||
|
}
|
||
|
}
|
||
|
|
||
|
$innervis fn is_unlinked(&self) -> bool {
|
||
|
self.head.is_unlinked()
|
||
|
}
|
||
|
|
||
|
$innervis unsafe fn unlink(&self) {
|
||
|
self.head.unlink();
|
||
|
}
|
||
|
|
||
|
$innervis unsafe fn insert_after(&self, node: &$parent<T>) {
|
||
|
let node_link: &Self = &node.$member;
|
||
|
self.head.insert_after(&node_link.head);
|
||
|
}
|
||
|
|
||
|
$innervis unsafe fn insert_before(&self, node: &$parent<T>) {
|
||
|
let node_link: &Self = &node.$member;
|
||
|
self.head.insert_before(&node_link.head);
|
||
|
}
|
||
|
}
|
||
|
|
||
|
#[derive(Debug)]
|
||
|
$innervis struct $head_name<T> {
|
||
|
head: LocalDLHead,
|
||
|
_mark: PhantomData<T>,
|
||
|
}
|
||
|
|
||
|
#[allow(dead_code)]
|
||
|
impl<T> $head_name<T> {
|
||
|
$innervis const fn new() -> Self {
|
||
|
Self {
|
||
|
head: LocalDLHead::new(),
|
||
|
_mark: PhantomData,
|
||
|
}
|
||
|
}
|
||
|
|
||
|
$innervis fn is_empty(&self) -> bool {
|
||
|
self.head.is_unlinked()
|
||
|
}
|
||
|
|
||
|
$innervis unsafe fn prepend(&self, node: &$parent<T>) {
|
||
|
let node_link: &$link_name<T> = &node.$member;
|
||
|
self.head.insert_after(&node_link.head);
|
||
|
}
|
||
|
|
||
|
$innervis unsafe fn append(&self, node: &$parent<T>) {
|
||
|
let node_link: &$link_name<T> = &node.$member;
|
||
|
self.head.insert_before(&node_link.head);
|
||
|
}
|
||
|
|
||
|
$innervis unsafe fn front(&self) -> Option<*const $parent<T>> {
|
||
|
let node_link = self.head.next()?;
|
||
|
Some($link_name::<T>::__base_from_node(node_link))
|
||
|
}
|
||
|
|
||
|
$innervis unsafe fn back(&self) -> Option<*const $parent<T>> {
|
||
|
let node_link = self.head.prev()?;
|
||
|
Some($link_name::<T>::__base_from_node(node_link))
|
||
|
}
|
||
|
|
||
|
$innervis unsafe fn next(&self, node: &$parent<T>) -> Option<*const $parent<T>> {
|
||
|
let node_link = node.$member.head.next()?;
|
||
|
if node_link as *const LocalDLHead == &self.head as *const LocalDLHead { return None; }
|
||
|
Some($link_name::<T>::__base_from_node(node_link))
|
||
|
}
|
||
|
|
||
|
$innervis unsafe fn prev(&self, node: &$parent<T>) -> Option<*const $parent<T>> {
|
||
|
let node_link = node.$member.head.prev()?;
|
||
|
if node_link as *const LocalDLHead == &self.head as *const LocalDLHead { return None; }
|
||
|
Some($link_name::<T>::__base_from_node(node_link))
|
||
|
}
|
||
|
|
||
|
$innervis unsafe fn pop_front(&self) -> Option<*const $parent<T>> {
|
||
|
let node_link = self.head.pop_front()?;
|
||
|
Some($link_name::<T>::__base_from_node(node_link))
|
||
|
}
|
||
|
|
||
|
$innervis unsafe fn pop_back(&self) -> Option<*const $parent<T>> {
|
||
|
let node_link = self.head.pop_back()?;
|
||
|
Some($link_name::<T>::__base_from_node(node_link))
|
||
|
}
|
||
|
|
||
|
$innervis unsafe fn take_from(&mut self, other: &Self) {
|
||
|
self.head.take_from(&other.head);
|
||
|
}
|
||
|
}
|
||
|
}
|
||
|
$vis use self::$modname::{$link_name, $head_name};
|
||
|
};
|
||
|
}
|