1// GenericsNote: Converted -- However, null keys will now be represented in the internal structures, a big change. 2/* 3 * Copyright 2003-2004 The Apache Software Foundation 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17package org.jivesoftware.smack.util.collections; 18 19import java.io.IOException; 20import java.io.ObjectInputStream; 21import java.io.ObjectOutputStream; 22import java.util.*; 23 24/** 25 * An abstract implementation of a hash-based map which provides numerous points for 26 * subclasses to override. 27 * <p/> 28 * This class implements all the features necessary for a subclass hash-based map. 29 * Key-value entries are stored in instances of the <code>HashEntry</code> class, 30 * which can be overridden and replaced. The iterators can similarly be replaced, 31 * without the need to replace the KeySet, EntrySet and Values view classes. 32 * <p/> 33 * Overridable methods are provided to change the default hashing behaviour, and 34 * to change how entries are added to and removed from the map. Hopefully, all you 35 * need for unusual subclasses is here. 36 * <p/> 37 * NOTE: From Commons Collections 3.1 this class extends AbstractMap. 38 * This is to provide backwards compatibility for ReferenceMap between v3.0 and v3.1. 39 * This extends clause will be removed in v4.0. 40 * 41 * @author java util HashMap 42 * @author Matt Hall, John Watkinson, Stephen Colebourne 43 * @version $Revision: 1.1 $ $Date: 2005/10/11 17:05:32 $ 44 * @since Commons Collections 3.0 45 */ 46public class AbstractHashedMap <K,V> extends AbstractMap<K, V> implements IterableMap<K, V> { 47 48 protected static final String NO_NEXT_ENTRY = "No next() entry in the iteration"; 49 protected static final String NO_PREVIOUS_ENTRY = "No previous() entry in the iteration"; 50 protected static final String REMOVE_INVALID = "remove() can only be called once after next()"; 51 protected static final String GETKEY_INVALID = "getKey() can only be called after next() and before remove()"; 52 protected static final String GETVALUE_INVALID = "getValue() can only be called after next() and before remove()"; 53 protected static final String SETVALUE_INVALID = "setValue() can only be called after next() and before remove()"; 54 55 /** 56 * The default capacity to use 57 */ 58 protected static final int DEFAULT_CAPACITY = 16; 59 /** 60 * The default threshold to use 61 */ 62 protected static final int DEFAULT_THRESHOLD = 12; 63 /** 64 * The default load factor to use 65 */ 66 protected static final float DEFAULT_LOAD_FACTOR = 0.75f; 67 /** 68 * The maximum capacity allowed 69 */ 70 protected static final int MAXIMUM_CAPACITY = 1 << 30; 71 /** 72 * An object for masking null 73 */ 74 protected static final Object NULL = new Object(); 75 76 /** 77 * Load factor, normally 0.75 78 */ 79 protected transient float loadFactor; 80 /** 81 * The size of the map 82 */ 83 protected transient int size; 84 /** 85 * Map entries 86 */ 87 protected transient HashEntry<K, V>[] data; 88 /** 89 * Size at which to rehash 90 */ 91 protected transient int threshold; 92 /** 93 * Modification count for iterators 94 */ 95 protected transient int modCount; 96 /** 97 * Entry set 98 */ 99 protected transient EntrySet<K, V> entrySet; 100 /** 101 * Key set 102 */ 103 protected transient KeySet<K, V> keySet; 104 /** 105 * Values 106 */ 107 protected transient Values<K, V> values; 108 109 /** 110 * Constructor only used in deserialization, do not use otherwise. 111 */ 112 protected AbstractHashedMap() { 113 super(); 114 } 115 116 /** 117 * Constructor which performs no validation on the passed in parameters. 118 * 119 * @param initialCapacity the initial capacity, must be a power of two 120 * @param loadFactor the load factor, must be > 0.0f and generally < 1.0f 121 * @param threshold the threshold, must be sensible 122 */ 123 protected AbstractHashedMap(int initialCapacity, float loadFactor, int threshold) { 124 super(); 125 this.loadFactor = loadFactor; 126 this.data = new HashEntry[initialCapacity]; 127 this.threshold = threshold; 128 init(); 129 } 130 131 /** 132 * Constructs a new, empty map with the specified initial capacity and 133 * default load factor. 134 * 135 * @param initialCapacity the initial capacity 136 * @throws IllegalArgumentException if the initial capacity is less than one 137 */ 138 protected AbstractHashedMap(int initialCapacity) { 139 this(initialCapacity, DEFAULT_LOAD_FACTOR); 140 } 141 142 /** 143 * Constructs a new, empty map with the specified initial capacity and 144 * load factor. 145 * 146 * @param initialCapacity the initial capacity 147 * @param loadFactor the load factor 148 * @throws IllegalArgumentException if the initial capacity is less than one 149 * @throws IllegalArgumentException if the load factor is less than or equal to zero 150 */ 151 protected AbstractHashedMap(int initialCapacity, float loadFactor) { 152 super(); 153 if (initialCapacity < 1) { 154 throw new IllegalArgumentException("Initial capacity must be greater than 0"); 155 } 156 if (loadFactor <= 0.0f || Float.isNaN(loadFactor)) { 157 throw new IllegalArgumentException("Load factor must be greater than 0"); 158 } 159 this.loadFactor = loadFactor; 160 this.threshold = calculateThreshold(initialCapacity, loadFactor); 161 initialCapacity = calculateNewCapacity(initialCapacity); 162 this.data = new HashEntry[initialCapacity]; 163 init(); 164 } 165 166 /** 167 * Constructor copying elements from another map. 168 * 169 * @param map the map to copy 170 * @throws NullPointerException if the map is null 171 */ 172 protected AbstractHashedMap(Map<? extends K, ? extends V> map) { 173 this(Math.max(2 * map.size(), DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); 174 putAll(map); 175 } 176 177 /** 178 * Initialise subclasses during construction, cloning or deserialization. 179 */ 180 protected void init() { 181 } 182 183 //----------------------------------------------------------------------- 184 /** 185 * Gets the value mapped to the key specified. 186 * 187 * @param key the key 188 * @return the mapped value, null if no match 189 */ 190 public V get(Object key) { 191 int hashCode = hash((key == null) ? NULL : key); 192 HashEntry<K, V> entry = data[hashIndex(hashCode, data.length)]; // no local for hash index 193 while (entry != null) { 194 if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) { 195 return entry.getValue(); 196 } 197 entry = entry.next; 198 } 199 return null; 200 } 201 202 /** 203 * Gets the size of the map. 204 * 205 * @return the size 206 */ 207 public int size() { 208 return size; 209 } 210 211 /** 212 * Checks whether the map is currently empty. 213 * 214 * @return true if the map is currently size zero 215 */ 216 public boolean isEmpty() { 217 return (size == 0); 218 } 219 220 //----------------------------------------------------------------------- 221 /** 222 * Checks whether the map contains the specified key. 223 * 224 * @param key the key to search for 225 * @return true if the map contains the key 226 */ 227 public boolean containsKey(Object key) { 228 int hashCode = hash((key == null) ? NULL : key); 229 HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index 230 while (entry != null) { 231 if (entry.hashCode == hashCode && isEqualKey(key, entry.getKey())) { 232 return true; 233 } 234 entry = entry.next; 235 } 236 return false; 237 } 238 239 /** 240 * Checks whether the map contains the specified value. 241 * 242 * @param value the value to search for 243 * @return true if the map contains the value 244 */ 245 public boolean containsValue(Object value) { 246 if (value == null) { 247 for (int i = 0, isize = data.length; i < isize; i++) { 248 HashEntry entry = data[i]; 249 while (entry != null) { 250 if (entry.getValue() == null) { 251 return true; 252 } 253 entry = entry.next; 254 } 255 } 256 } else { 257 for (int i = 0, isize = data.length; i < isize; i++) { 258 HashEntry entry = data[i]; 259 while (entry != null) { 260 if (isEqualValue(value, entry.getValue())) { 261 return true; 262 } 263 entry = entry.next; 264 } 265 } 266 } 267 return false; 268 } 269 270 //----------------------------------------------------------------------- 271 /** 272 * Puts a key-value mapping into this map. 273 * 274 * @param key the key to add 275 * @param value the value to add 276 * @return the value previously mapped to this key, null if none 277 */ 278 public V put(K key, V value) { 279 int hashCode = hash((key == null) ? NULL : key); 280 int index = hashIndex(hashCode, data.length); 281 HashEntry<K, V> entry = data[index]; 282 while (entry != null) { 283 if (entry.hashCode == hashCode && isEqualKey(key, entry.getKey())) { 284 V oldValue = entry.getValue(); 285 updateEntry(entry, value); 286 return oldValue; 287 } 288 entry = entry.next; 289 } 290 addMapping(index, hashCode, key, value); 291 return null; 292 } 293 294 /** 295 * Puts all the values from the specified map into this map. 296 * <p/> 297 * This implementation iterates around the specified map and 298 * uses {@link #put(Object, Object)}. 299 * 300 * @param map the map to add 301 * @throws NullPointerException if the map is null 302 */ 303 public void putAll(Map<? extends K, ? extends V> map) { 304 int mapSize = map.size(); 305 if (mapSize == 0) { 306 return; 307 } 308 int newSize = (int) ((size + mapSize) / loadFactor + 1); 309 ensureCapacity(calculateNewCapacity(newSize)); 310 // Have to cast here because of compiler inference problems. 311 for (Iterator it = map.entrySet().iterator(); it.hasNext();) { 312 Map.Entry<? extends K, ? extends V> entry = (Map.Entry<? extends K, ? extends V>) it.next(); 313 put(entry.getKey(), entry.getValue()); 314 } 315 } 316 317 /** 318 * Removes the specified mapping from this map. 319 * 320 * @param key the mapping to remove 321 * @return the value mapped to the removed key, null if key not in map 322 */ 323 public V remove(Object key) { 324 int hashCode = hash((key == null) ? NULL : key); 325 int index = hashIndex(hashCode, data.length); 326 HashEntry<K, V> entry = data[index]; 327 HashEntry<K, V> previous = null; 328 while (entry != null) { 329 if (entry.hashCode == hashCode && isEqualKey(key, entry.getKey())) { 330 V oldValue = entry.getValue(); 331 removeMapping(entry, index, previous); 332 return oldValue; 333 } 334 previous = entry; 335 entry = entry.next; 336 } 337 return null; 338 } 339 340 /** 341 * Clears the map, resetting the size to zero and nullifying references 342 * to avoid garbage collection issues. 343 */ 344 public void clear() { 345 modCount++; 346 HashEntry[] data = this.data; 347 for (int i = data.length - 1; i >= 0; i--) { 348 data[i] = null; 349 } 350 size = 0; 351 } 352 353 /** 354 * Gets the hash code for the key specified. 355 * This implementation uses the additional hashing routine from JDK1.4. 356 * Subclasses can override this to return alternate hash codes. 357 * 358 * @param key the key to get a hash code for 359 * @return the hash code 360 */ 361 protected int hash(Object key) { 362 // same as JDK 1.4 363 int h = key.hashCode(); 364 h += ~(h << 9); 365 h ^= (h >>> 14); 366 h += (h << 4); 367 h ^= (h >>> 10); 368 return h; 369 } 370 371 /** 372 * Compares two keys, in internal converted form, to see if they are equal. 373 * This implementation uses the equals method. 374 * Subclasses can override this to match differently. 375 * 376 * @param key1 the first key to compare passed in from outside 377 * @param key2 the second key extracted from the entry via <code>entry.key</code> 378 * @return true if equal 379 */ 380 protected boolean isEqualKey(Object key1, Object key2) { 381 return (key1 == key2 || ((key1 != null) && key1.equals(key2))); 382 } 383 384 /** 385 * Compares two values, in external form, to see if they are equal. 386 * This implementation uses the equals method and assumes neither value is null. 387 * Subclasses can override this to match differently. 388 * 389 * @param value1 the first value to compare passed in from outside 390 * @param value2 the second value extracted from the entry via <code>getValue()</code> 391 * @return true if equal 392 */ 393 protected boolean isEqualValue(Object value1, Object value2) { 394 return (value1 == value2 || value1.equals(value2)); 395 } 396 397 /** 398 * Gets the index into the data storage for the hashCode specified. 399 * This implementation uses the least significant bits of the hashCode. 400 * Subclasses can override this to return alternate bucketing. 401 * 402 * @param hashCode the hash code to use 403 * @param dataSize the size of the data to pick a bucket from 404 * @return the bucket index 405 */ 406 protected int hashIndex(int hashCode, int dataSize) { 407 return hashCode & (dataSize - 1); 408 } 409 410 //----------------------------------------------------------------------- 411 /** 412 * Gets the entry mapped to the key specified. 413 * <p/> 414 * This method exists for subclasses that may need to perform a multi-step 415 * process accessing the entry. The public methods in this class don't use this 416 * method to gain a small performance boost. 417 * 418 * @param key the key 419 * @return the entry, null if no match 420 */ 421 protected HashEntry<K, V> getEntry(Object key) { 422 int hashCode = hash((key == null) ? NULL : key); 423 HashEntry<K, V> entry = data[hashIndex(hashCode, data.length)]; // no local for hash index 424 while (entry != null) { 425 if (entry.hashCode == hashCode && isEqualKey(key, entry.getKey())) { 426 return entry; 427 } 428 entry = entry.next; 429 } 430 return null; 431 } 432 433 //----------------------------------------------------------------------- 434 /** 435 * Updates an existing key-value mapping to change the value. 436 * <p/> 437 * This implementation calls <code>setValue()</code> on the entry. 438 * Subclasses could override to handle changes to the map. 439 * 440 * @param entry the entry to update 441 * @param newValue the new value to store 442 */ 443 protected void updateEntry(HashEntry<K, V> entry, V newValue) { 444 entry.setValue(newValue); 445 } 446 447 /** 448 * Reuses an existing key-value mapping, storing completely new data. 449 * <p/> 450 * This implementation sets all the data fields on the entry. 451 * Subclasses could populate additional entry fields. 452 * 453 * @param entry the entry to update, not null 454 * @param hashIndex the index in the data array 455 * @param hashCode the hash code of the key to add 456 * @param key the key to add 457 * @param value the value to add 458 */ 459 protected void reuseEntry(HashEntry<K, V> entry, int hashIndex, int hashCode, K key, V value) { 460 entry.next = data[hashIndex]; 461 entry.hashCode = hashCode; 462 entry.key = key; 463 entry.value = value; 464 } 465 466 //----------------------------------------------------------------------- 467 /** 468 * Adds a new key-value mapping into this map. 469 * <p/> 470 * This implementation calls <code>createEntry()</code>, <code>addEntry()</code> 471 * and <code>checkCapacity()</code>. 472 * It also handles changes to <code>modCount</code> and <code>size</code>. 473 * Subclasses could override to fully control adds to the map. 474 * 475 * @param hashIndex the index into the data array to store at 476 * @param hashCode the hash code of the key to add 477 * @param key the key to add 478 * @param value the value to add 479 */ 480 protected void addMapping(int hashIndex, int hashCode, K key, V value) { 481 modCount++; 482 HashEntry<K, V> entry = createEntry(data[hashIndex], hashCode, key, value); 483 addEntry(entry, hashIndex); 484 size++; 485 checkCapacity(); 486 } 487 488 /** 489 * Creates an entry to store the key-value data. 490 * <p/> 491 * This implementation creates a new HashEntry instance. 492 * Subclasses can override this to return a different storage class, 493 * or implement caching. 494 * 495 * @param next the next entry in sequence 496 * @param hashCode the hash code to use 497 * @param key the key to store 498 * @param value the value to store 499 * @return the newly created entry 500 */ 501 protected HashEntry<K, V> createEntry(HashEntry<K, V> next, int hashCode, K key, V value) { 502 return new HashEntry<K, V>(next, hashCode, key, value); 503 } 504 505 /** 506 * Adds an entry into this map. 507 * <p/> 508 * This implementation adds the entry to the data storage table. 509 * Subclasses could override to handle changes to the map. 510 * 511 * @param entry the entry to add 512 * @param hashIndex the index into the data array to store at 513 */ 514 protected void addEntry(HashEntry<K, V> entry, int hashIndex) { 515 data[hashIndex] = entry; 516 } 517 518 //----------------------------------------------------------------------- 519 /** 520 * Removes a mapping from the map. 521 * <p/> 522 * This implementation calls <code>removeEntry()</code> and <code>destroyEntry()</code>. 523 * It also handles changes to <code>modCount</code> and <code>size</code>. 524 * Subclasses could override to fully control removals from the map. 525 * 526 * @param entry the entry to remove 527 * @param hashIndex the index into the data structure 528 * @param previous the previous entry in the chain 529 */ 530 protected void removeMapping(HashEntry<K, V> entry, int hashIndex, HashEntry<K, V> previous) { 531 modCount++; 532 removeEntry(entry, hashIndex, previous); 533 size--; 534 destroyEntry(entry); 535 } 536 537 /** 538 * Removes an entry from the chain stored in a particular index. 539 * <p/> 540 * This implementation removes the entry from the data storage table. 541 * The size is not updated. 542 * Subclasses could override to handle changes to the map. 543 * 544 * @param entry the entry to remove 545 * @param hashIndex the index into the data structure 546 * @param previous the previous entry in the chain 547 */ 548 protected void removeEntry(HashEntry<K, V> entry, int hashIndex, HashEntry<K, V> previous) { 549 if (previous == null) { 550 data[hashIndex] = entry.next; 551 } else { 552 previous.next = entry.next; 553 } 554 } 555 556 /** 557 * Kills an entry ready for the garbage collector. 558 * <p/> 559 * This implementation prepares the HashEntry for garbage collection. 560 * Subclasses can override this to implement caching (override clear as well). 561 * 562 * @param entry the entry to destroy 563 */ 564 protected void destroyEntry(HashEntry<K, V> entry) { 565 entry.next = null; 566 entry.key = null; 567 entry.value = null; 568 } 569 570 //----------------------------------------------------------------------- 571 /** 572 * Checks the capacity of the map and enlarges it if necessary. 573 * <p/> 574 * This implementation uses the threshold to check if the map needs enlarging 575 */ 576 protected void checkCapacity() { 577 if (size >= threshold) { 578 int newCapacity = data.length * 2; 579 if (newCapacity <= MAXIMUM_CAPACITY) { 580 ensureCapacity(newCapacity); 581 } 582 } 583 } 584 585 /** 586 * Changes the size of the data structure to the capacity proposed. 587 * 588 * @param newCapacity the new capacity of the array (a power of two, less or equal to max) 589 */ 590 protected void ensureCapacity(int newCapacity) { 591 int oldCapacity = data.length; 592 if (newCapacity <= oldCapacity) { 593 return; 594 } 595 if (size == 0) { 596 threshold = calculateThreshold(newCapacity, loadFactor); 597 data = new HashEntry[newCapacity]; 598 } else { 599 HashEntry<K, V> oldEntries[] = data; 600 HashEntry<K, V> newEntries[] = new HashEntry[newCapacity]; 601 602 modCount++; 603 for (int i = oldCapacity - 1; i >= 0; i--) { 604 HashEntry<K, V> entry = oldEntries[i]; 605 if (entry != null) { 606 oldEntries[i] = null; // gc 607 do { 608 HashEntry<K, V> next = entry.next; 609 int index = hashIndex(entry.hashCode, newCapacity); 610 entry.next = newEntries[index]; 611 newEntries[index] = entry; 612 entry = next; 613 } while (entry != null); 614 } 615 } 616 threshold = calculateThreshold(newCapacity, loadFactor); 617 data = newEntries; 618 } 619 } 620 621 /** 622 * Calculates the new capacity of the map. 623 * This implementation normalizes the capacity to a power of two. 624 * 625 * @param proposedCapacity the proposed capacity 626 * @return the normalized new capacity 627 */ 628 protected int calculateNewCapacity(int proposedCapacity) { 629 int newCapacity = 1; 630 if (proposedCapacity > MAXIMUM_CAPACITY) { 631 newCapacity = MAXIMUM_CAPACITY; 632 } else { 633 while (newCapacity < proposedCapacity) { 634 newCapacity <<= 1; // multiply by two 635 } 636 if (newCapacity > MAXIMUM_CAPACITY) { 637 newCapacity = MAXIMUM_CAPACITY; 638 } 639 } 640 return newCapacity; 641 } 642 643 /** 644 * Calculates the new threshold of the map, where it will be resized. 645 * This implementation uses the load factor. 646 * 647 * @param newCapacity the new capacity 648 * @param factor the load factor 649 * @return the new resize threshold 650 */ 651 protected int calculateThreshold(int newCapacity, float factor) { 652 return (int) (newCapacity * factor); 653 } 654 655 //----------------------------------------------------------------------- 656 /** 657 * Gets the <code>next</code> field from a <code>HashEntry</code>. 658 * Used in subclasses that have no visibility of the field. 659 * 660 * @param entry the entry to query, must not be null 661 * @return the <code>next</code> field of the entry 662 * @throws NullPointerException if the entry is null 663 * @since Commons Collections 3.1 664 */ 665 protected HashEntry<K, V> entryNext(HashEntry<K, V> entry) { 666 return entry.next; 667 } 668 669 /** 670 * Gets the <code>hashCode</code> field from a <code>HashEntry</code>. 671 * Used in subclasses that have no visibility of the field. 672 * 673 * @param entry the entry to query, must not be null 674 * @return the <code>hashCode</code> field of the entry 675 * @throws NullPointerException if the entry is null 676 * @since Commons Collections 3.1 677 */ 678 protected int entryHashCode(HashEntry<K, V> entry) { 679 return entry.hashCode; 680 } 681 682 /** 683 * Gets the <code>key</code> field from a <code>HashEntry</code>. 684 * Used in subclasses that have no visibility of the field. 685 * 686 * @param entry the entry to query, must not be null 687 * @return the <code>key</code> field of the entry 688 * @throws NullPointerException if the entry is null 689 * @since Commons Collections 3.1 690 */ 691 protected K entryKey(HashEntry<K, V> entry) { 692 return entry.key; 693 } 694 695 /** 696 * Gets the <code>value</code> field from a <code>HashEntry</code>. 697 * Used in subclasses that have no visibility of the field. 698 * 699 * @param entry the entry to query, must not be null 700 * @return the <code>value</code> field of the entry 701 * @throws NullPointerException if the entry is null 702 * @since Commons Collections 3.1 703 */ 704 protected V entryValue(HashEntry<K, V> entry) { 705 return entry.value; 706 } 707 708 //----------------------------------------------------------------------- 709 /** 710 * Gets an iterator over the map. 711 * Changes made to the iterator affect this map. 712 * <p/> 713 * A MapIterator returns the keys in the map. It also provides convenient 714 * methods to get the key and value, and set the value. 715 * It avoids the need to create an entrySet/keySet/values object. 716 * It also avoids creating the Map.Entry object. 717 * 718 * @return the map iterator 719 */ 720 public MapIterator<K, V> mapIterator() { 721 if (size == 0) { 722 return EmptyMapIterator.INSTANCE; 723 } 724 return new HashMapIterator<K, V>(this); 725 } 726 727 /** 728 * MapIterator implementation. 729 */ 730 protected static class HashMapIterator <K,V> extends HashIterator<K, V> implements MapIterator<K, V> { 731 732 protected HashMapIterator(AbstractHashedMap<K, V> parent) { 733 super(parent); 734 } 735 736 public K next() { 737 return super.nextEntry().getKey(); 738 } 739 740 public K getKey() { 741 HashEntry<K, V> current = currentEntry(); 742 if (current == null) { 743 throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID); 744 } 745 return current.getKey(); 746 } 747 748 public V getValue() { 749 HashEntry<K, V> current = currentEntry(); 750 if (current == null) { 751 throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID); 752 } 753 return current.getValue(); 754 } 755 756 public V setValue(V value) { 757 HashEntry<K, V> current = currentEntry(); 758 if (current == null) { 759 throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID); 760 } 761 return current.setValue(value); 762 } 763 } 764 765 //----------------------------------------------------------------------- 766 /** 767 * Gets the entrySet view of the map. 768 * Changes made to the view affect this map. 769 * To simply iterate through the entries, use {@link #mapIterator()}. 770 * 771 * @return the entrySet view 772 */ 773 public Set<Map.Entry<K, V>> entrySet() { 774 if (entrySet == null) { 775 entrySet = new EntrySet<K, V>(this); 776 } 777 return entrySet; 778 } 779 780 /** 781 * Creates an entry set iterator. 782 * Subclasses can override this to return iterators with different properties. 783 * 784 * @return the entrySet iterator 785 */ 786 protected Iterator<Map.Entry<K, V>> createEntrySetIterator() { 787 if (size() == 0) { 788 return EmptyIterator.INSTANCE; 789 } 790 return new EntrySetIterator<K, V>(this); 791 } 792 793 /** 794 * EntrySet implementation. 795 */ 796 protected static class EntrySet <K,V> extends AbstractSet<Map.Entry<K, V>> { 797 /** 798 * The parent map 799 */ 800 protected final AbstractHashedMap<K, V> parent; 801 802 protected EntrySet(AbstractHashedMap<K, V> parent) { 803 super(); 804 this.parent = parent; 805 } 806 807 public int size() { 808 return parent.size(); 809 } 810 811 public void clear() { 812 parent.clear(); 813 } 814 815 public boolean contains(Map.Entry<K, V> entry) { 816 Map.Entry<K, V> e = entry; 817 Entry<K, V> match = parent.getEntry(e.getKey()); 818 return (match != null && match.equals(e)); 819 } 820 821 public boolean remove(Object obj) { 822 if (obj instanceof Map.Entry == false) { 823 return false; 824 } 825 if (contains(obj) == false) { 826 return false; 827 } 828 Map.Entry<K, V> entry = (Map.Entry<K, V>) obj; 829 K key = entry.getKey(); 830 parent.remove(key); 831 return true; 832 } 833 834 public Iterator<Map.Entry<K, V>> iterator() { 835 return parent.createEntrySetIterator(); 836 } 837 } 838 839 /** 840 * EntrySet iterator. 841 */ 842 protected static class EntrySetIterator <K,V> extends HashIterator<K, V> implements Iterator<Map.Entry<K, V>> { 843 844 protected EntrySetIterator(AbstractHashedMap<K, V> parent) { 845 super(parent); 846 } 847 848 public HashEntry<K, V> next() { 849 return super.nextEntry(); 850 } 851 } 852 853 //----------------------------------------------------------------------- 854 /** 855 * Gets the keySet view of the map. 856 * Changes made to the view affect this map. 857 * To simply iterate through the keys, use {@link #mapIterator()}. 858 * 859 * @return the keySet view 860 */ 861 public Set<K> keySet() { 862 if (keySet == null) { 863 keySet = new KeySet<K, V>(this); 864 } 865 return keySet; 866 } 867 868 /** 869 * Creates a key set iterator. 870 * Subclasses can override this to return iterators with different properties. 871 * 872 * @return the keySet iterator 873 */ 874 protected Iterator<K> createKeySetIterator() { 875 if (size() == 0) { 876 return EmptyIterator.INSTANCE; 877 } 878 return new KeySetIterator<K, V>(this); 879 } 880 881 /** 882 * KeySet implementation. 883 */ 884 protected static class KeySet <K,V> extends AbstractSet<K> { 885 /** 886 * The parent map 887 */ 888 protected final AbstractHashedMap<K, V> parent; 889 890 protected KeySet(AbstractHashedMap<K, V> parent) { 891 super(); 892 this.parent = parent; 893 } 894 895 public int size() { 896 return parent.size(); 897 } 898 899 public void clear() { 900 parent.clear(); 901 } 902 903 public boolean contains(Object key) { 904 return parent.containsKey(key); 905 } 906 907 public boolean remove(Object key) { 908 boolean result = parent.containsKey(key); 909 parent.remove(key); 910 return result; 911 } 912 913 public Iterator<K> iterator() { 914 return parent.createKeySetIterator(); 915 } 916 } 917 918 /** 919 * KeySet iterator. 920 */ 921 protected static class KeySetIterator <K,V> extends HashIterator<K, V> implements Iterator<K> { 922 923 protected KeySetIterator(AbstractHashedMap<K, V> parent) { 924 super(parent); 925 } 926 927 public K next() { 928 return super.nextEntry().getKey(); 929 } 930 } 931 932 //----------------------------------------------------------------------- 933 /** 934 * Gets the values view of the map. 935 * Changes made to the view affect this map. 936 * To simply iterate through the values, use {@link #mapIterator()}. 937 * 938 * @return the values view 939 */ 940 public Collection<V> values() { 941 if (values == null) { 942 values = new Values(this); 943 } 944 return values; 945 } 946 947 /** 948 * Creates a values iterator. 949 * Subclasses can override this to return iterators with different properties. 950 * 951 * @return the values iterator 952 */ 953 protected Iterator<V> createValuesIterator() { 954 if (size() == 0) { 955 return EmptyIterator.INSTANCE; 956 } 957 return new ValuesIterator<K, V>(this); 958 } 959 960 /** 961 * Values implementation. 962 */ 963 protected static class Values <K,V> extends AbstractCollection<V> { 964 /** 965 * The parent map 966 */ 967 protected final AbstractHashedMap<K, V> parent; 968 969 protected Values(AbstractHashedMap<K, V> parent) { 970 super(); 971 this.parent = parent; 972 } 973 974 public int size() { 975 return parent.size(); 976 } 977 978 public void clear() { 979 parent.clear(); 980 } 981 982 public boolean contains(Object value) { 983 return parent.containsValue(value); 984 } 985 986 public Iterator<V> iterator() { 987 return parent.createValuesIterator(); 988 } 989 } 990 991 /** 992 * Values iterator. 993 */ 994 protected static class ValuesIterator <K,V> extends HashIterator<K, V> implements Iterator<V> { 995 996 protected ValuesIterator(AbstractHashedMap<K, V> parent) { 997 super(parent); 998 } 999 1000 public V next() { 1001 return super.nextEntry().getValue(); 1002 } 1003 } 1004 1005 //----------------------------------------------------------------------- 1006 /** 1007 * HashEntry used to store the data. 1008 * <p/> 1009 * If you subclass <code>AbstractHashedMap</code> but not <code>HashEntry</code> 1010 * then you will not be able to access the protected fields. 1011 * The <code>entryXxx()</code> methods on <code>AbstractHashedMap</code> exist 1012 * to provide the necessary access. 1013 */ 1014 protected static class HashEntry <K,V> implements Map.Entry<K, V>, KeyValue<K, V> { 1015 /** 1016 * The next entry in the hash chain 1017 */ 1018 protected HashEntry<K, V> next; 1019 /** 1020 * The hash code of the key 1021 */ 1022 protected int hashCode; 1023 /** 1024 * The key 1025 */ 1026 private K key; 1027 /** 1028 * The value 1029 */ 1030 private V value; 1031 1032 protected HashEntry(HashEntry<K, V> next, int hashCode, K key, V value) { 1033 super(); 1034 this.next = next; 1035 this.hashCode = hashCode; 1036 this.key = key; 1037 this.value = value; 1038 } 1039 1040 public K getKey() { 1041 return key; 1042 } 1043 1044 public void setKey(K key) { 1045 this.key = key; 1046 } 1047 1048 public V getValue() { 1049 return value; 1050 } 1051 1052 public V setValue(V value) { 1053 V old = this.value; 1054 this.value = value; 1055 return old; 1056 } 1057 1058 public boolean equals(Object obj) { 1059 if (obj == this) { 1060 return true; 1061 } 1062 if (obj instanceof Map.Entry == false) { 1063 return false; 1064 } 1065 Map.Entry other = (Map.Entry) obj; 1066 return (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey())) && (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue())); 1067 } 1068 1069 public int hashCode() { 1070 return (getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0 : getValue().hashCode()); 1071 } 1072 1073 public String toString() { 1074 return new StringBuilder().append(getKey()).append('=').append(getValue()).toString(); 1075 } 1076 } 1077 1078 /** 1079 * Base Iterator 1080 */ 1081 protected static abstract class HashIterator <K,V> { 1082 1083 /** 1084 * The parent map 1085 */ 1086 protected final AbstractHashedMap parent; 1087 /** 1088 * The current index into the array of buckets 1089 */ 1090 protected int hashIndex; 1091 /** 1092 * The last returned entry 1093 */ 1094 protected HashEntry<K, V> last; 1095 /** 1096 * The next entry 1097 */ 1098 protected HashEntry<K, V> next; 1099 /** 1100 * The modification count expected 1101 */ 1102 protected int expectedModCount; 1103 1104 protected HashIterator(AbstractHashedMap<K, V> parent) { 1105 super(); 1106 this.parent = parent; 1107 HashEntry<K, V>[] data = parent.data; 1108 int i = data.length; 1109 HashEntry<K, V> next = null; 1110 while (i > 0 && next == null) { 1111 next = data[--i]; 1112 } 1113 this.next = next; 1114 this.hashIndex = i; 1115 this.expectedModCount = parent.modCount; 1116 } 1117 1118 public boolean hasNext() { 1119 return (next != null); 1120 } 1121 1122 protected HashEntry<K, V> nextEntry() { 1123 if (parent.modCount != expectedModCount) { 1124 throw new ConcurrentModificationException(); 1125 } 1126 HashEntry<K, V> newCurrent = next; 1127 if (newCurrent == null) { 1128 throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY); 1129 } 1130 HashEntry<K, V>[] data = parent.data; 1131 int i = hashIndex; 1132 HashEntry<K, V> n = newCurrent.next; 1133 while (n == null && i > 0) { 1134 n = data[--i]; 1135 } 1136 next = n; 1137 hashIndex = i; 1138 last = newCurrent; 1139 return newCurrent; 1140 } 1141 1142 protected HashEntry<K, V> currentEntry() { 1143 return last; 1144 } 1145 1146 public void remove() { 1147 if (last == null) { 1148 throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID); 1149 } 1150 if (parent.modCount != expectedModCount) { 1151 throw new ConcurrentModificationException(); 1152 } 1153 parent.remove(last.getKey()); 1154 last = null; 1155 expectedModCount = parent.modCount; 1156 } 1157 1158 public String toString() { 1159 if (last != null) { 1160 return "Iterator[" + last.getKey() + "=" + last.getValue() + "]"; 1161 } else { 1162 return "Iterator[]"; 1163 } 1164 } 1165 } 1166 1167 //----------------------------------------------------------------------- 1168 /** 1169 * Writes the map data to the stream. This method must be overridden if a 1170 * subclass must be setup before <code>put()</code> is used. 1171 * <p/> 1172 * Serialization is not one of the JDK's nicest topics. Normal serialization will 1173 * initialise the superclass before the subclass. Sometimes however, this isn't 1174 * what you want, as in this case the <code>put()</code> method on read can be 1175 * affected by subclass state. 1176 * <p/> 1177 * The solution adopted here is to serialize the state data of this class in 1178 * this protected method. This method must be called by the 1179 * <code>writeObject()</code> of the first serializable subclass. 1180 * <p/> 1181 * Subclasses may override if they have a specific field that must be present 1182 * on read before this implementation will work. Generally, the read determines 1183 * what must be serialized here, if anything. 1184 * 1185 * @param out the output stream 1186 */ 1187 protected void doWriteObject(ObjectOutputStream out) throws IOException { 1188 out.writeFloat(loadFactor); 1189 out.writeInt(data.length); 1190 out.writeInt(size); 1191 for (MapIterator it = mapIterator(); it.hasNext();) { 1192 out.writeObject(it.next()); 1193 out.writeObject(it.getValue()); 1194 } 1195 } 1196 1197 /** 1198 * Reads the map data from the stream. This method must be overridden if a 1199 * subclass must be setup before <code>put()</code> is used. 1200 * <p/> 1201 * Serialization is not one of the JDK's nicest topics. Normal serialization will 1202 * initialise the superclass before the subclass. Sometimes however, this isn't 1203 * what you want, as in this case the <code>put()</code> method on read can be 1204 * affected by subclass state. 1205 * <p/> 1206 * The solution adopted here is to deserialize the state data of this class in 1207 * this protected method. This method must be called by the 1208 * <code>readObject()</code> of the first serializable subclass. 1209 * <p/> 1210 * Subclasses may override if the subclass has a specific field that must be present 1211 * before <code>put()</code> or <code>calculateThreshold()</code> will work correctly. 1212 * 1213 * @param in the input stream 1214 */ 1215 protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 1216 loadFactor = in.readFloat(); 1217 int capacity = in.readInt(); 1218 int size = in.readInt(); 1219 init(); 1220 data = new HashEntry[capacity]; 1221 for (int i = 0; i < size; i++) { 1222 K key = (K) in.readObject(); 1223 V value = (V) in.readObject(); 1224 put(key, value); 1225 } 1226 threshold = calculateThreshold(data.length, loadFactor); 1227 } 1228 1229 //----------------------------------------------------------------------- 1230 /** 1231 * Clones the map without cloning the keys or values. 1232 * <p/> 1233 * To implement <code>clone()</code>, a subclass must implement the 1234 * <code>Cloneable</code> interface and make this method public. 1235 * 1236 * @return a shallow clone 1237 */ 1238 protected Object clone() { 1239 try { 1240 AbstractHashedMap cloned = (AbstractHashedMap) super.clone(); 1241 cloned.data = new HashEntry[data.length]; 1242 cloned.entrySet = null; 1243 cloned.keySet = null; 1244 cloned.values = null; 1245 cloned.modCount = 0; 1246 cloned.size = 0; 1247 cloned.init(); 1248 cloned.putAll(this); 1249 return cloned; 1250 1251 } catch (CloneNotSupportedException ex) { 1252 return null; // should never happen 1253 } 1254 } 1255 1256 /** 1257 * Compares this map with another. 1258 * 1259 * @param obj the object to compare to 1260 * @return true if equal 1261 */ 1262 public boolean equals(Object obj) { 1263 if (obj == this) { 1264 return true; 1265 } 1266 if (obj instanceof Map == false) { 1267 return false; 1268 } 1269 Map map = (Map) obj; 1270 if (map.size() != size()) { 1271 return false; 1272 } 1273 MapIterator it = mapIterator(); 1274 try { 1275 while (it.hasNext()) { 1276 Object key = it.next(); 1277 Object value = it.getValue(); 1278 if (value == null) { 1279 if (map.get(key) != null || map.containsKey(key) == false) { 1280 return false; 1281 } 1282 } else { 1283 if (value.equals(map.get(key)) == false) { 1284 return false; 1285 } 1286 } 1287 } 1288 } catch (ClassCastException ignored) { 1289 return false; 1290 } catch (NullPointerException ignored) { 1291 return false; 1292 } 1293 return true; 1294 } 1295 1296 /** 1297 * Gets the standard Map hashCode. 1298 * 1299 * @return the hash code defined in the Map interface 1300 */ 1301 public int hashCode() { 1302 int total = 0; 1303 Iterator it = createEntrySetIterator(); 1304 while (it.hasNext()) { 1305 total += it.next().hashCode(); 1306 } 1307 return total; 1308 } 1309 1310 /** 1311 * Gets the map as a String. 1312 * 1313 * @return a string version of the map 1314 */ 1315 public String toString() { 1316 if (size() == 0) { 1317 return "{}"; 1318 } 1319 StringBuilder buf = new StringBuilder(32 * size()); 1320 buf.append('{'); 1321 1322 MapIterator it = mapIterator(); 1323 boolean hasNext = it.hasNext(); 1324 while (hasNext) { 1325 Object key = it.next(); 1326 Object value = it.getValue(); 1327 buf.append(key == this ? "(this Map)" : key).append('=').append(value == this ? "(this Map)" : value); 1328 1329 hasNext = it.hasNext(); 1330 if (hasNext) { 1331 buf.append(',').append(' '); 1332 } 1333 } 1334 1335 buf.append('}'); 1336 return buf.toString(); 1337 } 1338} 1339