Crate slotmap[][src]

slotmap

This library provides two containers with persistent unique keys to access stored values, SlotMap and DenseSlotMap. Upon insertion a key is returned that can be used to later access or remove the values. Insertion, deletion and access all take O(1) time with low overhead. Great for storing collections of objects that need stable, safe references but have no clear ownership otherwise, such as game entities or graph nodes.

The difference between a BTreeMap or HashMap and a slot map is that the slot map generates and returns the key when inserting a value. A key is always unique and will only refer to the value that was inserted. A slot map's main purpose is to simply own things in a safe and efficient manner.

Examples

let mut sm = SlotMap::new();
let foo = sm.insert("foo");  // Key generated on insert.
let bar = sm.insert("bar");
assert_eq!(sm[foo], "foo");
assert_eq!(sm[bar], "bar");

sm.remove(bar);
let reused = sm.insert("reuse");  // Space from bar reused.
assert_eq!(sm.contains_key(bar), false);  // After deletion a key stays invalid.

Serialization through serde

Both Key and the slot maps have full (de)seralization support through the serde library. A key remains valid for a slot map even after one or both have been serialized and deserialized! This makes storing or transferring complicated referential structures and graphs a breeze. Care has been taken such that deserializing keys and slot maps from untrusted sources is safe.

Why not slab?

Unlike slab, the keys returned by the slots maps are versioned. This means that once a key is removed, it stays removed, even if the physical storage inside the slotmap is re-used for new elements. A DenseSlotMap also provides faster iteration than slab does. Additionally, at the time of writing slab does not support serialization.

Choosing SlotMap or DenseSlotMap

The overhead on access with a Key in a SlotMap compared to storing your elements in a Vec is a mere equality check. However, as there can be 'holes' in the underlying representation of a SlotMap iteration can be inefficient when many slots are unoccupied (a slot gets unoccupied when an element is removed, and gets filled back up on insertion). If you often require fast iteration over all values, we also provide a DenseSlotMap. It trades random access performance for fast iteration over values by storing the actual values contiguously and using an extra array access to translate a key into a value index.

Performance characteristics and implementation details

Insertion, access and deletion is all O(1) with low overhead by storing the elements inside a Vec. Unlike references or indices into a vector, unless you remove a key it is never invalidated. Behind the scenes each slot in the vector is a (value, version) tuple. After insertion the returned key also contains a version. Only when the stored version and version in a key match is a key valid. This allows us to reuse space in the vector after deletion without letting removed keys point to spurious new elements. After 231 deletions and insertions to the same underlying slot the version wraps around and such a spurious reference could potentially occur. It is incredibly unlikely however, and in all circumstances is the behavior safe. A slot map can hold up to 232 - 1 elements at a time.

A slot map never shrinks - it couldn't even if it wanted to. It needs to remember for each slot what the latest version is as to not generate duplicate keys. The overhead for each element in SlotMap is 8 bytes. In DenseSlotMap it is 12 bytes.

Re-exports

pub use dense::DenseSlotMap;

Modules

dense

Contains the dense slot map implementation.

Structs

Drain

A draining iterator for SlotMap.

IntoIter

An iterator that moves key-value pairs out of a SlotMap.

Iter

An iterator over the key-value pairs in a SlotMap.

IterMut

A mutable iterator over the key-value pairs in a SlotMap.

Key

Key used to access stored values in a slot map.

Keys

An iterator over the keys in a SlotMap.

SlotMap

Slot map, storage with stable unique keys.

Values

An iterator over the values in a SlotMap.

ValuesMut

A mutable iterator over the values in a SlotMap.