3 releases (stable)
1.1.0 | Mar 13, 2021 |
---|---|
1.0.0 | Nov 5, 2020 |
0.0.0 | Sep 23, 2020 |
#1259 in Data structures
305KB
5.5K
SLoC
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, disablingno_std
for the crate. Currently, this only addsError
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. Requiresstd
. Not a concern inno_std
builds, since those do not have a panicking runtime by default.alloc
(enabled by default) — addsListStorage
trait implementations for standard library containers, except forLinkedList
, which is temporarily unsupported. This does not require standard library support and will only panic at runtime inno_std
environments without an allocator.smallvec
— forwarded to Granite, adds aListStorage
trait implementation forSmallVec
.slab
— forwarded to Granite, adds aStorage
trait implementation forSlab
.slotmap
— forwarded to Granite, addsStorage
trait implementations forSlotMap
,HopSlotMap
andDenseSlotMap
.union_optimizations
— forwarded to Granite, adds some layout optimizations by using untagged unions, decreasing memory usage inSparseStorage
. 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.
Dependencies
~240KB