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