Bark-Browser/lib/slab-tree

slab_tree

A vec-backed tree structure with tree-specific generational indexes.

Overview

This library provides a Tree<T> struct which allows the creation and manipulation of in-memory trees. The tree itself is backed by a vector and the tree's node relationships are managed by tree-specific generational indexes called NodeIds (more below). In addition, "views" of tree nodes are handed out which are either immutable (NodeRef) or mutable (NodeMut) instead of handing out references directly. Most tree mutations are achieved by modifying NodeMuts instead of talking to the tree itself.

Trees in this crate are "just" trees. They do not allow cycles, and they do not allow arbitrary graph structures to be created. Each node in the tree can have an arbitrary number of children, and there is no weight associated with edges between the nodes in the tree.

Please Note: this crate does not support comparison-based data insertion. In other words, this is not a binary search tree (or any other kind of search tree) crate. It is purely a crate for storing data in a hierarchical manner. The caller must know the structure that they wish to build and then use this crate to do so; this library will not make those structural decisions for you.

Safety

This crate uses #![forbid(unsafe_code)] to prevent any and all unsafe code usage.

Example Usage

use slab_tree::*;

fn main() {

    //      "hello"
    //        / \
    // "world"   "trees"
    //              |
    //            "are"
    //              |
    //            "cool"

    let mut tree = TreeBuilder::new().with_root("hello").build();
    let root_id = tree.root_id().expect("root doesn't exist?");
    let mut hello = tree.get_mut(root_id).unwrap();

    hello.append("world");
    hello
        .append("trees")
        .append("are")
        .append("cool");
}

NodeIds

NodeIds are tree-specific generational indexes. Using generational indexes means that we can re-use space inside the tree (after nodes have been removed) without also having to re-use the same tree indexes which could potentially cause confusion and bugs. The "tree-specific" part means that indexes from one tree cannot be confused for indexes for another tree. This is because each index contains a process-unique-id which is shared by the tree from which that index originated.

Project Goals

• Allow caller control of as many allocations as possible (through pre-allocation)
• Fast and Ergonomic Node insertion and removal
• Arbitrary Tree structure creation and manipulation

Non-Goals

• Arbitrary Graph structure creation and manipulation
• Comparison-based node insertion of any kind