com.sun.electric.tool.ncc.trees
Class LeafEquivRecords
java.lang.Object
com.sun.electric.tool.ncc.trees.LeafEquivRecords
public class LeafEquivRecords
- extends java.lang.Object
Object to keep track of the leaves of the EquivRecord tree.
Profiling has demonstrated that it is too expensive to repeatedly locate
the leaves of the EquivRecord tree by recursive descent from the root. A
flat NCC of qFourP2 (no size checking) spends fully 80% of its time doing
just this. Therefore I'm building a data structure to keep track of the
leaves. Because this data structure updates itself incrementally it never
has to scan the tree.
A separate list of matched EquivRecords is kept. Most records will be
matched. Most of the time we're interested in records not matched.
Separating out the matched records speeds up the scan for active records.
Tricky: LeafEquivRecords takes advantage of the fact that the Gemini hash
code algorithm only subdivides "notMatched" EquivRecords.
This allows me to keep a separate list for the "notMatched" and scan only
that list to see which EquivRecords have been subdivided. What's tricky
is that the series-parallel reduction can change an EquivRecord from
notMatched to matched. Also Local Partitioning can change subdivide
a matched EquivRecord. Therefore I must initialize the LeafEquivRecords
object after series-parallel reduction and Local Partitioning.
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
LeafEquivRecords
public LeafEquivRecords(EquivRecord root,
NccGlobals globals)
getNotMatched
public java.util.Iterator<EquivRecord> getNotMatched()
- Returns:
- all leaf EquivRecords that haven't been matched
numNotMatched
public int numNotMatched()
getMatched
public java.util.Iterator<EquivRecord> getMatched()
- Returns:
- all matched leaf EquivRecords
numMatched
public int numMatched()