| /* |
| * 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; |
| |
| /** |
| * Immutable hash map implementation for properties. Properties are keyed on strings. |
| * 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> |
| * A separate chronological list is kept for quick generation of keys and values, and, |
| * for rehashing. |
| * <p> |
| * Details: |
| * <p> |
| * The main goal is to be able to retrieve properties from a map quickly, keying on |
| * the property name (String.) 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 <String, 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; |
| |
| /** 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 final Element[] bins; |
| |
| /** All properties as an array (lazy). */ |
| private Property[] properties; |
| |
| /** |
| * Empty map constructor. |
| */ |
| private PropertyHashMap() { |
| this.size = 0; |
| this.threshold = 0; |
| this.bins = null; |
| this.list = null; |
| } |
| |
| /** |
| * Clone Constructor |
| * |
| * @param map Original {@link PropertyHashMap}. |
| */ |
| private PropertyHashMap(final PropertyHashMap map) { |
| this.size = map.size; |
| this.threshold = map.threshold; |
| this.bins = map.bins; |
| this.list = map.list; |
| } |
| |
| /** |
| * Constructor used internally to extend a map |
| * |
| * @param size Size of the new {@link PropertyHashMap}. |
| * @param bins The hash bins. |
| * @param list The {@link Property} list. |
| */ |
| private PropertyHashMap(final int size, final Element[] bins, final Element list) { |
| this.size = size; |
| this.threshold = bins != null ? threeQuarters(bins.length) : 0; |
| this.bins = bins; |
| this.list = list; |
| } |
| |
| /** |
| * 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() + "'"; |
| return cloneMap().replaceNoClone(property.getKey(), newProperty); |
| } |
| |
| /** |
| * 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; |
| PropertyHashMap newMap = cloneMap(newSize); |
| newMap = newMap.addNoClone(property); |
| return newMap; |
| } |
| |
| /** |
| * 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; |
| PropertyHashMap newMap = cloneMap(newSize); |
| for (final Property property : newProperties) { |
| newMap = newMap.addNoClone(property); |
| } |
| return newMap; |
| } |
| |
| /** |
| * 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(); |
| PropertyHashMap newMap = cloneMap(newSize); |
| for (final Property property : newProperties) { |
| newMap = newMap.addNoClone(property); |
| } |
| return newMap; |
| } |
| return this; |
| } |
| |
| /** |
| * Clone a {@link PropertyHashMap} and remove a {@link Property}. |
| * |
| * @param property {@link Property} to remove. |
| * |
| * @return New {@link PropertyHashMap}. |
| */ |
| public PropertyHashMap immutableRemove(final Property property) { |
| return immutableRemove(property.getKey()); |
| } |
| |
| /** |
| * 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 String key) { |
| if (bins != null) { |
| final int binIndex = binIndex(bins, key); |
| final Element bin = bins[binIndex]; |
| if (findElement(bin, key) != null) { |
| final int newSize = size - 1; |
| Element[] newBins = null; |
| if (newSize >= LIST_THRESHOLD) { |
| newBins = bins.clone(); |
| newBins[binIndex] = removeFromList(bin, key); |
| } |
| final Element newList = removeFromList(list, key); |
| return new PropertyHashMap(newSize, newBins, newList); |
| } |
| } else if (findElement(list, key) != null) { |
| final int newSize = size - 1; |
| return newSize != 0 ? new PropertyHashMap(newSize, null, removeFromList(list, key)) : 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 String 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 String 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 String 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 String key) { |
| 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 String key) { |
| final int hashCode = key.hashCode(); |
| for (Element element = elementList; element != null; element = element.getLink()) { |
| if (element.match(key, hashCode)) { |
| return element; |
| } |
| } |
| return null; |
| } |
| |
| |
| private PropertyHashMap cloneMap() { |
| return new PropertyHashMap(size, bins == null ? null : bins.clone(), list); |
| } |
| |
| /** |
| * Clone {@link PropertyHashMap} to accommodate new size. |
| * |
| * @param newSize New size of {@link PropertyHashMap}. |
| * |
| * @return Cloned {@link PropertyHashMap} with new size. |
| */ |
| private PropertyHashMap cloneMap(final int newSize) { |
| Element[] newBins; |
| if (bins == null && newSize <= LIST_THRESHOLD) { |
| newBins = null; |
| } else if (newSize > threshold) { |
| newBins = rehash(list, binsNeeded(newSize)); |
| } else { |
| newBins = bins.clone(); |
| } |
| return new PropertyHashMap(newSize, newBins, list); |
| } |
| |
| |
| |
| /** |
| * Add a {@link Property} to a temporary {@link PropertyHashMap}, that has |
| * been already cloned. Removes duplicates if necessary. |
| * |
| * @param property {@link Property} to add. |
| * |
| * @return New {@link PropertyHashMap}. |
| */ |
| private PropertyHashMap addNoClone(final Property property) { |
| int newSize = size; |
| final String key = property.getKey(); |
| Element newList = list; |
| if (bins != null) { |
| final int binIndex = binIndex(bins, key); |
| Element bin = bins[binIndex]; |
| if (findElement(bin, key) != null) { |
| newSize--; |
| bin = removeFromList(bin, key); |
| newList = removeFromList(list, key); |
| } |
| bins[binIndex] = new Element(bin, property); |
| } else { |
| if (findElement(list, key) != null) { |
| newSize--; |
| newList = removeFromList(list, key); |
| } |
| } |
| newList = new Element(newList, property); |
| return new PropertyHashMap(newSize, bins, newList); |
| } |
| |
| private PropertyHashMap replaceNoClone(final String key, final Property property) { |
| if (bins != null) { |
| final int binIndex = binIndex(bins, key); |
| Element bin = bins[binIndex]; |
| bin = replaceInList(bin, key, property); |
| bins[binIndex] = bin; |
| } |
| Element newList = list; |
| newList = replaceInList(newList, key, property); |
| return new PropertyHashMap(size, bins, newList); |
| } |
| |
| /** |
| * 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 String 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 String 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) { |
| if (key instanceof String) { |
| return findElement((String)key) != null; |
| } |
| assert key instanceof String; |
| return false; |
| } |
| |
| /** |
| * Check if the map contains a key. |
| * |
| * @param key {@link Property} key. |
| * |
| * @return {@code true} of key is in {@link PropertyHashMap}. |
| */ |
| public boolean containsKey(final String key) { |
| 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) { |
| if (key instanceof String) { |
| final Element element = findElement((String)key); |
| return element != null ? element.getProperty() : null; |
| } |
| assert key instanceof String; |
| return null; |
| } |
| |
| /** |
| * Get the {@link Property} given a key that is an explicit {@link String}. |
| * See also {@link PropertyHashMap#get(Object)} |
| * |
| * @param key {@link Property} key. |
| * |
| * @return {@link Property}, or {@code null} if no property with that key was found. |
| */ |
| public Property get(final String key) { |
| final Element element = findElement(key); |
| return element != null ? element.getProperty() : null; |
| } |
| |
| @Override |
| public Property put(final String 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 String, ? extends Property> m) { |
| throw new UnsupportedOperationException("Immutable map."); |
| } |
| |
| @Override |
| public void clear() { |
| throw new UnsupportedOperationException("Immutable map."); |
| } |
| |
| @Override |
| public Set<String> keySet() { |
| final HashSet<String> 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<String, Property>> entrySet() { |
| final HashSet<Entry<String, 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<String, Property> { |
| /** Link for list construction. */ |
| private Element link; |
| |
| /** Element property. */ |
| private final Property property; |
| |
| /** Element key. Kept separate for performance.) */ |
| private final String 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 String 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 String 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; |
| } |
| } |
| |
| } |
