bevy_ecs/storage/
sparse_set.rs

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

bevy_ecs/storage/
sparse_set.rs
