//! A doubly-linked list of power-of-two-sized subregions.

use core::{
    fmt,
    marker::PhantomPinned,
    pin::Pin,
    ptr::{self, NonNull},
};

/// The magic number a non-sentinel node should have.
const FREE_NODE_MAGIC: u64 = u64::from_ne_bytes(*b"FREENODE");

/// The magic number a sentinel node should have.
const SENTINEL_MAGIC: u64 = u64::from_ne_bytes(*b"SENTINEL");

/// A doubly-linked list of power-of-two-sized subregions.
///
/// This type is valid when zero-initialized.
///
/// # Safety
///
/// - This type is valid only if it is zero-initialized or if it contains a valid doubly-linked
///   list of subregions of the correct size, which it owns.
pub struct FreeList {
    sentinel: FreeListNode,
}

impl FreeList {
    /// Pushes a subregion into the free-list.
    ///
    /// # Safety
    ///
    /// - `subregion_ptr` must convey ownership over untyped memory of the correct size.
    pub unsafe fn push(mut self: Pin<&mut FreeList>, subregion_ptr: NonNull<u8>) {
        assert_ne!(self.sentinel.next, ptr::null_mut());
        assert_ne!(self.sentinel.prev, ptr::null_mut());

        // Write the header the node should have to the node.
        let sentinel = &self.sentinel as *const FreeListNode as *mut FreeListNode;
        let next = *self.as_mut().sentinel().next_mut();
        let node = subregion_ptr.cast();
        node.write(FreeListNode {
            next,
            prev: sentinel,
            magic: FREE_NODE_MAGIC,
            _phantom: PhantomPinned,
        });

        // Link the node into the list.
        *self.sentinel().next_mut() = node.as_ptr();
        (*next).prev = node.as_ptr();
    }

    /// Performs self-linking. This must be done before the free list is used in any other way.
    pub fn self_link(self: Pin<&mut FreeList>) {
        assert_eq!(self.sentinel.next, ptr::null_mut());
        assert_eq!(self.sentinel.prev, ptr::null_mut());

        let mut sentinel = self.sentinel_unchecked();
        // SAFETY: We do not use this pointer to move out of the sentinel.
        let sentinel_ptr = unsafe { sentinel.as_mut().get_unchecked_mut() as *mut FreeListNode };
        *sentinel.as_mut().next_mut() = sentinel_ptr;
        *sentinel.as_mut().prev_mut() = sentinel_ptr;
        *sentinel.as_mut().magic_mut() = SENTINEL_MAGIC;
    }

    /// Projects the sentinel node out of the list.
    fn sentinel(self: Pin<&mut FreeList>) -> Pin<&mut FreeListNode> {
        let mut sentinel = self.sentinel_unchecked();
        assert_eq!(*sentinel.as_mut().magic_mut(), SENTINEL_MAGIC);
        sentinel
    }

    /// Projects the sentinel node out of the list, without checking the magic number.
    fn sentinel_unchecked(self: Pin<&mut FreeList>) -> Pin<&mut FreeListNode> {
        // SAFETY: sentinel is structurally pinned.
        unsafe { self.map_unchecked_mut(|list| &mut list.sentinel) }
    }
}

/// This impl will panic until the sentinel has been self-linked.
impl fmt::Debug for FreeList {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        assert_ne!(self.sentinel.next, ptr::null_mut());
        assert_ne!(self.sentinel.prev, ptr::null_mut());

        let sentinel = &self.sentinel as *const FreeListNode;

        // SAFETY: The invariants of FreeList guarantee that the list is valid. In a valid list,
        // the next pointer is always valid and non-null.
        let mut ptr = unsafe { sentinel.as_ref().unwrap().next as *const FreeListNode };
        let mut fmt = fmt.debug_list();
        while ptr != sentinel {
            fmt.entry(&ptr);
            // SAFETY: The invariants of FreeList guarantee that the list is valid. In a valid
            // list, the next pointer is always valid and non-null.
            ptr = unsafe { ptr.as_ref().unwrap().next as *const FreeListNode };
        }
        fmt.finish()
    }
}

#[derive(Debug)]
struct FreeListNode {
    next: *mut FreeListNode,
    prev: *mut FreeListNode,
    magic: u64,
    _phantom: PhantomPinned,
}

impl FreeListNode {
    /// Projects the `next` pointer out of the node.
    fn next_mut(self: Pin<&mut FreeListNode>) -> &mut *mut FreeListNode {
        // SAFETY: next is not structurally pinned.
        unsafe { &mut self.get_unchecked_mut().next }
    }

    /// Projects the `prev` pointer out of the node.
    fn prev_mut(self: Pin<&mut FreeListNode>) -> &mut *mut FreeListNode {
        // SAFETY: prev is structurally pinned.
        unsafe { &mut self.get_unchecked_mut().prev }
    }

    /// Projects the `magic` number out of the node.
    fn magic_mut(self: Pin<&mut FreeListNode>) -> &mut u64 {
        // SAFETY: magic is structurally pinned.
        unsafe { &mut self.get_unchecked_mut().magic }
    }
}