Struct im_lists::shared_list::SharedList

pub struct SharedList<T: Clone>(_);

A persistent, thread safe, list.

This list is suitable for a multi threaded environment. If do not need an immutable list that can be shared across threads (i.e., is Send + Sync, see List).

It’s implemented as an unrolled linked list, which is a single linked list which stores a variable amount of elements in each node. The capacity of any individual node for now is set to to be 256 elements, which means that until more than 256 elements are cons’d onto a list, it will remain a vector under the hood.

The list is also designed to leverage in place mutations whenever possible - if the number of references pointing to either a cell containing a vector or the shared vector is one, then that mutation is done in place. Otherwise, it is copy-on-write, maintaining our persistent invariant.

Performance Notes

The algorithmic complexity of an unrolled linked list matches that of a normal linked list - however in practice we have a decrease by the factor of the capacity of a node that gives us practical performance wins. For a list that is fully filled, iteration becomes O(n / 256), rather than the typical O(n). In addition, the unrolled linked list is able to avoid the costly cache misses that a typical linked list suffers from, seeing very realistic performance gains.

Let n be the number of elements in the list, and m is the capacity of a node. In the worst case, a node will be on average half filled. In the best case, all nodes are completely full. This means for operations that for a normal linked list may take linear time Θ(n), we get a constant factor decrease of either a factor of m or m / 2.

Implementations

impl<T: Clone> SharedList<T>

pub fn new() -> Self

Construct an empty list.

pub fn strong_count(&self) -> usize

Get the number of strong references pointing to this list

Time: O(1)

pub fn ptr_eq(&self, other: &Self) -> bool

Compare this list to another for pointer equality

pub fn len(&self) -> usize

Get the length of the list

Examples

let list = shared_list![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
assert_eq!(list.len(), 10);

pub fn reverse(self) -> Self

Reverses the input list and returns a new list

Examples

let list = shared_list![1, 2, 3, 4, 5].reverse();
assert_eq!(list, shared_list![5, 4, 3, 2, 1])

pub fn last(&self) -> Option<&T>

Get the last element of the list. Returns None if the list is empty.

Examples

let list = shared_list![1, 2, 3, 4, 5];
assert_eq!(list.last().cloned(), Some(5));

pub fn car(&self) -> Option<T>

Get the first element of the list. Returns None if the list is empty.

Examples

let list = shared_list![1, 2, 3, 4, 5];
let car = list.car();
assert_eq!(car, Some(1));

let list: SharedList<usize> = shared_list![];
let car = list.car();
assert!(car.is_none());

pub fn first(&self) -> Option<&T>

Returns a reference to the first element of the list. Returns None if the list is empty.

Examples

let list = shared_list![1, 2, 3, 4, 5];
let first = list.first().cloned();
assert_eq!(first, Some(1));

let list: SharedList<usize> = shared_list![];
let first = list.first();
assert!(first.is_none());

pub fn cdr(&self) -> Option<SharedList<T>>

Get the “rest” of the elements as a list, excluding the first element

Examples

let list = shared_list![1, 2, 3, 4, 5];
let cdr = list.cdr().unwrap();
assert_eq!(cdr, shared_list![2, 3, 4, 5]);

let list = shared_list![5];
let cdr = list.cdr();
assert!(cdr.is_none());

pub fn rest(&self) -> Option<SharedList<T>>

Get the “rest” of the elements as a list. Alias for cdr

pub fn cdr_mut(&mut self) -> Option<&mut Self>

Gets the cdr of the list, mutably. Returns None if the next is empty - otherwise updates self to be the rest

Examples

let mut list = shared_list![1, 2, 3, 4, 5];
list.cdr_mut().expect("This list has a tail");
assert_eq!(list, shared_list![2, 3, 4, 5]);


let mut list = shared_list![1, 2, 3];
assert!(list.cdr_mut().is_some());
assert_eq!(list, shared_list![2, 3]);
assert!(list.cdr_mut().is_some());
assert_eq!(list, shared_list![3]);
assert!(list.cdr_mut().is_none());
assert_eq!(list, shared_list![]);

pub fn rest_mut(&mut self) -> Option<&mut Self>

Gets the rest of the list, mutably. Alias for cdr_mut

pub fn cons(value: T, other: SharedList<T>) -> SharedList<T>

Pushes an element onto the front of the list, returning a new list

Examples

let list = SharedList::cons(1, SharedList::cons(2, SharedList::cons(3, SharedList::cons(4, SharedList::new()))));
assert_eq!(list, shared_list![1, 2, 3, 4]);

pub fn cons_mut(&mut self, value: T)

Mutably pushes an element onto the front of the list, in place

Examples

let mut list = shared_list![];
list.cons_mut(3);
list.cons_mut(2);
list.cons_mut(1);
list.cons_mut(0);
assert_eq!(list, shared_list![0, 1, 2, 3])

pub fn push_front(&mut self, value: T)

Alias for cons_mut

Examples

let mut list = shared_list![];
list.push_front(3);
list.push_front(2);
list.push_front(1);
list.push_front(0);
assert_eq!(list, shared_list![0, 1, 2, 3])

pub fn pop_front(&mut self) -> Option<T>

Mutably pop the first value off of the list

Examples

let mut list = shared_list![1, 2, 3];
assert_eq!(list.pop_front().unwrap(), 1);
assert_eq!(list.pop_front().unwrap(), 2);
assert_eq!(list.pop_front().unwrap(), 3);
assert!(list.pop_front().is_none())

pub fn push_back(&mut self, value: T)

Push one value to the back of the list

Time: O(n)

Examples

let mut list = shared_list![];
list.push_back(0);
list.push_back(1);
list.push_back(2);
list.push_back(3);
assert_eq!(list, shared_list![0, 1, 2, 3])

pub fn take(&self, count: usize) -> Self

Construct a new list from the first count elements from the current list

Examples

let list = shared_list![0, 1, 2, 3, 4, 5];
let new_list = list.take(3);
assert_eq!(new_list, shared_list![0, 1, 2]);

pub fn tail(&self, len: usize) -> Option<Self>

Returns the list after the first len elements of lst. If the list has fewer then len elements, then this returns None.

Examples

let list = shared_list![0, 1, 2, 3, 4, 5];
let new_list = list.tail(2);
assert_eq!(new_list.unwrap(), shared_list![2, 3, 4, 5]);

let no_list = list.tail(100);
assert!(no_list.is_none())

pub fn iter(&self) -> impl Iterator<Item = &T>

Constructs an iterator over the list

pub fn get(&self, index: usize) -> Option<&T>

Get a reference to the value at index index in a list. Returns None if the index is out of bounds.

pub fn append(self, other: Self) -> Self

Append the list other to the end of the current list. Returns a new list.

Examples

let left = shared_list![1usize, 2, 3];
let right = shared_list![4usize, 5, 6];
assert_eq!(left.append(right), shared_list![1, 2, 3, 4, 5, 6])

pub fn append_mut(&mut self, other: Self)

Append the list ‘other’ to the end of the current list in place.

Examples

let mut left = shared_list![1usize, 2, 3];
let right = shared_list![4usize, 5, 6];
left.append_mut(right);
assert_eq!(left, shared_list![1, 2, 3, 4, 5, 6])

pub fn is_empty(&self) -> bool

Checks whether a list is empty

Examples

let mut list = SharedList::new();
assert!(list.is_empty());
list.cons_mut("applesauce");
assert!(!list.is_empty());

pub fn sort(&mut self) where
    T: Ord, 

Sorts the list

Examples

let mut list = shared_list![4, 2, 6, 3, 1, 5];
list.sort();
assert_eq!(list, shared_list![1, 2, 3, 4, 5, 6]);

pub fn sort_by<F>(&mut self, cmp: F) where
    F: Fn(&T, &T) -> Ordering, 

Sorts the list according to the ordering

Examples

let mut list = shared_list![4, 2, 6, 3, 1, 5];
list.sort_by(Ord::cmp);
assert_eq!(list, shared_list![1, 2, 3, 4, 5, 6]);

Trait Implementations

impl<'a, T: Clone> Add<&'a SharedList<T>> for &'a SharedList<T>

fn add(self, other: Self) -> Self::Output

Concatenate two lists

type Output = SharedList<T>

The resulting type after applying the + operator.

impl<T: Clone> Add<SharedList<T>> for SharedList<T>

fn add(self, other: Self) -> Self::Output

Concatenate two lists

type Output = SharedList<T>

The resulting type after applying the + operator.

impl<T: Clone + Clone> Clone for SharedList<T>

fn clone(&self) -> SharedList<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Clone + Debug> Debug for SharedList<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Clone> Default for SharedList<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Clone> Extend<T> for SharedList<T>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: Clone> From<&'_ [T]> for SharedList<T>

fn from(vec: &[T]) -> Self

Converts to this type from the input type.

impl<T: Clone> From<Vec<T, Global>> for SharedList<T>

fn from(vec: Vec<T>) -> Self

Converts to this type from the input type.

impl<'a, T: 'a + Clone> FromIterator<&'a SharedList<T>> for SharedList<T>

fn from_iter<I: IntoIterator<Item = &'a SharedList<T>>>(iter: I) -> Self

Creates a value from an iterator.

impl<T: Clone> FromIterator<SharedList<T>> for SharedList<T>

fn from_iter<I: IntoIterator<Item = SharedList<T>>>(iter: I) -> Self

Creates a value from an iterator.

impl<T: Clone> FromIterator<T> for SharedList<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<T: Clone + Hash> Hash for SharedList<T>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl<T: Clone> Index<usize> for SharedList<T>

fn index(&self, index: usize) -> &Self::Output

Get a reference to the value at index index in the vector.

Time: O(log n)

type Output = T

The returned type after indexing.

impl<'a, T: Clone> IntoIterator for &'a SharedList<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Clone> IntoIterator for SharedList<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = ConsumingIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Clone + Ord> Ord for SharedList<T>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

Restrict a value to a certain interval.

impl<T: Clone + PartialEq> PartialEq<SharedList<T>> for SharedList<T>

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<T: Clone + PartialOrd> PartialOrd<SharedList<T>> for SharedList<T>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T: Clone> Sum<SharedList<T>> for SharedList<T>

fn sum<I>(it: I) -> Self where
    I: Iterator<Item = Self>, 

Method which takes an iterator and generates Self from the elements by “summing up” the items.

impl<T: Clone + Eq> Eq for SharedList<T>