#generational-arena #data-structures #arena #graph #tree #generational #entity

no-std components-arena

Simple library for creating complex domain-specific self-referential data structures

76 releases (49 stable)

4.2.2 Oct 20, 2024
4.1.4 Mar 13, 2024
4.1.1 Sep 23, 2023
3.5.1 Apr 21, 2023
0.9.0 Sep 15, 2020

#344 in Rust patterns

Download history 179/week @ 2024-09-08 217/week @ 2024-09-15 46/week @ 2024-09-22 43/week @ 2024-09-29 25/week @ 2024-10-06 26/week @ 2024-10-13 190/week @ 2024-10-20 21/week @ 2024-10-27 42/week @ 2024-11-03 14/week @ 2024-11-10 15/week @ 2024-11-17

97 downloads per month
Used in 4 crates

MIT/Apache

60KB
1K SLoC

maintenance: actively developed

components-arena

Strong-typed arena. Simple library for creating complex domain-specific self-referential data structures.

This arena does not use generations approach in a strict sense, but it uses some similar technique for avoiding the ABA effect.

Example: circular linked list

use std::mem::replace;
use macro_attr_2018::macro_attr;
use components_arena::{Id, Arena, Component};

macro_attr! {
    #[derive(Component!)]
    struct Node {
        next: Id<Node>,
        data: (),
    }
}

struct List {
    last: Option<Id<Node>>,
    nodes: Arena<Node>,
}

impl List {
    fn new() -> Self {
        List { last: None, nodes: Arena::new() }
    }

    fn push(&mut self, data: ()) -> Id<Node> {
        let id = self.nodes.insert(|id| (Node { next: id, data }, id));
        if let Some(last) = self.last {
            self.nodes[id].next = replace(&mut self.nodes[last].next, id);
        } else {
            self.last = Some(id);
        }
        id
    }
}

Dependencies

~0.7–2MB
~36K SLoC