Struct sized_chunks::inline_array::InlineArray

pub struct InlineArray<A, T> { /* fields omitted */ }

A fixed capacity array sized to match some other type T.

This works like a vector, but allocated on the stack (and thus marginally faster than Vec), with the allocated space exactly matching the size of the given type T. The vector consists of a usize tracking its current length, followed by zero or more elements of type A. The capacity is thus ( size_of::<T>() - size_of::<usize>() ) / size_of::<A>(). This could lead to situations where the capacity is zero, if size_of::<A>() is greater than size_of::<T>() - size_of::<usize>(), which is not an error and handled properly by the data structure.

If size_of::<T>() is less than size_of::<usize>(), meaning the vector has no space to store its length, InlineArray::new() will panic.

This is meant to facilitate optimisations where a list data structure allocates a fairly large struct for itself, allowing you to replace it with an InlineArray until it grows beyond its capacity. This not only gives you a performance boost at very small sizes, it also saves you from having to allocate anything on the heap until absolutely necessary.

For instance, im::Vector<A> in its final form currently looks like this (approximately):

struct RRB<A> {
    length: usize,
    tree_height: usize,
    outer_head: Rc<Chunk<A>>,
    inner_head: Rc<Chunk<A>>,
    tree: Rc<TreeNode<A>>,
    inner_tail: Rc<Chunk<A>>,
    outer_tail: Rc<Chunk<A>>,
}

That's two usizes and five Rcs, which comes in at 56 bytes on x86_64 architectures. With InlineArray, that leaves us with 56 - size_of::<usize>() = 48 bytes we can use before having to expand into the full data struture. If A is u8, that's 48 elements, and even if A is a pointer we can still keep 6 of them inline before we run out of capacity.

We can declare an enum like this:

enum VectorWrapper<A> {
    Inline(InlineArray<A, RRB<A>>),
    Full(RRB<A>),
}

Both of these will have the same size, and we can swap the Inline case out with the Full case once the InlineArray runs out of capacity.

Methods

impl<A, T> InlineArray<A, T>

pub const CAPACITY: usize

#[must_use] pub fn len(&self) -> usize

Get the length of the array.

#[must_use] pub fn is_empty(&self) -> bool

Test if the array is empty.

#[must_use] pub fn is_full(&self) -> bool

Test if the array is at capacity.

#[must_use] pub fn new() -> Self

Construct a new empty array.

pub fn push(&mut self, value: A)

Push an item to the back of the array.

Panics if the capacity of the array is exceeded.

Time: O(1)

pub fn pop(&mut self) -> Option<A>

Pop an item from the back of the array.

Returns None if the array is empty.

Time: O(1)

pub fn insert(&mut self, index: usize, value: A)

Insert a new value at index index, shifting all the following values to the right.

Panics if the index is out of bounds or the array is at capacity.

Time: O(n) for the number of items shifted

pub fn remove(&mut self, index: usize) -> Option<A>

Remove the value at index index, shifting all the following values to the left.

Returns the removed value, or None if the array is empty or the index is out of bounds.

Time: O(n) for the number of items shifted

pub fn split_off(&mut self, index: usize) -> Self

Split an array into two, the original array containing everything up to index and the returned array containing everything from index onwards.

Panics if index is out of bounds.

Time: O(n) for the number of items in the new chunk

pub fn clear(&mut self)

Discard the contents of the array.

Time: O(n)

Important traits for Drain<'a, A, T>

impl<'a, A, T> Iterator for Drain<'a, A, T> type Item = A;

pub fn drain(&mut self) -> Drain<A, T>

Construct an iterator that drains values from the front of the array.

Trait Implementations

impl<A, T> AsMut<[A]> for InlineArray<A, T>

fn as_mut(&mut self) -> &mut [A]

Performs the conversion.

impl<A, T> Clone for InlineArray<A, T> where
    A: Clone, 

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<A, T> Ord for InlineArray<A, T> where
    A: Ord, 

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

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

Restrict a value to a certain interval.

impl<A, T> Default for InlineArray<A, T>

fn default() -> Self

Returns the "default value" for a type.

impl<A, T> IntoIterator for InlineArray<A, T>

type Item = A

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<'a, A, T> IntoIterator for &'a InlineArray<A, T>

type Item = &'a A

The type of the elements being iterated over.

type IntoIter = SliceIter<'a, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, A, T> IntoIterator for &'a mut InlineArray<A, T>

type Item = &'a mut A

The type of the elements being iterated over.

type IntoIter = SliceIterMut<'a, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<A, N, T> From<InlineArray<A, T>> for Chunk<A, N> where
    N: ChunkLength<A>, 

fn from(array: InlineArray<A, T>) -> Self

Performs the conversion.

impl<'a, A, N, T> From<&'a mut InlineArray<A, T>> for Chunk<A, N> where
    N: ChunkLength<A>, 

fn from(array: &mut InlineArray<A, T>) -> Self

Performs the conversion.

impl<A, T> Extend<A> for InlineArray<A, T>

fn extend<I>(&mut self, it: I) where
    I: IntoIterator<Item = A>, 

Append the contents of the iterator to the back of the array.

Panics if the array exceeds its capacity.

Time: O(n) for the length of the iterator

impl<'a, A, T> Extend<&'a A> for InlineArray<A, T> where
    A: 'a + Copy, 

fn extend<I>(&mut self, it: I) where
    I: IntoIterator<Item = &'a A>, 

Append the contents of the iterator to the back of the array.

Panics if the array exceeds its capacity.

Time: O(n) for the length of the iterator

impl<A, T> AsRef<[A]> for InlineArray<A, T>

fn as_ref(&self) -> &[A]

Performs the conversion.

impl<A, T> PartialOrd<InlineArray<A, T>> for InlineArray<A, T> where
    A: PartialOrd, 

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

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

#[must_use] fn lt(&self, other: &Rhs) -> bool

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

#[must_use] fn le(&self, other: &Rhs) -> bool

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

#[must_use] fn gt(&self, other: &Rhs) -> bool

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

#[must_use] 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<A, T, Slice> PartialEq<Slice> for InlineArray<A, T> where
    Slice: Borrow<[A]>,
    A: PartialEq, 

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

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

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<A, T> Drop for InlineArray<A, T>

fn drop(&mut self)

Executes the destructor for this type.

impl<A, T> Eq for InlineArray<A, T> where
    A: Eq, 

impl<A, T> Deref for InlineArray<A, T>

type Target = [A]

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<A, T> Debug for InlineArray<A, T> where
    A: Debug, 

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

Formats the value using the given formatter.

impl<A, T> DerefMut for InlineArray<A, T>

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.

impl<A, T> Hash for InlineArray<A, T> where
    A: Hash, 

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

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<A, T> FromIterator<A> for InlineArray<A, T>

fn from_iter<I>(it: I) -> Self where
    I: IntoIterator<Item = A>, 

Creates a value from an iterator.

impl<A, T> Borrow<[A]> for InlineArray<A, T>

fn borrow(&self) -> &[A]

Immutably borrows from an owned value.

impl<A, T> BorrowMut<[A]> for InlineArray<A, T>

fn borrow_mut(&mut self) -> &mut [A]

Mutably borrows from an owned value.