#arena #tree #index #reference-counting #trie #tree-traversal

no-std indextree

Arena based tree structure by using indices instead of reference counted pointers

22 stable releases (4 major)

4.6.1 Apr 3, 2024
4.6.0 Mar 9, 2023
4.5.0 Sep 16, 2022
4.4.0 Mar 8, 2022
0.1.1 Dec 22, 2016

#43 in Data structures

Download history 8276/week @ 2024-04-01 9490/week @ 2024-04-08 9580/week @ 2024-04-15 9271/week @ 2024-04-22 5254/week @ 2024-04-29 8583/week @ 2024-05-06 7490/week @ 2024-05-13 7088/week @ 2024-05-20 6909/week @ 2024-05-27 7160/week @ 2024-06-03 6393/week @ 2024-06-10 7395/week @ 2024-06-17 7308/week @ 2024-06-24 7202/week @ 2024-07-01 7847/week @ 2024-07-08 7500/week @ 2024-07-15

30,235 downloads per month
Used in 99 crates (35 directly)

MIT license

115KB
1.5K SLoC

indextree

GitHub Actions Coverage Dependency Status Doc indextree License MIT Crates.io doc.rs

Arena based tree structure with multithreading support

This arena tree structure is using just a single Vec and numerical identifiers (indices in the vector) instead of reference counted pointers. This means there is no RefCell and mutability is handled in a way much more idiomatic to Rust through unique (&mut) access to the arena. The tree can be sent or shared across threads like a Vec. This enables general multiprocessing support like parallel tree traversals.

Example usage

use indextree::Arena;

// Create a new arena
let arena = &mut Arena::new();

// Add some new nodes to the arena
let a = arena.new_node(1);
let b = arena.new_node(2);

// Append a to b
assert!(a.append(b, arena).is_ok());
assert_eq!(b.ancestors(arena).into_iter().count(), 2);

Benchmarks

https://github.com/mooman219/generational_arena_bench

Dependencies

~0–430KB