cycle_ptr 0.1.0

//! An implementation of a linked-list.
use crate::list::linked_list::state::ListEntry;
use crate::list::linked_list::traits::ListElement;
use crate::util::NonNull;
use std::fmt;
use std::marker::PhantomData;
use std::pin::Pin;
#[cfg(any(test, feature = "linked_list_reachability_assert"))]
use std::ptr;

/// A linked list containing `Type`.
pub(crate) struct List<Type, Tag>
where
    Type: ListElement<Tag, Type = Type> + ?Sized,
{
    /// First element of the list.
    ///
    /// [None] if the list is empty.
    head: Option<NonNull<Type>>,
    /// Last element of the list.
    ///
    /// [None] if the list is empty.
    tail: Option<NonNull<Type>>,
    /// Size of the list.
    sz: usize,

    /// Track tag.
    tag: PhantomData<Tag>,
}

/// Iterator for [List].
pub(crate) struct ListIterator<'elem_lifetime, Type, Tag>
where
    Type: 'elem_lifetime + ListElement<Tag, Type = Type> + ?Sized,
{
    /// Next element.
    next: Option<NonNull<Type>>,
    /// Remaining number of elements.
    remaining: usize,

    /// Track lifetime of elements.
    self_lifetime: PhantomData<&'elem_lifetime ()>,
    /// Track tag.
    tag: PhantomData<Tag>,
}

/// Consuming iterator for [List].
pub(crate) struct PopFrontIterator<Type, Tag>
where
    Type: 'static + ListElement<Tag, Type = Type> + ?Sized,
{
    /// List from which elements are consumed by this iterator.
    list: List<Type, Tag>,
}

/// Create an empty list.
impl<Type, Tag> Default for List<Type, Tag>
where
    Type: ListElement<Tag, Type = Type> + ?Sized,
{
    fn default() -> Self {
        List {
            head: None,
            tail: None,
            sz: 0,
            tag: PhantomData,
        }
    }
}

/// We implement [Drop] to assert a list is empty when it's dropped.
impl<Type, Tag> Drop for List<Type, Tag>
where
    Type: ListElement<Tag, Type = Type> + ?Sized,
{
    fn drop(&mut self) {
        self.clear();
        assert!(
            self.head.is_none() && self.tail.is_none(),
            "dropped list must be empty"
        );
    }
}

impl<Type, Tag> fmt::Debug for List<Type, Tag>
where
    Type: fmt::Debug + ListElement<Tag, Type = Type> + ?Sized,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
        f.debug_list().entries(self.iter()).finish()
    }
}

impl<Type, Tag> IntoIterator for List<Type, Tag>
where
    Type: 'static + ListElement<Tag, Type = Type> + ?Sized,
{
    type Item = Pin<&'static Type>;
    type IntoIter = PopFrontIterator<Type, Tag>;

    fn into_iter(self) -> Self::IntoIter {
        PopFrontIterator { list: self }
    }
}

/// A list is [Send], if its contained type is [Send].
unsafe impl<Type, Tag> Send for List<Type, Tag>
where
    Type: ListElement<Tag, Type = Type> + Send + ?Sized,
    Tag: Send,
{
}

impl<Type, Tag> List<Type, Tag>
where
    Type: ListElement<Tag, Type = Type> + ?Sized,
{
    /// Dereference a pointer.
    const unsafe fn get_ref<'a>(p: NonNull<Type>) -> &'a Type {
        unsafe { p.into_ref() }
    }

    /// Get the [ListEntry] for a pointer.
    unsafe fn get_entry<'a>(p: NonNull<Type>) -> &'a ListEntry<Type> {
        unsafe { Self::get_ref(p).get_entry() }
    }

    /// Get the [ListEntry] for a pointer.
    unsafe fn get_entry_mut<'a>(p: NonNull<Type>) -> &'a mut ListEntry<Type> {
        unsafe { Self::get_ref(p).get_entry_mut() }
    }

    /// Run assertions to confirm the invariant holds.
    fn assert_invariant(&self) {
        assert!(
            self.head.is_none() == self.tail.is_none(),
            "head and tail must agree on if there are some/none elements in the list"
        );
    }

    /// Test if an element is present in the list.
    ///
    /// This function does not run [List::assert_invariant].
    #[cfg(any(test, feature = "linked_list_reachability_assert"))]
    fn reachable(&self, e: &Type) -> bool {
        let mut iter = self.head.clone();
        while let Some(iter_elem_ref) = iter.map(|ptr| unsafe { Self::get_ref(ptr) }) {
            if ptr::eq(iter_elem_ref, e) {
                return true;
            }
            // advance
            iter = iter_elem_ref.get_entry().succ.clone();
        }
        false
    }

    /// Link an element into the list.
    ///
    /// `e`: element that is to be inserted.
    /// `opt_pred`: predecessor of `e`. [None] indicates that `e` is inserted at the front of the list.
    /// `opt_succ`: successor of `e`. [None] indicates that `e` is inserted at the back of the list.
    ///
    /// Returns a pointer to the inserted element.
    fn link_element(
        &mut self,
        e: Pin<&Type>,
        opt_pred: Option<NonNull<Type>>,
        opt_succ: Option<NonNull<Type>>,
    ) -> NonNull<Type> {
        let e_ptr: NonNull<Type> = NonNull::from_ref(e.get_ref());
        let e_entry: &mut ListEntry<Type> = unsafe { Self::get_entry_mut(e_ptr.clone()) };

        // Confirm `e` isn't part of a list already.
        assert!(
            !e_entry.linked,
            "to-be-inserted element must not be part of a list already"
        );
        assert!(
            e_entry.succ.is_none() && e_entry.pred.is_none(),
            "predecessor and successor pointers should be None"
        );

        self.assert_invariant();

        // Confirm predecessor is correctly linked.
        match opt_pred
            .clone()
            .map(|pred| unsafe { Self::get_entry(pred) })
        {
            Some(pred_entry) => assert_eq!(
                pred_entry.succ, opt_succ,
                "pred's successor must match opt_succ"
            ),
            None => assert_eq!(self.head, opt_succ),
        }

        // Confirm successor is correctly linked.
        match opt_succ
            .clone()
            .map(|succ| unsafe { Self::get_entry(succ) })
        {
            Some(succ_entry) => assert_eq!(
                succ_entry.pred, opt_pred,
                "succ's predecessor must match opt_pred"
            ),
            None => assert_eq!(self.tail, opt_pred),
        }

        // Confirm that predecessor or successor is in the list.
        // (Since we've already asserted that they're eachother's predecessor/successor,
        // we know that if one of them is in the list, both of them are.)
        #[cfg(feature = "linked_list_reachability_assert")]
        if let Some(predecessor_or_successor_ref) = opt_pred
            .clone()
            .or(opt_succ.clone())
            .map(|ptr| unsafe { Self::get_ref(ptr) })
        {
            debug_assert!(self.reachable(predecessor_or_successor_ref));
        }

        // ------------------------------------------------------------
        // All assertions are completed.
        // Changes are only made past this point.

        // Update predecessor of `e`.
        match opt_pred
            .clone()
            .map(|ptr| unsafe { Self::get_entry_mut(ptr) })
        {
            Some(pred_state) => pred_state.succ = Some(e_ptr.clone()),
            None => self.head = Some(e_ptr.clone()),
        }

        // Update successor of `e`.
        match opt_succ
            .clone()
            .map(|ptr| unsafe { Self::get_entry_mut(ptr) })
        {
            Some(succ_state) => succ_state.pred = Some(e_ptr.clone()),
            None => self.tail = Some(e_ptr.clone()),
        }

        // Update `e`.
        e_entry.succ = opt_succ;
        e_entry.pred = opt_pred;
        e_entry.linked = true;

        // Update list size.
        self.sz += 1;

        self.assert_invariant(); // Invariant must be maintained.
        #[cfg(feature = "linked_list_reachability_assert")]
        debug_assert!(self.reachable(unsafe { Self::get_ref(e_ptr.clone()) }));
        e_ptr
    }

    /// Unlink an element.
    fn unlink_element<'a>(&mut self, e_ptr: NonNull<Type>) -> Pin<&'a Type> {
        let e_entry: &mut ListEntry<Type> = unsafe { Self::get_entry_mut(e_ptr.clone()) };
        let pred = e_entry.pred.clone();
        let succ = e_entry.succ.clone();

        self.assert_invariant();
        #[cfg(feature = "linked_list_reachability_assert")]
        debug_assert!(
            self.reachable(unsafe { Self::get_ref(e_ptr.clone()) }),
            "unlinked element must be part of this list"
        );

        // Confirm that the predecessor indeed links back to us.
        match pred.clone().map(|ptr| unsafe { Self::get_entry(ptr) }) {
            Some(pred_entry) => assert_eq!(pred_entry.succ, Some(e_ptr.clone())),
            None => assert_eq!(self.head, Some(e_ptr.clone())),
        }

        // Confirm that the successor indeed links back to us.
        match succ.clone().map(|ptr| unsafe { Self::get_entry(ptr) }) {
            Some(succ_entry) => assert_eq!(succ_entry.pred, Some(e_ptr.clone())),
            None => assert_eq!(self.tail, Some(e_ptr.clone())),
        }

        // ------------------------------------------------------------
        // All assertions are completed.
        // Changes are only made past this point.

        // Update predecessor of `e`.
        match pred.clone().map(|ptr| unsafe { Self::get_entry_mut(ptr) }) {
            Some(pred_entry) => pred_entry.succ = succ.clone(),
            None => self.head = succ.clone(),
        }

        // Update successor of `e`.
        match succ.clone().map(|ptr| unsafe { Self::get_entry_mut(ptr) }) {
            Some(succ_entry) => succ_entry.pred = pred.clone(),
            None => self.tail = pred.clone(),
        }

        // Update `e`.
        e_entry.succ = None;
        e_entry.pred = None;
        e_entry.linked = false;

        // Update list size.
        self.sz -= 1;

        self.assert_invariant(); // Invariant must be maintained.
        #[cfg(feature = "linked_list_reachability_assert")]
        debug_assert!(!self.reachable(unsafe { Self::get_ref(e_ptr.clone()) }));
        unsafe { Pin::new_unchecked(Self::get_ref(e_ptr)) }
    }

    /// Test if the [List] is empty.
    pub(crate) fn is_empty(&self) -> bool {
        self.assert_invariant();
        self.head.is_none()
    }

    /// Get the number of elements in the [List].
    pub(crate) fn len(&self) -> usize {
        self.assert_invariant();
        self.sz
    }

    /// Insert an element at the back of the list.
    pub(crate) fn push_back(&mut self, e: Pin<&Type>) {
        self.link_element(e, self.tail.clone(), None);
    }

    /// Test if an element is in the list.
    #[cfg(test)]
    pub(crate) fn contains(&self, e: &Type) -> bool {
        self.assert_invariant();
        self.reachable(e)
    }

    /// Remove an element from the list.
    pub(crate) fn remove<'a>(&mut self, e: &'a Type) -> Pin<&'a Type> {
        self.unlink_element(NonNull::from_ref(e))
    }

    /// Iterate over the list items.
    pub(crate) fn iter(&self) -> ListIterator<'_, Type, Tag> {
        self.assert_invariant();
        ListIterator {
            next: self.head.clone(),
            remaining: self.sz,
            self_lifetime: PhantomData,
            tag: self.tag,
        }
    }

    /// Unlink all elements on the list.
    pub(crate) fn clear(&mut self) {
        while let Some(entry) = self.head.clone() {
            self.unlink_element(entry);
        }
    }

    /// Unlink the first element on the list.
    ///
    /// Returns a reference to the unlinked element.
    /// Returns [None] if the list is empty.
    fn pop_front(&mut self) -> Option<Pin<&'static Type>> {
        self.head.clone().map(|ptr| self.unlink_element(ptr))
    }

    /// Unlink the last element on the list.
    ///
    /// Returns a reference to the unlinked element.
    /// Returns [None] if the list is empty.
    pub(crate) fn pop_back<'a>(&mut self) -> Option<Pin<&'a Type>> {
        self.tail.clone().map(|ptr| self.unlink_element(ptr))
    }

    /// Merge all elements from `other` into the list.
    ///
    /// `other` will become empty.
    #[cfg(not(all(
        feature = "single_generation",
        any(feature = "single_generation_mt", not(feature = "multi_thread"))
    )))]
    pub(crate) fn merge(&mut self, other: &mut Self) {
        self.assert_invariant();
        other.assert_invariant();

        if !other.is_empty() {
            if self.is_empty() {
                self.head = other.head.take();
                self.tail = other.tail.take();
            } else {
                unsafe {
                    Self::get_entry_mut(other.head.as_ref().unwrap().clone()).pred =
                        self.tail.clone();
                    Self::get_entry_mut(self.tail.as_ref().unwrap().clone()).succ =
                        other.head.clone();
                    self.tail = other.tail.take();
                    other.head = None;
                }
            }

            self.sz += other.sz;
            other.sz = 0;
        }

        self.assert_invariant();
        other.assert_invariant();
    }
}

impl<'elem_lifetime, Type, Tag> Default for ListIterator<'elem_lifetime, Type, Tag>
where
    Type: 'elem_lifetime + ListElement<Tag, Type = Type> + ?Sized,
{
    fn default() -> Self {
        ListIterator {
            next: None,
            remaining: 0,
            self_lifetime: PhantomData,
            tag: PhantomData,
        }
    }
}

impl<'elem_lifetime, Type, Tag> Clone for ListIterator<'elem_lifetime, Type, Tag>
where
    Type: 'elem_lifetime + ListElement<Tag, Type = Type> + ?Sized,
{
    fn clone(&self) -> Self {
        ListIterator {
            next: self.next.clone(),
            remaining: self.remaining,
            self_lifetime: self.self_lifetime,
            tag: self.tag,
        }
    }
}

impl<'elem_lifetime, Type, Tag> Iterator for ListIterator<'elem_lifetime, Type, Tag>
where
    Type: 'elem_lifetime + ListElement<Tag, Type = Type> + ?Sized,
{
    type Item = Pin<&'elem_lifetime Type>;

    fn next(&mut self) -> Option<Self::Item> {
        match self
            .next
            .clone()
            .map(|ptr| unsafe { List::<Type, Tag>::get_ref(ptr) })
        {
            Some(next_elem) => {
                assert!(self.remaining > 0);
                self.next = next_elem.get_entry().succ.clone();
                self.remaining -= 1;
                Some(unsafe { Pin::new_unchecked(next_elem) })
            }
            None => {
                assert_eq!(self.remaining, 0);
                None
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining, Some(self.remaining))
    }
}

impl<'elem_lifetime, Type, Tag> ExactSizeIterator for ListIterator<'elem_lifetime, Type, Tag>
where
    Type: 'elem_lifetime + ListElement<Tag, Type = Type> + ?Sized,
{
    fn len(&self) -> usize {
        self.remaining
    }
}

impl<Type, Tag> Iterator for PopFrontIterator<Type, Tag>
where
    Type: 'static + ListElement<Tag, Type = Type> + ?Sized,
{
    type Item = Pin<&'static Type>;

    fn next(&mut self) -> Option<Self::Item> {
        self.list.pop_front()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.list.len(), Some(self.list.len()))
    }
}

impl<Type, Tag> ExactSizeIterator for PopFrontIterator<Type, Tag>
where
    Type: 'static + ListElement<Tag, Type = Type> + ?Sized,
{
    fn len(&self) -> usize {
        self.list.len()
    }
}