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 26package jdk.nashorn.internal.runtime; 27 28import java.util.Arrays; 29import java.util.Collection; 30import java.util.Collections; 31import java.util.HashSet; 32import java.util.Map; 33import 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 */ 105public final class PropertyHashMap implements Map <Object, 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 Object 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 Object 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 Object 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 Object 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 Object 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 Object 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 Object 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 Object 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 Object 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 Object 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 assert key instanceof String || key instanceof Symbol; 523 return findElement(key) != null; 524 } 525 526 @Override 527 public boolean containsValue(final Object value) { 528 if (value instanceof Property) { 529 final Property property = (Property) value; 530 final Element element = findElement(property.getKey()); 531 return element != null && element.getProperty().equals(value); 532 } 533 return false; 534 } 535 536 @Override 537 public Property get(final Object key) { 538 assert key instanceof String || key instanceof Symbol; 539 final Element element = findElement(key); 540 return element != null ? element.getProperty() : null; 541 } 542 543 @Override 544 public Property put(final Object key, final Property value) { 545 throw new UnsupportedOperationException("Immutable map."); 546 } 547 548 @Override 549 public Property remove(final Object key) { 550 throw new UnsupportedOperationException("Immutable map."); 551 } 552 553 @Override 554 public void putAll(final Map<? extends Object, ? extends Property> m) { 555 throw new UnsupportedOperationException("Immutable map."); 556 } 557 558 @Override 559 public void clear() { 560 throw new UnsupportedOperationException("Immutable map."); 561 } 562 563 @Override 564 public Set<Object> keySet() { 565 final HashSet<Object> set = new HashSet<>(); 566 for (Element element = list; element != null; element = element.getLink()) { 567 set.add(element.getKey()); 568 } 569 return Collections.unmodifiableSet(set); 570 } 571 572 @Override 573 public Collection<Property> values() { 574 return Collections.unmodifiableList(Arrays.asList(getProperties())); 575 } 576 577 @Override 578 public Set<Entry<Object, Property>> entrySet() { 579 final HashSet<Entry<Object, Property>> set = new HashSet<>(); 580 for (Element element = list; element != null; element = element.getLink()) { 581 set.add(element); 582 } 583 return Collections.unmodifiableSet(set); 584 } 585 586 /** 587 * List map element. 588 */ 589 static final class Element implements Entry<Object, Property> { 590 /** Link for list construction. */ 591 private Element link; 592 593 /** Element property. */ 594 private final Property property; 595 596 /** Element key. Kept separate for performance.) */ 597 private final Object key; 598 599 /** Element key hash code. */ 600 private final int hashCode; 601 602 /* 603 * Constructors 604 */ 605 606 Element(final Element link, final Property property) { 607 this.link = link; 608 this.property = property; 609 this.key = property.getKey(); 610 this.hashCode = this.key.hashCode(); 611 } 612 613 boolean match(final Object otherKey, final int otherHashCode) { 614 return this.hashCode == otherHashCode && this.key.equals(otherKey); 615 } 616 617 /* 618 * Entry implmentation. 619 */ 620 621 @Override 622 public boolean equals(final Object other) { 623 assert property != null && other != null; 624 return other instanceof Element && property.equals(((Element)other).property); 625 } 626 627 @Override 628 public Object getKey() { 629 return key; 630 } 631 632 @Override 633 public Property getValue() { 634 return property; 635 } 636 637 @Override 638 public int hashCode() { 639 return hashCode; 640 } 641 642 @Override 643 public Property setValue(final Property value) { 644 throw new UnsupportedOperationException("Immutable map."); 645 } 646 647 @Override 648 public String toString() { 649 final StringBuffer sb = new StringBuffer(); 650 651 sb.append('['); 652 653 Element elem = this; 654 do { 655 sb.append(elem.getValue()); 656 elem = elem.link; 657 if (elem != null) { 658 sb.append(" -> "); 659 } 660 } while (elem != null); 661 662 sb.append(']'); 663 664 return sb.toString(); 665 } 666 667 /* 668 * Accessors 669 */ 670 671 Element getLink() { 672 return link; 673 } 674 675 void setLink(final Element link) { 676 this.link = link; 677 } 678 679 Property getProperty() { 680 return property; 681 } 682 } 683 684} 685