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)] 33 #![no_std] 34 35 extern crate alloc; 36 37 // Re-export core so that the macros works with both std and no_std crates 38 #[doc(hidden)] 39 pub extern crate core as __core; 40 41 use core::iter::FusedIterator; 42 use core::ops::Range; 43 44 /// A type wrapping a small integer index should implement `EntityRef` so it can be used as the key 45 /// of an `SecondaryMap` or `SparseMap`. 46 pub trait EntityRef: Copy + Eq { 47 /// Create a new entity reference from a small integer. 48 /// This should crash if the requested index is not representable. 49 fn new(_: usize) -> Self; 50 51 /// Get the index that was used to create this entity reference. 52 fn index(self) -> usize; 53 } 54 55 /// Iterate over a `Range<E: EntityRef>`, yielding a sequence of `E` items. 56 #[inline] 57 pub fn iter_entity_range<E>(range: Range<E>) -> IterEntityRange<E> 58 where 59 E: EntityRef, 60 { 61 IterEntityRange { 62 range: range.start.index()..range.end.index(), 63 _phantom: core::marker::PhantomData, 64 } 65 } 66 67 /// Iterator type returned by `iter_entity_range`. 68 pub struct IterEntityRange<E> { 69 range: Range<usize>, 70 _phantom: core::marker::PhantomData<E>, 71 } 72 73 impl<E> Iterator for IterEntityRange<E> 74 where 75 E: EntityRef, 76 { 77 type Item = E; 78 79 #[inline] 80 fn next(&mut self) -> Option<Self::Item> { 81 let i = self.range.next()?; 82 Some(E::new(i)) 83 } 84 85 #[inline] 86 fn size_hint(&self) -> (usize, Option<usize>) { 87 self.range.size_hint() 88 } 89 } 90 91 impl<E> DoubleEndedIterator for IterEntityRange<E> 92 where 93 E: EntityRef, 94 { 95 #[inline] 96 fn next_back(&mut self) -> Option<Self::Item> { 97 let i = self.range.next_back()?; 98 Some(E::new(i)) 99 } 100 } 101 102 impl<E> FusedIterator for IterEntityRange<E> 103 where 104 E: EntityRef, 105 Range<usize>: FusedIterator, 106 { 107 } 108 109 impl<E> ExactSizeIterator for IterEntityRange<E> 110 where 111 E: EntityRef, 112 Range<usize>: ExactSizeIterator, 113 { 114 } 115 116 /// Macro which provides the common implementation of a 32-bit entity reference. 117 #[macro_export] 118 macro_rules! entity_impl { 119 // Basic traits. 120 ($entity:ident) => { 121 impl $crate::EntityRef for $entity { 122 #[inline] 123 fn new(index: usize) -> Self { 124 debug_assert!(index < ($crate::__core::u32::MAX as usize)); 125 $entity(index as u32) 126 } 127 128 #[inline] 129 fn index(self) -> usize { 130 self.0 as usize 131 } 132 } 133 134 impl $crate::packed_option::ReservedValue for $entity { 135 #[inline] 136 fn reserved_value() -> $entity { 137 $entity($crate::__core::u32::MAX) 138 } 139 140 #[inline] 141 fn is_reserved_value(&self) -> bool { 142 self.0 == $crate::__core::u32::MAX 143 } 144 } 145 146 impl $entity { 147 /// Create a new instance from a `u32`. 148 #[allow(dead_code, reason = "macro-generated code")] 149 #[inline] 150 pub fn from_u32(x: u32) -> Self { 151 debug_assert!(x < $crate::__core::u32::MAX); 152 $entity(x) 153 } 154 155 /// Return the underlying index value as a `u32`. 156 #[allow(dead_code, reason = "macro-generated code")] 157 #[inline] 158 pub fn as_u32(self) -> u32 { 159 self.0 160 } 161 162 /// Return the raw bit encoding for this instance. 163 /// 164 /// __Warning__: the raw bit encoding is opaque and has no 165 /// guaranteed correspondence to the entity's index. It encodes the 166 /// entire state of this index value: either a valid index or an 167 /// invalid-index sentinel. The value returned by this method should 168 /// only be passed to `from_bits`. 169 #[allow(dead_code, reason = "macro-generated code")] 170 #[inline] 171 pub fn as_bits(self) -> u32 { 172 self.0 173 } 174 175 /// Create a new instance from the raw bit encoding. 176 /// 177 /// __Warning__: the raw bit encoding is opaque and has no 178 /// guaranteed correspondence to the entity's index. It encodes the 179 /// entire state of this index value: either a valid index or an 180 /// invalid-index sentinel. The value returned by this method should 181 /// only be given bits from `as_bits`. 182 #[allow(dead_code, reason = "macro-generated code")] 183 #[inline] 184 pub fn from_bits(x: u32) -> Self { 185 $entity(x) 186 } 187 } 188 }; 189 190 // Include basic `Display` impl using the given display prefix. 191 // Display a `Block` reference as "block12". 192 ($entity:ident, $display_prefix:expr) => { 193 entity_impl!($entity); 194 195 impl $crate::__core::fmt::Display for $entity { 196 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 197 write!(f, concat!($display_prefix, "{}"), self.0) 198 } 199 } 200 201 impl $crate::__core::fmt::Debug for $entity { 202 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 203 (self as &dyn $crate::__core::fmt::Display).fmt(f) 204 } 205 } 206 }; 207 208 // Alternate form for tuples we can't directly construct; providing "to" and "from" expressions 209 // to turn an index *into* an entity, or get an index *from* an entity. 210 ($entity:ident, $display_prefix:expr, $arg:ident, $to_expr:expr, $from_expr:expr) => { 211 impl $crate::EntityRef for $entity { 212 #[inline] 213 fn new(index: usize) -> Self { 214 debug_assert!(index < ($crate::__core::u32::MAX as usize)); 215 let $arg = index as u32; 216 $to_expr 217 } 218 219 #[inline] 220 fn index(self) -> usize { 221 let $arg = self; 222 $from_expr as usize 223 } 224 } 225 226 impl $crate::packed_option::ReservedValue for $entity { 227 #[inline] 228 fn reserved_value() -> $entity { 229 $entity::from_u32($crate::__core::u32::MAX) 230 } 231 232 #[inline] 233 fn is_reserved_value(&self) -> bool { 234 self.as_u32() == $crate::__core::u32::MAX 235 } 236 } 237 238 impl $entity { 239 /// Create a new instance from a `u32`. 240 #[allow(dead_code, reason = "macro-generated code")] 241 #[inline] 242 pub fn from_u32(x: u32) -> Self { 243 debug_assert!(x < $crate::__core::u32::MAX); 244 let $arg = x; 245 $to_expr 246 } 247 248 /// Return the underlying index value as a `u32`. 249 #[allow(dead_code, reason = "macro-generated code")] 250 #[inline] 251 pub fn as_u32(self) -> u32 { 252 let $arg = self; 253 $from_expr 254 } 255 } 256 257 impl $crate::__core::fmt::Display for $entity { 258 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 259 write!(f, concat!($display_prefix, "{}"), self.as_u32()) 260 } 261 } 262 263 impl $crate::__core::fmt::Debug for $entity { 264 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 265 (self as &dyn $crate::__core::fmt::Display).fmt(f) 266 } 267 } 268 }; 269 } 270 271 pub mod packed_option; 272 273 mod boxed_slice; 274 mod iter; 275 mod keys; 276 mod list; 277 mod map; 278 mod primary; 279 mod set; 280 mod signed; 281 mod sparse; 282 mod unsigned; 283 284 pub use self::boxed_slice::BoxedSlice; 285 pub use self::iter::{Iter, IterMut}; 286 pub use self::keys::Keys; 287 pub use self::list::{EntityList, ListPool}; 288 pub use self::map::SecondaryMap; 289 pub use self::primary::PrimaryMap; 290 pub use self::set::EntitySet; 291 pub use self::signed::Signed; 292 pub use self::sparse::{SparseMap, SparseMapValue, SparseSet}; 293 pub use self::unsigned::Unsigned; 294 295 /// A collection of tests to ensure that use of the different `entity_impl!` forms will generate 296 /// `EntityRef` implementations that behave the same way. 297 #[cfg(test)] 298 mod tests { 299 /// A macro used to emit some basic tests to show that entities behave as we expect. 300 macro_rules! entity_test { 301 ($entity:ident) => { 302 #[test] 303 fn from_usize_to_u32() { 304 let e = $entity::new(42); 305 assert_eq!(e.as_u32(), 42_u32); 306 } 307 308 #[test] 309 fn from_u32_to_usize() { 310 let e = $entity::from_u32(42); 311 assert_eq!(e.index(), 42_usize); 312 } 313 314 #[test] 315 fn comparisons_work() { 316 let a = $entity::from_u32(42); 317 let b = $entity::new(42); 318 assert_eq!(a, b); 319 } 320 321 #[should_panic] 322 #[cfg(debug_assertions)] 323 #[test] 324 fn cannot_construct_from_reserved_u32() { 325 use crate::packed_option::ReservedValue; 326 let reserved = $entity::reserved_value().as_u32(); 327 let _ = $entity::from_u32(reserved); // panic 328 } 329 330 #[should_panic] 331 #[cfg(debug_assertions)] 332 #[test] 333 fn cannot_construct_from_reserved_usize() { 334 use crate::packed_option::ReservedValue; 335 let reserved = $entity::reserved_value().index(); 336 let _ = $entity::new(reserved); // panic 337 } 338 }; 339 } 340 341 /// Test cases for a plain ol' `EntityRef` implementation. 342 mod basic_entity { 343 use crate::EntityRef; 344 #[derive(Clone, Copy, Debug, PartialEq, Eq)] 345 struct BasicEntity(u32); 346 entity_impl!(BasicEntity); 347 entity_test!(BasicEntity); 348 } 349 350 /// Test cases for an `EntityRef` implementation that includes a display prefix. 351 mod prefix_entity { 352 use crate::EntityRef; 353 #[derive(Clone, Copy, PartialEq, Eq)] 354 struct PrefixEntity(u32); 355 entity_impl!(PrefixEntity, "prefix-"); 356 entity_test!(PrefixEntity); 357 358 #[test] 359 fn display_prefix_works() { 360 let e = PrefixEntity::new(0); 361 assert_eq!(alloc::format!("{e}"), "prefix-0"); 362 } 363 } 364 365 /// Test cases for an `EntityRef` implementation for a type we can only construct through 366 /// other means, such as calls to `core::convert::From<u32>`. 367 mod other_entity { 368 mod inner { 369 #[derive(Clone, Copy, PartialEq, Eq)] 370 pub struct InnerEntity(u32); 371 372 impl From<u32> for InnerEntity { 373 fn from(x: u32) -> Self { 374 Self(x) 375 } 376 } 377 378 impl From<InnerEntity> for u32 { 379 fn from(x: InnerEntity) -> Self { 380 x.0 381 } 382 } 383 } 384 385 use {self::inner::InnerEntity, crate::EntityRef}; 386 entity_impl!(InnerEntity, "inner-", i, InnerEntity::from(i), u32::from(i)); 387 entity_test!(InnerEntity); 388 389 #[test] 390 fn display_prefix_works() { 391 let e = InnerEntity::new(0); 392 assert_eq!(alloc::format!("{e}"), "inner-0"); 393 } 394 } 395 } 396