mirror of
https://github.com/chylex/Bark-Browser.git
synced 2024-11-23 19:42:50 +01:00
70 lines
2.8 KiB
Markdown
70 lines
2.8 KiB
Markdown
# slab_tree
|
|
|
|
[](https://travis-ci.org/iwburns/slab-tree)
|
|
[](https://github.com/iwburns/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 `NodeId`s (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 `NodeMut`s instead of talking to the tree
|
|
itself.
|
|
|
|
`Tree`s 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
|
|
```rust
|
|
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");
|
|
}
|
|
```
|
|
|
|
## `NodeId`s
|
|
`NodeId`s 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
|