Expand description
A safe, indexed, n-ary tree implementation
§About
This module using arena-like backing primarily as an easy way to provide safe node referencing to mutable tree structures in a way that avoids complex lifetime management, overly-restrictive API design, and the runtime overhead of reference counting.
Compromises over the link-based tree include being less spatially efficient as the arena’s growth algorithm logically shifts “pointers” to Nodes in the arena.
§Design
The implementation stores all Node values in a flat Vec-backed arena. For small trees (fewer than ~100 nodes), it is marginally slower than the Rc<RefCell>-based design due to fixed arena management overhead. However, for larger trees (starting around 1,000–10,000 nodes), it improves construction speed by roughly 20–25%, primarily from reduced heap allocations and better cache locality.
§Generations & Free Lists
This structure uses generations on its safe handles to mitigate dangling access & use-after-free errors, dead references via ABA problem mitigation, and handle forgery. This is something that both naive arena-backed structures and raw pointer structures are vulnerable to. Reference counting prevents dangling access and dead references, and makes handle forgery impossible.
This structure implements a free list to mitigate leaks. When nodes are removed, the backing slot takes on a None value, which can bloat the list unless those nodes are re-filled. However, this means that two node references could point to the same memory slot. As a result, the structure increments generational count by usage, guaranteeing that only the correct generational combination can access the memory slot.
§Drawbacks
This implementation includes several critical compromises over a more traditional link-based approach. This Vec-backed design is intended to provide a more ergonomic design over reference counted alternatives with interior mutability, as well as raw pointer-based designs with complex lifetime management and restrictive APIs. Unfortunately, this Vec-backed design also comes with its own compromises. The Vec-backed design is far less spatially efficient due to the structure’s growth. As the tree gets mutated, it also potentially loses cache locality.
§Example