com.sun.electric.tool.ncc.trees
Class LeafEquivRecords

java.lang.Object
  extended by 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.


Constructor Summary
LeafEquivRecords(EquivRecord root, NccGlobals globals)
           
 
Method Summary
 java.util.Iterator<EquivRecord> getMatched()
           
 java.util.Iterator<EquivRecord> getNotMatched()
           
 int numMatched()
           
 int numNotMatched()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

LeafEquivRecords

public LeafEquivRecords(EquivRecord root,
                        NccGlobals globals)
Method Detail

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()
Returns:
the number of EquivRecords that are matched