[][src]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):

This example is not tested
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:

This example is not tested
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>[src]

pub const CAPACITY: usize[src]

The maximum number of elements the InlineArray can hold.

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

Get the length of the array.

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

Test if the array is empty.

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

Test if the array is at capacity.

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

Construct a new empty array.

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

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>[src]

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)[src]

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>[src]

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[src]

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)[src]

Discard the contents of the array.

Time: O(n)

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

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

Trait Implementations

impl<A, T> Arbitrary for InlineArray<A, T> where
    A: Arbitrary,
    T: 'static, 
[src]

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

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

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

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

impl<A, T> Clone for InlineArray<A, T> where
    A: Clone
[src]

impl<A, T> Debug for InlineArray<A, T> where
    A: Debug
[src]

impl<A, T> Default for InlineArray<A, T>[src]

impl<A, T> Deref for InlineArray<A, T>[src]

type Target = [A]

The resulting type after dereferencing.

impl<A, T> DerefMut for InlineArray<A, T>[src]

impl<A, T> Drop for InlineArray<A, T>[src]

impl<A, T> Eq for InlineArray<A, T> where
    A: Eq
[src]

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

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

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> Extend<A> for InlineArray<A, T>[src]

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

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, N, T> From<&'a mut InlineArray<A, T>> for Chunk<A, N> where
    N: ChunkLength<A>, 
[src]

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

impl<A, T> FromIterator<A> for InlineArray<A, T>[src]

impl<A, T> Hash for InlineArray<A, T> where
    A: Hash
[src]

impl<A, T> IntoIterator for InlineArray<A, T>[src]

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?

impl<'a, A, T> IntoIterator for &'a InlineArray<A, T>[src]

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?

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

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?

impl<A, T> Ord for InlineArray<A, T> where
    A: Ord
[src]

impl<A, T, Slice> PartialEq<Slice> for InlineArray<A, T> where
    Slice: Borrow<[A]>,
    A: PartialEq
[src]

impl<A, T> PartialOrd<InlineArray<A, T>> for InlineArray<A, T> where
    A: PartialOrd
[src]

Auto Trait Implementations

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

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

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

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

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

Blanket Implementations

impl<T> Any for T where
    T: 'static + ?Sized
[src]

impl<T> Borrow<T> for T where
    T: ?Sized
[src]

impl<T> BorrowMut<T> for T where
    T: ?Sized
[src]

impl<T> From<T> for T[src]

impl<T, U> Into<U> for T where
    U: From<T>, 
[src]

impl<I> IntoIterator for I where
    I: Iterator
[src]

type Item = <I as Iterator>::Item

The type of the elements being iterated over.

type IntoIter = I

Which kind of iterator are we turning this into?

impl<T> Same<T> for T[src]

type Output = T

Should always be Self

impl<T> ToOwned for T where
    T: Clone
[src]

type Owned = T

The resulting type after obtaining ownership.

impl<T, U> TryFrom<U> for T where
    U: Into<T>, 
[src]

type Error = Infallible

The type returned in the event of a conversion error.

impl<T, U> TryInto<U> for T where
    U: TryFrom<T>, 
[src]

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.