Rust and Data Structures

Arena Allocation Concepts

Arena allocation (also known as region-based or slab allocation) groups the allocation of many nodes into a single backing container—either a contiguous Vec indexed by handles or a bump-allocated memory chunk—and ties their lifetimes together. In Rust, arenas solve two problems simultaneously: they eliminate thousands of individual heap allocations and allow cyclic or bidirectional graph/tree links (parent, prev, next) without Rc<RefCell<T>> or unsafe code!

Individual `Box` / `Rc` Allocations (Scattered Across Heap):
  [ Node 0 ] ---> (RAM miss) ---> [ Node 1 ] ---> (RAM miss) ---> [ Node 2 ]

Contiguous Index / Generational Arena (`Vec<Slot<T>>`):
  +-----------------------------------------------------------------------+
  | Slot 0 (gen=1) | Slot 1 (gen=1) | Slot 2 (gen=3, Free) | Slot 3 (gen=1)|
  +-----------------------------------------------------------------------+
  Referenced by lightweight 8-byte `ArenaKey { index: u32, generation: u32 }`!

Three Types of Arenas in Rust

Arena Pattern How References Are Represented Supports Individual Deletion? Ecosystem Crates
1. Simple Vec<T> Index Arena struct Id(u32) index into Vec<T> Append-only (or tombstone Option<T>) Built-in Vec<T>, la-arena
2. Generational Arena (SlotMap) Key { index: u32, generation: u32 } Yes ($O(1)$ removal + prevents ABA stale-key bugs!) slotmap, thunderdome, slab
3. Lifetime Bump Arena (&'arena T) Real Rust references &'arena T / &'arena mut T Freed all at once when the Arena is dropped bumpalo, typed-arena

Solving the Stale-Index ("ABA") Problem with a Generational Arena

In a simple Vec<Option<T>> slab where freed indices are reused by a free list, if you delete the item at index 2 and insert a new item that reuses index 2, an old stale Id(2) handle sitting elsewhere in the program will accidentally access the wrong new object (the ABA problem)!

A generational arena attaches a monotonically increasing generation: u32 counter to every slot in the vector and to every returned HandleId. When a slot is freed, its generation counter increments—so any stale HandleId with the old generation is rejected in $O(1)$ time with None!

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct ArenaKey {
    index: u32,
    generation: u32,
}

enum Slot<T> {
    Occupied { generation: u32, value: T },
    Vacant { generation: u32, next_free: Option<u32> },
}

pub struct GenerationalArena<T> {
    slots: Vec<Slot<T>>,
    free_head: Option<u32>,
    len: usize,
}

impl<T> GenerationalArena<T> {
    pub const fn new() -> Self {
        Self {
            slots: Vec::new(),
            free_head: None,
            len: 0,
        }
    }

    pub fn insert(&mut self, value: T) -> ArenaKey {
        self.len += 1;
        if let Some(idx) = self.free_head {
            let slot = &mut self.slots[idx as usize];
            match *slot {
                Slot::Vacant { generation, next_free } => {
                    self.free_head = next_free;
                    *slot = Slot::Occupied { generation, value };
                    ArenaKey { index: idx, generation }
                }
                Slot::Occupied { .. } => unreachable!("free list pointed to occupied slot"),
            }
        } else {
            let index = self.slots.len() as u32;
            let generation = 1;
            self.slots.push(Slot::Occupied { generation, value });
            ArenaKey { index, generation }
        }
    }

    pub fn get(&self, key: ArenaKey) -> Option<&T> {
        match self.slots.get(key.index as usize)? {
            Slot::Occupied { generation, value } if *generation == key.generation => Some(value),
            _ => None, // Slot is either vacant OR was reused by a newer generation!
        }
    }

    pub fn remove(&mut self, key: ArenaKey) -> Option<T> {
        let slot = self.slots.get_mut(key.index as usize)?;
        match slot {
            Slot::Occupied { generation, .. } if *generation == key.generation => {
                let next_gen = generation.wrapping_add(1);
                let old = std::mem::replace(
                    slot,
                    Slot::Vacant {
                        generation: next_gen,
                        next_free: self.free_head,
                    },
                );
                self.free_head = Some(key.index);
                self.len -= 1;
                match old {
                    Slot::Occupied { value, .. } => Some(value),
                    _ => unreachable!(),
                }
            }
            _ => None,
        }
    }
}

fn main() {
    let mut arena = GenerationalArena::new();

    let key_old = arena.insert("Player_1");
    assert_eq!(arena.get(key_old), Some(&"Player_1"));

    // Remove "Player_1" (slot 0's generation increments from 1 -> 2):
    assert_eq!(arena.remove(key_old), Some("Player_1"));

    // Insert "Player_2", which reuses slot 0 at generation 2:
    let key_new = arena.insert("Player_2");
    assert_eq!(key_old.index, key_new.index);
    assert_ne!(key_old.generation, key_new.generation);

    // Stale `key_old` safely returns `None` instead of reading "Player_2"!
    assert_eq!(arena.get(key_old), None);
    assert_eq!(arena.get(key_new), Some(&"Player_2"));

    println!(
        "Stale key rejected ({:?}), new key resolved: {:?}",
        arena.get(key_old),
        arena.get(key_new)
    );
}

Stale key rejected (None), new key resolved: Some("Player_2")