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

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

/// 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.
#[derive(Debug)]
pub struct FreeList {
    sentinel: FreeListNode,
}

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

        let self_ptr = &self.sentinel as *const FreeListNode as *mut FreeListNode;
        let mut sentinel = self.sentinel_unchecked();
        *sentinel.as_mut().next_mut() = self_ptr;
        *sentinel.as_mut().prev_mut() = self_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) }
    }
}

#[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 }
    }
}