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)] 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)] 157 #[inline] 158 pub fn as_u32(self) -> u32 { 159 self.0 160 } 161 162 /// Return the raw bit encoding for this instance. 163 #[allow(dead_code)] 164 #[inline] 165 pub fn as_bits(self) -> u32 { 166 self.0 167 } 168 169 /// Create a new instance from the raw bit encoding. 170 #[allow(dead_code)] 171 #[inline] 172 pub fn from_bits(x: u32) -> Self { 173 $entity(x) 174 } 175 } 176 }; 177 178 // Include basic `Display` impl using the given display prefix. 179 // Display a `Block` reference as "block12". 180 ($entity:ident, $display_prefix:expr) => { 181 entity_impl!($entity); 182 183 impl $crate::__core::fmt::Display for $entity { 184 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 185 write!(f, concat!($display_prefix, "{}"), self.0) 186 } 187 } 188 189 impl $crate::__core::fmt::Debug for $entity { 190 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 191 (self as &dyn $crate::__core::fmt::Display).fmt(f) 192 } 193 } 194 }; 195 196 // Alternate form for tuples we can't directly construct; providing "to" and "from" expressions 197 // to turn an index *into* an entity, or get an index *from* an entity. 198 ($entity:ident, $display_prefix:expr, $arg:ident, $to_expr:expr, $from_expr:expr) => { 199 impl $crate::EntityRef for $entity { 200 #[inline] 201 fn new(index: usize) -> Self { 202 debug_assert!(index < ($crate::__core::u32::MAX as usize)); 203 let $arg = index as u32; 204 $to_expr 205 } 206 207 #[inline] 208 fn index(self) -> usize { 209 let $arg = self; 210 $from_expr as usize 211 } 212 } 213 214 impl $crate::packed_option::ReservedValue for $entity { 215 #[inline] 216 fn reserved_value() -> $entity { 217 $entity::from_u32($crate::__core::u32::MAX) 218 } 219 220 #[inline] 221 fn is_reserved_value(&self) -> bool { 222 self.as_u32() == $crate::__core::u32::MAX 223 } 224 } 225 226 impl $entity { 227 /// Create a new instance from a `u32`. 228 #[allow(dead_code)] 229 #[inline] 230 pub fn from_u32(x: u32) -> Self { 231 debug_assert!(x < $crate::__core::u32::MAX); 232 let $arg = x; 233 $to_expr 234 } 235 236 /// Return the underlying index value as a `u32`. 237 #[allow(dead_code)] 238 #[inline] 239 pub fn as_u32(self) -> u32 { 240 let $arg = self; 241 $from_expr 242 } 243 } 244 245 impl $crate::__core::fmt::Display for $entity { 246 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 247 write!(f, concat!($display_prefix, "{}"), self.as_u32()) 248 } 249 } 250 251 impl $crate::__core::fmt::Debug for $entity { 252 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 253 (self as &dyn $crate::__core::fmt::Display).fmt(f) 254 } 255 } 256 }; 257 } 258 259 pub mod packed_option; 260 261 mod boxed_slice; 262 mod iter; 263 mod keys; 264 mod list; 265 mod map; 266 mod primary; 267 mod set; 268 mod sparse; 269 mod unsigned; 270 271 pub use self::boxed_slice::BoxedSlice; 272 pub use self::iter::{Iter, IterMut}; 273 pub use self::keys::Keys; 274 pub use self::list::{EntityList, ListPool}; 275 pub use self::map::SecondaryMap; 276 pub use self::primary::PrimaryMap; 277 pub use self::set::EntitySet; 278 pub use self::sparse::{SparseMap, SparseMapValue, SparseSet}; 279 pub use self::unsigned::Unsigned; 280 281 /// A collection of tests to ensure that use of the different `entity_impl!` forms will generate 282 /// `EntityRef` implementations that behave the same way. 283 #[cfg(test)] 284 mod tests { 285 /// A macro used to emit some basic tests to show that entities behave as we expect. 286 macro_rules! entity_test { 287 ($entity:ident) => { 288 #[test] 289 fn from_usize_to_u32() { 290 let e = $entity::new(42); 291 assert_eq!(e.as_u32(), 42_u32); 292 } 293 294 #[test] 295 fn from_u32_to_usize() { 296 let e = $entity::from_u32(42); 297 assert_eq!(e.index(), 42_usize); 298 } 299 300 #[test] 301 fn comparisons_work() { 302 let a = $entity::from_u32(42); 303 let b = $entity::new(42); 304 assert_eq!(a, b); 305 } 306 307 #[should_panic] 308 #[cfg(debug_assertions)] 309 #[test] 310 fn cannot_construct_from_reserved_u32() { 311 use crate::packed_option::ReservedValue; 312 let reserved = $entity::reserved_value().as_u32(); 313 let _ = $entity::from_u32(reserved); // panic 314 } 315 316 #[should_panic] 317 #[cfg(debug_assertions)] 318 #[test] 319 fn cannot_construct_from_reserved_usize() { 320 use crate::packed_option::ReservedValue; 321 let reserved = $entity::reserved_value().index(); 322 let _ = $entity::new(reserved); // panic 323 } 324 }; 325 } 326 327 /// Test cases for a plain ol' `EntityRef` implementation. 328 mod basic_entity { 329 use crate::EntityRef; 330 #[derive(Clone, Copy, Debug, PartialEq, Eq)] 331 struct BasicEntity(u32); 332 entity_impl!(BasicEntity); 333 entity_test!(BasicEntity); 334 } 335 336 /// Test cases for an `EntityRef` implementation that includes a display prefix. 337 mod prefix_entity { 338 use crate::EntityRef; 339 #[derive(Clone, Copy, PartialEq, Eq)] 340 struct PrefixEntity(u32); 341 entity_impl!(PrefixEntity, "prefix-"); 342 entity_test!(PrefixEntity); 343 344 #[test] 345 fn display_prefix_works() { 346 let e = PrefixEntity::new(0); 347 assert_eq!(alloc::format!("{e}"), "prefix-0"); 348 } 349 } 350 351 /// Test cases for an `EntityRef` implementation for a type we can only construct through 352 /// other means, such as calls to `core::convert::From<u32>`. 353 mod other_entity { 354 mod inner { 355 #[derive(Clone, Copy, PartialEq, Eq)] 356 pub struct InnerEntity(u32); 357 358 impl From<u32> for InnerEntity { 359 fn from(x: u32) -> Self { 360 Self(x) 361 } 362 } 363 364 impl From<InnerEntity> for u32 { 365 fn from(x: InnerEntity) -> Self { 366 x.0 367 } 368 } 369 } 370 371 use {self::inner::InnerEntity, crate::EntityRef}; 372 entity_impl!(InnerEntity, "inner-", i, InnerEntity::from(i), u32::from(i)); 373 entity_test!(InnerEntity); 374 375 #[test] 376 fn display_prefix_works() { 377 let e = InnerEntity::new(0); 378 assert_eq!(alloc::format!("{e}"), "inner-0"); 379 } 380 } 381 } 382