Charcoal

实现场分配的树数据结构和与之交互的接口。

概述

Charcoal 使用 Ben Lovy 描述的“场分配树”技术实现各种类型的树，详细说明请见"场分配树"。其核心思想是，树使用某种类型的后备存储来存储元素，通常是一个 Vec（或其变体，如 SmallVec 或 ArrayVec），而不是使用指针链接到子节点，而是使用存储中的索引。与基于 Rc 的树相比，这显著提高了元素插入和删除的性能，并为支持无需全局内存分配器的配置提供了空间。

存储

Charcoal 使用 Granite 来处理场分配存储。使用几个功能标志通过转发到 Granite 启用各种存储类型的各种依赖项。

功能标志

• std （默认启用） - 启用完整标准库，禁用 crate 中的 no_std。目前，这仅添加了一些类型的 Error trait 实现。
• unwind_safety （默认启用） - 当使用 unwinding panic 实现时必须启用，否则使用接受闭包的方法是未定义行为。需要 std。在 no_std 构建中不是问题，因为这些构建默认没有 panicking 运行时。
• alloc （默认启用） - 为标准库容器添加 ListStorage trait 实现，除了 LinkedList，暂时不支持。 这不要求标准库支持，并在没有分配器的 no_std 环境中仅在运行时引发 panic。
• smallvec - 转发到 Granite，为 SmallVec 添加 ListStorage trait 实现。
• slab — 转发到Granite，为Slab添加了Storage trait实现。
• slotmap — 转发到Granite，为SlotMap、HopSlotMap和DenseSlotMap添加了Storage trait实现。
• union_optimizations — 转发到Granite，通过使用无标签联合体，在SparseStorage中进行了某些布局优化，减少了内存使用。需要夜间编译器（请参阅RFC 2514的跟踪问题）因此默认禁用。

公共依赖

• arrayvec (必需) — ^0.5
• granite (必需) — ^1.0
  • smallvec (可选) — ^1.4
  • slab (可选) — ^0.4
  • slotmap (可选) — ^0.4

贡献

您可以通过以下方面为Charcoal做出贡献

• 算法优化 — Charcoal实现了各种通用的树算法，尽管它们使用了相当多的不安全代码，但它们仍然不是完美的，并且可以改进。如果您发现了一种改进Charcoal中算法实现的方法，欢迎您提交一个实现您改进的PR。
• 测试、调试和稳健性审计 — Charcoal的开发周期更偏好质量而非发布数量。您可以通过贡献测试和报告潜在的错误来帮助加快新版本的发布，这些错误可能非常罕见，但非常重要，它们应在发布新版本之前得到解决。
• 实现更多树 — 树数据结构有多种形状和大小。单个树的代码力求保持一致性，因此查看任何现有树就足以实现您自己的。Charcoal旨在成为所有类型树的通用crate，因此请随时提交直接PR来添加您的树类型，而不是发布自己的基于Charcoal的crate。