使用旧的 Rust 2015

0.0.1	2015年4月10日

1KB

不打算维护

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

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

rust-forest

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

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

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

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

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

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

此存储库包含多个crate，每个crate都使用不同的方法实现不同的权衡来实现DOM-like数据结构。

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

节点一旦没有强引用，就会被销毁。结构是这样的，只要持有根节点的引用，就可以保持整棵树的生命。然而，如果从树外部的唯一引用是用来遍历树的，那么在向下遍历之后，将无法回到树上的祖先和之前的兄弟节点，因为这些节点已经被销毁了。

对已销毁节点的弱引用被视为未设置。例如，当其父节点被销毁时，节点可以成为根节点。

由于节点被别名（存在多个引用），所以使用RefCell来实现内部可变。

优势

劣势

节点生命周期通过场分配器进行管理。

节点通过&'a T引用与场的生命周期相关联，当场被销毁时，节点将同时被销毁。节点之间的链接在内部也是&'a T引用。

由于节点被别名（存在多个引用），所以使用Cell来实现内部可变。

优势

劣势

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

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

优势

劣势