rctree

rctree 是使用引用计数实现的“DOM-like”树。

起源

这是 rust-forest rctree 的分支。

详情

这里的“DOM-like”意味着数据结构可以用来表示 HTML 或 XML 文档的解析内容，就像 DOM 一样，但不一定具有与 DOM 完全相同的 API。也就是说

• 树由节点组成。
• 每个节点可以有零个或多个 子节点，这些子节点是有序的。
• 每个节点最多有一个 父节点，即它是 子节点 的节点。
• 没有 父节点 的节点被称为 根节点。
• 因此，每个节点也可能有 兄弟节点：它的 父节点 的其他 子节点（如果有）。
• 从任何给定的节点，访问其父节点、前一个兄弟节点、后一个兄弟节点、第一个子节点和最后一个子节点（如果有），最多需要 O(1) 的时间。
• 每个节点还关联着数据，在这个项目的目的是纯泛型。对于 HTML 文档，数据将是文本节点的文本，或元素节点的名称和属性。
• 树是可变的：节点（及其子树）可以在树中的任何位置插入或删除。

节点通过 引用计数 来管理生命周期。为了避免导致内存泄漏的循环引用，树是 非对称的：每个节点持有其下一个兄弟节点和第一个子节点的可选 强引用，但只持有其父节点、前一个兄弟节点和最后一个子节点的可选 弱引用。

节点在没有任何强引用的情况下立即被销毁。结构是这样的，持有根节点的引用足以保持整个树的生命周期。然而，例如，如果从树外部的唯一引用是用于遍历它的引用，那么在向下遍历之后将无法返回树的上层（祖先和前一个兄弟节点），因为这些节点已经被销毁了。

已销毁节点的弱引用被视为未设置（例如，当一个节点的父节点被销毁时，该节点可以成为根节点）。

由于节点是别名的（有多个引用指向它们），使用RefCell来处理内部可变性。

优点

• 单个可操作的树用户可见类型，带有方法。
• 内存一旦不再使用（如果移除树的某些部分），就会立即释放。

缺点

• 树只能从创建它的线程中访问。
• 任何树操作，包括只读遍历，都需要增加和减少引用计数，这会导致运行时开销。
• 节点单独分配，可能会造成内存碎片化并影响性能。

许可证

rctree使用MIT许可证。