# MTB::Entity: An address-stable, interior-mutable Slab allocator
> 中文版请见: [README-zh.md](README-zh.md)
## ⚠️ Notes
- This allocator is experimental; its API may change significantly.
- It has not been thoroughly tested and may contain memory-safety issues. Use with care.
- It currently supports single-threaded use only, with no plans for multithreading support.
- The recommended alternative is the `slab` crate — it’s superior in both performance and safety in general. If you don’t specifically need interior mutability, prefer `slab`.
## Introduction
The motivation for this allocator came while building Remusys. The `slab` crate’s `Slab` requires a mutable reference to allocate elements, which complicated some of my optimizations. This chunked, address-stable allocator lets you allocate new elements while reading existing ones:
```rust
use mtb_entity_slab::{EntityAlloc, PtrID, IEntityAllocatable, EntityAllocPolicy256};
/// Not every type can be stored in this allocator. You need to implement the
/// `IEntityAllocatable` trait for your type.
///
/// If you're lazy enough, you can use the new proc macro `entity_allocatable`.
#[derive(Debug, Clone, PartialEq, Eq)]
#[mtb_entity_slab::entity_allocatable]
struct Inst {
pub opcode: u32,
pub operands: [u64; 4],
pub heap_data: String,
}
impl Inst {
fn new(opcode: u32) -> Self {
Self {
opcode,
operands: [0; 4],
heap_data: format!("InstData{}", opcode),
}
}
}
fn main() {
let mut alloc = EntityAlloc::with_capacity(1024);
let ptrs = {
let mut v = Vec::new();
for i in 0..1000 {
let ptr = alloc.allocate(Inst::new(i));
v.push(ptr);
}
v
};
let inst = ptrs[500].deref(&alloc);
// Allocate a new element while concurrently reading existing ones
let new_id = alloc.allocate(Inst::new(2000));
assert_eq!(inst.opcode, 500);
assert_eq!(new_id.deref(&alloc).opcode, 2000);
}
```
## Basic type hierarchy
- `EntityAlloc` — The allocator itself; manages all chunks and the allocation/freeing of elements.
- `IEntityAllocID<E>` — A trait for converting between `PtrID` and `IndexedID`.
- `PtrID<E>` — An ID pointing to an element inside the allocator, internally a raw pointer. Fast but unsafe.
- `IndexedID<E>` — An ID pointing to an element, represented by a pair of chunk index and in-chunk index. Safe but much slower.
- `IDProxy<'alloc, E>` — A proxy used for two-phase initialization of a target element.
## Allocation policies
The allocator supports multiple allocation strategies to fit different scenarios. Not every type can be stored in the allocator; your type must implement `IEntityAllocatable` and specify a policy. Available policies:
- `EntityAllocPolicy128<E>` — 128 elements per chunk (medium/small chunks, single-level bitmap).
- `EntityAllocPolicy256<E>` — 256 elements per chunk (medium/small chunks, single-level bitmap).
- `EntityAllocPolicy512<E>` — 512 elements per chunk (medium/small chunks, single-level bitmap).
- `EntityAllocPolicy1024<E>` — 1024 elements per chunk (large chunks, two-level bitmap).
- `EntityAllocPolicy2048<E>` — 2048 elements per chunk (large chunks, two-level bitmap).
- `EntityAllocPolicy4096<E>` — 4096 elements per chunk (large chunks, two-level bitmap).
Here’s the boilerplate for making a type allocatable, as in the example above:
```rust
use mtb_entity_slab::{IEntityAllocatable, EntityAllocPolicyXXX};
struct MyType {
// ...
}
impl IEntityAllocatable for MyType {
type AllocatePolicyT = EntityAllocPolicyXXX<Self>;
}
```
## Containers
Some container types are built on top of `EntityAlloc` for convenience:
- `EntityList<E>` — A doubly-linked list of entities. Internally mutable; modifying the list does not require `EntityAlloc` to be mutable.
- `EntityRingList<E>` — A doubly-linked ring list of entities. Internally mutable; modifying the list does not require `EntityAlloc` to be mutable.
## Auto-implementation Using `#[entity_allocatable]` Macro
The procedural attribute macro reduces boilerplate when implementing `IEntityAllocatable`.
Supported argument keys (all optional, order independent):
- `policy = ...` Choose allocation policy. Accepted forms:
- Short identifier: `Policy128`, `Policy256`, `Policy512`, `Policy1024`, `Policy2048`, `Policy4096`
- Full type name: `EntityAllocPolicy256`
- Integer literal: `128`, `256`, `512`, `1024`, `2048`, `4096`
Default: `Policy256` (i.e. `EntityAllocPolicy256`).
- `ptrid = TypePath` Use an external custom pointer ID type you define. Must implement `Copy + Eq` and conversions `From<PtrID<Self>>` and `From<Custom> for PtrID<Self>` (the macro does not generate those for external types).
- `wrapper = Ident` Generate a transparent newtype around `PtrID<Self>`; field is public; `Debug` prints the raw pointer address.
- `opaque_wrapper = Ident` Generate an opaque newtype; field is private; `Debug` hides the pointer address (`TypeName(<opaque>)`).
Mutual exclusions:
- `ptrid` cannot be combined with `wrapper` or `opaque_wrapper`.
- `wrapper` and `opaque_wrapper` cannot be used at the same time.
- Repeating the same key (e.g. two `policy=`) triggers a compile error.
### Minimal usage
```rust
use mtb_entity_slab::entity_allocatable;
#[entity_allocatable]
struct A;
```
Expands to roughly:
```rust
impl IEntityAllocatable for A {
type AllocatePolicyT = EntityAllocPolicy256<A>;
type PtrID = PtrID<A>;
}
```
### Specify a different policy
```rust
#[entity_allocatable(policy = Policy512)]
struct B;
```
or equivalently:
```rust
#[entity_allocatable(policy = 512)]
struct B;
```
### Generate a transparent wrapper type
```rust
#[entity_allocatable(wrapper = CPtr)]
struct C;
// Generated:
// pub struct CPtr(pub mtb_entity_slab::PtrID<C>); // Copy, Debug prints address
// impl IEntityAllocatable for C { type PtrID = CPtr; ... }
```
### Generate an opaque wrapper type
```rust
#[entity_allocatable(opaque_wrapper = DPtr, policy = 1024)]
struct D;
// pub struct DPtr(mtb_entity_slab::PtrID<D>); // field private, Debug hides address
// impl IEntityAllocatable for D { type PtrID = DPtr; type AllocatePolicyT = EntityAllocPolicy1024<D>; }
```
### Use external custom PtrID type
```rust
// Your custom type (must implement the required conversions)
#[derive(Copy, Clone, Eq, PartialEq)]
pub struct MyPtrID(PtrID<MyEntity>);
impl From<PtrID<MyEntity>> for MyPtrID {
fn from(p: PtrID<MyEntity>) -> Self { Self(p) }
}
impl From<MyPtrID> for PtrID<MyEntity> {
fn from(x: MyPtrID) -> Self { x.0 }
}
#[entity_allocatable(ptrid = MyPtrID, policy = Policy128)]
struct MyEntity;
```
### Generics example
Generics are supported; wrappers and policies apply per instantiation:
```rust
#[entity_allocatable(wrapper = NodePtr, policy = 4096)]
pub struct Node<T> { value: T }
// impl<T> IEntityAllocatable for Node<T> { ... }
// pub struct NodePtr<T>(pub PtrID<Node<T>>); // Copy, Debug prints address
```
### Error reporting
The macro validates conflicts (e.g. `ptrid` with `wrapper`) and repeats, and emits concise compile errors pointing to the offending argument.
### When to choose wrapper vs external ptrid
- Use `wrapper` / `opaque_wrapper` when you only need a thin newtype—conversion impls and `Debug` are generated for you.
- Use `ptrid = ...` when you need more control (extra trait impls, custom methods) and are willing to implement conversions yourself.
### Fallback: manual implementation
You can always bypass the macro:
```rust
impl IEntityAllocatable for ManualType {
type AllocatePolicyT = EntityAllocPolicy256<ManualType>;
type PtrID = PtrID<ManualType>;
}
```
If the macro doesn’t cover a special scenario, open an issue or implement manually.