Struct vec_arena::Arena

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

An object arena.

Arena<T> holds an array of slots for storing objects. Every slot is always in one of two states: occupied or vacant.

Essentially, this is equivalent to Vec<Option<T>>.

Insert and remove

When inserting a new object into arena, a vacant slot is found and then the object is placed into the slot. If there are no vacant slots, the array is reallocated with bigger capacity. The cost of insertion is amortized O(1).

When removing an object, the slot containing it is marked as vacant and the object is returned. The cost of removal is O(1).

use vec_arena::Arena;

let mut arena = Arena::new();
let a = arena.insert(10);
let b = arena.insert(20);

assert_eq!(a, 0); // 10 was placed at index 0
assert_eq!(b, 1); // 20 was placed at index 1

assert_eq!(arena.remove(a), Some(10));
assert_eq!(arena.get(a), None); // slot at index 0 is now vacant

assert_eq!(arena.insert(30), 0); // slot at index 0 is reused

Indexing

You can also access objects in an arena by index, just like you would in a Vec. However, accessing a vacant slot by index or using an out-of-bounds index will result in panic.

use vec_arena::Arena;

let mut arena = Arena::new();
let a = arena.insert(10);
let b = arena.insert(20);

assert_eq!(arena[a], 10);
assert_eq!(arena[b], 20);

arena[a] += arena[b];
assert_eq!(arena[a], 30);

To access slots without fear of panicking, use get and get_mut, which return Options.

Methods

impl<T> Arena<T>

fn new() -> Self

Constructs a new, empty arena.

The arena will not allocate until objects are inserted into it.

Examples

use vec_arena::Arena;

let mut arena: Arena<i32> = Arena::new();

fn with_capacity(cap: usize) -> Self

Constructs a new, empty arena with the specified capacity (number of slots).

The arena will be able to hold exactly capacity objects without reallocating. If capacity is 0, the arena will not allocate.

Examples

use vec_arena::Arena;

let mut arena = Arena::with_capacity(10);

assert_eq!(arena.len(), 0);
assert_eq!(arena.capacity(), 10);

// These inserts are done without reallocating...
for i in 0..10 {
    arena.insert(i);
}
assert_eq!(arena.capacity(), 10);

// ... but this one will reallocate.
arena.insert(11);
assert!(arena.capacity() > 10);

fn capacity(&self) -> usize

Returns the number of slots in the arena.

Examples

use vec_arena::Arena;

let arena: Arena<i32> = Arena::with_capacity(10);
assert_eq!(arena.capacity(), 10);

fn len(&self) -> usize

Returns the number of occupied slots in the arena.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
assert_eq!(arena.len(), 0);

for i in 0..10 {
    arena.insert(());
    assert_eq!(arena.len(), i + 1);
}

fn is_empty(&self) -> bool

Returns true if all slots are vacant.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
assert!(arena.is_empty());

arena.insert(1);
assert!(!arena.is_empty());

fn insert(&mut self, object: T) -> usize

Inserts an object into the arena and returns the slot index it was stored in. The arena will reallocate if it's full.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();

let a = arena.insert(1);
let b = arena.insert(2);
assert!(a != b);

fn remove(&mut self, index: usize) -> Option<T>

Removes the object stored at index from the arena and returns it.

None is returned in case the slot is vacant, or index is out of bounds.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
let a = arena.insert("hello");

assert_eq!(arena.len(), 1);
assert_eq!(arena.remove(a), Some("hello"));

assert_eq!(arena.len(), 0);
assert_eq!(arena.remove(a), None);

fn clear(&mut self)

Clears the arena, removing and dropping all objects it holds. Keeps the allocated memory for reuse.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
for i in 0..10 {
    arena.insert(i);
}

assert_eq!(arena.len(), 10);
arena.clear();
assert_eq!(arena.len(), 0);

fn get(&self, index: usize) -> Option<&T>

Returns a reference to the object stored at index.

If index is out of bounds or the slot is vacant, None is returned.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
let index = arena.insert("hello");

assert_eq!(arena.get(index), Some(&"hello"));
arena.remove(index);
assert_eq!(arena.get(index), None);

fn get_mut(&mut self, index: usize) -> Option<&mut T>

Returns a mutable reference to the object stored at index.

If index is out of bounds or the slot is vacant, None is returned.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
let index = arena.insert(7);

assert_eq!(arena.get_mut(index), Some(&mut 7));
*arena.get_mut(index).unwrap() *= 10;
assert_eq!(arena.get_mut(index), Some(&mut 70));

unsafe fn get_unchecked(&self, index: usize) -> &T

Returns a reference to the object stored at index.

Safety

Behavior is undefined if index is out of bounds or the slot is vacant.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
let index = arena.insert("hello");

unsafe { assert_eq!(&*arena.get_unchecked(index), &"hello") }

unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T

Returns a mutable reference to the object stored at index.

Safety

Behavior is undefined if index is out of bounds or the slot is vacant.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
let index = arena.insert("hello");

unsafe { assert_eq!(&*arena.get_unchecked_mut(index), &"hello") }

fn swap(&mut self, a: usize, b: usize)

Swaps two objects in the arena.

The two indices are a and b.

Panics

Panics if any of the indices is out of bounds or any of the slots is vacant.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
let a = arena.insert(7);
let b = arena.insert(8);

arena.swap(a, b);
assert_eq!(arena.get(a), Some(&8));
assert_eq!(arena.get(b), Some(&7));

fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more objects to be inserted. The arena may reserve more space to avoid frequent reallocations.

Panics

Panics if the new capacity overflows usize.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
arena.insert("hello");

arena.reserve(10);
assert!(arena.capacity() >= 11);

fn reserve_exact(&mut self, additional: usize)

Reserves the minimum capacity for exactly additional more objects to be inserted.

Note that the allocator may give the arena more space than it requests.

Panics

Panics if the new capacity overflows usize.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
arena.insert("hello");

arena.reserve_exact(10);
assert!(arena.capacity() >= 11);

fn iter(&self) -> Iter<T>

Returns an iterator over occupied slots.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
arena.insert(1);
arena.insert(2);
arena.insert(4);

let mut iterator = arena.iter();
assert_eq!(iterator.next(), Some((0, &1)));
assert_eq!(iterator.next(), Some((1, &2)));
assert_eq!(iterator.next(), Some((2, &4)));

fn iter_mut(&mut self) -> IterMut<T>

Returns an iterator that returns mutable references to objects.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
arena.insert("zero".to_string());
arena.insert("one".to_string());
arena.insert("two".to_string());

for (index, object) in arena.iter_mut() {
    *object = index.to_string() + " " + object;
}

let mut iterator = arena.iter();
assert_eq!(iterator.next(), Some((0, &"0 zero".to_string())));
assert_eq!(iterator.next(), Some((1, &"1 one".to_string())));
assert_eq!(iterator.next(), Some((2, &"2 two".to_string())));

Trait Implementations

impl<T> Debug for Arena<T>

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

Formats the value using the given formatter.

impl<T> Index<usize> for Arena<T>

type Output = T

The returned type after indexing

fn index(&self, index: usize) -> &T

The method for the indexing (container[index]) operation

impl<T> IndexMut<usize> for Arena<T>

fn index_mut(&mut self, index: usize) -> &mut T

The method for the mutable indexing (container[index]) operation

impl<T> Default for Arena<T>

fn default() -> Self

Returns the "default value" for a type.

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

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> IntoIterator for Arena<T>

type Item = (usize, T)

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.