Skip to content

Instantly share code, notes, and snippets.

@nuta
Created May 10, 2021 16:45
Show Gist options
  • Save nuta/79d266914c16378721f8bac56b8f223a to your computer and use it in GitHub Desktop.
Save nuta/79d266914c16378721f8bac56b8f223a to your computer and use it in GitHub Desktop.
intrusive_list.rs (not working)
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!()
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment