//! A doubly-linked list where callers are in charge of memory allocation
//! of the nodes in the list.

#[cfg(test)]
mod tests;

use crate::mem;
use crate::ptr::NonNull;

pub struct UnsafeListEntry<T> {
    next: NonNull<UnsafeListEntry<T>>,
    prev: NonNull<UnsafeListEntry<T>>,
    value: Option<T>,
}

impl<T> UnsafeListEntry<T> {
    fn dummy() -> Self {
        UnsafeListEntry { next: NonNull::dangling(), prev: NonNull::dangling(), value: None }
    }

    pub fn new(value: T) -> Self {
        UnsafeListEntry { value: Some(value), ..Self::dummy() }
    }
}

// WARNING: self-referential struct!
pub struct UnsafeList<T> {
    head_tail: NonNull<UnsafeListEntry<T>>,
    head_tail_entry: Option<UnsafeListEntry<T>>,
}

impl<T> UnsafeList<T> {
    pub const fn new() -> Self {
        unsafe { UnsafeList { head_tail: NonNull::new_unchecked(1 as _), head_tail_entry: None } }
    }

    /// # Safety
    unsafe fn init(&mut self) {
        if self.head_tail_entry.is_none() {
            self.head_tail_entry = Some(UnsafeListEntry::dummy());
            // SAFETY: `head_tail_entry` must be non-null, which it is because we assign it above.
            self.head_tail =
                unsafe { NonNull::new_unchecked(self.head_tail_entry.as_mut().unwrap()) };
            // SAFETY: `self.head_tail` must meet all requirements for a mutable reference.
            unsafe { self.head_tail.as_mut() }.next = self.head_tail;
            unsafe { self.head_tail.as_mut() }.prev = self.head_tail;
        }
    }

    pub fn is_empty(&self) -> bool {
        if self.head_tail_entry.is_some() {
            let first = unsafe { self.head_tail.as_ref() }.next;
            if first == self.head_tail {
                // ,-------> /---------\ next ---,
                // |         |head_tail|         |
                // `--- prev \---------/ <-------`
                // SAFETY: `self.head_tail` must meet all requirements for a reference.
                unsafe { rtassert!(self.head_tail.as_ref().prev == first) };
                true
            } else {
                false
            }
        } else {
            true
        }
    }

    /// Pushes an entry onto the back of the list.
    ///
    /// # Safety
    ///
    /// The entry must remain allocated until the entry is removed from the
    /// list AND the caller who popped is done using the entry. Special
    /// care must be taken in the caller of `push` to ensure unwinding does
    /// not destroy the stack frame containing the entry.
    pub unsafe fn push<'a>(&mut self, entry: &'a mut UnsafeListEntry<T>) -> &'a T {
        unsafe { self.init() };

        // BEFORE:
        //     /---------\ next ---> /---------\
        // ... |prev_tail|           |head_tail| ...
        //     \---------/ <--- prev \---------/
        //
        // AFTER:
        //     /---------\ next ---> /-----\ next ---> /---------\
        // ... |prev_tail|           |entry|           |head_tail| ...
        //     \---------/ <--- prev \-----/ <--- prev \---------/
        let mut entry = unsafe { NonNull::new_unchecked(entry) };
        let mut prev_tail = mem::replace(&mut unsafe { self.head_tail.as_mut() }.prev, entry);
        // SAFETY: `entry` must meet all requirements for a mutable reference.
        unsafe { entry.as_mut() }.prev = prev_tail;
        unsafe { entry.as_mut() }.next = self.head_tail;
        // SAFETY: `prev_tail` must meet all requirements for a mutable reference.
        unsafe { prev_tail.as_mut() }.next = entry;
        // unwrap ok: always `Some` on non-dummy entries
        unsafe { (*entry.as_ptr()).value.as_ref() }.unwrap()
    }

    /// Pops an entry from the front of the list.
    ///
    /// # Safety
    ///
    /// The caller must make sure to synchronize ending the borrow of the
    /// return value and deallocation of the containing entry.
    pub unsafe fn pop<'a>(&mut self) -> Option<&'a T> {
        unsafe { self.init() };

        if self.is_empty() {
            None
        } else {
            // BEFORE:
            //     /---------\ next ---> /-----\ next ---> /------\
            // ... |head_tail|           |first|           |second| ...
            //     \---------/ <--- prev \-----/ <--- prev \------/
            //
            // AFTER:
            //     /---------\ next ---> /------\
            // ... |head_tail|           |second| ...
            //     \---------/ <--- prev \------/
            let mut first = unsafe { self.head_tail.as_mut() }.next;
            let mut second = unsafe { first.as_mut() }.next;
            unsafe { self.head_tail.as_mut() }.next = second;
            unsafe { second.as_mut() }.prev = self.head_tail;
            unsafe { first.as_mut() }.next = NonNull::dangling();
            unsafe { first.as_mut() }.prev = NonNull::dangling();
            // unwrap ok: always `Some` on non-dummy entries
            Some(unsafe { (*first.as_ptr()).value.as_ref() }.unwrap())
        }
    }

    /// Removes an entry from the list.
    ///
    /// # Safety
    ///
    /// The caller must ensure that `entry` has been pushed onto `self`
    /// prior to this call and has not moved since then.
    pub unsafe fn remove(&mut self, entry: &mut UnsafeListEntry<T>) {
        rtassert!(!self.is_empty());
        // BEFORE:
        //     /----\ next ---> /-----\ next ---> /----\
        // ... |prev|           |entry|           |next| ...
        //     \----/ <--- prev \-----/ <--- prev \----/
        //
        // AFTER:
        //     /----\ next ---> /----\
        // ... |prev|           |next| ...
        //     \----/ <--- prev \----/
        let mut prev = entry.prev;
        let mut next = entry.next;
        // SAFETY: `prev` and `next` must meet all requirements for a mutable reference.entry
        unsafe { prev.as_mut() }.next = next;
        unsafe { next.as_mut() }.prev = prev;
        entry.next = NonNull::dangling();
        entry.prev = NonNull::dangling();
    }
}