cranelift_entity/
lib.rs

1//! Array-based data structures using densely numbered entity references as mapping keys.
2//!
3//! This crate defines a number of data structures based on arrays. The arrays are not indexed by
4//! `usize` as usual, but by *entity references* which are integers wrapped in new-types. This has
5//! a couple advantages:
6//!
7//! - Improved type safety. The various map and set types accept a specific key type, so there is
8//!   no confusion about the meaning of an array index, as there is with plain arrays.
9//! - Smaller indexes. The normal `usize` index is often 64 bits which is way too large for most
10//!   purposes. The entity reference types can be smaller, allowing for more compact data
11//!   structures.
12//!
13//! The `EntityRef` trait should be implemented by types to be used as indexed. The `entity_impl!`
14//! macro provides convenient defaults for types wrapping `u32` which is common.
15//!
16//! - [`PrimaryMap`](struct.PrimaryMap.html) is used to keep track of a vector of entities,
17//!   assigning a unique entity reference to each.
18//! - [`SecondaryMap`](struct.SecondaryMap.html) is used to associate secondary information to an
19//!   entity. The map is implemented as a simple vector, so it does not keep track of which
20//!   entities have been inserted. Instead, any unknown entities map to the default value.
21//! - [`SparseMap`](struct.SparseMap.html) is used to associate secondary information to a small
22//!   number of entities. It tracks accurately which entities have been inserted. This is a
23//!   specialized data structure which can use a lot of memory, so read the documentation before
24//!   using it.
25//! - [`EntitySet`](struct.EntitySet.html) is used to represent a secondary set of entities.
26//!   The set is implemented as a simple vector, so it does not keep track of which entities have
27//!   been inserted into the primary map. Instead, any unknown entities are not in the set.
28//! - [`EntityList`](struct.EntityList.html) is a compact representation of lists of entity
29//!   references allocated from an associated memory pool. It has a much smaller footprint than
30//!   `Vec`.
31
32#![deny(missing_docs, trivial_numeric_casts, unused_extern_crates)]
33#![warn(unused_import_braces)]
34#![cfg_attr(feature = "clippy", plugin(clippy(conf_file = "../../clippy.toml")))]
35#![cfg_attr(feature = "cargo-clippy", allow(clippy::new_without_default))]
36#![cfg_attr(
37    feature = "cargo-clippy",
38    warn(
39        clippy::float_arithmetic,
40        clippy::mut_mut,
41        clippy::nonminimal_bool,
42        clippy::option_map_unwrap_or,
43        clippy::option_map_unwrap_or_else,
44        clippy::print_stdout,
45        clippy::unicode_not_nfc,
46        clippy::use_self
47    )
48)]
49#![no_std]
50
51extern crate alloc;
52
53// Re-export core so that the macros works with both std and no_std crates
54#[doc(hidden)]
55pub extern crate core as __core;
56
57/// A type wrapping a small integer index should implement `EntityRef` so it can be used as the key
58/// of an `SecondaryMap` or `SparseMap`.
59pub trait EntityRef: Copy + Eq {
60    /// Create a new entity reference from a small integer.
61    /// This should crash if the requested index is not representable.
62    fn new(_: usize) -> Self;
63
64    /// Get the index that was used to create this entity reference.
65    fn index(self) -> usize;
66}
67
68/// Macro which provides the common implementation of a 32-bit entity reference.
69#[macro_export]
70macro_rules! entity_impl {
71    // Basic traits.
72    ($entity:ident) => {
73        impl $crate::EntityRef for $entity {
74            fn new(index: usize) -> Self {
75                debug_assert!(index < ($crate::__core::u32::MAX as usize));
76                $entity(index as u32)
77            }
78
79            fn index(self) -> usize {
80                self.0 as usize
81            }
82        }
83
84        impl $crate::packed_option::ReservedValue for $entity {
85            fn reserved_value() -> $entity {
86                $entity($crate::__core::u32::MAX)
87            }
88        }
89
90        impl $entity {
91            /// Return the underlying index value as a `u32`.
92            #[allow(dead_code)]
93            pub fn from_u32(x: u32) -> Self {
94                debug_assert!(x < $crate::__core::u32::MAX);
95                $entity(x)
96            }
97
98            /// Return the underlying index value as a `u32`.
99            #[allow(dead_code)]
100            pub fn as_u32(self) -> u32 {
101                self.0
102            }
103        }
104    };
105
106    // Include basic `Display` impl using the given display prefix.
107    // Display an `Ebb` reference as "ebb12".
108    ($entity:ident, $display_prefix:expr) => {
109        entity_impl!($entity);
110
111        impl $crate::__core::fmt::Display for $entity {
112            fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result {
113                write!(f, concat!($display_prefix, "{}"), self.0)
114            }
115        }
116
117        impl $crate::__core::fmt::Debug for $entity {
118            fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result {
119                (self as &dyn $crate::__core::fmt::Display).fmt(f)
120            }
121        }
122    };
123}
124
125pub mod packed_option;
126
127mod boxed_slice;
128mod iter;
129mod keys;
130mod list;
131mod map;
132mod primary;
133mod set;
134mod sparse;
135
136pub use self::boxed_slice::BoxedSlice;
137pub use self::iter::{Iter, IterMut};
138pub use self::keys::Keys;
139pub use self::list::{EntityList, ListPool};
140pub use self::map::SecondaryMap;
141pub use self::primary::PrimaryMap;
142pub use self::set::EntitySet;
143pub use self::sparse::{SparseMap, SparseMapValue, SparseSet};
cranelift_entity/lib.rs

cranelift_entity/
lib.rs
