bevy_ecs/storage/
sparse_set.rs

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

bevy_ecs/storage/
sparse_set.rs
