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