Struct granite::SparseStorage

pub struct SparseStorage<E, S> where
    S: ListStorage<Element = Slot<E>>,  { /* fields omitted */ }

A wrapper around a list-like storage type which considerably improves performance when removing elements.

Sparse storage with element type E wraps a normal storage which stores Slot<E>, which is a tagged union storing either an element or a “hole”. Those holes count as regular elements, but trying to get their value produces a panic, since the storage provides E as its element type, rather than Slot<E>. This behavior does not depend on whether checked or unchecked get/get_mut methods are used - all of those are guaranteed to panic upon fetching a hole.

When remove_and_shiftfix is called, elements are not actually shifted, but the element is replaced with a hole. If the elements of the storage store indicies towards other elements of the storage, they don’t get invalidated.

Example

use granite::{
    ListStorage, // ListStorage trait, for interfacing with the sparse
                 // storage's generic list-like storage capabilities
    SparseVec, // A sparse storage type definition for Vec
    DummyMoveFix, // Utility struct to have elements which can be removed with
                  // a move fix but which actually don't react to the hooks at all.
};

// Use the new() method from the Storage trait to create a sparse storage:
let mut storage = SparseVec::<DummyMoveFix<u32>>::new();
// Or, the with_capacity() method to preallocate some space for the elements:
let mut storage = SparseVec::<DummyMoveFix<u32>>::with_capacity(32);

// Let's put some elements in!
storage.add(0.into());
storage.add(1.into());
storage.add(2.into());

// Now that we have some elements, we can remove the one in the
// middle to create a hole, and see what sparse storage is about.
let val = storage.remove_and_shiftfix(1);
assert_eq!(val, 1);

// Let's check the length of the storage:
let len = storage.len();
// It hasn't changed, because the element from the wrapped storage wasn't actually removed...
assert_eq!(len, 3);

// ...but instead dropped and turned into a hole:
let num_holes = storage.num_holes();
assert_eq!(num_holes, 1);

// Let's remove yet another element:
let val = storage.remove_and_shiftfix(2);
assert_eq!(val, 2);
// It's the third element (index 2), because removing the
// previous one did not shift the elements from their indicies.

// The previous hole is still there, and we have a new one:
let num_holes = storage.num_holes();
assert_eq!(num_holes, 2);

// Let's remove the holes from the storage entirely:
storage.defragment();
// We could've called defragment_and_fix, but since we have
// the dummy move fix wrapper, that wouldn't make a difference.

// The holes are gone!
let num_holes = storage.num_holes();
assert_eq!(num_holes, 0);
// We can also use the is_dense() method to check for this:
assert!(storage.is_dense());
// The method is specific to sparse storage and is not a part of the Storage trait.

Implementations

impl<E, S> SparseStorage<E, S> where
    S: ListStorage<Element = Slot<E>>, 

pub fn defragment(&mut self)

Removes all holes from the sparse storage, without fixing elements’ indicies. This is an expensive operation and should only be called if is_dense is false to avoid needless overhead.

pub fn defragment_and_fix(&mut self) where
    E: MoveFix, 

Removes all holes from the sparse storage, fixing elements’ indicies. This is an expensive operation and should only be called if is_dense is false to avoid needless overhead.

pub fn into_inner(self) -> S

Consumes the sparse storage and returns its inner storage.

pub fn num_holes(&self) -> usize

Returns the number of holes in the storage. This operation returns immediately instead of looping through the entire storage, since the sparse storage automatically tracks the number of holes it creates and destroys.

pub fn is_dense(&self) -> bool

Returns true if there are no holes in the storage, false otherwise. This operation returns immediately instead of looping through the entire storage, since the sparse storage automatically tracks the number of holes it creates and destroys.

Trait Implementations

impl<E: Clone, S: Clone> Clone for SparseStorage<E, S> where
    S: ListStorage<Element = Slot<E>>, 

fn clone(&self) -> SparseStorage<E, S>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<E: Copy, S: Copy> Copy for SparseStorage<E, S> where
    S: ListStorage<Element = Slot<E>>, 

impl<E: Debug, S: Debug> Debug for SparseStorage<E, S> where
    S: ListStorage<Element = Slot<E>>, 

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

Formats the value using the given formatter.

impl<E: Default, S: Default> Default for SparseStorage<E, S> where
    S: ListStorage<Element = Slot<E>>, 

fn default() -> SparseStorage<E, S>

Returns the “default value” for a type.

impl<E: Eq, S: Eq> Eq for SparseStorage<E, S> where
    S: ListStorage<Element = Slot<E>>, 

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

type Element = E

The type of values in the container.

fn with_capacity(capacity: usize) -> Self

Creates an empty collection with the specified 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.

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.

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.

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.

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.

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.

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.

fn shrink_to_fit(&mut self)

Shrinks the capacity of the collection as much as possible.

fn truncate(&mut self, len: usize)

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

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).

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).

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.

const CAPACITY: Option<usize>

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.

fn is_empty(&self) -> bool

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

impl<E: PartialEq, S: PartialEq> PartialEq<SparseStorage<E, S>> for SparseStorage<E, S> where
    S: ListStorage<Element = Slot<E>>, 

fn eq(&self, other: &SparseStorage<E, S>) -> bool

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

fn ne(&self, other: &SparseStorage<E, S>) -> bool

This method tests for !=.

impl<E, S> StructuralEq for SparseStorage<E, S> where
    S: ListStorage<Element = Slot<E>>, 

impl<E, S> StructuralPartialEq for SparseStorage<E, S> where
    S: ListStorage<Element = Slot<E>>,