MTB::Entity: An address-stable, interior-mutable Slab allocator

中文版请见: 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:

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:

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

use mtb_entity_slab::entity_allocatable;

#[entity_allocatable]
struct A;

Expands to roughly:

impl IEntityAllocatable for A {
    type AllocatePolicyT = EntityAllocPolicy256<A>;
    type PtrID = PtrID<A>;
}

Specify a different policy

#[entity_allocatable(policy = Policy512)]
struct B;

or equivalently:

#[entity_allocatable(policy = 512)]
struct B;

Generate a transparent wrapper type

#[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

#[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

// 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:

#[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:

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.

mtb-entity-slab 0.1.3