arctree

arctree 是一个使用原子引用计数实现的“DOM-like”树。

起源

这是一个 rctree 的分支。

细节

"DOM-like" 指的是可以使用数据结构来表示HTML或XML文档的解析内容，就像 DOM 所做的那样，但并不一定具有与DOM完全相同的API。也就是说

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

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

一旦没有强引用指向节点，节点就会被销毁。结构是这样的，拥有根节点的引用足以保持整个树存活。然而，如果例如树外部的唯一引用是你用来遍历树的引用，那么在“向下”遍历后，你将无法“向上”遍历树到祖先和前一个兄弟节点，因为这些节点已经被销毁了。

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

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

优点

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

缺点

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

最低支持的Rust版本（MSRV）

当前的MSRV是1.49.0，这是由于parking_lot依赖项。

许可证

arctree采用MIT许可证。