Crate id_arena

A simple, id-based arena.

Id-based

Allocate objects and get an identifier for that object back, not a reference to the allocated object. Given an id, you can get a shared or exclusive reference to the allocated object from the arena. This id-based approach is useful for constructing mutable graph data structures.

If you want allocation to return a reference, consider the typed-arena crate instead.

No Deletion

This arena does not support deletion, which makes its implementation simple and allocation fast. If you want deletion, you need a way to solve the ABA problem. Consider using the generational-arena crate instead.

Homogeneous

This crate's arenas can only contain objects of a single type T. If you need an arena of objects with heterogeneous types, consider another crate.

#![no_std] Support

Requires the alloc nightly feature. Disable the on-by-default "std" feature:

[dependencies.id-arena]
version = "2"
default-features = false

rayon Support

If the rayon feature of this crate is activated:

[dependencies]
id-arena = { version = "2", features = ["rayon"] }

then you can use rayon's support for parallel iteration. The Arena type will have a par_iter family of methods where appropriate.

Example

use id_arena::{Arena, Id};

type AstNodeId = Id<AstNode>;

#[derive(Debug, Eq, PartialEq)]
pub enum AstNode {
    Const(i64),
    Var(String),
    Add {
        lhs: AstNodeId,
        rhs: AstNodeId,
    },
    Sub {
        lhs: AstNodeId,
        rhs: AstNodeId,
    },
    Mul {
        lhs: AstNodeId,
        rhs: AstNodeId,
    },
    Div {
        lhs: AstNodeId,
        rhs: AstNodeId,
    },
}

let mut ast_nodes = Arena::<AstNode>::new();

// Create the AST for `a * (b + 3)`.
let three = ast_nodes.alloc(AstNode::Const(3));
let b = ast_nodes.alloc(AstNode::Var("b".into()));
let b_plus_three = ast_nodes.alloc(AstNode::Add {
    lhs: b,
    rhs: three,
});
let a = ast_nodes.alloc(AstNode::Var("a".into()));
let a_times_b_plus_three = ast_nodes.alloc(AstNode::Mul {
    lhs: a,
    rhs: b_plus_three,
});

// Can use indexing to access allocated nodes.
assert_eq!(ast_nodes[three], AstNode::Const(3));

Structs

Arena	An arena of objects of type T.
DefaultArenaBehavior	The default ArenaBehavior implementation.
Id	An identifier for an object allocated within an arena.
IntoIter	An iterator over (Id, T) pairs in an arena.
IntoParIter	A parallel iterator over items in an arena.
Iter	An iterator over (Id, &T) pairs in an arena.
IterMut	An iterator over (Id, &mut T) pairs in an arena.
ParIter	A parallel iterator over shared references in an arena.
ParIterMut	A parallel iterator over mutable references in an arena.

Traits

ArenaBehavior

A trait representing the implementation behavior of an arena and how identifiers are represented.