1 /*
   2  * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package jdk.nashorn.internal.runtime;
  27 
  28 import java.util.Arrays;
  29 import java.util.Collection;
  30 import java.util.Collections;
  31 import java.util.HashSet;
  32 import java.util.Map;
  33 import java.util.Set;
  34 
  35 /**
  36  * Immutable hash map implementation for properties.  Properties are keyed on strings.
  37  * Copying and cloning is avoided by relying on immutability.
  38  * <p>
  39  * When adding an element to a hash table, only the head of a bin list is updated, thus
  40  * an add only requires the cloning of the bins array and adding an element to the head
  41  * of the bin list.  Similarly for removal, only a portion of a bin list is updated.
  42  * <p>
  43  * A separate chronological list is kept for quick generation of keys and values, and,
  44  * for rehashing.
  45  * <p>
  46  * Details:
  47  * <p>
  48  * The main goal is to be able to retrieve properties from a map quickly, keying on
  49  * the property name (String.)  A secondary, but important goal, is to keep maps
  50  * immutable, so that a map can be shared by multiple objects in a context.
  51  * Sharing maps allows objects to be categorized as having similar properties, a
  52  * fact that call site guards rely on.  In this discussion, immutability allows us
  53  * to significantly reduce the amount of duplication we have in our maps.
  54  * <p>
  55  * The simplest of immutable maps is a basic singly linked list.  New properties
  56  * are simply added to the head of the list.  Ancestor maps are not affected by the
  57  * addition, since they continue to refer to their own head.  Searching is done by
  58  * walking linearly though the elements until a match is found, O(N).
  59  * <p>
  60  * A hash map can be thought of as an optimization of a linked list map, where the
  61  * linked list is broken into fragments based on hashCode(key) .  An array is use
  62  * to quickly reference these fragments, indexing on hashCode(key) mod tableSize
  63  * (tableSize is typically a power of 2 so that the mod is a fast masking
  64  * operation.)  If the size of the table is sufficient large, then search time
  65  * approaches O(1).  In fact, most bins in a hash table are typically empty or
  66  * contain a one element list.
  67  * <p>
  68  * For immutable hash maps, we can think of the hash map as an array of the shorter
  69  * linked list maps.  If we add an element to the head of one of those lists,  it
  70  * doesn't affect any ancestor maps.  Thus adding an element to an immutable hash
  71  * map only requires cloning the array and inserting an element at the head of one
  72  * of the bins.
  73  * <p>
  74  * Using Java HashMaps we don't have enough control over the entries to allow us to
  75  * implement this technique, so we are forced to clone the entire hash map.
  76  * <p>
  77  * Removing elements is done similarly.  We clone the array and then only modify
  78  * the bin containing the removed element.  More often than not, the list contains
  79  * only one element (or is very short), so this is not very costly.  When the list
  80  * has several items, we need to clone the list portion prior to the removed item.
  81  * <p>
  82  * Another requirement of property maps is that we need to be able to gather all
  83  * properties in chronological (add) order.  We have been using LinkedHashMap to
  84  * provide this.  For the implementation of immutable hash map, we use a singly
  85  * linked list that is linked in reverse chronological order.  This means we simply
  86  * add new entries to the head of the list.  If we need to work with the list in
  87  * forward order, it's simply a matter of allocating an array (size is known) and
  88  * back filling in reverse order.  Removal of elements from the chronological list
  89  * is trickier.  LinkedHashMap uses a doubly linked list to give constant time
  90  * removal. Immutable hash maps can't do that and maintain immutability.  So we
  91  * manage the chronological list the same way we manage the bins, cloning up to the
  92  * point of removal.  Don't panic.  This cost is more than offset by the cost of
  93  * cloning an entire LinkedHashMap.  Plus removal is far more rare than addition.
  94  * <p>
  95  * One more optimization.  Maps with a small number of entries don't use the hash
  96  * map at all, the chronological list is used instead.
  97  * <p>
  98  * So the benefits from immutable arrays are; fewer objects and less copying.  For
  99  * immutable hash map, when no removal is involved, the number of elements per
 100  * property is two (bin + chronological elements).  For LinkedHashMap it is one
 101  * (larger element) times the number of maps that refer to the property.  For
 102  * immutable hash map, addition is constant time.  For LinkedHashMap it's O(N+C)
 103  * since we have to clone the older map.
 104  */
 105 public final class PropertyHashMap implements Map <String, Property> {
 106     /** Number of initial bins. Power of 2. */
 107     private static final int INITIAL_BINS = 16;
 108 
 109     /** Threshold before using bins. */
 110     private static final int LIST_THRESHOLD = 8;
 111 
 112     /** Initial map. */
 113     public static final PropertyHashMap EMPTY_HASHMAP = new PropertyHashMap();
 114 
 115     /** Number of properties in the map. */
 116     private final int size;
 117 
 118     /** Threshold before growing the bins. */
 119     private final int threshold;
 120 
 121     /** Reverse list of all properties. */
 122     private final Element list;
 123 
 124     /** Hash map bins. */
 125     private final Element[] bins;
 126 
 127     /** All properties as an array (lazy). */
 128     private Property[] properties;
 129 
 130     /**
 131      * Empty map constructor.
 132      */
 133     private PropertyHashMap() {
 134         this.size      = 0;
 135         this.threshold = 0;
 136         this.bins      = null;
 137         this.list      = null;
 138     }
 139 
 140     /**
 141      * Clone Constructor
 142      *
 143      * @param map Original {@link PropertyHashMap}.
 144      */
 145     private PropertyHashMap(final PropertyHashMap map) {
 146         this.size      = map.size;
 147         this.threshold = map.threshold;
 148         this.bins      = map.bins;
 149         this.list      = map.list;
 150     }
 151 
 152     /**
 153      * Constructor used internally to extend a map
 154      *
 155      * @param size Size of the new {@link PropertyHashMap}.
 156      * @param bins The hash bins.
 157      * @param list The {@link Property} list.
 158      */
 159     private PropertyHashMap(final int size, final Element[] bins, final Element list) {
 160         this.size      = size;
 161         this.threshold = bins != null ? threeQuarters(bins.length) : 0;
 162         this.bins      = bins;
 163         this.list      = list;
 164     }
 165 
 166     /**
 167      * Clone a property map, replacing a property with a new one in the same place,
 168      * which is important for property iterations if a property changes types
 169      * @param property    old property
 170      * @param newProperty new property
 171      * @return new property map
 172      */
 173     public PropertyHashMap immutableReplace(final Property property, final Property newProperty) {
 174         assert property.getKey().equals(newProperty.getKey()) : "replacing properties with different keys: '" + property.getKey() + "' != '" + newProperty.getKey() + "'";
 175         assert findElement(property.getKey()) != null         : "replacing property that doesn't exist in map: '" + property.getKey() + "'";
 176         return cloneMap().replaceNoClone(property.getKey(), newProperty);
 177     }
 178 
 179     /**
 180      * Clone a {@link PropertyHashMap} and add a {@link Property}.
 181      *
 182      * @param property {@link Property} to add.
 183      *
 184      * @return New {@link PropertyHashMap}.
 185      */
 186     public PropertyHashMap immutableAdd(final Property property) {
 187         final int newSize = size + 1;
 188         PropertyHashMap newMap = cloneMap(newSize);
 189         newMap = newMap.addNoClone(property);
 190         return newMap;
 191     }
 192 
 193     /**
 194      * Clone a {@link PropertyHashMap} and add an array of properties.
 195      *
 196      * @param newProperties Properties to add.
 197      *
 198      * @return New {@link PropertyHashMap}.
 199      */
 200     public PropertyHashMap immutableAdd(final Property... newProperties) {
 201         final int newSize = size + newProperties.length;
 202         PropertyHashMap newMap = cloneMap(newSize);
 203         for (final Property property : newProperties) {
 204             newMap = newMap.addNoClone(property);
 205         }
 206         return newMap;
 207     }
 208 
 209     /**
 210      * Clone a {@link PropertyHashMap} and add a collection of properties.
 211      *
 212      * @param newProperties Properties to add.
 213      *
 214      * @return New {@link PropertyHashMap}.
 215      */
 216     public PropertyHashMap immutableAdd(final Collection<Property> newProperties) {
 217         if (newProperties != null) {
 218             final int newSize = size + newProperties.size();
 219             PropertyHashMap newMap = cloneMap(newSize);
 220             for (final Property property : newProperties) {
 221                 newMap = newMap.addNoClone(property);
 222             }
 223             return newMap;
 224         }
 225         return this;
 226     }
 227 
 228     /**
 229      * Clone a {@link PropertyHashMap} and remove a {@link Property}.
 230      *
 231      * @param property {@link Property} to remove.
 232      *
 233      * @return New {@link PropertyHashMap}.
 234      */
 235     public PropertyHashMap immutableRemove(final Property property) {
 236         return immutableRemove(property.getKey());
 237     }
 238 
 239     /**
 240      * Clone a {@link PropertyHashMap} and remove a {@link Property} based on its key.
 241      *
 242      * @param key Key of {@link Property} to remove.
 243      *
 244      * @return New {@link PropertyHashMap}.
 245      */
 246     public PropertyHashMap immutableRemove(final String key) {
 247         if (bins != null) {
 248             final int binIndex = binIndex(bins, key);
 249             final Element bin = bins[binIndex];
 250             if (findElement(bin, key) != null) {
 251                 final int newSize = size - 1;
 252                 Element[] newBins = null;
 253                 if (newSize >= LIST_THRESHOLD) {
 254                     newBins = bins.clone();
 255                     newBins[binIndex] = removeFromList(bin, key);
 256                 }
 257                 final Element newList = removeFromList(list, key);
 258                 return new PropertyHashMap(newSize, newBins, newList);
 259             }
 260         } else if (findElement(list, key) != null) {
 261             final int newSize = size - 1;
 262             return newSize != 0 ? new PropertyHashMap(newSize, null, removeFromList(list, key)) : EMPTY_HASHMAP;
 263         }
 264         return this;
 265     }
 266 
 267     /**
 268      * Find a {@link Property} in the {@link PropertyHashMap}.
 269      *
 270      * @param key Key of {@link Property} to find.
 271      *
 272      * @return {@link Property} matching key or {@code null} if not found.
 273      */
 274     public Property find(final String key) {
 275         final Element element = findElement(key);
 276         return element != null ? element.getProperty() : null;
 277     }
 278 
 279     /**
 280      * Return an array of properties in chronological order of adding.
 281      *
 282      * @return Array of all properties.
 283      */
 284     Property[] getProperties() {
 285         if (properties == null) {
 286             final Property[] array = new Property[size];
 287             int i = size;
 288             for (Element element = list; element != null; element = element.getLink()) {
 289                 array[--i] = element.getProperty();
 290             }
 291             properties = array;
 292         }
 293         return properties;
 294     }
 295 
 296     /**
 297      * Returns the bin index from the key.
 298      *
 299      * @param bins     The bins array.
 300      * @param key      {@link Property} key.
 301      *
 302      * @return The bin index.
 303      */
 304     private static int binIndex(final Element[] bins, final String key) {
 305         return  key.hashCode() & bins.length - 1;
 306     }
 307 
 308     /**
 309      * Calculate the number of bins needed to contain n properties.
 310      *
 311      * @param n Number of elements.
 312      *
 313      * @return Number of bins required.
 314      */
 315     private static int binsNeeded(final int n) {
 316         // 50% padding
 317         return 1 << 32 - Integer.numberOfLeadingZeros(n + (n >>> 1) | INITIAL_BINS - 1);
 318     }
 319 
 320     /**
 321      * Used to calculate the current capacity of the bins.
 322      *
 323      * @param n Number of bin slots.
 324      *
 325      * @return 75% of n.
 326      */
 327     private static int threeQuarters(final int n) {
 328         return (n >>> 1) + (n >>> 2);
 329     }
 330 
 331     /**
 332      * Regenerate the bin table after changing the number of bins.
 333      *
 334      * @param list    // List of all properties.
 335      * @param binSize // New size of bins.
 336      *
 337      * @return Populated bins.
 338      */
 339     private static Element[] rehash(final Element list, final int binSize) {
 340         final Element[] newBins = new Element[binSize];
 341         for (Element element = list; element != null; element = element.getLink()) {
 342             final Property property = element.getProperty();
 343             final String   key      = property.getKey();
 344             final int      binIndex = binIndex(newBins, key);
 345 
 346             newBins[binIndex] = new Element(newBins[binIndex], property);
 347         }
 348         return newBins;
 349     }
 350 
 351     /**
 352      * Locate an element based on key.
 353      *
 354      * @param key {@link Element} key.
 355      *
 356      * @return {@link Element} matching key or {@code null} if not found.
 357      */
 358     private Element findElement(final String key) {
 359         if (bins != null) {
 360             final int binIndex = binIndex(bins, key);
 361             return findElement(bins[binIndex], key);
 362         }
 363         return findElement(list, key);
 364     }
 365 
 366     /**
 367      * Locate an {@link Element} based on key from a specific list.
 368      *
 369      * @param elementList Head of {@link Element} list
 370      * @param key         {@link Element} key.
 371      * @return {@link Element} matching key or {@code null} if not found.
 372      */
 373     private static Element findElement(final Element elementList, final String key) {
 374         final int hashCode = key.hashCode();
 375         for (Element element = elementList; element != null; element = element.getLink()) {
 376             if (element.match(key, hashCode)) {
 377                 return element;
 378             }
 379         }
 380         return null;
 381     }
 382 
 383 
 384     private PropertyHashMap cloneMap() {
 385         return new PropertyHashMap(size, bins == null ? null : bins.clone(), list);
 386     }
 387 
 388     /**
 389      * Clone {@link PropertyHashMap} to accommodate new size.
 390      *
 391      * @param newSize New size of {@link PropertyHashMap}.
 392      *
 393      * @return Cloned {@link PropertyHashMap} with new size.
 394      */
 395     private PropertyHashMap cloneMap(final int newSize) {
 396         final Element[] newBins = cloneBins(newSize);
 397         return new PropertyHashMap(newSize, newBins, list);
 398     }
 399 
 400     private Element[] cloneBins(final int newSize) {
 401         if (bins == null && newSize <= LIST_THRESHOLD) {
 402             return null;
 403         } else if (newSize > threshold) {
 404             return rehash(list, binsNeeded(newSize));
 405         } else {
 406             return bins == null ? null : bins.clone();
 407         }
 408     }
 409 
 410     /**
 411      * Create a property map containing the given <code>properties</code>. The collection must not
 412      * contain properties with duplicate keys or keys that represent valid array indices as this
 413      * method does not perform any sanity checks.
 414      *
 415      * @param properties collection of properties
 416      * @return the property hash map
 417      */
 418     public static PropertyHashMap create(final Collection<Property> properties) {
 419         if (properties == null) {
 420             return EMPTY_HASHMAP;
 421         }
 422 
 423         final int size = properties.size();
 424         final Element[] bins = EMPTY_HASHMAP.cloneBins(size);
 425         Element list = null;
 426 
 427         for (final Property property : properties) {
 428             final String key = property.getKey();
 429             if (bins != null) {
 430                 final int binIndex = binIndex(bins, key);
 431                 final Element bin = bins[binIndex];
 432                 bins[binIndex] = new Element(bin, property);
 433             }
 434             list = new Element(list, property);
 435         }
 436         return new PropertyHashMap(size, bins, list);
 437     }
 438 
 439     /**
 440      * Add a {@link Property} to a temporary {@link PropertyHashMap}, that has
 441      * been already cloned.  Removes duplicates if necessary.
 442      *
 443      * @param property {@link Property} to add.
 444      *
 445      * @return New {@link PropertyHashMap}.
 446      */
 447     private PropertyHashMap addNoClone(final Property property) {
 448         int newSize = size;
 449         final String key = property.getKey();
 450         Element newList = list;
 451         if (bins != null) {
 452             final int binIndex = binIndex(bins, key);
 453             Element bin = bins[binIndex];
 454             if (findElement(bin, key) != null) {
 455                 newSize--;
 456                 bin = removeFromList(bin, key);
 457                 newList = removeFromList(list, key);
 458             }
 459             bins[binIndex] = new Element(bin, property);
 460         } else {
 461             if (findElement(list, key) != null) {
 462                 newSize--;
 463                 newList = removeFromList(list, key);
 464             }
 465         }
 466         newList = new Element(newList, property);
 467         return new PropertyHashMap(newSize, bins, newList);
 468     }
 469 
 470     private PropertyHashMap replaceNoClone(final String key, final Property property) {
 471         if (bins != null) {
 472             final int binIndex = binIndex(bins, key);
 473             Element bin = bins[binIndex];
 474             bin = replaceInList(bin, key, property);
 475             bins[binIndex] = bin;
 476         }
 477         Element newList = list;
 478         newList = replaceInList(newList, key, property);
 479         return new PropertyHashMap(size, bins, newList);
 480     }
 481 
 482     /**
 483      * Removes an {@link Element} from a specific list, avoiding duplication.
 484      *
 485      * @param list List to remove from.
 486      * @param key  Key of {@link Element} to remove.
 487      *
 488      * @return New list with {@link Element} removed.
 489      */
 490     private static Element removeFromList(final Element list, final String key) {
 491         if (list == null) {
 492             return null;
 493         }
 494         final int hashCode = key.hashCode();
 495         if (list.match(key, hashCode)) {
 496             return list.getLink();
 497         }
 498         final Element head = new Element(null, list.getProperty());
 499         Element previous = head;
 500         for (Element element = list.getLink(); element != null; element = element.getLink()) {
 501             if (element.match(key, hashCode)) {
 502                 previous.setLink(element.getLink());
 503                 return head;
 504             }
 505             final Element next = new Element(null, element.getProperty());
 506             previous.setLink(next);
 507             previous = next;
 508         }
 509         return list;
 510     }
 511 
 512     // for element x. if x get link matches,
 513     private static Element replaceInList(final Element list, final String key, final Property property) {
 514         assert list != null;
 515         final int hashCode = key.hashCode();
 516 
 517         if (list.match(key, hashCode)) {
 518             return new Element(list.getLink(), property);
 519         }
 520 
 521         final Element head = new Element(null, list.getProperty());
 522         Element previous = head;
 523         for (Element element = list.getLink(); element != null; element = element.getLink()) {
 524             if (element.match(key, hashCode)) {
 525                 previous.setLink(new Element(element.getLink(), property));
 526                 return head;
 527             }
 528             final Element next = new Element(null, element.getProperty());
 529             previous.setLink(next);
 530             previous = next;
 531         }
 532         return list;
 533     }
 534 
 535 
 536     /*
 537      * Map implementation
 538      */
 539 
 540     @Override
 541     public int size() {
 542         return size;
 543     }
 544 
 545     @Override
 546     public boolean isEmpty() {
 547         return size == 0;
 548     }
 549 
 550     @Override
 551     public boolean containsKey(final Object key) {
 552         if (key instanceof String) {
 553             return findElement((String)key) != null;
 554         }
 555         return false;
 556     }
 557 
 558     /**
 559      * Check if the map contains a key.
 560      *
 561      * @param key {@link Property} key.
 562      *
 563      * @return {@code true} of key is in {@link PropertyHashMap}.
 564      */
 565     public boolean containsKey(final String key) {
 566         return findElement(key) != null;
 567     }
 568 
 569     @Override
 570     public boolean containsValue(final Object value) {
 571         if (value instanceof Property) {
 572             final Property property = (Property) value;
 573             final Element element = findElement(property.getKey());
 574             return element != null && element.getProperty().equals(value);
 575         }
 576         return false;
 577     }
 578 
 579     @Override
 580     public Property get(final Object key) {
 581         if (key instanceof String) {
 582             final Element element = findElement((String)key);
 583             return element != null ? element.getProperty() : null;
 584         }
 585         assert key instanceof String;
 586         return null;
 587     }
 588 
 589     /**
 590      * Get the {@link Property} given a key that is an explicit {@link String}.
 591      * See also {@link PropertyHashMap#get(Object)}
 592      *
 593      * @param key {@link Property} key.
 594      *
 595      * @return {@link Property}, or {@code null} if no property with that key was found.
 596      */
 597     public Property get(final String key) {
 598         final Element element = findElement(key);
 599         return element != null ? element.getProperty() : null;
 600     }
 601 
 602     @Override
 603     public Property put(final String key, final Property value) {
 604         throw new UnsupportedOperationException("Immutable map.");
 605     }
 606 
 607     @Override
 608     public Property remove(final Object key) {
 609         throw new UnsupportedOperationException("Immutable map.");
 610     }
 611 
 612     @Override
 613     public void putAll(final Map<? extends String, ? extends Property> m) {
 614         throw new UnsupportedOperationException("Immutable map.");
 615     }
 616 
 617     @Override
 618     public void clear() {
 619         throw new UnsupportedOperationException("Immutable map.");
 620     }
 621 
 622     @Override
 623     public Set<String> keySet() {
 624         final HashSet<String> set = new HashSet<>();
 625         for (Element element = list; element != null; element = element.getLink()) {
 626             set.add(element.getKey());
 627         }
 628         return Collections.unmodifiableSet(set);
 629     }
 630 
 631     @Override
 632     public Collection<Property> values() {
 633         return Collections.unmodifiableList(Arrays.asList(getProperties()));
 634     }
 635 
 636     @Override
 637     public Set<Entry<String, Property>> entrySet() {
 638         final HashSet<Entry<String, Property>> set = new HashSet<>();
 639         for (Element element = list; element != null; element = element.getLink()) {
 640             set.add(element);
 641         }
 642         return Collections.unmodifiableSet(set);
 643     }
 644 
 645     /**
 646      * List map element.
 647      */
 648     static final class Element implements Entry<String, Property> {
 649         /** Link for list construction. */
 650         private Element link;
 651 
 652         /** Element property. */
 653         private final Property property;
 654 
 655         /*
 656          * Constructors
 657          */
 658 
 659         Element(final Element link, final Property property) {
 660             this.link     = link;
 661             this.property = property;
 662         }
 663 
 664         boolean match(final String otherKey, final int otherHashCode) {
 665             final String key = property.getKey();
 666             return key.hashCode() == otherHashCode && key.equals(otherKey);
 667         }
 668 
 669         /*
 670          * Entry implmentation.
 671          */
 672 
 673         @Override
 674         public boolean equals(final Object other) {
 675             assert property != null && other != null;
 676             return other instanceof Element && property.equals(((Element)other).property);
 677         }
 678 
 679         @Override
 680         public String getKey() {
 681             return property.getKey();
 682         }
 683 
 684         @Override
 685         public Property getValue() {
 686             return property;
 687         }
 688 
 689         @Override
 690         public int hashCode() {
 691             return property.getKey().hashCode();
 692         }
 693 
 694         @Override
 695         public Property setValue(final Property value) {
 696             throw new UnsupportedOperationException("Immutable map.");
 697         }
 698 
 699         @Override
 700         public String toString() {
 701             final StringBuffer sb = new StringBuffer();
 702 
 703             sb.append('[');
 704 
 705             Element elem = this;
 706             do {
 707                 sb.append(elem.getValue());
 708                 elem = elem.link;
 709                 if (elem != null) {
 710                     sb.append(" -> ");
 711                 }
 712             } while (elem != null);
 713 
 714             sb.append(']');
 715 
 716             return sb.toString();
 717         }
 718 
 719         /*
 720          * Accessors
 721          */
 722 
 723         Element getLink() {
 724             return link;
 725         }
 726 
 727         void setLink(final Element link) {
 728             this.link = link;
 729         }
 730 
 731         Property getProperty() {
 732             return property;
 733         }
 734     }
 735 
 736 }