View on GitHub
SpanningTree
private struct SpanningTree : SendableA spanning tree of a control flow graph.
-
A node in the tree.
Declaration
Swift
typealias Node = Function.Blocks.Address -
A map from node to its parent.
-
Creates a spanning tree of
cfgrooted atroot.Declaration
Swift
init(of cfg: ControlFlowGraph, rootedAt root: Node) -
Returns the parent of
v.Requires
vis in the tree.Complexity
O(1). -
Sets
newParentasv‘s parent.Requires
vandnewParentare in the tree and distinct;visn’t the root.Complexity
O(1). -
Returns collection containing
vfollowed by all its ancestor, ordered by depth.Requires
vis in the tree.Complexity
O(h) where h is the height ofself. -
Returns the deepest vertex that is ancestor of both
vandu.Requires
vanduare in the tree.Complexity
O(h) where h is the height ofself.