# MTB::Entity: Address-stable, interior-mutable Slab allocator
> 中文版请见: [README-zh.md](README-zh.md)
## ⚠️ Notes
- This allocator is experimental; APIs change frequently and may include breaking changes.
- Not thoroughly tested; may contain memory-safety issues. Use with care.
- Single-threaded only; no plans for multithreading.
- If you don’t specifically need interior mutability, prefer the `slab` crate for performance and safety.
## Introduction
While building Remusys, needing a mutable reference to allocate with `slab::Slab` made some optimizations awkward. This allocator is chunked and address-stable, and it lets you allocate while reading existing elements.
```rust
use mtb_entity_slab::*;
/// You can use `#[entity_ptr_id]` to create an opaque ID wrapper bound to a fixed policy.
/// If the allocator type is too verbose, specify an alias via `allocator_type`.
#[entity_ptr_id(InstID, policy = 256, allocator_type = InstAllocT)]
#[derive(Debug, Clone, PartialEq, Eq)]
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() {
// In general you specify the policy at the type level.
// If you used `allocator_type = InstAllocT` above, you can use the alias instead of
// the verbose type `EntityAlloc<Inst, AllocPolicy256>`.
let alloc: EntityAlloc<Inst, AllocPolicy256> = 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 while reading
let new_id = alloc.allocate(Inst::new(2000));
assert_eq!(inst.opcode, 500);
assert_eq!(new_id.deref(&alloc).opcode, 2000);
}
```
## Core types
- `EntityAlloc<E, P>` — allocator managing chunks and elements.
- `PtrID<E, P>` — pointer-style ID; internally a raw pointer. Fast but unsafe to misuse.
- `IndexedID<E, P>` — index-style ID; chunk index + in-chunk index. Safer but slower.
- `IEntityAllocID<E, P>` — trait for converting between `PtrID` and `IndexedID`.
- `IPolicyPtrID` — trait binding an ID to its object type and allocator type (policy included). Both `PtrID<E, P>` and macro-generated wrappers implement this.
## Allocation policies
Policies are compile-time constants on `P`:
- `AllocPolicy128` — 128 elements per chunk (single-level bitmap)
- `AllocPolicy256` — 256 elements per chunk (single-level bitmap)
- `AllocPolicy512` — 512 elements per chunk (single-level bitmap)
- `AllocPolicy1024` — 1024 elements per chunk (two-level bitmap)
- `AllocPolicy2048` — 2048 elements per chunk (two-level bitmap)
- `AllocPolicy4096` — 4096 elements per chunk (two-level bitmap)
Examples with an `Inst` entity:
```rust
let alloc_128: EntityAlloc<Inst, AllocPolicy128> = EntityAlloc::new();
let alloc_256: EntityAlloc<Inst, AllocPolicy256> = EntityAlloc::new();
let alloc_512: EntityAlloc<Inst, AllocPolicy512> = EntityAlloc::new();
let alloc_1024: EntityAlloc<Inst, AllocPolicy1024> = EntityAlloc::new();
let alloc_2048: EntityAlloc<Inst, AllocPolicy2048> = EntityAlloc::new();
let alloc_4096: EntityAlloc<Inst, AllocPolicy4096> = EntityAlloc::new();
let id_128 = alloc_128.allocate (Inst::new(10)); // PtrID<Inst, AllocPolicy128>
let id_256 = alloc_256.allocate (Inst::new(10)); // PtrID<Inst, AllocPolicy256>
let id_512 = alloc_512.allocate (Inst::new(10)); // PtrID<Inst, AllocPolicy512>
let id_1024 = alloc_1024.allocate(Inst::new(10)); // PtrID<Inst, AllocPolicy1024>
let id_2048 = alloc_2048.allocate(Inst::new(10)); // PtrID<Inst, AllocPolicy2048>
let id_4096 = alloc_4096.allocate(Inst::new(10)); // PtrID<Inst, AllocPolicy4096>
```
The policy on the ID helps prevent accidentally using an ID with an allocator of the wrong capacity.
## Custom ID wrappers with `#[entity_ptr_id]`
This attribute generates a newtype wrapper around `PtrID<Object, Policy>` bound to a fixed policy and, optionally, an allocator type alias.
Example:
```rust
#[entity_ptr_id(InstID, policy = 256, allocator_type = InstAllocT)]
#[derive(Debug, Clone, PartialEq, Eq)]
struct Inst { /* fields */ }
fn use_inst_id() {
// InstAllocT is a type alias for EntityAlloc<Inst, AllocPolicy256>
let alloc_inst = InstAllocT::new();
// Returned IDs are wrapped as InstID
let id = InstID(alloc_inst.allocate(Inst::new(42)));
// You can project to the object through the allocator
let data: &Inst = id.deref_alloc(&alloc_inst);
assert_eq!(data.opcode, 42);
}
```
Options:
- `policy = NNN | PolicyNNN | AllocPolicyNNN` — bind to a specific policy; NNN in [128, 4096].
- `allocator_type = AliasName` — emit a type alias for the allocator (`type AliasName = EntityAlloc<Object, Policy>`). Visibility follows the annotated type.
- `opaque` — make the inner `PtrID` field crate-visible instead of public, reducing accidental exposure.
## ID constraints
Library data structures rely on the `IPolicyPtrID` trait to describe “an ID tied to a particular object and allocator type.” Both raw `PtrID<E, P>` and any `#[entity_ptr_id]` wrappers implement it, so you can use containers with either style.
## Containers
Built on `IPolicyPtrID`, the crate provides internally-mutable containers:
- `EntityList<I>` — doubly-linked list. Typical for instruction/basic-block lists. Internally mutable; no `&mut alloc` needed, but misuse can corrupt relationships.
- `EntityRingList<I>` — ring list. Useful for def-use sets; attach has no signals, detach does.
Note: In v0.2, container generics flipped from the object type `ObjT` to the constrained ID type `I`.
---
## Safety notice
This crate uses unsafe code without formal verification. It is neither general-purpose nor guaranteed safe. Prefer `slab` unless you truly need these semantics.