cellid.java

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

        // It is guaranteed that we see the correct values of non-null entries.

        // Get poiner to hash array locally once to avoid many reads of volatile variable.
        CellUsage[] hash = hashUsagesIn;

        // We shall try to search a sequence of non-null entries for CellUsage with our protoId.
        int i = protoId.hashCode() & 0x7FFFFFFF;
        i %= hash.length;
        for (int j = 1; hash[i] != null; j += 2) {
            CellUsage u = hash[i];

            // We scanned a seqence of non-null entries and found the result.
            // It is correct to return it without synchronization.
            if (u.protoId == protoId) return u;

            i += j;
            if (i >= hash.length) i -= hash.length;
        }

        // Need to enter into the synchronized mode.
        synchronized (CellUsage.class) {

            if (hash == hashUsagesIn && hash[i] == null) {
                // There we no rehash during our search and the last null entry is really null.
                // So we can safely use results of unsynchronized search.
                if (!create) return null;

                if (usagesIn.length*2 <= hash.length - 3) {
                    // create a new CellUsage, if enough space in the hash
                    CellUsage u = new CellUsage(this, protoId, usagesIn.length);
                    hash[i] = u;
                    usagesIn = appendUsage(usagesIn, u);
                    protoId.usagesOf = appendUsage(protoId.usagesOf, u);
                    check();
                    return u;
                }
                // enlarge hash if not
                rehashUsagesIn();
            }
            // retry in synchronized mode.
            return getUsageIn(protoId, create);
        }
    }

    /**
     * Rehash the usagesIn hash.
     * @throws IndexOutOfBoundsException on hash overflow.
     * This method may be called only inside synchronized block.
     */
    private void rehashUsagesIn() {
        CellUsage[] usagesIn = this.usagesIn;
        int newSize = usagesIn.length*2 + 3;
        if (newSize < 0) throw new IndexOutOfBoundsException();
        CellUsage[] newHash = new CellUsage[GenMath.primeSince(newSize)];
        for (int k = usagesIn.length - 1; k >= 0; k--) {
            CellUsage u = usagesIn[k];
            int i = u.protoId.hashCode() & 0x7FFFFFFF;
            i %= newHash.length;
            for (int j = 1; newHash[i] != null; j += 2) {
                i += j;
                if (i >= newHash.length) i -= newHash.length;
            }
            newHash[i] = u;
        }
        hashUsagesIn = newHash;
        check();
    }

    /**
     * Returns ExportId in this parent cell with specified external id.
     * If such ExportId doesn't exist returns null.
     * @param externalId external id of ExportId.
     * @return ExportId with specified external id or null.
     * @throws ArrayIndexOutOfBoundsException if no such ExportId.
     */
    private ExportId newExportId(String externalId, boolean create) {
        // The hashExportIds array is created in "rehashExportIds" method inside synchronized block.
        // "rehash" fills some entries leaving -1 in others.
        // All entries filled in rehashExportIds() are final.
        // However other threads may change initially -1 entries to positive value.
        // This positive value is final.
        // First we scan a sequence of positive entries out of synchronized block.
        // It is guaranteed that we see the correct values of positive entries.
        // All entries in exportIds are final

        // Get pointer to hash array locally once to avoid many reads of volatile variable.
        int[] hash = hashExportIds;
        ExportId[] exportIds = this.exportIds;
        // We shall try to search a sequence of non-null entries for CellUsage with our protoId.
        int i = externalId.hashCode() & 0x7FFFFFFF;
        i %= hash.length;
        try {
            for (int j = 1; hash[i] >= 0; j += 2) {
                ExportId exportId = exportIds[hash[i]];
                if (exportId.externalId.equals(externalId)) return exportId;
                i += j;
                if (i >= hash.length) i -= hash.length;
            }
        } catch (ArrayIndexOutOfBoundsException e) {
            // This may happen if some hash entries were concurrently filled with index out of ExportId range.
        }
        synchronized (this) {
            if (hash == hashExportIds && hash[i] == -1) {
                // There we no rehash during our search and the last -1 entry is really -1.
                // So we are sure that there is not ExportId with specified external id.
                if (!create) return null;

                int chronIndex = numExportIds;
                exportIds = this.exportIds;
                if (chronIndex*2 <= hash.length - 3) {
                    ExportId e = new ExportId(this, chronIndex, externalId);
                    hash[i] = chronIndex;
                    if (chronIndex >= exportIds.length) {
                        assert chronIndex == exportIds.length;
                        int newLength = (int)Math.min(exportIds.length*3L/2 + 1, Integer.MAX_VALUE);
                        ExportId[] newExportIds = new ExportId[newLength];
                        System.arraycopy(exportIds, 0, newExportIds, 0, chronIndex);
                        exportIds = newExportIds;
                    }
                    exportIds[chronIndex] = e;
                    this.exportIds = exportIds;
                    hashExportIds = hash;
                    numExportIds = chronIndex + 1;
                    return e;
                }
                // enlarge hash if not
                rehashExportIds(exportIds, numExportIds);
            }
            // retry in synchronized mode.
            return newExportId(externalId, create);
        }
    }

    /**
     * Rehash the exportIds hash.
     * @throws IndexOutOfBoundsException on hash overflow.
     * This method may be called only inside synchronized block.
     */
    private void rehashExportIds(ExportId[] exportIds, int numExports) {
        int newSize = exportIds.length*2 + 3;
        if (newSize < 0) throw new IndexOutOfBoundsException();
        int[] newHash = new int[GenMath.primeSince(newSize)];
        Arrays.fill(newHash, -1);
        for (int k = 0; k < numExports; k++) {
            ExportId exportId = exportIds[k];
            int i = exportId.hashCode() & 0x7FFFFFFF;
            i %= newHash.length;
            for (int j = 1; newHash[i] >= 0; j += 2) {
                assert exportIds[newHash[i]] != exportId;
                i += j;
                if (i >= newHash.length) i -= newHash.length;
            }
            newHash[i] = k;
        }
        hashExportIds = newHash;
        check();
    }

    /**
     * Append usage to the end of array.
     * @param usages array of usages.
     * @param newUsage new CellUsage.
     * @return array with new usage appended.
     */
    private static CellUsage[] appendUsage(CellUsage[] usages, CellUsage newUsage) {
        CellUsage[] newUsages = new CellUsage[usages.length + 1];
        System.arraycopy(usages, 0, newUsages, 0, usages.length);
        newUsages[usages.length] = newUsage;
        return newUsages;
    }

    /**
     * Checks invariants in this CellId.
     * ALL i: usagesIn[i].parentId == this;
     * ALL i: usagesIn[i].indexInParent == i;
     * ALL i, j: i != j IMPLIES usagesIn[i].protoId != usagesIn[i].protoId;
     *
     * ALL i: usagesOf[i].protoId == this;
     * ALL i, j: i != j IMPLIES usagesOf[i].parentId != usagesIn[j].parentId;
     *
     * hashUsagesIn[*] is a correct hash map CellUsage.protoId -> CellUsage;
     * hashUsagesIn[*] and usagesIn[*] are equal sets of CellUsages;
     *
     * ALL i: exportIds[i].parentId == this;
     * ALL i: exportIds[i].chronIndex == i;
     * This CellId, all usagesIn[*].protoId and all usagesOf[*].parentId are linked in
     *    static list of all CellIds;
     *
     * @exception AssertionError if invariants are not valid
     */
    void check() {
        checkLinked();
        assert idManager == libId.idManager;
        cellName.check();
        assert cellName.getVersion() > 0;
        assert libId.getCellId(cellName) == this;

        CellUsage[] usagesIn = this.usagesIn;
        for (int k = 0; k < usagesIn.length; k++) {
            CellUsage u = usagesIn[k];

            // Check that this CellUsage is properly owned and has proper indexInParent.
            // This also guarantees that all elements of usagesIn are distinct.
            assert u.parentId == this;
            assert u.indexInParent == k;
            assert u.protoId.getIdManager() == getIdManager();
            u.protoId.checkLinked();

            // Check the CellUsage invariants.
            // One of them guarantees that all CellUsages
            // in usagesIn have distinct parentIds.
            // It checks also that "u" is in hashUsageIn
            u.check();
        }

        // Check that hashUsagesIn contains without duplicates the same set of CellUsages as
        checkHashUsagesIn();
        // Check that hashExportIds has exportIds.length entries
        checkHashExportIds();

        // Check CellUsages in usagesOf array.
        // No need synchronization because usagesOf is volatile field.
        CellUsage[] usagesOf = this.usagesOf;
        for (int k = 0; k < usagesOf.length; k++) {
            CellUsage u = usagesOf[k];

            // Check that this CellUsage is properly owned by its parentId and
            // the parentId is in static list of all CellIds.
            assert u.protoId.getIdManager() == getIdManager();
            u.parentId.checkLinked();
            assert u == u.parentId.usagesIn[u.indexInParent];
        }

        int numExportIds = this.numExportIds;
        for (int chronIndex = 0; chronIndex < numExportIds; chronIndex++) {
            ExportId e = exportIds[chronIndex];
            assert e.parentId == this;
            assert e.chronIndex == chronIndex;
            assert newExportId(e.externalId, false) == e;
            e.check();
        }
    }

    /**
     * Check that usagesIn and hashUsagesIn contains the same number of CellUsages.
     * It checks also that each CellUsage from hashUsagesIn is in usagesIn.
     */
    private void checkHashUsagesIn() {
        CellUsage[] usagesIn;
        CellUsage[] hash;
        synchronized (CellUsage.class) {
            usagesIn = this.usagesIn;
            hash = this.hashUsagesIn;
        }
        int count = 0;
        for (int i = 0; i < hash.length; i++) {
            CellUsage u = hash[i];
            if (u == null) continue;
            assert u.parentId == this;
            assert u == usagesIn[u.indexInParent];
            count++;
        }
        assert usagesIn.length == count;
    }

    /**
     * Check that exportIds and hashExportIds contains the same number of ExportIds.
     */
    private void checkHashExportIds() {
        ExportId[] exportIds;
        int[] hash;
        synchronized (this) {
            exportIds = this.exportIds;
            hash = this.hashExportIds;
        }
        int count = 0;
        for (int i = 0; i < hash.length; i++) {
            int k = hash[i];
            if (k == -1) continue;
            assert k >= 0 && k < exportIds.length;
            count++;
        }
        assert numExportIds == count;
    }

    /**
     * Check that this CellId is linked in static list of all CellIds.
     * @throws AssertionError if this CellId is not linked.
     */
    private void checkLinked() {
        assert this == getIdManager().getCellId(cellIndex);
    }

    public static void main(String[] args) {
        IdManager idManager = new IdManager();
        LibId libId = idManager.newLibId("lib");
        CellName cellName = CellName.parseName("cell;1{sch}");
        CellId cellId = libId.newCellId(cellName);
        cellId.hashExportIds = new int[8];
        Arrays.fill(cellId.hashExportIds, -1);
        cellId.newPortId("A");
        String s = "B";
        cellId.newPortId(s);

        long startTime = System.currentTimeMillis();
        int numTries = 100*1000*1000;
        int k = 0;
        for (int i = 0; i < numTries; i++) {
            ExportId eId = cellId.newPortId(s);
            k += eId.chronIndex;
        }
        long stopTime = System.currentTimeMillis();
        System.out.println("k=" + k + " t=" + (stopTime - startTime));
    }
}