Struct Auto

pub struct Auto;

The Auto policy reclaims closed nodes whenever the utilization falls below 75%.

• The default policy; and hence, the generic parameter can be omitted.
• It automatically reclaims memory whenever the utilization falls below 75%.
• Automatic triggers of memory reclaims might lead to implicit invalidation of node indices due to ReorganizedCollection.
• It is important to note that, even when using Auto policy, tree growth will never trigger memory reclaim. Only node removing mutations such as prune can trigger node reorganization.

Compared to Lazy, auto approach has the following pros & cons:

• (+) Node indices (NodeIdx<V>) created for an auto-reclaim tree will can 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 auto policy, both the explicit (i) and implicit (ii) invalidation can occur.
• (-) Uses memory efficiently making sure that utilization can never go below a constant threshold.

Since Auto is the default memory policy, we do not need to include it in the tree type signature.

In order to observe the impact of the memory reclaim policy on validity of the node indices, please see the Examples section of MemoryPolicy.

Trait Implementations

impl MemoryPolicy for Auto

type MemoryReclaimPolicy<V> = MemoryReclaimOnThreshold<2, V, <V as TreeVariant>::Reclaimer> where V: TreeVariant

Memory reclaim policy for the specific tree variant V.