Struct Arena 

pub struct Arena<T> { /* private fields */ }

A generational arena of T.

Live values are stored packed, in two runs. The tail holds every slot from some index on, each one occupied, so its values are found by arithmetic; an arena that has only been appended to is all tail. The values before it are scattered: slots whose neighbours were dropped, found through a map from slot to position. An arena holds what is live and nothing for the slots it no longer uses, so cloning one costs what it holds, however many slots it has handed out.

Implementations

impl<T> Arena<T>

pub const fn new() -> Self

An empty arena.

pub fn with_capacity(capacity: usize) -> Self

An empty arena with room for capacity entries.

pub const fn len(&self) -> usize

Number of live entries.

pub const fn is_empty(&self) -> bool

Whether there are no live entries.

pub const fn scope(&self) -> u32

Which arena this is, for stamping keys that were rebuilt elsewhere.

UNSCOPED until the first insert.

pub const fn issued(&self, key: Key<T>) -> bool

Whether a key was issued by this arena.

Distinct from Arena::contains, which also asks whether the slot is still live. This asks only whether the key belongs here at all, which is the question a caller wants when reporting why a lookup failed.

pub fn next_index(&self) -> Option<u32>

The slot the next Arena::insert takes, at generation zero, when it takes a fresh one; None while a freed slot waits to be reused.

The precondition for extending the arena by offset, where a caller predicts the keys of entries it is about to append: the k-th insert from here lands at this index plus k.

pub fn key_at(&self, index: u32) -> Option<Key<T>>

The live key at slot index, if the slot holds a value.

pub fn insert(&mut self, value: T) -> Key<T>

Insert a value, returning its key.

The first insert is what fixes the arena’s identity, since Arena::new is const and cannot read a counter. That is safe because an arena with nothing in it has issued no keys to disagree with.

Panics

If the arena exceeds u32::MAX slots. A single model reaching four billion topological entities is a bug elsewhere, not a case to handle.

pub fn get(&self, key: Key<T>) -> Option<&T>

Borrow the value behind key, or None if the key is stale.

pub fn get_mut(&mut self, key: Key<T>) -> Option<&mut T>

Mutably borrow the value behind key, or None if the key is stale.

pub fn contains(&self, key: Key<T>) -> bool

Whether key resolves to a live entry.

pub fn remove(&mut self, key: Key<T>) -> Option<T>

Remove and return the value behind key, if it is live.

The slot’s generation is bumped, invalidating every outstanding copy of key, and a later insert reuses the slot.

pub fn retain(&mut self, keep: impl FnMut(Key<T>, &T) -> bool)

Keep the entries keep answers true for and drop the rest.

Every kept key still resolves to its value. A dropped key fails to resolve, and its slot is never handed out again, so no later entry answers to it. What is dropped stops costing memory: the arena holds the kept values, packed.

pub fn iter(&self) -> impl Iterator<Item = (Key<T>, &T)>

Iterate over live (key, &value) pairs, in slot order.

pub fn iter_mut(&mut self) -> impl Iterator<Item = (Key<T>, &mut T)>

Iterate over live (key, &mut value) pairs, in slot order.

pub fn values(&self) -> impl Iterator<Item = &T>

Iterate over live values.

pub fn into_values(self) -> impl Iterator<Item = T>

Consume the arena, yielding its live values in index order.

For appending one arena’s contents onto another: the receiving arena hands out its own keys, so the values travel bare.

pub fn is_dense(&self) -> bool

Whether the arena has only ever been appended to: every slot occupied, every generation zero.

When this holds, Arena::len is also the next index Arena::insert will hand out.

pub fn clear(&mut self)

Remove every entry. Existing keys go stale, and their slots are not handed out again.

Trait Implementations

impl<T: Clone> Clone for Arena<T>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for Arena<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for Arena<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> Index<Key<T>> for Arena<T>

fn index(&self, key: Key<T>) -> &T

Panics

If the key is stale. Use Arena::get where that is a possibility.

type Output = T

The returned type after indexing.

impl<T> IndexMut<Key<T>> for Arena<T>

fn index_mut(&mut self, key: Key<T>) -> &mut T

Panics

If the key is stale. Use Arena::get_mut where that is a possibility.