src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/PropertyHashMap.java

Print this page




  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). */


 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);


 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);


 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                 }




  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). */


 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);


 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);


 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                 }