364: Slab Pattern for Indexed Storage

Difficulty: 3 Level: Advanced Pre-allocated pool with stable integer indices — insert returns an index, not a reference.

The Problem This Solves

Sometimes you want a collection of objects where each object has a stable, reusable identity even as items come and go. A game engine with entities being created and destroyed. A network server tracking open connections. A graph implementation where nodes need stable IDs. You could use `Vec` with a "tombstone" marker for deleted slots, but you'd need to manage free-list recycling yourself. You could use `HashMap<usize, T>`, but that's heap allocation per entry plus hash overhead. You could use `Box<T>` handles, but then the borrow checker makes passing handles around painful. The `slab` crate gives you a pre-allocated pool that returns integer keys on insert, recycles slots on remove, and guarantees `O(1)` insert, remove, and lookup. No heap allocation per element after the initial slab creation. No fragmentation.

The Intuition

A slab maintains a `Vec<Slot<T>>` where each slot is either `Occupied(T)` or `Vacant(next_free_index)`. The vacant slots form a linked list via their stored indices — the "free list." Insert finds the next free slot (or grows the Vec), puts your value in, and returns the slot index. Remove marks the slot vacant and prepends it to the free list. Lookup is just `vec[index]`. The key property: indices are stable. When you remove entry 5, entry 6's index doesn't change. This makes slabs ideal for graph nodes, entity IDs, and any structure where external code holds references by integer key.

How It Works in Rust

use slab::Slab;

let mut slab = Slab::new();

// Insert returns a stable key
let alice = slab.insert("Alice");   // key: 0
let bob   = slab.insert("Bob");     // key: 1
let carol = slab.insert("Carol");   // key: 2

// O(1) lookup by key
println!("{}", slab[bob]);  // "Bob"

// Remove — key 1 is now free
slab.remove(bob);

// Next insert reuses key 1
let dave = slab.insert("Dave");
assert_eq!(dave, 1);

// Iterate occupied entries
for (key, name) in &slab {
 println!("{key}: {name}");
}

What This Unlocks

Entity-component systems — entities are slab keys; components stored in parallel slabs indexed by same key.
Connection pools — each connection gets a stable ID; closed connections' slots are recycled.
Graph representations — nodes stored in slabs, edges stored as `(usize, usize)` pairs — no lifetime juggling.

Key Differences

Concept	OCaml	Rust
Object pool	Manual with array + free list	`slab::Slab<T>` — handles free list automatically
Stable identity	Integer index into array	`slab.insert(v)` returns `usize` key
Slot recycling	Manual	Automatic via internal free list
Access	`array.(index)`	`slab[key]` or `slab.get(key)`

struct Slab<T> {
    entries: Vec<Option<T>>,
    free: Vec<usize>,
}

impl<T> Slab<T> {
    fn new() -> Self { Self { entries: Vec::new(), free: Vec::new() } }

    fn with_capacity(cap: usize) -> Self {
        Self { entries: Vec::with_capacity(cap), free: Vec::new() }
    }

    fn insert(&mut self, val: T) -> usize {
        if let Some(key) = self.free.pop() {
            self.entries[key] = Some(val);
            key
        } else {
            let key = self.entries.len();
            self.entries.push(Some(val));
            key
        }
    }

    fn get(&self, key: usize) -> Option<&T> {
        self.entries.get(key)?.as_ref()
    }

    fn get_mut(&mut self, key: usize) -> Option<&mut T> {
        self.entries.get_mut(key)?.as_mut()
    }

    fn remove(&mut self, key: usize) -> Option<T> {
        let slot = self.entries.get_mut(key)?;
        let val = slot.take()?;
        self.free.push(key);
        Some(val)
    }

    fn len(&self) -> usize { self.entries.iter().filter(|e| e.is_some()).count() }
    fn contains(&self, key: usize) -> bool { self.get(key).is_some() }
    fn iter(&self) -> impl Iterator<Item=(usize, &T)> {
        self.entries.iter().enumerate().filter_map(|(i,e)| e.as_ref().map(|v|(i,v)))
    }
}

fn main() {
    let mut slab: Slab<String> = Slab::new();
    let k1 = slab.insert("hello".into());
    let k2 = slab.insert("world".into());
    let k3 = slab.insert("foo".into());
    println!("k1={k1}: {:?}", slab.get(k1));
    println!("k2={k2}: {:?}", slab.get(k2));
    slab.remove(k1);
    let k4 = slab.insert("reused".into());
    println!("k4={k4} (reused slot from k1={k1}): {:?}", slab.get(k4));
    println!("Active: {}", slab.len());
    for (k,v) in slab.iter() { println!("  [{k}] = {v}"); }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test] fn insert_get() {
        let mut s: Slab<i32> = Slab::new();
        let k = s.insert(42);
        assert_eq!(s.get(k), Some(&42));
    }
    #[test] fn remove_and_reuse() {
        let mut s: Slab<i32> = Slab::new();
        let k1 = s.insert(1); s.insert(2); s.remove(k1);
        let k3 = s.insert(3);
        assert_eq!(k3, k1); // slot reused
    }
    #[test] fn stable_keys() {
        let mut s: Slab<String> = Slab::new();
        let k = s.insert("stable".into());
        for _ in 0..100 { s.insert("filler".into()); }
        assert_eq!(s.get(k).unwrap(), "stable");
    }
}

(* OCaml: slab-like pool with indices *)

type 'a slab = {
  mutable data: 'a option array;
  mutable free: int list;
  mutable next_id: int;
}

let make cap = { data=Array.make cap None; free=[]; next_id=0 }

let insert s v =
  match s.free with
  | i::rest -> s.data.(i) <- Some v; s.free <- rest; i
  | [] ->
    let i = s.next_id in
    s.data.(i) <- Some v; s.next_id <- i+1; i

let get s i = s.data.(i)
let remove s i = s.data.(i) <- None; s.free <- i :: s.free

let () =
  let s = make 8 in
  let k1 = insert s "hello" in
  let k2 = insert s "world" in
  Printf.printf "k1=%d: %s\n" k1 (Option.get (get s k1));
  remove s k1;
  let k3 = insert s "reused" in
  Printf.printf "k3=%d (reused slot): %s\n" k3 (Option.get (get s k3))