← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/electric/oneiric

« back to all changes in this revision

Viewing changes to com/sun/electric/database/CellTree.java

  • Committer: Bazaar Package Importer
  • Author(s): Onkar Shinde
  • Date: 2010-01-09 16:26:04 UTC
  • mfrom: (1.1.4 upstream) (3.1.6 sid)
  • Revision ID: james.westby@ubuntu.com-20100109162604-1ypvmy8ijmlc6oq7
Tags: 8.10-1
* New upstream version.
* debian/control
  - Add libjava3d-java and quilt build dependencies.
  - Update standards version to 3.8.3.
  - Add libjava3d-java as recommends to binary package.
* debian/rules
  - Use quilt patch system instead of simple patchsys.
  - Add java3d related jar files to DEB_JARS.
* debian/patches/*
  - Update as per current upstream source. Convert to quilt.
* debian/ant.properties
  - Do not disable 3D plugin anymore.
  - Use new property to disable compilation of OS X related classes.
* debian/wrappers/electric
  - Add java3d related jar files to runtime classpath.
* debian/README.source
  - Change text to the appropriate one for quilt.

Show diffs side-by-side

added added

removed removed

Lines of Context:
com/sun/electric/database/CellTree.java
 
1
/* -*- tab-width: 4 -*-
 
2
 *
 
3
 * Electric(tm) VLSI Design System
 
4
 *
 
5
 * File: CellTree.java
 
6
 * Written by: Dmitry Nadezhin, Sun Microsystems.
 
7
 *
 
8
 * Copyright (c) 2005 Sun Microsystems and Static Free Software
 
9
 *
 
10
 * Electric(tm) is free software; you can redistribute it and/or modify
 
11
 * it under the terms of the GNU General Public License as published by
 
12
 * the Free Software Foundation; either version 3 of the License, or
 
13
 * (at your option) any later version.
 
14
 *
 
15
 * Electric(tm) is distributed in the hope that it will be useful,
 
16
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
17
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
18
 * GNU General Public License for more details.
 
19
 *
 
20
 * You should have received a copy of the GNU General Public License
 
21
 * along with Electric(tm); see the file COPYING.  If not, write to
 
22
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 
23
 * Boston, Mass 02111-1307, USA.
 
24
 */
 
25
package com.sun.electric.database;
 
26
 
 
27
import com.sun.electric.database.geometry.DBMath;
 
28
import com.sun.electric.database.geometry.ERectangle;
 
29
import com.sun.electric.database.id.CellId;
 
30
import com.sun.electric.database.id.CellUsage;
 
31
import com.sun.electric.database.text.ImmutableArrayList;
 
32
import com.sun.electric.technology.TechPool;
 
33
 
 
34
import java.awt.geom.Rectangle2D;
 
35
import java.util.Arrays;
 
36
import java.util.BitSet;
 
37
import java.util.Collections;
 
38
import java.util.HashSet;
 
39
import java.util.IdentityHashMap;
 
40
import java.util.Set;
 
41
 
 
42
/**
 
43
 * CellTree consists of top CellBackup and all CellTrees for all subcells.
 
44
 * It can compute Cell bounds and shape of Exports.
 
45
 */
 
46
public class CellTree {
 
47
 
 
48
    public static final CellTree[] NULL_ARRAY = {};
 
49
    public static final ImmutableArrayList<CellTree> EMPTY_LIST = new ImmutableArrayList<CellTree>(NULL_ARRAY);
 
50
    /**
 
51
     * top CellBackup
 
52
     */
 
53
    public final CellBackup top;
 
54
    final CellTree[] subTrees;
 
55
    /**
 
56
     * TechPool containing all Technologies used in this CellTree
 
57
     */
 
58
    public final TechPool techPool;
 
59
    /**
 
60
     * All cells used in this CellTree
 
61
     */
 
62
    public final Set<CellId> allCells;
 
63
    private ERectangle bounds;
 
64
 
 
65
    private EquivPorts equivPorts;
 
66
 
 
67
    private CellTree(CellBackup top, CellTree[] subTrees, TechPool techPool, Set<CellId> allCells) {
 
68
        this.top = top;
 
69
        this.subTrees = subTrees;
 
70
        this.techPool = techPool;
 
71
        this.allCells = allCells;
 
72
    }
 
73
 
 
74
    public static CellTree newInstance(ImmutableCell d, TechPool techPool) {
 
75
        CellBackup top = CellBackup.newInstance(d, techPool);
 
76
        assert top.cellRevision.cellUsages.length == 0;
 
77
        return new CellTree(top, NULL_ARRAY, top.techPool, Collections.singleton(top.cellRevision.d.cellId));
 
78
    }
 
79
 
 
80
    /**
 
81
     * Returns CellTree which differs from this CellTree.
 
82
     * @param top new top CellBackup
 
83
     * @param subTrees new subCellTrees
 
84
     * @param superPool TechPool which contains
 
85
     * @return CellTree which differs from this CellTree.
 
86
     */
 
87
    public CellTree with(CellBackup top, CellTree[] subTrees, TechPool superPool) {
 
88
        // Canonize subTrees
 
89
        if (Arrays.equals(this.subTrees, subTrees)) {
 
90
            subTrees = this.subTrees;
 
91
        } else {
 
92
            subTrees = subTrees.clone();
 
93
            int l = subTrees.length;
 
94
            while (l > 0 && subTrees[l - 1] == null) {
 
95
                l--;
 
96
            }
 
97
            if (l == 0) {
 
98
                subTrees = NULL_ARRAY;
 
99
            } else if (l != subTrees.length) {
 
100
                CellTree[] newSubTrees = null;
 
101
                if (l == this.subTrees.length) {
 
102
                    newSubTrees = this.subTrees;
 
103
                    for (int i = 0; i < l; i++) {
 
104
                        if (newSubTrees[i] != subTrees[i]) {
 
105
                            newSubTrees = null;
 
106
                            break;
 
107
                        }
 
108
                    }
 
109
                }
 
110
                if (newSubTrees == null) {
 
111
                    newSubTrees = new CellTree[l];
 
112
                    System.arraycopy(subTrees, 0, newSubTrees, 0, l);
 
113
                }
 
114
                subTrees = newSubTrees;
 
115
            }
 
116
        }
 
117
        // Check if unchanged
 
118
        if (this.top == top && this.subTrees == subTrees) {
 
119
            return this;
 
120
        }
 
121
 
 
122
        // Check if subTrees match the top backup
 
123
        // Check technologies against superPool
 
124
        // Compute cells and technologies used in new tree
 
125
        CellRevision cellRevision = top.cellRevision;
 
126
        CellId cellId = cellRevision.d.cellId;
 
127
        BitSet techUsages = new BitSet();
 
128
        if (top.techPool != superPool.restrict(cellRevision.techUsages, top.techPool)) {
 
129
            throw new IllegalArgumentException();
 
130
        }
 
131
        techUsages.or(cellRevision.techUsages);
 
132
        HashSet<CellId> allCellsAccum = new HashSet<CellId>();
 
133
        for (int i = 0; i < cellRevision.cellUsages.length; i++) {
 
134
            CellRevision.CellUsageInfo cui = cellRevision.cellUsages[i];
 
135
            CellTree subTree = subTrees[i];
 
136
            if (cui == null) {
 
137
                if (subTree != null) {
 
138
                    throw new IllegalArgumentException();
 
139
                }
 
140
                continue;
 
141
            }
 
142
            BitSet subTechUsages = subTree.techPool.getTechUsages();
 
143
            if (subTree.techPool != superPool.restrict(subTechUsages, subTree.techPool)) {
 
144
                throw new IllegalArgumentException();
 
145
            }
 
146
            techUsages.or(subTechUsages);
 
147
            allCellsAccum.addAll(subTree.allCells);
 
148
            CellRevision subCellRevision = subTree.top.cellRevision;
 
149
            if (subCellRevision.d.cellId != cellId.getUsageIn(i).protoId) {
 
150
                throw new IllegalArgumentException();
 
151
            }
 
152
            cui.checkUsage(subCellRevision);
 
153
        }
 
154
 
 
155
        // Check for recursion
 
156
        if (allCellsAccum.contains(cellId)) {
 
157
            throw new IllegalArgumentException("Recursive " + cellId);
 
158
        }
 
159
        // Canonize new allCells
 
160
        allCellsAccum.add(cellId);
 
161
        Set<CellId> allCells;
 
162
        if (allCellsAccum.equals(this.allCells)) {
 
163
            allCells = this.allCells;
 
164
        } else if (allCellsAccum.size() == 1) {
 
165
            allCells = Collections.singleton(cellId);
 
166
        } else {
 
167
            allCells = Collections.unmodifiableSet(allCellsAccum);
 
168
        }
 
169
        assert allCellsAccum.equals(allCells);
 
170
 
 
171
        // Construct new CellTree
 
172
        TechPool techPool = superPool.restrict(techUsages, this.techPool);
 
173
        CellTree newCellTree = new CellTree(top, subTrees, techPool, allCells);
 
174
 
 
175
        if (this.top == top) {
 
176
            // Try to reuse cell bounds
 
177
            if (this.bounds != null) {
 
178
                assert newCellTree.subTrees.length == this.subTrees.length;
 
179
                ERectangle cellBounds = this.bounds;
 
180
                for (int i = 0; i < this.subTrees.length; i++) {
 
181
                    CellTree oldSubTree = this.subTrees[i];
 
182
                    if (oldSubTree == null) continue;
 
183
                    assert oldSubTree.bounds != null;
 
184
                    if (!newCellTree.subTrees[i].getBounds().equals(oldSubTree.bounds)) {
 
185
                        cellBounds = null;
 
186
                        break;
 
187
                    }
 
188
                }
 
189
                if (cellBounds != null) {
 
190
                    newCellTree.bounds = cellBounds;
 
191
                }
 
192
            }
 
193
            // Try to reuse NetCell
 
194
            if (this.equivPorts != null) {
 
195
                assert newCellTree.subTrees.length == this.subTrees.length;
 
196
                EquivPorts netCell = this.equivPorts;
 
197
                for (int i = 0; i < this.subTrees.length; i++) {
 
198
                    CellTree oldSubTree = this.subTrees[i];
 
199
                    if (oldSubTree == null) continue;
 
200
                    assert oldSubTree.equivPorts != null;
 
201
                    if (!newCellTree.subTrees[i].getEquivPorts().equalsPorts(oldSubTree.equivPorts)) {
 
202
                        netCell = null;
 
203
                        break;
 
204
                    }
 
205
                }
 
206
                if (netCell != null) {
 
207
                    newCellTree.equivPorts = netCell;
 
208
                }
 
209
            }
 
210
        }
 
211
 
 
212
        // Return the new CellTree
 
213
        return newCellTree;
 
214
    }
 
215
 
 
216
    public boolean sameNetlist(CellTree that) {
 
217
        if (this.top != that.top) {
 
218
            return false;
 
219
        }
 
220
        for (int i = 0; i < this.subTrees.length; i++) {
 
221
            CellTree thisSubTree = this.subTrees[i];
 
222
            if (thisSubTree == null) continue;
 
223
            if (!this.subTrees[i].getEquivPorts().equalsPorts(that.subTrees[i].getEquivPorts())) {
 
224
                return false;
 
225
            }
 
226
        }
 
227
        return true;
 
228
    }
 
229
 
 
230
    public CellTree[] getSubTrees() {
 
231
        return subTrees.clone();
 
232
    }
 
233
 
 
234
    /**
 
235
     * Returns cell bounds of this CellTree
 
236
     * @return cell bounds of this CellTree
 
237
     */
 
238
    public ERectangle getBounds() {
 
239
        if (bounds == null) {
 
240
            bounds = computeBounds(null);
 
241
        }
 
242
        return bounds;
 
243
    }
 
244
 
 
245
    private ERectangle computeBounds(ERectangle candidateBounds) {
 
246
        CellRevision cellRevision = top.cellRevision;
 
247
 
 
248
        // Collect subcell bounds
 
249
        IdentityHashMap<CellId, ERectangle> subCellBounds = new IdentityHashMap<CellId, ERectangle>(cellRevision.cellUsages.length);
 
250
        for (CellTree subTree : subTrees) {
 
251
            if (subTree == null) {
 
252
                continue;
 
253
            }
 
254
            subCellBounds.put(subTree.top.cellRevision.d.cellId, subTree.getBounds());
 
255
        }
 
256
 
 
257
        double cellLowX, cellHighX, cellLowY, cellHighY;
 
258
        boolean boundsEmpty = true;
 
259
        cellLowX = cellHighX = cellLowY = cellHighY = 0;
 
260
 
 
261
        Rectangle2D.Double sb = new Rectangle2D.Double();
 
262
        for (ImmutableNodeInst n : top.cellRevision.nodes) {
 
263
            if (!(n.protoId instanceof CellId)) {
 
264
                continue;
 
265
            }
 
266
 
 
267
            ERectangle b = subCellBounds.get((CellId) n.protoId);
 
268
            n.orient.rectangleBounds(b.getMinX(), b.getMinY(), b.getMaxX(), b.getMaxY(),
 
269
                    n.anchor.getX(), n.anchor.getY(), sb);
 
270
 
 
271
            double lowx = sb.getMinX();
 
272
            double highx = sb.getMaxX();
 
273
            double lowy = sb.getMinY();
 
274
            double highy = sb.getMaxY();
 
275
            if (boundsEmpty) {
 
276
                boundsEmpty = false;
 
277
                cellLowX = lowx;
 
278
                cellHighX = highx;
 
279
                cellLowY = lowy;
 
280
                cellHighY = highy;
 
281
            } else {
 
282
                if (lowx < cellLowX) {
 
283
                    cellLowX = lowx;
 
284
                }
 
285
                if (highx > cellHighX) {
 
286
                    cellHighX = highx;
 
287
                }
 
288
                if (lowy < cellLowY) {
 
289
                    cellLowY = lowy;
 
290
                }
 
291
                if (highy > cellHighY) {
 
292
                    cellHighY = highy;
 
293
                }
 
294
            }
 
295
        }
 
296
        long gridMinX = DBMath.lambdaToGrid(cellLowX);
 
297
        long gridMinY = DBMath.lambdaToGrid(cellLowY);
 
298
        long gridMaxX = DBMath.lambdaToGrid(cellHighX);
 
299
        long gridMaxY = DBMath.lambdaToGrid(cellHighY);
 
300
 
 
301
        ERectangle primitiveBounds = top.getPrimitiveBounds();
 
302
        if (primitiveBounds != null) {
 
303
            if (boundsEmpty) {
 
304
                gridMinX = primitiveBounds.getGridMinX();
 
305
                gridMaxX = primitiveBounds.getGridMaxX();
 
306
                gridMinY = primitiveBounds.getGridMinY();
 
307
                gridMaxY = primitiveBounds.getGridMaxY();
 
308
            } else {
 
309
                gridMinX = Math.min(gridMinX, primitiveBounds.getGridMinX());
 
310
                gridMaxX = Math.max(gridMaxX, primitiveBounds.getGridMaxX());
 
311
                gridMinY = Math.min(gridMinY, primitiveBounds.getGridMinY());
 
312
                gridMaxY = Math.max(gridMaxY, primitiveBounds.getGridMaxY());
 
313
            }
 
314
        }
 
315
        if (candidateBounds != null && gridMinX == candidateBounds.getGridMinX() && gridMinY == candidateBounds.getGridMinY()
 
316
                && gridMaxX == candidateBounds.getGridMaxX() && gridMaxY == candidateBounds.getGridMaxY()) {
 
317
            return candidateBounds;
 
318
        }
 
319
        return ERectangle.fromGrid(gridMinX, gridMinY, gridMaxX - gridMinX, gridMaxY - gridMinY);
 
320
    }
 
321
 
 
322
    public EquivPorts getEquivPorts() {
 
323
        if (equivPorts == null) {
 
324
            equivPorts = new EquivPorts(this);
 
325
        }
 
326
        return equivPorts;
 
327
    }
 
328
 
 
329
    public EquivPorts computeEquivPorts() {
 
330
        return new EquivPorts(this);
 
331
    }
 
332
 
 
333
    public void check() {
 
334
        top.check();
 
335
        CellId cellId = top.cellRevision.d.cellId;
 
336
        BitSet techUsages = new BitSet();
 
337
        techUsages.or(top.cellRevision.techUsages);
 
338
        assert subTrees.length == top.cellRevision.cellUsages.length;
 
339
        HashSet<CellId> allCells = new HashSet<CellId>();
 
340
        for (int i = 0; i < subTrees.length; i++) {
 
341
            CellTree subTree = subTrees[i];
 
342
            CellRevision.CellUsageInfo cui = top.cellRevision.cellUsages[i];
 
343
            if (cui == null) {
 
344
                assert subTree == null;
 
345
                continue;
 
346
            }
 
347
            CellRevision subCellRevision = subTree.top.cellRevision;
 
348
            CellUsage cu = cellId.getUsageIn(i);
 
349
            assert subCellRevision.d.cellId == cu.protoId;
 
350
            cui.checkUsage(subCellRevision);
 
351
            BitSet subTechUsage = subTree.techPool.getTechUsages();
 
352
            assert subTree.techPool == techPool.restrict(subTechUsage, subTree.techPool);
 
353
            techUsages.or(subTechUsage);
 
354
            allCells.addAll(subTree.allCells);
 
355
        }
 
356
        assert top.techPool == techPool.restrict(top.cellRevision.techUsages, top.techPool);
 
357
        assert techUsages.equals(techPool.getTechUsages());
 
358
        assert !allCells.contains(cellId);
 
359
        allCells.add(cellId);
 
360
        assert allCells.equals(this.allCells);
 
361
        if (bounds != null) {
 
362
            assert bounds == computeBounds(bounds);
 
363
        }
 
364
    }
 
365
 
 
366
    @Override
 
367
    public String toString() {
 
368
        return top.toString();
 
369
    }
 
370
}