mtb_entity_slab/
policy.rs

1use crate::{
2    bitalloc::{BitAlloc, IBitAlloc, SummaryAlloc},
3    chunk::Unit,
4    gen_index::GenIndex,
5};
6use std::{num::NonZeroU16, ops::IndexMut};
7
8/// Errors that can occur when working with slice pointers.
9///
10/// This is used in pointer ID validation in `EntityAlloc`.
11#[derive(Debug)]
12pub enum SlicePtrErr {
13    /// The pointer is out of the valid address range of the slice.
14    OutOfRange,
15
16    /// The pointer is not aligned with the start of any unit in the slice.
17    NotAlignedWith,
18}
19impl std::fmt::Display for SlicePtrErr {
20    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
21        let msg = match self {
22            SlicePtrErr::OutOfRange => "Pointer is out of the valid address range of the slice.",
23            SlicePtrErr::NotAlignedWith => {
24                "Pointer is not aligned with the start of any unit in the slice."
25            }
26        };
27        f.write_str(msg)
28    }
29}
30impl std::error::Error for SlicePtrErr {}
31
32/// Result type for operations involving slice pointers.
33pub type SlicePtrRes<T = ()> = Result<T, SlicePtrErr>;
34
35pub trait IUnitArray<E>: Sized + IndexMut<usize, Output = Unit<E>> {
36    const LEN: usize;
37    unsafe fn boxed_uninit() -> Box<Self>;
38    fn indexof_unit_ptr(&self, ptr: *const Unit<E>) -> Result<usize, SlicePtrErr>;
39}
40impl<E, const N: usize> IUnitArray<E> for [Unit<E>; N] {
41    const LEN: usize = N;
42
43    unsafe fn boxed_uninit() -> Box<Self> {
44        let mut ret: Box<Self> = unsafe { Box::new_uninit().assume_init() };
45        let init_id = initial_id::initial_id();
46        for i in 0..Self::LEN {
47            ret[i].indexed = init_id;
48        }
49        ret
50    }
51
52    fn indexof_unit_ptr(&self, ptr: *const Unit<E>) -> Result<usize, SlicePtrErr> {
53        use std::ops::Range;
54        let unit_size = std::mem::size_of::<Unit<E>>();
55        let Range { start, end } = self.as_ptr_range();
56        let start_addr = start as usize;
57        let end_addr = end as usize;
58        let ptr_addr = ptr as usize;
59        if ptr_addr < start_addr || ptr_addr >= end_addr {
60            return Err(SlicePtrErr::OutOfRange);
61        }
62        let offset = ptr_addr - start_addr;
63        if !offset.is_multiple_of(unit_size) {
64            return Err(SlicePtrErr::NotAlignedWith);
65        }
66        Ok(offset / unit_size)
67    }
68}
69
70mod initial_id {
71    use crate::gen_index::GenIndex;
72
73    #[cfg(feature = "random-generation")]
74    pub(super) fn initial_id() -> GenIndex {
75        use std::num::NonZeroU16;
76
77        let generation = NonZeroU16::new(fastrand::u16(1..)).unwrap();
78        GenIndex::compose(GenIndex::INVALID_INDEX, generation)
79    }
80    #[cfg(not(feature = "random-generation"))]
81    pub(super) const fn initial_id() -> GenIndex {
82        GenIndex::compose(GenIndex::INVALID_INDEX, GenIndex::GEN_1)
83    }
84}
85
86/// Entity allocation policy trait.
87///
88/// You are NOT ALLOWED to implement this trait for your own types.
89/// You can only select the following pre-defined policies:
90///
91/// - `AllocPolicy128` - Chunk size of 128.
92/// - `AllocPolicy256` - Chunk size of 256.
93/// - `AllocPolicy512` - Chunk size of 512.
94/// - `AllocPolicy1024` - Chunk size of 1024.
95/// - `AllocPolicy2048` - Chunk size of 2048.
96/// - `AllocPolicy4096` - Chunk size of 4096.
97///
98/// Entity 分配策略接口.
99///
100/// 你不允许为自己的类型实现此接口. 你只能选择以下预定义的策略:
101///
102/// - `AllocPolicy128` - 块大小为 128.
103/// - `AllocPolicy256` - 块大小为 256.
104/// - `AllocPolicy512` - 块大小为 512.
105/// - `AllocPolicy1024` - 块大小为 1024.
106/// - `AllocPolicy2048` - 块大小为 2048.
107/// - `AllocPolicy4096` - 块大小为 4096.
108pub trait IAllocPolicy: 'static {
109    /// Chunk size log2 (e.g., 7 for 128, 8 for 256, etc.)
110    const CHUNK_SIZE_LOG2: usize;
111
112    /// Chunk size (e.g., 128, 256, etc.)
113    const CHUNK_SIZE: usize;
114
115    /// Bitset length (number of u64 units in the bitset)
116    const BITSET_LEN: usize;
117
118    /// Unit ID mask, usually CHUNK_SIZE - 1
119    const UNIT_ID_MASK: usize;
120
121    /// Bit allocator type. `MTB::Entity` chooses different bit allocators
122    /// for different chunk sizes.
123    type BitAlloc: IBitAlloc;
124
125    /// Unit array type for the chunk.
126    type Units<E>: IUnitArray<E>;
127
128    /// Compose a `GenIndex` from chunk ID, unit ID, and generation.
129    fn compose(chunk: u32, unit: u16, generation: NonZeroU16) -> GenIndex {
130        let chunk_id_shift = Self::CHUNK_SIZE_LOG2;
131        let unit_id_mask = Self::UNIT_ID_MASK;
132        let chunk_id = chunk as u64;
133        let unit_id = (unit as u64) & (unit_id_mask as u64);
134        let real_index = (chunk_id << chunk_id_shift) | unit_id;
135        GenIndex::compose(real_index as usize, generation)
136    }
137    /// Extract chunk ID from a real index.
138    fn chunkof_real(real_index: usize) -> u32 {
139        (real_index >> Self::CHUNK_SIZE_LOG2) as u32
140    }
141    /// Extract chunk ID from a `GenIndex`.
142    fn chunk(index: GenIndex) -> u32 {
143        Self::chunkof_real(index.real_index())
144    }
145
146    /// Extract unit ID from a real index.
147    fn unitof_real(real_index: usize) -> u16 {
148        (real_index & Self::UNIT_ID_MASK) as u16
149    }
150    /// Extract unit ID from a `GenIndex`.
151    fn unit(index: GenIndex) -> u16 {
152        (index.real_index() & Self::UNIT_ID_MASK) as u16
153    }
154
155    /// Tear down a `GenIndex` into chunk ID, unit ID, and generation.
156    fn tear(index: GenIndex) -> (u32, u16, NonZeroU16) {
157        let chunk = Self::chunk(index);
158        let unit = Self::unit(index);
159        let generation = index.generation();
160        (chunk, unit, generation)
161    }
162}
163pub(crate) trait IAllocPolicyPrivate: IAllocPolicy {
164    /// # Safety
165    ///
166    /// This function returns a boxed array of uninitialized units.
167    unsafe fn unit_array<E>() -> Box<Self::Units<E>> {
168        unsafe { Self::Units::boxed_uninit() }
169    }
170}
171impl<T: IAllocPolicy> IAllocPolicyPrivate for T {}
172
173macro_rules! define_entity_alloc_policy {
174    ($name:ident, $chunk_size_log2:expr, $bit_alloc:ty, $doc:expr) => {
175        #[doc = $doc]
176        pub struct $name;
177
178        impl IAllocPolicy for $name {
179            const CHUNK_SIZE_LOG2: usize = $chunk_size_log2;
180            const CHUNK_SIZE: usize = 1 << $chunk_size_log2;
181            const BITSET_LEN: usize = Self::CHUNK_SIZE / 64;
182            const UNIT_ID_MASK: usize = (1 << Self::CHUNK_SIZE_LOG2) - 1;
183
184            type BitAlloc = $bit_alloc;
185            type Units<E> = [Unit<E>; Self::CHUNK_SIZE];
186        }
187    };
188}
189
190define_entity_alloc_policy! {AllocPolicy128,  7,  BitAlloc<2>, "Entity allocation policy for chunks of size 128."}
191define_entity_alloc_policy! {AllocPolicy256,  8,  BitAlloc<4>, "Entity allocation policy for chunks of size 256."}
192define_entity_alloc_policy! {AllocPolicy512,  9,  BitAlloc<8>, "Entity allocation policy for chunks of size 512."}
193define_entity_alloc_policy! {AllocPolicy1024, 10, SummaryAlloc<16>, "Entity allocation policy for chunks of size 1024."}
194define_entity_alloc_policy! {AllocPolicy2048, 11, SummaryAlloc<32>, "Entity allocation policy for chunks of size 2048."}
195define_entity_alloc_policy! {AllocPolicy4096, 12, SummaryAlloc<64>, "Entity allocation policy for chunks of size 4096."}
mtb_entity_slab/policy.rs

mtb_entity_slab/
policy.rs
