chainlink 0.1.0

//! # Chainlink
//!
//! ```rust
//! use chainlink::LinkedList;
//! let mut list = LinkedList::new();
//! list.push_tail(1); // 1
//! list.push_head(2); // 2, 1
//! list.push_tail(3); // 2, 1, 3
//!
//! assert_eq!(list.into_vec(), vec![2, 1, 3]);
//! ```
//!
//! Chainlink is an attempt to make a 100%-safe linked list in pure-Rust. The
//! strategy to accomplish this is to use a generational-arena allocator backing
//! the linked list instead of general-purpose pointers issued by a normal allocator.
//! This has two main benefits.
//!
//! 1. Because all our data is stored in a single vector, accesses and other
//! operations on that vector should be extremely fast compared to a normal linked
//! list, which is issued a new allocation for each node. Pointers issued by several
//! calls to a system allocator tend to have worse cache locality than multiple
//! elements of the same vector.
//!
//! 2. Our pointer equivalents are just indices that are logically
//! tied to a vector, and accesses to the vector are checked at runtime
//! to ensure we're within the bounds of valid memory. Since these types of runtime
//! checks will `panic` and crash if they fail, any failed check is a bug and is
//! expected to never happen. For that reason, we should expect the branch predictor
//! for these checks to perform well and reduce the extra runtime cost, which was
//! already unlikely to be a bottleneck in normal application code.
//!
//! ## Drawbacks
//!
//! This approach is not without its compromises.
//!
//! 1. It's memory-inefficient compared to a plain `Vec`. A normal vector will store
//! only the data you give it behind its heap-allocated pointer. That represents perfect
//! efficiency if you don't count the padding between elements. Our `LinkedList` node
//! currently uses 20 bytes to store a single `u8`. As the stored elements get larger,
//! the effective inefficiency of using a doubly linked list will decrease. However,
//! for small numbers of elements, consider using a normal `Vec`. It will have better
//! cache efficiency due to using less space.
//!
//! 2. We're limited to about four billion elements that can each undergo about four
//! billion revisions. Using generational-arena indices means that we have to store
//! the generation of the elements alongside the pointer-equivalent usize vector offset.
//! Instead of making every `Index` larger than a pointer, the underlying arena
//! implementation, [`thunderdome`](https://docs.rs/thunderdome), uses 32 bits for the
//! generation and 32 bits for the vector offset. In practice, the minimum size
//! of a node is 20 bytes and four billion of those nodes would take 80GB of memory.
//! It's unlikely you're going to use 80GB of memory. Though, for a very long-lived
//! application, you may bump up against the four-billion-times update limit. For
//! reference, that's about 120 updates per second over one year. We plan to implement
//! parameterized arenas that can be more tailored to the API users' needs.

use thunderdome::{Arena, Index};

pub use iter_links::IterLinks;

mod iter_links;

#[derive(Clone, Copy, Debug)]
struct Node<T> {
    data: T,
    next: Option<Index>,
    prev: Option<Index>,
}

#[derive(Clone, Debug)]
pub struct LinkedList<T> {
    nodes: Arena<Node<T>>,
    head: Option<Index>,
    tail: Option<Index>,
}

impl<T> LinkedList<T> {
    /// Create an empty linked list.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// assert_eq!(list.len(), 0);
    ///
    /// list.push_tail(0);
    /// assert_eq!(list.tail(), Some(&0));
    /// assert_eq!(list.len(), 1);
    /// ```
    pub fn new() -> Self {
        Self {
            nodes: Arena::new(),
            head: None,
            tail: None,
        }
    }

    /// Get an aliasable reference to the element of the list associated with
    /// the given index.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// let a = list.push_head('a');
    /// let b = list.push_head('b');
    /// assert_eq!(list.get(a), Some(&'a'));
    /// assert_eq!(list.get(b), Some(&'b'));
    /// ```
    pub fn get(&self, idx: Index) -> Option<&T> {
        self.nodes.get(idx).map(|node| &node.data)
    }

    /// Get unique reference to the element of the list associated with
    /// the given index.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// let a = list.push_head('a');
    /// let b = list.push_head('b');
    ///
    /// *list.get_mut(a).unwrap() = 'A';
    /// *list.get_mut(b).unwrap() = 'B';
    ///
    /// assert_eq!(list.get(a), Some(&'A'));
    /// assert_eq!(list.get(b), Some(&'B'));
    /// ```
    pub fn get_mut(&mut self, idx: Index) -> Option<&mut T> {
        self.nodes.get_mut(idx).map(|node| &mut node.data)
    }

    /// Get an aliasable reference to the head of the list. Note that the head of the list
    /// will come first in an ordered iteration.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// list.push_tail(0);
    /// assert_eq!(list.head(), Some(&0));
    ///
    /// list.push_head(1);
    /// list.push_tail(2);
    /// assert_eq!(list.head(), Some(&1));
    /// ```
    pub fn head(&self) -> Option<&T> {
        self.head.map(|head| self.get(head)).flatten()
    }

    /// Get an unique reference to the head of the list.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// list.push_head('a');
    /// *list.head_mut().unwrap() = 'b';
    /// assert_eq!(list.head(), Some(&'b'));
    /// ```
    pub fn head_mut(&mut self) -> Option<&mut T> {
        let head = self.head?;
        self.get_mut(head)
    }

    /// Get an aliasable reference to the tail of the list. Note that the tail of the list
    /// will come last in an ordered iteration.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// list.push_head(0);
    /// assert_eq!(list.tail(), Some(&0));
    ///
    /// list.push_tail(1);
    /// list.push_head(2);
    /// assert_eq!(list.tail(), Some(&1));
    /// ```
    pub fn tail(&self) -> Option<&T> {
        self.tail.map(|tail| self.get(tail)).flatten()
    }

    /// Get an unique reference to the tail of the list.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// list.push_tail('a');
    /// *list.tail_mut().unwrap() = 'b';
    /// assert_eq!(list.tail(), Some(&'b'));
    /// ```
    pub fn tail_mut(&mut self) -> Option<&mut T> {
        let tail = self.tail?;
        self.get_mut(tail)
    }

    /// Remove the element at the head of the list, if it exists, and return it.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// list.push_head(0);
    /// list.push_head(1);
    /// assert_eq!(list.pop_head(), Some(1));
    /// assert_eq!(list.pop_head(), Some(0));
    /// ```
    pub fn pop_head(&mut self) -> Option<T> {
        self.remove(self.head?)
    }

    /// Remove the element at the tail of the list, if it exists, and return it.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// list.push_tail(0);
    /// list.push_tail(1);
    /// assert_eq!(list.pop_tail(), Some(1));
    /// assert_eq!(list.pop_tail(), Some(0));
    /// ```
    pub fn pop_tail(&mut self) -> Option<T> {
        self.remove(self.tail?)
    }

    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// list.push_head(0);
    /// list.push_head(1);
    /// list.push_head(2);

    /// let mut iter = list.iter_links();
    /// assert_eq!(iter.next(), Some(&2));
    /// assert_eq!(iter.next(), Some(&1));
    /// assert_eq!(iter.next(), Some(&0));
    /// ```
    pub fn push_head(&mut self, data: T) -> Index {
        let node = Node {
            data,
            next: self.head,
            prev: None,
        };
        let node_idx = self.nodes.insert(node);

        if let Some(old_head_idx) = self.head {
            self.nodes[old_head_idx].prev = Some(node_idx);
        }

        self.head = Some(node_idx);

        // If this is the only node in the linked list, that means the list
        // was empty before, so the new node is also the tail of the list.
        if self.len() == 1 {
            self.tail = self.head;
        }

        node_idx
    }

    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// list.push_tail(0);
    /// list.push_tail(1);
    /// list.push_tail(2);

    /// let mut iter = list.iter_links();
    /// assert_eq!(iter.next(), Some(&0));
    /// assert_eq!(iter.next(), Some(&1));
    /// assert_eq!(iter.next(), Some(&2));
    /// ```
    pub fn push_tail(&mut self, data: T) -> Index {
        let node = Node {
            data,
            next: None,
            prev: self.tail,
        };
        let node_idx = self.nodes.insert(node);

        if let Some(old_tail_idx) = self.tail {
            self.nodes[old_tail_idx].next = Some(node_idx);
        }

        self.tail = Some(node_idx);

        // If this is the only node in the linked list, that means the list
        // was empty before, so the new node is also the head of the list.
        if self.len() == 1 {
            self.head = self.tail;
        }

        node_idx
    }

    /// Remove an arbitrary element from the list, given its Index.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    ///
    /// let a = list.push_tail(0);  // list: 0
    /// list.push_head(1);          // list: 1, 0
    /// list.push_tail(1);          // list: 1, 0, 1
    /// let a = list.remove(a).unwrap();
    ///
    /// assert_eq!(a, 0);
    /// assert!(!list.iter_fast().any(|&el| el == a));
    /// ```
    pub fn remove(&mut self, idx: Index) -> Option<T> {
        let removed_node = match self.nodes.remove(idx) {
            Some(node) => node,
            None => return None,
        };

        // If the node we're removing is the head or tail or the list, we
        // have to adjust our stored head/tail.
        if Some(idx) == self.head {
            self.head = removed_node.next;
        }
        if Some(idx) == self.tail {
            self.tail = removed_node.prev;
        }

        // Adjust the links for the adjacent nodes if they exist.
        if let Some(prev_idx) = removed_node.prev {
            self.nodes[prev_idx].next = removed_node.next;
        }
        if let Some(next_idx) = removed_node.next {
            self.nodes[next_idx].prev = removed_node.prev;
        }

        Some(removed_node.data)
    }

    /// Get the number of elements currently in the list.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// assert_eq!(list.len(), 0);
    ///
    /// list.push_tail(0);
    /// assert_eq!(list.len(), 1);
    ///
    /// list.push_tail(0);
    /// assert_eq!(list.len(), 2);
    ///
    /// list.pop_head();
    /// assert_eq!(list.len(), 1);
    /// ```
    pub fn len(&self) -> usize {
        self.nodes.len()
    }

    /// Returns `true` if and only if the list has no elements.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// assert!(list.is_empty());
    ///
    /// list.push_tail(1);
    /// assert!(!list.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    /// Create an iterator that will follow the order defined by the links in
    /// the `LinkedList`.
    ///
    /// Note that [`iter_fast`](crate::LinkedList::iter_fast)
    /// may be faster than this implementation because it eschews the order of
    /// the linked list and just reads the underlying vector from front to back
    /// contiguously. You should prefer `iter_fast` if you don't need the linked
    /// list ordering.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// list.push_tail(0); // 0
    /// list.push_head(1); // 1, 0
    /// list.push_tail(2); // 1, 0, 2
    ///
    /// let mut links = list.iter_links();
    /// assert_eq!(links.next(), Some(&1));
    /// assert_eq!(links.next(), Some(&0));
    /// assert_eq!(links.next(), Some(&2));
    /// ```
    ///
    /// [`IterLinks`](crate::IterLinks) also implements
    /// [`DoubleEndedIterator`](std::iter::DoubleEndedIterator), so you can reverse
    /// the iteration order.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// list.push_tail(0); // 0
    /// list.push_head(1); // 1, 0
    /// list.push_tail(2); // 1, 0, 2
    ///
    /// let mut links = list.iter_links().rev();
    /// assert_eq!(links.next(), Some(&2));
    /// assert_eq!(links.next(), Some(&0));
    /// assert_eq!(links.next(), Some(&1));
    /// ```
    pub fn iter_links(&self) -> iter_links::IterLinks<T> {
        IterLinks::new(self)
    }

    /// Consume the list and create a vector that holds the same elements in
    /// the order defined by the links between them, which is the same as the
    /// order followed by [`iter_links`](crate::LinkedList::iter_links).
    ///
    /// **Note**: this function allocates a new vector and frees the original.
    ///
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// list.push_tail(0); // 0
    /// list.push_head(1); // 1, 0
    /// list.push_tail(2); // 1, 0, 2
    /// assert_eq!(list.into_vec(), vec![1, 0, 2]);
    /// ```
    pub fn into_vec(mut self) -> Vec<T> {
        let mut result_vec = Vec::new();
        while let Some(head) = self.pop_head() {
            result_vec.push(head);
        }

        result_vec
    }

    /// Iterate over the nodes in the order defined by the underlying arena allocator
    /// implementation. This method should be faster than
    /// [`iter_links`](crate::LinkedList::iter_links) because it won't jump back and
    /// forth across the unlying vector holding the memory for our elements.
    /// In practice, especially for smaller lists, the difference in speed will likely
    /// be negligible.
    ///
    /// **This method does not follow the order of the linked list.** Use
    /// [`iter_links`](crate::LinkedList::iter_links) if that's the behavior you need.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// list.push_tail(1);
    /// list.push_head(2);
    /// list.push_tail(3);
    ///
    /// // The iterator will eventually emit each of the listed elements.
    /// // That's the only guarantee we have. The order is subject to change.
    /// assert!(list.iter_fast().any(|&el| el == 1));
    /// assert!(list.iter_fast().any(|&el| el == 2));
    /// assert!(list.iter_fast().any(|&el| el == 3));
    /// ```
    pub fn iter_fast(&self) -> impl Iterator<Item = &T> {
        self.nodes.iter().map(|(_idx, node)| &node.data)
    }

    /// Iterate mutably over the nodes in the order defined by the underlying arena allocator
    /// implementation. See the docs for [`iter_links`](crate::LinkedList::iter_links) for
    /// more information.
    /// ```rust
    /// # use chainlink::LinkedList;
    /// let mut list = LinkedList::new();
    /// list.push_tail(1u8);
    /// list.push_head(2);
    /// list.push_tail(3);
    ///
    /// for element in list.iter_fast_mut() {
    ///     *element = element.pow(2);
    /// }
    ///
    /// assert!(list.iter_fast().any(|&el| el == 1));
    /// assert!(list.iter_fast().any(|&el| el == 4));
    /// assert!(list.iter_fast().any(|&el| el == 9));
    /// ```
    pub fn iter_fast_mut(&mut self) -> impl Iterator<Item = &mut T> {
        self.nodes.iter_mut().map(|(_idx, node)| &mut node.data)
    }
}

impl<T> Default for LinkedList<T> {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn size_of_node() {
        // If this test fails, remember to update the sizes in the crate-level docs.
        assert_eq!(std::mem::size_of::<Node<u8>>(), 20);
    }
}