cellid.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: CellId.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.
 *
 * 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.id;

import com.sun.electric.database.EObjectInputStream;
import com.sun.electric.database.EObjectOutputStream;
import com.sun.electric.database.geometry.GenMath;
import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.hierarchy.EDatabase;
import com.sun.electric.database.text.CellName;

import java.io.IOException;
import java.io.NotSerializableException;
import java.io.Serializable;
import java.util.Arrays;
import java.util.Random;

/**
 * The CellId class identifies a type of NodeInst independently of threads.
 * It differs from Cell objects, which will be owned by threads in transactional database.
 * This class is thread-safe except inCurrentThread method in 1.5, but not thread-safe in 1.4  .
 */
public final class CellId implements NodeProtoId, Serializable {
    /** Empty CellId array for initialization. */
    public static final CellId[] NULL_ARRAY = {};

    /** IdManager which owns this LibId. */
    public final IdManager idManager;
    /** LibId which owns this CellId. */
    public final LibId libId;
    /** CellName of this CellId. */
    public final CellName cellName;
    /** Unique index of this cell in the database. */
    public final int cellIndex;
    /**
     * Usages of other proto subcells in this parent cell.
     * CellUsages are in chronological order by time of their creation.
     */
    private volatile CellUsage[] usagesIn = CellUsage.NULL_ARRAY;
    /**
     * Hash of usagesIn.
     * The size of nonempty hash is a prime number.
     * i-th entry of entry search sequence for a given protoId is ((protoId.hashCode() & 0x7FFFFFFF) + i*i) % hashUsagesIn.length .
     * This first (1 + hashUsagesIn.length/2) entries of this sequence are unique.
     * Invariant hashUsagesIn.length >= usagesIn.length*2 + 1 guaranties that there is at least one empty entry
     * in the search sequence.
     */
    private volatile CellUsage[] hashUsagesIn = EMPTY_USAGE_HASH;

    /**
     * Usages of this proto cell in other parent cells.
     * CellUsages are in chronological order by time of their creation.
     */
    private volatile CellUsage[] usagesOf = CellUsage.NULL_ARRAY;

    /**
     * Number of exportIds allocated so far.
     */
    private volatile int numExportIds = 0;
    /**
     * ExportIds of this cell. ExportIds have unique naems.
     * ExportIds are in cronological order by time of its creation.
     */
    private volatile ExportId[] exportIds = new ExportId[10];
    /**
     * Hash of ExportIds.
     * The size of nonempty hash is a prime number.
     * i-th entry of entry search sequence for a given exportId is ((exportId.hashCode() & 0x7FFFFFFF) + i*i) % hashExportIds.length .
     * This first (1 + hashExportIds.length/2) entries of this sequence are unique.
     * Invariant hashExportIds.length >= exportIds.length*2 + 1 guaranties that there is at least one empty entry
     * in the search sequence.
     */
    private volatile int[] hashExportIds = EMPTY_EXPORT_HASH;

    /**
     * Number of nodeIds returned by newNodeId.
     **/
    private volatile int numNodeIds = 0;

    /**
     * Number of arcIds returned by newArcId.
     **/
    private volatile int numArcIds = 0;

    /** Empty usage hash for initialization. */
    private static final CellUsage[] EMPTY_USAGE_HASH = { null };
    /** Empty usage hash for initialization. */
    private static final int[] EMPTY_EXPORT_HASH = { -1 };

    /**
     * CellId constructor.
     */
    CellId(LibId libId, CellName cellName, int cellIndex) {
        if (cellName.getVersion() <= 0)
            throw new IllegalArgumentException("cell version");
        idManager = libId.idManager;
        this.libId = libId;
        this.cellName = cellName;
        this.cellIndex = cellIndex;
    }

    private Object writeReplace() { return new CellIdKey(this); }

    private static class CellIdKey extends EObjectInputStream.Key<CellId> {
        public CellIdKey() {}
        private CellIdKey(CellId cellId) { super(cellId); }

        @Override
        public void writeExternal(EObjectOutputStream out, CellId cellId) throws IOException {
            if (cellId.idManager != out.getIdManager())
                throw new NotSerializableException(cellId + " from other IdManager");
            out.writeInt(cellId.cellIndex);
        }

        @Override
        public CellId readExternal(EObjectInputStream in) throws IOException, ClassNotFoundException {
            int cellIndex = in.readInt();
            return in.getIdManager().getCellId(cellIndex);
        }
    }

    /**
     * Returns IdManager which is owner of this CellId.
     * @return IdManager which is owner of this CellId.
     */
    public IdManager getIdManager() { return idManager; }

    /**
     * Returns a number CellUsages with this CellId as a parent cell.
     * This number may grow in time.
     * @return a number CellUsages with this CellId as a parent cell.
     */
    public int numUsagesIn() {
        // synchronized because usagesIn is volatile.
        return usagesIn.length;
    }

    /**
     * Returns the i-th in cronological order CellUsage with this CellId as a parent cell.
     * @param i chronological number of CellUsage.
     * @return i-th CellUsage with this CellId as a parent cell.
     * @throws ArrayIndexOutOfBoundsException if no such CellUsage.
     */
    public CellUsage getUsageIn(int i) {
        // synchronized because usagesIn is volatile and its entries are final.
        return usagesIn[i];
    }

    /**
     * Returns a number CellUsages whith this CellId as a proto subcell.
     * This mumber may grow in time.
     * @return a number CellUsages whith this CellId as a proto subcell.
     */
    public int numUsagesOf() {
        // synchronized because usagesOf is volatile.
        return usagesOf.length;
    }

    /**
     * Returns the i-th in cronological order CellUsage with this CellId as a proto subcell.
     * @param i chronological number of CellUsage.
     * @return i-th CellUsage with this CellId as a proto subcell.
     * @throws ArrayIndexOutOfBoundsException if no such CellUsage.
     */
    public CellUsage getUsageOf(int i) {
        // synchronized because usagesOf is volatile and its entries are final.
        return usagesOf[i];
    }

    /**
     * Returns CellUsage with this CellId as a parent cell and with given
     * CellId as a proto subcell. If this pair of cells is requested at a first time,
     * the new CellUsage is created, otherwise the early created CellUsage retruned.
     * @param protoId CellId of proto subcell.
     * @return CellUsage with this CellId as parent and protoId as a proto subcell.
     * @throws NullPointerException if prootId is null.
     */
    public CellUsage getUsageIn(CellId protoId) { return getUsageIn(protoId, true); }

    /**
     * Returns a number ExportIds in this parent cell.
     * This number may grow in time.
     * @return a number of ExportIds.
     */
    public int numExportIds() {
        // synchronized because numExportIds is volatile.
        return numExportIds;
    }

    /**
     * Returns ExportId in this parent cell with specified chronological index.
     * @param chronIndex chronological index of ExportId.
     * @return ExportId with specified chronological index.
     * @throws ArrayIndexOutOfBoundsException if no such ExportId.
     */
    public ExportId getPortId(int chronIndex) {
        // synchronized because exportIds is volatile and its entries are final.
        return exportIds[chronIndex];
    }

    /**
     * Returns ExportId in this parent cell with specified external id.
     * If this external id was requested earlier, the previously created ExportId returned,
     * otherwise the new ExportId is created.
     * @param externalId external id of ExportId.
     * @return ExportId with specified external id.
     * @throws NullPointerException if externalId is null.
     */
    public ExportId newPortId(String externalId) { return newExportId(externalId, true); }

    /**
     * Creates new random exportId, unique in this session for this parent CellId.
     * @param suggestedId suggested external id
     * @return new exportId.
     */
    public ExportId randomExportId(String suggestedId) {
        // Create random id
        String prefix = suggestedId;
        int ind = prefix.indexOf('@');
        if (ind >= 0)
            prefix = prefix.substring(0, ind + 1);
        else
            prefix = prefix + '@';
        Random random = new Random();
        for (;;) {
            int suffix = random.nextInt() & 0x3FFFFFFF;
            String s = prefix + suffix;
            synchronized (this) {
                if (newExportId(s, false) == null) {
                    return newExportId(s, true);
                }
            }
        }
    }

    /**
     * Returns new nodeId unique for this CellId.
     * @return new nodeId unique for this CellId.
     */
    public int newNodeId() { return numNodeIds++; }

    /**
     * Returns new arcId unique for this CellId.
     * @return new arcId unique for this CellId.
     */
    public int newArcId() { return numArcIds++; }

    /**
     * Method to return the Cell representing CellId in the specified EDatabase.
     * @param database EDatabase where to get from.
     * @return the Cell representing CellId in the specified database.
     * This method is not properly synchronized.
     */
    public Cell inDatabase(EDatabase database) { return database.getCell(this); }

    /**
     * Returns a printable version of this CellId.
     * @return a printable version of this CellId.
     */
    public String toString() {
        return libId + ":" + cellName.toString();
    }

	/**
	 * Method to determine whether this CellId is an id of an icon Cell.
	 * @return true if this CellId is an id of an icon Cell.
	 */
    public boolean isIcon() {
        return cellName.isIcon();
    }

	/**
	 * Method to determine whether this CellId is an id of an schematic Cell.
	 * @return true if this CellId is an id of an schematic Cell.
	 */
    public boolean isSchematic() {
        return cellName.isSchematic();
    }

    /**
     * Returns CellUsage with this CellId as a parent cell and with given
     * CellId as a proto subcell. If CellUsage with this pair of cells was already created,
     * it is returned. Otherwise the null is retruned when create=false and new CellUsage is
     * returned if create=true .
     * @param protoId CellId of proto subcell.
     * @return CellUsage with this CellId as parent and protoId as a proto subcell.
     * @throws NullPointerException if protoId is null.
     */
    CellUsage getUsageIn(CellId protoId, boolean create) {
        // The hashUsagesIn array is created in "rehashUsagesIn" method inside synchronized block.
        // "rehash" fills some entris leaving null in others.
        // All entries filled in rehashUsagesIn() are final.
        // However other threads may change initially null entries to non-null value.
        // This non-null value is final.
        // First we scan a sequence of non-null entries out of synchronized block.