Crate charcoal

Implements arena-allocated tree data structures and interfaces to work with them.

Overview

Charcoal implements various kinds of trees using a technique called “arena-allocated trees”, described by Ben Lovy. The gist of it is that the trees use some sort of backing storage to store the elements, typically a Vec (or its variants, like SmallVec or ArrayVec), and instead of using pointers to link to children, indices into the storage are used instead. This significantly improves element insertion and removal performance as compared to Rc-based trees, and gives room for supporting configurations without a global memory allocator.

Storage

Charcoal uses Granite to handle arena-allocated storage. Several feature flags are used to enable various dependencies on various storage types via forwaring them to Granite.

Feature flags

• std (enabled by default) — enables the full standard library, disabling no_std for the crate. Currently, this only adds Error trait implementations for some types.
• unwind_safety (enabled by default) — Must be enabled when using the unwinding panic implementation, otherwise using methods which accept closures is undefined behavior. Requires std. Not a concern in no_std builds, since those do not have a panicking runtime by default.
• alloc (enabled by default) — adds ListStorage trait implementations for standard library containers, except for LinkedList, which is temporarily unsupported. This does not require standard library support and will only panic at runtime in no_std environments without an allocator.
• smallvec — forwarded to Granite, adds a ListStorage trait implementation for SmallVec.
• slab — forwarded to Granite, adds a Storage trait implementation for Slab.
• slotmap — forwarded to Granite, adds Storage trait implementations for SlotMap, HopSlotMap and DenseSlotMap.
• union_optimizations — forwarded to Granite, adds some layout optimizations by using untagged unions, decreasing memory usage in SparseStorage. Requires a nightly compiler (see tracking issue for RFC 2514) and thus is disabled by default.

Public dependencies

• arrayvec (required) — ^0.5
• granite (required) — ^1.0
  • smallvec (optional) — ^1.4
  • slab (optional) — ^0.4
  • slotmap (optional) — ^0.4

Contributing

You can help by contributing to Charcoal in those aspects:

• Algorithm optimizations — Charcoal implements various ubiquitous algorithms for trees, and while those use a considerable amount of unsafe code, they still are never perfect and can be improved. If you find a way to improve an implementation of an algorithm in Charcoal, you’re welcome to submit a PR implementing your improvement.
• Testing, debugging and soundness auditing — the development cycle of Charcoal prefers quality over quantity of releases. You can help with releasing new versions faster by contributing tests and reporting potential bugs and soundness holes — those should be very rare but it’s very important that they are figured out and solved before being released in a new version of the crate.
• Implementing more trees — tree data structures come in various shapes and sizes. The code for the individual trees themselves strives to be consistent, so looking into any of the existing trees will be enough to implement your own. Charcoal aims to be the catch-all crate for all types of trees, so feel free to submit a direct PR to add your tree type instead of publishing your own Charcoal-based crate.

Re-exports

pub extern crate granite as storage;

pub use storage::Storage;

pub use storage::ListStorage;

pub use storage::DefaultStorage;

pub use binary_tree::BinaryTree;binary_tree

pub use octree::Octree;octree

pub use quadtree::Quadtree;quadtree

pub use freeform_tree::FreeformTree;freeform_tree

pub use traversal::Visitor;

pub use traversal::VisitorMut;

pub use traversal::Traversable;

pub use traversal::TraversableMut;

Modules

binary_treebinary_tree

Trees which allow at most two children for their nodes.

freeform_treefreeform_tree

Freeform trees, ones which don’t impose any restrictions on the number of child nodes that a branch node can have.

octreeoctree

Trees which allow nodes to have either zero children or exactly 8, most often used to partition a 3D space by recursively subdividing it into eight octants.

prelude

A prelude for using Charcoal, containing the most used types in a renamed form for safe glob-importing.

quadtreequadtree

Trees which allow nodes to have either zero children or exactly 4, most often used to partition a 2D space by recursively subdividing it into four quadrants.

traversal

Everything related to traversing trees in general.

Structs

MakeBranchError

The error type returned by methods on trees which convert leaf nodes into branch nodes, which occurs when the node which was attempted to be converted already is a branch node.

Enums

NodeValue

The payload of a node of a tree.

TryRemoveBranchError

The error type returned by methods on trees which remove branch nodes.

TryRemoveChildrenError

The error type returned by methods on trees which remove children branch nodes.

TryRemoveLeafError

The error type returned by methods on trees which remove leaf nodes.