mtb-entity-slab 0.1.1

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

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.