he3d_core/
arena.rs

1use alloc::vec::Vec;
2use core::marker::PhantomData;
3
4/// A stable generational handle into an [`Arena<T>`].
5/// 指向 [`Arena<T>`] 的稳定代际句柄。
6///
7/// An `Id` is two packed integers (slot index + generation) and never stores a reference, so it can outlive the arena without dangling.
8/// `Id` 由两个打包的整数（槽位索引 + 代际）组成，且从不存储引用，因此可以比 arena 存活更久而不会悬垂。
9/// Once a slot is removed, its generation advances, invalidating all previously issued `Id`s.
10/// 一旦槽位被移除，其代际就会递增，从而使所有先前发出的 `Id` 失效。
11///
12/// The `T` parameter is phantom: it exists only to make IDs of different arenas distinct types at compile time.
13/// `T` 参数是幻影的：它仅用于让不同 arena 的 ID 在编译期成为不同的类型。
14/// Trait impls are written by hand so that `Id<T>` is always `Copy`/`Eq`/`Hash` regardless of `T`.
15/// 特质实现均为手写，以便无论 `T` 为何，`Id<T>` 始终是 `Copy`/`Eq`/`Hash`。
16pub struct Id<T> {
17   index: u32,
18   generation: u32,
19   _marker: PhantomData<fn() -> T>,
20}
21
22impl<T> Id<T> {
23   /// The slot index of this handle.
24   /// 此句柄的槽位索引。
25   #[inline]
26   #[must_use]
27   pub fn index(self) -> u32 {
28      self.index
29   }
30
31   /// The generation of this handle.
32   /// 此句柄的代际。
33   #[inline]
34   #[must_use]
35   pub fn generation(self) -> u32 {
36      self.generation
37   }
38}
39
40impl<T> Clone for Id<T> {
41   #[inline]
42   fn clone(&self) -> Self {
43      *self
44   }
45}
46
47impl<T> Copy for Id<T> {}
48
49impl<T> PartialEq for Id<T> {
50   #[inline]
51   fn eq(&self, other: &Self) -> bool {
52      self.index == other.index && self.generation == other.generation
53   }
54}
55
56impl<T> Eq for Id<T> {}
57
58impl<T> PartialOrd for Id<T> {
59   #[inline]
60   fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
61      Some(self.cmp(other))
62   }
63}
64
65impl<T> Ord for Id<T> {
66   #[inline]
67   fn cmp(&self, other: &Self) -> core::cmp::Ordering {
68      (self.index, self.generation).cmp(&(other.index, other.generation))
69   }
70}
71
72impl<T> core::hash::Hash for Id<T> {
73   #[inline]
74   fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
75      core::hash::Hash::hash(&self.index, state);
76      core::hash::Hash::hash(&self.generation, state);
77   }
78}
79
80impl<T> core::fmt::Debug for Id<T> {
81   fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
82      write!(f, "Id({}@g{})", self.index, self.generation)
83   }
84}
85
86#[derive(Clone, Debug)]
87struct Slot<T> {
88   generation: u32,
89   value: Option<T>,
90}
91
92/// A generational arena: dense storage with reuse of freed slots and stale-handle detection.
93/// 代际 arena：密集存储，支持空闲槽位复用与过期句柄检测。
94///
95/// This is the ownership primitive behind meshes, textures, and render objects.
96/// 这是网格、纹理和渲染对象背后的所有权原语。
97/// It is intentionally a small self-contained type so it can be swapped for an external slot map without touching call sites.
98/// 它刻意做成一个小而自包含的类型，以便可以在不改动调用方的情况下替换为外部的槽位映射。
99#[derive(Clone, Debug)]
100pub struct Arena<T> {
101   slots: Vec<Slot<T>>,
102   free: Vec<u32>,
103   len: usize,
104}
105
106impl<T> Arena<T> {
107   /// Create an empty arena.
108   /// 创建一个空 arena。
109   #[must_use]
110   pub fn new() -> Self {
111      Self {
112         slots: Vec::new(),
113         free: Vec::new(),
114         len: 0,
115      }
116   }
117
118   /// Create an empty arena with storage reserved for `capacity` values.
119   /// 创建一个预留 `capacity` 个值存储空间的空 arena。
120   #[must_use]
121   pub fn with_capacity(capacity: usize) -> Self {
122      Self {
123         slots: Vec::with_capacity(capacity),
124         free: Vec::new(),
125         len: 0,
126      }
127   }
128
129   /// Insert a value and return its handle.
130   /// 插入一个值并返回其句柄。
131   ///
132   /// # Panics
133   /// 当活跃槽位数量超过 `u32` 上限时 panic（实践中不可能达到）。
134   /// Panics if the number of live slots exceeds the `u32` index space.
135   pub fn insert(&mut self, value: T) -> Id<T> {
136      self.len += 1;
137      if let Some(index) = self.free.pop() {
138         let slot = &mut self.slots[index as usize];
139         slot.generation = slot.generation.wrapping_add(1);
140         slot.value = Some(value);
141         return Id {
142            index,
143            generation: slot.generation,
144            _marker: PhantomData,
145         };
146      }
147
148      let index = u32::try_from(self.slots.len()).expect("arena index space exhausted");
149      self.slots.push(Slot {
150         generation: 0,
151         value: Some(value),
152      });
153      Id {
154         index,
155         generation: 0,
156         _marker: PhantomData,
157      }
158   }
159
160   /// Fetch a live value by handle.
161   /// 按句柄获取存活的值。
162   #[must_use]
163   pub fn get(&self, id: Id<T>) -> Option<&T> {
164      let slot = self.slots.get(id.index as usize)?;
165      if slot.generation != id.generation {
166         return None;
167      }
168      slot.value.as_ref()
169   }
170
171   /// Fetch a live value by handle, for mutation.
172   /// 按句柄获取存活的值，用于修改。
173   #[must_use]
174   pub fn get_mut(&mut self, id: Id<T>) -> Option<&mut T> {
175      let slot = self.slots.get_mut(id.index as usize)?;
176      if slot.generation != id.generation {
177         return None;
178      }
179      slot.value.as_mut()
180   }
181
182   /// Whether `id` currently refers to a live value.
183   /// `id` 当前是否指向一个存活的值。
184   #[must_use]
185   pub fn contains(&self, id: Id<T>) -> bool {
186      self.get(id).is_some()
187   }
188
189   /// Remove a value, invalidating the handle.
190   /// 移除一个值，并使该句柄失效。
191   #[must_use]
192   pub fn remove(&mut self, id: Id<T>) -> Option<T> {
193      let slot = self.slots.get_mut(id.index as usize)?;
194      if slot.generation != id.generation {
195         return None;
196      }
197      let value = slot.value.take()?;
198      slot.generation = slot.generation.wrapping_add(1);
199      self.free.push(id.index);
200      self.len -= 1;
201      Some(value)
202   }
203
204   /// The number of live values.
205   /// 存活值的数量。
206   #[must_use]
207   pub fn len(&self) -> usize {
208      self.len
209   }
210
211   /// Whether the arena holds no live values.
212   /// arena 是否不含任何存活值。
213   #[must_use]
214   pub fn is_empty(&self) -> bool {
215      self.len == 0
216   }
217
218   /// Iterate over all live `(id, value)` pairs in slot order.
219   /// 按槽位顺序遍历所有存活的 `(id, value)` 对。
220   #[must_use]
221   pub fn iter(&self) -> impl Iterator<Item = (Id<T>, &T)> {
222      self.slots.iter().enumerate().filter_map(|(index, slot)| {
223         let value = slot.value.as_ref()?;
224         let index = u32::try_from(index).ok()?;
225         Some((
226            Id {
227               index,
228               generation: slot.generation,
229               _marker: PhantomData,
230            },
231            value,
232         ))
233      })
234   }
235
236   /// Mutably iterate over all live `(id, value)` pairs in slot order.
237   /// 按槽位顺序可变地遍历所有存活的 `(id, value)` 对。
238   pub fn iter_mut(&mut self) -> impl Iterator<Item = (Id<T>, &mut T)> {
239      self
240         .slots
241         .iter_mut()
242         .enumerate()
243         .filter_map(|(index, slot)| {
244            let value = slot.value.as_mut()?;
245            let index = u32::try_from(index).ok()?;
246            Some((
247               Id {
248                  index,
249                  generation: slot.generation,
250                  _marker: PhantomData,
251               },
252               value,
253            ))
254         })
255   }
256}
257
258impl<T> Default for Arena<T> {
259   fn default() -> Self {
260      Self::new()
261   }
262}
263
264#[cfg(test)]
265mod tests {
266   use alloc::vec::Vec;
267
268   use super::Arena;
269
270   #[test]
271   fn insert_and_get() {
272      let mut arena = Arena::new();
273      let id = arena.insert(42u32);
274      assert_eq!(arena.get(id), Some(&42));
275      assert!(arena.contains(id));
276      assert_eq!(arena.len(), 1);
277   }
278
279   #[test]
280   fn removed_id_becomes_stale() {
281      let mut arena = Arena::new();
282      let id = arena.insert(7u32);
283      assert_eq!(arena.remove(id), Some(7));
284      assert!(!arena.contains(id));
285      assert_eq!(arena.get(id), None);
286      assert!(arena.is_empty());
287   }
288
289   #[test]
290   fn reused_slot_invalidates_previous_handle() {
291      let mut arena = Arena::new();
292      let first = arena.insert(1u32);
293      let _ = arena.remove(first);
294      let second = arena.insert(2u32);
295      // Same slot index, but the generation advanced.
296      // 槽位索引相同，但代际已经递增。
297      assert_eq!(first.index(), second.index());
298      assert_ne!(first, second);
299      assert_eq!(arena.get(first), None);
300      assert_eq!(arena.get(second), Some(&2));
301   }
302
303   #[test]
304   fn iter_yields_live_pairs() {
305      let mut arena = Arena::new();
306      let a = arena.insert("a");
307      let b = arena.insert("b");
308      let c = arena.insert("c");
309      let _ = arena.remove(b);
310      let mut seen: Vec<&str> = arena.iter().map(|(_, v)| *v).collect();
311      seen.sort_unstable();
312      assert_eq!(seen, ["a", "c"]);
313      assert!(arena.contains(a) && arena.contains(c));
314   }
315}
he3d_core/arena.rs

he3d_core/
arena.rs
