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() )  &amp;&amp;
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    }