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

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

use contracts::requires;

/// 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");

/// The magic number set into the spot for a node's magic number when it gets unlinked.
const USED_NODE_MAGIC: u64 = u64::from_ne_bytes(*b"ALLOC'ED");

/// A circular 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 circular
///   doubly-linked list of subregions of the correct size, which it owns.
pub struct FreeList {
    sentinel: FreeListNode,
}

impl FreeList {
    /// Pops a subregion from the free-list, returning ownership to the caller.
    pub fn pop(mut self: Pin<&mut FreeList>) -> Option<NonNull<u8>> {
        assert_ne!(self.sentinel.next, ptr::null_mut());
        assert_ne!(self.sentinel.prev, ptr::null_mut());

        // Check if the sentinel's next pointer points to the sentinel itself.
        let sentinel = &self.sentinel as *const FreeListNode as *mut FreeListNode;
        let next = *self.as_mut().sentinel().next_mut();
        if sentinel == next {
            // If so, the list is empty.
            None
        } else {
            // Otherwise, unlink that node.
            //
            // UNWRAP: The pointer was non-null, by the invariants of FreeList.
            let mut node = NonNull::new(next).unwrap();
            // SAFETY: The list was valid, by the invariants of FreeList.
            unsafe { node.as_mut().unlink() };
            Some(node.cast())
        }
    }

    /// 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.
        //
        // SAFETY: This &mut is not used to move out of the node.
        let sentinel = unsafe { self.as_mut().sentinel().get_unchecked_mut() };
        let mut node = subregion_ptr.cast();
        node.write(FreeListNode {
            next: sentinel.next,
            prev: sentinel,
            magic: FREE_NODE_MAGIC,
            _phantom: PhantomPinned,
        });

        // Link the node into the list.
        //
        // SAFETY: There are no other references to the node live.
        let node = unsafe { node.as_mut() };
        (*node.prev).next = node;
        (*node.next).prev = node;
    }

    /// 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 }
    }

    /// Links the node into a circular doubly-linked list.
    ///
    /// # Safety
    ///
    /// This must be a node that's not part of any linked list.
    unsafe fn link(&mut self) {
        todo!()
    }

    /// Unlinks a node from a circular doubly-linked list.
    ///
    /// # Safety
    ///
    /// This must be a non-sentinel node in a valid circular doubly-linked list.
    #[requires(self.magic == FREE_NODE_MAGIC)]
    #[ensures(self.magic == USED_NODE_MAGIC)]
    unsafe fn unlink(&mut self) {
        let prev = self.prev;
        let next = self.next;

        use core::ptr::addr_of_mut;
        *addr_of_mut!((*prev).next) = next;
        *addr_of_mut!((*next).prev) = prev;

        self.next = ptr::null_mut();
        self.prev = ptr::null_mut();
        self.magic = USED_NODE_MAGIC;
    }
}