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.