0001: /*
0002: * @(#)IdentityHashMap.java 1.12 03/01/23
0003: *
0004: * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
0005: * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
0006: */
0007:
0008: package clime.messadmin.utils;
0009:
0010: import java.util.AbstractCollection;
0011: import java.util.AbstractMap;
0012: import java.util.AbstractSet;
0013: import java.util.ArrayList;
0014: import java.util.Collection;
0015: import java.util.ConcurrentModificationException;
0016: import java.util.Iterator;
0017: import java.util.Map;
0018: import java.util.NoSuchElementException;
0019: import java.util.Set;
0020:
0021: /**
0022: * XXX NOTE: this class copied and slightly adapted from JDK 1.4.2_09
0023: *
0024: * This class implements the <tt>Map</tt> interface with a hash table, using
0025: * reference-equality in place of object-equality when comparing keys (and
0026: * values). In other words, in an <tt>IdentityHashMap</tt>, two keys
0027: * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
0028: * <tt>(k1==k2)</tt>. (In normal <tt>Map</tt> implementations (like
0029: * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
0030: * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
0031: *
0032: * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
0033: * implementation! While this class implements the <tt>Map</tt> interface, it
0034: * intentionally violates <tt>Map's</tt> general contract, which mandates the
0035: * use of the <tt>equals</tt> method when comparing objects. This class is
0036: * designed for use only in the rare cases wherein reference-equality
0037: * semantics are required.</b>
0038: *
0039: * <p>A typical use of this class is <i>topology-preserving object graph
0040: * transformations</i>, such as serialization or deep-copying. To perform such
0041: * a transformation, a program must maintain a "node table" that keeps track
0042: * of all the object references that have already been processed. The node
0043: * table must not equate distinct objects even if they happen to be equal.
0044: * Another typical use of this class is to maintain <i>proxy objects</i>. For
0045: * example, a debugging facility might wish to maintain a proxy object for
0046: * each object in the program being debugged.
0047: *
0048: * <p>This class provides all of the optional map operations, and permits
0049: * <tt>null</tt> values and the <tt>null</tt> key. This class makes no
0050: * guarantees as to the order of the map; in particular, it does not guarantee
0051: * that the order will remain constant over time.
0052: *
0053: * <p>This class provides constant-time performance for the basic
0054: * operations (<tt>get</tt> and <tt>put</tt>), assuming the system
0055: * identity hash function ({@link System#identityHashCode(Object)})
0056: * disperses elements properly among the buckets.
0057: *
0058: * <p>This class has one tuning parameter (which affects performance but not
0059: * semantics): <i>expected maximum size</i>. This parameter is the maximum
0060: * number of key-value mappings that the map is expected to hold. Internally,
0061: * this parameter is used to determine the number of buckets initially
0062: * comprising the hash table. The precise relationship between the expected
0063: * maximum size and the number of buckets is unspecified.
0064: *
0065: * <p>If the size of the map (the number of key-value mappings) sufficiently
0066: * exceeds the expected maximum size, the number of buckets is increased
0067: * Increasing the number of buckets ("rehashing") may be fairly expensive, so
0068: * it pays to create identity hash maps with a sufficiently large expected
0069: * maximum size. On the other hand, iteration over collection views requires
0070: * time proportional to the the number of buckets in the hash table, so it
0071: * pays not to set the expected maximum size too high if you are especially
0072: * concerned with iteration performance or memory usage.
0073: *
0074: * <p><b>Note that this implementation is not synchronized.</b> If multiple
0075: * threads access this map concurrently, and at least one of the threads
0076: * modifies the map structurally, it <i>must</i> be synchronized externally.
0077: * (A structural modification is any operation that adds or deletes one or
0078: * more mappings; merely changing the value associated with a key that an
0079: * instance already contains is not a structural modification.) This is
0080: * typically accomplished by synchronizing on some object that naturally
0081: * encapsulates the map. If no such object exists, the map should be
0082: * "wrapped" using the <tt>Collections.synchronizedMap</tt> method. This is
0083: * best done at creation time, to prevent accidental unsynchronized access to
0084: * the map: <pre>
0085: * Map m = Collections.synchronizedMap(new HashMap(...));
0086: * </pre>
0087: *
0088: * <p>The iterators returned by all of this class's "collection view methods"
0089: * are <i>fail-fast</i>: if the map is structurally modified at any time after
0090: * the iterator is created, in any way except through the iterator's own
0091: * <tt>remove</tt> or <tt>add</tt> methods, the iterator will throw a
0092: * <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
0093: * modification, the iterator fails quickly and cleanly, rather than risking
0094: * arbitrary, non-deterministic behavior at an undetermined time in the
0095: * future.
0096: *
0097: * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
0098: * as it is, generally speaking, impossible to make any hard guarantees in the
0099: * presence of unsynchronized concurrent modification. Fail-fast iterators
0100: * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
0101: * Therefore, it would be wrong to write a program that depended on this
0102: * exception for its correctness: <i>fail-fast iterators should be used only
0103: * to detect bugs.</i>
0104: *
0105: * <p>Implementation note: This is a simple <i>linear-probe</i> hash table,
0106: * as described for example in texts by Sedgewick and Knuth. The array
0107: * alternates holding keys and values. (This has better locality for large
0108: * tables than does using separate arrays.) For many JRE implementations
0109: * and operation mixes, this class will yield better performance than
0110: * {@link java.util.HashMap} (which uses <i>chaining</i> rather than linear-probing).
0111: *
0112: * <p>This class is a member of the
0113: * <a href="{@docRoot}/../guide/collections/index.html">
0114: * Java Collections Framework</a>.
0115: *
0116: * @see System#identityHashCode(Object)
0117: * @see Object#hashCode()
0118: * @see java.util.Collection
0119: * @see java.util.Map
0120: * @see java.util.HashMap
0121: * @see java.util.TreeMap
0122: * @author Doug Lea and Josh Bloch
0123: * @since 1.4
0124: */
0125:
0126: public final class IdentityHashMap extends AbstractMap implements Map,
0127: java.io.Serializable, Cloneable {
0128: /**
0129: * The initial capacity used by the no-args constructor.
0130: * MUST be a power of two. The value 32 corresponds to the
0131: * (specified) expected maximum size of 21, given a load factor
0132: * of 2/3.
0133: */
0134: private static final int DEFAULT_CAPACITY = 32;
0135:
0136: /**
0137: * The minimum capacity, used if a lower value is implicitly specified
0138: * by either of the constructors with arguments. The value 4 corresponds
0139: * to an expected maximum size of 2, given a load factor of 2/3.
0140: * MUST be a power of two.
0141: */
0142: private static final int MINIMUM_CAPACITY = 4;
0143:
0144: /**
0145: * The maximum capacity, used if a higher value is implicitly specified
0146: * by either of the constructors with arguments.
0147: * MUST be a power of two <= 1<<29.
0148: */
0149: private static final int MAXIMUM_CAPACITY = 1 << 29;
0150:
0151: /**
0152: * The table, resized as necessary. Length MUST always be a power of two.
0153: */
0154: protected transient Object[] table;
0155:
0156: /**
0157: * The number of key-value mappings contained in this identity hash map.
0158: *
0159: * @serial
0160: */
0161: protected int size;
0162:
0163: /**
0164: * The number of modifications, to support fast-fail iterators
0165: */
0166: protected transient volatile int modCount;
0167:
0168: /**
0169: * The next size value at which to resize (capacity * load factor).
0170: */
0171: private transient int threshold;
0172:
0173: /**
0174: * Value representing null keys inside tables.
0175: */
0176: private static final Object NULL_KEY = new Object();
0177:
0178: /**
0179: * Use NULL_KEY for key if it is null.
0180: */
0181:
0182: private static Object maskNull(Object key) {
0183: return (key == null ? NULL_KEY : key);
0184: }
0185:
0186: /**
0187: * Return internal representation of null key back to caller as null
0188: */
0189: protected static Object unmaskNull(Object key) {
0190: return (key == NULL_KEY ? null : key);
0191: }
0192:
0193: /**
0194: * Constructs a new, empty identity hash map with a default expected
0195: * maximum size (21).
0196: */
0197: public IdentityHashMap() {
0198: init(DEFAULT_CAPACITY);
0199: }
0200:
0201: /**
0202: * Constructs a new, empty map with the specified expected maximum size.
0203: * Putting more than the expected number of key-value mappings into
0204: * the map may cause the internal data structure to grow, which may be
0205: * somewhat time-consuming.
0206: *
0207: * @param expectedMaxSize the expected maximum size of the map.
0208: * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
0209: */
0210: public IdentityHashMap(int expectedMaxSize) {
0211: if (expectedMaxSize < 0)
0212: throw new IllegalArgumentException(
0213: "expectedMaxSize is negative: "//$NON-NLS-1$
0214: + expectedMaxSize);
0215: init(capacity(expectedMaxSize));
0216: }
0217:
0218: /**
0219: * Returns the appropriate capacity for the specified expected maximum
0220: * size. Returns the smallest power of two between MINIMUM_CAPACITY
0221: * and MAXIMUM_CAPACITY, inclusive, that is greater than
0222: * (3 * expectedMaxSize)/2, if such a number exists. Otherwise
0223: * returns MAXIMUM_CAPACITY. If (3 * expectedMaxSize)/2 is negative, it
0224: * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
0225: */
0226: private int capacity(int expectedMaxSize) {
0227: // Compute min capacity for expectedMaxSize given a load factor of 2/3
0228: int minCapacity = (3 * expectedMaxSize) / 2;
0229:
0230: // Compute the appropriate capacity
0231: int result;
0232: if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
0233: result = MAXIMUM_CAPACITY;
0234: } else {
0235: result = MINIMUM_CAPACITY;
0236: while (result < minCapacity)
0237: result <<= 1;
0238: }
0239: return result;
0240: }
0241:
0242: /**
0243: * Initialize object to be an empty map with the specified initial
0244: * capacity, which is assumed to be a power of two between
0245: * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
0246: */
0247: private void init(int initCapacity) {
0248: // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
0249: // assert initCapacity >= MINIMUM_CAPACITY;
0250: // assert initCapacity <= MAXIMUM_CAPACITY;
0251:
0252: threshold = (initCapacity * 2) / 3;
0253: table = new Object[2 * initCapacity];
0254: }
0255:
0256: /**
0257: * Constructs a new identity hash map containing the keys-value mappings
0258: * in the specified map.
0259: *
0260: * @param m the map whose mappings are to be placed into this map.
0261: * @throws NullPointerException if the specified map is null.
0262: */
0263: public IdentityHashMap(Map m) {
0264: // Allow for a bit of growth
0265: this ((int) ((1 + m.size()) * 1.1));
0266: putAll(m);
0267: }
0268:
0269: /**
0270: * Returns the number of key-value mappings in this identity hash map.
0271: *
0272: * @return the number of key-value mappings in this map.
0273: */
0274: public int size() {
0275: return size;
0276: }
0277:
0278: /**
0279: * Returns <tt>true</tt> if this identity hash map contains no key-value
0280: * mappings.
0281: *
0282: * @return <tt>true</tt> if this identity hash map contains no key-value
0283: * mappings.
0284: */
0285: public boolean isEmpty() {
0286: return size == 0;
0287: }
0288:
0289: /**
0290: * Return index for Object x.
0291: */
0292: protected static int hash(Object x, int length) {
0293: int h = System.identityHashCode(x);
0294: // Multiply by -127, and left-shift to use least bit as part of hash
0295: return ((h << 1) - (h << 8)) & (length - 1);
0296: }
0297:
0298: /**
0299: * Circularly traverse table of size len.
0300: **/
0301: protected static int nextKeyIndex(int i, int len) {
0302: return (i + 2 < len ? i + 2 : 0);
0303: }
0304:
0305: /**
0306: * Returns the value to which the specified key is mapped in this identity
0307: * hash map, or <tt>null</tt> if the map contains no mapping for
0308: * this key. A return value of <tt>null</tt> does not <i>necessarily</i>
0309: * indicate that the map contains no mapping for the key; it is also
0310: * possible that the map explicitly maps the key to <tt>null</tt>. The
0311: * <tt>containsKey</tt> method may be used to distinguish these two
0312: * cases.
0313: *
0314: * @param key the key whose associated value is to be returned.
0315: * @return the value to which this map maps the specified key, or
0316: * <tt>null</tt> if the map contains no mapping for this key.
0317: * @see #put(Object, Object)
0318: */
0319: public Object get(Object key) {
0320: Object k = maskNull(key);
0321: Object[] tab = table;
0322: int len = tab.length;
0323: int i = hash(k, len);
0324: while (true) {
0325: Object item = tab[i];
0326: if (item == k)
0327: return tab[i + 1];
0328: if (item == null)
0329: return item;
0330: i = nextKeyIndex(i, len);
0331: }
0332: }
0333:
0334: /**
0335: * Tests whether the specified object reference is a key in this identity
0336: * hash map.
0337: *
0338: * @param key possible key.
0339: * @return <code>true</code> if the specified object reference is a key
0340: * in this map.
0341: * @see #containsValue(Object)
0342: */
0343: public boolean containsKey(Object key) {
0344: Object k = maskNull(key);
0345: Object[] tab = table;
0346: int len = tab.length;
0347: int i = hash(k, len);
0348: while (true) {
0349: Object item = tab[i];
0350: if (item == k)
0351: return true;
0352: if (item == null)
0353: return false;
0354: i = nextKeyIndex(i, len);
0355: }
0356: }
0357:
0358: /**
0359: * Tests whether the specified object reference is a value in this identity
0360: * hash map.
0361: *
0362: * @param value value whose presence in this map is to be tested.
0363: * @return <tt>true</tt> if this map maps one or more keys to the
0364: * specified object reference.
0365: * @see #containsKey(Object)
0366: */
0367: public boolean containsValue(Object value) {
0368: Object[] tab = table;
0369: for (int i = 1; i < tab.length; i += 2)
0370: if (tab[i] == value)
0371: return true;
0372:
0373: return false;
0374: }
0375:
0376: /**
0377: * Tests if the specified key-value mapping is in the map.
0378: *
0379: * @param key possible key.
0380: * @param value possible value.
0381: * @return <code>true</code> if and only if the specified key-value
0382: * mapping is in map.
0383: */
0384: protected boolean containsMapping(Object key, Object value) {
0385: Object k = maskNull(key);
0386: Object[] tab = table;
0387: int len = tab.length;
0388: int i = hash(k, len);
0389: while (true) {
0390: Object item = tab[i];
0391: if (item == k)
0392: return tab[i + 1] == value;
0393: if (item == null)
0394: return false;
0395: i = nextKeyIndex(i, len);
0396: }
0397: }
0398:
0399: /**
0400: * Associates the specified value with the specified key in this identity
0401: * hash map. If the map previously contained a mapping for this key, the
0402: * old value is replaced.
0403: *
0404: * @param key the key with which the specified value is to be associated.
0405: * @param value the value to be associated with the specified key.
0406: * @return the previous value associated with <tt>key</tt>, or
0407: * <tt>null</tt> if there was no mapping for <tt>key</tt>. (A
0408: * <tt>null</tt> return can also indicate that the map previously
0409: * associated <tt>null</tt> with the specified key.)
0410: * @see Object#equals(Object)
0411: * @see #get(Object)
0412: * @see #containsKey(Object)
0413: */
0414: public Object put(Object key, Object value) {
0415: Object k = maskNull(key);
0416: Object[] tab = table;
0417: int len = tab.length;
0418: int i = hash(k, len);
0419:
0420: Object item;
0421: while ((item = tab[i]) != null) {
0422: if (item == k) {
0423: Object oldValue = tab[i + 1];
0424: tab[i + 1] = value;
0425: return oldValue;
0426: }
0427: i = nextKeyIndex(i, len);
0428: }
0429:
0430: ++modCount;
0431: tab[i] = k;
0432: tab[i + 1] = value;
0433: if (++size >= threshold)
0434: resize(len); // len == 2 * current capacity.
0435: return null;
0436: }
0437:
0438: /**
0439: * Resize the table to hold given capacity.
0440: *
0441: * @param newCapacity the new capacity, must be a power of two.
0442: */
0443: private void resize(int newCapacity) {
0444: // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
0445: int newLength = newCapacity * 2;
0446:
0447: Object[] oldTable = table;
0448: int oldLength = oldTable.length;
0449: if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
0450: if (threshold == MAXIMUM_CAPACITY - 1)
0451: throw new IllegalStateException("Capacity exhausted.");//$NON-NLS-1$
0452: threshold = MAXIMUM_CAPACITY - 1; // Gigantic map!
0453: return;
0454: }
0455: if (oldLength >= newLength)
0456: return;
0457:
0458: Object[] newTable = new Object[newLength];
0459: threshold = newLength / 3;
0460:
0461: for (int j = 0; j < oldLength; j += 2) {
0462: Object key = oldTable[j];
0463: if (key != null) {
0464: Object value = oldTable[j + 1];
0465: oldTable[j] = null;
0466: oldTable[j + 1] = null;
0467: int i = hash(key, newLength);
0468: while (newTable[i] != null)
0469: i = nextKeyIndex(i, newLength);
0470: newTable[i] = key;
0471: newTable[i + 1] = value;
0472: }
0473: }
0474: table = newTable;
0475: }
0476:
0477: /**
0478: * Copies all of the mappings from the specified map to this map
0479: * These mappings will replace any mappings that
0480: * this map had for any of the keys currently in the specified map.<p>
0481: *
0482: * @param t mappings to be stored in this map.
0483: * @throws NullPointerException if the specified map is null.
0484: */
0485: public void putAll(Map t) {
0486: int n = t.size();
0487: if (n == 0)
0488: return;
0489: if (n > threshold) // conservatively pre-expand
0490: resize(capacity(n));
0491:
0492: for (Iterator it = t.entrySet().iterator(); it.hasNext();) {
0493: Entry e = (Entry) it.next();
0494: put(e.getKey(), e.getValue());
0495: }
0496: }
0497:
0498: /**
0499: * Removes the mapping for this key from this map if present.
0500: *
0501: * @param key key whose mapping is to be removed from the map.
0502: * @return previous value associated with specified key, or <tt>null</tt>
0503: * if there was no entry for key. (A <tt>null</tt> return can
0504: * also indicate that the map previously associated <tt>null</tt>
0505: * with the specified key.)
0506: */
0507: public Object remove(Object key) {
0508: Object k = maskNull(key);
0509: Object[] tab = table;
0510: int len = tab.length;
0511: int i = hash(k, len);
0512:
0513: while (true) {
0514: Object item = tab[i];
0515: if (item == k) {
0516: ++modCount;
0517: --size;
0518: Object oldValue = tab[i + 1];
0519: tab[i + 1] = null;
0520: tab[i] = null;
0521: closeDeletion(i);
0522: return oldValue;
0523: }
0524: if (item == null)
0525: return null;
0526: i = nextKeyIndex(i, len);
0527: }
0528:
0529: }
0530:
0531: /**
0532: * Removes the specified key-value mapping from the map if it is present.
0533: *
0534: * @param key possible key.
0535: * @param value possible value.
0536: * @return <code>true</code> if and only if the specified key-value
0537: * mapping was in map.
0538: */
0539: protected boolean removeMapping(Object key, Object value) {
0540: Object k = maskNull(key);
0541: Object[] tab = table;
0542: int len = tab.length;
0543: int i = hash(k, len);
0544:
0545: while (true) {
0546: Object item = tab[i];
0547: if (item == k) {
0548: if (tab[i + 1] != value)
0549: return false;
0550: ++modCount;
0551: --size;
0552: tab[i] = null;
0553: tab[i + 1] = null;
0554: closeDeletion(i);
0555: return true;
0556: }
0557: if (item == null)
0558: return false;
0559: i = nextKeyIndex(i, len);
0560: }
0561: }
0562:
0563: /**
0564: * Rehash all possibly-colliding entries following a
0565: * deletion. This preserves the linear-probe
0566: * collision properties required by get, put, etc.
0567: *
0568: * @param d the index of a newly empty deleted slot
0569: */
0570: private void closeDeletion(int d) {
0571: // Adapted from Knuth Section 6.4 Algorithm R
0572: Object[] tab = table;
0573: int len = tab.length;
0574:
0575: // Look for items to swap into newly vacated slot
0576: // starting at index immediately following deletion,
0577: // and continuing until a null slot is seen, indicating
0578: // the end of a run of possibly-colliding keys.
0579: Object item;
0580: for (int i = nextKeyIndex(d, len); (item = tab[i]) != null; i = nextKeyIndex(
0581: i, len)) {
0582: // The following test triggers if the item at slot i (which
0583: // hashes to be at slot r) should take the spot vacated by d.
0584: // If so, we swap it in, and then continue with d now at the
0585: // newly vacated i. This process will terminate when we hit
0586: // the null slot at the end of this run.
0587: // The test is messy because we are using a circular table.
0588: int r = hash(item, len);
0589: if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
0590: tab[d] = item;
0591: tab[d + 1] = tab[i + 1];
0592: tab[i] = null;
0593: tab[i + 1] = null;
0594: d = i;
0595: }
0596: }
0597: }
0598:
0599: /**
0600: * Removes all mappings from this map.
0601: */
0602: public void clear() {
0603: ++modCount;
0604: Object[] tab = table;
0605: for (int i = 0; i < tab.length; ++i)
0606: tab[i] = null;
0607: size = 0;
0608: }
0609:
0610: /**
0611: * Compares the specified object with this map for equality. Returns
0612: * <tt>true</tt> if the given object is also a map and the two maps
0613: * represent identical object-reference mappings. More formally, this
0614: * map is equal to another map <tt>m</tt> if and only if
0615: * map <tt>this.entrySet().equals(m.entrySet())</tt>.
0616: *
0617: * <p><b>Owing to the reference-equality-based semantics of this map it is
0618: * possible that the symmetry and transitivity requirements of the
0619: * <tt>Object.equals</tt> contract may be violated if this map is compared
0620: * to a normal map. However, the <tt>Object.equals</tt> contract is
0621: * guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>
0622: *
0623: * @param o object to be compared for equality with this map.
0624: * @return <tt>true</tt> if the specified object is equal to this map.
0625: * @see Object#equals(Object)
0626: */
0627: public boolean equals(Object o) {
0628: if (o == this ) {
0629: return true;
0630: } else if (o instanceof IdentityHashMap) {
0631: IdentityHashMap m = (IdentityHashMap) o;
0632: if (m.size() != size)
0633: return false;
0634:
0635: Object[] tab = m.table;
0636: for (int i = 0; i < tab.length; i += 2) {
0637: Object k = tab[i];
0638: if (k != null && !containsMapping(k, tab[i + 1]))
0639: return false;
0640: }
0641: return true;
0642: } else if (o instanceof Map) {
0643: Map m = (Map) o;
0644: return entrySet().equals(m.entrySet());
0645: } else {
0646: return false; // o is not a Map
0647: }
0648: }
0649:
0650: /**
0651: * Returns the hash code value for this map. The hash code of a map
0652: * is defined to be the sum of the hashcode of each entry in the map's
0653: * entrySet view. This ensures that <tt>t1.equals(t2)</tt> implies
0654: * that <tt>t1.hashCode()==t2.hashCode()</tt> for any two
0655: * <tt>IdentityHashMap</tt> instances <tt>t1</tt> and <tt>t2</tt>, as
0656: * required by the general contract of {@link Object#hashCode()}.
0657: *
0658: * <p><b>Owing to the reference-equality-based semantics of the
0659: * <tt>Map.Entry</tt> instances in the set returned by this map's
0660: * <tt>entrySet</tt> method, it is possible that the contractual
0661: * requirement of <tt>Object.hashCode</tt> mentioned in the previous
0662: * paragraph will be violated if one of the two objects being compared is
0663: * an <tt>IdentityHashMap</tt> instance and the other is a normal map.</b>
0664: *
0665: * @return the hash code value for this map.
0666: * @see Object#hashCode()
0667: * @see Object#equals(Object)
0668: * @see #equals(Object)
0669: */
0670: public int hashCode() {
0671: int result = 0;
0672: Object[] tab = table;
0673: for (int i = 0; i < tab.length; i += 2) {
0674: Object key = tab[i];
0675: if (key != null) {
0676: Object k = unmaskNull(key);
0677: result += System.identityHashCode(k)
0678: ^ System.identityHashCode(tab[i + 1]);
0679: }
0680: }
0681: return result;
0682: }
0683:
0684: /**
0685: * Returns a shallow copy of this identity hash map: the keys and values
0686: * themselves are not cloned.
0687: *
0688: * @return a shallow copy of this map.
0689: */
0690: public Object clone() {
0691: try {
0692: IdentityHashMap t = (IdentityHashMap) super .clone();
0693: t.entrySet = null;
0694: t.table = (Object[]) (table.clone());
0695: return t;
0696: } catch (CloneNotSupportedException e) {
0697: throw new InternalError();
0698: }
0699: }
0700:
0701: private abstract class IdentityHashMapIterator implements Iterator {
0702: int index = (size != 0 ? 0 : table.length); // current slot.
0703: int expectedModCount = modCount; // to support fast-fail
0704: int lastReturnedIndex = -1; // to allow remove()
0705: boolean indexValid; // To avoid unecessary next computation
0706: Object[] traversalTable = table; // reference to main table or copy
0707:
0708: public boolean hasNext() {
0709: Object[] tab = traversalTable;
0710: for (int i = index; i < tab.length; i += 2) {
0711: Object key = tab[i];
0712: if (key != null) {
0713: index = i;
0714: return indexValid = true;
0715: }
0716: }
0717: index = tab.length;
0718: return false;
0719: }
0720:
0721: protected int nextIndex() {
0722: if (modCount != expectedModCount)
0723: throw new ConcurrentModificationException();
0724: if (!indexValid && !hasNext())
0725: throw new NoSuchElementException();
0726:
0727: indexValid = false;
0728: lastReturnedIndex = index;
0729: index += 2;
0730: return lastReturnedIndex;
0731: }
0732:
0733: public void remove() {
0734: if (lastReturnedIndex == -1)
0735: throw new IllegalStateException();
0736: if (modCount != expectedModCount)
0737: throw new ConcurrentModificationException();
0738:
0739: expectedModCount = ++modCount;
0740: int deletedSlot = lastReturnedIndex;
0741: lastReturnedIndex = -1;
0742: --size;
0743: // back up index to revisit new contents after deletion
0744: index = deletedSlot;
0745: indexValid = false;
0746:
0747: // Removal code proceeds as in closeDeletion except that
0748: // it must catch the rare case where an element already
0749: // seen is swapped into a vacant slot that will be later
0750: // traversed by this iterator. We cannot allow future
0751: // next() calls to return it again. The likelihood of
0752: // this occurring under 2/3 load factor is very slim, but
0753: // when it does happen, we must make a copy of the rest of
0754: // the table to use for the rest of the traversal. Since
0755: // this can only happen when we are near the end of the table,
0756: // even in these rare cases, this is not very expensive in
0757: // time or space.
0758:
0759: Object[] tab = traversalTable;
0760: int len = tab.length;
0761:
0762: int d = deletedSlot;
0763: Object key = tab[d];
0764: tab[d] = null; // vacate the slot
0765: tab[d + 1] = null;
0766:
0767: // If traversing a copy, remove in real table.
0768: // We can skip gap-closure on copy.
0769: if (tab != IdentityHashMap.this .table) {
0770: IdentityHashMap.this .remove(key);
0771: expectedModCount = modCount;
0772: return;
0773: }
0774:
0775: Object item;
0776: for (int i = nextKeyIndex(d, len); (item = tab[i]) != null; i = nextKeyIndex(
0777: i, len)) {
0778: int r = hash(item, len);
0779: // See closeDeletion for explanation of this conditional
0780: if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
0781:
0782: // If we are about to swap an already-seen element
0783: // into a slot that may later be returned by next(),
0784: // then clone the rest of table for use in future
0785: // next() calls. It is OK that our copy will have
0786: // a gap in the "wrong" place, since it will never
0787: // be used for searching anyway.
0788:
0789: if (i < deletedSlot
0790: && d >= deletedSlot
0791: && traversalTable == IdentityHashMap.this .table) {
0792: int remaining = len - deletedSlot;
0793: Object[] newTable = new Object[remaining];
0794: System.arraycopy(tab, deletedSlot, newTable, 0,
0795: remaining);
0796: traversalTable = newTable;
0797: index = 0;
0798: }
0799:
0800: tab[d] = item;
0801: tab[d + 1] = tab[i + 1];
0802: tab[i] = null;
0803: tab[i + 1] = null;
0804: d = i;
0805: }
0806: }
0807: }
0808: }
0809:
0810: private class KeyIterator extends IdentityHashMapIterator {
0811: public Object next() {
0812: return unmaskNull(traversalTable[nextIndex()]);
0813: }
0814: }
0815:
0816: private class ValueIterator extends IdentityHashMapIterator {
0817: public Object next() {
0818: return traversalTable[nextIndex() + 1];
0819: }
0820: }
0821:
0822: /**
0823: * Since we don't use Entry objects, we use the Iterator
0824: * itself as an entry.
0825: */
0826: private class EntryIterator extends IdentityHashMapIterator
0827: implements Map.Entry {
0828: public Object next() {
0829: nextIndex();
0830: return this ;
0831: }
0832:
0833: public Object getKey() {
0834: // Provide a better exception than out of bounds index
0835: if (lastReturnedIndex < 0)
0836: throw new IllegalStateException("Entry was removed");//$NON-NLS-1$
0837:
0838: return unmaskNull(traversalTable[lastReturnedIndex]);
0839: }
0840:
0841: public Object getValue() {
0842: // Provide a better exception than out of bounds index
0843: if (lastReturnedIndex < 0)
0844: throw new IllegalStateException("Entry was removed");//$NON-NLS-1$
0845:
0846: return traversalTable[lastReturnedIndex + 1];
0847: }
0848:
0849: public Object setValue(Object value) {
0850: // It would be mean-spirited to proceed here if remove() called
0851: if (lastReturnedIndex < 0)
0852: throw new IllegalStateException("Entry was removed");//$NON-NLS-1$
0853: Object oldValue = traversalTable[lastReturnedIndex + 1];
0854: traversalTable[lastReturnedIndex + 1] = value;
0855: // if shadowing, force into main table
0856: if (traversalTable != IdentityHashMap.this .table)
0857: put(traversalTable[lastReturnedIndex], value);
0858: return oldValue;
0859: }
0860:
0861: public boolean equals(Object o) {
0862: if (!(o instanceof Map.Entry))
0863: return false;
0864: Map.Entry e = (Map.Entry) o;
0865: return e.getKey() == getKey() && e.getValue() == getValue();
0866: }
0867:
0868: public int hashCode() {
0869: return System.identityHashCode(getKey())
0870: ^ System.identityHashCode(getValue());
0871: }
0872:
0873: public String toString() {
0874: return getKey() + "=" + getValue();//$NON-NLS-1$
0875: }
0876: }
0877:
0878: // Views
0879:
0880: /**
0881: * This field is initialized to contain an instance of the entry set
0882: * view the first time this view is requested. The view is stateless,
0883: * so there's no reason to create more than one.
0884: */
0885:
0886: private transient Set entrySet = null;
0887:
0888: /**
0889: * Returns an identity-based set view of the keys contained in this map.
0890: * The set is backed by the map, so changes to the map are reflected in
0891: * the set, and vice-versa. If the map is modified while an iteration
0892: * over the set is in progress, the results of the iteration are
0893: * undefined. The set supports element removal, which removes the
0894: * corresponding mapping from the map, via the <tt>Iterator.remove</tt>,
0895: * <tt>Set.remove</tt>, <tt>removeAll</tt> <tt>retainAll</tt>, and
0896: * <tt>clear</tt> methods. It does not support the <tt>add</tt> or
0897: * <tt>addAll</tt> methods.
0898: *
0899: * <p><b>While the object returned by this method implements the
0900: * <tt>Set</tt> interface, it does <i>not</i> obey <tt>Set's</tt> general
0901: * contract. Like its backing map, the set returned by this method
0902: * defines element equality as reference-equality rather than
0903: * object-equality. This affects the behavior of its <tt>contains</tt>,
0904: * <tt>remove</tt>, <tt>containsAll</tt>, <tt>equals</tt>, and
0905: * <tt>hashCode</tt> methods.</b>
0906: *
0907: * <p>The <tt>equals</tt> method of the returned set returns <tt>true</tt>
0908: * only if the specified object is a set containing exactly the same
0909: * object references as the returned set. The symmetry and transitivity
0910: * requirements of the <tt>Object.equals</tt> contract may be violated if
0911: * the set returned by this method is compared to a normal set. However,
0912: * the <tt>Object.equals</tt> contract is guaranteed to hold among sets
0913: * returned by this method.</b>
0914: *
0915: * <p>The <tt>hashCode</tt> method of the returned set returns the sum of
0916: * the <i>identity hashcodes</i> of the elements in the set, rather than
0917: * the sum of their hashcodes. This is mandated by the change in the
0918: * semantics of the <tt>equals</tt> method, in order to enforce the
0919: * general contract of the <tt>Object.hashCode</tt> method among sets
0920: * returned by this method.
0921: *
0922: * @return an identity-based set view of the keys contained in this map.
0923: * @see Object#equals(Object)
0924: * @see System#identityHashCode(Object)
0925: */
0926: public Set keySet() {
0927: return new KeySet();//XXX can't do otherwise than de-optimize
0928: /*
0929: Set ks = keySet;
0930: if (ks != null)
0931: return ks;
0932: else
0933: return keySet = new KeySet();
0934: */
0935: }
0936:
0937: private class KeySet extends AbstractSet {
0938: public Iterator iterator() {
0939: return new KeyIterator();
0940: }
0941:
0942: public int size() {
0943: return size;
0944: }
0945:
0946: public boolean contains(Object o) {
0947: return containsKey(o);
0948: }
0949:
0950: public boolean remove(Object o) {
0951: int oldSize = size;
0952: IdentityHashMap.this .remove(o);
0953: return size != oldSize;
0954: }
0955:
0956: /*
0957: * Must revert from AbstractSet's impl to AbstractCollection's, as
0958: * the former contains an optimization that results in incorrect
0959: * behavior when c is a smaller "normal" (non-identity-based) Set.
0960: */
0961: public boolean removeAll(Collection c) {
0962: boolean modified = false;
0963: for (Iterator i = iterator(); i.hasNext();) {
0964: if (c.contains(i.next())) {
0965: i.remove();
0966: modified = true;
0967: }
0968: }
0969: return modified;
0970: }
0971:
0972: public void clear() {
0973: IdentityHashMap.this .clear();
0974: }
0975:
0976: public int hashCode() {
0977: int result = 0;
0978: for (Iterator i = iterator(); i.hasNext();)
0979: result += System.identityHashCode(i.next());
0980: return result;
0981: }
0982: }
0983:
0984: /**
0985: * <p>Returns a collection view of the values contained in this map. The
0986: * collection is backed by the map, so changes to the map are reflected in
0987: * the collection, and vice-versa. If the map is modified while an
0988: * iteration over the collection is in progress, the results of the
0989: * iteration are undefined. The collection supports element removal,
0990: * which removes the corresponding mapping from the map, via the
0991: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0992: * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt> methods.
0993: * It does not support the <tt>add</tt> or <tt>addAll</tt> methods.
0994: *
0995: * <p><b>While the object returned by this method implements the
0996: * <tt>Collection</tt> interface, it does <i>not</i> obey
0997: * <tt>Collection's</tt> general contract. Like its backing map,
0998: * the collection returned by this method defines element equality as
0999: * reference-equality rather than object-equality. This affects the
1000: * behavior of its <tt>contains</tt>, <tt>remove</tt> and
1001: * <tt>containsAll</tt> methods.</b>
1002: *
1003: * @return a collection view of the values contained in this map.
1004: */
1005: public Collection values() {
1006: return new Values();//XXX can't do otherwise than de-optimize
1007: /*
1008: Collection vs = values;
1009: if (vs != null)
1010: return vs;
1011: else
1012: return values = new Values();
1013: */
1014: }
1015:
1016: private class Values extends AbstractCollection {
1017: public Iterator iterator() {
1018: return new ValueIterator();
1019: }
1020:
1021: public int size() {
1022: return size;
1023: }
1024:
1025: public boolean contains(Object o) {
1026: return containsValue(o);
1027: }
1028:
1029: public boolean remove(Object o) {
1030: for (Iterator i = iterator(); i.hasNext();) {
1031: if (i.next() == o) {
1032: i.remove();
1033: return true;
1034: }
1035: }
1036: return false;
1037: }
1038:
1039: public void clear() {
1040: IdentityHashMap.this .clear();
1041: }
1042: }
1043:
1044: /**
1045: * Returns a set view of the mappings contained in this map. Each element
1046: * in the returned set is a reference-equality-based <tt>Map.Entry</tt>.
1047: * The set is backed by the map, so changes to the map are reflected in
1048: * the set, and vice-versa. If the map is modified while an iteration
1049: * over the set is in progress, the results of the iteration are
1050: * undefined. The set supports element removal, which removes the
1051: * corresponding mapping from the map, via the <tt>Iterator.remove</tt>,
1052: * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
1053: * <tt>clear</tt> methods. It does not support the <tt>add</tt> or
1054: * <tt>addAll</tt> methods.
1055: *
1056: * <p>Like the backing map, the <tt>Map.Entry</tt> objects in the set
1057: * returned by this method define key and value equality as
1058: * reference-equality rather than object-equality. This affects the
1059: * behavior of the <tt>equals</tt> and <tt>hashCode</tt> methods of these
1060: * <tt>Map.Entry</tt> objects. A reference-equality based <tt>Map.Entry
1061: * e</tt> is equal to an object <tt>o</tt> if and only if <tt>o</tt> is a
1062: * <tt>Map.Entry</tt> and <tt>e.getKey()==o.getKey() &&
1063: * e.getValue()==o.getValue()</tt>. To accommodate these equals
1064: * semantics, the <tt>hashCode</tt> method returns
1065: * <tt>System.identityHashCode(e.getKey()) ^
1066: * System.identityHashCode(e.getValue())</tt>.
1067: *
1068: * <p><b>Owing to the reference-equality-based semantics of the
1069: * <tt>Map.Entry</tt> instances in the set returned by this method,
1070: * it is possible that the symmetry and transitivity requirements of
1071: * the {@link Object#equals(Object)} contract may be violated if any of
1072: * the entries in the set is compared to a normal map entry, or if
1073: * the set returned by this method is compared to a set of normal map
1074: * entries (such as would be returned by a call to this method on a normal
1075: * map). However, the <tt>Object.equals</tt> contract is guaranteed to
1076: * hold among identity-based map entries, and among sets of such entries.
1077: * </b>
1078: *
1079: * @return a set view of the identity-mappings contained in this map.
1080: */
1081: public Set entrySet() {
1082: Set es = entrySet;
1083: if (es != null)
1084: return es;
1085: else
1086: return entrySet = new EntrySet();
1087: }
1088:
1089: private class EntrySet extends AbstractSet {
1090: public Iterator iterator() {
1091: return new EntryIterator();
1092: }
1093:
1094: public boolean contains(Object o) {
1095: if (!(o instanceof Map.Entry))
1096: return false;
1097: Map.Entry entry = (Map.Entry) o;
1098: return containsMapping(entry.getKey(), entry.getValue());
1099: }
1100:
1101: public boolean remove(Object o) {
1102: if (!(o instanceof Map.Entry))
1103: return false;
1104: Map.Entry entry = (Map.Entry) o;
1105: return removeMapping(entry.getKey(), entry.getValue());
1106: }
1107:
1108: public int size() {
1109: return size;
1110: }
1111:
1112: public void clear() {
1113: IdentityHashMap.this .clear();
1114: }
1115:
1116: /*
1117: * Must revert from AbstractSet's impl to AbstractCollection's, as
1118: * the former contains an optimization that results in incorrect
1119: * behavior when c is a smaller "normal" (non-identity-based) Set.
1120: */
1121: public boolean removeAll(Collection c) {
1122: boolean modified = false;
1123: for (Iterator i = iterator(); i.hasNext();) {
1124: if (c.contains(i.next())) {
1125: i.remove();
1126: modified = true;
1127: }
1128: }
1129: return modified;
1130: }
1131:
1132: public Object[] toArray() {
1133: Collection c = new ArrayList(size());
1134: for (Iterator i = iterator(); i.hasNext();)
1135: c.add(new SimpleEntry((Map.Entry) i.next()));
1136: return c.toArray();
1137: }
1138:
1139: public Object[] toArray(Object a[]) {
1140: Collection c = new ArrayList(size());
1141: for (Iterator i = iterator(); i.hasNext();)
1142: c.add(new SimpleEntry((Map.Entry) i.next()));
1143: return c.toArray(a);
1144: }
1145:
1146: }
1147:
1148: /**
1149: * Save the state of the <tt>IdentityHashMap</tt> instance to a stream
1150: * (i.e., serialize it).
1151: *
1152: * @serialData The <i>size</i> of the HashMap (the number of key-value
1153: * mappings) (<tt>int</tt>), followed by the key (Object) and
1154: * value (Object) for each key-value mapping represented by the
1155: * IdentityHashMap. The key-value mappings are emitted in no
1156: * particular order.
1157: */
1158: private void writeObject(java.io.ObjectOutputStream s)
1159: throws java.io.IOException {
1160: // Write out and any hidden stuff
1161: s.defaultWriteObject();
1162:
1163: // Write out size (number of Mappings)
1164: s.writeInt(size);
1165:
1166: // Write out keys and values (alternating)
1167: Object[] tab = table;
1168: for (int i = 0; i < tab.length; i += 2) {
1169: Object key = tab[i];
1170: if (key != null) {
1171: s.writeObject(unmaskNull(key));
1172: s.writeObject(tab[i + 1]);
1173: }
1174: }
1175: }
1176:
1177: /**
1178: * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
1179: * deserialize it).
1180: */
1181: private void readObject(java.io.ObjectInputStream s)
1182: throws java.io.IOException, ClassNotFoundException {
1183: // Read in any hidden stuff
1184: s.defaultReadObject();
1185:
1186: // Read in size (number of Mappings)
1187: int l_size = s.readInt();
1188:
1189: // Allow for 33% growth (i.e., capacity is >= 2* size()).
1190: init(capacity((l_size * 4) / 3));
1191:
1192: // Read the keys and values, and put the mappings in the table
1193: for (int i = 0; i < l_size; ++i) {
1194: Object key = s.readObject();
1195: Object value = s.readObject();
1196: put(key, value);
1197: }
1198: }
1199: }
|