无意进行维护

此仓库存在是为了发布我在某个周末做的某些实验的结果。这不是一个随着时间的推移而被维护的软件项目。

如果您想使用此代码，请考虑将其复制到您自己的源代码库中，并符合MIT许可证的条款。

rust-forest

Rust 中“DOM-like”树数据结构的各种实现策略。

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

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

特别是，访问父节点的需要意味着我们不能使用子节点直接由其父节点 拥有 的明显结构

struct Node<T> {
    data: T,
    children: Vec<Node<T>>,
    parent: /* ??? */
}

更普遍地，具有父子关系和兄弟关系（除了父子关系）的树可以被视为一种特殊类型的图，但仍然是一个包含环的图。Rust的默认所有权模型不易支持环。因此，我们需要一个更复杂的策略来管理节点的作用域。

在 Servo 中，DOM 节点由 JavaScript 垃圾回收器管理。然而，Rust 目前还没有自己的跟踪垃圾回收器，许多 Rust 项目可能想要操作类似 DOM 的树，而不需要嵌入整个 JavaScript 虚拟机。

此存储库包含多个 crate，每个 crate 都以不同的方法和不同的权衡实现了一个类似 DOM 的数据结构。

rctree

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

一旦没有强引用指向节点，节点就会被销毁。这种结构使得持有对根节点的引用就足以保持整个树存活。然而，例如，如果从树外部的唯一引用是用于遍历它的引用，则在“向下”遍历之后，您将无法返回到树中的祖先和前一个兄弟，因为这些节点已被销毁。

对已销毁节点的弱引用被当作未设置处理。（例如，一个节点可以在其父节点被销毁时成为根节点。）

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

优点

• 一个单一的 NodeRef 可视类型来操作树，具有方法
• 内存一旦不再使用（如果删除了树的某些部分）就会释放。

缺点

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

arena-tree

节点生命周期通过 竞技场分配器 来管理。

节点通过 &'a T 引用与竞技场的生命周期相关联，当竞技场被销毁时，节点会一起被销毁。节点之间的链接也是内部使用 &'a T 引用。

由于节点是 别名（有多个引用指向它们），因此使用 Cell 来实现内部可变性。

优点

• 节点仍然有方法，在树操作过程中可以 largely 忽略竞技场（只要它保持存活）。
• 更少的运行时开销。（分配速度快，无需增加或减少引用计数。）
• 节点在大型连续的内存块中分配。这有助于内存缓存性能。

缺点

• 还有一个对象（竞技场）需要保留。
• 树只能从创建它的线程中访问。
• 在竞技场销毁之前从树中移除节点时，会出现内存“泄漏”。这可以通过维护一个 空闲列表 来缓解，该列表包含不再使用的节点，可以重复使用，但这些节点必须显式释放。（而引用计数和垃圾回收会自动释放未使用的节点。）但是，没有阻止保留对已释放节点的引用。可以添加另一个显式机制（如在每个节点中跟踪一个 生成号）来防止（主要是）此类引用和访问已释放或重新分配的节点。

idtree

与 arena-tree 类似，但竞技场简化为一个单一的 Vec，并使用数值标识符（向量中的索引）而不是 &'a T 引用。

优点

• 没有 RefCell，可变性通过在竞技场中进行唯一（&mut）访问的方式处理，这种方式在 Rust 中更加符合习惯。
• 这棵树可以像 Vec 一样在线程之间传递或共享。这使并行树遍历成为可能。

缺点

• 每次访问都需要通过竞技场进行，这可能很麻烦。
• 由于边界检查，相对于 arena-tree 而言，存在一些运行时开销。
• 从给定竞技场中的一个节点 ID 可以在另一个竞技场中使用，这很可能会不会引起错误并访问到无关的节点。

lib.rs:

基于 &Node 引用的类似 DOM 的树数据结构。

任何非平凡的树都涉及引用循环（例如，如果一个节点有一个第一个子节点，该子节点的父节点就是该节点）。为了实现这一点，节点需要存在于竞技场分配器中，例如 rustc 一起分发的 arena::TypedArena（截至撰写本文时为 #[unstable]）或 typed_arena::Arena。

如果你需要在节点 data 中使用可变性，可以将其设置为单元格（Cell 或 RefCell）或在其内部使用单元格。

示例

extern crate typed_arena;
extern crate arena_tree;
use std::cell::RefCell;

let arena = typed_arena::Arena::new();
let a = arena.alloc(arena_tree::Node::new(RefCell::new(String::new())));
let b = arena.alloc(arena_tree::Node::new(RefCell::new(String::new())));
a.append(b);
b.data.borrow_mut().push_str("content");
assert_eq!(a.descendants().map(|node| node.data.borrow().clone()).collect::<Vec<_>>(), [
"".to_string(), "content".to_string()
]);