unsafe_list 0.1.57

//! Linux 风格侵入式双向链表
//!
//! 对标 Linux 内核 `<linux/list.h>` 的 `list_head` 实现。
//! 操作对象均为裸指针，无并发支持，无所有权语义。
//!
//! # Safety
//!
//! 所有公开 `unsafe` 方法均要求：
//! - 节点生命周期长于链表引用
//! - 无并发访问，或由调用方自行同步
#![no_std]
#![allow(unsafe_code)]

/// 已删除节点的 next 哨兵值（use-after-free 检测）
pub const LIST_POISON1: usize = 0xdead0100;
/// 已删除节点的 prev 哨兵值（use-after-free 检测）
pub const LIST_POISON2: usize = 0xdead0200;

/// 侵入式双向链表头
#[derive(Clone, Copy)]
pub struct UnsafeListHead<T> {
    next: *mut UnsafeListNode<T>,
    prev: *mut UnsafeListNode<T>,
    offset: usize,
}

impl<T> Default for UnsafeListHead<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> UnsafeListHead<T> {
    /// 构造链表头（未初始化），需调用 [`init_list_head`](Self::init_list_head) 后使用
    pub const fn new() -> Self {
        let init = core::ptr::null_mut::<UnsafeListNode<T>>();
        Self { next: init, prev: init, offset: 0 }
    }

    #[inline(always)]
    fn head_node(&self) -> *mut UnsafeListNode<T> {
        core::ptr::from_ref(self).cast_mut().cast()
    }

    #[inline(always)]
    unsafe fn container_of(&self, node: *const UnsafeListNode<T>) -> *const T {
        unsafe { node.byte_sub(self.offset).cast() }
    }

    #[inline(always)]
    unsafe fn container_of_mut(&self, node: *mut UnsafeListNode<T>) -> *mut T {
        unsafe { node.byte_sub(self.offset).cast() }
    }

    /// 初始化链表头，`offset` 为节点字段在包含结构体中的偏移
    pub fn init_list_head(&mut self, offset: usize) {
        let ptr = self.head_node();
        unsafe {
            core::ptr::write_volatile(&raw mut self.next, ptr);
        }
        self.prev = ptr;
        self.offset = offset;
    }

    #[inline(always)]
    unsafe fn __list_add(
        new: &mut UnsafeListNode<T>,
        prev: &mut UnsafeListNode<T>,
        next: &mut UnsafeListNode<T>,
    ) {
        next.prev = new;
        new.next = next;
        new.prev = prev;
        unsafe {
            core::ptr::write_volatile(&raw mut prev.next, new);
        }
    }

    /// 在链表头部插入节点
    ///
    /// # Safety
    /// 见模块文档
    #[inline(always)]
    pub unsafe fn list_add(&mut self, new: &mut UnsafeListNode<T>) {
        unsafe {
            Self::__list_add(new, &mut *self.head_node(), &mut *self.next);
        }
    }

    /// 在链表尾部插入节点
    ///
    /// # Safety
    /// 见模块文档
    #[inline(always)]
    pub unsafe fn list_add_tail(&mut self, new: &mut UnsafeListNode<T>) {
        unsafe {
            Self::__list_add(new, &mut *self.prev, &mut *self.head_node());
        }
    }

    /// 判断节点是否为链表最后一个元素
    ///
    /// # Safety
    /// 见模块文档
    #[inline(always)]
    pub unsafe fn list_is_last(&self, list: &UnsafeListNode<T>) -> bool {
        core::ptr::eq(list.next, self.head_node())
    }

    /// 判断链表是否为空（volatile 读取 next）
    ///
    /// # Safety
    /// 见模块文档
    #[inline(always)]
    pub unsafe fn list_empty(&self) -> bool {
        unsafe {
            let next = core::ptr::read_volatile(&raw const self.next);
            core::ptr::eq(next, self.head_node())
        }
    }

    /// 判断链表是否为空（同时检查 next 和 prev）
    ///
    /// # Safety
    /// 见模块文档
    #[inline(always)]
    pub unsafe fn list_empty_careful(&self) -> bool {
        unsafe {
            let next = core::ptr::read_volatile(&raw const self.next);
            core::ptr::eq(next, self.head_node()) && core::ptr::eq(next, self.prev)
        }
    }

    /// 获取第一个元素，空链表返回 `None`
    ///
    /// # Safety
    /// 见模块文档
    #[inline(always)]
    pub unsafe fn list_first_entry_or_null(&self) -> Option<&T> {
        if core::ptr::eq(self.next, self.head_node()) {
            None
        } else {
            Some(unsafe { &*self.container_of(self.next) })
        }
    }

    /// 获取第一个元素的可变引用，空链表返回 `None`
    ///
    /// # Safety
    /// 见模块文档
    #[inline(always)]
    pub unsafe fn list_first_entry_or_null_mut(&mut self) -> Option<&mut T> {
        if core::ptr::eq(self.next, self.head_node()) {
            None
        } else {
            Some(unsafe { &mut *self.container_of_mut(self.next) })
        }
    }

    /// 获取第一个元素（调用方需确保链表非空）
    ///
    /// # Safety
    /// 见模块文档，且链表必须非空
    #[inline(always)]
    pub unsafe fn list_first_entry(&self) -> &T {
        unsafe { &*self.container_of(self.next) }
    }

    /// 获取第一个元素的可变引用（调用方需确保链表非空）
    ///
    /// # Safety
    /// 见模块文档，且链表必须非空
    #[inline(always)]
    pub unsafe fn list_first_entry_mut(&mut self) -> &mut T {
        unsafe { &mut *self.container_of_mut(self.next) }
    }

    /// 获取最后一个元素（调用方需确保链表非空）
    ///
    /// # Safety
    /// 见模块文档，且链表必须非空
    #[inline(always)]
    pub unsafe fn list_last_entry(&self) -> &T {
        unsafe { &*self.container_of(self.prev) }
    }

    /// 获取最后一个元素的可变引用（调用方需确保链表非空）
    ///
    /// # Safety
    /// 见模块文档，且链表必须非空
    #[inline(always)]
    pub unsafe fn list_last_entry_mut(&mut self) -> &mut T {
        unsafe { &mut *self.container_of_mut(self.prev) }
    }
}

/// 初始化链表头
#[macro_export]
macro_rules! init_unsafe_list_head {
    ($var:ident, $type:ty, $($member:tt).+ $(,)?) => {
        $var.init_list_head(core::mem::offset_of!($type, $($member).+));
    };
}

/// 定义并初始化链表头
#[macro_export]
macro_rules! define_unsafe_list_head {
    ($var:ident, $type:ty, $($member:tt).+ $(,)?) => {
        let mut $var = $crate::UnsafeListHead::<$type>::new();
        $crate::init_unsafe_list_head!($var, $type, $($member).+);
    };
}

/// 侵入式双向链表节点
#[derive(Clone, Copy)]
pub struct UnsafeListNode<T> {
    next: *mut UnsafeListNode<T>,
    prev: *mut UnsafeListNode<T>,
}

impl<T> Default for UnsafeListNode<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> UnsafeListNode<T> {
    /// 构造链表节点（null 指针，嵌入结构体后由链表操作初始化）
    pub const fn new() -> Self {
        let init = core::ptr::null_mut::<UnsafeListNode<T>>();
        Self { next: init, prev: init }
    }

    #[inline(always)]
    unsafe fn init_list_node(&mut self) {
        let value = self as *mut UnsafeListNode<T>;
        unsafe {
            core::ptr::write_volatile(&raw mut self.next, value);
        }
        self.prev = value;
    }

    #[inline(always)]
    unsafe fn __list_del(prev: &mut UnsafeListNode<T>, next: &mut UnsafeListNode<T>) {
        next.prev = prev;
        unsafe {
            core::ptr::write_volatile(&raw mut prev.next, next);
        }
    }

    #[inline(always)]
    unsafe fn __list_del_entry(&mut self) {
        unsafe {
            Self::__list_del(&mut *self.prev, &mut *self.next);
        }
    }

    /// 从链表中删除节点，指针置为 poison 值
    ///
    /// # Safety
    /// 见模块文档
    #[inline(always)]
    pub unsafe fn list_del(&mut self) {
        unsafe {
            self.__list_del_entry();
        }
        self.next = LIST_POISON1 as *mut UnsafeListNode<T>;
        self.prev = LIST_POISON2 as *mut UnsafeListNode<T>;
    }

    /// 用 `new` 替换当前节点在链表中的位置
    ///
    /// # Safety
    /// 见模块文档
    #[inline(always)]
    pub unsafe fn list_replace(&mut self, new: &mut UnsafeListNode<T>) {
        unsafe {
            new.next = self.next;
            (*new.next).prev = new;
            new.prev = self.prev;
            (*new.prev).next = new;
        }
    }

    /// 用 `new` 替换当前节点，并将当前节点重新初始化为自引用
    ///
    /// # Safety
    /// 见模块文档
    #[inline(always)]
    pub unsafe fn list_replace_init(&mut self, new: &mut UnsafeListNode<T>) {
        unsafe {
            self.list_replace(new);
            self.init_list_node();
        }
    }

    /// 从链表中删除节点，并重新初始化为自引用
    ///
    /// # Safety
    /// 见模块文档
    #[inline(always)]
    pub unsafe fn list_del_init(&mut self) {
        unsafe {
            self.__list_del_entry();
            self.init_list_node();
        }
    }

    /// 将节点移动到另一个链表的头部
    ///
    /// # Safety
    /// 见模块文档
    #[inline(always)]
    pub unsafe fn list_move(&mut self, head: &mut UnsafeListHead<T>) {
        unsafe {
            self.__list_del_entry();
            head.list_add(self);
        }
    }

    /// 将节点移动到另一个链表的尾部
    ///
    /// # Safety
    /// 见模块文档
    #[inline(always)]
    pub unsafe fn list_move_tail(&mut self, head: &mut UnsafeListHead<T>) {
        unsafe {
            self.__list_del_entry();
            head.list_add_tail(self);
        }
    }
}

/// 不可变迭代器
pub struct UnsafeListHeadIter<'a, T> {
    front: *const UnsafeListNode<T>,
    back: *const UnsafeListNode<T>,
    head: &'a UnsafeListHead<T>,
}

impl<'a, T> UnsafeListHeadIter<'a, T> {
    fn new(head: &'a UnsafeListHead<T>) -> Self {
        Self { front: head.next.cast_const(), back: head.prev.cast_const(), head }
    }
}

impl<T> UnsafeListHead<T> {
    /// 创建不可变迭代器
    pub fn iter(&self) -> UnsafeListHeadIter<'_, T> {
        UnsafeListHeadIter::new(self)
    }
}

impl<'a, T> IntoIterator for &'a UnsafeListHead<T> {
    type IntoIter = UnsafeListHeadIter<'a, T>;
    type Item = &'a T;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, T> Iterator for UnsafeListHeadIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        unsafe {
            let sentinel = self.head.head_node().cast_const();
            if self.front == sentinel {
                return None;
            }
            let node = self.front;
            if self.front == self.back {
                self.front = sentinel;
                self.back = sentinel;
            } else {
                self.front = (*self.front).next.cast_const();
            }
            Some(&*self.head.container_of(node))
        }
    }
}

impl<'a, T> DoubleEndedIterator for UnsafeListHeadIter<'a, T> {
    fn next_back(&mut self) -> Option<&'a T> {
        unsafe {
            let sentinel = self.head.head_node().cast_const();
            if self.back == sentinel {
                return None;
            }
            let node = self.back;
            if self.front == self.back {
                self.front = sentinel;
                self.back = sentinel;
            } else {
                self.back = (*self.back).prev.cast_const();
            }
            Some(&*self.head.container_of(node))
        }
    }
}

/// 可变迭代器
pub struct UnsafeListHeadIterMut<'a, T> {
    front: *mut UnsafeListNode<T>,
    back: *mut UnsafeListNode<T>,
    head: &'a mut UnsafeListHead<T>,
}

impl<'a, T> UnsafeListHeadIterMut<'a, T> {
    fn new(head: &'a mut UnsafeListHead<T>) -> Self {
        Self { front: head.next, back: head.prev, head }
    }
}

impl<T> UnsafeListHead<T> {
    /// 创建可变迭代器
    pub fn iter_mut(&mut self) -> UnsafeListHeadIterMut<'_, T> {
        UnsafeListHeadIterMut::new(self)
    }
}

impl<'a, T> IntoIterator for &'a mut UnsafeListHead<T> {
    type IntoIter = UnsafeListHeadIterMut<'a, T>;
    type Item = &'a mut T;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

impl<'a, T> Iterator for UnsafeListHeadIterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        unsafe {
            let sentinel = self.head.head_node();
            if self.front == sentinel {
                return None;
            }
            let node = self.front;
            if self.front == self.back {
                self.front = sentinel;
                self.back = sentinel;
            } else {
                self.front = (*self.front).next;
            }
            Some(&mut *self.head.container_of_mut(node))
        }
    }
}

impl<'a, T> DoubleEndedIterator for UnsafeListHeadIterMut<'a, T> {
    fn next_back(&mut self) -> Option<&'a mut T> {
        unsafe {
            let sentinel = self.head.head_node();
            if self.back == sentinel {
                return None;
            }
            let node = self.back;
            if self.front == self.back {
                self.front = sentinel;
                self.back = sentinel;
            } else {
                self.back = (*self.back).prev;
            }
            Some(&mut *self.head.container_of_mut(node))
        }
    }
}