Trait granite::ListStorage[−][src]

pub unsafe trait ListStorage: Sized {
    type Element;

    const CAPACITY: Option<usize>;

Show methods
    fn with_capacity(capacity: usize) -> Self;

    fn insert(&mut self, index: usize, element: Self::Element);

    fn remove(&mut self, index: usize) -> Self::Element;

    fn len(&self) -> usize;

    unsafe fn get_unchecked(&self, index: usize) -> &Self::Element;

    unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut Self::Element;

    fn get(&self, index: usize) -> Option<&Self::Element> { ... }

    fn get_mut(&mut self, index: usize) -> Option<&mut Self::Element> { ... }

    fn new() -> Self { ... }

    fn is_empty(&self) -> bool { ... }

    fn push(&mut self, element: Self::Element) { ... }

    fn pop(&mut self) -> Option<Self::Element> { ... }

    fn capacity(&self) -> usize { ... }

    fn reserve(&mut self, additional: usize) { ... }

    fn shrink_to_fit(&mut self) { ... }

    fn truncate(&mut self, len: usize) { ... }

    fn insert_and_shiftfix(&mut self, index: usize, element: Self::Element)
    where
        Self::Element: MoveFix,
    { ... }

    fn remove_and_shiftfix(&mut self, index: usize) -> Self::Element
    where
        Self::Element: MoveFix,
    { ... }

    fn add(&mut self, element: Self::Element) -> usize { ... }

}

Trait for list-like containers which can be the backing storage for data structures.

Safety

There’s a number of invariants which have to be followed by the container:

  • The length of the storage cannot be modified in the container when it’s borrowed immutably or not borrowed at all;
  • new and with_capacity must return empty storages, i.e. those which have len() == 0 and is_empty() == true;
  • it should be impossible for the length of the storage to overflow isize;
  • Calling get_unchecked or get_unchecked_mut with self.len() > index should not cause undefined behavior (otherwise, it may or may not — that is implementation specific);
  • insert_and_fix/remove_and_fix call unsafe methods from MoveFix, meaning that insert and remove must be implemented according to the contract of the methods of that trait;
  • If an element is added at a position, it must be retrieveable in the exact same state as it was inserted until it is removed or modified using a method which explicitly does so.
  • If CAPACITY is Some(...), the capacity method is required to return its value.

Data structures may rely on those invariants for safety.

Associated Types

type Element[src]

The type of values in the container.

Loading content...

Associated Constants

const CAPACITY: Option<usize>[src]

The fixed capacity, for statically allocated storages. Storages like SmallVec should set this to None, since going above this limit is generally assumed to panic.

Loading content...

Required methods

fn with_capacity(capacity: usize) -> Self[src]

Creates an empty collection with the specified capacity.

Panics

Collections with a fixed capacity should panic if the specified capacity is bigger than their actual one. Collections which use the heap are allowed to panic if an allocation cannot be performed, though using the OOM abort mechanism is also allowed.

fn insert(&mut self, index: usize, element: Self::Element)[src]

Inserts an element at position index within the collection, shifting all elements after it to the right.

Panics

Required to panic if index > len().

fn remove(&mut self, index: usize) -> Self::Element[src]

Removes and returns the element at position index within the vector, shifting all elements after it to the left.

Panics

Required to panic if the specified index does not exist.

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

Returns the number of elements in the collection, also referred to as its ‘length’.

unsafe fn get_unchecked(&self, index: usize) -> &Self::Element[src]

Returns a reference to the specified element in the collection, without doing bounds checking.

Safety

If the specified index is out of bounds, a dangling reference will be created, causing immediate undefined behavior.

unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut Self::Element[src]

Returns a mutable reference to the specified element in the collection, without doing bounds checking.

Safety

If the specified index is out of bounds, a dangling reference will be created, causing immediate undefined behavior.

Loading content...

Provided methods

fn get(&self, index: usize) -> Option<&Self::Element>[src]

Returns a reference to the specified element in the collection, or None if the index is out of bounds.

fn get_mut(&mut self, index: usize) -> Option<&mut Self::Element>[src]

Returns a mutable reference to the specified element in the collection, or None if the index is out of bounds.

fn new() -> Self[src]

Creates a new empty collection. Dynamically-allocated collections created this way do not allocate memory.

The default implementation calls Self::with_capacity(0), which usually doesn’t allocate for heap-based storages.

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

Returns true if the collection contains no elements, false otherwise.

fn push(&mut self, element: Self::Element)[src]

Appends an element to the back of the collection.

fn pop(&mut self) -> Option<Self::Element>[src]

Removes the last element from the collection and returns it, or None if it is empty.

fn capacity(&self) -> usize[src]

Returns the amount of elements the collection can hold without requiring a memory allocation.

The default implementation uses the current length. Implementors are heavily encouraged to override the default behavior.

fn reserve(&mut self, additional: usize)[src]

Reserves capacity for at least additional more elements to be inserted in the given collection. The collection may reserve more space to avoid frequent reallocations. After calling reserve, capacity will be greater than or equal to self.len() + additional. Does nothing if capacity is already sufficient.

For collections which have a fixed capacity, this should first check for the specified amount of elements to reserve for and if it’s not zero, either reallocate the collection anew or, if that is not supported, panic. The default implementation does exactly that.

fn shrink_to_fit(&mut self)[src]

Shrinks the capacity of the collection as much as possible.

It will drop down as close as possible to the current length, though dynamically allocated collections may not always reallocate exactly as much as it is needed to store all elements and none more.

The default implementation does nothing.

fn truncate(&mut self, len: usize)[src]

Shortens the collection, keeping the first len elements and dropping the rest.

If len is greater than the collection’s current length, this has no effect.

Note that this method has no effect on the allocated capacity of the collection.

fn insert_and_shiftfix(&mut self, index: usize, element: Self::Element) where
    Self::Element: MoveFix, [src]

Inserts an element at position index within the collection. The items after the inserted item should be notified using the MoveFix trait or not have their indices changed at all (index changes are not guaranteed and this behavior is implementation-dependent).

Panics

Same as insert.

fn remove_and_shiftfix(&mut self, index: usize) -> Self::Element where
    Self::Element: MoveFix, [src]

Removes and returns the element at position index within the collection. The items after the inserted item should be notified using the MoveFix trait or not change indicies at all (index changes are not guaranteed and this behavior is implementation-dependent).

Panics

Same as remove.

fn add(&mut self, element: Self::Element) -> usize[src]

Adds an element to the collection at an arbitrary index, returning that index. Will never shift elements around. The default implementation will call push and return the index of the element pushed.

This method is used instead of push by data structures. It is overriden by SparseStorage with the use of a free-list for placing new elements in place of old holes.

Loading content...

Implementations on Foreign Types

impl<T> ListStorage for Vec<T>[src]

type Element = T

impl<T> ListStorage for VecDeque<T>[src]

type Element = T

impl<A> ListStorage for ArrayVec<A> where
    A: Array, [src]

type Element = A::Item

impl<A: Array> ListStorage for SmallVec<A>[src]

type Element = A::Item

impl<A: Array> ListStorage for TinyVec<A>[src]

type Element = A::Item

impl<A: Array> ListStorage for ArrayVec<A>[src]

type Element = A::Item

impl<'s, T: Default> ListStorage for SliceVec<'s, T>[src]

type Element = T

Loading content...

Implementors

impl<E, S> ListStorage for SparseStorage<E, S> where
    S: ListStorage<Element = Slot<E>>, [src]

type Element = E

impl<T, S, I> ListStorage for Chain<T, S, I> where
    S: List<Element = T>,
    I: List<Element = S>, [src]

type Element = T

fn add(&mut self, element: Self::Element) -> usize[src]

Uses push under the hood. The Chain should be wrapped in SparseStorage, not vice versa.

Loading content...