1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
// Generational entity handle and the allocator that hands them out. An Entity
// is a runtime-only identity for one live instance; it is never serialized. The
// generation makes a handle to a despawned-and-recycled slot detectable, so a
// stale handle resolves to a safe `None` rather than aliasing a new entity.
//
// The allocator supports two ways to mint ids: `alloc` under `&mut self`
// (recycles freed slots), and `reserve` under `&self` (lock-free, fresh ids
// only) for command recording on worker threads. `flush` materializes reserved
// ids into the metadata table before they are looked up.
use alloc::vec::Vec;
use core::num::NonZeroU32;
use core::sync::atomic::{AtomicU32, Ordering};
// Generation 1 is the first valid generation; the NonZeroU32 niche keeps a
// zeroed handle invalid and Option<Entity> at 8 bytes.
const FIRST_GEN: NonZeroU32 = NonZeroU32::MIN;
#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
/// A live entity handle: a slot index plus the generation that slot
/// carried when the handle was minted.
pub struct Entity {
index: u32,
generation: NonZeroU32,
}
impl Entity {
pub(crate) fn new(index: u32, generation: NonZeroU32) -> Entity {
Entity { index, generation }
}
/// The entity's slot index.
pub fn index(self) -> u32 {
self.index
}
/// The generation the slot carried when this handle was minted.
pub fn generation(self) -> u32 {
self.generation.get()
}
/// Pack into a single u64 (index in the high half, generation in the low
/// half). Stable representation for an FFI / scripting boundary.
pub fn to_bits(self) -> u64 {
((self.index as u64) << 32) | self.generation.get() as u64
}
/// Inverse of `to_bits`. Returns `None` when the generation half is zero,
/// which no live handle ever has, so a zeroed or truncated value is rejected
/// instead of forged into a valid-looking entity.
pub fn from_bits(bits: u64) -> Option<Entity> {
let generation = NonZeroU32::new(bits as u32)?;
Some(Entity {
index: (bits >> 32) as u32,
generation,
})
}
/// A handle the allocator never hands out (the top index is unreachable in
/// practice). For a runtime-only component that has to name an Entity field
/// but is never built from serialized args -- its real value is inserted at
/// runtime, so this placeholder is never observed by any system.
pub fn dangling() -> Entity {
Entity {
index: u32::MAX,
generation: FIRST_GEN,
}
}
}
#[derive(Debug)]
struct EntityMeta {
generation: NonZeroU32,
alive: bool,
}
#[derive(Debug, Default)]
/// The entity allocator: slot generations, the free list, and the
/// reservation counter.
pub struct Entities {
meta: Vec<EntityMeta>,
// Recycled indices, available to `alloc`. Reservation never recycles.
free: Vec<u32>,
// Next fresh index. Always >= meta.len(); the gap is reserved-but-not-yet
// materialized fresh ids, realized by `flush`. An atomic so `reserve` can
// run under `&self` from worker threads.
next_fresh: AtomicU32,
}
impl Entities {
/// An allocator with no slots.
pub fn new() -> Entities {
Entities::default()
}
/// Allocate an entity, recycling a freed slot when one is available. The
/// recycled slot keeps the generation it was bumped to at despawn, so old
/// handles to it stay invalid.
pub fn alloc(&mut self) -> Entity {
if let Some(index) = self.free.pop() {
let meta = &mut self.meta[index as usize];
meta.alive = true;
return Entity::new(index, meta.generation);
}
let index = {
let next = self.next_fresh.get_mut();
let i = *next;
*next += 1;
i
};
self.grow_to(index);
let meta = &mut self.meta[index as usize];
meta.alive = true;
Entity::new(index, meta.generation)
}
/// Reserve a fresh entity id without taking `&mut self`. Lock-free, so it is
/// safe to call from worker threads while recording commands. Reserved ids
/// are always fresh (never recycled) and carry the first generation; call
/// `flush` under `&mut self` before looking them up.
pub fn reserve(&self) -> Entity {
let index = self.next_fresh.fetch_add(1, Ordering::Relaxed);
Entity::new(index, FIRST_GEN)
}
/// Materialize any reserved-but-unmaterialized ids into the metadata table,
/// marking them alive. Idempotent.
pub fn flush(&mut self) {
let high = *self.next_fresh.get_mut();
if high == 0 {
return;
}
self.grow_to(high - 1);
}
/// Despawn an entity. Validates the generation, so a stale or already-dead
/// handle is a no-op returning `false`. Bumps the slot's generation and
/// frees the index for reuse.
pub fn despawn(&mut self, entity: Entity) -> bool {
self.flush();
let Some(meta) = self.meta.get_mut(entity.index as usize) else {
return false;
};
if !meta.alive || meta.generation != entity.generation {
return false;
}
meta.alive = false;
meta.generation = next_generation(meta.generation);
self.free.push(entity.index);
true
}
/// Whether the handle refers to a currently-live entity. Reflects only
/// materialized state; reserved ids appear after `flush`.
pub fn is_alive(&self, entity: Entity) -> bool {
self.meta
.get(entity.index as usize)
.is_some_and(|meta| meta.alive && meta.generation == entity.generation)
}
// Number of metadata slots ever allocated (live plus recycled). Not the
// live count.
#[cfg(test)]
pub(crate) fn total_slots(&self) -> usize {
self.meta.len()
}
// Grow the metadata table so `index` is in range. Every index below
// `next_fresh` was handed out by `alloc` or `reserve` and is live until
// despawned (the free-list tracks the despawned ones), so a newly
// materialized slot starts alive at the first generation.
fn grow_to(&mut self, index: u32) {
while self.meta.len() as u32 <= index {
self.meta.push(EntityMeta {
generation: FIRST_GEN,
alive: true,
});
}
}
}
// Bump a generation, wrapping past u32::MAX back to the first valid generation
// (skipping 0, which the NonZeroU32 niche forbids). After 2^32 reuses of one
// slot a stale handle can alias a live entity again (generational ABA).
fn next_generation(generation: NonZeroU32) -> NonZeroU32 {
NonZeroU32::new(generation.get().wrapping_add(1)).unwrap_or(FIRST_GEN)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn alloc_hands_out_distinct_fresh_ids() {
let mut entities = Entities::new();
let a = entities.alloc();
let b = entities.alloc();
assert_ne!(a.index(), b.index());
assert_eq!(a.generation(), 1);
assert_eq!(b.generation(), 1);
assert!(entities.is_alive(a));
assert!(entities.is_alive(b));
}
#[test]
fn despawn_recycles_index_and_bumps_generation() {
let mut entities = Entities::new();
let a = entities.alloc();
assert!(entities.despawn(a));
// Index reused, generation advanced.
let b = entities.alloc();
assert_eq!(a.index(), b.index());
assert_eq!(b.generation(), 2);
// The stale handle no longer resolves.
assert!(!entities.is_alive(a));
assert!(entities.is_alive(b));
}
#[test]
fn double_despawn_and_stale_despawn_are_noops() {
let mut entities = Entities::new();
let a = entities.alloc();
assert!(entities.despawn(a));
assert!(!entities.despawn(a));
let b = entities.alloc();
// Despawning with the old generation must not touch the live entity.
assert!(!entities.despawn(a));
assert!(entities.is_alive(b));
}
#[test]
fn reserve_then_flush_materializes_live_entities() {
let mut entities = Entities::new();
let a = entities.reserve();
let b = entities.reserve();
assert_ne!(a.index(), b.index());
entities.flush();
assert!(entities.is_alive(a));
assert!(entities.is_alive(b));
assert_eq!(entities.total_slots(), 2);
}
#[test]
fn reserve_is_distinct_across_threads() {
use std::sync::Arc;
let entities = Arc::new(Entities::new());
let mut handles = Vec::new();
for _ in 0..8 {
let shared = Arc::clone(&entities);
handles.push(std::thread::spawn(move || {
(0..1000)
.map(|_| shared.reserve().index())
.collect::<Vec<_>>()
}));
}
let mut all: Vec<u32> = handles
.into_iter()
.flat_map(|h| h.join().unwrap())
.collect();
all.sort_unstable();
let count = all.len();
all.dedup();
assert_eq!(all.len(), count, "reserved indices must be unique");
}
#[test]
fn alloc_and_reserve_never_collide() {
let mut entities = Entities::new();
let reserved = entities.reserve();
let allocated = entities.alloc();
assert_ne!(reserved.index(), allocated.index());
}
#[test]
fn to_bits_round_trips_and_rejects_zero_generation() {
let mut entities = Entities::new();
let a = entities.alloc();
let bits = a.to_bits();
assert_eq!(Entity::from_bits(bits), Some(a));
// A zero generation half is never a live handle.
assert_eq!(Entity::from_bits(0), None);
assert_eq!(Entity::from_bits(7u64 << 32), None);
}
#[test]
fn generation_wraps_past_max_to_one() {
let max = NonZeroU32::new(u32::MAX).unwrap();
assert_eq!(next_generation(max), FIRST_GEN);
assert_eq!(next_generation(FIRST_GEN).get(), 2);
}
}