mtb-entity-slab 0.1.2

# 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};

#[derive(Debug, Clone, PartialEq, Eq)]
struct Inst {
    pub opcode: u32,
    pub operands: [u64; 4],
    pub heap_data: String,
}
/// Not every type can be stored in this allocator. You need to implement the
/// `IEntityAllocatable` trait for your type.
impl IEntityAllocatable for Inst {
    type AllocatePolicyT = EntityAllocPolicy256<Self>;

    /// You should implement your own pointer ID wrapper.
    type PtrID = PtrID<Inst>;
}

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.