rust-galmon-web/src/utils/local_dl_list.rs

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};
	};
}