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::map_unwrap_or, 43 clippy::clippy::print_stdout, 44 clippy::unicode_not_nfc, 45 clippy::use_self 46 ) 47 )] 48 #![no_std] 49 50 extern crate alloc; 51 52 // Re-export core so that the macros works with both std and no_std crates 53 #[doc(hidden)] 54 pub extern crate core as __core; 55 56 /// A type wrapping a small integer index should implement `EntityRef` so it can be used as the key 57 /// of an `SecondaryMap` or `SparseMap`. 58 pub trait EntityRef: Copy + Eq { 59 /// Create a new entity reference from a small integer. 60 /// This should crash if the requested index is not representable. 61 fn new(_: usize) -> Self; 62 63 /// Get the index that was used to create this entity reference. 64 fn index(self) -> usize; 65 } 66 67 /// Macro which provides the common implementation of a 32-bit entity reference. 68 #[macro_export] 69 macro_rules! entity_impl { 70 // Basic traits. 71 ($entity:ident) => { 72 impl $crate::EntityRef for $entity { 73 #[inline] 74 fn new(index: usize) -> Self { 75 debug_assert!(index < ($crate::__core::u32::MAX as usize)); 76 $entity(index as u32) 77 } 78 79 #[inline] 80 fn index(self) -> usize { 81 self.0 as usize 82 } 83 } 84 85 impl $crate::packed_option::ReservedValue for $entity { 86 #[inline] 87 fn reserved_value() -> $entity { 88 $entity($crate::__core::u32::MAX) 89 } 90 91 #[inline] 92 fn is_reserved_value(&self) -> bool { 93 self.0 == $crate::__core::u32::MAX 94 } 95 } 96 97 impl $entity { 98 /// Create a new instance from a `u32`. 99 #[allow(dead_code)] 100 #[inline] 101 pub fn from_u32(x: u32) -> Self { 102 debug_assert!(x < $crate::__core::u32::MAX); 103 $entity(x) 104 } 105 106 /// Return the underlying index value as a `u32`. 107 #[allow(dead_code)] 108 #[inline] 109 pub fn as_u32(self) -> u32 { 110 self.0 111 } 112 } 113 }; 114 115 // Include basic `Display` impl using the given display prefix. 116 // Display a `Block` reference as "block12". 117 ($entity:ident, $display_prefix:expr) => { 118 entity_impl!($entity); 119 120 impl $crate::__core::fmt::Display for $entity { 121 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 122 write!(f, concat!($display_prefix, "{}"), self.0) 123 } 124 } 125 126 impl $crate::__core::fmt::Debug for $entity { 127 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 128 (self as &dyn $crate::__core::fmt::Display).fmt(f) 129 } 130 } 131 }; 132 133 // Alternate form for tuples we can't directly construct; providing "to" and "from" expressions 134 // to turn an index *into* an entity, or get an index *from* an entity. 135 ($entity:ident, $display_prefix:expr, $arg:ident, $to_expr:expr, $from_expr:expr) => { 136 impl $crate::EntityRef for $entity { 137 #[inline] 138 fn new(index: usize) -> Self { 139 debug_assert!(index < ($crate::__core::u32::MAX as usize)); 140 let $arg = index as u32; 141 $to_expr 142 } 143 144 #[inline] 145 fn index(self) -> usize { 146 let $arg = self; 147 $from_expr as usize 148 } 149 } 150 151 impl $crate::packed_option::ReservedValue for $entity { 152 #[inline] 153 fn reserved_value() -> $entity { 154 $entity::from_u32($crate::__core::u32::MAX) 155 } 156 157 #[inline] 158 fn is_reserved_value(&self) -> bool { 159 self.as_u32() == $crate::__core::u32::MAX 160 } 161 } 162 163 impl $entity { 164 /// Create a new instance from a `u32`. 165 #[allow(dead_code)] 166 #[inline] 167 pub fn from_u32(x: u32) -> Self { 168 debug_assert!(x < $crate::__core::u32::MAX); 169 let $arg = x; 170 $to_expr 171 } 172 173 /// Return the underlying index value as a `u32`. 174 #[allow(dead_code)] 175 #[inline] 176 pub fn as_u32(self) -> u32 { 177 let $arg = self; 178 $from_expr 179 } 180 } 181 182 impl $crate::__core::fmt::Display for $entity { 183 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 184 write!(f, concat!($display_prefix, "{}"), self.as_u32()) 185 } 186 } 187 188 impl $crate::__core::fmt::Debug for $entity { 189 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 190 (self as &dyn $crate::__core::fmt::Display).fmt(f) 191 } 192 } 193 }; 194 } 195 196 pub mod packed_option; 197 198 mod boxed_slice; 199 mod iter; 200 mod keys; 201 mod list; 202 mod map; 203 mod primary; 204 mod set; 205 mod sparse; 206 207 pub use self::boxed_slice::BoxedSlice; 208 pub use self::iter::{Iter, IterMut}; 209 pub use self::keys::Keys; 210 pub use self::list::{EntityList, ListPool}; 211 pub use self::map::SecondaryMap; 212 pub use self::primary::PrimaryMap; 213 pub use self::set::EntitySet; 214 pub use self::sparse::{SparseMap, SparseMapValue, SparseSet}; 215 216 /// A collection of tests to ensure that use of the different `entity_impl!` forms will generate 217 /// `EntityRef` implementations that behave the same way. 218 #[cfg(test)] 219 mod tests { 220 /// A macro used to emit some basic tests to show that entities behave as we expect. 221 macro_rules! entity_test { 222 ($entity:ident) => { 223 #[test] 224 fn from_usize_to_u32() { 225 let e = $entity::new(42); 226 assert_eq!(e.as_u32(), 42_u32); 227 } 228 229 #[test] 230 fn from_u32_to_usize() { 231 let e = $entity::from_u32(42); 232 assert_eq!(e.index(), 42_usize); 233 } 234 235 #[test] 236 fn comparisons_work() { 237 let a = $entity::from_u32(42); 238 let b = $entity::new(42); 239 assert_eq!(a, b); 240 } 241 242 #[should_panic] 243 #[test] 244 fn cannot_construct_from_reserved_u32() { 245 use crate::packed_option::ReservedValue; 246 let reserved = $entity::reserved_value().as_u32(); 247 let _ = $entity::from_u32(reserved); // panic 248 } 249 250 #[should_panic] 251 #[test] 252 fn cannot_construct_from_reserved_usize() { 253 use crate::packed_option::ReservedValue; 254 let reserved = $entity::reserved_value().index(); 255 let _ = $entity::new(reserved); // panic 256 } 257 }; 258 } 259 260 /// Test cases for a plain ol' `EntityRef` implementation. 261 mod basic_entity { 262 use crate::EntityRef; 263 #[derive(Clone, Copy, Debug, PartialEq, Eq)] 264 struct BasicEntity(u32); 265 entity_impl!(BasicEntity); 266 entity_test!(BasicEntity); 267 } 268 269 /// Test cases for an `EntityRef` implementation that includes a display prefix. 270 mod prefix_entity { 271 use crate::EntityRef; 272 #[derive(Clone, Copy, PartialEq, Eq)] 273 struct PrefixEntity(u32); 274 entity_impl!(PrefixEntity, "prefix-"); 275 entity_test!(PrefixEntity); 276 277 #[test] 278 fn display_prefix_works() { 279 let e = PrefixEntity::new(0); 280 assert_eq!(alloc::format!("{}", e), "prefix-0"); 281 } 282 } 283 284 /// Test cases for an `EntityRef` implementation for a type we can only construct through 285 /// other means, such as calls to `core::convert::From<u32>`. 286 mod other_entity { 287 mod inner { 288 #[derive(Clone, Copy, PartialEq, Eq)] 289 pub struct InnerEntity(u32); 290 291 impl From<u32> for InnerEntity { 292 fn from(x: u32) -> Self { 293 Self(x) 294 } 295 } 296 297 impl From<InnerEntity> for u32 { 298 fn from(x: InnerEntity) -> Self { 299 x.0 300 } 301 } 302 } 303 304 use {self::inner::InnerEntity, crate::EntityRef}; 305 entity_impl!(InnerEntity, "inner-", i, InnerEntity::from(i), u32::from(i)); 306 entity_test!(InnerEntity); 307 308 #[test] 309 fn display_prefix_works() { 310 let e = InnerEntity::new(0); 311 assert_eq!(alloc::format!("{}", e), "inner-0"); 312 } 313 } 314 } 315