slab

slab is a small, dependency-free Rust crate that provides pre-allocated storage for a single, uniform data type. Rather than allocating and freeing memory for each individual value, Slab keeps a Vec of slots that are either occupied or vacant, reusing freed slots via an intrusive free list threaded through the vacant entries themselves. Storing a value returns an integer key that stays valid until the value is removed, so lookups become plain indexed access instead of pointer chasing or hashing.

This makes slab a natural fit anywhere code needs to hand out a lightweight, stable handle to a value it owns — connection tables, task/waker registries, entity or resource pools, and similar “give me an ID, give me the value back” patterns. It is #![no_std]-compatible (with an optional std feature) and has an optional serde feature for serializing the collection as key-value pairs, making it usable in embedded and constrained environments as well as ordinary applications.

The crate is maintained under the tokio-rs organization and is a foundational dependency of Tokio’s own internals (and other async runtimes like mio), which has made its correctness and performance characteristics unusually battle-tested for a library of its size.

What You Get

• Stable integer keys - insert returns a usize key that indexes directly into the underlying storage and remains valid until that specific value is removed.
• O(1) amortized insert/remove/get - slot reuse via an intrusive free list avoids the reallocation and fragmentation costs of general-purpose allocation.
• vacant_entry() / VacantEntry - reserve a key before the value exists, useful for self-referential or cyclic structures where a value needs to know its own key.
• no_std support - builds without the standard library via the alloc crate, with std enabled by default and toggleable via Cargo features.
• Optional serde support - a serde feature flag adds Serialize/Deserialize implementations that round-trip the collection as key-value pairs.
• Bulk operations - retain, compact, clear, drain, and FromIterator<(usize, T)> (via an internal Builder) for reshaping or rebuilding the slab efficiently.

Common Use Cases

• Connection/session tables - servers hand out a usize connection ID on accept and use it as a stable handle into per-connection state stored in a Slab.
• Task or waker registries in async runtimes - schedulers store pending tasks or wakers in a slab and reference them by index instead of heap pointers, which is exactly how Tokio and mio use it internally.
• Entity/resource pools in games and simulations - entities are inserted once and referenced by a lightweight integer ID for the rest of their lifetime, with IDs recycled as entities are removed.
• Graph and arena-style data structures - nodes are stored in a slab and reference each other by index instead of using Rc/RefCell or unsafe pointers, sidestepping Rust’s borrow-checker friction for cyclic structures.

Under The Hood

Architecture Slab<T> is backed by a single Vec<Entry<T>> (src/lib.rs) where Entry is either Occupied(T) or Vacant(next_index); vacant slots form an intrusive singly-linked free list threaded through the Vec itself, so no separate free-list allocation is needed. insert/remove manipulate this list in O(1) amortized time, and VacantEntry lets a caller reserve a key before constructing the value, which is essential for self-referential structures. A dedicated Builder (src/builder.rs) reconstructs a valid slab (including the free list) from an arbitrary, possibly out-of-order stream of (key, value) pairs, falling back to recreate_vacant_list() when the input isn’t already in a consistent order — this backs both FromIterator and the optional serde deserializer. Iterator types (Iter, IterMut, IntoIter, Drain) are thin wrappers over the entries Vec that skip vacant slots and implement DoubleEndedIterator, ExactSizeIterator, and FusedIterator. The crate is intentionally a single flat module (lib.rs at ~1,650 lines, plus the two small helper modules) — appropriate for a data structure whose entire contract is the Slab type itself, with no internal layering needed.

Tech Stack Pure Rust, edition 2018, with an MSRV pinned at 1.51 and enforced in CI. The crate has zero mandatory dependencies; an optional serde dependency (^1.0.95, default-features = false, features = ["alloc"]) is gated behind a serde feature so it doesn’t bloat consumers who don’t need it. It is #![no_std] by default at the crate level, using extern crate alloc when the std feature (on by default) is disabled — CI verifies this by building for the thumbv7m-none-eabi embedded target. Distribution is via crates.io; there is no build tooling beyond Cargo itself.

Code Quality tests/slab.rs is a substantial 782-line test suite exercising insert/remove/get/get_disjoint_mut/iteration/retain/compact/vacant_entry behavior, plus a separate tests/serde.rs for the optional serde round-trip. GitHub Actions CI runs cargo hack across the full feature powerset, an MSRV-pinned build, cargo clippy --all-features and cargo fmt --check with RUSTFLAGS=-Dwarnings (zero lint tolerance), a docs build with -Dwarnings, and — notably for a crate that uses unsafe internally (MaybeUninit-based slot access and the const-generic get_disjoint_mut multiple-mutable-borrow API) — a scheduled Miri run under -Zmiri-strict-provenance -Zmiri-symbolic-alignment-check, which is a strong correctness signal for low-level unsafe code. Naming and structure are idiomatic Rust throughout.

API Design The public API is small and consistent: insert/try_remove/remove/get/get_mut/contains/len/is_empty mirror the shape of a Vec/HashMap hybrid, so the learning curve for anyone familiar with Rust collections is minimal. vacant_entry() and get_disjoint_mut::<N>() are the two more advanced entry points, and both are thoroughly documented with runnable doctest examples in lib.rs’s module-level docs, which double as the crate’s primary usage guide (there’s no separate docs/ or examples/ directory). The crate deliberately does not implement Index-with-panicking-only semantics for every accessor — get/try_remove return Option for fallible use, while Index/remove panic, giving callers an explicit choice.