netcell.java

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

/* -*- tab-width: 4 -*-
 *
 * Electric(tm) VLSI Design System
 *
 * File: NetCell.java
 * Written by: Dmitry Nadezhin, Sun Microsystems.
 *
 * Copyright (c) 2003 Sun Microsystems and Static Free Software
 *
 * Electric(tm) is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Electric(tm) is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Electric(tm); see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, Mass 02111-1307, USA.
 */
package com.sun.electric.database.network;

import com.sun.electric.database.geometry.GenMath;
import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.hierarchy.Export;
import com.sun.electric.database.hierarchy.Nodable;
import com.sun.electric.database.id.CellUsage;
import com.sun.electric.database.prototype.NodeProto;
import com.sun.electric.database.prototype.PortProto;
import com.sun.electric.database.text.Name;
import com.sun.electric.database.topology.ArcInst;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.database.topology.PortInst;
import com.sun.electric.technology.ArcProto;
import com.sun.electric.technology.PrimitiveNode;
import com.sun.electric.technology.PrimitivePort;
import com.sun.electric.technology.technologies.Artwork;
import com.sun.electric.technology.technologies.Generic;
import com.sun.electric.technology.technologies.Schematics;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * This is the Cell mirror in Network tool.
 */
class NetCell
{
	/** If bit set, netlist is valid for cell tree.*/				static final int VALID = 1;
	/** If bit set, netlist is valid with current  equivPorts of subcells.*/static final int LOCALVALID = 2;
    /** Separator for net names of unconnected port instances */    static final char PORT_SEPARATOR = '.';

    /** Network manager to which this NetCell belongs. */           final NetworkManager networkManager;
	/** Cell from database. */										final Cell cell;
	/** Flags of this NetCell. */									int flags;
    /** The number of times this NetCell has been <i>structurally modified</i>.
     * Structural modifications are those that change the number of networks in
	 * its netlists, or otherwise perturb them in such a fashion that iterations in
     * progress may yield incorrect results.<p>
     *
     * This field is used by the netlist implementation returned by the
	 * <tt>getNetlist</tt> methods. If the value of this field changes unexpectedly,
	 * the netlist will throw a <tt>ConcurrentModificationException</tt> in
     * response to the <tt>getNetwork</tt> and other operations.  This provides
     * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
     * the face of concurrent modification during netlist examination.<p>
     */																int modCount = 0;

	/**
     * Equivalence of ports.
     * equivPorts.size == ports.size.
	 * equivPorts[i] contains minimal index among ports of its group.
     */																int[] equivPortsN;
                                                                    int[] equivPortsP;
                                                                    int[] equivPortsA;
	/** Node offsets. */											int[] ni_pi;
    /** arc index in alpanumeric order by arcId */                  private int[] arcIndexByArcIdMap;
	/** */															int arcsOffset;
	/** */															private int[] headConn;
	/** */															private int[] tailConn;
	/** */															int[] drawns;
	/** */															int numDrawns;
    /** */                                                          int numExportedDrawns;
	/** */															int numConnectedDrawns;

	/** A map from canonic String to NetName. */					HashMap<Name,GenMath.MutableInteger> netNames = new HashMap<Name,GenMath.MutableInteger>();
	/** Counter for enumerating NetNames. */						private int netNameCount;
	/** Counter for enumerating NetNames. */						int exportedNetNameCount;

	/** Netlist for ShortResistors.NO option. */                    NetlistImpl netlistN;
	/** Netlist for true ShortResistors.PARASITIC option. */        NetlistShorted netlistP;
	/** Netlist for true ShortResistors.ALL option. */              NetlistShorted netlistA;


	/** */															private static PortProto busPinPort = Schematics.tech().busPinNode.getPort(0);
	/** */															private static ArcProto busArc = Schematics.tech().bus_arc;
	NetCell(Cell cell)
	{
        this.networkManager = cell.getDatabase().getNetworkManager();
		this.cell = cell;
		networkManager.setCell(cell, this);
	}

	final void setNetworksDirty()
	{
		setInvalid(true, false);
	}

	void exportsChanged()
	{
		setInvalid(true, true);
	}

	void setInvalid(boolean strongMe, boolean strongUsages)
	{
//		System.out.println("setInvalid " + cell + " " + strongMe + " " + strongUsages);
		if (strongMe) flags &= ~LOCALVALID;
		if ((flags & VALID) == 0 && !strongUsages) return;
		flags &= ~VALID;
		invalidateUsagesOf(strongUsages);
	}

	void invalidateUsagesOf(boolean strong)
	{
//		System.out.println("NetSchem.invalidateUsagesOf " + cell + " " + strong);
		for (Iterator<CellUsage> it = cell.getUsagesOf(); it.hasNext();) {
			CellUsage u = it.next();
            Cell parent = u.getParent();
			if (cell.isIconOf(parent)) continue;
			NetCell netCell = networkManager.getNetCell(parent);
			if (netCell != null) netCell.setInvalid(strong, false);
		}
	}

	Netlist getNetlist(Netlist.ShortResistors shortResistors) {
		if ((flags & VALID) == 0) redoNetworks();
        switch (shortResistors) {
            case NO: return netlistN;
            case PARASITIC: return netlistP;
            case ALL: return netlistA;
            default: throw new AssertionError();
        }
	}

	/**
	 * Get an iterator over all of the Nodables of this Cell.
	 */
	Iterator<Nodable> getNodables() { return cell.getNodables(); }

	/**
	 * Get a set of global signal in this Cell and its descendants.
	 */
	Global.Set getGlobals() { return Global.Set.empty; }

	/*
	 * Get offset in networks map for given global signal.
	 */
	int getNetMapOffset(Global global) { return -1; }

	/**
	 * Get offset in networks map for given global of nodable.
	 * @param no nodable.
	 * @param global global signal.
	 * @return offset in networks map.
	 */
    int getNetMapOffset(Nodable no, Global global) { return -1; }

	/**
	 * Get offset in networks map for given subnetwork of nodable.
	 * @param no nodable.
	 * @param equivPortIndex index of entry in equivPortsX
	 * @return offset in networks map.
	 */
    int getNetMapOffset(Nodable no, int equivPortIndex) {
        NodeInst ni = (NodeInst)no;
		return drawns[ni_pi[ni.getNodeIndex()] + equivPortIndex];
    }

	/*
	 * Get offset in networks map for given port instance.
	 */
	int getNetMapOffset(Nodable no, PortProto portProto, int busIndex) {
		NodeInst ni = (NodeInst)no;
		return drawns[ni_pi[ni.getNodeIndex()] + portProto.getPortIndex()];
	}

	/**
	 * Method to return the port width of port of the Nodable.
	 * @return the either the port width.
	 */
	int getBusWidth(Nodable no, PortProto portProto) { return 1; }

	/*
	 * Get offset in networks map for given export..
	 */
	int getNetMapOffset(Export export, int busIndex) {
		return drawns[export.getPortIndex()];
	}

	/*
	 * Get offset in networks map for given arc.
	 */
	int getNetMapOffset(ArcInst ai, int busIndex) {
		return getArcDrawn(ai);
	}

	/**
	 * Method to return either the network name or the bus name on this ArcInst.
	 * @return the either the network name or the bus name on this ArcInst.
	 */
	Name getBusName(ArcInst ai) { return null; }

	/**
	 * Method to return the bus width on this ArcInst.
	 * @return the either the bus width on this ArcInst.
	 */
	public int getBusWidth(ArcInst ai)
	{
		int drawn = getArcDrawn(ai);
		if (drawn < 0) return 0;
		return 1;
	}

    int getArcDrawn(ArcInst ai) {
        assert ai.getParent() == cell;
        int arcIndex = arcIndexByArcIdMap[ai.getArcId()];
        return drawns[arcsOffset + arcIndex];
    }

	private void initConnections() {
		int numPorts = cell.getNumPorts();
		int numNodes = cell.getNumNodes();
		int numArcs = cell.getNumArcs();
		if (ni_pi == null || ni_pi.length != numNodes)
			ni_pi = new int[numNodes];
		int offset = numPorts;
		for (int i = 0; i < numNodes; i++) {
			NodeInst ni = cell.getNode(i);
			ni_pi[i] = offset;
			offset += ni.getProto().getNumPorts();
		}
        arcIndexByArcIdMap = cell.getTopology().getArcIndexByArcIdMap();
		arcsOffset = offset;
		offset += numArcs;
		if (headConn == null || headConn.length != offset) {
			headConn = new int[offset];
			tailConn = new int[offset];
			drawns = new int[offset];
		}
		for (int i = numPorts; i < arcsOffset; i++) {
			headConn[i] = i;
			tailConn[i] = i;
		}
		for (int i = 0; i < numPorts; i++) {
			int portOffset = i;
			Export export = cell.getPort(i);
			int orig = getPortInstOffset(export.getOriginalPort());
			headConn[portOffset] = headConn[orig];
			headConn[orig] = portOffset;
			tailConn[portOffset] = -1;
		}
        int arcIndex = 0;
		for (Iterator<ArcInst> it = cell.getArcs(); arcIndex < numArcs; arcIndex++) {
			ArcInst ai = it.next();
			int arcOffset = arcsOffset + arcIndex;
			int head = getPortInstOffset(ai.getHeadPortInst());
			headConn[arcOffset] = headConn[head];
			headConn[head] = arcOffset;
			int tail = getPortInstOffset(ai.getTailPortInst());
			tailConn[arcOffset] = tailConn[tail];
			tailConn[tail] = arcOffset;
		}
		//showConnections();
	}

//	private void showConnections() {
//		int numNodes = cell.getNumNodes();
//		for (int i = 0; i < numNodes; i++) {
//			NodeInst ni = cell.getNode(i);
//			int numPortInsts = ni.getProto().getNumPorts();
//			for (int j = 0; j < numPortInsts; j++) {
//				PortInst pi = ni.getPortInst(j);
//				System.out.println("Connections of " + pi);
//				int piOffset = getPortInstOffset(pi);
//				for (int k = piOffset; headConn[k] != piOffset; ) {
//					k = headConn[k];
//					if (k >= arcsOffset)
//						System.out.println("\thead_arc\t" + cell.getArc(k - arcsOffset).describe(true));
//					else
//						System.out.println("\tport\t" + cell.getPort(k));
//				}
//				for (int k = piOffset; tailConn[k] != piOffset; ) {
//					k = tailConn[k];
//					System.out.println("\ttail_arc\t" + cell.getArc(k - arcsOffset).describe(true));
//				}
//			}
//		}
//	}

    private ArrayList<PortInst> stack;

	private void addToDrawn1(PortInst pi) {
		int piOffset = getPortInstOffset(pi);
		if (drawns[piOffset] >= 0) return;
		PortProto pp = pi.getPortProto();
		if (pp instanceof PrimitivePort && ((PrimitivePort)pp).isIsolated()) return;
		drawns[piOffset] = numDrawns;
		if (NetworkTool.debug) System.out.println(numDrawns + ": " + pi);

		for (int k = piOffset; headConn[k] != piOffset; ) {
			k = headConn[k];
			if (drawns[k] >= 0) continue;
			if (k < arcsOffset) {
				// This is port
				drawns[k] = numDrawns;
				if (NetworkTool.debug) System.out.println(numDrawns + ": " + cell.getPort(k));
				continue;
			}
			ArcInst ai = cell.getArc(k - arcsOffset);
			ArcProto ap = ai.getProto();
			if (ap.getFunction() == ArcProto.Function.NONELEC) continue;
			if (pp == busPinPort && ap != busArc) continue;
			drawns[k] = numDrawns;
			if (NetworkTool.debug) System.out.println(numDrawns + ": " + ai);
			PortInst tpi = ai.getTailPortInst();
			if (tpi.getPortProto() == busPinPort && ap != busArc) continue;
			stack.add(tpi);
		}
		for (int k = piOffset; tailConn[k] != piOffset; ) {
			k = tailConn[k];
			if (drawns[k] >= 0) continue;
			ArcInst ai = cell.getArc(k - arcsOffset);
			ArcProto ap = ai.getProto();
			if (ap.getFunction() == ArcProto.Function.NONELEC) continue;
			if (pp == busPinPort && ap != busArc) continue;
			drawns[k] = numDrawns;
			if (NetworkTool.debug) System.out.println(numDrawns + ": " + ai);
			PortInst hpi = ai.getHeadPortInst();
			if (hpi.getPortProto() == busPinPort && ap != busArc) continue;
			stack.add(hpi);
		}
	}

    private void addToDrawn(PortInst pi) {
        assert stack.isEmpty();
        stack.add(pi);
        while (!stack.isEmpty()) {
            pi = stack.remove(stack.size() - 1);
            PortProto pp = pi.getPortProto();
            NodeProto np = pp.getParent();
            int numPorts = np.getNumPorts();
            if (numPorts == 1 || np instanceof Cell) {
                addToDrawn1(pi);
                continue;
            }
            NodeInst ni = pi.getNodeInst();
            int topology = ((PrimitivePort)pp).getTopology();
            for (int i = 0; i < numPorts; i++) {
                if (((PrimitivePort)np.getPort(i)).getTopology() != topology) continue;
                addToDrawn1(ni.getPortInst(i));
            }
        }
    }

	void makeDrawns() {
		initConnections();
		Arrays.fill(drawns, -1);
        stack = new ArrayList<PortInst>();
		numDrawns = 0;
		for (int i = 0, numPorts = cell.getNumPorts(); i < numPorts; i++) {
			if (drawns[i] >= 0) continue;
			drawns[i] = numDrawns;
			Export export = cell.getPort(i);
			addToDrawn(export.getOriginalPort());
			numDrawns++;
		}
        numExportedDrawns = numDrawns;
		for (int i = 0, numArcs = cell.getNumArcs(); i < numArcs; i++) {
			if (drawns[arcsOffset + i] >= 0) continue;
			ArcInst ai = cell.getArc(i);
			ArcProto ap = ai.getProto();
			if (ap.getFunction() == ArcProto.Function.NONELEC) continue;
			drawns[arcsOffset + i] = numDrawns;
			if (NetworkTool.debug) System.out.println(numDrawns + ": " + ai);
			PortInst hpi = ai.getHeadPortInst();
			if (hpi.getPortProto() != busPinPort || ap == busArc)
				addToDrawn(hpi);
			PortInst tpi = ai.getTailPortInst();
			if (tpi.getPortProto() != busPinPort || ap == busArc)
				addToDrawn(tpi);
			numDrawns++;
		}