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 = 32;
 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         Element[] newBins;




 397         if (bins == null && newSize <= LIST_THRESHOLD) {
 398             newBins = null;
 399         } else if (newSize > threshold) {
 400             newBins = rehash(list, binsNeeded(newSize));
 401         } else {
 402             newBins = bins.clone();
 403         }
 404         return new PropertyHashMap(newSize, newBins, list);
 405     }
 406 
















 407 











 408 
 409     /**
 410      * Add a {@link Property} to a temporary {@link PropertyHashMap}, that has
 411      * been already cloned.  Removes duplicates if necessary.
 412      *
 413      * @param property {@link Property} to add.
 414      *
 415      * @return New {@link PropertyHashMap}.
 416      */
 417     private PropertyHashMap addNoClone(final Property property) {
 418         int newSize = size;
 419         final String key = property.getKey();
 420         Element newList = list;
 421         if (bins != null) {
 422             final int binIndex = binIndex(bins, key);
 423             Element bin = bins[binIndex];
 424             if (findElement(bin, key) != null) {
 425                 newSize--;
 426                 bin = removeFromList(bin, key);
 427                 newList = removeFromList(list, key);
 428             }
 429             bins[binIndex] = new Element(bin, property);
 430         } else {
 431             if (findElement(list, key) != null) {
 432                 newSize--;
 433                 newList = removeFromList(list, key);
 434             }
 435         }
 436         newList = new Element(newList, property);
 437         return new PropertyHashMap(newSize, bins, newList);
 438     }
 439 
 440     private PropertyHashMap replaceNoClone(final String key, final Property property) {
 441         if (bins != null) {
 442             final int binIndex = binIndex(bins, key);
 443             Element bin = bins[binIndex];
 444             bin = replaceInList(bin, key, property);
 445             bins[binIndex] = bin;
 446         }
 447         Element newList = list;
 448         newList = replaceInList(newList, key, property);
 449         return new PropertyHashMap(size, bins, newList);
 450     }
 451 
 452     /**
 453      * Removes an {@link Element} from a specific list, avoiding duplication.
 454      *
 455      * @param list List to remove from.
 456      * @param key  Key of {@link Element} to remove.
 457      *
 458      * @return New list with {@link Element} removed.
 459      */
 460     private static Element removeFromList(final Element list, final String key) {
 461         if (list == null) {
 462             return null;
 463         }
 464         final int hashCode = key.hashCode();
 465         if (list.match(key, hashCode)) {
 466             return list.getLink();
 467         }
 468         final Element head = new Element(null, list.getProperty());
 469         Element previous = head;
 470         for (Element element = list.getLink(); element != null; element = element.getLink()) {
 471             if (element.match(key, hashCode)) {
 472                 previous.setLink(element.getLink());
 473                 return head;
 474             }
 475             final Element next = new Element(null, element.getProperty());
 476             previous.setLink(next);
 477             previous = next;
 478         }
 479         return list;
 480     }
 481 
 482     // for element x. if x get link matches,
 483     private static Element replaceInList(final Element list, final String key, final Property property) {
 484         assert list != null;
 485         final int hashCode = key.hashCode();
 486 
 487         if (list.match(key, hashCode)) {
 488             return new Element(list.getLink(), property);
 489         }
 490 
 491         final Element head = new Element(null, list.getProperty());
 492         Element previous = head;
 493         for (Element element = list.getLink(); element != null; element = element.getLink()) {
 494             if (element.match(key, hashCode)) {
 495                 previous.setLink(new Element(element.getLink(), property));
 496                 return head;
 497             }
 498             final Element next = new Element(null, element.getProperty());
 499             previous.setLink(next);
 500             previous = next;
 501         }
 502         return list;
 503     }
 504 
 505 
 506     /*
 507      * Map implementation
 508      */
 509 
 510     @Override
 511     public int size() {
 512         return size;
 513     }
 514 
 515     @Override
 516     public boolean isEmpty() {
 517         return size == 0;
 518     }
 519 
 520     @Override
 521     public boolean containsKey(final Object key) {
 522         if (key instanceof String) {
 523             return findElement((String)key) != null;
 524         }
 525         assert key instanceof String;
 526         return false;
 527     }
 528 
 529     /**
 530      * Check if the map contains a key.
 531      *
 532      * @param key {@link Property} key.
 533      *
 534      * @return {@code true} of key is in {@link PropertyHashMap}.
 535      */
 536     public boolean containsKey(final String key) {
 537         return findElement(key) != null;
 538     }
 539 
 540     @Override
 541     public boolean containsValue(final Object value) {
 542         if (value instanceof Property) {
 543             final Property property = (Property) value;
 544             final Element element = findElement(property.getKey());
 545             return element != null && element.getProperty().equals(value);
 546         }
 547         return false;
 548     }
 549 
 550     @Override
 551     public Property get(final Object key) {
 552         if (key instanceof String) {
 553             final Element element = findElement((String)key);
 554             return element != null ? element.getProperty() : null;
 555         }
 556         assert key instanceof String;
 557         return null;
 558     }
 559 
 560     /**
 561      * Get the {@link Property} given a key that is an explicit {@link String}.
 562      * See also {@link PropertyHashMap#get(Object)}
 563      *
 564      * @param key {@link Property} key.
 565      *
 566      * @return {@link Property}, or {@code null} if no property with that key was found.
 567      */
 568     public Property get(final String key) {
 569         final Element element = findElement(key);
 570         return element != null ? element.getProperty() : null;
 571     }
 572 
 573     @Override
 574     public Property put(final String key, final Property value) {
 575         throw new UnsupportedOperationException("Immutable map.");
 576     }
 577 
 578     @Override
 579     public Property remove(final Object key) {
 580         throw new UnsupportedOperationException("Immutable map.");
 581     }
 582 
 583     @Override
 584     public void putAll(final Map<? extends String, ? extends Property> m) {
 585         throw new UnsupportedOperationException("Immutable map.");
 586     }
 587 
 588     @Override
 589     public void clear() {
 590         throw new UnsupportedOperationException("Immutable map.");
 591     }
 592 
 593     @Override
 594     public Set<String> keySet() {
 595         final HashSet<String> set = new HashSet<>();
 596         for (Element element = list; element != null; element = element.getLink()) {
 597             set.add(element.getKey());
 598         }
 599         return Collections.unmodifiableSet(set);
 600     }
 601 
 602     @Override
 603     public Collection<Property> values() {
 604         return Collections.unmodifiableList(Arrays.asList(getProperties()));
 605     }
 606 
 607     @Override
 608     public Set<Entry<String, Property>> entrySet() {
 609         final HashSet<Entry<String, Property>> set = new HashSet<>();
 610         for (Element element = list; element != null; element = element.getLink()) {
 611             set.add(element);
 612         }
 613         return Collections.unmodifiableSet(set);
 614     }
 615 
 616     /**
 617      * List map element.
 618      */
 619     static final class Element implements Entry<String, Property> {
 620         /** Link for list construction. */
 621         private Element link;
 622 
 623         /** Element property. */
 624         private final Property property;
 625 
 626         /** Element key. Kept separate for performance.) */
 627         private final String key;
 628 
 629         /** Element key hash code. */
 630         private final int hashCode;
 631 
 632         /*
 633          * Constructors
 634          */
 635 
 636         Element(final Element link, final Property property) {
 637             this.link     = link;
 638             this.property = property;
 639             this.key      = property.getKey();
 640             this.hashCode = this.key.hashCode();
 641         }
 642 
 643         boolean match(final String otherKey, final int otherHashCode) {
 644             return this.hashCode == otherHashCode && this.key.equals(otherKey);

 645         }
 646 
 647         /*
 648          * Entry implmentation.
 649          */
 650 
 651         @Override
 652         public boolean equals(final Object other) {
 653             assert property != null && other != null;
 654             return other instanceof Element && property.equals(((Element)other).property);
 655         }
 656 
 657         @Override
 658         public String getKey() {
 659             return key;
 660         }
 661 
 662         @Override
 663         public Property getValue() {
 664             return property;
 665         }
 666 
 667         @Override
 668         public int hashCode() {
 669             return hashCode;
 670         }
 671 
 672         @Override
 673         public Property setValue(final Property value) {
 674             throw new UnsupportedOperationException("Immutable map.");
 675         }
 676 
 677         @Override
 678         public String toString() {
 679             final StringBuffer sb = new StringBuffer();
 680 
 681             sb.append('[');
 682 
 683             Element elem = this;
 684             do {
 685                 sb.append(elem.getValue());
 686                 elem = elem.link;
 687                 if (elem != null) {
 688                     sb.append(" -> ");
 689                 }
 690             } while (elem != null);
 691 
 692             sb.append(']');
 693 
 694             return sb.toString();
 695         }
 696 
 697         /*
 698          * Accessors
 699          */
 700 
 701         Element getLink() {
 702             return link;
 703         }
 704 
 705         void setLink(final Element link) {
 706             this.link = link;
 707         }
 708 
 709         Property getProperty() {
 710             return property;
 711         }
 712     }
 713 
 714 }
--- EOF ---