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.
new(_: usize) -> Self49 fn new(_: usize) -> Self;
50
51 /// Get the index that was used to create this entity reference.
index(self) -> usize52 fn index(self) -> usize;
53 }
54
55 /// Iterate over a `Range<E: EntityRef>`, yielding a sequence of `E` items.
56 #[inline]
iter_entity_range<E>(range: Range<E>) -> IterEntityRange<E> where E: EntityRef,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]
next(&mut self) -> Option<Self::Item>80 fn next(&mut self) -> Option<Self::Item> {
81 let i = self.range.next()?;
82 Some(E::new(i))
83 }
84
85 #[inline]
size_hint(&self) -> (usize, Option<usize>)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]
next_back(&mut self) -> Option<Self::Item>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::{IntoIter, 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]
display_prefix_works()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 {
from(x: u32) -> Self369 fn from(x: u32) -> Self {
370 Self(x)
371 }
372 }
373
374 impl From<InnerEntity> for u32 {
from(x: InnerEntity) -> Self375 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]
display_prefix_works()386 fn display_prefix_works() {
387 let e = InnerEntity::new(0);
388 assert_eq!(alloc::format!("{e}"), "inner-0");
389 }
390 }
391 }
392