bevy_ecs/storage/
table.rs

1use crate::{
2    component::{ComponentId, ComponentInfo, ComponentTicks, Components, Tick, TickCells},
3    entity::Entity,
4    query::DebugCheckedUnwrap,
5    storage::{blob_vec::BlobVec, ImmutableSparseSet, SparseSet},
6};
7use bevy_ptr::{OwningPtr, Ptr, PtrMut, UnsafeCellDeref};
8use bevy_utils::HashMap;
9use std::alloc::Layout;
10use std::{
11    cell::UnsafeCell,
12    ops::{Index, IndexMut},
13};
14
15/// An opaque unique ID for a [`Table`] within a [`World`].
16///
17/// Can be used with [`Tables::get`] to fetch the corresponding
18/// table.
19///
20/// Each [`Archetype`] always points to a table via [`Archetype::table_id`].
21/// Multiple archetypes can point to the same table so long as the components
22/// stored in the table are identical, but do not share the same sparse set
23/// components.
24///
25/// [`World`]: crate::world::World
26/// [`Archetype`]: crate::archetype::Archetype
27/// [`Archetype::table_id`]: crate::archetype::Archetype::table_id
28#[derive(Debug, Clone, Copy, PartialEq, Eq)]
29// SAFETY: Must be repr(transparent) due to the safety requirements on EntityLocation
30#[repr(transparent)]
31pub struct TableId(u32);
32
33impl TableId {
34    pub(crate) const INVALID: TableId = TableId(u32::MAX);
35
36    /// Creates a new [`TableId`].
37    ///
38    /// `index` *must* be retrieved from calling [`TableId::as_u32`] on a `TableId` you got
39    /// from a table of a given [`World`] or the created ID may be invalid.
40    ///
41    /// [`World`]: crate::world::World
42    #[inline]
43    pub const fn from_u32(index: u32) -> Self {
44        Self(index)
45    }
46
47    /// Creates a new [`TableId`].
48    ///
49    /// `index` *must* be retrieved from calling [`TableId::as_usize`] on a `TableId` you got
50    /// from a table of a given [`World`] or the created ID may be invalid.
51    ///
52    /// [`World`]: crate::world::World
53    ///
54    /// # Panics
55    ///
56    /// Will panic if the provided value does not fit within a [`u32`].
57    #[inline]
58    pub const fn from_usize(index: usize) -> Self {
59        debug_assert!(index as u32 as usize == index);
60        Self(index as u32)
61    }
62
63    /// Gets the underlying table index from the ID.
64    #[inline]
65    pub const fn as_u32(self) -> u32 {
66        self.0
67    }
68
69    /// Gets the underlying table index from the ID.
70    #[inline]
71    pub const fn as_usize(self) -> usize {
72        // usize is at least u32 in Bevy
73        self.0 as usize
74    }
75
76    /// The [`TableId`] of the [`Table`] without any components.
77    #[inline]
78    pub const fn empty() -> Self {
79        Self(0)
80    }
81}
82
83/// A opaque newtype for rows in [`Table`]s. Specifies a single row in a specific table.
84///
85/// Values of this type are retrievable from [`Archetype::entity_table_row`] and can be
86/// used alongside [`Archetype::table_id`] to fetch the exact table and row where an
87/// [`Entity`]'s
88///
89/// Values of this type are only valid so long as entities have not moved around.
90/// Adding and removing components from an entity, or despawning it will invalidate
91/// potentially any table row in the table the entity was previously stored in. Users
92/// should *always* fetch the appropriate row from the entity's [`Archetype`] before
93/// fetching the entity's components.
94///
95/// [`Archetype`]: crate::archetype::Archetype
96/// [`Archetype::entity_table_row`]: crate::archetype::Archetype::entity_table_row
97/// [`Archetype::table_id`]: crate::archetype::Archetype::table_id
98#[derive(Debug, Clone, Copy, PartialEq, Eq)]
99// SAFETY: Must be repr(transparent) due to the safety requirements on EntityLocation
100#[repr(transparent)]
101pub struct TableRow(u32);
102
103impl TableRow {
104    pub(crate) const INVALID: TableRow = TableRow(u32::MAX);
105
106    /// Creates a `TableRow`.
107    #[inline]
108    pub const fn from_u32(index: u32) -> Self {
109        Self(index)
110    }
111
112    /// Creates a `TableRow` from a [`usize`] index.
113    ///
114    /// # Panics
115    ///
116    /// Will panic if the provided value does not fit within a [`u32`].
117    #[inline]
118    pub const fn from_usize(index: usize) -> Self {
119        debug_assert!(index as u32 as usize == index);
120        Self(index as u32)
121    }
122
123    /// Gets the index of the row as a [`usize`].
124    #[inline]
125    pub const fn as_usize(self) -> usize {
126        // usize is at least u32 in Bevy
127        self.0 as usize
128    }
129
130    /// Gets the index of the row as a [`usize`].
131    #[inline]
132    pub const fn as_u32(self) -> u32 {
133        self.0
134    }
135}
136
137/// A type-erased contiguous container for data of a homogeneous type.
138///
139/// Conceptually, a [`Column`] is very similar to a type-erased `Vec<T>`.
140/// It also stores the change detection ticks for its components, kept in two separate
141/// contiguous buffers internally. An element shares its data across these buffers by using the
142/// same index (i.e. the entity at row 3 has its data at index 3 and its change detection ticks at
143/// index 3). A slice to these contiguous blocks of memory can be fetched
144/// via [`Column::get_data_slice`], [`Column::get_added_ticks_slice`], and
145/// [`Column::get_changed_ticks_slice`].
146///
147/// Like many other low-level storage types, [`Column`] has a limited and highly unsafe
148/// interface. It's highly advised to use higher level types and their safe abstractions
149/// instead of working directly with [`Column`].
150#[derive(Debug)]
151pub struct Column {
152    data: BlobVec,
153    added_ticks: Vec<UnsafeCell<Tick>>,
154    changed_ticks: Vec<UnsafeCell<Tick>>,
155}
156
157impl Column {
158    /// Constructs a new [`Column`], configured with a component's layout and an initial `capacity`.
159    #[inline]
160    pub(crate) fn with_capacity(component_info: &ComponentInfo, capacity: usize) -> Self {
161        Column {
162            // SAFETY: component_info.drop() is valid for the types that will be inserted.
163            data: unsafe { BlobVec::new(component_info.layout(), component_info.drop(), capacity) },
164            added_ticks: Vec::with_capacity(capacity),
165            changed_ticks: Vec::with_capacity(capacity),
166        }
167    }
168
169    /// Fetches the [`Layout`] for the underlying type.
170    #[inline]
171    pub fn item_layout(&self) -> Layout {
172        self.data.layout()
173    }
174
175    /// Writes component data to the column at given row.
176    /// Assumes the slot is uninitialized, drop is not called.
177    /// To overwrite existing initialized value, use `replace` instead.
178    ///
179    /// # Safety
180    /// Assumes data has already been allocated for the given row.
181    #[inline]
182    pub(crate) unsafe fn initialize(&mut self, row: TableRow, data: OwningPtr<'_>, tick: Tick) {
183        debug_assert!(row.as_usize() < self.len());
184        self.data.initialize_unchecked(row.as_usize(), data);
185        *self.added_ticks.get_unchecked_mut(row.as_usize()).get_mut() = tick;
186        *self
187            .changed_ticks
188            .get_unchecked_mut(row.as_usize())
189            .get_mut() = tick;
190    }
191
192    /// Writes component data to the column at given row.
193    /// Assumes the slot is initialized, calls drop.
194    ///
195    /// # Safety
196    /// Assumes data has already been allocated for the given row.
197    #[inline]
198    pub(crate) unsafe fn replace(&mut self, row: TableRow, data: OwningPtr<'_>, change_tick: Tick) {
199        debug_assert!(row.as_usize() < self.len());
200        self.data.replace_unchecked(row.as_usize(), data);
201        *self
202            .changed_ticks
203            .get_unchecked_mut(row.as_usize())
204            .get_mut() = change_tick;
205    }
206
207    /// Gets the current number of elements stored in the column.
208    #[inline]
209    pub fn len(&self) -> usize {
210        self.data.len()
211    }
212
213    /// Checks if the column is empty. Returns `true` if there are no elements, `false` otherwise.
214    #[inline]
215    pub fn is_empty(&self) -> bool {
216        self.data.is_empty()
217    }
218
219    /// Removes an element from the [`Column`].
220    ///
221    /// - The value will be dropped if it implements [`Drop`].
222    /// - This does not preserve ordering, but is O(1).
223    /// - This does not do any bounds checking.
224    /// - The element is replaced with the last element in the [`Column`].
225    ///
226    /// # Safety
227    /// `row` must be within the range `[0, self.len())`.
228    ///
229    #[inline]
230    pub(crate) unsafe fn swap_remove_unchecked(&mut self, row: TableRow) {
231        self.data.swap_remove_and_drop_unchecked(row.as_usize());
232        self.added_ticks.swap_remove(row.as_usize());
233        self.changed_ticks.swap_remove(row.as_usize());
234    }
235
236    /// Removes an element from the [`Column`] and returns it and its change detection ticks.
237    /// This does not preserve ordering, but is O(1) and does not do any bounds checking.
238    ///
239    /// The element is replaced with the last element in the [`Column`].
240    ///
241    /// It's the caller's responsibility to ensure that the removed value is dropped or used.
242    /// Failure to do so may result in resources not being released (i.e. files handles not being
243    /// released, memory leaks, etc.)
244    ///
245    /// # Safety
246    /// `row` must be within the range `[0, self.len())`.
247    #[inline]
248    #[must_use = "The returned pointer should be used to dropped the removed component"]
249    pub(crate) unsafe fn swap_remove_and_forget_unchecked(
250        &mut self,
251        row: TableRow,
252    ) -> (OwningPtr<'_>, ComponentTicks) {
253        let data = self.data.swap_remove_and_forget_unchecked(row.as_usize());
254        let added = self.added_ticks.swap_remove(row.as_usize()).into_inner();
255        let changed = self.changed_ticks.swap_remove(row.as_usize()).into_inner();
256        (data, ComponentTicks { added, changed })
257    }
258
259    /// Removes the element from `other` at `src_row` and inserts it
260    /// into the current column to initialize the values at `dst_row`.
261    /// Does not do any bounds checking.
262    ///
263    /// # Safety
264    ///
265    ///  - `other` must have the same data layout as `self`
266    ///  - `src_row` must be in bounds for `other`
267    ///  - `dst_row` must be in bounds for `self`
268    ///  - `other[src_row]` must be initialized to a valid value.
269    ///  - `self[dst_row]` must not be initialized yet.
270    #[inline]
271    pub(crate) unsafe fn initialize_from_unchecked(
272        &mut self,
273        other: &mut Column,
274        src_row: TableRow,
275        dst_row: TableRow,
276    ) {
277        debug_assert!(self.data.layout() == other.data.layout());
278        let ptr = self.data.get_unchecked_mut(dst_row.as_usize());
279        other.data.swap_remove_unchecked(src_row.as_usize(), ptr);
280        *self.added_ticks.get_unchecked_mut(dst_row.as_usize()) =
281            other.added_ticks.swap_remove(src_row.as_usize());
282        *self.changed_ticks.get_unchecked_mut(dst_row.as_usize()) =
283            other.changed_ticks.swap_remove(src_row.as_usize());
284    }
285
286    /// Pushes a new value onto the end of the [`Column`].
287    ///
288    /// # Safety
289    /// `ptr` must point to valid data of this column's component type
290    pub(crate) unsafe fn push(&mut self, ptr: OwningPtr<'_>, ticks: ComponentTicks) {
291        self.data.push(ptr);
292        self.added_ticks.push(UnsafeCell::new(ticks.added));
293        self.changed_ticks.push(UnsafeCell::new(ticks.changed));
294    }
295
296    #[inline]
297    pub(crate) fn reserve_exact(&mut self, additional: usize) {
298        self.data.reserve_exact(additional);
299        self.added_ticks.reserve_exact(additional);
300        self.changed_ticks.reserve_exact(additional);
301    }
302
303    /// Fetches the data pointer to the first element of the [`Column`].
304    ///
305    /// The pointer is type erased, so using this function to fetch anything
306    /// other than the first element will require computing the offset using
307    /// [`Column::item_layout`].
308    #[inline]
309    pub fn get_data_ptr(&self) -> Ptr<'_> {
310        self.data.get_ptr()
311    }
312
313    /// Fetches the slice to the [`Column`]'s data cast to a given type.
314    ///
315    /// Note: The values stored within are [`UnsafeCell`].
316    /// Users of this API must ensure that accesses to each individual element
317    /// adhere to the safety invariants of [`UnsafeCell`].
318    ///
319    /// # Safety
320    /// The type `T` must be the type of the items in this column.
321    pub unsafe fn get_data_slice<T>(&self) -> &[UnsafeCell<T>] {
322        self.data.get_slice()
323    }
324
325    /// Fetches the slice to the [`Column`]'s "added" change detection ticks.
326    ///
327    /// Note: The values stored within are [`UnsafeCell`].
328    /// Users of this API must ensure that accesses to each individual element
329    /// adhere to the safety invariants of [`UnsafeCell`].
330    #[inline]
331    pub fn get_added_ticks_slice(&self) -> &[UnsafeCell<Tick>] {
332        &self.added_ticks
333    }
334
335    /// Fetches the slice to the [`Column`]'s "changed" change detection ticks.
336    ///
337    /// Note: The values stored within are [`UnsafeCell`].
338    /// Users of this API must ensure that accesses to each individual element
339    /// adhere to the safety invariants of [`UnsafeCell`].
340    #[inline]
341    pub fn get_changed_ticks_slice(&self) -> &[UnsafeCell<Tick>] {
342        &self.changed_ticks
343    }
344
345    /// Fetches a reference to the data and change detection ticks at `row`.
346    ///
347    /// Returns `None` if `row` is out of bounds.
348    #[inline]
349    pub fn get(&self, row: TableRow) -> Option<(Ptr<'_>, TickCells<'_>)> {
350        (row.as_usize() < self.data.len())
351            // SAFETY: The row is length checked before fetching the pointer. This is being
352            // accessed through a read-only reference to the column.
353            .then(|| unsafe {
354                (
355                    self.data.get_unchecked(row.as_usize()),
356                    TickCells {
357                        added: self.added_ticks.get_unchecked(row.as_usize()),
358                        changed: self.changed_ticks.get_unchecked(row.as_usize()),
359                    },
360                )
361            })
362    }
363
364    /// Fetches a read-only reference to the data at `row`.
365    ///
366    /// Returns `None` if `row` is out of bounds.
367    #[inline]
368    pub fn get_data(&self, row: TableRow) -> Option<Ptr<'_>> {
369        (row.as_usize() < self.data.len()).then(|| {
370            // SAFETY: The row is length checked before fetching the pointer. This is being
371            // accessed through a read-only reference to the column.
372            unsafe { self.data.get_unchecked(row.as_usize()) }
373        })
374    }
375
376    /// Fetches a read-only reference to the data at `row`. Unlike [`Column::get`] this does not
377    /// do any bounds checking.
378    ///
379    /// # Safety
380    /// - `row` must be within the range `[0, self.len())`.
381    /// - no other mutable reference to the data of the same row can exist at the same time
382    #[inline]
383    pub unsafe fn get_data_unchecked(&self, row: TableRow) -> Ptr<'_> {
384        debug_assert!(row.as_usize() < self.data.len());
385        self.data.get_unchecked(row.as_usize())
386    }
387
388    /// Fetches a mutable reference to the data at `row`.
389    ///
390    /// Returns `None` if `row` is out of bounds.
391    #[inline]
392    pub fn get_data_mut(&mut self, row: TableRow) -> Option<PtrMut<'_>> {
393        (row.as_usize() < self.data.len()).then(|| {
394            // SAFETY: The row is length checked before fetching the pointer. This is being
395            // accessed through an exclusive reference to the column.
396            unsafe { self.data.get_unchecked_mut(row.as_usize()) }
397        })
398    }
399
400    /// Fetches a mutable reference to the data at `row`. Unlike [`Column::get_data_mut`] this does not
401    /// do any bounds checking.
402    ///
403    /// # Safety
404    /// - index must be in-bounds
405    /// - no other reference to the data of the same row can exist at the same time
406    #[inline]
407    pub(crate) unsafe fn get_data_unchecked_mut(&mut self, row: TableRow) -> PtrMut<'_> {
408        debug_assert!(row.as_usize() < self.data.len());
409        self.data.get_unchecked_mut(row.as_usize())
410    }
411
412    /// Fetches the "added" change detection tick for the value at `row`.
413    ///
414    /// Returns `None` if `row` is out of bounds.
415    ///
416    /// Note: The values stored within are [`UnsafeCell`].
417    /// Users of this API must ensure that accesses to each individual element
418    /// adhere to the safety invariants of [`UnsafeCell`].
419    #[inline]
420    pub fn get_added_tick(&self, row: TableRow) -> Option<&UnsafeCell<Tick>> {
421        self.added_ticks.get(row.as_usize())
422    }
423
424    /// Fetches the "changed" change detection tick for the value at `row`.
425    ///
426    /// Returns `None` if `row` is out of bounds.
427    ///
428    /// Note: The values stored within are [`UnsafeCell`].
429    /// Users of this API must ensure that accesses to each individual element
430    /// adhere to the safety invariants of [`UnsafeCell`].
431    #[inline]
432    pub fn get_changed_tick(&self, row: TableRow) -> Option<&UnsafeCell<Tick>> {
433        self.changed_ticks.get(row.as_usize())
434    }
435
436    /// Fetches the change detection ticks for the value at `row`.
437    ///
438    /// Returns `None` if `row` is out of bounds.
439    #[inline]
440    pub fn get_ticks(&self, row: TableRow) -> Option<ComponentTicks> {
441        if row.as_usize() < self.data.len() {
442            // SAFETY: The size of the column has already been checked.
443            Some(unsafe { self.get_ticks_unchecked(row) })
444        } else {
445            None
446        }
447    }
448
449    /// Fetches the "added" change detection tick for the value at `row`. Unlike [`Column::get_added_tick`]
450    /// this function does not do any bounds checking.
451    ///
452    /// # Safety
453    /// `row` must be within the range `[0, self.len())`.
454    #[inline]
455    pub unsafe fn get_added_tick_unchecked(&self, row: TableRow) -> &UnsafeCell<Tick> {
456        debug_assert!(row.as_usize() < self.added_ticks.len());
457        self.added_ticks.get_unchecked(row.as_usize())
458    }
459
460    /// Fetches the "changed" change detection tick for the value at `row`. Unlike [`Column::get_changed_tick`]
461    /// this function does not do any bounds checking.
462    ///
463    /// # Safety
464    /// `row` must be within the range `[0, self.len())`.
465    #[inline]
466    pub unsafe fn get_changed_tick_unchecked(&self, row: TableRow) -> &UnsafeCell<Tick> {
467        debug_assert!(row.as_usize() < self.changed_ticks.len());
468        self.changed_ticks.get_unchecked(row.as_usize())
469    }
470
471    /// Fetches the change detection ticks for the value at `row`. Unlike [`Column::get_ticks`]
472    /// this function does not do any bounds checking.
473    ///
474    /// # Safety
475    /// `row` must be within the range `[0, self.len())`.
476    #[inline]
477    pub unsafe fn get_ticks_unchecked(&self, row: TableRow) -> ComponentTicks {
478        debug_assert!(row.as_usize() < self.added_ticks.len());
479        debug_assert!(row.as_usize() < self.changed_ticks.len());
480        ComponentTicks {
481            added: self.added_ticks.get_unchecked(row.as_usize()).read(),
482            changed: self.changed_ticks.get_unchecked(row.as_usize()).read(),
483        }
484    }
485
486    /// Clears the column, removing all values.
487    ///
488    /// Note that this function has no effect on the allocated capacity of the [`Column`]>
489    pub fn clear(&mut self) {
490        self.data.clear();
491        self.added_ticks.clear();
492        self.changed_ticks.clear();
493    }
494
495    #[inline]
496    pub(crate) fn check_change_ticks(&mut self, change_tick: Tick) {
497        for component_ticks in &mut self.added_ticks {
498            component_ticks.get_mut().check_tick(change_tick);
499        }
500        for component_ticks in &mut self.changed_ticks {
501            component_ticks.get_mut().check_tick(change_tick);
502        }
503    }
504}
505
506/// A builder type for constructing [`Table`]s.
507///
508///  - Use [`with_capacity`] to initialize the builder.
509///  - Repeatedly call [`add_column`] to add columns for components.
510///  - Finalize with [`build`] to get the constructed [`Table`].
511///
512/// [`with_capacity`]: Self::with_capacity
513/// [`add_column`]: Self::add_column
514/// [`build`]: Self::build
515pub(crate) struct TableBuilder {
516    columns: SparseSet<ComponentId, Column>,
517    capacity: usize,
518}
519
520impl TableBuilder {
521    /// Creates a blank [`Table`], allocating space for `column_capacity` columns
522    /// with the capacity to hold `capacity` entities worth of components each.
523    pub fn with_capacity(capacity: usize, column_capacity: usize) -> Self {
524        Self {
525            columns: SparseSet::with_capacity(column_capacity),
526            capacity,
527        }
528    }
529
530    #[must_use]
531    pub fn add_column(mut self, component_info: &ComponentInfo) -> Self {
532        self.columns.insert(
533            component_info.id(),
534            Column::with_capacity(component_info, self.capacity),
535        );
536        self
537    }
538
539    #[must_use]
540    pub fn build(self) -> Table {
541        Table {
542            columns: self.columns.into_immutable(),
543            entities: Vec::with_capacity(self.capacity),
544        }
545    }
546}
547
548/// A column-oriented [structure-of-arrays] based storage for [`Component`]s of entities
549/// in a [`World`].
550///
551/// Conceptually, a `Table` can be thought of as an `HashMap<ComponentId, Column>`, where
552/// each [`Column`] is a type-erased `Vec<T: Component>`. Each row corresponds to a single entity
553/// (i.e. index 3 in Column A and index 3 in Column B point to different components on the same
554/// entity). Fetching components from a table involves fetching the associated column for a
555/// component type (via its [`ComponentId`]), then fetching the entity's row within that column.
556///
557/// [structure-of-arrays]: https://en.wikipedia.org/wiki/AoS_and_SoA#Structure_of_arrays
558/// [`Component`]: crate::component::Component
559/// [`World`]: crate::world::World
560pub struct Table {
561    columns: ImmutableSparseSet<ComponentId, Column>,
562    entities: Vec<Entity>,
563}
564
565impl Table {
566    /// Fetches a read-only slice of the entities stored within the [`Table`].
567    #[inline]
568    pub fn entities(&self) -> &[Entity] {
569        &self.entities
570    }
571
572    /// Removes the entity at the given row and returns the entity swapped in to replace it (if an
573    /// entity was swapped in)
574    ///
575    /// # Safety
576    /// `row` must be in-bounds
577    pub(crate) unsafe fn swap_remove_unchecked(&mut self, row: TableRow) -> Option<Entity> {
578        for column in self.columns.values_mut() {
579            column.swap_remove_unchecked(row);
580        }
581        let is_last = row.as_usize() == self.entities.len() - 1;
582        self.entities.swap_remove(row.as_usize());
583        if is_last {
584            None
585        } else {
586            Some(self.entities[row.as_usize()])
587        }
588    }
589
590    /// Moves the `row` column values to `new_table`, for the columns shared between both tables.
591    /// Returns the index of the new row in `new_table` and the entity in this table swapped in
592    /// to replace it (if an entity was swapped in). missing columns will be "forgotten". It is
593    /// the caller's responsibility to drop them.  Failure to do so may result in resources not
594    /// being released (i.e. files handles not being released, memory leaks, etc.)
595    ///
596    /// # Safety
597    /// Row must be in-bounds
598    pub(crate) unsafe fn move_to_and_forget_missing_unchecked(
599        &mut self,
600        row: TableRow,
601        new_table: &mut Table,
602    ) -> TableMoveResult {
603        debug_assert!(row.as_usize() < self.entity_count());
604        let is_last = row.as_usize() == self.entities.len() - 1;
605        let new_row = new_table.allocate(self.entities.swap_remove(row.as_usize()));
606        for (component_id, column) in self.columns.iter_mut() {
607            if let Some(new_column) = new_table.get_column_mut(*component_id) {
608                new_column.initialize_from_unchecked(column, row, new_row);
609            } else {
610                // It's the caller's responsibility to drop these cases.
611                let (_, _) = column.swap_remove_and_forget_unchecked(row);
612            }
613        }
614        TableMoveResult {
615            new_row,
616            swapped_entity: if is_last {
617                None
618            } else {
619                Some(self.entities[row.as_usize()])
620            },
621        }
622    }
623
624    /// Moves the `row` column values to `new_table`, for the columns shared between both tables.
625    /// Returns the index of the new row in `new_table` and the entity in this table swapped in
626    /// to replace it (if an entity was swapped in).
627    ///
628    /// # Safety
629    /// row must be in-bounds
630    pub(crate) unsafe fn move_to_and_drop_missing_unchecked(
631        &mut self,
632        row: TableRow,
633        new_table: &mut Table,
634    ) -> TableMoveResult {
635        debug_assert!(row.as_usize() < self.entity_count());
636        let is_last = row.as_usize() == self.entities.len() - 1;
637        let new_row = new_table.allocate(self.entities.swap_remove(row.as_usize()));
638        for (component_id, column) in self.columns.iter_mut() {
639            if let Some(new_column) = new_table.get_column_mut(*component_id) {
640                new_column.initialize_from_unchecked(column, row, new_row);
641            } else {
642                column.swap_remove_unchecked(row);
643            }
644        }
645        TableMoveResult {
646            new_row,
647            swapped_entity: if is_last {
648                None
649            } else {
650                Some(self.entities[row.as_usize()])
651            },
652        }
653    }
654
655    /// Moves the `row` column values to `new_table`, for the columns shared between both tables.
656    /// Returns the index of the new row in `new_table` and the entity in this table swapped in
657    /// to replace it (if an entity was swapped in).
658    ///
659    /// # Safety
660    /// `row` must be in-bounds. `new_table` must contain every component this table has
661    pub(crate) unsafe fn move_to_superset_unchecked(
662        &mut self,
663        row: TableRow,
664        new_table: &mut Table,
665    ) -> TableMoveResult {
666        debug_assert!(row.as_usize() < self.entity_count());
667        let is_last = row.as_usize() == self.entities.len() - 1;
668        let new_row = new_table.allocate(self.entities.swap_remove(row.as_usize()));
669        for (component_id, column) in self.columns.iter_mut() {
670            new_table
671                .get_column_mut(*component_id)
672                .debug_checked_unwrap()
673                .initialize_from_unchecked(column, row, new_row);
674        }
675        TableMoveResult {
676            new_row,
677            swapped_entity: if is_last {
678                None
679            } else {
680                Some(self.entities[row.as_usize()])
681            },
682        }
683    }
684
685    /// Fetches a read-only reference to the [`Column`] for a given [`Component`] within the
686    /// table.
687    ///
688    /// Returns `None` if the corresponding component does not belong to the table.
689    ///
690    /// [`Component`]: crate::component::Component
691    #[inline]
692    pub fn get_column(&self, component_id: ComponentId) -> Option<&Column> {
693        self.columns.get(component_id)
694    }
695
696    /// Fetches a mutable reference to the [`Column`] for a given [`Component`] within the
697    /// table.
698    ///
699    /// Returns `None` if the corresponding component does not belong to the table.
700    ///
701    /// [`Component`]: crate::component::Component
702    #[inline]
703    pub(crate) fn get_column_mut(&mut self, component_id: ComponentId) -> Option<&mut Column> {
704        self.columns.get_mut(component_id)
705    }
706
707    /// Checks if the table contains a [`Column`] for a given [`Component`].
708    ///
709    /// Returns `true` if the column is present, `false` otherwise.
710    ///
711    /// [`Component`]: crate::component::Component
712    #[inline]
713    pub fn has_column(&self, component_id: ComponentId) -> bool {
714        self.columns.contains(component_id)
715    }
716
717    /// Reserves `additional` elements worth of capacity within the table.
718    pub(crate) fn reserve(&mut self, additional: usize) {
719        if self.entities.capacity() - self.entities.len() < additional {
720            self.entities.reserve(additional);
721
722            // use entities vector capacity as driving capacity for all related allocations
723            let new_capacity = self.entities.capacity();
724
725            for column in self.columns.values_mut() {
726                column.reserve_exact(new_capacity - column.len());
727            }
728        }
729    }
730
731    /// Allocates space for a new entity
732    ///
733    /// # Safety
734    /// the allocated row must be written to immediately with valid values in each column
735    pub(crate) unsafe fn allocate(&mut self, entity: Entity) -> TableRow {
736        self.reserve(1);
737        let index = self.entities.len();
738        self.entities.push(entity);
739        for column in self.columns.values_mut() {
740            column.data.set_len(self.entities.len());
741            column.added_ticks.push(UnsafeCell::new(Tick::new(0)));
742            column.changed_ticks.push(UnsafeCell::new(Tick::new(0)));
743        }
744        TableRow::from_usize(index)
745    }
746
747    /// Gets the number of entities currently being stored in the table.
748    #[inline]
749    pub fn entity_count(&self) -> usize {
750        self.entities.len()
751    }
752
753    /// Gets the number of components being stored in the table.
754    #[inline]
755    pub fn component_count(&self) -> usize {
756        self.columns.len()
757    }
758
759    /// Gets the maximum number of entities the table can currently store
760    /// without reallocating the underlying memory.
761    #[inline]
762    pub fn entity_capacity(&self) -> usize {
763        self.entities.capacity()
764    }
765
766    /// Checks if the [`Table`] is empty or not.
767    ///
768    /// Returns `true` if the table contains no entities, `false` otherwise.
769    #[inline]
770    pub fn is_empty(&self) -> bool {
771        self.entities.is_empty()
772    }
773
774    pub(crate) fn check_change_ticks(&mut self, change_tick: Tick) {
775        for column in self.columns.values_mut() {
776            column.check_change_ticks(change_tick);
777        }
778    }
779
780    /// Iterates over the [`Column`]s of the [`Table`].
781    pub fn iter(&self) -> impl Iterator<Item = &Column> {
782        self.columns.values()
783    }
784
785    /// Clears all of the stored components in the [`Table`].
786    pub(crate) fn clear(&mut self) {
787        self.entities.clear();
788        for column in self.columns.values_mut() {
789            column.clear();
790        }
791    }
792}
793
794/// A collection of [`Table`] storages, indexed by [`TableId`]
795///
796/// Can be accessed via [`Storages`](crate::storage::Storages)
797pub struct Tables {
798    tables: Vec<Table>,
799    table_ids: HashMap<Box<[ComponentId]>, TableId>,
800}
801
802impl Default for Tables {
803    fn default() -> Self {
804        let empty_table = TableBuilder::with_capacity(0, 0).build();
805        Tables {
806            tables: vec![empty_table],
807            table_ids: HashMap::default(),
808        }
809    }
810}
811
812pub(crate) struct TableMoveResult {
813    pub swapped_entity: Option<Entity>,
814    pub new_row: TableRow,
815}
816
817impl Tables {
818    /// Returns the number of [`Table`]s this collection contains
819    #[inline]
820    pub fn len(&self) -> usize {
821        self.tables.len()
822    }
823
824    /// Returns true if this collection contains no [`Table`]s
825    #[inline]
826    pub fn is_empty(&self) -> bool {
827        self.tables.is_empty()
828    }
829
830    /// Fetches a [`Table`] by its [`TableId`].
831    ///
832    /// Returns `None` if `id` is invalid.
833    #[inline]
834    pub fn get(&self, id: TableId) -> Option<&Table> {
835        self.tables.get(id.as_usize())
836    }
837
838    /// Fetches mutable references to two different [`Table`]s.
839    ///
840    /// # Panics
841    ///
842    /// Panics if `a` and `b` are equal.
843    #[inline]
844    pub(crate) fn get_2_mut(&mut self, a: TableId, b: TableId) -> (&mut Table, &mut Table) {
845        if a.as_usize() > b.as_usize() {
846            let (b_slice, a_slice) = self.tables.split_at_mut(a.as_usize());
847            (&mut a_slice[0], &mut b_slice[b.as_usize()])
848        } else {
849            let (a_slice, b_slice) = self.tables.split_at_mut(b.as_usize());
850            (&mut a_slice[a.as_usize()], &mut b_slice[0])
851        }
852    }
853
854    /// Attempts to fetch a table based on the provided components,
855    /// creating and returning a new [`Table`] if one did not already exist.
856    ///
857    /// # Safety
858    /// `component_ids` must contain components that exist in `components`
859    pub(crate) unsafe fn get_id_or_insert(
860        &mut self,
861        component_ids: &[ComponentId],
862        components: &Components,
863    ) -> TableId {
864        let tables = &mut self.tables;
865        let (_key, value) = self
866            .table_ids
867            .raw_entry_mut()
868            .from_key(component_ids)
869            .or_insert_with(|| {
870                let mut table = TableBuilder::with_capacity(0, component_ids.len());
871                for component_id in component_ids {
872                    table = table.add_column(components.get_info_unchecked(*component_id));
873                }
874                tables.push(table.build());
875                (component_ids.into(), TableId::from_usize(tables.len() - 1))
876            });
877
878        *value
879    }
880
881    /// Iterates through all of the tables stored within in [`TableId`] order.
882    pub fn iter(&self) -> std::slice::Iter<'_, Table> {
883        self.tables.iter()
884    }
885
886    /// Clears all data from all [`Table`]s stored within.
887    pub(crate) fn clear(&mut self) {
888        for table in &mut self.tables {
889            table.clear();
890        }
891    }
892
893    pub(crate) fn check_change_ticks(&mut self, change_tick: Tick) {
894        for table in &mut self.tables {
895            table.check_change_ticks(change_tick);
896        }
897    }
898}
899
900impl Index<TableId> for Tables {
901    type Output = Table;
902
903    #[inline]
904    fn index(&self, index: TableId) -> &Self::Output {
905        &self.tables[index.as_usize()]
906    }
907}
908
909impl IndexMut<TableId> for Tables {
910    #[inline]
911    fn index_mut(&mut self, index: TableId) -> &mut Self::Output {
912        &mut self.tables[index.as_usize()]
913    }
914}
915
916#[cfg(test)]
917mod tests {
918    use crate as bevy_ecs;
919    use crate::component::Component;
920    use crate::ptr::OwningPtr;
921    use crate::storage::Storages;
922    use crate::{
923        component::{Components, Tick},
924        entity::Entity,
925        storage::{TableBuilder, TableRow},
926    };
927    #[derive(Component)]
928    struct W<T>(T);
929
930    #[test]
931    fn table() {
932        let mut components = Components::default();
933        let mut storages = Storages::default();
934        let component_id = components.init_component::<W<TableRow>>(&mut storages);
935        let columns = &[component_id];
936        let mut table = TableBuilder::with_capacity(0, columns.len())
937            .add_column(components.get_info(component_id).unwrap())
938            .build();
939        let entities = (0..200).map(Entity::from_raw).collect::<Vec<_>>();
940        for entity in &entities {
941            // SAFETY: we allocate and immediately set data afterwards
942            unsafe {
943                let row = table.allocate(*entity);
944                let value: W<TableRow> = W(row);
945                OwningPtr::make(value, |value_ptr| {
946                    table.get_column_mut(component_id).unwrap().initialize(
947                        row,
948                        value_ptr,
949                        Tick::new(0),
950                    );
951                });
952            };
953        }
954
955        assert_eq!(table.entity_capacity(), 256);
956        assert_eq!(table.entity_count(), 200);
957    }
958}