001 /* 002 * Copyright (c) 2009 The JOMC Project 003 * Copyright (c) 2005 Christian Schulte <cs@jomc.org> 004 * All rights reserved. 005 * 006 * Redistribution and use in source and binary forms, with or without 007 * modification, are permitted provided that the following conditions 008 * are met: 009 * 010 * o Redistributions of source code must retain the above copyright 011 * notice, this list of conditions and the following disclaimer. 012 * 013 * o Redistributions in binary form must reproduce the above copyright 014 * notice, this list of conditions and the following disclaimer in 015 * the documentation and/or other materials provided with the 016 * distribution. 017 * 018 * THIS SOFTWARE IS PROVIDED BY THE JOMC PROJECT AND CONTRIBUTORS "AS IS" 019 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 020 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 021 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE JOMC PROJECT OR 022 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 023 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 024 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 025 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 026 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 027 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 028 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 029 * 030 * $Id: WeakIdentityHashMap.java 891 2009-11-02 03:40:00Z schulte2005 $ 031 * 032 */ 033 package org.jomc.util; 034 035 import java.lang.ref.ReferenceQueue; 036 import java.lang.ref.WeakReference; 037 import java.util.AbstractCollection; 038 import java.util.AbstractSet; 039 import java.util.Collection; 040 import java.util.ConcurrentModificationException; 041 import java.util.Iterator; 042 import java.util.Map; 043 import java.util.NoSuchElementException; 044 import java.util.Set; 045 046 /** 047 * Hash-table based {@code Map} implementation with weak keys, using object-identity in place of object-equality when 048 * comparing keys. 049 * 050 * <p>In a {@code WeakIdentityHashMap} two keys {@code k1} and {@code k2} are considered equal if and only if 051 * {@code k1==k2} evaluates to {@code true}. An entry will automatically be removed when its key is no longer in 052 * ordinary use. More precisely, the presence of a mapping for a given key will not prevent the key from being discarded 053 * by the garbage collector, that is, made finalizable, finalized, and then reclaimed. When a key has been discarded its 054 * entry is effectively removed from the map, so this class behaves somewhat differently from other {@code Map} 055 * implementations and is not a general-purpose {@code Map} implementation! Although it implements the {@code Map} 056 * interface, it intentionally violates {@code Map}'s general contract, which mandates the use of the {@code equals} 057 * method when comparing objects.</p> 058 * 059 * <p>This class has performance characteristics similar to those of the {@code HashMap} class, and has the same 060 * efficiency parameters of {@code initialCapacity} and {@code loadFactor}. All of the optional map operations are 061 * provided. It does not support {@code null} values and the {@code null} key. All methods taking a key or value will 062 * throw a {@code NullPointerException} when given a {@code null} reference. No guarantees are made as to the order of 063 * the map; in particular, there is no guarantee that the order will remain constant over time. Like most collection 064 * classes, this class is not synchronized. A synchronized {@code WeakIdentityHashMap} may be constructed using the 065 * {@code Collections.synchronizedMap} method.</p> 066 * 067 * <p>The behavior of the {@code WeakIdentityHashMap} class depends in part upon the actions of the garbage collector, 068 * so several {@code Map} invariants do not hold for this class. Because the garbage collector may discard keys at 069 * any time, a {@code WeakIdentityHashMap} may behave as though an unknown thread is silently removing entries. In 070 * particular, even if synchronizing on a {@code WeakIdentityHashMap} instance and invoking none of its mutator 071 * methods, it is possible for the {@code size} method to return smaller values over time, for the {@code isEmpty} 072 * method to return {@code false} and then {@code true}, for the {@code containsKey} method to return {@code true} and 073 * later {@code false} for a given key, for the {@code get} method to return a value for a given key but later return 074 * {@code null}, for the {@code put} method to return {@code null} and the {@code remove} method to return {@code false} 075 * for a key that previously appeared to be in the map, and for successive examinations of the key set, the value 076 * collection, and the entry set to yield successively smaller numbers of elements. To protect against such situations 077 * all {@code Iterator}s and {@code Entry}s created by this class throw an {@code IllegalStateException} when a key 078 * becomes {@code null} or a mapping got removed.</p> 079 * 080 * <p>The iterators returned by the {@code iterator} method of the collections returned by all of this class's 081 * "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is 082 * created, in any way except through the iterator's own {@code remove} method, the iterator will throw a 083 * {@code ConcurrentModificationException}. Note that the fail-fast behavior of an iterator cannot be guaranteed as it 084 * is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent 085 * modification. Fail-fast iterators throw {@code ConcurrentModificationException}s on a best-effort basis. Therefore, 086 * it would be wrong to write a program that depends on this exception for its correctness: <i>the fail-fast behavior of 087 * iterators should be used only to detect bugs.</i></p> 088 * 089 * @author <a href="mailto:cs@jomc.org">Christian Schulte</a> 090 * @version $Id: WeakIdentityHashMap.java 891 2009-11-02 03:40:00Z schulte2005 $ 091 * 092 * @see java.util.HashMap 093 * @see java.util.WeakHashMap 094 * @see java.util.IdentityHashMap 095 * @see java.util.Collections#synchronizedMap 096 */ 097 public final class WeakIdentityHashMap implements Map 098 { 099 100 /** Maximum capacity of the hash-table backing the implementation ({@code 2^30}). */ 101 private static final int MAXIMUM_CAPACITY = 0x40000000; 102 103 /** Default initial capacity ({@code 2^4}). */ 104 private static final int DEFAULT_INITIAL_CAPACITY = 16; 105 106 /** Default load factor ({@code 0.75}). */ 107 private static final float DEFAULT_LOAD_FACTOR = 0.75F; 108 109 /** The number of times the map got structurally modified. */ 110 private volatile int modifications; 111 112 /** The number of mappings held by the map. */ 113 private int size; 114 115 /** The size value at which the hash table needs resizing. */ 116 private int resizeThreshold; 117 118 /** The hash-table backing the map. */ 119 private Entry[] hashTable; 120 121 /** Queue, to which weak keys are appended to. */ 122 private final ReferenceQueue referenceQueue = new ReferenceQueue(); 123 124 /** The key set view of the map. */ 125 private transient Set keySet; 126 127 /** The entry set view of the map. */ 128 private transient Set entrySet; 129 130 /** The value collection view of the map. */ 131 private transient Collection valueCollection; 132 133 /** The initial capacity of the hash table. */ 134 private final int initialCapacity; 135 136 /** The load factor for the hash table. */ 137 private final float loadFactor; 138 139 /** Null value returned by method {@link #getEntry(Object)}. */ 140 private final Entry NULL_ENTRY = new Entry( null, null, 0, this.referenceQueue ); 141 142 /** 143 * Constructs a new, empty {@code WeakIdentityHashMap} with the default initial capacity ({@code 16}) and load 144 * factor ({@code 0.75}). 145 */ 146 public WeakIdentityHashMap() 147 { 148 this( DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR ); 149 } 150 151 /** 152 * Constructs a new, empty {@code WeakIdentityHashMap} with the given initial capacity and the default load factor 153 * ({@code 0.75}). 154 * 155 * @param initialCapacity The initial capacity of the {@code WeakIdentityHashMap}. 156 * 157 * @throws IllegalArgumentException if {@code initialCapacity} is negative or greater than the maximum supported 158 * capacity ({@code 2^30}). 159 */ 160 public WeakIdentityHashMap( final int initialCapacity ) 161 { 162 this( initialCapacity, DEFAULT_LOAD_FACTOR ); 163 } 164 165 /** 166 * Constructs a new, empty {@code WeakIdentityHashMap} with the default initial capacity ({@code 16}) and the given 167 * load factor. 168 * 169 * @param loadFactor The load factor of the {@code WeakIdentityHashMap}. 170 * 171 * @throws IllegalArgumentException if {@code loadFactor} is nonpositive. 172 */ 173 public WeakIdentityHashMap( final float loadFactor ) 174 { 175 this( DEFAULT_INITIAL_CAPACITY, loadFactor ); 176 } 177 178 /** 179 * Constructs a new, empty {@code WeakIdentityHashMap} with the given initial capacity and the given load factor. 180 * 181 * @param initialCapacity The initial capacity of the {@code WeakIdentityHashMap}. 182 * @param loadFactor The load factor of the {@code WeakIdentityHashMap}. 183 * 184 * @throws IllegalArgumentException if {@code initialCapacity} is negative or greater than the maximum supported 185 * capacity ({@code 2^30}), or if {@code loadFactor} is nonpositive. 186 */ 187 public WeakIdentityHashMap( final int initialCapacity, final float loadFactor ) 188 { 189 if ( initialCapacity < 0 || initialCapacity > MAXIMUM_CAPACITY ) 190 { 191 throw new IllegalArgumentException( Integer.toString( initialCapacity ) ); 192 } 193 if ( loadFactor <= 0 || Float.isNaN( loadFactor ) ) 194 { 195 throw new IllegalArgumentException( Float.toString( loadFactor ) ); 196 } 197 198 this.initialCapacity = initialCapacity; 199 this.loadFactor = loadFactor; 200 this.resizeThreshold = initialCapacity; 201 this.size = 0; 202 this.hashTable = new Entry[ initialCapacity ]; 203 } 204 205 /** 206 * Gets the number of key-value mappings in this map. 207 * <p>If the map contains more than {@code Integer.MAX_VALUE} elements, returns {@code Integer.MAX_VALUE}.</p> 208 * 209 * @return The number of key-value mappings in this map. 210 */ 211 public int size() 212 { 213 if ( this.size > 0 ) 214 { 215 this.purge(); 216 } 217 218 return this.size; 219 } 220 221 /** 222 * Gets a flag indicating if this map is empty. 223 * 224 * @return {@code true} if this map contains no key-value mappings; {@code false} if this map contains at least one 225 * mapping. 226 */ 227 public boolean isEmpty() 228 { 229 return this.size() == 0; 230 } 231 232 /** 233 * Gets a flag indicating if this map contains a mapping for a given key. 234 * <p>More formally, returns {@code true} if and only if this map contains a mapping for a key {@code k} such that 235 * {@code key==k}. There can be at most one such mapping.</p> 236 * 237 * @param key The key whose presence in this map is to be tested. 238 * 239 * @return {@code true} if this map contains a mapping for {@code key}; {@code false} if this map does not contain a 240 * mapping for {@code key}. 241 * 242 * @throws NullPointerException if {@code key} is {@code null}. 243 */ 244 public boolean containsKey( final Object key ) 245 { 246 if ( key == null ) 247 { 248 throw new NullPointerException( "key" ); 249 } 250 251 return this.getEntry( key ).value != null; 252 } 253 254 /** 255 * Gets a flag indicating if this map maps one or more keys to the specified value. 256 * <p>More formally, this method returns {@code true} if and only if this map contains at least one mapping to a 257 * value {@code v} such that {@code value.equals(v)}. This operation requires time linear in the map size.</p> 258 * 259 * @param value The value whose presence in this map is to be tested. 260 * 261 * @return {@code true} if this map maps one or more keys to {@code value}; {@code false} if this map does not map 262 * any key to {@code value}. 263 * 264 * @throws NullPointerException if {@code value} is {@code null}. 265 */ 266 public boolean containsValue( final Object value ) 267 { 268 if ( value == null ) 269 { 270 throw new NullPointerException( "value" ); 271 } 272 273 final Entry[] table = this.getHashTable(); 274 275 for ( int i = table.length - 1; i >= 0; i-- ) 276 { 277 for ( Entry e = table[i]; e != null; e = e.next ) 278 { 279 if ( value.equals( e.value ) ) 280 { 281 return true; 282 } 283 } 284 } 285 286 return false; 287 } 288 289 /** 290 * Gets the value to which a given key is mapped, or {@code null} if this map contains no mapping for that key. 291 * <p>More formally, if this map contains a mapping from a key {@code k} to a value {@code v} such that 292 * {@code key==k}, then this method returns {@code v}; otherwise it returns {@code null}. There can be at most one 293 * such mapping.</p> 294 * 295 * @param key The key whose associated value is to be returned. 296 * 297 * @return the value to which {@code key} is mapped, or {@code null} if this map contains no mapping for 298 * {@code key}. 299 * 300 * @throws NullPointerException if {@code key} is {@code null}. 301 */ 302 public Object get( final Object key ) 303 { 304 if ( key == null ) 305 { 306 throw new NullPointerException( "key" ); 307 } 308 309 return this.getEntry( key ).value; 310 } 311 312 /** 313 * Associates a given value with a given key in this map. 314 * <p>If the map previously contained a mapping for that key, the old value is replaced by the given value.</p> 315 * 316 * @param key The key with which {@code value} is to be associated. 317 * @param value The value to be associated with {@code key}. 318 * 319 * @return the value previously associated with {@code key}, or {@code null} if there was no mapping for 320 * {@code key}. 321 * 322 * @throws NullPointerException if {@code key} or {@code value} is {@code null}. 323 */ 324 public Object put( final Object key, final Object value ) 325 { 326 if ( key == null ) 327 { 328 throw new NullPointerException( "key" ); 329 } 330 if ( value == null ) 331 { 332 throw new NullPointerException( "value" ); 333 } 334 335 final int hashCode = getHashCode( key ); 336 final Entry[] table = this.getHashTable(); 337 final int index = getHashTableIndex( hashCode, table.length ); 338 339 for ( Entry e = table[index]; e != null; e = e.next ) 340 { 341 if ( e.hashCode == hashCode && e.get() == key ) 342 { 343 final Object oldValue = e.value; 344 e.value = value; 345 return oldValue; 346 } 347 } 348 349 final Entry entry = new Entry( key, value, hashCode, this.referenceQueue ); 350 entry.next = table[index]; 351 table[index] = entry; 352 353 this.increaseSize(); 354 355 return null; 356 } 357 358 /** 359 * Removes the mapping for a given key from this map if it is present. 360 * <p>More formally, if this map contains a mapping from key {@code k} to value {@code v} such that {@code key==k}, 361 * that mapping is removed. The map can contain at most one such mapping. The map will not contain a mapping for the 362 * given key once the call returns.</p> 363 * 364 * @param key The key whose mapping is to be removed from the map. 365 * 366 * @return the value previously associated with {@code key}, or {@code null} if there was no mapping for 367 * {@code key}. 368 * 369 * @throws NullPointerException if {@code key} is {@code null}. 370 */ 371 public Object remove( final Object key ) 372 { 373 if ( key == null ) 374 { 375 throw new NullPointerException( "key" ); 376 } 377 378 final Entry[] table = this.getHashTable(); 379 final int hashCode = getHashCode( key ); 380 final int index = getHashTableIndex( hashCode, table.length ); 381 382 for ( Entry e = table[index], pre = null; e != null; pre = e, e = e.next ) 383 { 384 if ( e.hashCode == hashCode && e.get() == key ) 385 { 386 if ( pre != null ) 387 { 388 pre.next = e.next; 389 } 390 else 391 { 392 table[index] = e.next; 393 } 394 395 this.decreaseSize(); 396 this.modifications++; 397 398 final Object removed = e.value; 399 e.removed = true; 400 e.value = null; 401 e.next = null; 402 return removed; 403 } 404 } 405 406 return null; 407 } 408 409 /** 410 * Copies all of the mappings from a given map to this map. 411 * <p>The effect of this call is equivalent to that of calling {@link #put(Object,Object) put(k, v)} on this map 412 * once for each mapping from key {@code k} to value {@code v} in the given map. The behavior of this operation is 413 * undefined if the given map is modified while the operation is in progress.</p> 414 * 415 * @param m The mappings to be stored in this map. 416 * 417 * @throws NullPointerException if {@code map} is {@code null}, or if {@code map} contains {@code null} keys or 418 * values. 419 */ 420 public void putAll( final Map m ) 421 { 422 if ( m == null ) 423 { 424 throw new NullPointerException( "m" ); 425 } 426 427 for ( final Iterator it = m.entrySet().iterator(); it.hasNext(); ) 428 { 429 final Map.Entry entry = (Map.Entry) it.next(); 430 this.put( entry.getKey(), entry.getValue() ); 431 } 432 } 433 434 /** Removes all of the mappings from this map so that the map will be empty after this call returns. */ 435 @SuppressWarnings( "empty-statement" ) 436 public void clear() 437 { 438 this.purge(); 439 this.hashTable = new Entry[ this.initialCapacity ]; 440 this.size = 0; 441 this.resizeThreshold = this.initialCapacity; 442 this.modifications++; 443 while ( this.referenceQueue.poll() != null ); 444 } 445 446 /** 447 * Gets a {@code Set} view of the keys contained in this map. 448 * <p>The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is 449 * modified while an iteration over the set is in progress (except through the iterator's own {@code remove} 450 * operation), the results of the iteration are undefined, that is, the iterator may throw an 451 * {@code IllegalStateException}. The set supports element removal, which removes the corresponding mapping from the 452 * map, via the {@code Iterator.remove}, {@code Set.remove}, {@code removeAll}, {@code retainAll}, and {@code clear} 453 * operations. It does not support the {@code add} or {@code addAll} operations.</p> 454 * 455 * @return a set view of the keys contained in this map. 456 */ 457 public Set keySet() 458 { 459 if ( this.keySet == null ) 460 { 461 this.keySet = new AbstractSet() 462 { 463 464 public Iterator iterator() 465 { 466 return new EntryIterator() 467 { 468 469 @Override 470 public Object next() 471 { 472 return ( (Entry) super.next() ).getKey(); 473 } 474 475 }; 476 } 477 478 public int size() 479 { 480 return WeakIdentityHashMap.this.size(); 481 } 482 483 }; 484 485 } 486 487 return this.keySet; 488 } 489 490 /** 491 * Gets a {@code Collection} view of the values contained in this map. 492 * <p>The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. 493 * If the map is modified while an iteration over the collection is in progress (except through the iterator's own 494 * {@code remove} operation), the results of the iteration are undefined, that is, the iterator may throw an 495 * {@code IllegalStateException}. The collection supports element removal, which removes the corresponding mapping 496 * from the map, via the {@code Iterator.remove}, {@code Collection.remove}, {@code removeAll}, {@code retainAll} 497 * and {@code clear} operations. It does not support the {@code add} or {@code addAll} operations.</p> 498 * 499 * @return a collection view of the values contained in this map. 500 */ 501 public Collection values() 502 { 503 if ( this.valueCollection == null ) 504 { 505 this.valueCollection = new AbstractCollection() 506 { 507 508 public Iterator iterator() 509 { 510 return new EntryIterator() 511 { 512 513 @Override 514 public Object next() 515 { 516 return ( (Entry) super.next() ).getValue(); 517 } 518 519 }; 520 } 521 522 public int size() 523 { 524 return WeakIdentityHashMap.this.size(); 525 } 526 527 }; 528 } 529 530 return this.valueCollection; 531 } 532 533 /** 534 * Gets a {@code Set} view of the mappings contained in this map. 535 * <p>The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is 536 * modified while an iteration over the set is in progress (except through the iterator's own {@code remove} 537 * operation, or through the {@code setValue} operation on a map entry returned by the iterator) the results of the 538 * iteration are undefined, that is, the iterator may throw an {@code IllegalStateException}. The set supports 539 * element removal, which removes the corresponding mapping from the map, via the {@code Iterator.remove}, 540 * {@code Set.remove}, {@code removeAll}, {@code retainAll} and {@code clear} operations. It does not support the 541 * {@code add} or {@code addAll} operations.</p> 542 * 543 * @return a set view of the mappings contained in this map. 544 */ 545 public Set entrySet() 546 { 547 if ( this.entrySet == null ) 548 { 549 this.entrySet = new AbstractSet() 550 { 551 552 public Iterator iterator() 553 { 554 return new EntryIterator(); 555 } 556 557 public int size() 558 { 559 return WeakIdentityHashMap.this.size(); 560 } 561 562 }; 563 } 564 565 return this.entrySet; 566 } 567 568 /** 569 * Returns a string representation of the object. 570 * 571 * @return a string representation of the object. 572 */ 573 @Override 574 public String toString() 575 { 576 return super.toString() + this.internalString(); 577 } 578 579 /** 580 * Compares the specified object with this map for equality. 581 * <p>Returns {@code true} if the given object is also a map and the two maps represent the same mappings. More 582 * formally, two maps {@code m1} and {@code m2} represent the same mappings if 583 * {@code m1.entrySet().equals(m2.entrySet())}.</p> 584 * 585 * @param o The object to be compared for equality with this map. 586 * 587 * @return {@code true} if {@code o} is equal to this map; {@code false} if {@code o} is not equal to this map. 588 */ 589 @Override 590 public boolean equals( final Object o ) 591 { 592 boolean equal = this == o; 593 594 if ( !equal && o instanceof Map ) 595 { 596 final Map that = (Map) o; 597 equal = this.entrySet().equals( that.entrySet() ); 598 } 599 600 return equal; 601 } 602 603 /** 604 * Gets the hash code value for this map. 605 * <p>The hash code of a map is defined to be the sum of the hash codes of each entry in the map's 606 * {@code entrySet()} view.</p> 607 * 608 * @return the hash code value for this map. 609 */ 610 @Override 611 public int hashCode() 612 { 613 return this.entrySet().hashCode(); 614 } 615 616 /** 617 * Creates a string representing the mappings of the instance. 618 * 619 * @return a string representing the mappings of the instance. 620 */ 621 private String internalString() 622 { 623 final StringBuilder buf = new StringBuilder( 12 * this.size() ).append( '{' ); 624 final Entry[] table = this.getHashTable(); 625 for ( int i = table.length - 1, index = 0; i >= 0; i-- ) 626 { 627 for ( Entry e = table[i]; e != null; e = e.next ) 628 { 629 if ( buf.length() > 1 ) 630 { 631 buf.append( ", " ); 632 } 633 634 buf.append( '[' ).append( index++ ).append( "]=" ).append( e ); 635 } 636 } 637 638 return buf.append( '}' ).toString(); 639 } 640 641 /** 642 * Gets a hash-code value for a given key. 643 * 644 * @param key The key to get a hash-code value for. 645 * 646 * @return Hash-code value of {@code key}. 647 */ 648 private static int getHashCode( final Object key ) 649 { 650 return System.identityHashCode( key ); 651 } 652 653 /** 654 * Gets the index of a hash code value. 655 * 656 * @param hashCode The hash code value to return the index of. 657 * @param capacity The capacity to return an index for. 658 * 659 * @return the index of {@code hashCode} for {@code capacity}. 660 */ 661 private static int getHashTableIndex( final int hashCode, final int capacity ) 662 { 663 return hashCode & ( capacity - 1 ); 664 } 665 666 /** 667 * Gets the hash-table backing the instance. 668 * <p>This method creates a new hash-table and re-hashes any mappings whenever the size of the map gets greater than 669 * the capacity of the internal hash-table times the load factor value.</p> 670 * 671 * @return the hash-table backing the instance. 672 */ 673 private Entry[] getHashTable() 674 { 675 if ( this.hashTable.length < this.resizeThreshold ) 676 { 677 final Entry[] table = new Entry[ this.calculateCapacity() ]; 678 679 for ( int i = this.hashTable.length - 1; i >= 0; i-- ) 680 { 681 Entry entry = this.hashTable[i]; 682 683 while ( entry != null ) 684 { 685 final Entry next = entry.next; 686 final int index = getHashTableIndex( entry.hashCode, table.length ); 687 688 entry.next = table[index]; 689 table[index] = entry; 690 entry = next; 691 } 692 } 693 694 this.hashTable = table; 695 this.modifications++; 696 } 697 698 this.purge(); 699 return this.hashTable; 700 } 701 702 /** Removes any garbage collected entries. */ 703 private void purge() 704 { 705 Entry purge; 706 707 while ( ( purge = (Entry) this.referenceQueue.poll() ) != null ) 708 { 709 final int index = getHashTableIndex( purge.hashCode, this.hashTable.length ); 710 711 for ( Entry e = this.hashTable[index], pre = null; e != null; pre = e, e = e.next ) 712 { 713 if ( e == purge ) 714 { 715 if ( pre != null ) 716 { 717 pre.next = purge.next; 718 } 719 else 720 { 721 this.hashTable[index] = purge.next; 722 } 723 724 purge.removed = true; 725 purge.next = null; 726 purge.value = null; 727 728 this.decreaseSize(); 729 730 break; 731 } 732 } 733 } 734 } 735 736 private void increaseSize() 737 { 738 if ( this.size < Integer.MAX_VALUE ) 739 { 740 this.size++; 741 this.resizeThreshold = (int) ( this.size * this.loadFactor ); 742 } 743 744 this.modifications++; 745 } 746 747 private void decreaseSize() 748 { 749 if ( this.size > 0 ) 750 { 751 this.size--; 752 } 753 } 754 755 private int calculateCapacity() 756 { 757 int maxCapacity = this.initialCapacity; 758 if ( maxCapacity < this.resizeThreshold ) 759 { 760 maxCapacity = this.resizeThreshold > MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : this.resizeThreshold; 761 } 762 763 int capacity = 1; 764 while ( capacity < maxCapacity ) 765 { 766 capacity <<= 1; 767 } 768 769 return capacity; 770 } 771 772 private Entry getEntry( final Object key ) 773 { 774 final int hashCode = getHashCode( key ); 775 for ( Entry e = this.hashTable[getHashTableIndex( hashCode, this.hashTable.length )]; e != null; e = e.next ) 776 { 777 if ( e.hashCode == hashCode && e.get() == key ) 778 { 779 return e; 780 } 781 } 782 783 return NULL_ENTRY; 784 } 785 786 /** 787 * A map entry (key-value pair) with weakly referenced key. 788 * <p>The {@code WeakIdentityHashMap.entrySet} method returns a collection-view of the map, whose elements are of 789 * this class. The only way to obtain a reference to a map entry is from the iterator of this collection-view. These 790 * {@code Map.Entry} objects are valid only for the duration of the iteration; more formally, the behavior of a map 791 * entry is undefined if the backing map has been modified after the entry was returned by the iterator, except 792 * through the {@code setValue} operation on the map entry.</p> 793 * 794 * @see WeakIdentityHashMap#entrySet() 795 */ 796 private static class Entry extends WeakReference implements Map.Entry 797 { 798 799 /** The value of the entry. */ 800 private Object value; 801 802 /** The next entry in the bucket. */ 803 private Entry next; 804 805 /** Flag indicating that this entry got removed from the map. */ 806 private boolean removed; 807 808 /** The hash code value of the key. */ 809 private final int hashCode; 810 811 Entry( final Object key, final Object value, final int hashCode, final ReferenceQueue queue ) 812 { 813 super( key, queue ); 814 this.hashCode = hashCode; 815 this.value = value; 816 } 817 818 /** 819 * Gets the key corresponding to this entry. 820 * 821 * @return The key corresponding to this entry. 822 * 823 * @throws IllegalStateException if the entry got removed from the backing map (either due to an iterator's 824 * {@code remove} operation or due to the key having been garbage collected). 825 */ 826 public Object getKey() 827 { 828 final Object key = this.get(); 829 830 if ( key == null || this.removed ) 831 { 832 throw new IllegalStateException(); 833 } 834 835 return key; 836 } 837 838 /** 839 * Gets the value corresponding to this entry. 840 * 841 * @return the value corresponding to this entry. 842 * 843 * @throws IllegalStateException if the entry got removed from the backing map (either due to an iterator's 844 * {@code remove} operation or due to the key having been garbage collected). 845 */ 846 public Object getValue() 847 { 848 if ( this.get() == null || this.removed ) 849 { 850 throw new IllegalStateException(); 851 } 852 853 return this.value; 854 } 855 856 /** 857 * Replaces the value corresponding to this entry with the specified value. 858 * 859 * @param value The new value to be stored in this entry. 860 * 861 * @return old value corresponding to the entry. 862 * 863 * @throws NullPointerException if {@code value} is {@code null}. 864 * @throws IllegalStateException if the entry got removed from the backing map (either due to an iterator's 865 * {@code remove} operation or due to the key having been garbage collected). 866 */ 867 public Object setValue( final Object value ) 868 { 869 if ( value == null ) 870 { 871 throw new NullPointerException( "value" ); 872 } 873 if ( this.get() == null || this.removed ) 874 { 875 throw new IllegalStateException(); 876 } 877 878 final Object oldValue = this.getValue(); 879 880 if ( value != oldValue && !value.equals( oldValue ) ) 881 { 882 this.value = value; 883 } 884 885 return oldValue; 886 } 887 888 /** 889 * Returns a string representation of the object. 890 * 891 * @return a string representation of the object. 892 */ 893 @Override 894 public String toString() 895 { 896 return super.toString() + this.internalString(); 897 } 898 899 /** 900 * Compares a given object with this entry for equality. 901 * <p>Returns {@code true} if the given object is also a map entry and the two entries represent the same 902 * mapping. More formally, two entries {@code e1} and {@code e2} represent the same mapping if 903 * <pre><blockquote> 904 * ( e1.getKey() == e2.getKey() ) && 905 * ( e1.getValue().equals( e2.getValue() ) ) 906 * </blockquote></pre></p> 907 * 908 * @param o The object to be compared for equality with this map entry. 909 * 910 * @return {@code true} if {@code o} is equal to this map entry; {@code false} if {@code o} is not equal to this 911 * map entry. 912 */ 913 @Override 914 public boolean equals( final Object o ) 915 { 916 boolean equal = this == o; 917 918 if ( !equal && o instanceof Map.Entry ) 919 { 920 final Map.Entry that = (Map.Entry) o; 921 equal = this.getKey() == that.getKey() && this.getValue().equals( that.getValue() ); 922 } 923 924 return equal; 925 } 926 927 /** 928 * Gets the hash code value for this map entry. 929 * <p>The hash code of a map entry {@code e} is defined to be: 930 * <pre><blockquote> 931 * ( e.getKey() == null ? 0 : e.getKey().hashCode() ) ^ 932 * ( e.getValue() == null ? 0 : e.getValue().hashCode() ) 933 * </blockquote></pre></p> 934 * 935 * @return the hash code value for this map entry. 936 */ 937 @Override 938 public int hashCode() 939 { 940 return ( this.hashCode ) ^ ( this.getValue().hashCode() ); 941 } 942 943 /** 944 * Creates a string representing the properties of the instance. 945 * 946 * @return a string representing the properties of the instance. 947 */ 948 private String internalString() 949 { 950 final StringBuilder buf = new StringBuilder( 50 ).append( '{' ); 951 buf.append( "key=" ).append( this.getKey() ).append( ", value=" ).append( this.getValue() ); 952 return buf.append( '}' ).toString(); 953 } 954 955 } 956 957 /** An iterator over the hash-table backing the implementation. */ 958 private class EntryIterator implements Iterator 959 { 960 961 /** The next element in the iteration. */ 962 private Entry next; 963 964 /** The current element in the iteration. */ 965 private Entry current; 966 967 /** The current index into the hash-table. */ 968 private int index; 969 970 /** The number of modifications when this iterator got created. */ 971 private int modifications; 972 973 /** Creates a new {@code EntryIterator} instance. */ 974 EntryIterator() 975 { 976 final Entry[] table = getHashTable(); 977 for ( this.index = table.length - 1; this.index >= 0; this.index-- ) 978 { 979 if ( table[this.index] != null ) 980 { 981 this.next = table[this.index--]; 982 break; 983 } 984 } 985 986 this.modifications = WeakIdentityHashMap.this.modifications; 987 } 988 989 /** 990 * Gets a flag indicating that the iteration has more elements. 991 * 992 * @return {@code true} if the iterator has more elements; {@code false} if the iterator does not have more 993 * elements. 994 */ 995 public boolean hasNext() 996 { 997 if ( this.modifications != WeakIdentityHashMap.this.modifications ) 998 { 999 throw new ConcurrentModificationException(); 1000 } 1001 1002 return this.next != null; 1003 } 1004 1005 /** 1006 * Gets the next element in the iteration. 1007 * 1008 * @return the next element in the iteration. 1009 * 1010 * @throws NoSuchElementException if the iterator does not have more elements. 1011 */ 1012 public Object next() 1013 { 1014 if ( this.modifications != WeakIdentityHashMap.this.modifications ) 1015 { 1016 throw new ConcurrentModificationException(); 1017 } 1018 if ( this.next == null ) 1019 { 1020 throw new NoSuchElementException(); 1021 } 1022 1023 this.current = this.next; 1024 1025 if ( this.next.next != null ) 1026 { 1027 this.next = this.next.next; 1028 } 1029 else 1030 { 1031 this.next = null; 1032 final Entry[] table = getHashTable(); 1033 for ( ; this.index >= 0; this.index-- ) 1034 { 1035 if ( table[this.index] != null ) 1036 { 1037 this.next = table[this.index--]; 1038 break; 1039 } 1040 } 1041 } 1042 1043 return this.current; 1044 } 1045 1046 /** 1047 * Removes from the underlying hash-table the last element returned by the iterator. 1048 * 1049 * @throws IllegalStateException if the {@code next} method has not yet been called, or the {@code remove} 1050 * method has already been called after the last call to the {@code next} method. 1051 */ 1052 public void remove() 1053 { 1054 if ( this.modifications != WeakIdentityHashMap.this.modifications ) 1055 { 1056 throw new ConcurrentModificationException(); 1057 } 1058 if ( this.current == null ) 1059 { 1060 throw new IllegalStateException(); 1061 } 1062 1063 final Object key = this.current.getKey(); 1064 1065 if ( key == null ) 1066 { 1067 throw new IllegalStateException(); 1068 } 1069 1070 WeakIdentityHashMap.this.remove( key ); 1071 this.modifications = WeakIdentityHashMap.this.modifications; 1072 this.current = null; 1073 } 1074 1075 } 1076 1077 }