WeakIdentityHashMap.java
/*
* Copyright (C) Christian Schulte <cs@schulte.it>, 2005-206
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* o Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* o Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
* AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* $JOMC: WeakIdentityHashMap.java 5043 2015-05-27 07:03:39Z schulte $
*
*/
package org.jomc.util;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
/**
* Hash-table based {@code Map} implementation with weak keys, using object-identity in place of object-equality when
* comparing keys.
*
* <p>
* In a {@code WeakIdentityHashMap} two keys {@code k1} and {@code k2} are considered equal if and only if
* {@code k1==k2} evaluates to {@code true}. An entry will automatically be removed when its key is no longer in
* ordinary use. More precisely, the presence of a mapping for a given key will not prevent the key from being discarded
* by the garbage collector, that is, made finalizable, finalised, and then reclaimed. When a key has been discarded its
* entry is effectively removed from the map, so this class behaves somewhat differently from other {@code Map}
* implementations and is not a general-purpose {@code Map} implementation! Although it implements the {@code Map}
* interface, it intentionally violates {@code Map}'s general contract, which mandates the use of the {@code equals}
* method when comparing objects.
* </p>
*
* <p>
* This class has performance characteristics similar to those of the {@code HashMap} class, and has the same
* efficiency parameters of {@code initialCapacity} and {@code loadFactor}. All of the optional map operations are
* provided. It does not support {@code null} values and the {@code null} key. All methods taking a key or value will
* throw a {@code NullPointerException} when given a {@code null} reference. No guarantees are made as to the order of
* the map; in particular, there is no guarantee that the order will remain constant over time. Like most collection
* classes, this class is not synchronised. A synchronised {@code WeakIdentityHashMap} may be constructed using the
* {@code Collections.synchronizedMap} method.
* </p>
*
* <p>
* The behaviour of the {@code WeakIdentityHashMap} class depends in part upon the actions of the garbage collector,
* so several {@code Map} invariants do not hold for this class. Because the garbage collector may discard keys at
* any time, a {@code WeakIdentityHashMap} may behave as though an unknown thread is silently removing entries. In
* particular, even if synchronising on a {@code WeakIdentityHashMap} instance and invoking none of its mutator
* methods, it is possible for the {@code size} method to return smaller values over time, for the {@code isEmpty}
* method to return {@code false} and then {@code true}, for the {@code containsKey} method to return {@code true} and
* later {@code false} for a given key, for the {@code get} method to return a value for a given key but later return
* {@code null}, for the {@code put} method to return {@code null} and the {@code remove} method to return {@code false}
* for a key that previously appeared to be in the map, and for successive examinations of the key set, the value
* collection, and the entry set to yield successively smaller numbers of elements. To protect against such situations
* all {@code Iterator}s and {@code Entry}s created by this class throw an {@code IllegalStateException} when a key
* becomes {@code null} or a mapping got removed.
* </p>
*
* <p>
* The iterators returned by the {@code iterator} method of the collections returned by all of this classes
* "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is
* created, in any way except through the iterator's own {@code remove} method, the iterator will throw a
* {@code ConcurrentModificationException}. Note that the fail-fast behaviour of an iterator cannot be guaranteed as it
* is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronised concurrent
* modification. Fail-fast iterators throw {@code ConcurrentModificationException}s on a best-effort basis. Therefore,
* it would be wrong to write a program that depends on this exception for its correctness: <i>the fail-fast behaviour
* of iterators should be used only to detect bugs.</i>
* </p>
*
* @param <K> The type of keys maintained by this map.
* @param <V> The type of mapped values.
*
* @author <a href="mailto:cs@schulte.it">Christian Schulte</a>
* @version $JOMC: WeakIdentityHashMap.java 5043 2015-05-27 07:03:39Z schulte $
*
* @see java.util.HashMap
* @see java.util.WeakHashMap
* @see java.util.IdentityHashMap
* @see java.util.Collections#synchronizedMap
*/
public final class WeakIdentityHashMap<K, V> implements Map<K, V>
{
/**
* Maximum capacity of the hash-table backing the implementation ({@code 2^30}).
*/
private static final int MAXIMUM_CAPACITY = 0x40000000;
/**
* Default initial capacity ({@code 2^4}).
*/
private static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* Default load factor ({@code 0.75}).
*/
private static final float DEFAULT_LOAD_FACTOR = 0.75F;
/**
* The number of times the map got structurally modified.
*/
private int modifications;
/**
* The number of mappings held by the map.
*/
private int size;
/**
* The size value at which the hash table needs resizing.
*/
private int resizeThreshold;
/**
* The hash-table backing the map.
*/
private WeakEntry<K, V>[] hashTable;
/**
* Queue, to which weak keys are appended to.
*/
private final ReferenceQueue<K> referenceQueue = new ReferenceQueue<K>();
/**
* The key set view of the map.
*/
private transient Set<K> keySet;
/**
* The entry set view of the map.
*/
private transient Set<Map.Entry<K, V>> entrySet;
/**
* The value collection view of the map.
*/
private transient Collection<V> valueCollection;
/**
* The initial capacity of the hash table.
*/
private final int initialCapacity;
/**
* The load factor for the hash table.
*/
private final float loadFactor;
/**
* Null value returned by method {@link #getEntry(Object)}.
*/
private final WeakEntry<K, V> NULL_ENTRY = new WeakEntry<K, V>( null, null, 0, this.referenceQueue );
/**
* Constructs a new, empty {@code WeakIdentityHashMap} with the default initial capacity ({@code 16}) and load
* factor ({@code 0.75}).
*/
public WeakIdentityHashMap()
{
this( DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR );
}
/**
* Constructs a new, empty {@code WeakIdentityHashMap} with the given initial capacity and the default load factor
* ({@code 0.75}).
*
* @param initialCapacity The initial capacity of the {@code WeakIdentityHashMap}.
*
* @throws IllegalArgumentException if {@code initialCapacity} is negative or greater than the maximum supported
* capacity ({@code 2^30}).
*/
public WeakIdentityHashMap( final int initialCapacity )
{
this( initialCapacity, DEFAULT_LOAD_FACTOR );
}
/**
* Constructs a new, empty {@code WeakIdentityHashMap} with the default initial capacity ({@code 16}) and the given
* load factor.
*
* @param loadFactor The load factor of the {@code WeakIdentityHashMap}.
*
* @throws IllegalArgumentException if {@code loadFactor} is nonpositive.
*/
public WeakIdentityHashMap( final float loadFactor )
{
this( DEFAULT_INITIAL_CAPACITY, loadFactor );
}
/**
* Constructs a new, empty {@code WeakIdentityHashMap} with the given initial capacity and the given load factor.
*
* @param initialCapacity The initial capacity of the {@code WeakIdentityHashMap}.
* @param loadFactor The load factor of the {@code WeakIdentityHashMap}.
*
* @throws IllegalArgumentException if {@code initialCapacity} is negative or greater than the maximum supported
* capacity ({@code 2^30}), or if {@code loadFactor} is nonpositive.
*/
public WeakIdentityHashMap( final int initialCapacity, final float loadFactor )
{
if ( initialCapacity < 0 || initialCapacity > MAXIMUM_CAPACITY )
{
throw new IllegalArgumentException( Integer.toString( initialCapacity ) );
}
if ( loadFactor <= 0 || Float.isNaN( loadFactor ) )
{
throw new IllegalArgumentException( Float.toString( loadFactor ) );
}
this.initialCapacity = initialCapacity;
this.loadFactor = loadFactor;
this.resizeThreshold = initialCapacity;
this.size = 0;
this.hashTable = new WeakEntry[ initialCapacity ];
}
/**
* Gets the number of key-value mappings in this map.
* <p>
* If the map contains more than {@code Integer.MAX_VALUE} elements, returns {@code Integer.MAX_VALUE}.
* </p>
*
* @return The number of key-value mappings in this map.
*/
public int size()
{
if ( this.size > 0 )
{
this.purge();
}
return this.size;
}
/**
* Gets a flag indicating if this map is empty.
*
* @return {@code true}, if this map contains no key-value mappings; {@code false}, if this map contains at least
* one mapping.
*/
public boolean isEmpty()
{
return this.size() == 0;
}
/**
* Gets a flag indicating if this map contains a mapping for a given key.
* <p>
* More formally, returns {@code true}, if and only if this map contains a mapping for a key {@code k} such that
* {@code key==k}. There can be at most one such mapping.
* </p>
*
* @param key The key whose presence in this map is to be tested.
*
* @return {@code true}, if this map contains a mapping for {@code key}; {@code false}, if this map does not contain
* a mapping for {@code key}.
*
* @throws NullPointerException if {@code key} is {@code null}.
*/
public boolean containsKey( final Object key )
{
if ( key == null )
{
throw new NullPointerException( "key" );
}
return this.getEntry( key ).value != null;
}
/**
* Gets a flag indicating if this map maps one or more keys to the specified value.
* <p>
* More formally, this method returns {@code true}, if and only if this map contains at least one mapping to a
* value {@code v} such that {@code value.equals(v)}. This operation requires time linear in the map size.
* </p>
*
* @param value The value whose presence in this map is to be tested.
*
* @return {@code true}, if this map maps one or more keys to {@code value}; {@code false}, if this map does not map
* any key to {@code value}.
*
* @throws NullPointerException if {@code value} is {@code null}.
*/
public boolean containsValue( final Object value )
{
if ( value == null )
{
throw new NullPointerException( "value" );
}
final WeakEntry<K, V>[] table = this.getHashTable();
for ( int i = table.length - 1; i >= 0; i-- )
{
for ( WeakEntry<K, V> e = table[i]; e != null; e = e.next )
{
if ( value.equals( e.value ) )
{
return true;
}
}
}
return false;
}
/**
* Gets the value to which a given key is mapped or {@code null}, if this map contains no mapping for that key.
* <p>
* More formally, if this map contains a mapping from a key {@code k} to a value {@code v} such that
* {@code key==k}, then this method returns {@code v}; otherwise it returns {@code null}. There can be at most one
* such mapping.
* </p>
*
* @param key The key whose associated value is to be returned.
*
* @return The value to which {@code key} is mapped or {@code null}, if this map contains no mapping for
* {@code key}.
*
* @throws NullPointerException if {@code key} is {@code null}.
*/
public V get( final Object key )
{
if ( key == null )
{
throw new NullPointerException( "key" );
}
return this.getEntry( key ).value;
}
/**
* Associates a given value with a given key in this map.
* <p>
* If the map previously contained a mapping for that key, the old value is replaced by the given value.
* </p>
*
* @param key The key with which {@code value} is to be associated.
* @param value The value to be associated with {@code key}.
*
* @return The value previously associated with {@code key} or {@code null}, if there was no mapping for
* {@code key}.
*
* @throws NullPointerException if {@code key} or {@code value} is {@code null}.
*/
public V put( final K key, final V value )
{
if ( key == null )
{
throw new NullPointerException( "key" );
}
if ( value == null )
{
throw new NullPointerException( "value" );
}
final int hashCode = System.identityHashCode( key );
final WeakEntry<K, V>[] table = this.getHashTable();
final int index = getHashTableIndex( hashCode, table.length );
for ( WeakEntry<K, V> e = table[index]; e != null; e = e.next )
{
if ( e.hashCode == hashCode && e.get() == key )
{
final V oldValue = e.value;
e.value = value;
return oldValue;
}
}
final WeakEntry<K, V> entry = new WeakEntry<K, V>( key, value, hashCode, this.referenceQueue );
entry.next = table[index];
table[index] = entry;
this.increaseSize();
return null;
}
/**
* Removes the mapping for a given key from this map if it is present.
* <p>
* More formally, if this map contains a mapping from key {@code k} to value {@code v} such that {@code key==k},
* that mapping is removed. The map can contain at most one such mapping. The map will not contain a mapping for the
* given key once the call returns.
* </p>
*
* @param key The key whose mapping is to be removed from the map.
*
* @return The value previously associated with {@code key} or {@code null}, if there was no mapping for
* {@code key}.
*
* @throws NullPointerException if {@code key} is {@code null}.
*/
public V remove( final Object key )
{
if ( key == null )
{
throw new NullPointerException( "key" );
}
final WeakEntry<K, V>[] table = this.getHashTable();
final int hashCode = System.identityHashCode( key );
final int index = getHashTableIndex( hashCode, table.length );
for ( WeakEntry<K, V> e = table[index], pre = null; e != null; pre = e, e = e.next )
{
if ( e.hashCode == hashCode && e.get() == key )
{
if ( pre != null )
{
pre.next = e.next;
}
else
{
table[index] = e.next;
}
this.decreaseSize();
final V removed = e.value;
e.removed = true;
e.value = null;
e.next = null;
return removed;
}
}
return null;
}
/**
* Copies all of the mappings from a given map to this map.
* <p>
* The effect of this call is equivalent to that of calling {@link #put(Object,Object) put(k, v)} on this map
* once for each mapping from key {@code k} to value {@code v} in the given map. The behavior of this operation is
* undefined if the given map is modified while the operation is in progress.
* </p>
*
* @param m The mappings to be stored in this map.
*
* @throws NullPointerException if {@code map} is {@code null}, or if {@code map} contains {@code null} keys or
* values.
*/
public void putAll( final Map<? extends K, ? extends V> m )
{
if ( m == null )
{
throw new NullPointerException( "m" );
}
for ( final Iterator<? extends Map.Entry<? extends K, ? extends V>> it = m.entrySet().iterator();
it.hasNext(); )
{
final Map.Entry<? extends K, ? extends V> entry = it.next();
this.put( entry.getKey(), entry.getValue() );
}
}
/**
* Removes all of the mappings from this map so that the map will be empty after this call returns.
*/
@SuppressWarnings( "empty-statement" )
public void clear()
{
this.purge();
this.hashTable = new WeakEntry[ this.initialCapacity ];
this.size = 0;
this.resizeThreshold = this.initialCapacity;
this.modifications++;
while ( this.referenceQueue.poll() != null );
}
/**
* Gets a {@code Set} view of the keys contained in this map.
* <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
* modified while an iteration over the set is in progress (except through the iterator's own {@code remove}
* operation), the results of the iteration are undefined, that is, the iterator may throw an
* {@code IllegalStateException}. The set supports element removal, which removes the corresponding mapping from the
* map, via the {@code Iterator.remove}, {@code Set.remove}, {@code removeAll}, {@code retainAll}, and {@code clear}
* operations. It does not support the {@code add} or {@code addAll} operations.
* </p>
*
* @return A set view of the keys contained in this map.
*/
public Set<K> keySet()
{
if ( this.keySet == null )
{
this.keySet = new AbstractSet<K>()
{
public Iterator<K> iterator()
{
return new KeyIterator();
}
public int size()
{
return WeakIdentityHashMap.this.size();
}
};
}
return this.keySet;
}
/**
* Gets a {@code Collection} view of the values contained in this map.
* <p>
* The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa.
* If the map is modified while an iteration over the collection is in progress (except through the iterator's own
* {@code remove} operation), the results of the iteration are undefined, that is, the iterator may throw an
* {@code IllegalStateException}. The collection supports element removal, which removes the corresponding mapping
* from the map, via the {@code Iterator.remove}, {@code Collection.remove}, {@code removeAll}, {@code retainAll}
* and {@code clear} operations. It does not support the {@code add} or {@code addAll} operations.
* </p>
*
* @return A collection view of the values contained in this map.
*/
public Collection<V> values()
{
if ( this.valueCollection == null )
{
this.valueCollection = new AbstractCollection<V>()
{
public Iterator<V> iterator()
{
return new ValueIterator();
}
public int size()
{
return WeakIdentityHashMap.this.size();
}
};
}
return this.valueCollection;
}
/**
* Gets a {@code Set} view of the mappings contained in this map.
* <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
* modified while an iteration over the set is in progress (except through the iterator's own {@code remove}
* operation, or through the {@code setValue} operation on a map entry returned by the iterator) the results of the
* iteration are undefined, that is, the iterator may throw an {@code IllegalStateException}. The set supports
* element removal, which removes the corresponding mapping from the map, via the {@code Iterator.remove},
* {@code Set.remove}, {@code removeAll}, {@code retainAll} and {@code clear} operations. It does not support the
* {@code add} or {@code addAll} operations.
* </p>
*
* @return A set view of the mappings contained in this map.
*/
public Set<Map.Entry<K, V>> entrySet()
{
if ( this.entrySet == null )
{
this.entrySet = new AbstractSet<Map.Entry<K, V>>()
{
public Iterator<Map.Entry<K, V>> iterator()
{
return new EntryIterator();
}
public int size()
{
return WeakIdentityHashMap.this.size();
}
};
}
return this.entrySet;
}
/**
* Returns a string representation of the object.
*
* @return A string representation of the object.
*/
@Override
public String toString()
{
return super.toString() + this.internalString();
}
/**
* Compares the specified object with this map for equality.
* <p>
* Returns {@code true}, if the given object is also a map and the two maps represent the same mappings. More
* formally, two maps {@code m1} and {@code m2} represent the same mappings if
* {@code m1.entrySet().equals(m2.entrySet())}.
* </p>
*
* @param o The object to be compared for equality with this map.
*
* @return {@code true}, if {@code o} is equal to this map; {@code false}, if {@code o} is not equal to this map.
*/
@Override
public boolean equals( final Object o )
{
boolean equal = this == o;
if ( !equal && o instanceof Map<?, ?> )
{
final Map<?, ?> that = (Map<?, ?>) o;
equal = this.entrySet().equals( that.entrySet() );
}
return equal;
}
/**
* Gets the hash code value for this map.
* <p>
* The hash code of a map is defined to be the sum of the hash codes of each entry in the map's
* {@code entrySet()} view.
* </p>
*
* @return The hash code value for this map.
*/
@Override
public int hashCode()
{
return this.entrySet().hashCode();
}
/**
* Finalizes the object by polling the internal reference queue for any pending references.
*
* @since 1.2
*/
@Override
protected void finalize() throws Throwable
{
this.modifications++;
while ( this.referenceQueue.poll() != null );
super.finalize();
}
/**
* Creates a string representing the mappings of the instance.
*
* @return A string representing the mappings of the instance.
*/
private String internalString()
{
final StringBuilder buf = new StringBuilder( 12 * this.size() ).append( '{' );
final WeakEntry<K, V>[] table = this.getHashTable();
for ( int i = table.length - 1, index = 0; i >= 0; i-- )
{
for ( WeakEntry<K, V> e = table[i]; e != null; e = e.next )
{
if ( buf.length() > 1 )
{
buf.append( ", " );
}
buf.append( '[' ).append( index++ ).append( "]=" ).append( e );
}
}
return buf.append( '}' ).toString();
}
/**
* Gets the index of a hash code value.
*
* @param hashCode The hash code value to return the index of.
* @param capacity The capacity to return an index for.
*
* @return The index of {@code hashCode} for {@code capacity}.
*/
private static int getHashTableIndex( final int hashCode, final int capacity )
{
return hashCode & ( capacity - 1 );
}
/**
* Gets the hash-table backing the instance.
* <p>
* This method creates a new hash-table and re-hashes any mappings whenever the size of the map gets greater than
* the capacity of the internal hash-table times the load factor value.
* </p>
*
* @return The hash-table backing the instance.
*/
private WeakEntry<K, V>[] getHashTable()
{
if ( this.hashTable.length < this.resizeThreshold )
{
@SuppressWarnings( "unchecked" )
final WeakEntry<K, V>[] table = new WeakEntry[ this.calculateCapacity() ];
for ( int i = this.hashTable.length - 1; i >= 0; i-- )
{
WeakEntry<K, V> entry = this.hashTable[i];
while ( entry != null )
{
final WeakEntry<K, V> next = entry.next;
final int index = getHashTableIndex( entry.hashCode, table.length );
entry.next = table[index];
table[index] = entry;
entry = next;
}
}
this.hashTable = table;
this.modifications++;
}
this.purge();
return this.hashTable;
}
/**
* Removes any garbage collected entries.
*/
private void purge()
{
WeakEntry<K, V> purge;
while ( ( purge = (WeakEntry<K, V>) this.referenceQueue.poll() ) != null )
{
final int index = getHashTableIndex( purge.hashCode, this.hashTable.length );
for ( WeakEntry<K, V> e = this.hashTable[index], pre = null; e != null; pre = e, e = e.next )
{
if ( e == purge )
{
if ( pre != null )
{
pre.next = purge.next;
}
else
{
this.hashTable[index] = purge.next;
}
purge.removed = true;
purge.next = null;
purge.value = null;
this.decreaseSize();
break;
}
}
}
}
private void increaseSize()
{
if ( this.size < Integer.MAX_VALUE )
{
this.size++;
this.resizeThreshold = (int) ( this.size * this.loadFactor );
}
this.modifications++;
}
private void decreaseSize()
{
if ( this.size > 0 )
{
this.size--;
}
this.modifications++;
}
private int calculateCapacity()
{
int maxCapacity = this.initialCapacity;
if ( maxCapacity < this.resizeThreshold )
{
maxCapacity = this.resizeThreshold > MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : this.resizeThreshold;
}
int capacity = 1;
while ( capacity < maxCapacity )
{
capacity <<= 1;
}
return capacity;
}
private WeakEntry<K, V> getEntry( final Object key )
{
final int hashCode = System.identityHashCode( key );
final WeakEntry<K, V>[] table = getHashTable();
for ( WeakEntry<K, V> e = table[getHashTableIndex( hashCode, table.length )]; e != null; e = e.next )
{
if ( e.hashCode == hashCode && e.get() == key )
{
return e;
}
}
return NULL_ENTRY;
}
/**
* A map entry (key-value pair) with weakly referenced key.
* <p>
* The {@code WeakIdentityHashMap.entrySet} method returns a collection-view of the map, whose elements are of
* this class. The only way to obtain a reference to a map entry is from the iterator of this collection-view. These
* {@code Map.Entry} objects are valid only for the duration of the iteration; more formally, the behavior of a map
* entry is undefined if the backing map has been modified after the entry was returned by the iterator, except
* through the {@code setValue} operation on the map entry.
* </p>
*
* @param <K> The type of the key.
* @param <V> The type of the value.
*
* @see WeakIdentityHashMap#entrySet()
*/
private static class WeakEntry<K, V> extends WeakReference<K> implements Map.Entry<K, V>
{
/**
* The value of the entry.
*/
private V value;
/**
* The next entry in the bucket.
*/
private WeakEntry<K, V> next;
/**
* Flag indicating that this entry got removed from the map.
*/
private boolean removed;
/**
* The hash code value of the key.
*/
private final int hashCode;
WeakEntry( final K key, final V value, final int hashCode, final ReferenceQueue<K> queue )
{
super( key, queue );
this.hashCode = hashCode;
this.value = value;
}
/**
* Gets the key corresponding to this entry.
*
* @return The key corresponding to this entry.
*
* @throws IllegalStateException if the entry got removed from the backing map (either due to an iterator's
* {@code remove} operation or due to the key having been garbage collected).
*/
public K getKey()
{
final K key = this.get();
if ( key == null || this.removed )
{
throw new IllegalStateException();
}
return key;
}
/**
* Gets the value corresponding to this entry.
*
* @return The value corresponding to this entry.
*
* @throws IllegalStateException if the entry got removed from the backing map (either due to an iterator's
* {@code remove} operation or due to the key having been garbage collected).
*/
public V getValue()
{
if ( this.get() == null || this.removed )
{
throw new IllegalStateException();
}
return this.value;
}
/**
* Replaces the value corresponding to this entry with the specified value.
*
* @param value The new value to be stored in this entry.
*
* @return The old value corresponding to the entry.
*
* @throws NullPointerException if {@code value} is {@code null}.
* @throws IllegalStateException if the entry got removed from the backing map (either due to an iterator's
* {@code remove} operation or due to the key having been garbage collected).
*/
public V setValue( final V value )
{
if ( value == null )
{
throw new NullPointerException( "value" );
}
if ( this.get() == null || this.removed )
{
throw new IllegalStateException();
}
final V oldValue = this.getValue();
if ( value != oldValue && !value.equals( oldValue ) )
{
this.value = value;
}
return oldValue;
}
/**
* Returns a string representation of the object.
*
* @return A string representation of the object.
*/
@Override
public String toString()
{
return super.toString() + this.internalString();
}
/**
* Compares a given object with this entry for equality.
* <p>
* Returns {@code true}, if the given object is also a map entry and the two entries represent the same
* mapping. More formally, two entries {@code e1} and {@code e2} represent the same mapping if
* <pre><blockquote>
* ( e1.getKey() == e2.getKey() ) &&
* ( e1.getValue().equals( e2.getValue() ) )
* </blockquote></pre></p>
*
* @param o The object to be compared for equality with this map entry.
*
* @return {@code true}, if {@code o} is equal to this map entry; {@code false}, if {@code o} is not equal to
* this map entry.
*/
@Override
public boolean equals( final Object o )
{
boolean equal = this == o;
if ( !equal && o instanceof Map.Entry<?, ?> )
{
final Map.Entry<?, ?> that = (Map.Entry<?, ?>) o;
equal = this.getKey() == that.getKey() && this.getValue().equals( that.getValue() );
}
return equal;
}
/**
* Gets the hash code value for this map entry.
* <p>
* The hash code of a map entry {@code e} is defined to be:
* <pre><blockquote>
* ( e.getKey() == null ? 0 : e.getKey().hashCode() ) ^
* ( e.getValue() == null ? 0 : e.getValue().hashCode() )
* </blockquote></pre></p>
*
* @return The hash code value for this map entry.
*/
@Override
public int hashCode()
{
return ( this.hashCode ) ^ ( this.getValue().hashCode() );
}
/**
* Creates a string representing the properties of the instance.
*
* @return A string representing the properties of the instance.
*/
private String internalString()
{
final StringBuilder buf = new StringBuilder( 50 ).append( '{' );
buf.append( "key=" ).append( this.getKey() ).append( ", value=" ).append( this.getValue() );
return buf.append( '}' ).toString();
}
}
/**
* Base iterator implementation over the hash-table backing the implementation.
*/
private class WeakEntryIterator
{
/**
* The next element in the iteration.
*/
private WeakEntry<K, V> next;
/**
* The current element in the iteration.
*/
private WeakEntry<K, V> current;
/**
* The current index into the hash-table.
*/
private int index;
/**
* The number of modifications when this iterator got created.
*/
private int modifications;
/**
* Creates a new {@code WeakEntryIterator} instance.
*/
WeakEntryIterator()
{
final WeakEntry<K, V>[] table = getHashTable();
for ( this.index = table.length - 1; this.index >= 0; this.index-- )
{
if ( table[this.index] != null )
{
this.next = table[this.index--];
break;
}
}
this.modifications = WeakIdentityHashMap.this.modifications;
}
/**
* Gets a flag indicating that the iteration has more elements.
*
* @return {@code true}, if the iterator has more elements; {@code false}, if the iterator does not have more
* elements.
*/
public boolean hasNext()
{
if ( this.modifications != WeakIdentityHashMap.this.modifications )
{
throw new ConcurrentModificationException();
}
return this.next != null;
}
/**
* Gets the next element in the iteration.
*
* @return The next element in the iteration.
*
* @throws NoSuchElementException if the iterator does not have more elements.
*/
public Map.Entry<K, V> nextElement()
{
if ( this.modifications != WeakIdentityHashMap.this.modifications )
{
throw new ConcurrentModificationException();
}
if ( this.next == null )
{
throw new NoSuchElementException();
}
this.current = this.next;
if ( this.next.next != null )
{
this.next = this.next.next;
}
else
{
this.next = null;
final WeakEntry<K, V>[] table = getHashTable();
for ( ; this.index >= 0; this.index-- )
{
if ( table[this.index] != null )
{
this.next = table[this.index--];
break;
}
}
}
return this.current;
}
/**
* Removes from the underlying hash-table the last element returned by the iterator.
*
* @throws IllegalStateException if the {@code next} method has not yet been called, or the {@code remove}
* method has already been called after the last call to the {@code next} method.
*/
public void remove()
{
if ( this.modifications != WeakIdentityHashMap.this.modifications )
{
throw new ConcurrentModificationException();
}
if ( this.current == null )
{
throw new IllegalStateException();
}
final K key = this.current.getKey();
if ( key == null )
{
throw new IllegalStateException();
}
WeakIdentityHashMap.this.remove( key );
this.modifications = WeakIdentityHashMap.this.modifications;
this.current = null;
}
}
/**
* Iterator over the hash-table backing the implementation.
*/
private class EntryIterator extends WeakEntryIterator implements Iterator<Map.Entry<K, V>>
{
/**
* Creates a new {@code EntryIterator} instance.
*/
EntryIterator()
{
super();
}
/**
* Gets the next element in the iteration.
*
* @return The next element in the iteration.
*
* @throws NoSuchElementException if the iterator does not have more elements.
*/
public Map.Entry<K, V> next()
{
return super.nextElement();
}
}
/**
* Iterator over the hash-table backing the implementation.
*/
private class KeyIterator extends WeakEntryIterator implements Iterator<K>
{
/**
* Creates a new {@code KeyIterator} instance.
*/
KeyIterator()
{
super();
}
/**
* Gets the next element in the iteration.
*
* @return The next element in the iteration.
*
* @throws NoSuchElementException if the iterator does not have more elements.
*/
public K next()
{
return super.nextElement().getKey();
}
}
/**
* Iterator over the hash-table backing the implementation.
*/
private class ValueIterator extends WeakEntryIterator implements Iterator<V>
{
/**
* Creates a new {@code ValueIterator} instance.
*/
ValueIterator()
{
super();
}
/**
* Gets the next element in the iteration.
*
* @return The next element in the iteration.
*
* @throws NoSuchElementException if the iterator does not have more elements.
*/
public V next()
{
return super.nextElement().getValue();
}
}
}