unsafe_list 0.1.56

//! Unsafe list head 实现
//!
//! Unsafe list head 的实现是 linux 的 `list_head` 实现.
//! 这个模块是一个非常底层的接口, 没有并发支持, 没有所有权,
//! 操作的对象都是裸指针, 所有操作均是 unsafe 的.
//! 这个模块的实现只是为了方便实现 page alloc 接口.
#![no_std]
#![allow(unsafe_code, clippy::ptr_eq)]

/// 链表标识1
pub const LIST_POISON1: usize = 0xdead0100;
/// 链表标识2
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`初始化才能使用
    pub const fn new() -> Self {
        let init = core::ptr::null_mut::<UnsafeListNode<T>>();
        Self { next: init, prev: init, offset: 0 }
    }

    /// 初始化链表头
    pub fn init_list_head(&mut self, offset: usize) {
        let ptr = (self as *mut UnsafeListHead<T>).cast::<UnsafeListNode<T>>();
        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>,
    ) {
        unsafe {
            next.prev = new;
            new.next = next;
            new.prev = prev;
            core::ptr::write_volatile(&raw mut prev.next, new);
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_add(&mut self, new: &mut UnsafeListNode<T>) {
        unsafe {
            UnsafeListHead::__list_add(
                new,
                &mut *(self as *mut UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
                &mut *self.next,
            );
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_add_tail(&mut self, new: &mut UnsafeListNode<T>) {
        unsafe {
            UnsafeListHead::__list_add(
                new,
                &mut *self.prev,
                &mut *(self as *mut UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
            );
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_is_last(&self, list: &mut UnsafeListNode<T>) -> bool {
        core::ptr::eq(
            list.next.cast_const(),
            (self as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
        )
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_empty(&self) -> bool {
        unsafe {
            core::ptr::eq(
                core::ptr::read_volatile(&raw const self.next).cast_const(),
                (self as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
            )
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_empty_careful(&self) -> bool {
        let next = self.next.cast_const();
        next == (self as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>() && next == self.prev
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_first_entry_or_null(&self) -> Option<&T> {
        unsafe {
            let next = self.next;
            if core::ptr::eq(
                next.cast_const(),
                (self as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
            ) {
                None
            } else {
                Some(&*((next as usize - self.offset) as *const T))
            }
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_first_entry_or_null_mut(&mut self) -> Option<&mut T> {
        unsafe {
            let next = self.next;
            if next == (self as *mut UnsafeListHead<T>).cast::<UnsafeListNode<T>>() {
                None
            } else {
                Some(&mut *((next as usize - self.offset) as *mut T))
            }
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_first_entry_mut(&mut self) -> &mut T {
        unsafe { &mut *((self.next as usize - self.offset) as *mut T) }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_first_entry(&self) -> &T {
        unsafe { &*((self.next as usize - self.offset) as *const T) }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_last_entry_mut(&mut self) -> &mut T {
        unsafe { &mut *((self.prev as usize - self.offset) as *mut T) }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_last_entry(&self) -> &T {
        unsafe { &*((self.prev as usize - self.offset) as *const T) }
    }
}

/// 初始化链表头
#[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> {
    /// 构造一个链表节点
    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) {
        unsafe {
            let value = self as *mut UnsafeListNode<T>;
            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>) {
        unsafe {
            next.prev = prev;
            core::ptr::write_volatile(&raw mut prev.next, next);
        }
    }

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

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[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>;
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[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;
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_replace_init(&mut self, new: &mut UnsafeListNode<T>) {
        unsafe {
            self.list_replace(new);
            self.init_list_node();
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_del_init(&mut self) {
        unsafe {
            self.__list_del_entry();
            self.init_list_node();
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_move(&mut self, head: &mut UnsafeListHead<T>) {
        unsafe {
            self.__list_del_entry();
            head.list_add(self);
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[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> {
    prev_pos: *const UnsafeListNode<T>,
    next_pos: *const UnsafeListNode<T>,
    head: &'a UnsafeListHead<T>,
}

impl<'a, T> UnsafeListHeadIter<'a, T> {
    fn new(head: &'a UnsafeListHead<T>) -> Self {
        let init = core::ptr::null::<UnsafeListNode<T>>();
        Self { prev_pos: init, next_pos: init, 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 {
            if self.next_pos.is_null() {
                if self.head.list_empty() {
                    return None;
                }
                self.next_pos = (*self.head.next).next;
                return Some(self.head.list_first_entry());
            }

            let this = self.next_pos;
            let end = if self.prev_pos.is_null() {
                (self.head as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>()
            } else {
                self.prev_pos
            };
            if this == end {
                return None;
            }

            let val = &*((self.next_pos as usize - self.head.offset) as *const T);
            self.next_pos = (*self.next_pos).next;
            Some(val)
        }
    }
}

impl<'a, T> DoubleEndedIterator for UnsafeListHeadIter<'a, T> {
    fn next_back(&mut self) -> Option<&'a T> {
        unsafe {
            if self.prev_pos.is_null() {
                if self.head.list_empty() {
                    return None;
                }
                self.prev_pos = (*self.head.prev).prev;
                return Some(self.head.list_last_entry());
            }

            let this = self.prev_pos;
            let end = if self.next_pos.is_null() {
                (self.head as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>()
            } else {
                self.next_pos
            };
            if this == end {
                return None;
            }

            let val = &*((self.prev_pos as usize - self.head.offset) as *const T);
            self.prev_pos = (*self.prev_pos).prev;
            Some(val)
        }
    }
}

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

impl<'a, T> UnsafeListHeadIterMut<'a, T> {
    fn new(head: &'a mut UnsafeListHead<T>) -> Self {
        let init = core::ptr::null_mut::<UnsafeListNode<T>>();
        Self { prev_pos: init, next_pos: init, 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 {
            if self.next_pos.is_null() {
                if self.head.list_empty() {
                    return None;
                }
                self.next_pos = (*self.head.next).next;
                let this = self.head as *mut UnsafeListHead<T>;
                return Some((*this).list_first_entry_mut());
            }

            let this = self.next_pos.cast_const();
            let end = if self.prev_pos.is_null() {
                (self.head as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>()
            } else {
                self.prev_pos
            };
            if this == end {
                return None;
            }

            let val = &mut *((self.next_pos as usize - self.head.offset) as *mut T);
            self.next_pos = (*self.next_pos).next;
            Some(val)
        }
    }
}

impl<'a, T> DoubleEndedIterator for UnsafeListHeadIterMut<'a, T> {
    fn next_back(&mut self) -> Option<&'a mut T> {
        unsafe {
            if self.prev_pos.is_null() {
                if self.head.list_empty() {
                    return None;
                }
                self.prev_pos = (*self.head.prev).prev;
                let this = self.head as *mut UnsafeListHead<T>;
                return Some((*this).list_last_entry_mut());
            }

            let this = self.prev_pos.cast_const();
            let end = if self.next_pos.is_null() {
                (self.head as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>()
            } else {
                self.next_pos
            };
            if this == end {
                return None;
            }

            let val = &mut *((self.prev_pos as usize - self.head.offset) as *mut T);
            self.prev_pos = (*self.prev_pos).prev;
            Some(val)
        }
    }
}