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 134 pub mod packed_option; 135 136 mod boxed_slice; 137 mod iter; 138 mod keys; 139 mod list; 140 mod map; 141 mod primary; 142 mod set; 143 mod sparse; 144 145 pub use self::boxed_slice::BoxedSlice; 146 pub use self::iter::{Iter, IterMut}; 147 pub use self::keys::Keys; 148 pub use self::list::{EntityList, ListPool}; 149 pub use self::map::SecondaryMap; 150 pub use self::primary::PrimaryMap; 151 pub use self::set::EntitySet; 152 pub use self::sparse::{SparseMap, SparseMapValue, SparseSet}; 153