[−][src]Trait granite::ListStorage

pub unsafe trait ListStorage: Sized {
    type Element;
    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.

Data structures may rely on those invariants for safety.

Associated Types

type Element

The type of values in the container.

Loading content...

Required methods

fn with_capacity(capacity: usize) -> Self

Creates an empty collection with the specified capacity.

Panics

Collections with a fixed capacity should panic if the specified capacity does not match their actual one, and are recommended to override the new method to use the correct capacity.

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

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

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

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

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

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

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>

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>

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

fn new() -> Self

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

Collections with fixed capacity should override this method to use the correct capacity, as the default implementation calls Self::with_capacity(0).

fn is_empty(&self) -> bool

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

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

Appends an element to the back of the collection.

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

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

fn capacity(&self) -> usize

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

For collections which have a fixed capacity, this should be equal to the length; the default implementation uses exactly that.

fn reserve(&mut self, additional: usize)

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)

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)

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, 

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, 

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

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> ListStorage for SmallVec<A> where
    A: Array, [src]

type Element = A::Item

Loading content...

Implementors

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

type Element = E

Loading content...