#entity #map #set #default-value #memory-pool #data-structures

yanked cretonne-entity

Data structures using entity references as mapping keys

Uses old Rust 2015

0.13.2 Jul 14, 2018
0.12.0 Jun 16, 2018

#55 in #memory-pool


Used in 9 crates (2 directly)

Apache-2.0

68KB
1.5K SLoC

Cretonne has been renamed to Cranelift! For future versions, see the cranelift-entity crate.

This crate contains array-based data structures used by the core Cretonne code generator which use densely numbered entity references as mapping keys.


lib.rs:

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.
  • EntityMap 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.

No runtime deps

Features