# MTB::Entity: Address-stable, interior-mutable Slab allocator
> 中文版请见: [README-zh.md](README-zh.md)
## ⚠️ Notes
- This allocator is experimental and unstable: for each semver 0.x.y, each `.y` change causes API breaking changes and
each `.x` change causes rewrite or redesign of this project.
- 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_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_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 {
// Allocate while only holding &alloc (interior mutability)
let ptr = alloc.allocate_ptr(Inst::new(i));
v.push(ptr);
}
v
};
let inst = ptrs[500].deref(&alloc);
// Allocate while reading
let new_id = alloc.allocate_ptr(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`.
- `IPoliciedID` — trait binding an ID to its object type and allocator type (policy included). `PtrID<E, P>`, `IndexedID<E, P>` and macro-generated wrappers implement this.
- `IDBoundAlloc<I>` — convenience alias for `EntityAlloc<<I as IPoliciedID>::ObjectT, <I as IPoliciedID>::PolicyT>`.
## 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_id]`
This attribute generates a newtype wrapper around a backend ID (`PtrID<Object, Policy>` or `IndexedID<Object, Policy>`) bound to a fixed policy and, optionally, an allocator type alias.
Example:
```rust
// Pointer backend (default)
#[entity_id(InstID, policy = 256, allocator_type = InstAllocT, backend = ptr)]
#[derive(Debug, Clone, PartialEq, Eq)]
struct Inst { /* fields */ }
fn use_inst_id_ptr_backend() {
// InstAllocT is a type alias for EntityAlloc<Inst, AllocPolicy256>
let alloc_inst = InstAllocT::new();
// Allocate raw backend ID then wrap
let raw: PtrID<Inst, AllocPolicy256> = alloc_inst.allocate_ptr(Inst::new(42));
let id = InstID::from(raw); // or InstID::from_backend(raw)
let data: &Inst = id.deref_alloc(&alloc_inst);
assert_eq!(data.opcode, 42);
}
// Index backend (safer, slower)
#[entity_id(InstIndexID, policy = 256, backend = index)]
#[derive(Debug, Clone, PartialEq, Eq)]
struct Inst2 { /* fields */ }
fn use_inst_id_index_backend() {
let alloc: EntityAlloc<Inst2, AllocPolicy256> = EntityAlloc::new();
let raw_index: IndexedID<Inst2, AllocPolicy256> = IndexedID::allocate_from(&alloc, Inst2 { /* init */ });
let id = InstIndexID::from_backend(raw_index);
let _data: &Inst2 = id.deref_alloc(&alloc);
}
```
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.
- `backend = ptr | index` — choose pointer or index ID backend (default: `ptr`).
- `opaque` — make the inner backend ID field crate-visible instead of public, reducing accidental exposure.
## ID constraints
Library data structures rely on the `IPoliciedID` trait to describe "an ID tied to a particular object and allocator type." Raw `PtrID<E, P>`, `IndexedID<E, P>` and any `#[entity_id]` wrappers implement it, so you can use containers with any backend.
Note: Wrapper types intentionally do not expose allocation/free convenience methods; allocation stays at the raw layer (`allocate_ptr`, `allocate_index` or `IEntityAllocID::allocate_from`).
## Containers
Built on `IPoliciedID`, 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.