Crate cranelift_entity

Array-based data structures using densely numbered entity references as mapping keys.

This crate defines a number of data structures based on arrays. The arrays are not indexed by usize as usual, but by entity references which are integers wrapped in new-types. This has a couple advantages:

• Improved type safety. The various map and set types accept a specific key type, so there is no confusion about the meaning of an array index, as there is with plain arrays.
• Smaller indexes. The normal usize index is often 64 bits which is way too large for most purposes. The entity reference types can be smaller, allowing for more compact data structures.

The EntityRef trait should be implemented by types to be used as indexed. The entity_impl! macro provides convenient defaults for types wrapping u32 which is common.

• PrimaryMap is used to keep track of a vector of entities, assigning a unique entity reference to each.
• SecondaryMap is used to associate secondary information to an entity. The map is implemented as a simple vector, so it does not keep track of which entities have been inserted. Instead, any unknown entities map to the default value.
• SparseMap is used to associate secondary information to a small number of entities. It tracks accurately which entities have been inserted. This is a specialized data structure which can use a lot of memory, so read the documentation before using it.
• EntitySet is used to represent a secondary set of entities. The set is implemented as a simple vector, so it does not keep track of which entities have been inserted into the primary map. Instead, any unknown entities are not in the set.
• EntityList is a compact representation of lists of entity references allocated from an associated memory pool. It has a much smaller footprint than Vec.

Modules

packed_option

Compact representation of Option<T> for types with a reserved value.

Macros

entity_impl

Macro which provides the common implementation of a 32-bit entity reference.

Structs

BoxedSlice

A slice mapping K -> V allocating dense entity references.

EntityList

A small list of entity references allocated from a pool.

EntitySet

A set of K for densely indexed entity references.

Iter

Iterate over all keys in order.

IterEntityRange

Iterator type returned by iter_entity_range.

IterMut

Iterate over all keys in order.

Keys

Iterate over all keys in order.

ListPool

A memory pool for storing lists of T.

PrimaryMap

A primary mapping K -> V allocating dense entity references.

SecondaryMap

A mapping K -> V for densely indexed entity references.

SparseMap

A sparse mapping of entity references.

Traits

EntityRef

A type wrapping a small integer index should implement EntityRef so it can be used as the key of an SecondaryMap or SparseMap.

SparseMapValue

Trait for extracting keys from values stored in a SparseMap.

Unsigned

Helper trait used to add unsigned() methods to primitive signed integer types.

Functions

iter_entity_range

Iterate over a Range<E: EntityRef>, yielding a sequence of E items.

Type Aliases

SparseSet

A sparse set of entity references.