shipyard/sparse_set/
mod.rs

1mod add_component;
2mod bulk_add_entity;
3mod delete;
4mod drain;
5mod memory_usage;
6mod remove;
7mod sparse_array;
8#[cfg(feature = "thread_local")]
9mod thread_local;
10mod window;
11
12pub use add_component::TupleAddComponent;
13pub use bulk_add_entity::BulkAddEntity;
14pub use delete::TupleDelete;
15pub use drain::SparseSetDrain;
16pub use memory_usage::{SparseSetMemory, SparseSetMemoryUsage};
17pub use remove::TupleRemove;
18pub use sparse_array::SparseArray;
19#[doc(hidden)]
20pub use window::RawEntityIdAccess;
21
22pub(crate) use window::{FullRawWindow, FullRawWindowMut};
23
24use crate::all_storages::AllStorages;
25use crate::component::Component;
26use crate::entity_id::EntityId;
27use crate::error;
28use crate::memory_usage::StorageMemoryUsage;
29use crate::r#mut::Mut;
30use crate::storage::{SBoxBuilder, Storage, StorageId};
31use crate::tracking::{Tracking, TrackingTimestamp};
32use alloc::boxed::Box;
33use alloc::vec::Vec;
34use core::any::type_name;
35use core::mem::size_of;
36use core::{
37    cmp::{Ord, Ordering},
38    fmt,
39};
40
41pub(crate) const BUCKET_SIZE: usize = 256 / size_of::<EntityId>();
42
43/// Default component storage.
44// A sparse array is a data structure with 2 vectors: one sparse, the other dense.
45// Only usize can be added. On insertion, the number is pushed into the dense vector
46// and sparse[number] is set to dense.len() - 1.
47// For all number present in the sparse array, dense[sparse[number]] == number.
48// For all other values if set sparse[number] will have any value left there
49// and if set dense[sparse[number]] != number.
50// We can't be limited to store solely integers, this is why there is a third vector.
51// It mimics the dense vector in regard to insertion/deletion.
52pub struct SparseSet<T: Component> {
53    pub(crate) sparse: SparseArray<EntityId, BUCKET_SIZE>,
54    pub(crate) dense: Vec<EntityId>,
55    pub(crate) data: Vec<T>,
56    pub(crate) last_insert: TrackingTimestamp,
57    pub(crate) last_modified: TrackingTimestamp,
58    pub(crate) insertion_data: Vec<TrackingTimestamp>,
59    pub(crate) modification_data: Vec<TrackingTimestamp>,
60    pub(crate) deletion_data: Vec<(EntityId, TrackingTimestamp, T)>,
61    pub(crate) removal_data: Vec<(EntityId, TrackingTimestamp)>,
62    pub(crate) is_tracking_insertion: bool,
63    pub(crate) is_tracking_modification: bool,
64    pub(crate) is_tracking_deletion: bool,
65    pub(crate) is_tracking_removal: bool,
66    #[allow(clippy::type_complexity)]
67    on_insertion: Option<Box<dyn FnMut(EntityId, &T) + Send + Sync>>,
68    #[allow(clippy::type_complexity)]
69    on_removal: Option<Box<dyn FnMut(EntityId, &T) + Send + Sync>>,
70    clone: Option<fn(&T) -> T>,
71}
72
73impl<T: fmt::Debug + Component> fmt::Debug for SparseSet<T> {
74    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
75        f.debug_list()
76            .entries(self.dense.iter().zip(&self.data))
77            .finish()
78    }
79}
80
81impl<T: Component> SparseSet<T> {
82    #[inline]
83    pub(crate) fn new() -> Self {
84        SparseSet {
85            sparse: SparseArray::new(),
86            dense: Vec::new(),
87            data: Vec::new(),
88            last_insert: TrackingTimestamp::new(0),
89            last_modified: TrackingTimestamp::new(0),
90            insertion_data: Vec::new(),
91            modification_data: Vec::new(),
92            deletion_data: Vec::new(),
93            removal_data: Vec::new(),
94            is_tracking_insertion: T::Tracking::track_insertion(),
95            is_tracking_modification: T::Tracking::track_modification(),
96            is_tracking_deletion: T::Tracking::track_deletion(),
97            is_tracking_removal: T::Tracking::track_removal(),
98            on_insertion: None,
99            on_removal: None,
100            clone: None,
101        }
102    }
103    /// Returns a new [`SparseSet`] to be used in custom storage.
104    #[inline]
105    pub fn new_custom_storage() -> Self {
106        SparseSet::new()
107    }
108    /// Returns a slice of all the components in this storage.
109    #[inline]
110    pub fn as_slice(&self) -> &[T] {
111        &self.data
112    }
113}
114
115impl<T: Component> SparseSet<T> {
116    /// Returns `true` if `entity` owns a component in this storage.
117    #[inline]
118    pub fn contains(&self, entity: EntityId) -> bool {
119        self.index_of(entity).is_some()
120    }
121    /// Returns the length of the storage.
122    #[inline]
123    pub fn len(&self) -> usize {
124        self.dense.len()
125    }
126    /// Returns true if the storage's length is 0.
127    #[inline]
128    pub fn is_empty(&self) -> bool {
129        self.dense.is_empty()
130    }
131}
132
133impl<T: Component> SparseSet<T> {
134    /// Returns the index of `entity`'s component in the `dense` and `data` vectors.  
135    /// This index is only valid for this storage and until a modification happens.
136    #[inline]
137    pub fn index_of(&self, entity: EntityId) -> Option<usize> {
138        self.sparse.get(entity).and_then(|sparse_entity| {
139            if entity.gen() == sparse_entity.gen() {
140                Some(sparse_entity.uindex())
141            } else {
142                None
143            }
144        })
145    }
146    /// Returns the index of `entity`'s component in the `dense` and `data` vectors.  
147    /// This index is only valid for this storage and until a modification happens.
148    ///
149    /// # Safety
150    ///
151    /// `entity` has to own a component of this type.  
152    /// The index is only valid until a modification occurs in the storage.
153    #[inline]
154    pub unsafe fn index_of_unchecked(&self, entity: EntityId) -> usize {
155        self.sparse.get_unchecked(entity).uindex()
156    }
157    /// Returns the `EntityId` at a given `index`.
158    #[inline]
159    pub fn id_at(&self, index: usize) -> Option<EntityId> {
160        self.dense.get(index).copied()
161    }
162
163    /// Sets the on insertion callback.
164    pub fn on_insertion(&mut self, f: impl FnMut(EntityId, &T) + Send + Sync + 'static) {
165        self.on_insertion = Some(Box::new(f));
166    }
167
168    /// Remove the on insertion callback.
169    #[allow(clippy::type_complexity)]
170    pub fn take_on_insertion(
171        &mut self,
172    ) -> Option<Box<dyn FnMut(EntityId, &T) + Send + Sync + 'static>> {
173        self.on_insertion.take()
174    }
175
176    /// Sets the on removal and deletion callback.
177    pub fn on_removal(&mut self, f: impl FnMut(EntityId, &T) + Send + Sync + 'static) {
178        self.on_removal = Some(Box::new(f));
179    }
180
181    /// Remove the on removal and deletion callback.
182    #[allow(clippy::type_complexity)]
183    pub fn take_on_removal(
184        &mut self,
185    ) -> Option<Box<dyn FnMut(EntityId, &T) + Send + Sync + 'static>> {
186        self.on_removal.take()
187    }
188
189    #[inline]
190    pub(crate) fn private_get(&self, entity: EntityId) -> Option<&T> {
191        self.index_of(entity)
192            .map(|index| unsafe { self.data.get_unchecked(index) })
193    }
194}
195
196/// [`SparseSet::insert`]'s return value.
197#[must_use]
198pub enum InsertionResult<T> {
199    /// No component were present at this index.
200    Inserted,
201    /// The component was inserted.\
202    /// A component from the same entity was present.
203    ComponentOverride(T),
204    /// A component from an entity with a smaller generation was present.
205    OtherComponentOverride,
206    /// A component from an entity with a larger generation was present.
207    NotInserted,
208}
209
210impl<T> InsertionResult<T> {
211    pub(crate) fn was_inserted(&self) -> bool {
212        match self {
213            InsertionResult::Inserted
214            | InsertionResult::ComponentOverride(_)
215            | InsertionResult::OtherComponentOverride => true,
216            InsertionResult::NotInserted => false,
217        }
218    }
219
220    #[track_caller]
221    pub(crate) fn assert_inserted(&self) {
222        assert!(self.was_inserted());
223    }
224}
225
226impl<T: Component> SparseSet<T> {
227    /// Inserts `value` in the `SparseSet`.
228    ///
229    /// # Tracking
230    ///
231    /// In case `entity` had a component of this type, the new component will be considered `modified`.  
232    /// In all other cases it'll be considered `inserted`.
233    #[track_caller]
234    pub fn insert(
235        &mut self,
236        entity: EntityId,
237        value: T,
238        current: TrackingTimestamp,
239    ) -> InsertionResult<T> {
240        self.sparse.allocate_at(entity);
241
242        // at this point there can't be nothing at the sparse index
243        let sparse_entity = unsafe { self.sparse.get_mut_unchecked(entity) };
244
245        let old_component;
246
247        if sparse_entity.is_dead() {
248            if let Some(on_insertion) = &mut self.on_insertion {
249                on_insertion(entity, &value);
250            }
251
252            *sparse_entity =
253                EntityId::new_from_index_and_gen(self.dense.len() as u64, entity.gen());
254
255            if self.is_tracking_insertion {
256                self.insertion_data.push(current);
257            }
258            if self.is_tracking_modification {
259                self.modification_data.push(TrackingTimestamp::origin());
260            }
261
262            self.dense.push(entity);
263            self.data.push(value);
264
265            old_component = InsertionResult::Inserted;
266        } else if entity.gen() == sparse_entity.gen() {
267            if let Some(on_insertion) = &mut self.on_insertion {
268                on_insertion(entity, &value);
269            }
270
271            let old_data = unsafe {
272                core::mem::replace(self.data.get_unchecked_mut(sparse_entity.uindex()), value)
273            };
274
275            old_component = InsertionResult::ComponentOverride(old_data);
276
277            sparse_entity.copy_gen(entity);
278
279            let dense_entity = unsafe { self.dense.get_unchecked_mut(sparse_entity.uindex()) };
280
281            if self.is_tracking_modification {
282                unsafe {
283                    *self
284                        .modification_data
285                        .get_unchecked_mut(sparse_entity.uindex()) = current;
286                }
287            }
288
289            dense_entity.copy_index_gen(entity);
290        } else if entity.gen() > sparse_entity.gen() {
291            if let Some(on_insertion) = &mut self.on_insertion {
292                on_insertion(entity, &value);
293            }
294
295            let _ = unsafe {
296                core::mem::replace(self.data.get_unchecked_mut(sparse_entity.uindex()), value)
297            };
298
299            old_component = InsertionResult::OtherComponentOverride;
300
301            sparse_entity.copy_gen(entity);
302
303            let dense_entity = unsafe { self.dense.get_unchecked_mut(sparse_entity.uindex()) };
304
305            if self.is_tracking_insertion {
306                unsafe {
307                    *self
308                        .insertion_data
309                        .get_unchecked_mut(sparse_entity.uindex()) = current;
310                }
311            }
312
313            dense_entity.copy_index_gen(entity);
314        } else {
315            old_component = InsertionResult::NotInserted;
316        }
317
318        old_component
319    }
320}
321
322impl<T: Component> SparseSet<T> {
323    /// Same as `delete` but checks tracking at runtime.
324    #[inline]
325    pub(crate) fn dyn_delete(&mut self, entity: EntityId, current: TrackingTimestamp) -> bool {
326        if let Some(component) = self.actual_remove(entity) {
327            if self.is_tracking_deletion() {
328                self.deletion_data.push((entity, current, component));
329            }
330
331            true
332        } else {
333            false
334        }
335    }
336
337    /// Same as `remove` but checks tracking at runtime.
338    #[inline]
339    pub(crate) fn dyn_remove(&mut self, entity: EntityId, current: TrackingTimestamp) -> Option<T> {
340        let component = self.actual_remove(entity);
341
342        if component.is_some() && self.is_tracking_removal() {
343            self.removal_data.push((entity, current));
344        }
345
346        component
347    }
348
349    #[inline]
350    pub(crate) fn actual_remove(&mut self, entity: EntityId) -> Option<T> {
351        let sparse_entity = self.sparse.get(entity)?;
352
353        if entity.gen() >= sparse_entity.gen() {
354            unsafe {
355                *self.sparse.get_mut_unchecked(entity) = EntityId::dead();
356            }
357
358            self.dense.swap_remove(sparse_entity.uindex());
359            if self.is_tracking_insertion() {
360                self.insertion_data.swap_remove(sparse_entity.uindex());
361            }
362            if self.is_tracking_modification() {
363                self.modification_data.swap_remove(sparse_entity.uindex());
364            }
365            let component = self.data.swap_remove(sparse_entity.uindex());
366
367            // The SparseSet could now be empty or the removed component could have been the last one
368            if sparse_entity.uindex() < self.dense.len() {
369                unsafe {
370                    let last = *self.dense.get_unchecked(sparse_entity.uindex());
371                    self.sparse
372                        .get_mut_unchecked(last)
373                        .copy_index(sparse_entity);
374                }
375            }
376
377            if entity.gen() == sparse_entity.gen() {
378                if let Some(on_remove) = &mut self.on_removal {
379                    on_remove(entity, &component);
380                }
381
382                Some(component)
383            } else {
384                None
385            }
386        } else {
387            None
388        }
389    }
390}
391
392impl<T: Component> SparseSet<T> {
393    /// Removes the *inserted* flag on all components of this storage.
394    pub(crate) fn private_clear_all_inserted(&mut self, current: TrackingTimestamp) {
395        self.last_insert = current;
396    }
397    /// Removes the *modified* flag on all components of this storage.
398    pub(crate) fn private_clear_all_modified(&mut self, current: TrackingTimestamp) {
399        self.last_modified = current;
400    }
401    /// Removes the *inserted* and *modified* flags on all components of this storage.
402    pub(crate) fn private_clear_all_inserted_and_modified(&mut self, current: TrackingTimestamp) {
403        self.last_insert = current;
404        self.last_modified = current;
405    }
406    /// Clear all deletion tracking data.
407    pub fn clear_all_deleted(&mut self) {
408        self.deletion_data.clear();
409    }
410    /// Clear all deletion tracking data older than some timestamp.
411    pub fn clear_all_deleted_older_than_timestamp(&mut self, timestamp: TrackingTimestamp) {
412        self.deletion_data
413            .retain(|(_, t, _)| timestamp.is_older_than(*t));
414    }
415    /// Clear all removal tracking data.
416    pub fn clear_all_removed(&mut self) {
417        self.removal_data.clear();
418    }
419    /// Clear all removal tracking data older than some timestamp.
420    pub fn clear_all_removed_older_than_timestamp(&mut self, timestamp: TrackingTimestamp) {
421        self.removal_data
422            .retain(|(_, t)| timestamp.is_older_than(*t));
423    }
424    /// Clear all deletion and removal tracking data.
425    pub fn clear_all_removed_and_deleted(&mut self) {
426        self.removal_data.clear();
427    }
428    /// Clear all deletion and removal tracking data older than some timestamp.
429    pub fn clear_all_removed_and_deleted_older_than_timestamp(
430        &mut self,
431        timestamp: TrackingTimestamp,
432    ) {
433        self.deletion_data
434            .retain(|(_, t, _)| timestamp.is_older_than(*t));
435        self.removal_data
436            .retain(|(_, t)| timestamp.is_older_than(*t));
437    }
438}
439
440impl<T: Component> SparseSet<T> {
441    /// Make this storage track insertions.
442    #[allow(clippy::manual_repeat_n, reason = "Too recent version")]
443    pub fn track_insertion(&mut self) -> &mut SparseSet<T> {
444        if self.is_tracking_insertion() {
445            return self;
446        }
447
448        self.is_tracking_insertion = true;
449
450        self.insertion_data
451            .extend(core::iter::repeat(TrackingTimestamp::new(0)).take(self.dense.len()));
452
453        self
454    }
455    /// Make this storage track modification.
456    #[allow(clippy::manual_repeat_n, reason = "Too recent version")]
457    pub fn track_modification(&mut self) -> &mut SparseSet<T> {
458        if self.is_tracking_modification() {
459            return self;
460        }
461
462        self.is_tracking_modification = true;
463
464        self.modification_data
465            .extend(core::iter::repeat(TrackingTimestamp::new(0)).take(self.dense.len()));
466
467        self
468    }
469    /// Make this storage track deletions.
470    pub fn track_deletion(&mut self) -> &mut SparseSet<T> {
471        self.is_tracking_deletion = true;
472        self
473    }
474    /// Make this storage track removals.
475    pub fn track_removal(&mut self) -> &mut SparseSet<T> {
476        self.is_tracking_removal = true;
477        self
478    }
479    /// Make this storage track insertions, modifications, deletions and removals.
480    pub fn track_all(&mut self) {
481        self.track_insertion()
482            .track_modification()
483            .track_deletion()
484            .track_removal();
485    }
486    /// Returns `true` if the storage tracks insertion.
487    pub fn is_tracking_insertion(&self) -> bool {
488        self.is_tracking_insertion
489    }
490    /// Returns `true` if the storage tracks modification.
491    pub fn is_tracking_modification(&self) -> bool {
492        self.is_tracking_modification
493    }
494    /// Returns `true` if the storage tracks deletion.
495    pub fn is_tracking_deletion(&self) -> bool {
496        self.is_tracking_deletion
497    }
498    /// Returns `true` if the storage tracks removal.
499    pub fn is_tracking_removal(&self) -> bool {
500        self.is_tracking_removal
501    }
502    /// Returns `true` if the storage tracks insertion, deletion or removal.
503    pub fn is_tracking_any(&self) -> bool {
504        self.is_tracking_insertion()
505            || self.is_tracking_modification()
506            || self.is_tracking_deletion()
507            || self.is_tracking_removal()
508    }
509    pub(crate) fn check_tracking<Track: Tracking>(&self) -> Result<(), error::GetStorage> {
510        if (Track::track_insertion() && !self.is_tracking_insertion())
511            || (Track::track_modification() && !self.is_tracking_modification())
512            || (Track::track_deletion() && !self.is_tracking_deletion())
513            || (Track::track_removal() && !self.is_tracking_removal())
514        {
515            return Err(error::GetStorage::TrackingNotEnabled {
516                name: Some(type_name::<SparseSet<T>>()),
517                id: StorageId::of::<SparseSet<T>>(),
518                tracking: Track::name(),
519            });
520        }
521
522        Ok(())
523    }
524    pub(crate) fn enable_tracking<Track: Tracking>(&mut self) {
525        if Track::track_insertion() {
526            self.track_insertion();
527        }
528        if Track::track_modification() {
529            self.track_modification();
530        }
531        if Track::track_deletion() {
532            self.track_deletion();
533        }
534        if Track::track_removal() {
535            self.track_removal();
536        }
537    }
538}
539
540impl<T: Component> SparseSet<T> {
541    /// Reserves memory for at least `additional` components. Adding components can still allocate though.
542    #[inline]
543    pub fn reserve(&mut self, additional: usize) {
544        self.dense.reserve(additional);
545        self.data.reserve(additional);
546    }
547    /// Sorts the `SparseSet` with a comparator function, but may not preserve the order of equal elements.
548    pub fn sort_unstable_by<F: FnMut(&T, &T) -> Ordering>(&mut self, mut compare: F) {
549        let mut transform: Vec<usize> = (0..self.dense.len()).collect();
550
551        transform.sort_unstable_by(|&i, &j| {
552            // SAFE dense and data have the same length
553            compare(unsafe { self.data.get_unchecked(i) }, unsafe {
554                self.data.get_unchecked(j)
555            })
556        });
557
558        let mut pos;
559        for i in 0..transform.len() {
560            // SAFE we're in bound
561            pos = unsafe { *transform.get_unchecked(i) };
562            while pos < i {
563                // SAFE we're in bound
564                pos = unsafe { *transform.get_unchecked(pos) };
565            }
566            self.dense.swap(i, pos);
567            self.data.swap(i, pos);
568        }
569
570        for (i, id) in self.dense.iter().enumerate() {
571            unsafe {
572                self.sparse.get_mut_unchecked(*id).set_index(i as u64);
573            }
574        }
575    }
576
577    /// Applies the given function `f` to the entities `a` and `b`.\
578    /// The two entities shouldn't point to the same component.  
579    ///
580    /// ### Panics
581    ///
582    /// - MissingComponent - if one of the entity doesn't have any component in the storage.
583    /// - IdenticalIds - if the two entities point to the same component.
584    #[track_caller]
585    pub(crate) fn private_apply<R, F: FnOnce(&mut T, &T) -> R>(
586        &mut self,
587        a: EntityId,
588        b: EntityId,
589        f: F,
590        current: TrackingTimestamp,
591    ) -> R {
592        let a_index = self.index_of(a).unwrap_or_else(move || {
593            panic!(
594                "Entity {:?} does not have any component in this storage.",
595                a
596            )
597        });
598        let b_index = self.index_of(b).unwrap_or_else(move || {
599            panic!(
600                "Entity {:?} does not have any component in this storage.",
601                b
602            )
603        });
604
605        if a_index != b_index {
606            if self.is_tracking_modification {
607                self.modification_data[a_index] = current;
608            }
609
610            let a = unsafe { &mut *self.data.as_mut_ptr().add(a_index) };
611            let b = unsafe { &*self.data.as_mut_ptr().add(b_index) };
612
613            f(a, b)
614        } else {
615            panic!("Cannot use apply with identical components.");
616        }
617    }
618
619    /// Applies the given function `f` to the entities `a` and `b`.\
620    /// The two entities shouldn't point to the same component.  
621    ///
622    /// ### Panics
623    ///
624    /// - MissingComponent - if one of the entity doesn't have any component in the storage.
625    /// - IdenticalIds - if the two entities point to the same component.
626    #[track_caller]
627    pub(crate) fn private_apply_mut<R, F: FnOnce(&mut T, &mut T) -> R>(
628        &mut self,
629        a: EntityId,
630        b: EntityId,
631        f: F,
632        current: TrackingTimestamp,
633    ) -> R {
634        let a_index = self.index_of(a).unwrap_or_else(move || {
635            panic!(
636                "Entity {:?} does not have any component in this storage.",
637                a
638            )
639        });
640        let b_index = self.index_of(b).unwrap_or_else(move || {
641            panic!(
642                "Entity {:?} does not have any component in this storage.",
643                b
644            )
645        });
646
647        if a_index != b_index {
648            if self.is_tracking_modification {
649                self.modification_data[a_index] = current;
650                self.modification_data[b_index] = current;
651            }
652
653            let a = unsafe { &mut *self.data.as_mut_ptr().add(a_index) };
654            let b = unsafe { &mut *self.data.as_mut_ptr().add(b_index) };
655
656            f(a, b)
657        } else {
658            panic!("Cannot use apply with identical components.");
659        }
660    }
661
662    /// Deletes all components in this storage.
663    pub(crate) fn private_clear(&mut self, current: TrackingTimestamp) {
664        for &id in &self.dense {
665            unsafe {
666                *self.sparse.get_mut_unchecked(id) = EntityId::dead();
667            }
668        }
669
670        self.insertion_data.clear();
671        self.modification_data.clear();
672
673        let is_tracking_deletion = self.is_tracking_deletion();
674
675        let dense = self.dense.drain(..);
676        let data = self.data.drain(..);
677
678        if is_tracking_deletion {
679            let iter = dense
680                .zip(data)
681                .map(|(entity, component)| (entity, current, component));
682            self.deletion_data.extend(iter);
683        }
684    }
685
686    /// Creates a draining iterator that empties the storage and yields the removed items.
687    pub(crate) fn private_drain(&mut self, current: TrackingTimestamp) -> SparseSetDrain<'_, T> {
688        if self.is_tracking_removal {
689            self.removal_data
690                .extend(self.dense.iter().map(|&entity| (entity, current)));
691        }
692
693        for id in &self.dense {
694            // SAFE ids from sparse_set.dense are always valid
695            unsafe {
696                *self.sparse.get_mut_unchecked(*id) = EntityId::dead();
697            }
698        }
699
700        self.insertion_data.clear();
701        self.modification_data.clear();
702
703        let dense_ptr = self.dense.as_ptr();
704        let dense_len = self.dense.len();
705
706        unsafe {
707            self.dense.set_len(0);
708        }
709
710        SparseSetDrain {
711            dense_ptr,
712            dense_len,
713            data: self.data.drain(..),
714        }
715    }
716
717    pub(crate) fn private_retain<F: FnMut(EntityId, &T) -> bool>(
718        &mut self,
719        current: TrackingTimestamp,
720        mut f: F,
721    ) {
722        let mut removed = 0;
723        for i in 0..self.len() {
724            let i = i - removed;
725
726            let eid = unsafe { *self.dense.get_unchecked(i) };
727            let component = unsafe { self.data.get_unchecked(i) };
728
729            if !f(eid, component) {
730                self.dyn_delete(eid, current);
731                removed += 1;
732            }
733        }
734    }
735
736    pub(crate) fn private_retain_mut<F: FnMut(EntityId, Mut<'_, T>) -> bool>(
737        &mut self,
738        current: TrackingTimestamp,
739        mut f: F,
740    ) {
741        let mut removed = 0;
742        for i in 0..self.len() {
743            let i = i - removed;
744
745            let eid = unsafe { *self.dense.get_unchecked(i) };
746            let component = Mut {
747                flag: self.modification_data.get_mut(i),
748                current,
749                data: unsafe { self.data.get_unchecked_mut(i) },
750            };
751
752            if !f(eid, component) {
753                self.dyn_delete(eid, current);
754                removed += 1;
755            }
756        }
757    }
758}
759
760impl<T: Ord + Component> SparseSet<T> {
761    /// Sorts the `SparseSet`, but may not preserve the order of equal elements.
762    pub fn sort_unstable(&mut self) {
763        self.sort_unstable_by(Ord::cmp)
764    }
765}
766
767impl<T: Clone + Component> SparseSet<T> {
768    /// Registers the function to clone this component.
769    #[inline]
770    pub fn register_clone(&mut self) {
771        self.clone = Some(T::clone)
772    }
773}
774
775impl<T: Component + Send + Sync> Storage for SparseSet<T> {
776    #[inline]
777    fn delete(&mut self, entity: EntityId, current: TrackingTimestamp) {
778        self.dyn_delete(entity, current);
779    }
780    #[inline]
781    fn clear(&mut self, current: TrackingTimestamp) {
782        self.private_clear(current);
783    }
784    fn sparse_array(&self) -> Option<&SparseArray<EntityId, BUCKET_SIZE>> {
785        Some(&self.sparse)
786    }
787    fn memory_usage(&self) -> Option<StorageMemoryUsage> {
788        Some(self.private_memory_usage())
789    }
790    fn is_empty(&self) -> bool {
791        self.is_empty()
792    }
793    fn clear_all_inserted(&mut self, current: TrackingTimestamp) {
794        self.last_insert = current;
795    }
796    fn clear_all_modified(&mut self, current: TrackingTimestamp) {
797        self.last_modified = current;
798    }
799    fn clear_all_removed_and_deleted(&mut self) {
800        self.deletion_data.clear();
801        self.removal_data.clear();
802    }
803    fn clear_all_removed_and_deleted_older_than_timestamp(&mut self, timestamp: TrackingTimestamp) {
804        self.deletion_data
805            .retain(|(_, t, _)| timestamp.is_older_than(*t));
806
807        self.removal_data
808            .retain(|(_, t)| timestamp.is_older_than(*t));
809    }
810    #[inline]
811    fn move_component_from(
812        &mut self,
813        other_all_storages: &mut AllStorages,
814        from: EntityId,
815        to: EntityId,
816        current: TrackingTimestamp,
817        other_current: TrackingTimestamp,
818    ) {
819        if let Some(component) = self.dyn_remove(from, current) {
820            let other_sparse_set = other_all_storages.exclusive_storage_or_insert_mut(
821                StorageId::of::<SparseSet<T>>(),
822                SparseSet::<T>::new,
823            );
824
825            let _ = other_sparse_set.insert(to, component, other_current);
826        }
827    }
828
829    fn try_clone(&self, other_current: TrackingTimestamp) -> Option<SBoxBuilder> {
830        self.clone.map(|clone| {
831            let mut sparse_set = SparseSet::<T>::new();
832
833            sparse_set.sparse = self.sparse.clone();
834            sparse_set.dense = self.dense.clone();
835            sparse_set.data = self.data.iter().map(clone).collect();
836
837            if sparse_set.is_tracking_insertion {
838                sparse_set
839                    .insertion_data
840                    .resize(self.dense.len(), other_current);
841            }
842            if sparse_set.is_tracking_modification {
843                sparse_set
844                    .modification_data
845                    .resize(self.dense.len(), TrackingTimestamp::origin());
846            }
847
848            SBoxBuilder::new(sparse_set)
849        })
850    }
851
852    fn clone_component_to(
853        &self,
854        other_all_storages: &mut AllStorages,
855        from: EntityId,
856        to: EntityId,
857        other_current: TrackingTimestamp,
858    ) {
859        if let Some(clone) = &self.clone {
860            if let Some(component) = self.private_get(from) {
861                let other_sparse_set = other_all_storages.exclusive_storage_or_insert_mut(
862                    StorageId::of::<SparseSet<T>>(),
863                    SparseSet::<T>::new,
864                );
865
866                let _ = other_sparse_set.insert(to, (clone)(component), other_current);
867            }
868        }
869    }
870}
871
872#[cfg(test)]
873mod tests {
874    use super::*;
875    use crate::Component;
876    use std::println;
877
878    #[derive(PartialEq, Eq, Debug)]
879    struct STR(&'static str);
880
881    impl Component for STR {
882        type Tracking = crate::track::Untracked;
883    }
884
885    #[derive(PartialEq, Eq, PartialOrd, Ord, Debug)]
886    struct I32(i32);
887
888    impl Component for I32 {
889        type Tracking = crate::track::Untracked;
890    }
891
892    #[test]
893    fn insert() {
894        let mut array = SparseSet::new();
895
896        array
897            .insert(
898                EntityId::new_from_parts(0, 0),
899                STR("0"),
900                TrackingTimestamp::new(0),
901            )
902            .assert_inserted();
903        assert_eq!(array.dense, &[EntityId::new_from_parts(0, 0)]);
904        assert_eq!(array.data, &[STR("0")]);
905        assert_eq!(
906            array.private_get(EntityId::new_from_parts(0, 0)),
907            Some(&STR("0"))
908        );
909
910        array
911            .insert(
912                EntityId::new_from_parts(1, 0),
913                STR("1"),
914                TrackingTimestamp::new(0),
915            )
916            .assert_inserted();
917        assert_eq!(
918            array.dense,
919            &[
920                EntityId::new_from_parts(0, 0),
921                EntityId::new_from_parts(1, 0)
922            ]
923        );
924        assert_eq!(array.data, &[STR("0"), STR("1")]);
925        assert_eq!(
926            array.private_get(EntityId::new_from_parts(0, 0)),
927            Some(&STR("0"))
928        );
929        assert_eq!(
930            array.private_get(EntityId::new_from_parts(1, 0)),
931            Some(&STR("1"))
932        );
933
934        array
935            .insert(
936                EntityId::new_from_parts(5, 0),
937                STR("5"),
938                TrackingTimestamp::new(0),
939            )
940            .assert_inserted();
941        assert_eq!(
942            array.dense,
943            &[
944                EntityId::new_from_parts(0, 0),
945                EntityId::new_from_parts(1, 0),
946                EntityId::new_from_parts(5, 0)
947            ]
948        );
949        assert_eq!(array.data, &[STR("0"), STR("1"), STR("5")]);
950        assert_eq!(
951            array.private_get(EntityId::new_from_parts(5, 0)),
952            Some(&STR("5"))
953        );
954
955        assert_eq!(array.private_get(EntityId::new_from_parts(4, 0)), None);
956    }
957
958    #[test]
959    fn remove() {
960        let mut array = SparseSet::new();
961        array
962            .insert(
963                EntityId::new_from_parts(0, 0),
964                STR("0"),
965                TrackingTimestamp::new(0),
966            )
967            .assert_inserted();
968        array
969            .insert(
970                EntityId::new_from_parts(5, 0),
971                STR("5"),
972                TrackingTimestamp::new(0),
973            )
974            .assert_inserted();
975        array
976            .insert(
977                EntityId::new_from_parts(10, 0),
978                STR("10"),
979                TrackingTimestamp::new(0),
980            )
981            .assert_inserted();
982
983        assert_eq!(
984            array.dyn_remove(EntityId::new_from_parts(0, 0), TrackingTimestamp::new(0)),
985            Some(STR("0")),
986        );
987        assert_eq!(
988            array.dense,
989            &[
990                EntityId::new_from_parts(10, 0),
991                EntityId::new_from_parts(5, 0)
992            ]
993        );
994        assert_eq!(array.data, &[STR("10"), STR("5")]);
995        assert_eq!(array.private_get(EntityId::new_from_parts(0, 0)), None);
996        assert_eq!(
997            array.private_get(EntityId::new_from_parts(5, 0)),
998            Some(&STR("5"))
999        );
1000        assert_eq!(
1001            array.private_get(EntityId::new_from_parts(10, 0)),
1002            Some(&STR("10"))
1003        );
1004
1005        array
1006            .insert(
1007                EntityId::new_from_parts(3, 0),
1008                STR("3"),
1009                TrackingTimestamp::new(0),
1010            )
1011            .assert_inserted();
1012        array
1013            .insert(
1014                EntityId::new_from_parts(100, 0),
1015                STR("100"),
1016                TrackingTimestamp::new(0),
1017            )
1018            .assert_inserted();
1019        assert_eq!(
1020            array.dense,
1021            &[
1022                EntityId::new_from_parts(10, 0),
1023                EntityId::new_from_parts(5, 0),
1024                EntityId::new_from_parts(3, 0),
1025                EntityId::new_from_parts(100, 0)
1026            ]
1027        );
1028        assert_eq!(array.data, &[STR("10"), STR("5"), STR("3"), STR("100")]);
1029        assert_eq!(array.private_get(EntityId::new_from_parts(0, 0)), None);
1030        assert_eq!(
1031            array.private_get(EntityId::new_from_parts(3, 0)),
1032            Some(&STR("3"))
1033        );
1034        assert_eq!(
1035            array.private_get(EntityId::new_from_parts(5, 0)),
1036            Some(&STR("5"))
1037        );
1038        assert_eq!(
1039            array.private_get(EntityId::new_from_parts(10, 0)),
1040            Some(&STR("10"))
1041        );
1042        assert_eq!(
1043            array.private_get(EntityId::new_from_parts(100, 0)),
1044            Some(&STR("100"))
1045        );
1046
1047        assert_eq!(
1048            array.dyn_remove(EntityId::new_from_parts(3, 0), TrackingTimestamp::new(0)),
1049            Some(STR("3")),
1050        );
1051        assert_eq!(
1052            array.dense,
1053            &[
1054                EntityId::new_from_parts(10, 0),
1055                EntityId::new_from_parts(5, 0),
1056                EntityId::new_from_parts(100, 0)
1057            ]
1058        );
1059        assert_eq!(array.data, &[STR("10"), STR("5"), STR("100")]);
1060        assert_eq!(array.private_get(EntityId::new_from_parts(0, 0)), None);
1061        assert_eq!(array.private_get(EntityId::new_from_parts(3, 0)), None);
1062        assert_eq!(
1063            array.private_get(EntityId::new_from_parts(5, 0)),
1064            Some(&STR("5"))
1065        );
1066        assert_eq!(
1067            array.private_get(EntityId::new_from_parts(10, 0)),
1068            Some(&STR("10"))
1069        );
1070        assert_eq!(
1071            array.private_get(EntityId::new_from_parts(100, 0)),
1072            Some(&STR("100"))
1073        );
1074
1075        assert_eq!(
1076            array.dyn_remove(EntityId::new_from_parts(100, 0), TrackingTimestamp::new(0)),
1077            Some(STR("100"))
1078        );
1079        assert_eq!(
1080            array.dense,
1081            &[
1082                EntityId::new_from_parts(10, 0),
1083                EntityId::new_from_parts(5, 0)
1084            ]
1085        );
1086        assert_eq!(array.data, &[STR("10"), STR("5")]);
1087        assert_eq!(array.private_get(EntityId::new_from_parts(0, 0)), None);
1088        assert_eq!(array.private_get(EntityId::new_from_parts(3, 0)), None);
1089        assert_eq!(
1090            array.private_get(EntityId::new_from_parts(5, 0)),
1091            Some(&STR("5"))
1092        );
1093        assert_eq!(
1094            array.private_get(EntityId::new_from_parts(10, 0)),
1095            Some(&STR("10"))
1096        );
1097        assert_eq!(array.private_get(EntityId::new_from_parts(100, 0)), None);
1098    }
1099
1100    #[test]
1101    fn clear() {
1102        let mut sparse_set = SparseSet::new();
1103        sparse_set.track_all();
1104
1105        sparse_set
1106            .insert(EntityId::new(0), I32(0), TrackingTimestamp::new(0))
1107            .assert_inserted();
1108        sparse_set
1109            .insert(EntityId::new(1), I32(1), TrackingTimestamp::new(0))
1110            .assert_inserted();
1111
1112        sparse_set.private_clear(TrackingTimestamp::new(0));
1113
1114        assert_eq!(sparse_set.len(), 0);
1115        assert_eq!(sparse_set.private_get(EntityId::new(0)), None);
1116        assert_eq!(sparse_set.private_get(EntityId::new(1)), None);
1117        assert_eq!(sparse_set.insertion_data.len(), 0);
1118        assert_eq!(sparse_set.modification_data.len(), 0);
1119        assert_eq!(sparse_set.deletion_data.len(), 2);
1120        assert_eq!(sparse_set.removal_data.len(), 0);
1121    }
1122
1123    #[test]
1124    fn drain() {
1125        let mut sparse_set = SparseSet::new();
1126        sparse_set.track_all();
1127
1128        sparse_set
1129            .insert(EntityId::new(0), I32(0), TrackingTimestamp::new(0))
1130            .assert_inserted();
1131        sparse_set
1132            .insert(EntityId::new(1), I32(1), TrackingTimestamp::new(0))
1133            .assert_inserted();
1134
1135        let mut drain = sparse_set.private_drain(TrackingTimestamp::new(0));
1136
1137        assert_eq!(drain.next(), Some(I32(0)));
1138        assert_eq!(drain.next(), Some(I32(1)));
1139        assert_eq!(drain.next(), None);
1140
1141        drop(drain);
1142
1143        assert_eq!(sparse_set.len(), 0);
1144        assert_eq!(sparse_set.private_get(EntityId::new(0)), None);
1145        assert_eq!(sparse_set.private_get(EntityId::new(1)), None);
1146        assert_eq!(sparse_set.insertion_data.len(), 0);
1147        assert_eq!(sparse_set.modification_data.len(), 0);
1148        assert_eq!(sparse_set.deletion_data.len(), 0);
1149        assert_eq!(sparse_set.removal_data.len(), 2);
1150    }
1151
1152    #[test]
1153    fn drain_with_id() {
1154        let mut sparse_set = SparseSet::new();
1155
1156        sparse_set
1157            .insert(EntityId::new(0), I32(0), TrackingTimestamp::new(0))
1158            .assert_inserted();
1159        sparse_set
1160            .insert(EntityId::new(1), I32(1), TrackingTimestamp::new(0))
1161            .assert_inserted();
1162
1163        let mut drain = sparse_set
1164            .private_drain(TrackingTimestamp::new(0))
1165            .with_id();
1166
1167        assert_eq!(drain.next(), Some((EntityId::new(0), I32(0))));
1168        assert_eq!(drain.next(), Some((EntityId::new(1), I32(1))));
1169        assert_eq!(drain.next(), None);
1170
1171        drop(drain);
1172
1173        assert_eq!(sparse_set.len(), 0);
1174        assert_eq!(sparse_set.private_get(EntityId::new(0)), None);
1175    }
1176
1177    #[test]
1178    fn drain_empty() {
1179        let mut sparse_set = SparseSet::<I32>::new();
1180
1181        assert_eq!(
1182            sparse_set.private_drain(TrackingTimestamp::new(0)).next(),
1183            None
1184        );
1185        assert_eq!(
1186            sparse_set
1187                .private_drain(TrackingTimestamp::new(0))
1188                .with_id()
1189                .next(),
1190            None
1191        );
1192
1193        assert_eq!(sparse_set.len(), 0);
1194    }
1195
1196    #[test]
1197    fn unstable_sort() {
1198        let mut array = SparseSet::new();
1199
1200        for i in (0..100).rev() {
1201            let mut entity_id = EntityId::zero();
1202            entity_id.set_index(100 - i);
1203            array
1204                .insert(entity_id, I32(i as i32), TrackingTimestamp::new(0))
1205                .assert_inserted();
1206        }
1207
1208        array.sort_unstable();
1209
1210        for window in array.data.windows(2) {
1211            assert!(window[0] < window[1]);
1212        }
1213        for i in 0..100 {
1214            let mut entity_id = EntityId::zero();
1215            entity_id.set_index(100 - i);
1216            assert_eq!(array.private_get(entity_id), Some(&I32(i as i32)));
1217        }
1218    }
1219
1220    #[test]
1221    fn partially_sorted_unstable_sort() {
1222        let mut array = SparseSet::new();
1223
1224        for i in 0..20 {
1225            let mut entity_id = EntityId::zero();
1226            entity_id.set_index(i);
1227            array
1228                .insert(entity_id, I32(i as i32), TrackingTimestamp::new(0))
1229                .assert_inserted();
1230        }
1231        for i in (20..100).rev() {
1232            let mut entity_id = EntityId::zero();
1233            entity_id.set_index(100 - i + 20);
1234            array
1235                .insert(entity_id, I32(i as i32), TrackingTimestamp::new(0))
1236                .assert_inserted();
1237        }
1238
1239        array.sort_unstable();
1240
1241        for window in array.data.windows(2) {
1242            assert!(window[0] < window[1]);
1243        }
1244        for i in 0..20 {
1245            let mut entity_id = EntityId::zero();
1246            entity_id.set_index(i);
1247            assert_eq!(array.private_get(entity_id), Some(&I32(i as i32)));
1248        }
1249        for i in 20..100 {
1250            let mut entity_id = EntityId::zero();
1251            entity_id.set_index(100 - i + 20);
1252            assert_eq!(array.private_get(entity_id), Some(&I32(i as i32)));
1253        }
1254    }
1255
1256    #[test]
1257    fn debug() {
1258        let mut sparse_set = SparseSet::new();
1259
1260        sparse_set
1261            .insert(EntityId::new(0), STR("0"), TrackingTimestamp::new(0))
1262            .assert_inserted();
1263        sparse_set
1264            .insert(EntityId::new(5), STR("5"), TrackingTimestamp::new(0))
1265            .assert_inserted();
1266        sparse_set
1267            .insert(EntityId::new(10), STR("10"), TrackingTimestamp::new(0))
1268            .assert_inserted();
1269
1270        println!("{:#?}", sparse_set);
1271    }
1272
1273    #[test]
1274    fn multiple_enable_tracking() {
1275        let mut sparse_set = SparseSet::new();
1276
1277        sparse_set
1278            .insert(
1279                EntityId::new_from_parts(0, 0),
1280                I32(0),
1281                TrackingTimestamp::new(0),
1282            )
1283            .assert_inserted();
1284
1285        sparse_set.track_all();
1286        sparse_set.track_all();
1287        sparse_set.track_all();
1288
1289        assert_eq!(sparse_set.insertion_data.len(), 1);
1290        assert_eq!(sparse_set.modification_data.len(), 1);
1291    }
1292}
shipyard/sparse_set/mod.rs

shipyard/sparse_set/
mod.rs
