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 $crate::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 sparse; 281 282 pub use self::boxed_slice::BoxedSlice; 283 pub use self::iter::{Iter, IterMut}; 284 pub use self::keys::Keys; 285 pub use self::list::{EntityList, ListPool}; 286 pub use self::map::SecondaryMap; 287 pub use self::primary::PrimaryMap; 288 pub use self::set::{EntitySet, SetIter}; 289 pub use self::sparse::{SparseMap, SparseMapValue, SparseSet}; 290 291 /// A collection of tests to ensure that use of the different `entity_impl!` forms will generate 292 /// `EntityRef` implementations that behave the same way. 293 #[cfg(test)] 294 mod tests { 295 /// A macro used to emit some basic tests to show that entities behave as we expect. 296 macro_rules! entity_test { 297 ($entity:ident) => { 298 #[test] 299 fn from_usize_to_u32() { 300 let e = $entity::new(42); 301 assert_eq!(e.as_u32(), 42_u32); 302 } 303 304 #[test] 305 fn from_u32_to_usize() { 306 let e = $entity::from_u32(42); 307 assert_eq!(e.index(), 42_usize); 308 } 309 310 #[test] 311 fn comparisons_work() { 312 let a = $entity::from_u32(42); 313 let b = $entity::new(42); 314 assert_eq!(a, b); 315 } 316 317 #[should_panic] 318 #[cfg(debug_assertions)] 319 #[test] 320 fn cannot_construct_from_reserved_u32() { 321 use crate::packed_option::ReservedValue; 322 let reserved = $entity::reserved_value().as_u32(); 323 let _ = $entity::from_u32(reserved); // panic 324 } 325 326 #[should_panic] 327 #[cfg(debug_assertions)] 328 #[test] 329 fn cannot_construct_from_reserved_usize() { 330 use crate::packed_option::ReservedValue; 331 let reserved = $entity::reserved_value().index(); 332 let _ = $entity::new(reserved); // panic 333 } 334 }; 335 } 336 337 /// Test cases for a plain ol' `EntityRef` implementation. 338 mod basic_entity { 339 use crate::EntityRef; 340 #[derive(Clone, Copy, Debug, PartialEq, Eq)] 341 struct BasicEntity(u32); 342 entity_impl!(BasicEntity); 343 entity_test!(BasicEntity); 344 } 345 346 /// Test cases for an `EntityRef` implementation that includes a display prefix. 347 mod prefix_entity { 348 use crate::EntityRef; 349 #[derive(Clone, Copy, PartialEq, Eq)] 350 struct PrefixEntity(u32); 351 entity_impl!(PrefixEntity, "prefix-"); 352 entity_test!(PrefixEntity); 353 354 #[test] 355 fn display_prefix_works() { 356 let e = PrefixEntity::new(0); 357 assert_eq!(alloc::format!("{e}"), "prefix-0"); 358 } 359 } 360 361 /// Test cases for an `EntityRef` implementation for a type we can only construct through 362 /// other means, such as calls to `core::convert::From<u32>`. 363 mod other_entity { 364 mod inner { 365 #[derive(Clone, Copy, PartialEq, Eq)] 366 pub struct InnerEntity(u32); 367 368 impl From<u32> for InnerEntity { 369 fn from(x: u32) -> Self { 370 Self(x) 371 } 372 } 373 374 impl From<InnerEntity> for u32 { 375 fn from(x: InnerEntity) -> Self { 376 x.0 377 } 378 } 379 } 380 381 use {self::inner::InnerEntity, crate::EntityRef}; 382 entity_impl!(InnerEntity, "inner-", i, InnerEntity::from(i), u32::from(i)); 383 entity_test!(InnerEntity); 384 385 #[test] 386 fn display_prefix_works() { 387 let e = InnerEntity::new(0); 388 assert_eq!(alloc::format!("{e}"), "inner-0"); 389 } 390 } 391 } 392