indextree

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.

Minimum Supported Rust Version (MSRV)

The current MSRV is 1.85.0.

Features

Feature	Default	Description
std	yes	Standard library support. Disable for no_std (requires alloc).
macros	yes	tree! macro for declarative tree construction.
serde	no	Serde serialization and deserialization.
par_iter	no	Parallel iteration via rayon.

The legacy feature name deser is still accepted as an alias for serde.

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 b to a
a.append(b, arena);
assert_eq!(b.ancestors(arena).count(), 2);

Building trees with the tree! macro

The optional macros feature (enabled by default) provides a tree! macro for declarative tree construction:

use indextree::{Arena, macros::tree};

let arena = &mut Arena::new();
let root = tree!(arena, "root" => {
    "child_1" => {
        "grandchild_1",
        "grandchild_2",
    },
    "child_2",
    "child_3",
});

assert_eq!(root.child_count(arena), 3);
assert_eq!(root.descendants(arena).count(), 6);

Building a file system tree

use indextree::Arena;

let arena = &mut Arena::new();
let root = arena.new_node("/");
let etc = root.append_value("etc/", arena);
let usr = root.append_value("usr/", arena);

etc.append_value("hosts", arena);
etc.append_value("resolv.conf", arena);

let bin = usr.append_value("bin/", arena);
bin.append_value("rustc", arena);

// Traverse and collect paths
let descendants: Vec<_> = root
    .descendants(arena)
    .map(|id| *arena[id].get())
    .collect();
assert_eq!(
    descendants,
    vec!["/", "etc/", "hosts", "resolv.conf", "usr/", "bin/", "rustc"]
);

Parallel iteration

With the par_iter feature, trees can be traversed in parallel using rayon:

use indextree::Arena;
use rayon::prelude::*;

let arena = &mut Arena::new();
let root = arena.new_node(0);
for i in 1..=1000 {
    root.append_value(i, arena);
}

let sum: i64 = arena.par_iter().map(|node| *node.get()).sum();
assert_eq!(sum, 500500);

no_std usage

Disable default features and the crate works in no_std environments (requires alloc):

[dependencies]
indextree = { version = "4", default-features = false }