8 stable releases

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

#11 in Memory management

Download history 20/week @ 2018-11-10 46/week @ 2018-11-17 65/week @ 2018-11-24 71/week @ 2018-12-01 70/week @ 2018-12-08 207/week @ 2018-12-15 157/week @ 2018-12-22 207/week @ 2018-12-29 83/week @ 2019-01-05 151/week @ 2019-01-12 123/week @ 2019-01-19 149/week @ 2019-01-26 78/week @ 2019-02-02 818/week @ 2019-02-09

751 downloads per month
Used in 6 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