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

#[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)

Important traits for Drain<'a, A, T>
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> Clone for InlineArray<A, T> where
    A: Clone
[src]

fn clone_from(&mut self, source: &Self)1.0.0[src]

Performs copy-assignment from source. Read more

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

fn max(self, other: Self) -> Self1.21.0[src]

Compares and returns the maximum of two values. Read more

fn min(self, other: Self) -> Self1.21.0[src]

Compares and returns the minimum of two values. Read more

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

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

Restrict a value to a certain interval. Read more

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

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

impl<A, T> Default for InlineArray<A, T>[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, N, T> From<InlineArray<A, T>> for Chunk<A, N> where
    N: ChunkLength<A>, 
[src]

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

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

#[must_use] fn lt(&self, other: &Rhs) -> bool1.0.0[src]

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

#[must_use] fn le(&self, other: &Rhs) -> bool1.0.0[src]

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

#[must_use] fn gt(&self, other: &Rhs) -> bool1.0.0[src]

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

#[must_use] fn ge(&self, other: &Rhs) -> bool1.0.0[src]

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

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

#[must_use] fn ne(&self, other: &Rhs) -> bool1.0.0[src]

This method tests for !=.

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

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

impl<A, T> DerefMut 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> Debug for InlineArray<A, T> where
    A: Debug
[src]

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

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

Feeds a slice of this type into the given [Hasher]. Read more

impl<A, T> FromIterator<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]

Auto Trait Implementations

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

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

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

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

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

Blanket Implementations

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> From<T> for T[src]

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

type Owned = T

The resulting type after obtaining ownership.

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

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.

impl<T, V> SliceConcat<T> for V where
    T: Clone,
    V: Borrow<[T]>, 
[src]

type Output = Vec<T>

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

The resulting type after concatenation

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

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

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

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

type Output = T

Should always be Self