mtb_entity_slab/
gen_index.rs

1use std::num::{NonZeroU16, NonZeroU64};
2
3/// Generation + index combined identifier used by the allocator.
4///
5/// The value stores a 16-bit generation in the low bits and a platform-sized
6/// real index in the high bits. Concretely this crate places the generation in
7/// the lower 16 bits and the real index in the upper bits of the `u64`
8/// storage. `GenIndex` is a compact handle that allows fast comparison while
9/// also providing a generation counter to detect use-after-free or stale
10/// references.
11///
12/// Key points：
13/// - Lower 16 bits: generation - to differentiate entities at the same slot across different lifetimes.
14/// - Upper bits: real index - the actual index (48 bits on 64-bit platforms)
15/// - `is_invalid()` checks if the index is a special invalid value (`INVALID_INDEX`).
16/// - `to_invalid()` replaces the real index with `INVALID_INDEX`, preserving generation info.
17/// - 使用 `generation_inc()` 在释放并重新分配同一槽位时递增 generation，避免 ABA 问题。
18///
19/// 注意：真实索引必须小于或等于 `INDEX_MASK`，否则行为未定义；该类型提供了 `compose`
20/// 和 `replace_index` 等安全构造器/替换方法。
21///
22/// 用例示例（简要）：
23/// ```ignore
24/// let idx = GenIndex::compose(1234, 1);
25/// let bumped = idx.generation_inc();
26/// assert!(!idx.generation_match(bumped));
27/// ```
28#[repr(transparent)]
29#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
30pub struct GenIndex(pub NonZeroU64);
31impl From<NonZeroU64> for GenIndex {
32    fn from(value: NonZeroU64) -> Self {
33        GenIndex(value)
34    }
35}
36impl From<GenIndex> for NonZeroU64 {
37    fn from(value: GenIndex) -> Self {
38        value.0
39    }
40}
41impl From<GenIndex> for u64 {
42    fn from(value: GenIndex) -> Self {
43        value.0.get()
44    }
45}
46impl GenIndex {
47    #[cfg(not(any(target_pointer_width = "64", target_pointer_width = "32")))]
48    compile_error!("MTB::Entity only supports 32-bit and 64-bit platform.");
49
50    /// Bit shift amount for generation bits. ( = 0 )
51    pub const GEN_SHIFT: u32 = 0;
52
53    /// Bit mask for generation bits. ( = 0xFFFF )
54    pub const GEN_MASK: u64 = 0xFFFF;
55
56    /// Generation value representing the first generation (1).
57    /// Generation 0 is reserved to represent invalid indices.
58    pub const GEN_1: NonZeroU16 = NonZeroU16::new(1).unwrap();
59
60    /// Bit mask for real index bits.
61    pub const INDEX_MASK: u64 = !Self::GEN_MASK;
62
63    /// Bit shift amount for real index bits. ( = 16 )
64    pub const INDEX_SHIFT: u32 = Self::GEN_SHIFT + 16;
65
66    /// INVALID_INDEX is a special real index value (usize::MAX) used to
67    /// represent an invalid or null reference.
68    #[cfg(target_pointer_width = "32")]
69    pub const INVALID_INDEX: usize = usize::MAX;
70
71    /// On 64-bit platforms, we can use the full 48 bits for real index,
72    /// so INVALID_INDEX is 0xFFFFFFFFFFFF.
73    #[cfg(target_pointer_width = "64")]
74    pub const INVALID_INDEX: usize = 0xFFFF_FFFF_FFFF;
75
76    pub(crate) const fn do_generation_inc(gene: NonZeroU16) -> NonZeroU16 {
77        let gene = gene.get();
78        let gene = match gene.wrapping_add(1) {
79            0 => 1, // Skip zero to maintain non-zero invariant
80            other => other,
81        };
82        NonZeroU16::new(gene).expect("Generation must be non-zero")
83    }
84
85    /// Compose a `GenIndex` from a raw `real_index` and `generation`.
86    ///
87    /// 构造函数：从真实索引和世代值组合出 `GenIndex`。`real_index` 会被掩码截断，
88    /// 因此传入值应保证在 `INDEX_MASK` 范围内以避免信息丢失。
89    pub const fn compose(real_index: usize, generation: NonZeroU16) -> Self {
90        let real_index = real_index as u64;
91        let generation = generation.get() as u64;
92        let value = real_index << Self::INDEX_SHIFT | generation;
93        let value = NonZeroU64::new(value).expect("GenIndex value must be non-zero");
94        GenIndex(value)
95    }
96
97    /// Return the generation.
98    ///
99    /// 返回世代号
100    pub const fn generation(self) -> NonZeroU16 {
101        let gene = (self.0.get() & Self::GEN_MASK) as u16;
102        NonZeroU16::new(gene).expect("GenIndex generation must be non-zero")
103    }
104
105    /// Return the real index (high bits masked by `INDEX_MASK`).
106    ///
107    /// 返回真实索引（高位，已掩码）。
108    pub const fn real_index(self) -> usize {
109        ((self.0.get() & Self::INDEX_MASK) >> Self::INDEX_SHIFT) as usize
110    }
111    /// Decompose into `(real_index, generation)` tuple.
112    ///
113    /// 拆分为 `(真实索引, 世代)`。
114    pub const fn tear(self) -> (usize, NonZeroU16) {
115        (self.real_index(), self.generation())
116    }
117
118    /// Return a new `GenIndex` with generation incremented by one.
119    ///
120    /// 世代递增（使用 wrapping add），用于在槽位复用时更新世代号以避免允许旧引用访问。
121    pub const fn generation_inc(self) -> Self {
122        let (real_index, generation) = self.tear();
123        let new_generation = Self::do_generation_inc(generation);
124        Self::compose(real_index, new_generation)
125    }
126
127    /// Check whether two `GenIndex` values have the same generation.
128    ///
129    /// 比较两个索引的世代是否相同（不关心真实索引部分）。
130    pub const fn generation_match(self, other: Self) -> bool {
131        let lgene = self.0.get() & Self::GEN_MASK;
132        let rgene = other.0.get() & Self::GEN_MASK;
133        lgene == rgene
134    }
135
136    /// Replace the real-index portion while preserving the generation bits.
137    ///
138    /// 替换真实索引部分，同时保留世代位。这在需要重映射索引但保留
139    /// 当前世代信息时非常有用。`new_index` 将被掩码截断以适配位宽。
140    pub const fn replace_index(self, new_index: usize) -> Self {
141        Self::compose(new_index, self.generation())
142    }
143
144    /// Check whether this `GenIndex` represents an invalid sentinel index.
145    ///
146    /// 判定是否为特殊无效索引（`INVALID_INDEX`），通常用于表示无效/空引用。
147    pub const fn is_invalid(self) -> bool {
148        self.real_index() == Self::INVALID_INDEX
149    }
150
151    /// Convert this `GenIndex` into an invalid-index while preserving generation bits.
152    ///
153    /// 将真实索引替换为 `INVALID_INDEX`，保留世代信息。
154    pub const fn to_invalid(self) -> Self {
155        self.replace_index(Self::INVALID_INDEX)
156    }
157
158    /// Create a canonical invalid `GenIndex` with generation `1`.
159    ///
160    /// 返回一个基本的无效索引（世代 = 1）。
161    pub const fn new_basic_invalid() -> Self {
162        GenIndex::compose(Self::INVALID_INDEX, Self::GEN_1)
163    }
164}
mtb_entity_slab/gen_index.rs

mtb_entity_slab/
gen_index.rs
