[−][src]Trait granite::Storage
Trait for various kinds of 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
andwith_capacity
must return empty storages, i.e. those which havelen() == 0
andis_empty() == true
;- it should be impossible for the length of the storage to overflow
usize
; - Calling
get_unchecked
orget_unchecked_mut
ifcontains_key
on the same key returnstrue
should not cause undefined behavior (otherwise, it may or may not — that is implementation specific); - Calling
remove
ifcontains_key
on the same key should never panic or only perform an aborting panic (i.e. not allowing unwinding), as that might leave the data structure in an invalid state during some operations; - If an element is added at a key, 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 Key: Clone + Debug + Eq
The type used for element naming.
type Element
The type of the elements stored.
Required methods
fn add(&mut self, element: Self::Element) -> Self::Key
Adds an element to the collection with an unspecified key, returning that key.
fn remove(&mut self, key: &Self::Key) -> Self::Element
Removes and returns the element identified by key
within the storage.
Panics
Required to panic if the specified key does not exist.
fn len(&self) -> usize
Returns the number of elements in the storage, also referred to as its 'length'.
fn with_capacity(capacity: usize) -> Self
Creates an empty storage with the specified capacity.
Panics
Storages 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.
unsafe fn get_unchecked(&self, key: &Self::Key) -> &Self::Element
Returns a reference to the specified element in the storage, without checking for presence of the key inside the collection.
Safety
If the element at the specified key is not present in the storage, a dangling reference will be created, causing immediate undefined behavior.
unsafe fn get_unchecked_mut(&mut self, key: &Self::Key) -> &mut Self::Element
Returns a mutable reference to the specified element in the storage, without checking for presence of the key inside the collection.
Safety
If the element at the specified key is not present in the storage, a dangling reference will be created, causing immediate undefined behavior.
fn contains_key(&self, key: &Self::Key) -> bool
Returns true
if the specified key is present in the storage, false
otherwise.
If this method returned true
, calling get_unchecked
/get_unchecked_mut
on the same key is guaranteed to be safe.
Provided methods
fn get(&self, key: &Self::Key) -> Option<&Self::Element>
Returns a reference to the specified element in the collection, or None
if the key is not present in the storage.
fn get_mut(&mut self, key: &Self::Key) -> Option<&mut Self::Element>
Returns a mutable reference to the specified element in the collection, or None
if the key is not present in the storage.
fn new() -> Self
Creates a new empty storage. Dynamically-allocated storages created this way do not allocate memory.
Storages 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 storage contains no elements, false
otherwise.
fn capacity(&self) -> usize
Returns the amount of elements the storage can hold without requiring a memory allocation.
For storages 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 storage. The storage 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 storages 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 storage as much as possible.
It will drop down as close as possible to the current length, though dynamically allocated storages may not always reallocate exactly as much as it is needed to store all elements and none more.
The default implementation does nothing.
Implementations on Foreign Types
impl<T> Storage for Slab<T>
[src]
type Key = usize
type Element = T
fn add(&mut self, element: Self::Element) -> Self::Key
[src]
fn remove(&mut self, key: &Self::Key) -> Self::Element
[src]
fn len(&self) -> usize
[src]
fn with_capacity(capacity: usize) -> Self
[src]
unsafe fn get_unchecked(&self, key: &Self::Key) -> &Self::Element
[src]
unsafe fn get_unchecked_mut(&mut self, key: &Self::Key) -> &mut Self::Element
[src]
fn contains_key(&self, key: &Self::Key) -> bool
[src]
fn get(&self, key: &Self::Key) -> Option<&Self::Element>
[src]
fn get_mut(&mut self, key: &Self::Key) -> Option<&mut Self::Element>
[src]
fn new() -> Self
[src]
fn capacity(&self) -> usize
[src]
fn reserve(&mut self, additional: usize)
[src]
fn shrink_to_fit(&mut self)
[src]
impl<K, V> Storage for SlotMap<K, V> where
K: Key + Debug + Eq,
V: Slottable,
[src]
K: Key + Debug + Eq,
V: Slottable,
type Key = K
type Element = V
fn add(&mut self, element: Self::Element) -> Self::Key
[src]
fn remove(&mut self, key: &Self::Key) -> Self::Element
[src]
fn len(&self) -> usize
[src]
fn with_capacity(capacity: usize) -> Self
[src]
unsafe fn get_unchecked(&self, key: &Self::Key) -> &Self::Element
[src]
unsafe fn get_unchecked_mut(&mut self, key: &Self::Key) -> &mut Self::Element
[src]
fn contains_key(&self, key: &Self::Key) -> bool
[src]
fn get(&self, key: &Self::Key) -> Option<&Self::Element>
[src]
fn get_mut(&mut self, key: &Self::Key) -> Option<&mut Self::Element>
[src]
fn capacity(&self) -> usize
[src]
fn reserve(&mut self, additional: usize)
[src]
fn shrink_to_fit(&mut self)
[src]
impl<K, V> Storage for HopSlotMap<K, V> where
K: Key + Debug + Eq,
V: Slottable,
[src]
K: Key + Debug + Eq,
V: Slottable,
type Key = K
type Element = V
fn add(&mut self, element: Self::Element) -> Self::Key
[src]
fn remove(&mut self, key: &Self::Key) -> Self::Element
[src]
fn len(&self) -> usize
[src]
fn with_capacity(capacity: usize) -> Self
[src]
unsafe fn get_unchecked(&self, key: &Self::Key) -> &Self::Element
[src]
unsafe fn get_unchecked_mut(&mut self, key: &Self::Key) -> &mut Self::Element
[src]
fn contains_key(&self, key: &Self::Key) -> bool
[src]
fn get(&self, key: &Self::Key) -> Option<&Self::Element>
[src]
fn get_mut(&mut self, key: &Self::Key) -> Option<&mut Self::Element>
[src]
fn capacity(&self) -> usize
[src]
fn reserve(&mut self, additional: usize)
[src]
fn shrink_to_fit(&mut self)
[src]
impl<K, V> Storage for DenseSlotMap<K, V> where
K: Key + Debug + Eq,
V: Slottable,
[src]
K: Key + Debug + Eq,
V: Slottable,
type Key = K
type Element = V
fn add(&mut self, element: Self::Element) -> Self::Key
[src]
fn remove(&mut self, key: &Self::Key) -> Self::Element
[src]
fn len(&self) -> usize
[src]
fn with_capacity(capacity: usize) -> Self
[src]
unsafe fn get_unchecked(&self, key: &Self::Key) -> &Self::Element
[src]
unsafe fn get_unchecked_mut(&mut self, key: &Self::Key) -> &mut Self::Element
[src]
fn contains_key(&self, key: &Self::Key) -> bool
[src]
fn get(&self, key: &Self::Key) -> Option<&Self::Element>
[src]
fn get_mut(&mut self, key: &Self::Key) -> Option<&mut Self::Element>
[src]
fn capacity(&self) -> usize
[src]
fn reserve(&mut self, additional: usize)
[src]
fn shrink_to_fit(&mut self)
[src]
Implementors
impl<T, E> Storage for T where
T: ListStorage<Element = E>,
E: MoveFix,
[src]
T: ListStorage<Element = E>,
E: MoveFix,