3 releases (stable)
|1.1.0||Mar 13, 2021|
|1.0.0||Nov 5, 2020|
|0.0.0||Sep 23, 2020|
#1107 in Data structures
Implements arena-allocated tree data structures and interfaces to work with them.
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
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.
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.
std(enabled by default) — enables the full standard library, disabling
no_stdfor the crate. Currently, this only adds
Errortrait 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_stdbuilds, since those do not have a panicking runtime by default.
alloc(enabled by default) — adds
ListStoragetrait 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_stdenvironments without an allocator.
smallvec— forwarded to Granite, adds a
ListStoragetrait implementation for
slab— forwarded to Granite, adds a
Storagetrait implementation for
slotmap— forwarded to Granite, adds
Storagetrait implementations for
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.
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.