8 stable releases

2.2.1 Feb 16, 2019
2.2.0 Jan 30, 2019
2.0.0 Nov 28, 2018
1.0.2 Nov 25, 2018

#10 in Memory management

Download history 169/week @ 2019-01-23 152/week @ 2019-01-30 241/week @ 2019-02-06 1025/week @ 2019-02-13 888/week @ 2019-02-20 980/week @ 2019-02-27 540/week @ 2019-03-06 598/week @ 2019-03-13 974/week @ 2019-03-20 695/week @ 2019-03-27 455/week @ 2019-04-03 1031/week @ 2019-04-10 558/week @ 2019-04-17 861/week @ 2019-04-24 954/week @ 2019-05-01

2,193 downloads per month
Used in 8 crates (2 directly)

MIT/Apache

29KB
607 lines

id-arena

Travis CI Build Status

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

Dependencies