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#[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 #[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 #[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 #[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 #[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 #[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 pub fn clear(&mut self) {
103 self.values.clear();
104 }
105
106 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#[derive(Debug)]
119pub struct ComponentSparseSet {
120 dense: Column,
121 #[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 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 pub(crate) fn clear(&mut self) {
144 self.dense.clear();
145 self.entities.clear();
146 self.sparse.clear();
147 }
148
149 #[inline]
151 pub fn len(&self) -> usize {
152 self.dense.len()
153 }
154
155 #[inline]
157 pub fn is_empty(&self) -> bool {
158 self.dense.len() == 0
159 }
160
161 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 #[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 #[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 unsafe { self.dense.get_data_unchecked(dense_index) }
218 })
219 }
220
221 #[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 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 #[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 unsafe { Some(self.dense.get_added_tick_unchecked(dense_index)) }
251 }
252
253 #[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 unsafe { Some(self.dense.get_changed_tick_unchecked(dense_index)) }
263 }
264
265 #[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 unsafe { Some(self.dense.get_ticks_unchecked(dense_index)) }
275 }
276
277 #[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 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 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 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#[derive(Debug)]
336pub struct SparseSet<I, V: 'static> {
337 dense: Vec<V>,
338 indices: Vec<I>,
339 sparse: SparseArray<I, NonMaxUsize>,
340}
341
342#[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 #[inline]
356 pub fn len(&self) -> usize {
357 self.dense.len()
358 }
359
360 #[inline]
362 pub fn contains(&self, index: I) -> bool {
363 self.sparse.contains(index)
364 }
365
366 pub fn get(&self, index: I) -> Option<&V> {
370 self.sparse.get(index).map(|dense_index| {
371 unsafe { self.dense.get_unchecked(dense_index.get()) }
373 })
374 }
375
376 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 unsafe { dense.get_unchecked_mut(dense_index.get()) }
384 })
385 }
386
387 pub fn indices(&self) -> impl Iterator<Item = I> + '_ {
389 self.indices.iter().cloned()
390 }
391
392 pub fn values(&self) -> impl Iterator<Item = &V> {
394 self.dense.iter()
395 }
396
397 pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
399 self.dense.iter_mut()
400 }
401
402 pub fn iter(&self) -> impl Iterator<Item = (&I, &V)> {
404 self.indices.iter().zip(self.dense.iter())
405 }
406
407 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 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 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 #[inline]
447 pub fn capacity(&self) -> usize {
448 self.dense.capacity()
449 }
450
451 pub fn insert(&mut self, index: I, value: V) {
455 if let Some(dense_index) = self.sparse.get(index.clone()).cloned() {
456 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 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 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 unsafe { self.dense.get_unchecked_mut(dense_index) }
483 }
484 }
485
486 #[inline]
488 pub fn is_empty(&self) -> bool {
489 self.dense.len() == 0
490 }
491
492 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 pub fn clear(&mut self) {
511 self.dense.clear();
512 self.indices.clear();
513 self.sparse.clear();
514 }
515
516 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
526pub trait SparseSetIndex: Clone + PartialEq + Eq + Hash {
532 fn sparse_set_index(&self) -> usize;
534 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#[derive(Default)]
560pub struct SparseSets {
561 sets: SparseSet<ComponentId, ComponentSparseSet>,
562}
563
564impl SparseSets {
565 #[inline]
567 pub fn len(&self) -> usize {
568 self.sets.len()
569 }
570
571 #[inline]
573 pub fn is_empty(&self) -> bool {
574 self.sets.is_empty()
575 }
576
577 pub fn iter(&self) -> impl Iterator<Item = (ComponentId, &ComponentSparseSet)> {
580 self.sets.iter().map(|(id, data)| (*id, data))
581 }
582
583 #[inline]
585 pub fn get(&self, component_id: ComponentId) -> Option<&ComponentSparseSet> {
586 self.sets.get(component_id)
587 }
588
589 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 pub(crate) fn get_mut(&mut self, component_id: ComponentId) -> Option<&mut ComponentSparseSet> {
607 self.sets.get_mut(component_id)
608 }
609
610 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 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}