netlist.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: Netlist.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.hierarchy.Export;
import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.hierarchy.Nodable;
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.PortInst;
import com.sun.electric.database.topology.NodeInst;

import java.util.Arrays;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;

/**
 * This is the Netlist class. It contains information about electric
 * networks of a cell for a given set of options. Networks are 0-based
 * indices. First positions occupies indices of networks connected to
 * global signals, then networks connected to exports, and then local
 * networks.
 */
public abstract class Netlist
{
    /** Enumaration defines mode of short resistors in Netlist. */
    public enum ShortResistors {
        /** No resistors are shortened */                       NO,
        /** Resistors are shortened except poly resistors */    PARASITIC,
        /** All resistors are shortened */                      ALL
    };

	// -------------------------- private data ---------------------------------

	/** NetCell which owns this Netlist. */
	NetCell netCell;
    ShortResistors shortResistors;
//    HashMap/*<Cell,Netlist>*/ subNetlists;

	/**
	 * The modCount value that the netlist believes that the backing
	 * netCell should have.  If this expectation is violated, the netlist
	 * has detected concurrent modification.
	 */
	int expectedModCount;

	/** An equivalence map of PortInsts and NetNames. */
	final int[] netMap;
	final int[] nm_net;

	/** An array of Networks in this Cell. */
	private Network[] networks;
    int numExternalEntries;
    int numExternalNets;

	// ---------------------- package methods -----------------

	/**
	 * The constructor of Netlist object..
	 */
	Netlist(NetCell netCell, ShortResistors shortResistors, int numExternals, int[] map) {
		this.netCell = netCell;
        this.shortResistors = shortResistors;
//        this.subNetlists = subNetlists;
		expectedModCount = netCell.modCount;
		netMap = map;
		nm_net = new int[netMap.length];

		closureMap(netMap);
		int k = 0;
		for (int i = 0; i < netMap.length; i++) {
			if (netMap[i] == i) k++;
		}
		networks = new Network[k];

        numExternalEntries = numExternals;
		k = 0;
		for (int i = 0; i < netMap.length; i++) {
			if (netMap[i] == i) {
				nm_net[i] = k;
				k++;
                if (i < numExternals)
                    numExternalNets++;
			} else {
				nm_net[i] = nm_net[netMap[i]];
			}
		}
	}

	/**
	 * Init equivalence map.
     * @param size numeber of elements in equivalence map
     * @return integer array representing equivalence map consisting of disjoint elements.
	 */
    static int[] initMap(int size) {
        int[] map = new int[size];
		for (int i = 0; i < map.length; i++) map[i] = i;
        return map;
    }

	/**
	 * Merge classes of equivalence map to which elements a1 and a2 belong.
	 */
	static void connectMap(int[] map, int a1, int a2)
	{
		int m1, m2, m;

		for (m1 = a1; map[m1] != m1; m1 = map[m1]);
		for (m2 = a2; map[m2] != m2; m2 = map[m2]);
		m = m1 < m2 ? m1 : m2;

		for (;;)
		{
			int k = map[a1];
			map[a1] = m;
			if (a1 == k) break;
			a1 = k;
		}
		for (;;)
		{
			int k = map[a2];
			map[a2] = m;
			if (a2 == k) break;
			a2 = k;
		}
	}

	/**
	 * Obtain canonical representation of equivalence map.
	 */
	static void closureMap(int[] map)
	{
		for (int i = 0; i < map.length; i++)
		{
			map[i] = map[map[i]];
		}
	}

	/**
	 * Obtain canonical representation of equivalence map.
	 */
//	private static boolean equalMaps(int[] map1, int[] map2)
//	{
//		if (map1.length != map2.length) return false;
//		for (int i = 0; i < map1.length; i++)
//		{
//			if (map1[i] != map2[i]) return false;
//		}
//		return true;
//	}

    /** A cell of this netlist. */
    public Cell getCell() { return netCell.cell; }

    /** A net can have multiple names. Return alphabetized list of names. */
    abstract Iterator<String> getNames(int netIndex);

    /** A net can have multiple names. Return alphabetized list of names. */
    abstract Iterator<String> getExportedNames(int netIndex);

    /**
     * Returns most appropriate name of the net.
     * Intitialized net has at least one name - user-defiend or temporary.
     */
    abstract String getName(int netIndex);

    /** Returns true if nm is one of Network's names */
    abstract boolean hasName(int netIndex, String nm);

    /**
     * Add names of this net to two Collections. One for exported, and other for unexported names.
     * @param exportedNames Collection for exported names.
     * @param privateNames Collection for unexported names.
     */
    abstract void fillNames(int netIndex, Collection<String> exportedNames, Collection<String> privateNames);

    /**
     * Method to tell whether this network has any exports or globals on it.
     * @return true if there are exports or globals on this Network.
     */
    boolean isExported(int netIndex) { return netIndex < numExternalNets; }

    /**
     * Method to tell whether this network has user-defined name.
     * @return true if this Network has user-defined name.
     */
    abstract boolean isUsernamed(int netIndex);

	int getNetIndexByMap(int mapOffset) { return nm_net[mapOffset]; }

    abstract int getEquivPortIndexByNetIndex(int netIndex);

	private final void checkForModification() {
		if (expectedModCount != netCell.modCount)
			throw new ConcurrentModificationException();
	}

	// ---------------------- public methods -----------------

    // JKG: trying this out
	/**
	 * Returns Nodable for given NodeInst and array index.
	 * The Nodable is NodeInst itself for primitives and layout subcells.
	 * The Nodable is a proxy nodable for icon instances.
	 * @param ni node instance
	 * @param arrayIndex array index for arrayed icons or zero.
	 * @return Nodable for given NodeInst and array index.
	 */
    public static Nodable getNodableFor(NodeInst ni, int arrayIndex) {
        Cell parent = ni.getParent();
        NetworkManager networkManager = parent.getDatabase().getNetworkManager();
		NetCell netCell = networkManager.getNetCell(parent);
		if (netCell == null) return null;
//        Netlist netlist = NetworkTool.getUserNetlist(parent);
        for (Iterator<Nodable> it = netCell.getNodables(); it.hasNext(); ) {
//        for (Iterator<Nodable> it = netlist.getNodables(); it.hasNext(); ) {
            Nodable no = it.next();
            if (no.contains(ni, arrayIndex)) return no;
        }
        return null;
    }

	/**
	 * Get an iterator over all of the Nodables of this Cell.
	 * <p> Warning: before getNodables() is called, Networks must be
	 * build by calling Cell.rebuildNetworks()
	 */
	public Iterator<Nodable> getNodables() {
		checkForModification();
		return netCell.getNodables();
	}

	/**
	 * Returns subnetlist for a given Nodable.
	 * @param no Nadable in this Netlist
	 * @return subnetlist for a given Nidable.
	 */
	public Netlist getNetlist(Nodable no) {
		if (!no.isCellInstance()) return null;
        return netCell.networkManager.getNetCell((Cell)no.getProto()).getNetlist(shortResistors);
//		return subNetlists.get(no.getProto());
	}

	/**
	 * Returns set of global signals in this Netlist.
	 * @return set of global signals in this Netlist.
	 */
	public Global.Set getGlobals() {
		checkForModification();
		return netCell.getGlobals();
	}

	/**
	 * Get number of networks in this Netlist.
	 * @return number of networks in this Netlist.
	 */
	public int getNumNetworks() {
		checkForModification();
		return networks.length;
	}

	/**
	 * Get number of networks in this Netlist, which are
     * connected to exports or globals.
	 * @return number of external networks in this Netlist.
	 */
	public int getNumExternalNetworks() {
		checkForModification();
		return numExternalNets;
	}

	/**
	 * Get Network with specified index.
	 * @param netIndex index of Network
	 * @return Network with specified index.
	 */
	public Network getNetwork(int netIndex) {
		checkForModification();
		return getNetworkRaw(netIndex);
	}

	/**
	 * Get Network with specified index.
     * If Network was not allocated yet, allocate it.
	 * @param netIndex index of Network
	 * @return Network with specified index.
	 */
    private Network getNetworkRaw(int netIndex) {
		if (netIndex < 0) return null;
        Network network = networks[netIndex];
        if (network != null) {
            return network;
        }
        network = new Network(this, netIndex);

        // Check if concurrent thread allocated this network also
        // This code is not properly synchronized !!!!!!
        if (networks[netIndex] != null)
            return networks[netIndex];
        networks[netIndex] = network;
        return network;
    }

   	/**
	 * Get an iterator over all of the Networks of this Netlist.
	 */
	public Iterator<Network> getNetworks() {
		checkForModification();
        for (int netIndex = 0; netIndex < networks.length; netIndex++) {
            if (networks[netIndex] == null)
                getNetworkRaw(netIndex);
        }
		return Arrays.asList(networks).iterator();
	}

	/**
	 * Get net index of a global signal.
	 * @param global global signal.
	 * @return net index of a gloabal signal.
	 */
	int getNetIndex(Global global) {
		checkForModification();