Struct DenseSlotMap

pub struct DenseSlotMap<K: Key, V> {
    pub(crate) base: DenseSlotMap<K, Entry<V>>,
    pub(crate) n_unusable: usize,
    pub(crate) _valid: DenseSlotMapValidationToken,
}

A variation of slotmap::DenseSlotMap that can never give the same key for multiple objects.

Unlike a regular version of DenseSlotMap, this version will not allow a slot’s version counter to roll over to 0 if it reaches 2^31. Instead, it will mark the slot as unusable for future values.

Limitations

The possibility of marking a slot as unusable makes it possible, given enough removals and re-insertions, for a slotmap to use an unbounded amount of memory, even if it is not storing much actual data. (From a DOS point of view: Given the ability to re-insert an entry ~2^31 times, an attacker can cause a slot-map to render approximately 4+sizeof(V) bytes unusable.)

This type does not include implementations for:

• get_unchecked_mut()
• get_disjoint_unchecked_mut()
• IntoIterator.
• serde::{Serialize, Deserialize}.

Risky business!

This code relies upon stability of some undocumented properties of slotmap keys. In particular, it assumes:

• that the slotmap KeyData serde format is stable,
• that slot versions are represented as u32.
• that the least significant bit of a slot version is 1 if the slot is full, and 0 if the slot is empty.
• that slot versions start at 0, and increase monotonically as the slot is emptied and reused.

Note that these assumptions are probably okay: if slotmap were to change them, it would thereby create a breaking change in its serde version.

Fields

base: DenseSlotMap<K, Entry<V>>

An underlying SlotMap, obeying the invariants above.

n_unusable: usize

The number of entries in this SlotMap that are filled with Entry::Unusable values.

_valid: DenseSlotMapValidationToken

A ZST, used to guarantee that we have spot-checked the behavior of the underlying SlotMap implementation.

Implementations

impl<V> DenseSlotMap<DefaultKey, V>

pub fn new() -> Self

Construct a new empty map, using a default key type.

See slotmap::DenseSlotMap::new().

pub fn with_capacity(capacity: usize) -> Self

Construct a new empty map with a specified capacity, using a default key type.

See slotmap::DenseSlotMap::with_capacity(). ::with_capacity()`].

impl<K: Key, V> DenseSlotMap<K, V>

pub fn with_key() -> Self

Construct a new empty map, using a specialized key type.

See slotmap::DenseSlotMap::with_key().

pub fn with_capacity_and_key(capacity: usize) -> Self

Construct a new empty map with a specified capacity, using a specialized key type.

See slotmap::DenseSlotMap::with_capacity_and_key().

pub fn len(&self) -> usize

Return the number of items in this map.

See slotmap::DenseSlotMap::len().

pub fn is_empty(&self) -> bool

Return true if this map has no items.

See slotmap::DenseSlotMap::is_empty().

pub fn capacity(&self) -> usize

Return the total number of slots available for entries in this map.

This number includes used slots, as well as empty slots that may become used.

See slotmap::DenseSlotMap::capacity(), but note that a slotmap-careful implementation may lose capacity over time, as slots are marked unusable.

pub fn reserve(&mut self, additional: usize)

Reserve space as needed.

Allocates if needed, so that this map can hold additional new entries without having to resize.

See slotmap::DenseSlotMap::reserve().

pub fn contains_key(&self, key: K) -> bool

Return true if the map contains an entry with a given key.

See slotmap::DenseSlotMap::contains_key().

pub fn insert(&mut self, value: V) -> K

Insert a new value into the map, and return the key used for it.

See slotmap::DenseSlotMap::insert().

pub fn insert_with_key<F>(&mut self, f: F) -> K

where F: FnOnce(K) -> V,

Insert a new value into the map, constructing it using its own new key.

This method is useful for the case where a value needs to refer to the key that will be assigned to it.

See slotmap::DenseSlotMap::insert_with_key().

pub fn try_insert_with_key<F, E>(&mut self, f: F) -> Result<K, E>

where F: FnOnce(K) -> Result<V, E>,

As Self::insert_with_key, but may return an Err.

See slotmap::DenseSlotMap::try_insert_with_key().

pub fn remove(&mut self, key: K) -> Option<V>

Remove and return the element of this map with a given key.

Return None if the key is not present in the map.

See slotmap::DenseSlotMap::remove().

pub fn retain<F>(&mut self, f: F)

where F: FnMut(K, &mut V) -> bool,

Remove every element of this map that does not satisfy a given predicate.

See slotmap::DenseSlotMap::retain().

pub fn clear(&mut self)

Remove every element of this map.

See slotmap::DenseSlotMap::clear().

pub fn get(&self, key: K) -> Option<&V>

Return a reference to the element of this map with a given key.

Return None if there is no such element.

See slotmap::DenseSlotMap::get().

pub fn get_mut(&mut self, key: K) -> Option<&mut V>

Return a mutable reference to the element of this map with a given key.

Return None if there is no such element.

See slotmap::DenseSlotMap::get_mut().

pub fn get_disjoint_mut<const N: usize>( &mut self, keys: [K; N], ) -> Option<[&mut V; N]>

Return an array of mutable references to the elements of this map with a given list of keys.

Return None if any key is not present, or if the same key is given twice.

See slotmap::DenseSlotMap::get_disjoint_mut().

pub fn iter(&self) -> impl Iterator<Item = (K, &V)> + '_

Return an iterator over the elements of this map.

See slotmap::DenseSlotMap::iter().

Current limitations

Does not return a named type.

pub fn drain(&mut self) -> impl Iterator<Item = (K, V)> + '_

Remove every element of this map.

See slotmap::DenseSlotMap::drain().

pub fn iter_mut(&mut self) -> impl Iterator<Item = (K, &mut V)> + '_

Return a mutable iterator over the elements of this map.

See slotmap::DenseSlotMap::iter_mut().

Current limitations

Does not return a named type.

pub fn keys(&self) -> impl Iterator<Item = K> + '_

Return an iterator over all the keys in this map.

See slotmap::DenseSlotMap::keys().

Current limitations

Does not return a named type.

pub fn values(&self) -> impl Iterator<Item = &V> + '_

Return an iterator over the values in this map.

See slotmap::DenseSlotMap::values().

Current limitations

Does not return a named type.

pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> + '_

Return a mutable iterator over the values in this map.

See slotmap::DenseSlotMap::values_mut().

Current limitations

Does not return a named type.

Trait Implementations

impl<K: Clone + Key, V: Clone> Clone for DenseSlotMap<K, V>

fn clone(&self) -> DenseSlotMap<K, V>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K: Debug + Key, V: Debug> Debug for DenseSlotMap<K, V>

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

Formats the value using the given formatter.

impl<K: Key, V> Default for DenseSlotMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K: Key, V> Index<K> for DenseSlotMap<K, V>

type Output = V

The returned type after indexing.

fn index(&self, key: K) -> &V

Performs the indexing (container[index]) operation.

impl<K: Key, V> IndexMut<K> for DenseSlotMap<K, V>

fn index_mut(&mut self, key: K) -> &mut V

Performs the mutable indexing (container[index]) operation.