You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by te...@apache.org on 2006/08/07 17:41:48 UTC
svn commit: r429370 -
/incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
Author: tellison
Date: Mon Aug 7 08:41:47 2006
New Revision: 429370
URL: http://svn.apache.org/viewvc?rev=429370&view=rev
Log:
Cody reformatting, fix minor compiler warning.
Modified:
incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
Modified: incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java?rev=429370&r1=429369&r2=429370&view=diff
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java (original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java Mon Aug 7 08:41:47 2006
@@ -15,7 +15,6 @@
package java.util;
-
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
@@ -37,732 +36,741 @@
*
* @since 1.4
*/
-public class IdentityHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Serializable,
- Cloneable {
+public class IdentityHashMap<K, V> extends AbstractMap<K, V> implements
+ Map<K, V>, Serializable, Cloneable {
- private static final long serialVersionUID = 8188218128353913216L;
+ private static final long serialVersionUID = 8188218128353913216L;
- /*
- * The internal data structure to hold key value pairs This array holds keys
- * and values in an alternating fashion.
- */
- transient Object[] elementData;
-
- /* Actual number of key-value pairs. */
- int size;
-
- /*
- * maximum number of elements that can be put in this map before having to
- * rehash.
- */
- transient int threshold;
-
- /*
- * default threshold value that an IdentityHashMap created using the default
- * constructor would have.
- */
- private static final int DEFAULT_MAX_SIZE = 21;
-
- /* Default load factor of 0.75; */
- private static final int loadFactor = 7500;
-
- /*
- * modification count, to keep track of structural modifications between
- * the IdentityHashMap and the iterator
- */
- transient int modCount = 0;
-
- /* Object used to represent null keys and values.
- * This is used to differentiate a literal 'null' key
- * value pair from an empty spot in the map.
- */
- private static final Object NULL_OBJECT = new Object();
-
- static class IdentityHashMapEntry<K, V> extends MapEntry<K, V> {
- IdentityHashMapEntry(K theKey, V theValue) {
- super(theKey, theValue);
- }
+ /*
+ * The internal data structure to hold key value pairs This array holds keys
+ * and values in an alternating fashion.
+ */
+ transient Object[] elementData;
+
+ /* Actual number of key-value pairs. */
+ int size;
+
+ /*
+ * maximum number of elements that can be put in this map before having to
+ * rehash.
+ */
+ transient int threshold;
+
+ /*
+ * default threshold value that an IdentityHashMap created using the default
+ * constructor would have.
+ */
+ private static final int DEFAULT_MAX_SIZE = 21;
+
+ /* Default load factor of 0.75; */
+ private static final int loadFactor = 7500;
+
+ /*
+ * modification count, to keep track of structural modifications between the
+ * IdentityHashMap and the iterator
+ */
+ transient int modCount = 0;
+
+ /*
+ * Object used to represent null keys and values. This is used to
+ * differentiate a literal 'null' key value pair from an empty spot in the
+ * map.
+ */
+ private static final Object NULL_OBJECT = new Object();
+
+ static class IdentityHashMapEntry<K, V> extends MapEntry<K, V> {
+ IdentityHashMapEntry(K theKey, V theValue) {
+ super(theKey, theValue);
+ }
- @Override
+ @Override
public Object clone() {
- return super.clone();
- }
+ return super.clone();
+ }
- @Override
+ @Override
public boolean equals(Object object) {
- if (this == object) {
+ if (this == object) {
return true;
}
- if (object instanceof Map.Entry) {
- Map.Entry<?, ?> entry = (Map.Entry) object;
- return (key == entry.getKey()) && (value == entry.getValue());
- }
- return false;
- }
+ if (object instanceof Map.Entry) {
+ Map.Entry<?, ?> entry = (Map.Entry) object;
+ return (key == entry.getKey()) && (value == entry.getValue());
+ }
+ return false;
+ }
- @Override
+ @Override
public int hashCode() {
- return System.identityHashCode(key)
- ^ System.identityHashCode(value);
- }
+ return System.identityHashCode(key)
+ ^ System.identityHashCode(value);
+ }
- @Override
+ @Override
public String toString() {
- return key + "=" + value;
- }
- }
+ return key + "=" + value; //$NON-NLS-1$
+ }
+ }
- static class IdentityHashMapIterator<E, KT, VT> implements Iterator<E> {
- private int position = 0; // the current position
+ static class IdentityHashMapIterator<E, KT, VT> implements Iterator<E> {
+ private int position = 0; // the current position
- // the position of the entry that was last returned from next()
- private int lastPosition = 0;
+ // the position of the entry that was last returned from next()
+ private int lastPosition = 0;
- final IdentityHashMap<KT, VT> associatedMap;
+ final IdentityHashMap<KT, VT> associatedMap;
- int expectedModCount;
+ int expectedModCount;
- final MapEntry.Type<E, KT, VT> type;
+ final MapEntry.Type<E, KT, VT> type;
- boolean canRemove = false;
+ boolean canRemove = false;
- IdentityHashMapIterator(MapEntry.Type<E, KT, VT> value, IdentityHashMap<KT, VT> hm) {
- associatedMap = hm;
- type = value;
- expectedModCount = hm.modCount;
- }
+ IdentityHashMapIterator(MapEntry.Type<E, KT, VT> value,
+ IdentityHashMap<KT, VT> hm) {
+ associatedMap = hm;
+ type = value;
+ expectedModCount = hm.modCount;
+ }
- public boolean hasNext() {
- while (position < associatedMap.elementData.length) {
- // if this is an empty spot, go to the next one
- if (associatedMap.elementData[position] == null) {
+ public boolean hasNext() {
+ while (position < associatedMap.elementData.length) {
+ // if this is an empty spot, go to the next one
+ if (associatedMap.elementData[position] == null) {
position += 2;
} else {
return true;
}
- }
- return false;
- }
+ }
+ return false;
+ }
- void checkConcurrentMod() throws ConcurrentModificationException {
- if (expectedModCount != associatedMap.modCount) {
+ void checkConcurrentMod() throws ConcurrentModificationException {
+ if (expectedModCount != associatedMap.modCount) {
throw new ConcurrentModificationException();
}
- }
+ }
- public E next() {
- checkConcurrentMod();
- if (!hasNext()) {
+ public E next() {
+ checkConcurrentMod();
+ if (!hasNext()) {
throw new NoSuchElementException();
}
-
- IdentityHashMapEntry<KT, VT> result = associatedMap.getEntry(position);
- lastPosition = position;
- position += 2;
-
- canRemove = true;
- return type.get(result);
- }
-
- public void remove() {
- checkConcurrentMod();
- if (!canRemove) {
+
+ IdentityHashMapEntry<KT, VT> result = associatedMap
+ .getEntry(position);
+ lastPosition = position;
+ position += 2;
+
+ canRemove = true;
+ return type.get(result);
+ }
+
+ public void remove() {
+ checkConcurrentMod();
+ if (!canRemove) {
throw new IllegalStateException();
}
-
- canRemove = false;
- associatedMap.remove(associatedMap.elementData[lastPosition]);
- position = lastPosition;
- expectedModCount++;
- }
- }
-
- static class IdentityHashMapEntrySet<KT,VT> extends AbstractSet<Map.Entry<KT, VT>> {
- private final IdentityHashMap<KT,VT> associatedMap;
-
- public IdentityHashMapEntrySet(IdentityHashMap<KT,VT> hm) {
- associatedMap = hm;
- }
-
- IdentityHashMap<KT,VT> hashMap() {
- return associatedMap;
- }
- @Override
+ canRemove = false;
+ associatedMap.remove(associatedMap.elementData[lastPosition]);
+ position = lastPosition;
+ expectedModCount++;
+ }
+ }
+
+ static class IdentityHashMapEntrySet<KT, VT> extends
+ AbstractSet<Map.Entry<KT, VT>> {
+ private final IdentityHashMap<KT, VT> associatedMap;
+
+ public IdentityHashMapEntrySet(IdentityHashMap<KT, VT> hm) {
+ associatedMap = hm;
+ }
+
+ IdentityHashMap<KT, VT> hashMap() {
+ return associatedMap;
+ }
+
+ @Override
public int size() {
- return associatedMap.size;
- }
+ return associatedMap.size;
+ }
- @Override
+ @Override
public void clear() {
- associatedMap.clear();
- }
+ associatedMap.clear();
+ }
- @Override
+ @Override
public boolean remove(Object object) {
- if (contains(object)) {
- associatedMap.remove(((Map.Entry) object).getKey());
- return true;
- }
- return false;
- }
+ if (contains(object)) {
+ associatedMap.remove(((Map.Entry) object).getKey());
+ return true;
+ }
+ return false;
+ }
- @Override
+ @Override
public boolean contains(Object object) {
- if (object instanceof Map.Entry) {
- IdentityHashMapEntry<?, ?> entry = associatedMap
- .getEntry(((Map.Entry) object).getKey());
- // we must call equals on the entry obtained from "this"
- return entry != null && entry.equals(object);
- }
- return false;
- }
+ if (object instanceof Map.Entry) {
+ IdentityHashMapEntry<?, ?> entry = associatedMap
+ .getEntry(((Map.Entry) object).getKey());
+ // we must call equals on the entry obtained from "this"
+ return entry != null && entry.equals(object);
+ }
+ return false;
+ }
- @Override
+ @Override
public Iterator<Map.Entry<KT, VT>> iterator() {
- return new IdentityHashMapIterator<Map.Entry<KT,VT>,KT,VT>(new MapEntry.Type<Map.Entry<KT,VT>, KT, VT>() {
- public Map.Entry<KT,VT> get(MapEntry<KT,VT> entry) {
- return entry;
- }
- }, associatedMap);
- }
- }
-
- /**
- * Create an IdentityHashMap with default maximum size
- */
- public IdentityHashMap() {
- this(DEFAULT_MAX_SIZE);
- }
-
- /**
- * Create an IdentityHashMap with the given maximum size parameter
- *
- * @param maxSize
- * The estimated maximum number of entries that will be put in
- * this map.
- */
- public IdentityHashMap(int maxSize) {
- if (maxSize >= 0) {
- this.size = 0;
- threshold = getThreshold(maxSize);
- elementData = newElementArray(computeElementArraySize());
- } else {
+ return new IdentityHashMapIterator<Map.Entry<KT, VT>, KT, VT>(
+ new MapEntry.Type<Map.Entry<KT, VT>, KT, VT>() {
+ public Map.Entry<KT, VT> get(MapEntry<KT, VT> entry) {
+ return entry;
+ }
+ }, associatedMap);
+ }
+ }
+
+ /**
+ * Create an IdentityHashMap with default maximum size
+ */
+ public IdentityHashMap() {
+ this(DEFAULT_MAX_SIZE);
+ }
+
+ /**
+ * Create an IdentityHashMap with the given maximum size parameter
+ *
+ * @param maxSize
+ * The estimated maximum number of entries that will be put in
+ * this map.
+ */
+ public IdentityHashMap(int maxSize) {
+ if (maxSize >= 0) {
+ this.size = 0;
+ threshold = getThreshold(maxSize);
+ elementData = newElementArray(computeElementArraySize());
+ } else {
throw new IllegalArgumentException();
}
- }
+ }
+
+ private int getThreshold(int maxSize) {
+ // assign the threshold to maxSize initially, this will change to a
+ // higher value if rehashing occurs.
+ return maxSize > 3 ? maxSize : 3;
+ }
+
+ private int computeElementArraySize() {
+ return (int) (((long) threshold * 10000) / loadFactor) * 2;
+ }
+
+ /**
+ * Create a new element array
+ *
+ * @param s
+ * the number of elements
+ * @return Reference to the element array
+ */
+ private Object[] newElementArray(int s) {
+ return new Object[s];
+ }
+
+ /**
+ * Create an IdentityHashMap using the given Map as initial values.
+ *
+ * @param map
+ * A map of (key,value) pairs to copy into the IdentityHashMap
+ */
+ public IdentityHashMap(Map<? extends K, ? extends V> map) {
+ this(map.size() < 6 ? 11 : map.size() * 2);
+ putAll(map);
+ }
- private int getThreshold(int maxSize) {
- // assign the threshold to maxSize initially, this will change to a
- // higher value if rehashing occurs.
- return maxSize > 3 ? maxSize : 3;
- }
-
- private int computeElementArraySize() {
- return (int) (((long) threshold * 10000) / loadFactor) * 2;
- }
-
- /**
- * Create a new element array
- *
- * @param s
- * the number of elements
- * @return Reference to the element array
- */
- private Object[] newElementArray(int s) {
- return new Object[s];
- }
-
- /**
- * Create an IdentityHashMap using the given Map as initial values.
- *
- * @param map
- * A map of (key,value) pairs to copy into the IdentityHashMap
- */
- public IdentityHashMap(Map<? extends K, ? extends V> map) {
- this(map.size() < 6 ? 11 : map.size() * 2);
- putAll(map);
- }
-
@SuppressWarnings("unchecked")
private V massageValue(Object value) {
- return (V)((value == NULL_OBJECT) ? null : value);
+ return (V) ((value == NULL_OBJECT) ? null : value);
}
- /**
- * Removes all elements from this Map, leaving it empty.
- *
- * @exception UnsupportedOperationException
- * when removing from this Map is not supported
- *
- * @see #isEmpty
- * @see #size
- */
- @Override
+ /**
+ * Removes all elements from this Map, leaving it empty.
+ *
+ * @exception UnsupportedOperationException
+ * when removing from this Map is not supported
+ *
+ * @see #isEmpty
+ * @see #size
+ */
+ @Override
public void clear() {
- size = 0;
- for (int i = 0; i < elementData.length; i++) {
- elementData[i] = null;
- }
- modCount ++;
- }
-
- /**
- * Searches this Map for the specified key.
- *
- * @param key
- * the object to search for
- * @return true if <code>key</code> is a key of this Map, false otherwise
- */
- @Override
+ size = 0;
+ for (int i = 0; i < elementData.length; i++) {
+ elementData[i] = null;
+ }
+ modCount++;
+ }
+
+ /**
+ * Searches this Map for the specified key.
+ *
+ * @param key
+ * the object to search for
+ * @return true if <code>key</code> is a key of this Map, false otherwise
+ */
+ @Override
public boolean containsKey(Object key) {
- if (key == null) {
- key = NULL_OBJECT;
- }
-
- int index = findIndex(key, elementData);
- return elementData[index] == key;
- }
-
- /**
- * Searches this Map for the specified value.
- *
- *
- * @param value
- * the object to search for
- * @return true if <code>value</code> is a value of this Map, false
- * otherwise
- */
- @Override
+ if (key == null) {
+ key = NULL_OBJECT;
+ }
+
+ int index = findIndex(key, elementData);
+ return elementData[index] == key;
+ }
+
+ /**
+ * Searches this Map for the specified value.
+ *
+ *
+ * @param value
+ * the object to search for
+ * @return true if <code>value</code> is a value of this Map, false
+ * otherwise
+ */
+ @Override
public boolean containsValue(Object value) {
- if (value == null) {
- value = NULL_OBJECT;
- }
-
- for (int i = 1; i < elementData.length; i = i + 2) {
- if (elementData[i] == value) {
- return true;
- }
- }
- return false;
- }
-
- /**
- * Answers the value of the mapping with the specified key.
- *
- * @param key
- * the key
- * @return the value of the mapping with the specified key
- */
+ if (value == null) {
+ value = NULL_OBJECT;
+ }
+
+ for (int i = 1; i < elementData.length; i = i + 2) {
+ if (elementData[i] == value) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Answers the value of the mapping with the specified key.
+ *
+ * @param key
+ * the key
+ * @return the value of the mapping with the specified key
+ */
@Override
public V get(Object key) {
- if (key == null) {
- key = NULL_OBJECT;
- }
-
- int index = findIndex(key, elementData);
-
- if (elementData[index] == key) {
- Object result = elementData[index + 1];
- return massageValue(result);
- }
-
- return null;
- }
-
- private IdentityHashMapEntry<K, V> getEntry(Object key) {
- if (key == null) {
- key = NULL_OBJECT;
- }
-
- int index = findIndex(key, elementData);
- if (elementData[index] == key) {
- return getEntry(index);
- }
-
- return null;
- }
-
- /**
- * Convenience method for getting the IdentityHashMapEntry without the
- * NULL_OBJECT elements
- */
- @SuppressWarnings("unchecked")
+ if (key == null) {
+ key = NULL_OBJECT;
+ }
+
+ int index = findIndex(key, elementData);
+
+ if (elementData[index] == key) {
+ Object result = elementData[index + 1];
+ return massageValue(result);
+ }
+
+ return null;
+ }
+
+ private IdentityHashMapEntry<K, V> getEntry(Object key) {
+ if (key == null) {
+ key = NULL_OBJECT;
+ }
+
+ int index = findIndex(key, elementData);
+ if (elementData[index] == key) {
+ return getEntry(index);
+ }
+
+ return null;
+ }
+
+ /**
+ * Convenience method for getting the IdentityHashMapEntry without the
+ * NULL_OBJECT elements
+ */
+ @SuppressWarnings("unchecked")
private IdentityHashMapEntry<K, V> getEntry(int index) {
- Object key = elementData[index];
- Object value = elementData[index + 1];
+ Object key = elementData[index];
+ Object value = elementData[index + 1];
+
+ if (key == NULL_OBJECT) {
+ key = null;
+ }
+ if (value == NULL_OBJECT) {
+ value = null;
+ }
- if (key == NULL_OBJECT) {
- key = null;
- }
- if (value == NULL_OBJECT) {
- value = null;
- }
-
- return new IdentityHashMapEntry<K, V>((K)key, (V)value);
- }
-
- /**
- * Returns the index where the key is found at, or the index of the next
- * empty spot if the key is not found in this table.
- */
- private int findIndex(Object key, Object[] array) {
- int length = array.length;
- int index = getModuloHash(key, length);
- int last = (index + length - 2) % length;
- while (index != last) {
- if (array[index] == key || (array[index] == null)) {
- /*
- * Found the key, or the next empty spot (which means key is not
- * in the table)
- */
- break;
- }
- index = (index + 2) % length;
- }
- return index;
- }
-
- private int getModuloHash(Object key, int length) {
- return ((System.identityHashCode(key) & 0x7FFFFFFF) % (length / 2)) * 2;
- }
-
- /**
- * Maps the specified key to the specified value.
- *
- * @param key
- * the key
- * @param value
- * the value
- * @return the value of any previous mapping with the specified key or null
- * if there was no mapping
- */
+ return new IdentityHashMapEntry<K, V>((K) key, (V) value);
+ }
+
+ /**
+ * Returns the index where the key is found at, or the index of the next
+ * empty spot if the key is not found in this table.
+ */
+ private int findIndex(Object key, Object[] array) {
+ int length = array.length;
+ int index = getModuloHash(key, length);
+ int last = (index + length - 2) % length;
+ while (index != last) {
+ if (array[index] == key || (array[index] == null)) {
+ /*
+ * Found the key, or the next empty spot (which means key is not
+ * in the table)
+ */
+ break;
+ }
+ index = (index + 2) % length;
+ }
+ return index;
+ }
+
+ private int getModuloHash(Object key, int length) {
+ return ((System.identityHashCode(key) & 0x7FFFFFFF) % (length / 2)) * 2;
+ }
+
+ /**
+ * Maps the specified key to the specified value.
+ *
+ * @param key
+ * the key
+ * @param value
+ * the value
+ * @return the value of any previous mapping with the specified key or null
+ * if there was no mapping
+ */
@Override
public V put(K key, V value) {
Object _key = key;
Object _value = value;
- if (_key == null) {
- _key = NULL_OBJECT;
- }
-
- if (_value == null) {
- _value = NULL_OBJECT;
- }
-
- int index = findIndex(_key, elementData);
-
- // if the key doesn't exist in the table
- if (elementData[index] != _key) {
- modCount++;
- if (++size > threshold) {
- rehash();
- index = findIndex(_key, elementData);
- }
-
- // insert the key and assign the value to null initially
- elementData[index] = _key;
- elementData[index + 1] = null;
- }
-
- // insert value to where it needs to go, return the old value
- Object result = elementData[index + 1];
- elementData[index + 1] = _value;
-
- return massageValue(result);
- }
-
- private void rehash() {
- int newlength = elementData.length << 1;
- if (newlength == 0) {
+ if (_key == null) {
+ _key = NULL_OBJECT;
+ }
+
+ if (_value == null) {
+ _value = NULL_OBJECT;
+ }
+
+ int index = findIndex(_key, elementData);
+
+ // if the key doesn't exist in the table
+ if (elementData[index] != _key) {
+ modCount++;
+ if (++size > threshold) {
+ rehash();
+ index = findIndex(_key, elementData);
+ }
+
+ // insert the key and assign the value to null initially
+ elementData[index] = _key;
+ elementData[index + 1] = null;
+ }
+
+ // insert value to where it needs to go, return the old value
+ Object result = elementData[index + 1];
+ elementData[index + 1] = _value;
+
+ return massageValue(result);
+ }
+
+ private void rehash() {
+ int newlength = elementData.length << 1;
+ if (newlength == 0) {
newlength = 1;
}
- Object[] newData = newElementArray(newlength);
- for (int i = 0; i < elementData.length; i = i + 2) {
- Object key = elementData[i];
- if (key != null) {
- // if not empty
- int index = findIndex(key, newData);
- newData[index] = key;
- newData[index + 1] = elementData[i + 1];
- }
- }
- elementData = newData;
- computeMaxSize();
- }
-
- private void computeMaxSize() {
- threshold = (int) ((long) (elementData.length / 2) * loadFactor / 10000);
- }
-
- /**
- * Removes a mapping with the specified key from this IdentityHashMap.
- *
- * @param key
- * the key of the mapping to remove
- * @return the value of the removed mapping, or null if key is not a key in
- * this Map
- */
- @Override
+ Object[] newData = newElementArray(newlength);
+ for (int i = 0; i < elementData.length; i = i + 2) {
+ Object key = elementData[i];
+ if (key != null) {
+ // if not empty
+ int index = findIndex(key, newData);
+ newData[index] = key;
+ newData[index + 1] = elementData[i + 1];
+ }
+ }
+ elementData = newData;
+ computeMaxSize();
+ }
+
+ private void computeMaxSize() {
+ threshold = (int) ((long) (elementData.length / 2) * loadFactor / 10000);
+ }
+
+ /**
+ * Removes a mapping with the specified key from this IdentityHashMap.
+ *
+ * @param key
+ * the key of the mapping to remove
+ * @return the value of the removed mapping, or null if key is not a key in
+ * this Map
+ */
+ @Override
public V remove(Object key) {
- if (key == null) {
- key = NULL_OBJECT;
- }
-
- boolean hashedOk;
- int index, next, hash;
- Object result, object;
- index = next = findIndex(key, elementData);
+ if (key == null) {
+ key = NULL_OBJECT;
+ }
+
+ boolean hashedOk;
+ int index, next, hash;
+ Object result, object;
+ index = next = findIndex(key, elementData);
- if (elementData[index] != key) {
+ if (elementData[index] != key) {
return null;
}
- // store the value for this key
- result = elementData[index + 1];
+ // store the value for this key
+ result = elementData[index + 1];
- // shift the following elements up if needed
- // until we reach an empty spot
- int length = elementData.length;
- while (true) {
- next = (next + 2) % length;
- object = elementData[next];
- if (object == null) {
+ // shift the following elements up if needed
+ // until we reach an empty spot
+ int length = elementData.length;
+ while (true) {
+ next = (next + 2) % length;
+ object = elementData[next];
+ if (object == null) {
break;
}
- hash = getModuloHash(object, length);
- hashedOk = hash > index;
- if (next < index) {
- hashedOk = hashedOk || (hash <= next);
- } else {
- hashedOk = hashedOk && (hash <= next);
- }
- if (!hashedOk) {
- elementData[index] = object;
- elementData[index + 1] = elementData[next + 1];
- index = next;
- }
- }
-
- size--;
- modCount++;
-
- // clear both the key and the value
- elementData[index] = null;
- elementData[index + 1] = null;
-
- return massageValue(result);
- }
-
- /**
- * Answers a Set of the mappings contained in this IdentityHashMap. Each
- * element in the set is a Map.Entry. The set is backed by this Map so
- * changes to one are reflected by the other. The set does not support
- * adding.
- *
- * @return a Set of the mappings
- */
- @Override
+ hash = getModuloHash(object, length);
+ hashedOk = hash > index;
+ if (next < index) {
+ hashedOk = hashedOk || (hash <= next);
+ } else {
+ hashedOk = hashedOk && (hash <= next);
+ }
+ if (!hashedOk) {
+ elementData[index] = object;
+ elementData[index + 1] = elementData[next + 1];
+ index = next;
+ }
+ }
+
+ size--;
+ modCount++;
+
+ // clear both the key and the value
+ elementData[index] = null;
+ elementData[index + 1] = null;
+
+ return massageValue(result);
+ }
+
+ /**
+ * Answers a Set of the mappings contained in this IdentityHashMap. Each
+ * element in the set is a Map.Entry. The set is backed by this Map so
+ * changes to one are reflected by the other. The set does not support
+ * adding.
+ *
+ * @return a Set of the mappings
+ */
+ @Override
public Set<Map.Entry<K, V>> entrySet() {
- return new IdentityHashMapEntrySet<K, V>(this);
- }
+ return new IdentityHashMapEntrySet<K, V>(this);
+ }
- /**
- * Answers a Set of the keys contained in this IdentityHashMap. The set is
- * backed by this IdentityHashMap so changes to one are reflected by the
- * other. The set does not support adding.
- *
- * @return a Set of the keys
- */
- @Override
+ /**
+ * Answers a Set of the keys contained in this IdentityHashMap. The set is
+ * backed by this IdentityHashMap so changes to one are reflected by the
+ * other. The set does not support adding.
+ *
+ * @return a Set of the keys
+ */
+ @Override
public Set<K> keySet() {
- if (keySet == null) {
- keySet = new AbstractSet<K>() {
- @Override
+ if (keySet == null) {
+ keySet = new AbstractSet<K>() {
+ @Override
public boolean contains(Object object) {
- return containsKey(object);
- }
+ return containsKey(object);
+ }
- @Override
+ @Override
public int size() {
- return IdentityHashMap.this.size();
- }
+ return IdentityHashMap.this.size();
+ }
- @Override
+ @Override
public void clear() {
- IdentityHashMap.this.clear();
- }
+ IdentityHashMap.this.clear();
+ }
- @Override
+ @Override
public boolean remove(Object key) {
- if (containsKey(key)) {
- IdentityHashMap.this.remove(key);
- return true;
- }
- return false;
- }
+ if (containsKey(key)) {
+ IdentityHashMap.this.remove(key);
+ return true;
+ }
+ return false;
+ }
- @Override
+ @Override
public Iterator<K> iterator() {
- return new IdentityHashMapIterator<K,K,V>(new MapEntry.Type<K,K,V>() {
- public K get(MapEntry<K,V> entry) {
- return entry.key;
- }
- }, IdentityHashMap.this);
- }
- };
- }
- return keySet;
- }
-
- /**
- * Answers a Collection of the values contained in this IdentityHashMap. The
- * collection is backed by this IdentityHashMap so changes to one are
- * reflected by the other. The collection does not support adding.
- *
- * @return a Collection of the values
- */
- @Override
+ return new IdentityHashMapIterator<K, K, V>(
+ new MapEntry.Type<K, K, V>() {
+ public K get(MapEntry<K, V> entry) {
+ return entry.key;
+ }
+ }, IdentityHashMap.this);
+ }
+ };
+ }
+ return keySet;
+ }
+
+ /**
+ * Answers a Collection of the values contained in this IdentityHashMap. The
+ * collection is backed by this IdentityHashMap so changes to one are
+ * reflected by the other. The collection does not support adding.
+ *
+ * @return a Collection of the values
+ */
+ @Override
public Collection<V> values() {
- if (valuesCollection == null) {
- valuesCollection = new AbstractCollection<V>() {
- @Override
+ if (valuesCollection == null) {
+ valuesCollection = new AbstractCollection<V>() {
+ @Override
public boolean contains(Object object) {
- return containsValue(object);
- }
+ return containsValue(object);
+ }
- @Override
+ @Override
public int size() {
- return IdentityHashMap.this.size();
- }
+ return IdentityHashMap.this.size();
+ }
- @Override
+ @Override
public void clear() {
- IdentityHashMap.this.clear();
- }
+ IdentityHashMap.this.clear();
+ }
- @Override
+ @Override
public Iterator<V> iterator() {
- return new IdentityHashMapIterator<V,K,V>(new MapEntry.Type<V,K,V>() {
- public V get(MapEntry<K,V> entry) {
- return entry.value;
- }
- }, IdentityHashMap.this);
- }
-
- @Override
+ return new IdentityHashMapIterator<V, K, V>(
+ new MapEntry.Type<V, K, V>() {
+ public V get(MapEntry<K, V> entry) {
+ return entry.value;
+ }
+ }, IdentityHashMap.this);
+ }
+
+ @Override
public boolean remove(Object object) {
- Iterator<?> it = iterator();
- while (it.hasNext()) {
- if (object == it.next()) {
- it.remove();
- return true;
- }
- }
- return false;
- }
- };
- }
- return valuesCollection;
- }
-
- /**
- * Compares this map with other objects. This map is equal to another map is
- * it represents the same set of mappings. With this map, two mappings are
- * the same if both the key and the value are equal by reference.
- *
- * When compared with a map that is not an IdentityHashMap, the equals
- * method is not necessarily symmetric (a.equals(b) implies b.equals(a)) nor
- * transitive (a.equals(b) and b.equals(c) implies a.equals(c)).
- *
- * @return whether the argument object is equal to this object
- */
- @Override
+ Iterator<?> it = iterator();
+ while (it.hasNext()) {
+ if (object == it.next()) {
+ it.remove();
+ return true;
+ }
+ }
+ return false;
+ }
+ };
+ }
+ return valuesCollection;
+ }
+
+ /**
+ * Compares this map with other objects. This map is equal to another map is
+ * it represents the same set of mappings. With this map, two mappings are
+ * the same if both the key and the value are equal by reference.
+ *
+ * When compared with a map that is not an IdentityHashMap, the equals
+ * method is not necessarily symmetric (a.equals(b) implies b.equals(a)) nor
+ * transitive (a.equals(b) and b.equals(c) implies a.equals(c)).
+ *
+ * @return whether the argument object is equal to this object
+ */
+ @Override
public boolean equals(Object object) {
- // we need to override the equals method in AbstractMap because
- // AbstractMap.equals will call ((Map) object).entrySet().contains() to
- // determine equality of the entries, so it will defer to the argument
- // for comparison, meaning that reference-based comparison will not take
- // place. We must ensure that all comparison is implemented by methods
- // in this class (or in one of our inner classes) for reference-based
- // comparison to take place.
- if (this == object) {
+ /*
+ * We need to override the equals method in AbstractMap because
+ * AbstractMap.equals will call ((Map) object).entrySet().contains() to
+ * determine equality of the entries, so it will defer to the argument
+ * for comparison, meaning that reference-based comparison will not take
+ * place. We must ensure that all comparison is implemented by methods
+ * in this class (or in one of our inner classes) for reference-based
+ * comparison to take place.
+ */
+ if (this == object) {
return true;
}
- if (object instanceof Map) {
- Map<?, ?> map = (Map) object;
- if (size() != map.size()) {
+ if (object instanceof Map) {
+ Map<?, ?> map = (Map) object;
+ if (size() != map.size()) {
return false;
}
- Set<Map.Entry<K, V>> set = entrySet();
- // ensure we use the equals method of the set created by "this"
- return set.equals(map.entrySet());
- }
- return false;
- }
-
- /**
- * Answers a new IdentityHashMap with the same mappings and size as this
- * one.
- *
- * @return a shallow copy of this IdentityHashMap
- *
- * @see java.lang.Cloneable
- */
- @Override
+ Set<Map.Entry<K, V>> set = entrySet();
+ // ensure we use the equals method of the set created by "this"
+ return set.equals(map.entrySet());
+ }
+ return false;
+ }
+
+ /**
+ * Answers a new IdentityHashMap with the same mappings and size as this
+ * one.
+ *
+ * @return a shallow copy of this IdentityHashMap
+ *
+ * @see java.lang.Cloneable
+ */
+ @Override
public Object clone() {
- try {
- return super.clone();
- } catch (CloneNotSupportedException e) {
- return null;
- }
- }
-
- /**
- * Answers if this IdentityHashMap has no elements, a size of zero.
- *
- * @return true if this IdentityHashMap has no elements, false otherwise
- *
- * @see #size
- */
- @Override
+ try {
+ return super.clone();
+ } catch (CloneNotSupportedException e) {
+ return null;
+ }
+ }
+
+ /**
+ * Answers if this IdentityHashMap has no elements, a size of zero.
+ *
+ * @return true if this IdentityHashMap has no elements, false otherwise
+ *
+ * @see #size
+ */
+ @Override
public boolean isEmpty() {
- return size == 0;
- }
+ return size == 0;
+ }
- /**
- * Answers the number of mappings in this IdentityHashMap.
- *
- * @return the number of mappings in this IdentityHashMap
- */
- @Override
+ /**
+ * Answers the number of mappings in this IdentityHashMap.
+ *
+ * @return the number of mappings in this IdentityHashMap
+ */
+ @Override
public int size() {
- return size;
- }
+ return size;
+ }
- private void writeObject(ObjectOutputStream stream) throws IOException {
+ private void writeObject(ObjectOutputStream stream) throws IOException {
stream.defaultWriteObject();
- stream.writeInt(size);
- Iterator<?> iterator = entrySet().iterator();
- while (iterator.hasNext()) {
- MapEntry<?, ?> entry = (MapEntry) iterator.next();
- stream.writeObject(entry.key);
- stream.writeObject(entry.value);
- }
- }
+ stream.writeInt(size);
+ Iterator<?> iterator = entrySet().iterator();
+ while (iterator.hasNext()) {
+ MapEntry<?, ?> entry = (MapEntry) iterator.next();
+ stream.writeObject(entry.key);
+ stream.writeObject(entry.value);
+ }
+ }
- @SuppressWarnings("unchecked")
+ @SuppressWarnings("unchecked")
private void readObject(ObjectInputStream stream) throws IOException,
- ClassNotFoundException {
+ ClassNotFoundException {
stream.defaultReadObject();
- int savedSize = stream.readInt();
- threshold = getThreshold(DEFAULT_MAX_SIZE);
- elementData = newElementArray(computeElementArraySize());
- for (int i = savedSize; --i >= 0;) {
- K key = (K)stream.readObject();
- put(key, (V)stream.readObject());
- }
+ int savedSize = stream.readInt();
+ threshold = getThreshold(DEFAULT_MAX_SIZE);
+ elementData = newElementArray(computeElementArraySize());
+ for (int i = savedSize; --i >= 0;) {
+ K key = (K) stream.readObject();
+ put(key, (V) stream.readObject());
+ }
size = savedSize;
- }
+ }
}