intrusive_list.rs (not working)

intrusive_list.rs

use core::{marker::PhantomData, ptr::NonNull};
use memoffset::offset_of;

/// An intrusive doubly-linked list node.
pub struct ListNode<T> {
    /// The previous node. It points to itself if the list has only sigle entry.
    prev: NonNull<ListNode<T>>,
    /// The next node. It points to itself if the list has only sigle entry.
    next: NonNull<ListNode<T>>,
    _pd: PhantomData<T>,
}

impl<T> ListNode<T> {
    pub fn remove_from_list(&mut self) {
        unsafe {
            remove_node(NonNull::new_unchecked(self));
        }
    }
}

/// Inserts `new` between `prev` and `next`.
unsafe fn insert_node<P: FixedPointer>(
    mut prev: NonNull<ListNode<P>>,
    mut next: NonNull<ListNode<P>>,
    mut new: NonNull<ListNode<P>>,
) {
    // println!("insert: prev={:x?}, next={:x?}, new={:x?}", prev, next, new);
    new.as_mut().prev = prev;
    new.as_mut().next = next;
    next.as_mut().prev = new;
    prev.as_mut().next = new;
}

/// Removes the node from the lsit.
unsafe fn remove_node<T>(mut node: NonNull<ListNode<T>>) {
    // println!(
    //     "remove: node={:x?}, prev={:x?}, next={:x?}",
    //     node,
    //     node.as_ref().prev,
    //     node.as_ref().next
    // );
    let node = node.as_mut();
    let node_next = node.next;
    let node_prev = node.prev;
    node_prev.clone().as_mut().next = node_next;
    node_next.clone().as_mut().prev = node_prev;

    node.prev = NonNull::dangling();
    node.next = NonNull::dangling();
}

/// Returns the container of a node.
unsafe fn container_of_node<P: FixedPointer>(node: NonNull<ListNode<P>>, offset: usize) -> P {
    P::from_fixed_ptr((node.as_ptr() as *const u8).sub(offset))
}

/// Returns the node at `offset` in the container.
unsafe fn node_in_container<P: FixedPointer>(entry: P, offset: usize) -> NonNull<ListNode<P>> {
    NonNull::new_unchecked(entry.as_fixed_ptr().add(offset) as *mut ListNode<P>)
}

macro_rules! define_linked_list {
    (Rc<SpinLock<$st:ident>>, $field:ident) => {
        crate::utils::linked_list::LinkedList<Rc<SpinLock<$st>>, { unsafe { memoffset::offset_of!($st, $field) }  }>
    };
    (NonNull<$st:ident>, $field:ident) => {
        crate::utils::linked_list::LinkedList<NonNull<$st>, { unsafe { memoffset::offset_of!($st, $field) }  }>
    };
}

/// A intrusive doubly-linked list.
pub struct LinkedList<P: FixedPointer, const N: usize> {
    head: Option<NonNull<ListNode<P>>>,
    tail: Option<NonNull<ListNode<P>>>,
    /// The number of entries in the list.
    len: usize,
    _pd: PhantomData<P>,
}

impl<P: FixedPointer, const N: usize> LinkedList<P, N> {
    /// Creates a list. *DON'T USE THIS DIRECTLY -- use `linked_list!` instead.*.
    pub const fn new() -> LinkedList<P, N> {
        LinkedList {
            head: None,
            tail: None,
            len: 0,
            _pd: PhantomData,
        }
    }

    /// Returns `true` if the list is empty.
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// The number of entries in the list.
    pub fn len(&self) -> usize {
        self.len
    }

    /// Appends an entry at the end of the list.
    pub fn push_back(&mut self, entry: P) {
        unsafe {
            let node = node_in_container(entry, N);
            let prev = if let Some(tail) = self.tail {
                tail
            } else {
                node
            };

            let next = if let Some(head) = self.head {
                head
            } else {
                node
            };

            insert_node(prev, next, node);

            if self.head.is_none() {
                self.head = Some(node);
            }
            self.tail = Some(node);
            self.len += 1;
        }
    }

    /// Gets and removes the first entry of the list.
    pub fn pop_front(&mut self) -> Option<P> {
        unsafe {
            self.head.take().map(|head| {
                let ListNode { prev, next, .. } = head.as_ref();
                self.len -= 1;
                if self.len == 0 {
                    self.head = None;
                    self.tail = None;
                } else {
                    self.head = Some(*next);
                    self.tail = Some(*prev);
                }

                // Don't remove `head` before updating fields -- `remove_node`
                // clears `prev` and `next` with invalid pointers!
                drop(next);
                drop(prev);
                remove_node(head);
                container_of_node(head, N)
            })
        }
    }

    /// Returns a head-to-tail iterator.
    pub fn iter(&self) -> Iter<'_, P, N> {
        Iter {
            current: self.head,
            list: self,
        }
    }
}

pub struct Iter<'a, P: FixedPointer, const N: usize> {
    current: Option<NonNull<ListNode<P>>>,
    list: &'a LinkedList<P, N>,
}

impl<'a, P: FixedPointer, const N: usize> Iterator for Iter<'a, P, N> {
    type Item = P;
    fn next(&mut self) -> Option<Self::Item> {
        unsafe {
            let current = self.current?;
            if Some(current) == self.list.tail {
                self.current = None;
            } else {
                let next = Some(current.as_ref().next);
                self.current = next;
            }

            Some(container_of_node(current, N))
        }
    }
}

unsafe impl<P: FixedPointer, const N: usize> Send for LinkedList<P, N> {}
unsafe impl<P: FixedPointer, const N: usize> Sync for LinkedList<P, N> {}

/// A pointer type located at a fixed virtual memory address.
pub trait FixedPointer {
    fn from_fixed_ptr(ptr: *const u8) -> Self;
    fn as_fixed_ptr(&self) -> *const u8;
}

use crate::arch::SpinLock;
use crate::rc::Rc;

impl<T> FixedPointer for Rc<T> {
    fn from_fixed_ptr(ptr: *const u8) -> Self {
        todo!()
    }
    fn as_fixed_ptr(&self) -> *const u8 {
        // unsafe { self.inner_ptr().add(offset_of!(SpinLock<T>, inner)) }
        //
        todo!()
    }
}