#tree #arena #index #indextree #generational

generational-indextree

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

9 stable releases

1.1.4 Jan 15, 2022
1.1.3 Jan 10, 2022
1.1.2 Dec 2, 2020
1.1.1 Jun 20, 2020
1.0.2 Apr 6, 2020

#227 in Data structures

Download history 11/week @ 2022-12-06 17/week @ 2022-12-13 9/week @ 2022-12-20 28/week @ 2022-12-27 22/week @ 2023-01-03 18/week @ 2023-01-10 16/week @ 2023-01-17 27/week @ 2023-01-24 22/week @ 2023-01-31 17/week @ 2023-02-07 41/week @ 2023-02-14 36/week @ 2023-02-21 12/week @ 2023-02-28 12/week @ 2023-03-07 36/week @ 2023-03-14 3/week @ 2023-03-21

66 downloads per month
Used in phreak_engine

MIT license

79KB
857 lines

generational-indextree

License MIT Crates.io doc.rs dependency status

Arena based tree structure with support for removing nodes

This arena tree structure is using just a single GenerationalArena and indices 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.

Credits

This crate is a fork of the indextree crate, but with a generational arena to store the nodes instead of a Vec. This enables us to remove nodes and use the vacant spots to insert new nodes, without suffering from the ABA problem, as explained in the generational-arena crate.

We do sacrifice the rayon support in indextree in favor of the improved remove node api.

This package was forked from the excelent https://github.com/saschagrunert/indextree crate. The backing store was replaced by https://github.com/fitzgen/generational-arena, to improve support for removing nodes and reusing the space.

Example usage

use generational_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);

Change log

version date Change
1.1.4 15-01-2022 Leaner debug output, fixed !std support, improved test pipeline
1.1.3 10-01-2022 Fixed serde feature flag, thanks to Tal Liberman for the MR. Added new_node_with method that allow self-referential data, by Chris Laplante
1.1.2 02-12-2020 Resync to indextree version 4.3.1
1.1.1 20-06-2020 Resync to indextree version 4.1.0
1.1.0 16-06-2020 Resync to indextree version 4.0.0
1.0.0 05-04-2020 For of indextree, but using GenerationArena

Dependencies

~56–270KB