JDK14/Java14源码在线阅读

/*
 * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code 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
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package jdk.nashorn.internal.runtime;

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import jdk.nashorn.internal.runtime.options.Options;

/**
 * Immutable hash map implementation for properties. Properties are keyed on strings
 * or symbols (ES6). Copying and cloning is avoided by relying on immutability.
 * <p>
 * When adding an element to a hash table, only the head of a bin list is updated, thus
 * an add only requires the cloning of the bins array and adding an element to the head
 * of the bin list.  Similarly for removal, only a portion of a bin list is updated.
 * <p>
 * For large tables with hundreds or thousands of elements, even just cloning the bins
 * array when adding properties is an expensive operation. For this case, we put new
 * elements in a separate list called {@link ElementQueue}.
 * The list component is merged into the hash table at regular intervals during element
 * insertion to keep it from growing too long. Also, when a map with a queue component
 * is queried repeatedly, the map will replace itself with a pure hash table version
 * of itself to optimize lookup performance.
 * <p>
 * A separate chronological list is kept for quick generation of keys and values, and,
 * for rehashing. For very small maps where the overhead of the hash table would
 * outweigh its benefits we deliberately avoid creating a hash structure and use the
 * chronological list alone for element storage.
 * <p>
 * Details:
 * <p>
 * The main goal is to be able to retrieve properties from a map quickly, keying on
 * the property name (String or Symbol). A secondary, but important goal, is to keep
 * maps immutable, so that a map can be shared by multiple objects in a context.
 * Sharing maps allows objects to be categorized as having similar properties, a
 * fact that call site guards rely on.  In this discussion, immutability allows us
 * to significantly reduce the amount of duplication we have in our maps.
 * <p>
 * The simplest of immutable maps is a basic singly linked list.  New properties
 * are simply added to the head of the list.  Ancestor maps are not affected by the
 * addition, since they continue to refer to their own head.  Searching is done by
 * walking linearly though the elements until a match is found, O(N).
 * <p>
 * A hash map can be thought of as an optimization of a linked list map, where the
 * linked list is broken into fragments based on hashCode(key) .  An array is use
 * to quickly reference these fragments, indexing on hashCode(key) mod tableSize
 * (tableSize is typically a power of 2 so that the mod is a fast masking
 * operation.)  If the size of the table is sufficient large, then search time
 * approaches O(1).  In fact, most bins in a hash table are typically empty or
 * contain a one element list.
 * <p>
 * For immutable hash maps, we can think of the hash map as an array of the shorter
 * linked list maps.  If we add an element to the head of one of those lists,  it
 * doesn't affect any ancestor maps.  Thus adding an element to an immutable hash
 * map only requires cloning the array and inserting an element at the head of one
 * of the bins.
 * <p>
 * Using Java HashMaps we don't have enough control over the entries to allow us to
 * implement this technique, so we are forced to clone the entire hash map.
 * <p>
 * Removing elements is done similarly.  We clone the array and then only modify
 * the bin containing the removed element.  More often than not, the list contains
 * only one element (or is very short), so this is not very costly.  When the list
 * has several items, we need to clone the list portion prior to the removed item.
 * <p>
 * Another requirement of property maps is that we need to be able to gather all
 * properties in chronological (add) order.  We have been using LinkedHashMap to
 * provide this.  For the implementation of immutable hash map, we use a singly
 * linked list that is linked in reverse chronological order.  This means we simply
 * add new entries to the head of the list.  If we need to work with the list in
 * forward order, it's simply a matter of allocating an array (size is known) and
 * back filling in reverse order.  Removal of elements from the chronological list
 * is trickier.  LinkedHashMap uses a doubly linked list to give constant time
 * removal. Immutable hash maps can't do that and maintain immutability.  So we
 * manage the chronological list the same way we manage the bins, cloning up to the
 * point of removal.  Don't panic.  This cost is more than offset by the cost of
 * cloning an entire LinkedHashMap.  Plus removal is far more rare than addition.
 * <p>
 * One more optimization.  Maps with a small number of entries don't use the hash
 * map at all, the chronological list is used instead.
 * <p>
 * So the benefits from immutable arrays are; fewer objects and less copying.  For
 * immutable hash map, when no removal is involved, the number of elements per
 * property is two (bin + chronological elements).  For LinkedHashMap it is one
 * (larger element) times the number of maps that refer to the property.  For
 * immutable hash map, addition is constant time.  For LinkedHashMap it's O(N+C)
 * since we have to clone the older map.
 */
public final class PropertyHashMap implements Map <Object, Property> {
    /** Number of initial bins. Power of 2. */
    private static final int INITIAL_BINS = 32;

    /** Threshold before using bins. */
    private static final int LIST_THRESHOLD = 8;

    /** Threshold before adding new elements to queue instead of directly adding to hash bins. */
    private static final int QUEUE_THRESHOLD = Options.getIntProperty("nashorn.propmap.queue.threshold", 500);

    /** Initial map. */
    public static final PropertyHashMap EMPTY_HASHMAP = new PropertyHashMap();

    /** Number of properties in the map. */
    private final int size;

    /** Threshold before growing the bins. */
    private final int threshold;

    /** Reverse list of all properties. */
    private final Element list;

    /** Hash map bins. */
    private Element[] bins;

    /** Queue for adding elements to large maps with delayed hashing. */
    private ElementQueue queue;

    /** All properties as an array (lazy). */
    private Property[] properties;

    /**
     * Empty map constructor.
     */
    private PropertyHashMap() {
        this.size      = 0;
        this.threshold = 0;
        this.bins      = null;
        this.queue     = null;
        this.list      = null;
    }

    /**
     * Constructor used internally to create new maps
     *
     * @param map the new map
     */
    private PropertyHashMap(final MapBuilder map) {
        this.size      = map.size;
        if (map.qhead == null) {
            this.bins = map.bins;
            this.queue = null;
        } else {
            this.bins = null;
            this.queue = new ElementQueue(map.qhead, map.bins);
        }
        this.list      = map.list;
        this.threshold = map.bins != null ? threeQuarters(map.bins.length) : 0;
    }

    /**
     * Clone a property map, replacing a property with a new one in the same place,
     * which is important for property iterations if a property changes types
     * @param property    old property
     * @param newProperty new property
     * @return new property map
     */
    public PropertyHashMap immutableReplace(final Property property, final Property newProperty) {
        assert property.getKey().equals(newProperty.getKey()) : "replacing properties with different keys: '" + property.getKey() + "' != '" + newProperty.getKey() + "'";
        assert findElement(property.getKey()) != null         : "replacing property that doesn't exist in map: '" + property.getKey() + "'";
        final MapBuilder builder = newMapBuilder(size);
        builder.replaceProperty(property.getKey(), newProperty);
        return new PropertyHashMap(builder);
    }

    /**
     * Clone a {@link PropertyHashMap} and add a {@link Property}.
     *
     * @param property {@link Property} to add.
     *
     * @return New {@link PropertyHashMap}.
     */
    public PropertyHashMap immutableAdd(final Property property) {
        final int newSize = size + 1;
        MapBuilder builder = newMapBuilder(newSize);
        builder.addProperty(property);
        return new PropertyHashMap(builder);
    }

    /**
     * Clone a {@link PropertyHashMap} and add an array of properties.
     *
     * @param newProperties Properties to add.
     *
     * @return New {@link PropertyHashMap}.
     */
    public PropertyHashMap immutableAdd(final Property... newProperties) {
        final int newSize = size + newProperties.length;
        MapBuilder builder = newMapBuilder(newSize);
        for (final Property property : newProperties) {
            builder.addProperty(property);
        }
        return new PropertyHashMap(builder);
    }

    /**
     * Clone a {@link PropertyHashMap} and add a collection of properties.
     *
     * @param newProperties Properties to add.
     *
     * @return New {@link PropertyHashMap}.
     */
    public PropertyHashMap immutableAdd(final Collection<Property> newProperties) {
        if (newProperties != null) {
            final int newSize = size + newProperties.size();
            MapBuilder builder = newMapBuilder(newSize);
            for (final Property property : newProperties) {
                builder.addProperty(property);
            }
            return new PropertyHashMap(builder);
        }
        return this;
    }

    /**
     * Clone a {@link PropertyHashMap} and remove a {@link Property} based on its key.
     *
     * @param key Key of {@link Property} to remove.
     *
     * @return New {@link PropertyHashMap}.
     */
    public PropertyHashMap immutableRemove(final Object key) {
        MapBuilder builder = newMapBuilder(size);
        builder.removeProperty(key);
        if (builder.size < size) {
            return builder.size != 0 ? new PropertyHashMap(builder) : EMPTY_HASHMAP;
        }
        return this;
    }

    /**
     * Find a {@link Property} in the {@link PropertyHashMap}.
     *
     * @param key Key of {@link Property} to find.
     *
     * @return {@link Property} matching key or {@code null} if not found.
     */
    public Property find(final Object key) {
        final Element element = findElement(key);
        return element != null ? element.getProperty() : null;
    }

    /**
     * Return an array of properties in chronological order of adding.
     *
     * @return Array of all properties.
     */
    Property[] getProperties() {
        if (properties == null) {
            final Property[] array = new Property[size];
            int i = size;
            for (Element element = list; element != null; element = element.getLink()) {
                array[--i] = element.getProperty();
            }
            properties = array;
        }
        return properties;
    }

    /**
     * Returns the bin index from the key.
     *
     * @param bins     The bins array.
     * @param key      {@link Property} key.
     *
     * @return The bin index.
     */
    private static int binIndex(final Element[] bins, final Object key) {
        return  key.hashCode() & bins.length - 1;
    }

    /**
     * Calculate the number of bins needed to contain n properties.
     *
     * @param n Number of elements.
     *
     * @return Number of bins required.
     */
    private static int binsNeeded(final int n) {
        // 50% padding
        return 1 << 32 - Integer.numberOfLeadingZeros(n + (n >>> 1) | INITIAL_BINS - 1);
    }

    /**
     * Used to calculate the current capacity of the bins.
     *
     * @param n Number of bin slots.
     *
     * @return 75% of n.
     */
    private static int threeQuarters(final int n) {
        return (n >>> 1) + (n >>> 2);
    }

    /**
     * Regenerate the bin table after changing the number of bins.
     *
     * @param list    // List of all properties.
     * @param binSize // New size of bins.
     *
     * @return Populated bins.
     */
    private static Element[] rehash(final Element list, final int binSize) {
        final Element[] newBins = new Element[binSize];
        for (Element element = list; element != null; element = element.getLink()) {
            final Property property = element.getProperty();
            final Object   key      = property.getKey();
            final int      binIndex = binIndex(newBins, key);

            newBins[binIndex] = new Element(newBins[binIndex], property);
        }
        return newBins;
    }

    /**
     * Locate an element based on key.
     *
     * @param key {@link Element} key.
     *
     * @return {@link Element} matching key or {@code null} if not found.
     */
    private Element findElement(final Object key) {
        if (queue != null) {
            return queue.find(key);
        } else if (bins != null) {
            final int binIndex = binIndex(bins, key);
            return findElement(bins[binIndex], key);
        }
        return findElement(list, key);
    }

    /**
     * Locate an {@link Element} based on key from a specific list.
     *
     * @param elementList Head of {@link Element} list
     * @param key         {@link Element} key.
     * @return {@link Element} matching key or {@code null} if not found.
     */
    private static Element findElement(final Element elementList, final Object key) {
        final int hashCode = key.hashCode();
        for (Element element = elementList; element != null; element = element.getLink()) {
            if (element.match(key, hashCode)) {
                return element;
            }
        }
        return null;
    }

    /**
     * Create a {@code MapBuilder} to add new elements to.
     *
     * @param newSize New size of {@link PropertyHashMap}.
     *
     * @return {@link MapBuilder} for the new size.
     */
    private MapBuilder newMapBuilder(final int newSize) {
        if (bins == null && newSize < LIST_THRESHOLD) {
            return new MapBuilder(bins, list, size, false);
        } else if (newSize > threshold) {
            return new MapBuilder(rehash(list, binsNeeded(newSize)), list, size, true);
        } else if (shouldCloneBins(size, newSize)) {
            return new MapBuilder(cloneBins(), list, size, true);
        } else if (queue == null) {
            return new MapBuilder(bins, list, size, false);
        } else {
            return new MapBuilder(queue, list, size, false);
        }
    }

    /**
     * Create a cloned or new bins array and merge the elements in the queue into it if there are any.
     *
     * @return the cloned bins array
     */
    private Element[] cloneBins() {
        if (queue != null) {
            return queue.cloneAndMergeBins();
        }

        return bins.clone();
    }

    /**
     * Used on insertion to determine whether the bins array should be cloned, or we should keep
     * using the ancestor's bins array and put new elements into the queue.
     *
     * @param oldSize the old map size
     * @param newSize the new map size
     * @return whether to clone the bins array
     */
    private boolean shouldCloneBins(final int oldSize, final int newSize) {
        // For maps with less than QUEUE_THRESHOLD elements we clone the bins array on every insertion.
        // Above that threshold we put new elements into the queue and only merge every 512  elements.
        return newSize < QUEUE_THRESHOLD || (newSize >>> 9) > (oldSize >>> 9);
    }

    /**
     * Removes an {@link Element} from a specific list, avoiding duplication.
     *
     * @param list List to remove from.
     * @param key  Key of {@link Element} to remove.
     *
     * @return New list with {@link Element} removed.
     */
    private static Element removeFromList(final Element list, final Object key) {
        if (list == null) {
            return null;
        }
        final int hashCode = key.hashCode();
        if (list.match(key, hashCode)) {
            return list.getLink();
        }
        final Element head = new Element(null, list.getProperty());
        Element previous = head;
        for (Element element = list.getLink(); element != null; element = element.getLink()) {
            if (element.match(key, hashCode)) {
                previous.setLink(element.getLink());
                return head;
            }
            final Element next = new Element(null, element.getProperty());
            previous.setLink(next);
            previous = next;
        }
        return list;
    }

    // for element x. if x get link matches,
    private static Element replaceInList(final Element list, final Object key, final Property property) {
        assert list != null;
        final int hashCode = key.hashCode();

        if (list.match(key, hashCode)) {
            return new Element(list.getLink(), property);
        }

        final Element head = new Element(null, list.getProperty());
        Element previous = head;
        for (Element element = list.getLink(); element != null; element = element.getLink()) {
            if (element.match(key, hashCode)) {
                previous.setLink(new Element(element.getLink(), property));
                return head;
            }
            final Element next = new Element(null, element.getProperty());
            previous.setLink(next);
            previous = next;
        }
        return list;
    }


    /*
     * Map implementation
     */

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean containsKey(final Object key) {
        assert key instanceof String || key instanceof Symbol;
        return findElement(key) != null;
    }

    @Override
    public boolean containsValue(final Object value) {
        if (value instanceof Property) {
            final Property property = (Property) value;
            final Element element = findElement(property.getKey());
            return element != null && element.getProperty().equals(value);
        }
        return false;
    }

    @Override
    public Property get(final Object key) {
        assert key instanceof String || key instanceof Symbol;
        final Element element = findElement(key);
        return element != null ? element.getProperty() : null;
    }

    @Override
    public Property put(final Object key, final Property value) {
        throw new UnsupportedOperationException("Immutable map.");
    }

    @Override
    public Property remove(final Object key) {
        throw new UnsupportedOperationException("Immutable map.");
    }

    @Override
    public void putAll(final Map<? extends Object, ? extends Property> m) {
        throw new UnsupportedOperationException("Immutable map.");
    }

    @Override
    public void clear() {
        throw new UnsupportedOperationException("Immutable map.");
    }

    @Override
    public Set<Object> keySet() {
        final HashSet<Object> set = new HashSet<>();
        for (Element element = list; element != null; element = element.getLink()) {
            set.add(element.getKey());
        }
        return Collections.unmodifiableSet(set);
    }

    @Override
    public Collection<Property> values() {
        return Collections.unmodifiableList(Arrays.asList(getProperties()));
    }

    @Override
    public Set<Entry<Object, Property>> entrySet() {
        final HashSet<Entry<Object, Property>> set = new HashSet<>();
        for (Element element = list; element != null; element = element.getLink()) {
            set.add(element);
        }
        return Collections.unmodifiableSet(set);
    }

    /**
     * List map element.
     */
    static final class Element implements Entry<Object, Property> {
        /** Link for list construction. */
        private Element link;

        /** Element property. */
        private final Property property;

        /** Element key. Kept separate for performance.) */
        private final Object key;

        /** Element key hash code. */
        private final int hashCode;

        /*
         * Constructors
         */

        Element(final Element link, final Property property) {
            this.link     = link;
            this.property = property;
            this.key      = property.getKey();
            this.hashCode = this.key.hashCode();
        }

        boolean match(final Object otherKey, final int otherHashCode) {
            return this.hashCode == otherHashCode && this.key.equals(otherKey);
        }

        /*
         * Entry implmentation.
         */

        @Override
        public boolean equals(final Object other) {
            assert property != null && other != null;
            return other instanceof Element && property.equals(((Element)other).property);
        }

        @Override
        public Object getKey() {
            return key;
        }

        @Override
        public Property getValue() {
            return property;
        }

        @Override
        public int hashCode() {
            return hashCode;
        }

        @Override
        public Property setValue(final Property value) {
            throw new UnsupportedOperationException("Immutable map.");
        }

        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer();

            sb.append('[');

            Element elem = this;
            do {
                sb.append(elem.getValue());
                elem = elem.link;
                if (elem != null) {
                    sb.append(" -> ");
                }
            } while (elem != null);

            sb.append(']');

            return sb.toString();
        }

        /*
         * Accessors
         */

        Element getLink() {
            return link;
        }

        void setLink(final Element link) {
            this.link = link;
        }

        Property getProperty() {
            return property;
        }
    }

    /**
     * A hybrid map/list structure to add elements to the map without the need to clone and rehash the main table.
     * This is used for large maps to reduce the overhead of adding elements. Instances of this class can replace
     * themselves with a pure hash map version of themselves to optimize query performance.
     */
    private class ElementQueue {

        /** List of elements not merged into bins */
        private final Element qhead;

        /** Our own bins array. Differs from original PropertyHashMap bins when queue is merged. */
        private final Element[] qbins;

        /** Count searches to trigger merging of queue into bins. */
        int searchCount = 0;

        ElementQueue(final Element qhead, final Element[] qbins) {
            this.qhead = qhead;
            this.qbins = qbins;
        }

        Element find(final Object key) {
            final int binIndex = binIndex(qbins, key);
            final Element element = findElement(qbins[binIndex], key);
            if (element != null) {
                return element;
            }
            if (qhead != null) {
                if (++searchCount > 2) {
                    // Merge the queue into the hash bins if this map is queried more than a few times
                    final Element[] newBins = cloneAndMergeBins();
                    assert newBins != qbins;
                    PropertyHashMap.this.queue = new ElementQueue(null, newBins);
                    return PropertyHashMap.this.queue.find(key);
                }
                return findElement(qhead, key);
            }
            return null;
        }

        /**
         * Create a cloned or new bins array and merge the elements in the queue into it if there are any.
         *
         * @return the cloned bins array
         */
        private Element[] cloneAndMergeBins() {
            if (qhead == null) {
                return qbins;
            }

            final Element[] newBins = qbins.clone();

            for (Element element = qhead; element != null; element = element.getLink()) {
                final Property property = element.getProperty();
                final Object key = property.getKey();
                final int binIndex = binIndex(newBins, key);

                newBins[binIndex] = new Element(newBins[binIndex], property);
            }

            return newBins;
        }

    }

    /**
     * A builder class used for adding, replacing, or removing elements.
     */
    private static class MapBuilder {

        /** Bins array - may be shared with map that created us. */
        private Element[] bins;
        /** Whether our bins are shared */
        private boolean hasOwnBins;

        /** Queue of unmerged elements */
        private Element qhead;

        /** Full property list. */
        private Element list;

        /** Number of properties. */
        private int size;

        MapBuilder(final Element[] bins, final Element list, final int size, final boolean hasOwnBins) {
            this.bins  = bins;
            this.hasOwnBins = hasOwnBins;
            this.list  = list;
            this.qhead = null;
            this.size  = size;
        }

        MapBuilder(final ElementQueue queue, final Element list, final int size, final boolean hasOwnBins) {
            this.bins  = queue.qbins;
            this.hasOwnBins = hasOwnBins;
            this.list  = list;
            this.qhead = queue.qhead;
            this.size  = size;
        }

        /**
         * Add a {@link Property}. Removes duplicates if necessary.
         *
         * @param property {@link Property} to add.
         */
        private void addProperty(final Property property) {
            final Object key = property.getKey();

            if (bins != null) {
                final int binIndex = binIndex(bins, key);
                if (findElement(bins[binIndex], key) != null) {
                    ensureOwnBins();
                    bins[binIndex] = removeExistingElement(bins[binIndex], key);
                } else if (findElement(qhead, key) != null) {

/**代码未完, 请加载全部代码(NowJava.com).**/