Crate slotmap

slotmap

This library provides a container with persistent unique keys to access stored values, SlotMap. Upon insertion a key is returned that can be used to later access or remove the values. Insertion, removal 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.

You can also create (multiple) secondary maps that can map the keys returned by SlotMap to other values, to associate arbitrary data with objects stored in slot maps, without hashing required - it’s direct indexing under the hood.

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 reuse = sm.insert("reuse");  // Space from bar reused.
assert_eq!(sm.contains_key(bar), false);  // After deletion a key stays invalid.

let mut sec = SecondaryMap::new();
sec.insert(foo, "noun");  // We provide the key for secondary maps.
sec.insert(reuse, "verb");

for (key, val) in sm {
    println!("{} is a {}", val, sec[key]);
}

Serialization through serde

Both keys 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. If you wish to use these features you must enable the serde feature flag for slotmap in your Cargo.toml.

slotmap = { version = "...", features = ["serde"] }

Why not slab?

Unlike slab, the keys returned by SlotMap are versioned. This means that once a key is removed, it stays removed, even if the physical storage inside the slotmap is reused for new elements. The key is a permanently unique^* reference to the inserted value. Despite supporting versioning, a SlotMap is not slower than slab, by internally using carefully checked unsafe code. A HopSlotMap also provides faster iteration than slab does, and DenseSlotMap even faster still. Additionally, at the time of writing slab does not support serialization.

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 2³¹ 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 2³² - 2 elements at a time.

The memory usage for each slot in SlotMap is 4 + max(sizeof(T), 4) rounded up to the alignment of T. Similarly it is 4 + max(sizeof(T), 12) for HopSlotMap. DenseSlotMap has an overhead of 8 bytes per element and 8 bytes per slot.

Choosing SlotMap, HopSlotMap or DenseSlotMap

A SlotMap can never shrink the size of its underlying storage, because for each storage slot it must remember what the latest stored version was, even if the slot is empty now. This means that iteration can be slow as it must iterate over potentially a lot of empty slots.

HopSlotMap solves this by maintaining more information on insertion/removal, allowing it to iterate only over filled slots by ‘hopping over’ contiguous blocks of vacant slots. This can give it significantly better iteration speed. If you expect to iterate over all elements in a SlotMap a lot, choose HopSlotMap. The downside is that insertion and removal is roughly twice as slow. Random access is the same speed for both.

DenseSlotMap goes even further and stores all elements on a contiguous block of memory. It uses two indirects per random access; the slots contain indices used to access the contiguous memory. This means random access is slower than both SlotMap and HopSlotMap, but iteration is significantly faster. Finally, there is no trait requirement on the value type of a DenseSlotMap, see Slottable for more details.

Choosing SecondaryMap or SparseSecondaryMap

You want to associate extra data with objects stored in a slot map, so you use (multiple) secondary maps to map keys to that data.

A SecondaryMap is simply a Vec of slots like slot map is, and essentially provides all the same guarantees as SlotMap does for its operations (with the exception that you provide the keys as produced by the primary slot map). This does mean that even if you associate data to only a single element from the primary slot map, you could need and have to initialize as much memory as the original.

A SparseSecondaryMap is like a HashMap from keys to objects, however it automatically removes outdated keys for slots that had their space reused. You should use this variant if you expect to store some associated data for only a small portion of the primary slot map.

Custom key types

If you have multiple slot maps it’s an error to use the key of one slot map on another slot map. The result is safe, but unspecified, and can not be detected at runtime, so it can lead to a hard to find bug.

To prevent this, slot maps allow you to specify what the type is of the key they return, as long as that type implements the Key trait. To aid with this, the new_key_type! macro is provided that builds such a type for you. The resulting type is exactly like DefaultKey. So instead of simply using SlotMap<DefaultKey, Player> you would use:

new_key_type! { struct PlayerKey; }
let sm: SlotMap<PlayerKey, Player> = SlotMap::with_key();

Re-exports

pub use crate::dense::DenseSlotMap;
pub use crate::hop::HopSlotMap;
pub use crate::secondary::SecondaryMap;
pub use crate::sparse_secondary::SparseSecondaryMap;

Modules

dense	Contains the dense slot map implementation.
hop	Contains the faster iteration, slower insertion/removal slot map implementation.
secondary	Contains the secondary map implementation.
sparse_secondary	Contains the sparse secondary map implementation.

Macros

new_key_type

A helper macro to conveniently create new key types. If you use a new key type for each slot map you create you can entirely prevent using the wrong key on the wrong slot map.

Structs

DefaultKey	The default slot map key type.
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.
KeyData	The actual data stored in a Key.
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.

Traits

Key	Key used to access stored values in a slot map.
Slottable	A trait for items that can go in a SlotMap or HopSlotMap. Due to current stable Rust restrictions a type must be Copy to be placed in one of those slot maps. This restriction does not apply to DenseSlotMap, SecondaryMap or SparseSecondaryMap. It also does not apply if you use nightly Rust and enable the unstable feature for slotmap by editing your Cargo.toml: