Struct Arena 

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

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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.

Implementations

impl<T> Arena<T>

pub fn new() -> Self

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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();

Examples found in repository

examples/splay-tree.rs (line 44)

    fn new() -> Splay<T> {
        Splay {
            arena: Arena::new(),
            root: NULL,
        }
    }

examples/linked-list.rs (line 37)

    fn new() -> Self {
        List {
            arena: Arena::new(),
            head: NULL,
            tail: NULL,
        }
    }

pub fn with_capacity(cap: usize) -> Self

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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

The arena will be able to hold exactly cap objects without reallocating. If cap 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);

pub fn capacity(&self) -> usize

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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);

pub fn len(&self) -> usize

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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);
}

Examples found in repository

examples/linked-list.rs (line 45)

    fn len(&self) -> usize {
        self.arena.len()
    }

pub fn is_empty(&self) -> bool

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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());

pub fn next_vacant(&self) -> usize

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

Returns the index of the slot that next insert will use if no mutating calls take place in between.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();

let a = arena.next_vacant();
let b = arena.insert(1);
assert_eq!(a, b);
let c = arena.next_vacant();
let d = arena.insert(2);
assert_eq!(c, d);

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

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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);

Examples found in repository

examples/linked-list.rs (lines 60-64)

    fn push_back(&mut self, value: T) -> usize {
        let node = self.arena.insert(Node {
            prev: NULL,
            next: NULL,
            value: value,
        });

        let tail = self.tail;
        self.link(tail, node);

        self.tail = node;
        if self.head == NULL {
            self.head = node;
        }
        node
    }

examples/splay-tree.rs (line 132)

    fn insert(&mut self, value: T) {
        // Variables:
        // - `n` is the new node
        // - `p` will be it's parent
        // - `c` is the present child of `p`

        let n = self.arena.insert(Node::new(value));

        if self.root == NULL {
            self.root = n;
        } else {
            let mut p = self.root;
            loop {
                // Decide whether to go left or right.
                let dir = if self.arena[n].value < self.arena[p].value {
                    0
                } else {
                    1
                };
                let c = self.arena[p].children[dir];

                if c == NULL {
                    self.link(p, n, dir);
                    self.splay(n);
                    break;
                }
                p = c;
            }
        }
    }

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

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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

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

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);

Examples found in repository

examples/linked-list.rs (line 78)

    fn pop_front(&mut self) -> T {
        let node = self.arena.remove(self.head).unwrap();

        self.link(NULL, node.next);
        self.head = node.next;
        if node.next == NULL {
            self.tail = NULL;
        }
        node.value
    }

    /// Removes the element specified by `index`.
    fn remove(&mut self, index: usize) -> T {
        let node = self.arena.remove(index).unwrap();

        self.link(node.prev, node.next);
        if self.head == index {
            self.head = node.next;
        }
        if self.tail == index {
            self.tail = node.prev;
        }

        node.value
    }

pub fn retain<F>(&mut self, f: F)

where F: FnMut(usize, &mut T) -> bool,

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

Retains objects for which the closure returns true.

All other objects will be removed from the arena.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();

let a = arena.insert(0);
let b = arena.insert(1);
let c = arena.insert(2);

arena.retain(|k, v| k == a || *v == 1);

assert!(arena.get(a).is_some());
assert!(arena.get(b).is_some());
assert!(arena.get(c).is_none());

pub fn clear(&mut self)

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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);

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

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

Returns a reference to the object stored at index.

If the slot is vacant or index is out of bounds, None will be 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);

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

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

Returns a mutable reference to the object stored at index.

If the slot is vacant or index is out of bounds, None will be 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));

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

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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));

pub fn reserve(&mut self, additional: usize)

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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);

pub fn reserve_exact(&mut self, additional: usize)

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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);

pub fn iter(&self) -> Iter<'_, T>

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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)));

pub fn iter_mut(&mut self) -> IterMut<'_, T>

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

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())));

pub fn shrink_to_fit(&mut self)

👎Deprecated since 1.2.0: This crate is now deprecated in favor of slab.

Shrinks the capacity of the arena as much as possible.

It will drop down as close as possible to the length but the allocator may still inform the arena that there is space for a few more elements.

Examples

use vec_arena::Arena;

let mut arena = Arena::with_capacity(10);
arena.insert("first".to_string());
arena.insert("second".to_string());
arena.insert("third".to_string());
assert_eq!(arena.capacity(), 10);
arena.shrink_to_fit();
assert!(arena.capacity() >= 3);

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 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> FromIterator<T> for Arena<T>

fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> Arena<T>

Creates a value from an iterator.

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

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

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

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

Performs the mutable indexing (container[index]) operation.

impl<'a, T> IntoIterator for &'a Arena<T>

type Item = (usize, &'a T)

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut Arena<T>

type Item = (usize, &'a mut T)

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

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.