Struct Lazy

pub struct Lazy;

The Lazy policy never reclaims closed nodes.

• It never reclaims memory.
• It never leads to implicit invalidation of node indices. In other words, a node index can only be invalidated if we remove that node from the tree (RemovedNode).

Compared to Auto, lazy approach has the following pros & cons:

• (+) Node indices (NodeIdx<V>) created for a lazy tree will never be implicitly invalidated. Recall that, analogous to random access to an array element with its index, node indices allow for constant time access to the corresponding node. A node index can be invalidated if either of the following happens (i) the node is removed from the tree, (ii) other nodes are removed from the tree triggering a memory reclaim operation. With lazy policy, the second case can never happen.
• (-) Uses more memory due to the gaps of the closed nodes especially when there exist many deletions from the tree.

Notice that the con can never be observed for grow-only situations; or might be insignificant when the number of removals is not very large. In such situations, it is the recommended memory reclaim policy.

Trait Implementations

impl MemoryPolicy for Lazy

type MemoryReclaimPolicy<V> = MemoryReclaimNever where V: TreeVariant

Memory reclaim policy for the specific tree variant V.