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 }