PropertyHashMap.java revision 953:221a84ef44c0
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 <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} 715