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 /// Return the raw bit encoding for this instance. 114 #[allow(dead_code)] 115 #[inline] 116 pub fn as_bits(self) -> u32 { 117 self.0 118 } 119 120 /// Create a new instance from the raw bit encoding. 121 #[allow(dead_code)] 122 #[inline] 123 pub fn from_bits(x: u32) -> Self { 124 $entity(x) 125 } 126 } 127 }; 128 129 // Include basic `Display` impl using the given display prefix. 130 // Display a `Block` reference as "block12". 131 ($entity:ident, $display_prefix:expr) => { 132 entity_impl!($entity); 133 134 impl $crate::__core::fmt::Display for $entity { 135 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 136 write!(f, concat!($display_prefix, "{}"), self.0) 137 } 138 } 139 140 impl $crate::__core::fmt::Debug for $entity { 141 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 142 (self as &dyn $crate::__core::fmt::Display).fmt(f) 143 } 144 } 145 }; 146 147 // Alternate form for tuples we can't directly construct; providing "to" and "from" expressions 148 // to turn an index *into* an entity, or get an index *from* an entity. 149 ($entity:ident, $display_prefix:expr, $arg:ident, $to_expr:expr, $from_expr:expr) => { 150 impl $crate::EntityRef for $entity { 151 #[inline] 152 fn new(index: usize) -> Self { 153 debug_assert!(index < ($crate::__core::u32::MAX as usize)); 154 let $arg = index as u32; 155 $to_expr 156 } 157 158 #[inline] 159 fn index(self) -> usize { 160 let $arg = self; 161 $from_expr as usize 162 } 163 } 164 165 impl $crate::packed_option::ReservedValue for $entity { 166 #[inline] 167 fn reserved_value() -> $entity { 168 $entity::from_u32($crate::__core::u32::MAX) 169 } 170 171 #[inline] 172 fn is_reserved_value(&self) -> bool { 173 self.as_u32() == $crate::__core::u32::MAX 174 } 175 } 176 177 impl $entity { 178 /// Create a new instance from a `u32`. 179 #[allow(dead_code)] 180 #[inline] 181 pub fn from_u32(x: u32) -> Self { 182 debug_assert!(x < $crate::__core::u32::MAX); 183 let $arg = x; 184 $to_expr 185 } 186 187 /// Return the underlying index value as a `u32`. 188 #[allow(dead_code)] 189 #[inline] 190 pub fn as_u32(self) -> u32 { 191 let $arg = self; 192 $from_expr 193 } 194 } 195 196 impl $crate::__core::fmt::Display for $entity { 197 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 198 write!(f, concat!($display_prefix, "{}"), self.as_u32()) 199 } 200 } 201 202 impl $crate::__core::fmt::Debug for $entity { 203 fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result { 204 (self as &dyn $crate::__core::fmt::Display).fmt(f) 205 } 206 } 207 }; 208 } 209 210 pub mod packed_option; 211 212 mod boxed_slice; 213 mod iter; 214 mod keys; 215 mod list; 216 mod map; 217 mod primary; 218 mod set; 219 mod sparse; 220 221 pub use self::boxed_slice::BoxedSlice; 222 pub use self::iter::{Iter, IterMut}; 223 pub use self::keys::Keys; 224 pub use self::list::{EntityList, ListPool}; 225 pub use self::map::SecondaryMap; 226 pub use self::primary::PrimaryMap; 227 pub use self::set::EntitySet; 228 pub use self::sparse::{SparseMap, SparseMapValue, SparseSet}; 229 230 /// A collection of tests to ensure that use of the different `entity_impl!` forms will generate 231 /// `EntityRef` implementations that behave the same way. 232 #[cfg(test)] 233 mod tests { 234 /// A macro used to emit some basic tests to show that entities behave as we expect. 235 macro_rules! entity_test { 236 ($entity:ident) => { 237 #[test] 238 fn from_usize_to_u32() { 239 let e = $entity::new(42); 240 assert_eq!(e.as_u32(), 42_u32); 241 } 242 243 #[test] 244 fn from_u32_to_usize() { 245 let e = $entity::from_u32(42); 246 assert_eq!(e.index(), 42_usize); 247 } 248 249 #[test] 250 fn comparisons_work() { 251 let a = $entity::from_u32(42); 252 let b = $entity::new(42); 253 assert_eq!(a, b); 254 } 255 256 #[should_panic] 257 #[test] 258 fn cannot_construct_from_reserved_u32() { 259 use crate::packed_option::ReservedValue; 260 let reserved = $entity::reserved_value().as_u32(); 261 let _ = $entity::from_u32(reserved); // panic 262 } 263 264 #[should_panic] 265 #[test] 266 fn cannot_construct_from_reserved_usize() { 267 use crate::packed_option::ReservedValue; 268 let reserved = $entity::reserved_value().index(); 269 let _ = $entity::new(reserved); // panic 270 } 271 }; 272 } 273 274 /// Test cases for a plain ol' `EntityRef` implementation. 275 mod basic_entity { 276 use crate::EntityRef; 277 #[derive(Clone, Copy, Debug, PartialEq, Eq)] 278 struct BasicEntity(u32); 279 entity_impl!(BasicEntity); 280 entity_test!(BasicEntity); 281 } 282 283 /// Test cases for an `EntityRef` implementation that includes a display prefix. 284 mod prefix_entity { 285 use crate::EntityRef; 286 #[derive(Clone, Copy, PartialEq, Eq)] 287 struct PrefixEntity(u32); 288 entity_impl!(PrefixEntity, "prefix-"); 289 entity_test!(PrefixEntity); 290 291 #[test] 292 fn display_prefix_works() { 293 let e = PrefixEntity::new(0); 294 assert_eq!(alloc::format!("{}", e), "prefix-0"); 295 } 296 } 297 298 /// Test cases for an `EntityRef` implementation for a type we can only construct through 299 /// other means, such as calls to `core::convert::From<u32>`. 300 mod other_entity { 301 mod inner { 302 #[derive(Clone, Copy, PartialEq, Eq)] 303 pub struct InnerEntity(u32); 304 305 impl From<u32> for InnerEntity { 306 fn from(x: u32) -> Self { 307 Self(x) 308 } 309 } 310 311 impl From<InnerEntity> for u32 { 312 fn from(x: InnerEntity) -> Self { 313 x.0 314 } 315 } 316 } 317 318 use {self::inner::InnerEntity, crate::EntityRef}; 319 entity_impl!(InnerEntity, "inner-", i, InnerEntity::from(i), u32::from(i)); 320 entity_test!(InnerEntity); 321 322 #[test] 323 fn display_prefix_works() { 324 let e = InnerEntity::new(0); 325 assert_eq!(alloc::format!("{}", e), "inner-0"); 326 } 327 } 328 } 329