Description

A SparseTreeMap encodes a subset of nodes within a tree used for sparse-ancestor queries.

Combined with a SparseTreeHelper, this supports an Insert to add a tree node to the set and a Find operation to locate the nearest tree ancestor of a given node such that the ancestor is also in the set.

Given a set of blocks {B1, B2, B3} within the dominator tree, established by stm.Insert()ing B1, B2, B3, etc, a query at block B (performed with stm.Find(stm, B, adjust, helper)) will return the member of the set that is the nearest strict ancestor of B within the dominator tree, or nil if none exists. The expected complexity of this operation is the log of the size the set, given certain assumptions about sparsity (the log complexity could be guaranteed with additional data structures whose constant- factor overhead has not yet been justified.)

The adjust parameter allows positioning of the insertion and lookup points within a block -- one of AdjustBefore, AdjustWithin, AdjustAfter, where lookups at AdjustWithin can find insertions at AdjustBefore in the same block, and lookups at AdjustAfter can find insertions at either AdjustBefore or AdjustWithin in the same block. (Note that this assumes a gappy numbering such that exit number or exit number is separated from its nearest neighbor by at least 3).

The Sparse Tree lookup algorithm is described by Paul F. Dietz. Maintaining order in a linked list. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 122–127, May 1982. and by Ben Wegbreit. Faster retrieval from context trees. Communications of the ACM, 19(9):526–529, September 1976.