bevy_ecs/storage/
sparse_set.rs

1use crate::{
2    change_detection::MaybeLocation,
3    component::{ComponentId, ComponentInfo, ComponentTicks, Tick, TickCells},
4    entity::Entity,
5    storage::{Column, TableRow},
6};
7use alloc::{boxed::Box, vec::Vec};
8use bevy_ptr::{OwningPtr, Ptr};
9use core::{cell::UnsafeCell, hash::Hash, marker::PhantomData, panic::Location};
10use nonmax::NonMaxUsize;
11
12type EntityIndex = u32;
13
14#[derive(Debug)]
15pub(crate) struct SparseArray<I, V = I> {
16    values: Vec<Option<V>>,
17    marker: PhantomData<I>,
18}
19
20/// A space-optimized version of [`SparseArray`] that cannot be changed
21/// after construction.
22#[derive(Debug)]
23pub(crate) struct ImmutableSparseArray<I, V = I> {
24    values: Box<[Option<V>]>,
25    marker: PhantomData<I>,
26}
27
28impl<I: SparseSetIndex, V> Default for SparseArray<I, V> {
29    fn default() -> Self {
30        Self::new()
31    }
32}
33
34impl<I, V> SparseArray<I, V> {
35    #[inline]
36    pub const fn new() -> Self {
37        Self {
38            values: Vec::new(),
39            marker: PhantomData,
40        }
41    }
42}
43
44macro_rules! impl_sparse_array {
45    ($ty:ident) => {
46        impl<I: SparseSetIndex, V> $ty<I, V> {
47            /// Returns `true` if the collection contains a value for the specified `index`.
48            #[inline]
49            pub fn contains(&self, index: I) -> bool {
50                let index = index.sparse_set_index();
51                self.values.get(index).is_some_and(Option::is_some)
52            }
53
54            /// Returns a reference to the value at `index`.
55            ///
56            /// Returns `None` if `index` does not have a value or if `index` is out of bounds.
57            #[inline]
58            pub fn get(&self, index: I) -> Option<&V> {
59                let index = index.sparse_set_index();
60                self.values.get(index).and_then(Option::as_ref)
61            }
62        }
63    };
64}
65
66impl_sparse_array!(SparseArray);
67impl_sparse_array!(ImmutableSparseArray);
68
69impl<I: SparseSetIndex, V> SparseArray<I, V> {
70    /// Inserts `value` at `index` in the array.
71    ///
72    /// If `index` is out-of-bounds, this will enlarge the buffer to accommodate it.
73    #[inline]
74    pub fn insert(&mut self, index: I, value: V) {
75        let index = index.sparse_set_index();
76        if index >= self.values.len() {
77            self.values.resize_with(index + 1, || None);
78        }
79        self.values[index] = Some(value);
80    }
81
82    /// Returns a mutable reference to the value at `index`.
83    ///
84    /// Returns `None` if `index` does not have a value or if `index` is out of bounds.
85    #[inline]
86    pub fn get_mut(&mut self, index: I) -> Option<&mut V> {
87        let index = index.sparse_set_index();
88        self.values.get_mut(index).and_then(Option::as_mut)
89    }
90
91    /// Removes and returns the value stored at `index`.
92    ///
93    /// Returns `None` if `index` did not have a value or if `index` is out of bounds.
94    #[inline]
95    pub fn remove(&mut self, index: I) -> Option<V> {
96        let index = index.sparse_set_index();
97        self.values.get_mut(index).and_then(Option::take)
98    }
99
100    /// Removes all of the values stored within.
101    pub fn clear(&mut self) {
102        self.values.clear();
103    }
104
105    /// Converts the [`SparseArray`] into an immutable variant.
106    pub(crate) fn into_immutable(self) -> ImmutableSparseArray<I, V> {
107        ImmutableSparseArray {
108            values: self.values.into_boxed_slice(),
109            marker: PhantomData,
110        }
111    }
112}
113
114/// A sparse data structure of [`Component`](crate::component::Component)s.
115///
116/// Designed for relatively fast insertions and deletions.
117#[derive(Debug)]
118pub struct ComponentSparseSet {
119    dense: Column,
120    // Internally this only relies on the Entity index to keep track of where the component data is
121    // stored for entities that are alive. The generation is not required, but is stored
122    // in debug builds to validate that access is correct.
123    #[cfg(not(debug_assertions))]
124    entities: Vec<EntityIndex>,
125    #[cfg(debug_assertions)]
126    entities: Vec<Entity>,
127    sparse: SparseArray<EntityIndex, TableRow>,
128}
129
130impl ComponentSparseSet {
131    /// Creates a new [`ComponentSparseSet`] with a given component type layout and
132    /// initial `capacity`.
133    pub(crate) fn new(component_info: &ComponentInfo, capacity: usize) -> Self {
134        Self {
135            dense: Column::with_capacity(component_info, capacity),
136            entities: Vec::with_capacity(capacity),
137            sparse: Default::default(),
138        }
139    }
140
141    /// Removes all of the values stored within.
142    pub(crate) fn clear(&mut self) {
143        self.dense.clear();
144        self.entities.clear();
145        self.sparse.clear();
146    }
147
148    /// Returns the number of component values in the sparse set.
149    #[inline]
150    pub fn len(&self) -> usize {
151        self.dense.len()
152    }
153
154    /// Returns `true` if the sparse set contains no component values.
155    #[inline]
156    pub fn is_empty(&self) -> bool {
157        self.dense.len() == 0
158    }
159
160    /// Inserts the `entity` key and component `value` pair into this sparse
161    /// set.
162    ///
163    /// # Safety
164    /// The `value` pointer must point to a valid address that matches the [`Layout`](std::alloc::Layout)
165    /// inside the [`ComponentInfo`] given when constructing this sparse set.
166    pub(crate) unsafe fn insert(
167        &mut self,
168        entity: Entity,
169        value: OwningPtr<'_>,
170        change_tick: Tick,
171        caller: MaybeLocation,
172    ) {
173        if let Some(&dense_index) = self.sparse.get(entity.index()) {
174            #[cfg(debug_assertions)]
175            assert_eq!(entity, self.entities[dense_index.as_usize()]);
176            self.dense.replace(dense_index, value, change_tick, caller);
177        } else {
178            let dense_index = self.dense.len();
179            self.dense
180                .push(value, ComponentTicks::new(change_tick), caller);
181            self.sparse
182                .insert(entity.index(), TableRow::from_usize(dense_index));
183            #[cfg(debug_assertions)]
184            assert_eq!(self.entities.len(), dense_index);
185            #[cfg(not(debug_assertions))]
186            self.entities.push(entity.index());
187            #[cfg(debug_assertions)]
188            self.entities.push(entity);
189        }
190    }
191
192    /// Returns `true` if the sparse set has a component value for the provided `entity`.
193    #[inline]
194    pub fn contains(&self, entity: Entity) -> bool {
195        #[cfg(debug_assertions)]
196        {
197            if let Some(&dense_index) = self.sparse.get(entity.index()) {
198                #[cfg(debug_assertions)]
199                assert_eq!(entity, self.entities[dense_index.as_usize()]);
200                true
201            } else {
202                false
203            }
204        }
205        #[cfg(not(debug_assertions))]
206        self.sparse.contains(entity.index())
207    }
208
209    /// Returns a reference to the entity's component value.
210    ///
211    /// Returns `None` if `entity` does not have a component in the sparse set.
212    #[inline]
213    pub fn get(&self, entity: Entity) -> Option<Ptr<'_>> {
214        self.sparse.get(entity.index()).map(|&dense_index| {
215            #[cfg(debug_assertions)]
216            assert_eq!(entity, self.entities[dense_index.as_usize()]);
217            // SAFETY: if the sparse index points to something in the dense vec, it exists
218            unsafe { self.dense.get_data_unchecked(dense_index) }
219        })
220    }
221
222    /// Returns references to the entity's component value and its added and changed ticks.
223    ///
224    /// Returns `None` if `entity` does not have a component in the sparse set.
225    #[inline]
226    pub fn get_with_ticks(
227        &self,
228        entity: Entity,
229    ) -> Option<(
230        Ptr<'_>,
231        TickCells<'_>,
232        MaybeLocation<&UnsafeCell<&'static Location<'static>>>,
233    )> {
234        let dense_index = *self.sparse.get(entity.index())?;
235        #[cfg(debug_assertions)]
236        assert_eq!(entity, self.entities[dense_index.as_usize()]);
237        // SAFETY: if the sparse index points to something in the dense vec, it exists
238        unsafe {
239            Some((
240                self.dense.get_data_unchecked(dense_index),
241                TickCells {
242                    added: self.dense.get_added_tick_unchecked(dense_index),
243                    changed: self.dense.get_changed_tick_unchecked(dense_index),
244                },
245                self.dense.get_changed_by_unchecked(dense_index),
246            ))
247        }
248    }
249
250    /// Returns a reference to the "added" tick of the entity's component value.
251    ///
252    /// Returns `None` if `entity` does not have a component in the sparse set.
253    #[inline]
254    pub fn get_added_tick(&self, entity: Entity) -> Option<&UnsafeCell<Tick>> {
255        let dense_index = *self.sparse.get(entity.index())?;
256        #[cfg(debug_assertions)]
257        assert_eq!(entity, self.entities[dense_index.as_usize()]);
258        // SAFETY: if the sparse index points to something in the dense vec, it exists
259        unsafe { Some(self.dense.get_added_tick_unchecked(dense_index)) }
260    }
261
262    /// Returns a reference to the "changed" tick of the entity's component value.
263    ///
264    /// Returns `None` if `entity` does not have a component in the sparse set.
265    #[inline]
266    pub fn get_changed_tick(&self, entity: Entity) -> Option<&UnsafeCell<Tick>> {
267        let dense_index = *self.sparse.get(entity.index())?;
268        #[cfg(debug_assertions)]
269        assert_eq!(entity, self.entities[dense_index.as_usize()]);
270        // SAFETY: if the sparse index points to something in the dense vec, it exists
271        unsafe { Some(self.dense.get_changed_tick_unchecked(dense_index)) }
272    }
273
274    /// Returns a reference to the "added" and "changed" ticks of the entity's component value.
275    ///
276    /// Returns `None` if `entity` does not have a component in the sparse set.
277    #[inline]
278    pub fn get_ticks(&self, entity: Entity) -> Option<ComponentTicks> {
279        let dense_index = *self.sparse.get(entity.index())?;
280        #[cfg(debug_assertions)]
281        assert_eq!(entity, self.entities[dense_index.as_usize()]);
282        // SAFETY: if the sparse index points to something in the dense vec, it exists
283        unsafe { Some(self.dense.get_ticks_unchecked(dense_index)) }
284    }
285
286    /// Returns a reference to the calling location that last changed the entity's component value.
287    ///
288    /// Returns `None` if `entity` does not have a component in the sparse set.
289    #[inline]
290    pub fn get_changed_by(
291        &self,
292        entity: Entity,
293    ) -> MaybeLocation<Option<&UnsafeCell<&'static Location<'static>>>> {
294        MaybeLocation::new_with_flattened(|| {
295            let dense_index = *self.sparse.get(entity.index())?;
296            #[cfg(debug_assertions)]
297            assert_eq!(entity, self.entities[dense_index.as_usize()]);
298            // SAFETY: if the sparse index points to something in the dense vec, it exists
299            unsafe { Some(self.dense.get_changed_by_unchecked(dense_index)) }
300        })
301    }
302
303    /// Returns the drop function for the component type stored in the sparse set,
304    /// or `None` if it doesn't need to be dropped.
305    #[inline]
306    pub fn get_drop(&self) -> Option<unsafe fn(OwningPtr<'_>)> {
307        self.dense.get_drop()
308    }
309
310    /// Removes the `entity` from this sparse set and returns a pointer to the associated value (if
311    /// it exists).
312    #[must_use = "The returned pointer must be used to drop the removed component."]
313    pub(crate) fn remove_and_forget(&mut self, entity: Entity) -> Option<OwningPtr<'_>> {
314        self.sparse.remove(entity.index()).map(|dense_index| {
315            #[cfg(debug_assertions)]
316            assert_eq!(entity, self.entities[dense_index.as_usize()]);
317            self.entities.swap_remove(dense_index.as_usize());
318            let is_last = dense_index.as_usize() == self.dense.len() - 1;
319            // SAFETY: dense_index was just removed from `sparse`, which ensures that it is valid
320            let (value, _, _) = unsafe { self.dense.swap_remove_and_forget_unchecked(dense_index) };
321            if !is_last {
322                let swapped_entity = self.entities[dense_index.as_usize()];
323                #[cfg(not(debug_assertions))]
324                let index = swapped_entity;
325                #[cfg(debug_assertions)]
326                let index = swapped_entity.index();
327                *self.sparse.get_mut(index).unwrap() = dense_index;
328            }
329            value
330        })
331    }
332
333    /// Removes (and drops) the entity's component value from the sparse set.
334    ///
335    /// Returns `true` if `entity` had a component value in the sparse set.
336    pub(crate) fn remove(&mut self, entity: Entity) -> bool {
337        if let Some(dense_index) = self.sparse.remove(entity.index()) {
338            #[cfg(debug_assertions)]
339            assert_eq!(entity, self.entities[dense_index.as_usize()]);
340            self.entities.swap_remove(dense_index.as_usize());
341            let is_last = dense_index.as_usize() == self.dense.len() - 1;
342            // SAFETY: if the sparse index points to something in the dense vec, it exists
343            unsafe {
344                self.dense.swap_remove_unchecked(dense_index);
345            }
346            if !is_last {
347                let swapped_entity = self.entities[dense_index.as_usize()];
348                #[cfg(not(debug_assertions))]
349                let index = swapped_entity;
350                #[cfg(debug_assertions)]
351                let index = swapped_entity.index();
352                *self.sparse.get_mut(index).unwrap() = dense_index;
353            }
354            true
355        } else {
356            false
357        }
358    }
359
360    pub(crate) fn check_change_ticks(&mut self, change_tick: Tick) {
361        self.dense.check_change_ticks(change_tick);
362    }
363}
364
365/// A data structure that blends dense and sparse storage
366///
367/// `I` is the type of the indices, while `V` is the type of data stored in the dense storage.
368#[derive(Debug)]
369pub struct SparseSet<I, V: 'static> {
370    dense: Vec<V>,
371    indices: Vec<I>,
372    sparse: SparseArray<I, NonMaxUsize>,
373}
374
375/// A space-optimized version of [`SparseSet`] that cannot be changed
376/// after construction.
377#[derive(Debug)]
378pub(crate) struct ImmutableSparseSet<I, V: 'static> {
379    dense: Box<[V]>,
380    indices: Box<[I]>,
381    sparse: ImmutableSparseArray<I, NonMaxUsize>,
382}
383
384macro_rules! impl_sparse_set {
385    ($ty:ident) => {
386        impl<I: SparseSetIndex, V> $ty<I, V> {
387            /// Returns the number of elements in the sparse set.
388            #[inline]
389            pub fn len(&self) -> usize {
390                self.dense.len()
391            }
392
393            /// Returns `true` if the sparse set contains a value for `index`.
394            #[inline]
395            pub fn contains(&self, index: I) -> bool {
396                self.sparse.contains(index)
397            }
398
399            /// Returns a reference to the value for `index`.
400            ///
401            /// Returns `None` if `index` does not have a value in the sparse set.
402            pub fn get(&self, index: I) -> Option<&V> {
403                self.sparse.get(index).map(|dense_index| {
404                    // SAFETY: if the sparse index points to something in the dense vec, it exists
405                    unsafe { self.dense.get_unchecked(dense_index.get()) }
406                })
407            }
408
409            /// Returns a mutable reference to the value for `index`.
410            ///
411            /// Returns `None` if `index` does not have a value in the sparse set.
412            pub fn get_mut(&mut self, index: I) -> Option<&mut V> {
413                let dense = &mut self.dense;
414                self.sparse.get(index).map(move |dense_index| {
415                    // SAFETY: if the sparse index points to something in the dense vec, it exists
416                    unsafe { dense.get_unchecked_mut(dense_index.get()) }
417                })
418            }
419
420            /// Returns an iterator visiting all keys (indices) in arbitrary order.
421            pub fn indices(&self) -> impl Iterator<Item = I> + Clone + '_ {
422                self.indices.iter().cloned()
423            }
424
425            /// Returns an iterator visiting all values in arbitrary order.
426            pub fn values(&self) -> impl Iterator<Item = &V> {
427                self.dense.iter()
428            }
429
430            /// Returns an iterator visiting all values mutably in arbitrary order.
431            pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
432                self.dense.iter_mut()
433            }
434
435            /// Returns an iterator visiting all key-value pairs in arbitrary order, with references to the values.
436            pub fn iter(&self) -> impl Iterator<Item = (&I, &V)> {
437                self.indices.iter().zip(self.dense.iter())
438            }
439
440            /// Returns an iterator visiting all key-value pairs in arbitrary order, with mutable references to the values.
441            pub fn iter_mut(&mut self) -> impl Iterator<Item = (&I, &mut V)> {
442                self.indices.iter().zip(self.dense.iter_mut())
443            }
444        }
445    };
446}
447
448impl_sparse_set!(SparseSet);
449impl_sparse_set!(ImmutableSparseSet);
450
451impl<I: SparseSetIndex, V> Default for SparseSet<I, V> {
452    fn default() -> Self {
453        Self::new()
454    }
455}
456
457impl<I, V> SparseSet<I, V> {
458    /// Creates a new [`SparseSet`].
459    pub const fn new() -> Self {
460        Self {
461            dense: Vec::new(),
462            indices: Vec::new(),
463            sparse: SparseArray::new(),
464        }
465    }
466}
467
468impl<I: SparseSetIndex, V> SparseSet<I, V> {
469    /// Creates a new [`SparseSet`] with a specified initial capacity.
470    pub fn with_capacity(capacity: usize) -> Self {
471        Self {
472            dense: Vec::with_capacity(capacity),
473            indices: Vec::with_capacity(capacity),
474            sparse: Default::default(),
475        }
476    }
477
478    /// Returns the total number of elements the [`SparseSet`] can hold without needing to reallocate.
479    #[inline]
480    pub fn capacity(&self) -> usize {
481        self.dense.capacity()
482    }
483
484    /// Inserts `value` at `index`.
485    ///
486    /// If a value was already present at `index`, it will be overwritten.
487    pub fn insert(&mut self, index: I, value: V) {
488        if let Some(dense_index) = self.sparse.get(index.clone()).cloned() {
489            // SAFETY: dense indices stored in self.sparse always exist
490            unsafe {
491                *self.dense.get_unchecked_mut(dense_index.get()) = value;
492            }
493        } else {
494            self.sparse
495                .insert(index.clone(), NonMaxUsize::new(self.dense.len()).unwrap());
496            self.indices.push(index);
497            self.dense.push(value);
498        }
499    }
500
501    /// Returns a reference to the value for `index`, inserting one computed from `func`
502    /// if not already present.
503    pub fn get_or_insert_with(&mut self, index: I, func: impl FnOnce() -> V) -> &mut V {
504        if let Some(dense_index) = self.sparse.get(index.clone()).cloned() {
505            // SAFETY: dense indices stored in self.sparse always exist
506            unsafe { self.dense.get_unchecked_mut(dense_index.get()) }
507        } else {
508            let value = func();
509            let dense_index = self.dense.len();
510            self.sparse
511                .insert(index.clone(), NonMaxUsize::new(dense_index).unwrap());
512            self.indices.push(index);
513            self.dense.push(value);
514            // SAFETY: dense index was just populated above
515            unsafe { self.dense.get_unchecked_mut(dense_index) }
516        }
517    }
518
519    /// Returns `true` if the sparse set contains no elements.
520    #[inline]
521    pub fn is_empty(&self) -> bool {
522        self.dense.len() == 0
523    }
524
525    /// Removes and returns the value for `index`.
526    ///
527    /// Returns `None` if `index` does not have a value in the sparse set.
528    pub fn remove(&mut self, index: I) -> Option<V> {
529        self.sparse.remove(index).map(|dense_index| {
530            let index = dense_index.get();
531            let is_last = index == self.dense.len() - 1;
532            let value = self.dense.swap_remove(index);
533            self.indices.swap_remove(index);
534            if !is_last {
535                let swapped_index = self.indices[index].clone();
536                *self.sparse.get_mut(swapped_index).unwrap() = dense_index;
537            }
538            value
539        })
540    }
541
542    /// Clears all of the elements from the sparse set.
543    pub fn clear(&mut self) {
544        self.dense.clear();
545        self.indices.clear();
546        self.sparse.clear();
547    }
548
549    /// Converts the sparse set into its immutable variant.
550    pub(crate) fn into_immutable(self) -> ImmutableSparseSet<I, V> {
551        ImmutableSparseSet {
552            dense: self.dense.into_boxed_slice(),
553            indices: self.indices.into_boxed_slice(),
554            sparse: self.sparse.into_immutable(),
555        }
556    }
557}
558
559/// Represents something that can be stored in a [`SparseSet`] as an integer.
560///
561/// Ideally, the `usize` values should be very small (ie: incremented starting from
562/// zero), as the number of bits needed to represent a `SparseSetIndex` in a `FixedBitSet`
563/// is proportional to the **value** of those `usize`.
564pub trait SparseSetIndex: Clone + PartialEq + Eq + Hash {
565    /// Gets the sparse set index corresponding to this instance.
566    fn sparse_set_index(&self) -> usize;
567    /// Creates a new instance of this type with the specified index.
568    fn get_sparse_set_index(value: usize) -> Self;
569}
570
571macro_rules! impl_sparse_set_index {
572    ($($ty:ty),+) => {
573        $(impl SparseSetIndex for $ty {
574            #[inline]
575            fn sparse_set_index(&self) -> usize {
576                *self as usize
577            }
578
579            #[inline]
580            fn get_sparse_set_index(value: usize) -> Self {
581                value as $ty
582            }
583        })*
584    };
585}
586
587impl_sparse_set_index!(u8, u16, u32, u64, usize);
588
589/// A collection of [`ComponentSparseSet`] storages, indexed by [`ComponentId`]
590///
591/// Can be accessed via [`Storages`](crate::storage::Storages)
592#[derive(Default)]
593pub struct SparseSets {
594    sets: SparseSet<ComponentId, ComponentSparseSet>,
595}
596
597impl SparseSets {
598    /// Returns the number of [`ComponentSparseSet`]s this collection contains.
599    #[inline]
600    pub fn len(&self) -> usize {
601        self.sets.len()
602    }
603
604    /// Returns true if this collection contains no [`ComponentSparseSet`]s.
605    #[inline]
606    pub fn is_empty(&self) -> bool {
607        self.sets.is_empty()
608    }
609
610    /// An Iterator visiting all ([`ComponentId`], [`ComponentSparseSet`]) pairs.
611    /// NOTE: Order is not guaranteed.
612    pub fn iter(&self) -> impl Iterator<Item = (ComponentId, &ComponentSparseSet)> {
613        self.sets.iter().map(|(id, data)| (*id, data))
614    }
615
616    /// Gets a reference to the [`ComponentSparseSet`] of a [`ComponentId`]. This may be `None` if the component has never been spawned.
617    #[inline]
618    pub fn get(&self, component_id: ComponentId) -> Option<&ComponentSparseSet> {
619        self.sets.get(component_id)
620    }
621
622    /// Gets a mutable reference of [`ComponentSparseSet`] of a [`ComponentInfo`].
623    /// Create a new [`ComponentSparseSet`] if not exists.
624    pub(crate) fn get_or_insert(
625        &mut self,
626        component_info: &ComponentInfo,
627    ) -> &mut ComponentSparseSet {
628        if !self.sets.contains(component_info.id()) {
629            self.sets.insert(
630                component_info.id(),
631                ComponentSparseSet::new(component_info, 64),
632            );
633        }
634
635        self.sets.get_mut(component_info.id()).unwrap()
636    }
637
638    /// Gets a mutable reference to the [`ComponentSparseSet`] of a [`ComponentId`]. This may be `None` if the component has never been spawned.
639    pub(crate) fn get_mut(&mut self, component_id: ComponentId) -> Option<&mut ComponentSparseSet> {
640        self.sets.get_mut(component_id)
641    }
642
643    /// Clear entities stored in each [`ComponentSparseSet`]
644    pub(crate) fn clear_entities(&mut self) {
645        for set in self.sets.values_mut() {
646            set.clear();
647        }
648    }
649
650    pub(crate) fn check_change_ticks(&mut self, change_tick: Tick) {
651        for set in self.sets.values_mut() {
652            set.check_change_ticks(change_tick);
653        }
654    }
655}
656
657#[cfg(test)]
658mod tests {
659    use super::SparseSets;
660    use crate::{
661        component::{Component, ComponentDescriptor, ComponentId, ComponentInfo},
662        entity::Entity,
663        storage::SparseSet,
664    };
665    use alloc::{vec, vec::Vec};
666
667    #[derive(Debug, Eq, PartialEq)]
668    struct Foo(usize);
669
670    #[test]
671    fn sparse_set() {
672        let mut set = SparseSet::<Entity, Foo>::default();
673        let e0 = Entity::from_raw(0);
674        let e1 = Entity::from_raw(1);
675        let e2 = Entity::from_raw(2);
676        let e3 = Entity::from_raw(3);
677        let e4 = Entity::from_raw(4);
678
679        set.insert(e1, Foo(1));
680        set.insert(e2, Foo(2));
681        set.insert(e3, Foo(3));
682
683        assert_eq!(set.get(e0), None);
684        assert_eq!(set.get(e1), Some(&Foo(1)));
685        assert_eq!(set.get(e2), Some(&Foo(2)));
686        assert_eq!(set.get(e3), Some(&Foo(3)));
687        assert_eq!(set.get(e4), None);
688
689        {
690            let iter_results = set.values().collect::<Vec<_>>();
691            assert_eq!(iter_results, vec![&Foo(1), &Foo(2), &Foo(3)]);
692        }
693
694        assert_eq!(set.remove(e2), Some(Foo(2)));
695        assert_eq!(set.remove(e2), None);
696
697        assert_eq!(set.get(e0), None);
698        assert_eq!(set.get(e1), Some(&Foo(1)));
699        assert_eq!(set.get(e2), None);
700        assert_eq!(set.get(e3), Some(&Foo(3)));
701        assert_eq!(set.get(e4), None);
702
703        assert_eq!(set.remove(e1), Some(Foo(1)));
704
705        assert_eq!(set.get(e0), None);
706        assert_eq!(set.get(e1), None);
707        assert_eq!(set.get(e2), None);
708        assert_eq!(set.get(e3), Some(&Foo(3)));
709        assert_eq!(set.get(e4), None);
710
711        set.insert(e1, Foo(10));
712
713        assert_eq!(set.get(e1), Some(&Foo(10)));
714
715        *set.get_mut(e1).unwrap() = Foo(11);
716        assert_eq!(set.get(e1), Some(&Foo(11)));
717    }
718
719    #[test]
720    fn sparse_sets() {
721        let mut sets = SparseSets::default();
722
723        #[derive(Component, Default, Debug)]
724        struct TestComponent1;
725
726        #[derive(Component, Default, Debug)]
727        struct TestComponent2;
728
729        assert_eq!(sets.len(), 0);
730        assert!(sets.is_empty());
731
732        register_component::<TestComponent1>(&mut sets, 1);
733        assert_eq!(sets.len(), 1);
734
735        register_component::<TestComponent2>(&mut sets, 2);
736        assert_eq!(sets.len(), 2);
737
738        // check its shape by iter
739        let mut collected_sets = sets
740            .iter()
741            .map(|(id, set)| (id, set.len()))
742            .collect::<Vec<_>>();
743        collected_sets.sort();
744        assert_eq!(
745            collected_sets,
746            vec![(ComponentId::new(1), 0), (ComponentId::new(2), 0),]
747        );
748
749        fn register_component<T: Component>(sets: &mut SparseSets, id: usize) {
750            let descriptor = ComponentDescriptor::new::<T>();
751            let id = ComponentId::new(id);
752            let info = ComponentInfo::new(id, descriptor);
753            sets.get_or_insert(&info);
754        }
755    }
756}
bevy_ecs/storage/sparse_set.rs

bevy_ecs/storage/
sparse_set.rs
