001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.collections4.map; 018 019import java.io.IOException; 020import java.io.ObjectInputStream; 021import java.io.ObjectOutputStream; 022import java.io.Serializable; 023import java.util.AbstractCollection; 024import java.util.AbstractSet; 025import java.util.Collection; 026import java.util.Iterator; 027import java.util.Map; 028import java.util.NoSuchElementException; 029import java.util.Objects; 030import java.util.Set; 031 032import org.apache.commons.collections4.CollectionUtils; 033import org.apache.commons.collections4.IterableMap; 034import org.apache.commons.collections4.MapIterator; 035import org.apache.commons.collections4.ResettableIterator; 036import org.apache.commons.collections4.iterators.EmptyIterator; 037import org.apache.commons.collections4.iterators.EmptyMapIterator; 038 039/** 040 * A {@code Map} implementation that stores data in simple fields until 041 * the size is greater than 3. 042 * <p> 043 * This map is designed for performance and can outstrip HashMap. 044 * It also has good garbage collection characteristics. 045 * </p> 046 * <ul> 047 * <li>Optimised for operation at size 3 or less. 048 * <li>Still works well once size 3 exceeded. 049 * <li>Gets at size 3 or less are about 0-10% faster than HashMap, 050 * <li>Puts at size 3 or less are over 4 times faster than HashMap. 051 * <li>Performance 5% slower than HashMap once size 3 exceeded once. 052 * </ul> 053 * <p> 054 * The design uses two distinct modes of operation - flat and delegate. 055 * While the map is size 3 or less, operations map straight onto fields using 056 * switch statements. Once size 4 is reached, the map switches to delegate mode 057 * and only switches back when cleared. In delegate mode, all operations are 058 * forwarded straight to a HashMap resulting in the 5% performance loss. 059 * </p> 060 * <p> 061 * The performance gains on puts are due to not needing to create a Map Entry 062 * object. This is a large saving not only in performance but in garbage collection. 063 * </p> 064 * <p> 065 * Whilst in flat mode this map is also easy for the garbage collector to dispatch. 066 * This is because it contains no complex objects or arrays which slow the progress. 067 * </p> 068 * <p> 069 * Do not use {@code Flat3Map} if the size is likely to grow beyond 3. 070 * </p> 071 * <p> 072 * <strong>Note that Flat3Map is not synchronized and is not thread-safe.</strong> 073 * If you wish to use this map from multiple threads concurrently, you must use 074 * appropriate synchronization. The simplest approach is to wrap this map 075 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw 076 * exceptions when accessed by concurrent threads without synchronization. 077 * </p> 078 * 079 * @param <K> the type of the keys in this map 080 * @param <V> the type of the values in this map 081 * @since 3.0 082 */ 083public class Flat3Map<K, V> implements IterableMap<K, V>, Serializable, Cloneable { 084 085 abstract static class EntryIterator<K, V> { 086 private final Flat3Map<K, V> parent; 087 private int nextIndex; 088 private FlatMapEntry<K, V> currentEntry; 089 090 /** 091 * Create a new Flat3Map.EntryIterator. 092 */ 093 EntryIterator(final Flat3Map<K, V> parent) { 094 this.parent = parent; 095 } 096 097 public boolean hasNext() { 098 return nextIndex < parent.size; 099 } 100 101 public Map.Entry<K, V> nextEntry() { 102 if (!hasNext()) { 103 throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY); 104 } 105 currentEntry = new FlatMapEntry<>(parent, ++nextIndex); 106 return currentEntry; 107 } 108 109 public void remove() { 110 if (currentEntry == null) { 111 throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID); 112 } 113 parent.remove(currentEntry.getKey()); 114 currentEntry.setRemoved(true); 115 nextIndex--; 116 currentEntry = null; 117 } 118 119 } 120 121 /** 122 * EntrySet 123 */ 124 static class EntrySet<K, V> extends AbstractSet<Map.Entry<K, V>> { 125 private final Flat3Map<K, V> parent; 126 127 EntrySet(final Flat3Map<K, V> parent) { 128 this.parent = parent; 129 } 130 131 @Override 132 public void clear() { 133 parent.clear(); 134 } 135 136 @Override 137 public Iterator<Map.Entry<K, V>> iterator() { 138 if (parent.delegateMap != null) { 139 return parent.delegateMap.entrySet().iterator(); 140 } 141 if (parent.isEmpty()) { 142 return EmptyIterator.<Map.Entry<K, V>>emptyIterator(); 143 } 144 return new EntrySetIterator<>(parent); 145 } 146 147 @Override 148 public boolean remove(final Object obj) { 149 if (!(obj instanceof Map.Entry)) { 150 return false; 151 } 152 final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj; 153 final Object key = entry.getKey(); 154 final boolean result = parent.containsKey(key); 155 parent.remove(key); 156 return result; 157 } 158 159 @Override 160 public int size() { 161 return parent.size(); 162 } 163 } 164 /** 165 * EntrySetIterator and MapEntry 166 */ 167 static class EntrySetIterator<K, V> extends EntryIterator<K, V> implements Iterator<Map.Entry<K, V>> { 168 EntrySetIterator(final Flat3Map<K, V> parent) { 169 super(parent); 170 } 171 172 @Override 173 public Map.Entry<K, V> next() { 174 return nextEntry(); 175 } 176 } 177 static class FlatMapEntry<K, V> implements Map.Entry<K, V> { 178 private final Flat3Map<K, V> parent; 179 private final int index; 180 private volatile boolean removed; 181 182 FlatMapEntry(final Flat3Map<K, V> parent, final int index) { 183 this.parent = parent; 184 this.index = index; 185 this.removed = false; 186 } 187 188 @Override 189 public boolean equals(final Object obj) { 190 if (removed) { 191 return false; 192 } 193 if (!(obj instanceof Map.Entry)) { 194 return false; 195 } 196 final Map.Entry<?, ?> other = (Map.Entry<?, ?>) obj; 197 final Object key = getKey(); 198 final Object value = getValue(); 199 return (key == null ? other.getKey() == null : key.equals(other.getKey())) && 200 (value == null ? other.getValue() == null : value.equals(other.getValue())); 201 } 202 203 @Override 204 public K getKey() { 205 if (removed) { 206 throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID); 207 } 208 switch (index) { 209 case 3: 210 return parent.key3; 211 case 2: 212 return parent.key2; 213 case 1: 214 return parent.key1; 215 } 216 throw new IllegalStateException("Invalid map index: " + index); 217 } 218 219 @Override 220 public V getValue() { 221 if (removed) { 222 throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID); 223 } 224 switch (index) { 225 case 3: 226 return parent.value3; 227 case 2: 228 return parent.value2; 229 case 1: 230 return parent.value1; 231 } 232 throw new IllegalStateException("Invalid map index: " + index); 233 } 234 235 @Override 236 public int hashCode() { 237 if (removed) { 238 return 0; 239 } 240 final Object key = getKey(); 241 final Object value = getValue(); 242 return (key == null ? 0 : key.hashCode()) ^ 243 (value == null ? 0 : value.hashCode()); 244 } 245 246 /** 247 * Used by the iterator that created this entry to indicate that 248 * {@link java.util.Iterator#remove()} has been called. 249 * <p> 250 * As a consequence, all subsequent call to {@link #getKey()}, 251 * {@link #setValue(Object)} and {@link #getValue()} will fail. 252 * 253 * @param flag the new value of the removed flag 254 */ 255 void setRemoved(final boolean flag) { 256 this.removed = flag; 257 } 258 259 @Override 260 public V setValue(final V value) { 261 if (removed) { 262 throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID); 263 } 264 final V old = getValue(); 265 switch (index) { 266 case 3: 267 parent.value3 = value; 268 break; 269 case 2: 270 parent.value2 = value; 271 break; 272 case 1: 273 parent.value1 = value; 274 break; 275 default: 276 throw new IllegalStateException("Invalid map index: " + index); 277 } 278 return old; 279 } 280 281 @Override 282 public String toString() { 283 if (!removed) { 284 return getKey() + "=" + getValue(); 285 } 286 return ""; 287 } 288 289 } 290 /** 291 * FlatMapIterator 292 */ 293 static class FlatMapIterator<K, V> implements MapIterator<K, V>, ResettableIterator<K> { 294 private final Flat3Map<K, V> parent; 295 private int nextIndex; 296 private boolean canRemove; 297 298 FlatMapIterator(final Flat3Map<K, V> parent) { 299 this.parent = parent; 300 } 301 302 @Override 303 public K getKey() { 304 if (!canRemove) { 305 throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID); 306 } 307 switch (nextIndex) { 308 case 3: 309 return parent.key3; 310 case 2: 311 return parent.key2; 312 case 1: 313 return parent.key1; 314 } 315 throw new IllegalStateException("Invalid map index: " + nextIndex); 316 } 317 318 @Override 319 public V getValue() { 320 if (!canRemove) { 321 throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID); 322 } 323 switch (nextIndex) { 324 case 3: 325 return parent.value3; 326 case 2: 327 return parent.value2; 328 case 1: 329 return parent.value1; 330 } 331 throw new IllegalStateException("Invalid map index: " + nextIndex); 332 } 333 334 @Override 335 public boolean hasNext() { 336 return nextIndex < parent.size; 337 } 338 339 @Override 340 public K next() { 341 if (!hasNext()) { 342 throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY); 343 } 344 canRemove = true; 345 nextIndex++; 346 return getKey(); 347 } 348 349 @Override 350 public void remove() { 351 if (!canRemove) { 352 throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID); 353 } 354 parent.remove(getKey()); 355 nextIndex--; 356 canRemove = false; 357 } 358 359 @Override 360 public void reset() { 361 nextIndex = 0; 362 canRemove = false; 363 } 364 365 @Override 366 public V setValue(final V value) { 367 if (!canRemove) { 368 throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID); 369 } 370 final V old = getValue(); 371 switch (nextIndex) { 372 case 3: 373 parent.value3 = value; 374 break; 375 case 2: 376 parent.value2 = value; 377 break; 378 case 1: 379 parent.value1 = value; 380 break; 381 default: 382 throw new IllegalStateException("Invalid map index: " + nextIndex); 383 } 384 return old; 385 } 386 387 @Override 388 public String toString() { 389 if (canRemove) { 390 return "Iterator[" + getKey() + "=" + getValue() + "]"; 391 } 392 return "Iterator[]"; 393 } 394 } 395 /** 396 * KeySet 397 */ 398 static class KeySet<K> extends AbstractSet<K> { 399 private final Flat3Map<K, ?> parent; 400 401 KeySet(final Flat3Map<K, ?> parent) { 402 this.parent = parent; 403 } 404 405 @Override 406 public void clear() { 407 parent.clear(); 408 } 409 410 @Override 411 public boolean contains(final Object key) { 412 return parent.containsKey(key); 413 } 414 415 @Override 416 public Iterator<K> iterator() { 417 if (parent.delegateMap != null) { 418 return parent.delegateMap.keySet().iterator(); 419 } 420 if (parent.isEmpty()) { 421 return EmptyIterator.<K>emptyIterator(); 422 } 423 return new KeySetIterator<>(parent); 424 } 425 426 @Override 427 public boolean remove(final Object key) { 428 final boolean result = parent.containsKey(key); 429 parent.remove(key); 430 return result; 431 } 432 433 @Override 434 public int size() { 435 return parent.size(); 436 } 437 } 438 /** 439 * KeySetIterator 440 */ 441 static class KeySetIterator<K> extends EntryIterator<K, Object> implements Iterator<K> { 442 443 @SuppressWarnings("unchecked") 444 KeySetIterator(final Flat3Map<K, ?> parent) { 445 super((Flat3Map<K, Object>) parent); 446 } 447 448 @Override 449 public K next() { 450 return nextEntry().getKey(); 451 } 452 } 453 /** 454 * Values 455 */ 456 static class Values<V> extends AbstractCollection<V> { 457 private final Flat3Map<?, V> parent; 458 459 Values(final Flat3Map<?, V> parent) { 460 this.parent = parent; 461 } 462 463 @Override 464 public void clear() { 465 parent.clear(); 466 } 467 468 @Override 469 public boolean contains(final Object value) { 470 return parent.containsValue(value); 471 } 472 473 @Override 474 public Iterator<V> iterator() { 475 if (parent.delegateMap != null) { 476 return parent.delegateMap.values().iterator(); 477 } 478 if (parent.isEmpty()) { 479 return EmptyIterator.<V>emptyIterator(); 480 } 481 return new ValuesIterator<>(parent); 482 } 483 484 @Override 485 public int size() { 486 return parent.size(); 487 } 488 } 489 /** 490 * ValuesIterator 491 */ 492 static class ValuesIterator<V> extends EntryIterator<Object, V> implements Iterator<V> { 493 494 @SuppressWarnings("unchecked") 495 ValuesIterator(final Flat3Map<?, V> parent) { 496 super((Flat3Map<Object, V>) parent); 497 } 498 499 @Override 500 public V next() { 501 return nextEntry().getValue(); 502 } 503 } 504 /** Serialization version */ 505 private static final long serialVersionUID = -6701087419741928296L; 506 /** The size of the map, used while in flat mode */ 507 private transient int size; 508 /** Hash, used while in flat mode */ 509 private transient int hash1; 510 511 /** Hash, used while in flat mode */ 512 private transient int hash2; 513 514 /** Hash, used while in flat mode */ 515 private transient int hash3; 516 517 /** Key, used while in flat mode */ 518 private transient K key1; 519 520 /** Key, used while in flat mode */ 521 private transient K key2; 522 523 /** Key, used while in flat mode */ 524 private transient K key3; 525 526 /** Value, used while in flat mode */ 527 private transient V value1; 528 529 /** Value, used while in flat mode */ 530 private transient V value2; 531 532 /** Value, used while in flat mode */ 533 private transient V value3; 534 535 /** Map, used while in delegate mode */ 536 private transient AbstractHashedMap<K, V> delegateMap; 537 538 /** 539 * Constructs a new instance. 540 */ 541 public Flat3Map() { 542 } 543 544 /** 545 * Constructor copying elements from another map. 546 * 547 * @param map the map to copy 548 * @throws NullPointerException if the map is null 549 */ 550 public Flat3Map(final Map<? extends K, ? extends V> map) { 551 putAll(map); 552 } 553 554 /** 555 * Clears the map, resetting the size to zero and nullifying references 556 * to avoid garbage collection issues. 557 */ 558 @Override 559 public void clear() { 560 if (delegateMap != null) { 561 delegateMap.clear(); // should aid gc 562 delegateMap = null; // switch back to flat mode 563 } else { 564 size = 0; 565 hash1 = hash2 = hash3 = 0; 566 key1 = key2 = key3 = null; 567 value1 = value2 = value3 = null; 568 } 569 } 570 571 /** 572 * Clones the map without cloning the keys or values. 573 * 574 * @return a shallow clone 575 * @since 3.1 576 */ 577 @Override 578 @SuppressWarnings("unchecked") 579 public Flat3Map<K, V> clone() { 580 try { 581 final Flat3Map<K, V> cloned = (Flat3Map<K, V>) super.clone(); 582 if (cloned.delegateMap != null) { 583 cloned.delegateMap = cloned.delegateMap.clone(); 584 } 585 return cloned; 586 } catch (final CloneNotSupportedException ex) { 587 throw new UnsupportedOperationException(ex); 588 } 589 } 590 591 /** 592 * Checks whether the map contains the specified key. 593 * 594 * @param key the key to search for 595 * @return true if the map contains the key 596 */ 597 @Override 598 public boolean containsKey(final Object key) { 599 if (delegateMap != null) { 600 return delegateMap.containsKey(key); 601 } 602 if (key == null) { 603 switch (size) { // drop through 604 case 3: 605 if (key3 == null) { 606 return true; 607 } 608 case 2: 609 if (key2 == null) { 610 return true; 611 } 612 case 1: 613 if (key1 == null) { 614 return true; 615 } 616 } 617 } else { 618 if (size > 0) { 619 final int hashCode = key.hashCode(); 620 switch (size) { // drop through 621 case 3: 622 if (hash3 == hashCode && key.equals(key3)) { 623 return true; 624 } 625 case 2: 626 if (hash2 == hashCode && key.equals(key2)) { 627 return true; 628 } 629 case 1: 630 if (hash1 == hashCode && key.equals(key1)) { 631 return true; 632 } 633 } 634 } 635 } 636 return false; 637 } 638 639 /** 640 * Checks whether the map contains the specified value. 641 * 642 * @param value the value to search for 643 * @return true if the map contains the key 644 */ 645 @Override 646 public boolean containsValue(final Object value) { 647 if (delegateMap != null) { 648 return delegateMap.containsValue(value); 649 } 650 if (value == null) { // drop through 651 switch (size) { 652 case 3: 653 if (value3 == null) { 654 return true; 655 } 656 case 2: 657 if (value2 == null) { 658 return true; 659 } 660 case 1: 661 if (value1 == null) { 662 return true; 663 } 664 } 665 } else { 666 switch (size) { // drop through 667 case 3: 668 if (value.equals(value3)) { 669 return true; 670 } 671 case 2: 672 if (value.equals(value2)) { 673 return true; 674 } 675 case 1: 676 if (value.equals(value1)) { 677 return true; 678 } 679 } 680 } 681 return false; 682 } 683 684 /** 685 * Converts the flat map data to a map. 686 */ 687 private void convertToMap() { 688 delegateMap = createDelegateMap(); 689 switch (size) { // drop through 690 case 3: 691 delegateMap.put(key3, value3); 692 case 2: 693 delegateMap.put(key2, value2); 694 case 1: 695 delegateMap.put(key1, value1); 696 case 0: 697 break; 698 default: 699 throw new IllegalStateException("Invalid map index: " + size); 700 } 701 702 size = 0; 703 hash1 = hash2 = hash3 = 0; 704 key1 = key2 = key3 = null; 705 value1 = value2 = value3 = null; 706 } 707 708 /** 709 * Create an instance of the map used for storage when in delegation mode. 710 * <p> 711 * This can be overridden by subclasses to provide a different map implementation. 712 * Not every AbstractHashedMap is suitable, identity and reference based maps 713 * would be poor choices. 714 * 715 * @return a new AbstractHashedMap or subclass 716 * @since 3.1 717 */ 718 protected AbstractHashedMap<K, V> createDelegateMap() { 719 return new HashedMap<>(); 720 } 721 722 /** 723 * Gets the entrySet view of the map. 724 * Changes made to the view affect this map. 725 * <p> 726 * NOTE: from 4.0, the returned Map Entry will be an independent object and will 727 * not change anymore as the iterator progresses. To avoid this additional object 728 * creation and simply iterate through the entries, use {@link #mapIterator()}. 729 * 730 * @return the entrySet view 731 */ 732 @Override 733 public Set<Map.Entry<K, V>> entrySet() { 734 if (delegateMap != null) { 735 return delegateMap.entrySet(); 736 } 737 return new EntrySet<>(this); 738 } 739 740 /** 741 * Compares this map with another. 742 * 743 * @param obj the object to compare to 744 * @return true if equal 745 */ 746 @Override 747 public boolean equals(final Object obj) { 748 if (obj == this) { 749 return true; 750 } 751 if (delegateMap != null) { 752 return delegateMap.equals(obj); 753 } 754 if (!(obj instanceof Map)) { 755 return false; 756 } 757 final Map<?, ?> other = (Map<?, ?>) obj; 758 if (size != other.size()) { 759 return false; 760 } 761 if (size > 0) { 762 Object otherValue = null; 763 switch (size) { // drop through 764 case 3: 765 if (!other.containsKey(key3)) { 766 return false; 767 } 768 otherValue = other.get(key3); 769 if (!Objects.equals(value3, otherValue)) { 770 return false; 771 } 772 case 2: 773 if (!other.containsKey(key2)) { 774 return false; 775 } 776 otherValue = other.get(key2); 777 if (!Objects.equals(value2, otherValue)) { 778 return false; 779 } 780 case 1: 781 if (!other.containsKey(key1)) { 782 return false; 783 } 784 otherValue = other.get(key1); 785 if (!Objects.equals(value1, otherValue)) { 786 return false; 787 } 788 } 789 } 790 return true; 791 } 792 793 /** 794 * Gets the value mapped to the key specified. 795 * 796 * @param key the key 797 * @return the mapped value, null if no match 798 */ 799 @Override 800 public V get(final Object key) { 801 if (delegateMap != null) { 802 return delegateMap.get(key); 803 } 804 if (key == null) { 805 switch (size) { 806 // drop through 807 case 3: 808 if (key3 == null) { 809 return value3; 810 } 811 case 2: 812 if (key2 == null) { 813 return value2; 814 } 815 case 1: 816 if (key1 == null) { 817 return value1; 818 } 819 } 820 } else { 821 if (size > 0) { 822 final int hashCode = key.hashCode(); 823 switch (size) { 824 // drop through 825 case 3: 826 if (hash3 == hashCode && key.equals(key3)) { 827 return value3; 828 } 829 case 2: 830 if (hash2 == hashCode && key.equals(key2)) { 831 return value2; 832 } 833 case 1: 834 if (hash1 == hashCode && key.equals(key1)) { 835 return value1; 836 } 837 } 838 } 839 } 840 return null; 841 } 842 843 /** 844 * Gets the standard Map hashCode. 845 * 846 * @return the hash code defined in the Map interface 847 */ 848 @Override 849 public int hashCode() { 850 if (delegateMap != null) { 851 return delegateMap.hashCode(); 852 } 853 int total = 0; 854 switch (size) { // drop through 855 case 3: 856 total += hash3 ^ (value3 == null ? 0 : value3.hashCode()); 857 case 2: 858 total += hash2 ^ (value2 == null ? 0 : value2.hashCode()); 859 case 1: 860 total += hash1 ^ (value1 == null ? 0 : value1.hashCode()); 861 case 0: 862 break; 863 default: 864 throw new IllegalStateException("Invalid map index: " + size); 865 } 866 return total; 867 } 868 869 /** 870 * Checks whether the map is currently empty. 871 * 872 * @return true if the map is currently size zero 873 */ 874 @Override 875 public boolean isEmpty() { 876 return size() == 0; 877 } 878 879 /** 880 * Gets the keySet view of the map. 881 * Changes made to the view affect this map. 882 * To simply iterate through the keys, use {@link #mapIterator()}. 883 * 884 * @return the keySet view 885 */ 886 @Override 887 public Set<K> keySet() { 888 if (delegateMap != null) { 889 return delegateMap.keySet(); 890 } 891 return new KeySet<>(this); 892 } 893 894 /** 895 * Gets an iterator over the map. 896 * Changes made to the iterator affect this map. 897 * <p> 898 * A MapIterator returns the keys in the map. It also provides convenient 899 * methods to get the key and value, and set the value. 900 * It avoids the need to create an entrySet/keySet/values object. 901 * It also avoids creating the Map Entry object. 902 * 903 * @return the map iterator 904 */ 905 @Override 906 public MapIterator<K, V> mapIterator() { 907 if (delegateMap != null) { 908 return delegateMap.mapIterator(); 909 } 910 if (size == 0) { 911 return EmptyMapIterator.<K, V>emptyMapIterator(); 912 } 913 return new FlatMapIterator<>(this); 914 } 915 916 /** 917 * Puts a key-value mapping into this map. 918 * 919 * @param key the key to add 920 * @param value the value to add 921 * @return the value previously mapped to this key, null if none 922 */ 923 @Override 924 public V put(final K key, final V value) { 925 if (delegateMap != null) { 926 return delegateMap.put(key, value); 927 } 928 // change existing mapping 929 if (key == null) { 930 switch (size) { // drop through 931 case 3: 932 if (key3 == null) { 933 final V old = value3; 934 value3 = value; 935 return old; 936 } 937 case 2: 938 if (key2 == null) { 939 final V old = value2; 940 value2 = value; 941 return old; 942 } 943 case 1: 944 if (key1 == null) { 945 final V old = value1; 946 value1 = value; 947 return old; 948 } 949 } 950 } else { 951 if (size > 0) { 952 final int hashCode = key.hashCode(); 953 switch (size) { // drop through 954 case 3: 955 if (hash3 == hashCode && key.equals(key3)) { 956 final V old = value3; 957 value3 = value; 958 return old; 959 } 960 case 2: 961 if (hash2 == hashCode && key.equals(key2)) { 962 final V old = value2; 963 value2 = value; 964 return old; 965 } 966 case 1: 967 if (hash1 == hashCode && key.equals(key1)) { 968 final V old = value1; 969 value1 = value; 970 return old; 971 } 972 } 973 } 974 } 975 976 // add new mapping 977 switch (size) { 978 default: 979 convertToMap(); 980 delegateMap.put(key, value); 981 return null; 982 case 2: 983 hash3 = key == null ? 0 : key.hashCode(); 984 key3 = key; 985 value3 = value; 986 break; 987 case 1: 988 hash2 = key == null ? 0 : key.hashCode(); 989 key2 = key; 990 value2 = value; 991 break; 992 case 0: 993 hash1 = key == null ? 0 : key.hashCode(); 994 key1 = key; 995 value1 = value; 996 break; 997 } 998 size++; 999 return null; 1000 } 1001 1002 /** 1003 * Puts all the values from the specified map into this map. 1004 * 1005 * @param map the map to add 1006 * @throws NullPointerException if the map is null 1007 */ 1008 @Override 1009 public void putAll(final Map<? extends K, ? extends V> map) { 1010 final int size = map.size(); 1011 if (size == 0) { 1012 return; 1013 } 1014 if (delegateMap != null) { 1015 delegateMap.putAll(map); 1016 return; 1017 } 1018 if (size < 4) { 1019 for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 1020 put(entry.getKey(), entry.getValue()); 1021 } 1022 } else { 1023 convertToMap(); 1024 delegateMap.putAll(map); 1025 } 1026 } 1027 1028 /** 1029 * Read the map in using a custom routine. 1030 * 1031 * @param in the input stream 1032 * @throws IOException if an error occurs while reading from the stream 1033 * @throws ClassNotFoundException if an object read from the stream can not be loaded 1034 */ 1035 @SuppressWarnings("unchecked") 1036 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException { 1037 in.defaultReadObject(); 1038 final int count = in.readInt(); 1039 if (count > 3) { 1040 delegateMap = createDelegateMap(); 1041 } 1042 for (int i = count; i > 0; i--) { 1043 put((K) in.readObject(), (V) in.readObject()); 1044 } 1045 } 1046 1047 /** 1048 * Removes the specified mapping from this map. 1049 * 1050 * @param key the mapping to remove 1051 * @return the value mapped to the removed key, null if key not in map 1052 */ 1053 @Override 1054 public V remove(final Object key) { 1055 if (delegateMap != null) { 1056 return delegateMap.remove(key); 1057 } 1058 if (size == 0) { 1059 return null; 1060 } 1061 if (key == null) { 1062 switch (size) { // drop through 1063 case 3: 1064 if (key3 == null) { 1065 final V old = value3; 1066 hash3 = 0; 1067 key3 = null; 1068 value3 = null; 1069 size = 2; 1070 return old; 1071 } 1072 if (key2 == null) { 1073 final V old = value2; 1074 hash2 = hash3; 1075 key2 = key3; 1076 value2 = value3; 1077 hash3 = 0; 1078 key3 = null; 1079 value3 = null; 1080 size = 2; 1081 return old; 1082 } 1083 if (key1 == null) { 1084 final V old = value1; 1085 hash1 = hash3; 1086 key1 = key3; 1087 value1 = value3; 1088 hash3 = 0; 1089 key3 = null; 1090 value3 = null; 1091 size = 2; 1092 return old; 1093 } 1094 return null; 1095 case 2: 1096 if (key2 == null) { 1097 final V old = value2; 1098 hash2 = 0; 1099 key2 = null; 1100 value2 = null; 1101 size = 1; 1102 return old; 1103 } 1104 if (key1 == null) { 1105 final V old = value1; 1106 hash1 = hash2; 1107 key1 = key2; 1108 value1 = value2; 1109 hash2 = 0; 1110 key2 = null; 1111 value2 = null; 1112 size = 1; 1113 return old; 1114 } 1115 return null; 1116 case 1: 1117 if (key1 == null) { 1118 final V old = value1; 1119 hash1 = 0; 1120 key1 = null; 1121 value1 = null; 1122 size = 0; 1123 return old; 1124 } 1125 } 1126 } else { 1127 if (size > 0) { 1128 final int hashCode = key.hashCode(); 1129 switch (size) { // drop through 1130 case 3: 1131 if (hash3 == hashCode && key.equals(key3)) { 1132 final V old = value3; 1133 hash3 = 0; 1134 key3 = null; 1135 value3 = null; 1136 size = 2; 1137 return old; 1138 } 1139 if (hash2 == hashCode && key.equals(key2)) { 1140 final V old = value2; 1141 hash2 = hash3; 1142 key2 = key3; 1143 value2 = value3; 1144 hash3 = 0; 1145 key3 = null; 1146 value3 = null; 1147 size = 2; 1148 return old; 1149 } 1150 if (hash1 == hashCode && key.equals(key1)) { 1151 final V old = value1; 1152 hash1 = hash3; 1153 key1 = key3; 1154 value1 = value3; 1155 hash3 = 0; 1156 key3 = null; 1157 value3 = null; 1158 size = 2; 1159 return old; 1160 } 1161 return null; 1162 case 2: 1163 if (hash2 == hashCode && key.equals(key2)) { 1164 final V old = value2; 1165 hash2 = 0; 1166 key2 = null; 1167 value2 = null; 1168 size = 1; 1169 return old; 1170 } 1171 if (hash1 == hashCode && key.equals(key1)) { 1172 final V old = value1; 1173 hash1 = hash2; 1174 key1 = key2; 1175 value1 = value2; 1176 hash2 = 0; 1177 key2 = null; 1178 value2 = null; 1179 size = 1; 1180 return old; 1181 } 1182 return null; 1183 case 1: 1184 if (hash1 == hashCode && key.equals(key1)) { 1185 final V old = value1; 1186 hash1 = 0; 1187 key1 = null; 1188 value1 = null; 1189 size = 0; 1190 return old; 1191 } 1192 } 1193 } 1194 } 1195 return null; 1196 } 1197 1198 /** 1199 * Gets the size of the map. 1200 * 1201 * @return the size 1202 */ 1203 @Override 1204 public int size() { 1205 if (delegateMap != null) { 1206 return delegateMap.size(); 1207 } 1208 return size; 1209 } 1210 1211 /** 1212 * Gets the map as a String. 1213 * 1214 * @return a string version of the map 1215 */ 1216 @Override 1217 public String toString() { 1218 if (delegateMap != null) { 1219 return delegateMap.toString(); 1220 } 1221 if (size == 0) { 1222 return "{}"; 1223 } 1224 final StringBuilder buf = new StringBuilder(128); 1225 buf.append('{'); 1226 switch (size) { // drop through 1227 case 3: 1228 buf.append(key3 == this ? "(this Map)" : key3); 1229 buf.append('='); 1230 buf.append(value3 == this ? "(this Map)" : value3); 1231 buf.append(CollectionUtils.COMMA); 1232 case 2: 1233 buf.append(key2 == this ? "(this Map)" : key2); 1234 buf.append('='); 1235 buf.append(value2 == this ? "(this Map)" : value2); 1236 buf.append(CollectionUtils.COMMA); 1237 case 1: 1238 buf.append(key1 == this ? "(this Map)" : key1); 1239 buf.append('='); 1240 buf.append(value1 == this ? "(this Map)" : value1); 1241 break; 1242 // case 0: has already been dealt with 1243 default: 1244 throw new IllegalStateException("Invalid map index: " + size); 1245 } 1246 buf.append('}'); 1247 return buf.toString(); 1248 } 1249 1250 /** 1251 * Gets the values view of the map. 1252 * Changes made to the view affect this map. 1253 * To simply iterate through the values, use {@link #mapIterator()}. 1254 * 1255 * @return the values view 1256 */ 1257 @Override 1258 public Collection<V> values() { 1259 if (delegateMap != null) { 1260 return delegateMap.values(); 1261 } 1262 return new Values<>(this); 1263 } 1264 1265 /** 1266 * Write the map out using a custom routine. 1267 * 1268 * @param out the output stream 1269 * @throws IOException if an error occurs while writing to the stream 1270 */ 1271 private void writeObject(final ObjectOutputStream out) throws IOException { 1272 out.defaultWriteObject(); 1273 out.writeInt(size()); 1274 for (final MapIterator<?, ?> it = mapIterator(); it.hasNext();) { 1275 out.writeObject(it.next()); // key 1276 out.writeObject(it.getValue()); // value 1277 } 1278 } 1279 1280}