cellbackup.java

The ElectricTM VLSI Design System is an open-source Electronic Design Automation (EDA) system that c

//         */
//        private final int[] nodesById;
        public final int[] connections;
        /** ImmutableExports sorted by original PortInst. */
        private final ImmutableExport[] exportIndexByOriginalPort;
        private final BitSet wiped = new BitSet();
        private final BitSet hardArcs = new BitSet();

        Memoization() {
//            long startTime = System.currentTimeMillis();
            cellBackupsMemoized++;
            ImmutableArrayList<ImmutableNodeInst> nodes = cellRevision.nodes;
            ImmutableArrayList<ImmutableArcInst> arcs = cellRevision.arcs;
            int maxNodeId = -1;
            for (int nodeIndex = 0; nodeIndex < nodes.size(); nodeIndex++)
                maxNodeId = Math.max(maxNodeId, nodes.get(nodeIndex).nodeId);
//            int[] nodesById = new int[maxNodeId + 1];
//            for (int nodeIndex = 0; nodeIndex < nodes.size(); nodeIndex++) {
//                ImmutableNodeInst n = nodes.get(nodeIndex);
//                nodesById[n.nodeId] = nodeIndex;
//            }
//            this.nodesById = nodesById;

            // Put connections into buckets by nodeId.
            int[] connections = new int[arcs.size()*2];
            int[] connectionsByNodeId = new int[maxNodeId+1];
            for (ImmutableArcInst a: arcs) {
                connectionsByNodeId[a.headNodeId]++;
                connectionsByNodeId[a.tailNodeId]++;
            }
            int sum = 0;
            for (int nodeId = 0; nodeId < connectionsByNodeId.length; nodeId++) {
                int start = sum;
                sum += connectionsByNodeId[nodeId];
                connectionsByNodeId[nodeId] = start;
            }
            for (int i = 0; i < arcs.size(); i++) {
                ImmutableArcInst a = arcs.get(i);
                connections[connectionsByNodeId[a.tailNodeId]++] = i*2;
                connections[connectionsByNodeId[a.headNodeId]++] = i*2 + 1;
            }

            // Sort each bucket by portId.
            sum = 0;
            for (int nodeId = 0; nodeId < connectionsByNodeId.length; nodeId++) {
                int start = sum;
                sum = connectionsByNodeId[nodeId];
                if (sum - 1 > start)
                    sortConnections(connections, start, sum - 1);
            }
            this.connections = connections;

            ImmutableExport[] exportIndexByOriginalPort = cellRevision.exports.toArray(new ImmutableExport[cellRevision.exports.size()]);
            Arrays.sort(exportIndexByOriginalPort, BY_ORIGINAL_PORT);
            this.exportIndexByOriginalPort = exportIndexByOriginalPort;

            for (ImmutableArcInst a: arcs) {
                ArcProto ap = techPool.getArcProto(a.protoId);
                // wipe status
                if (ap.isWipable()) {
                    wiped.set(a.tailNodeId);
                    wiped.set(a.headNodeId);
                }
                // hard arcs
                if (!ap.getTechnology().isEasyShape(a, false))
                    hardArcs.set(a.arcId);
            }
            for (int nodeIndex = 0; nodeIndex < nodes.size(); nodeIndex++) {
                ImmutableNodeInst n = nodes.get(nodeIndex);
                NodeProtoId np = n.protoId;
                if (!(np instanceof PrimitiveNodeId && techPool.getPrimitiveNode((PrimitiveNodeId)np).isArcsWipe()))
                    wiped.clear(n.nodeId);
            }
//            long stopTime = System.currentTimeMillis();
//            System.out.println("Memoization " + cellRevision.d.cellId + " took " + (stopTime - startTime) + " msec");
        }

       /**
         * Returns true of there are Exports on specified NodeInst.
         * @param originalNodeId nodeId of specified NodeInst.
         * @return true if there are Exports on specified NodeInst.
         */
        public boolean hasExports(int originalNodeId) {
            int startIndex = searchExportByOriginalPort(originalNodeId, 0);
            if (startIndex >= exportIndexByOriginalPort.length) return false;
            ImmutableExport e = exportIndexByOriginalPort[startIndex];
            return e.originalNodeId == originalNodeId;
        }

        /**
         * Method to return the number of Exports on specified NodeInst.
         * @param originalNodeId nodeId of specified NodeInst.
         * @return the number of Exports on specified NodeInst.
         */
        public int getNumExports(int originalNodeId) {
            int startIndex = searchExportByOriginalPort(originalNodeId, 0);
            int j = startIndex;
            for (; j < exportIndexByOriginalPort.length; j++) {
                ImmutableExport e = exportIndexByOriginalPort[j];
                if (e.originalNodeId != originalNodeId) break;
            }
            return j - startIndex;
        }

        /**
         * Method to return an Iterator over all ImmutableExports on specified NodeInst.
         * @param originalNodeId nodeId of specified NodeInst.
         * @return an Iterator over all ImmutableExports on specified NodeInst.
         */
        public Iterator<ImmutableExport> getExports(int originalNodeId) {
            int startIndex = searchExportByOriginalPort(originalNodeId, 0);
            int j = startIndex;
            for (; j < exportIndexByOriginalPort.length; j++) {
                ImmutableExport e = exportIndexByOriginalPort[j];
                if (e.originalNodeId != originalNodeId) break;
            }
            return ArrayIterator.iterator(exportIndexByOriginalPort, startIndex, j);
        }

        private int searchExportByOriginalPort(int originalNodeId, int originalChronIndex) {
            int low = 0;
            int high = exportIndexByOriginalPort.length-1;
            while (low <= high) {
                int mid = (low + high) >> 1; // try in a middle
                ImmutableExport e = exportIndexByOriginalPort[mid];
                int cmp = e.originalNodeId - originalNodeId;
                if (cmp == 0)
                    cmp = e.originalPortId.getChronIndex() >= originalChronIndex ? 1 : -1;

                if (cmp < 0)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            return low;
        }

        public int searchConnectionByPort(int nodeId, int chronIndex) {
            int low = 0;
            int high = connections.length-1;
            while (low <= high) {
                int mid = (low + high) >> 1; // try in a middle
                int con = connections[mid];
                ImmutableArcInst a = cellRevision.arcs.get(con >>> 1);
                boolean end = (con & 1) != 0;
                int endNodeId = end ? a.headNodeId : a.tailNodeId;
                int cmp = endNodeId - nodeId;
                if (cmp == 0) {
                    PortProtoId portId = end ? a.headPortId : a.tailPortId;
                    cmp = portId.getChronIndex() - chronIndex;
                }

                if (cmp < 0)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            return low;
        }

        public ImmutableArrayList<ImmutableArcInst> getArcs() { return cellRevision.arcs; }

        /**
         * Method to tell whether the specified ImmutableNodeInst is wiped.
         * Wiped ImmutableNodeInsts are erased.  Typically, pin ImmutableNodeInsts can be wiped.
         * This means that when an arc connects to the pin, it is no longer drawn.
         * In order for a ImmutableNodeInst to be wiped, its prototype must have the "setArcsWipe" state,
         * and the arcs connected to it must have "setWipable" in their prototype.
         * @param nodeId nodeId of specified ImmutableNodeInst
         * @return true if specified ImmutableNodeInst is wiped.
         */
        public boolean isWiped(int nodeId) {
            return wiped.get(nodeId);
        }

        public boolean isHardArc(int arcId) {
            return hardArcs.get(arcId);
        }

        /**
         * Checks invariant of this CellBackup.
         * @throws AssertionError if invariant is broken.
         */
        private void check() {
            assert exportIndexByOriginalPort.length == cellRevision.exports.size();
            ImmutableExport prevE = null;
            for (ImmutableExport e: exportIndexByOriginalPort) {
                if (prevE != null)
                    assert BY_ORIGINAL_PORT.compare(prevE, e) < 0;
                assert e == cellRevision.getExport(e.exportId);
                prevE = e;
            }
            assert connections.length == cellRevision.arcs.size()*2;
            for (int i = 1; i < connections.length; i++)
                assert compareConnections(connections[i - 1], connections[i]) < 0;
        }

        private void sortConnections(int[] connections, int l, int r) {
            ImmutableArrayList<ImmutableArcInst> arcs = cellRevision.arcs;
            while (l + 1 < r) {
                int x = connections[(l + r) >>> 1];
                ImmutableArcInst ax = arcs.get(x >>> 1);
                boolean endx = (x & 1) != 0;
                PortProtoId portIdX = endx ? ax.headPortId : ax.tailPortId;
                int chronIndexX = portIdX.getChronIndex();
                int i = l, j = r;
                do {
                    // while (compareConnections(connections[i], x) < 0) i++;
                    for (;;) {
                        int con = connections[i];
                        ImmutableArcInst a = arcs.get(con >>> 1);
                        boolean end = (con & 1) != 0;
                        PortProtoId portId = end ? a.headPortId : a.tailPortId;
                        if (portId.getChronIndex() > chronIndexX) break;
                        if (portId.getChronIndex() == chronIndexX && con >= x) break;
                        i++;
                    }

                    // while (compareConnections(x, connections[j]) < 0) j--;
                    for (;;) {
                        int con = connections[j];
                        ImmutableArcInst a = arcs.get(con >>> 1);
                        boolean end = (con & 1) != 0;
                        PortProtoId portId = end ? a.headPortId : a.tailPortId;
                        if (chronIndexX > portId.getChronIndex()) break;
                        if (chronIndexX == portId.getChronIndex() && x >= con) break;
                        j--;
                    }

                    if (i <= j) {
                        int w = connections[i];
                        connections[i] = connections[j];
                        connections[j] = w;
                        i++; j--;
                    }
                } while (i <= j);
                if (j - l < r - i) {
                    sortConnections(connections, l, j);
                    l = i;
                } else {
                    sortConnections(connections, i, r);
                    r = j;
                }
            }
            if (l + 1 == r) {
                int con1 = connections[l];
                int con2 = connections[r];
                ImmutableArcInst a1 = arcs.get(con1 >>> 1);
                ImmutableArcInst a2 = arcs.get(con2 >>> 1);
                boolean end1 = (con1 & 1) != 0;
                boolean end2 = (con2 & 1) != 0;
                PortProtoId portId1 = end1 ? a1.headPortId : a1.tailPortId;
                PortProtoId portId2 = end2 ? a2.headPortId : a2.tailPortId;
                int cmp = portId1.getChronIndex() - portId2.getChronIndex();
                if (cmp > 0 || cmp == 0 && con1 > con2) {
                    connections[l] = con2;
                    connections[r] = con1;
                }
            }
        }

        private int compareConnections(int con1, int con2) {
            ImmutableArcInst a1 = cellRevision.arcs.get(con1 >>> 1);
            ImmutableArcInst a2 = cellRevision.arcs.get(con2 >>> 1);
            boolean end1 = (con1 & 1) != 0;
            boolean end2 = (con2 & 1) != 0;
            int nodeId1 = end1 ? a1.headNodeId : a1.tailNodeId;
            int nodeId2 = end2 ? a2.headNodeId : a2.tailNodeId;
            int cmp = nodeId1 - nodeId2;
            if (cmp != 0) return cmp;
            PortProtoId portId1 = end1 ? a1.headPortId : a1.tailPortId;
            PortProtoId portId2 = end2 ? a2.headPortId : a2.tailPortId;
            cmp = portId1.getChronIndex() - portId2.getChronIndex();
            if (cmp != 0) return cmp;
            return con1 - con2;
        }
    }

    private static final Comparator<ImmutableExport> BY_ORIGINAL_PORT = new Comparator<ImmutableExport>() {
        public int compare(ImmutableExport e1, ImmutableExport e2) {
            int result = e1.originalNodeId - e2.originalNodeId;
            if (result != 0) return result;
            result = e1.originalPortId.getChronIndex() - e2.originalPortId.getChronIndex();
            if (result != 0) return result;
            return e1.exportId.chronIndex - e2.exportId.chronIndex;
        }
    };
 }