cycle_ptr 0.1.1

//! Provide a list implementation.
//!
//! The module switches between a vector-based implementation
//! (which is probably both safer and faster)
//! and a doubly linked list implementation
//! (which does not require any memory to be allocated at runtime.
//!
//! Both implementations implement the same accessors and are interchangeable.
mod linked_list;

pub(crate) use linked_list::{List, ListElement, ListEntry};

#[cfg(test)]
mod list_tests {
    use super::List;
    use super::{ListElement, ListEntry};
    use std::cell::UnsafeCell;
    use std::pin::pin;
    use std::ptr;

    struct Tag;

    #[derive(Debug, Default)]
    struct Elem {
        _n: u32,
        entry: UnsafeCell<ListEntry<Elem>>,
    }

    impl Clone for Elem {
        fn clone(&self) -> Self {
            Elem {
                _n: self._n,
                entry: UnsafeCell::new(ListEntry::default()),
            }
        }
    }

    impl ListElement<Tag> for Elem {
        type Type = Elem;

        fn get_entry(&self) -> &ListEntry<Elem> {
            unsafe { &*self.entry.get() }
        }

        fn get_entry_mut(&self) -> &mut ListEntry<Elem> {
            unsafe { &mut *self.entry.get() }
        }
    }

    impl From<u32> for Elem {
        fn from(n: u32) -> Self {
            Elem {
                _n: n,
                entry: UnsafeCell::new(ListEntry::default()),
            }
        }
    }

    #[test]
    fn empty_list() {
        let mut list: List<Elem, Tag> = List::default();
        assert!(list.is_empty());
        assert_eq!(list.len(), 0);

        assert!(list.iter().next().is_none());
        assert_eq!(list.iter().len(), 0);
        assert!(list.pop_back().is_none());
    }

    #[test]
    fn push_back() {
        let e1 = Elem::default();
        let e2 = Elem::default();
        let e1 = pin!(e1);
        let e2 = pin!(e2);

        let mut list: List<Elem, Tag> = List::default();

        list.push_back(e1.as_ref());
        list.push_back(e2.as_ref());

        assert!(!list.is_empty());
        assert_eq!(list.len(), 2);

        let mut iter = list.iter();
        assert!(ptr::eq(iter.next().unwrap().get_ref(), &*e1));
        assert!(ptr::eq(iter.next().unwrap().get_ref(), &*e2));
        assert!(iter.next().is_none());
    }

    #[test]
    fn clear() {
        let e1 = Elem::default();
        let e2 = Elem::default();
        let e1 = pin!(e1);
        let e2 = pin!(e2);

        let mut list: List<Elem, Tag> = List::default();
        list.push_back(e1.as_ref());
        list.push_back(e2.as_ref());

        list.clear();

        assert!(list.is_empty());
        assert_eq!(list.len(), 0);

        assert!(list.iter().next().is_none());
    }

    #[test]
    fn pop_back() {
        let e1 = Elem::default();
        let e2 = Elem::default();
        let e1 = pin!(e1);
        let e2 = pin!(e2);

        let mut list: List<Elem, Tag> = List::default();
        list.push_back(e1.as_ref());
        list.push_back(e2.as_ref());

        assert!(ptr::eq(list.pop_back().unwrap().get_ref(), &*e2));
        assert!(ptr::eq(list.pop_back().unwrap().get_ref(), &*e1));
        assert!(list.pop_back().is_none());
    }

    /// Test if something implements [Send].
    fn assert_is_send<T>(_: &T)
    where
        T: Send,
    {
    }

    #[test]
    fn element_is_send() {
        let e1 = Elem::default();

        assert_is_send(&e1);
    }

    #[test]
    fn list_is_send() {
        let list: List<Elem, Tag> = List::default();

        assert_is_send(&list);
    }

    #[test]
    fn debug() {
        let e1 = Elem::from(1);
        let e2 = Elem::from(2);
        let e3 = Elem::from(3);
        let e1 = pin!(e1);
        let e2 = pin!(e2);
        let e3 = pin!(e3);

        let mut list: List<Elem, Tag> = List::default();
        list.push_back(e1.as_ref());
        list.push_back(e2.as_ref());
        list.push_back(e3.as_ref());

        assert_eq!(
            format!("{list:?}"),
            "[Elem { _n: 1, entry: UnsafeCell { .. } }, Elem { _n: 2, entry: UnsafeCell { .. } }, Elem { _n: 3, entry: UnsafeCell { .. } }]"
        );
    }

    #[test]
    fn contains() {
        let e1 = Elem::default();
        let e2 = Elem::default();
        let e1 = pin!(e1);
        let e2 = pin!(e2);
        let absent_element = Elem::default(); // Never inserted.

        let mut list: List<Elem, Tag> = List::default();

        list.push_back(e1.as_ref());
        list.push_back(e2.as_ref());

        assert!(list.contains(&*e1));
        assert!(list.contains(&*e2));
        assert!(!list.contains(&absent_element));
    }
}