MTB::Entity: Address-stable, interior-mutable Slab allocator

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

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:

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:

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