third_party/rust/id-arena/README.md

   1 # `id-arena`
   2
   3 [![](https://img.shields.io/crates/v/id-arena.svg)](https://crates.io/crates/id-arena)
   4 [![](https://img.shields.io/crates/d/id-arena.svg)](https://crates.io/crates/id-arena)
   5 [![Travis CI Build Status](https://travis-ci.org/fitzgen/id-arena.svg?branch=master)](https://travis-ci.org/fitzgen/id-arena)
   6
   7 A simple, id-based arena.
   8
   9 ### Id-based
  10
  11 Allocate objects and get an identifier for that object back, *not* a
  12 reference to the allocated object. Given an id, you can get a shared or
  13 exclusive reference to the allocated object from the arena. This id-based
  14 approach is useful for constructing mutable graph data structures.
  15
  16 If you want allocation to return a reference, consider [the `typed-arena`
  17 crate](https://github.com/SimonSapin/rust-typed-arena/) instead.
  18
  19 ### No Deletion
  20
  21 This arena does not support deletion, which makes its implementation simple
  22 and allocation fast. If you want deletion, you need a way to solve the ABA
  23 problem. Consider using [the `generational-arena`
  24 crate](https://github.com/fitzgen/generational-arena) instead.
  25
  26 ### Homogeneous
  27
  28 This crate's arenas can only contain objects of a single type `T`. If you
  29 need an arena of objects with heterogeneous types, consider another crate.
  30
  31 ### `#![no_std]` Support
  32
  33 Requires the `alloc` nightly feature. Disable the on-by-default `"std"` feature:
  34
  35 ```toml
  36 [dependencies.id-arena]
  37 version = "2"
  38 default-features = false
  39 ```
  40
  41 ### `rayon` Support
  42
  43 If the `rayon` feature of this crate is activated:
  44
  45 ```toml
  46 [dependencies]
  47 id-arena = { version = "2", features = ["rayon"] }
  48 ```
  49
  50 then you can use [`rayon`](https://crates.io/crates/rayon)'s support for
  51 parallel iteration. The `Arena` type will have a `par_iter` family of
  52 methods where appropriate.
  53
  54 ### Example
  55
  56 ```rust
  57 use id_arena::{Arena, Id};
  58
  59 type AstNodeId = Id<AstNode>;
  60
  61 #[derive(Debug, Eq, PartialEq)]
  62 pub enum AstNode {
  63     Const(i64),
  64     Var(String),
  65     Add {
  66         lhs: AstNodeId,
  67         rhs: AstNodeId,
  68     },
  69     Sub {
  70         lhs: AstNodeId,
  71         rhs: AstNodeId,
  72     },
  73     Mul {
  74         lhs: AstNodeId,
  75         rhs: AstNodeId,
  76     },
  77     Div {
  78         lhs: AstNodeId,
  79         rhs: AstNodeId,
  80     },
  81 }
  82
  83 let mut ast_nodes = Arena::<AstNode>::new();
  84
  85 // Create the AST for `a * (b + 3)`.
  86 let three = ast_nodes.alloc(AstNode::Const(3));
  87 let b = ast_nodes.alloc(AstNode::Var("b".into()));
  88 let b_plus_three = ast_nodes.alloc(AstNode::Add {
  89     lhs: b,
  90     rhs: three,
  91 });
  92 let a = ast_nodes.alloc(AstNode::Var("a".into()));
  93 let a_times_b_plus_three = ast_nodes.alloc(AstNode::Mul {
  94     lhs: a,
  95     rhs: b_plus_three,
  96 });
  97
  98 // Can use indexing to access allocated nodes.
  99 assert_eq!(ast_nodes[three], AstNode::Const(3));
 100 ```