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