0001: /* ====================================================================
0002: * Trove - Copyright (c) 1997-2000 Walt Disney Internet Group
0003: * ====================================================================
0004: * The Tea Software License, Version 1.1
0005: *
0006: * Copyright (c) 2000 Walt Disney Internet Group. All rights reserved.
0007: *
0008: * Redistribution and use in source and binary forms, with or without
0009: * modification, are permitted provided that the following conditions
0010: * are met:
0011: *
0012: * 1. Redistributions of source code must retain the above copyright
0013: * notice, this list of conditions and the following disclaimer.
0014: *
0015: * 2. Redistributions in binary form must reproduce the above copyright
0016: * notice, this list of conditions and the following disclaimer in
0017: * the documentation and/or other materials provided with the
0018: * distribution.
0019: *
0020: * 3. The end-user documentation included with the redistribution,
0021: * if any, must include the following acknowledgment:
0022: * "This product includes software developed by the
0023: * Walt Disney Internet Group (http://opensource.go.com/)."
0024: * Alternately, this acknowledgment may appear in the software itself,
0025: * if and wherever such third-party acknowledgments normally appear.
0026: *
0027: * 4. The names "Tea", "TeaServlet", "Kettle", "Trove" and "BeanDoc" must
0028: * not be used to endorse or promote products derived from this
0029: * software without prior written permission. For written
0030: * permission, please contact opensource@dig.com.
0031: *
0032: * 5. Products derived from this software may not be called "Tea",
0033: * "TeaServlet", "Kettle" or "Trove", nor may "Tea", "TeaServlet",
0034: * "Kettle", "Trove" or "BeanDoc" appear in their name, without prior
0035: * written permission of the Walt Disney Internet Group.
0036: *
0037: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
0038: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
0039: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
0040: * DISCLAIMED. IN NO EVENT SHALL THE WALT DISNEY INTERNET GROUP OR ITS
0041: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
0042: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
0043: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
0044: * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
0045: * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0046: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
0047: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0048: * ====================================================================
0049: *
0050: * For more information about Tea, please see http://opensource.go.com/.
0051: */
0052:
0053: package com.go.trove.util;
0054:
0055: import java.lang.ref.*;
0056: import java.util.*;
0057:
0058: /******************************************************************************
0059: * An IdentityMap is like WeakHashMap, except it uses a key's identity
0060: * hashcode and equals methods. IdentityMap is not thread-safe and must be
0061: * wrapped with Collections.synchronizedMap to be made thread-safe. Most of the
0062: * implementation for this class is ripped off from java.util.HashMap, but not
0063: * java.util.WeakHashMap, in order to acheive greater efficiency.
0064: * <p>
0065: * The documentation for WeakHashMap states that it is intended primarily
0066: * for use with key objects whose equals methods test for object identity
0067: * using the == operator. Because WeakHashMap uses a key's own equals and
0068: * hashcode methods, it is better suited for implementing methods that behave
0069: * like {@link String#intern}. However, because WeakHashMap stongly references
0070: * values, {@link Utils#intern Utils.intern} provides a safer intern mechanism.
0071: * <p>
0072: * In this implementation, all key objects are tested for equality using the
0073: * == operator, and null keys are not permitted. IdentityMap is therefore
0074: * better suited for "canonicalized" mappings.
0075: * <p>
0076: * Note: Weakly referenced entries may be automatically removed during
0077: * either accessor or mutator operations, possibly causing a concurrent
0078: * modification to be detected. Therefore, even if multiple threads are only
0079: * accessing this map, be sure to synchronize this map first. Also, do not
0080: * rely on the value returned by size() when using an iterator from this map.
0081: * The iterators may return less entries than the amount reported by size().
0082: *
0083: * parametrized for GJ by Stefan Reich (doc@drjava.de)
0084: *
0085: * @author Brian S O'Neill
0086: * @version
0087: * <!--$$Revision: 1.2 $-->, <!--$$JustDate:--> 00/12/18 <!-- $-->
0088: * @see java.util.WeakHashMap
0089: * @see java.util.HashMap
0090: */
0091: public class IdentityMap<A, B> extends AbstractMap<A, B> implements
0092: Cloneable {
0093: // Types of Iterators
0094: static final int KEYS = 0;
0095: static final int VALUES = 1;
0096: static final int ENTRIES = 2;
0097:
0098: static final Iterator cEmptyHashIterator = new Iterator() {
0099: public boolean hasNext() {
0100: return false;
0101: }
0102:
0103: public Object next() {
0104: throw new NoSuchElementException();
0105: }
0106:
0107: public void remove() {
0108: throw new IllegalStateException();
0109: }
0110: };
0111:
0112: /**
0113: * Test program.
0114: */
0115: /*
0116: public static void main(String[] args) throws Exception {
0117: Map map = new IdentityMap();
0118: map.put("Hello", "There");
0119: for (int i=0; i<1000000; i++) {
0120: if (i % 5 == 0) {
0121: map.put(new String("Hello"), "Dude");
0122: }
0123: map.get("Hello");
0124: map.get("Stuff");
0125: }
0126:
0127: System.out.println(map.containsValue("Dude"));
0128: System.out.println(map.get("Hello"));
0129:
0130: System.gc();
0131:
0132: System.out.println(map);
0133: System.out.println(map.size());
0134:
0135: System.out.println(map.containsValue("Dude"));
0136: System.out.println(map.get("Hello"));
0137:
0138: map.remove("Hello");
0139:
0140: System.out.println(map);
0141: System.out.println(map.size());
0142:
0143: System.out.println(map.containsValue("Dude"));
0144: System.out.println(map.get("Hello"));
0145: }
0146: */
0147:
0148: /**
0149: * Converts a string to a collection without calling size(). Iterators from
0150: * this map may return less entries than the amount reported by size().
0151: */
0152: static String toString(Collection c) {
0153: StringBuffer buf = new StringBuffer();
0154: Iterator it = c.iterator();
0155: buf.append("[");
0156: for (int i = 0; it.hasNext(); i++) {
0157: if (i > 0) {
0158: buf.append(", ");
0159: }
0160: buf.append(String.valueOf(it.next()));
0161: }
0162: buf.append("]");
0163: return buf.toString();
0164: }
0165:
0166: /**
0167: * The hash table data.
0168: */
0169: private transient Entry<A, B> mTable[];
0170:
0171: /**
0172: * The total number of mappings in the hash table.
0173: */
0174: private transient int mCount;
0175:
0176: /**
0177: * The table is rehashed when its size exceeds this threshold. (The
0178: * value of this field is (int)(capacity * loadFactor).)
0179: *
0180: * @serial
0181: */
0182: private int mThreshold;
0183:
0184: /**
0185: * The load factor for the hashtable.
0186: *
0187: * @serial
0188: */
0189: private float mLoadFactor;
0190:
0191: /**
0192: * The number of times this HashMap has been structurally modified
0193: * Structural modifications are those that change the number of mappings in
0194: * the HashMap or otherwise modify its internal structure (e.g.,
0195: * rehash). This field is used to make iterators on Collection-views of
0196: * the HashMap fail-fast. (See ConcurrentModificationException).
0197: */
0198: private transient int mModCount = 0;
0199:
0200: // Views
0201:
0202: private transient Set mKeySet = null;
0203: private transient Set mEntrySet = null;
0204: private transient Collection mValues = null;
0205:
0206: /**
0207: * Constructs a new, empty map with the specified initial
0208: * capacity and the specified load factor.
0209: *
0210: * @param initialCapacity the initial capacity of the HashMap.
0211: * @param loadFactor the load factor of the HashMap
0212: * @throws IllegalArgumentException if the initial capacity is less
0213: * than zero, or if the load factor is nonpositive.
0214: */
0215: public IdentityMap(int initialCapacity, float loadFactor) {
0216: if (initialCapacity < 0) {
0217: throw new IllegalArgumentException(
0218: "Illegal Initial Capacity: " + initialCapacity);
0219: }
0220:
0221: if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
0222: throw new IllegalArgumentException("Illegal Load factor: "
0223: + loadFactor);
0224: }
0225:
0226: if (initialCapacity == 0) {
0227: initialCapacity = 1;
0228: }
0229:
0230: mLoadFactor = loadFactor;
0231: mTable = new Entry<A, B>[initialCapacity];
0232: mThreshold = (int) (initialCapacity * loadFactor);
0233: }
0234:
0235: /**
0236: * Constructs a new, empty map with the specified initial capacity
0237: * and default load factor, which is <tt>0.75</tt>.
0238: *
0239: * @param initialCapacity the initial capacity of the HashMap.
0240: * @throws IllegalArgumentException if the initial capacity is less
0241: * than zero.
0242: */
0243: public IdentityMap(int initialCapacity) {
0244: this (initialCapacity, 0.75f);
0245: }
0246:
0247: /**
0248: * Constructs a new, empty map with a default capacity and load
0249: * factor, which is <tt>0.75</tt>.
0250: */
0251: public IdentityMap() {
0252: this (11, 0.75f);
0253: }
0254:
0255: /**
0256: * Constructs a new map with the same mappings as the given map. The
0257: * map is created with a capacity of twice the number of mappings in
0258: * the given map or 11 (whichever is greater), and a default load factor,
0259: * which is <tt>0.75</tt>.
0260: */
0261: public IdentityMap(Map t) {
0262: this (Math.max(2 * t.size(), 11), 0.75f);
0263: putAll(t);
0264: }
0265:
0266: /**
0267: * Returns the number of key-value mappings in this map, but this value
0268: * may be larger than actual amount of entries produced by an iterator.
0269: *
0270: * @return the number of key-value mappings in this map.
0271: */
0272: public int size() {
0273: return mCount;
0274: }
0275:
0276: /**
0277: * Returns <tt>true</tt> if this map contains no key-value mappings.
0278: *
0279: * @return <tt>true</tt> if this map contains no key-value mappings.
0280: */
0281: public boolean isEmpty() {
0282: return mCount == 0;
0283: }
0284:
0285: /**
0286: * Returns <tt>true</tt> if this map maps one or more keys to the
0287: * specified value.
0288: *
0289: * @param value value whose presence in this map is to be tested.
0290: * @return <tt>true</tt> if this map maps one or more keys to the
0291: * specified value.
0292: */
0293: public boolean containsValue(B value) {
0294: Entry<A, B> tab[] = mTable;
0295:
0296: if (value == null) {
0297: for (int i = tab.length; i-- > 0;) {
0298: for (Entry<A, B> e = tab[i], prev = null; e != null; e = e.mNext) {
0299: if (e.getKey() == null) {
0300: // Clean up after a cleared Reference.
0301: mModCount++;
0302: if (prev != null) {
0303: prev.mNext = e.mNext;
0304: } else {
0305: tab[i] = e.mNext;
0306: }
0307: mCount--;
0308: } else if (e.mValue == null) {
0309: return true;
0310: } else {
0311: prev = e;
0312: }
0313: }
0314: }
0315: } else {
0316: for (int i = tab.length; i-- > 0;) {
0317: for (Entry<A, B> e = tab[i], prev = null; e != null; e = e.mNext) {
0318: if (e.getKey() == null) {
0319: // Clean up after a cleared Reference.
0320: mModCount++;
0321: if (prev != null) {
0322: prev.mNext = e.mNext;
0323: } else {
0324: tab[i] = e.mNext;
0325: }
0326: mCount--;
0327: } else if (value.equals(e.mValue)) {
0328: return true;
0329: } else {
0330: prev = e;
0331: }
0332: }
0333: }
0334: }
0335:
0336: return false;
0337: }
0338:
0339: /**
0340: * Returns <tt>true</tt> if this map contains a mapping for the specified
0341: * key.
0342: *
0343: * @return <tt>true</tt> if this map contains a mapping for the specified
0344: * key.
0345: * @param key key whose presence in this Map is to be tested.
0346: */
0347: public boolean containsKey(A key) {
0348: if (key == null) {
0349: return false;
0350: }
0351:
0352: Entry<A, B> tab[] = mTable;
0353: int hash = System.identityHashCode(key);
0354: int index = (hash & 0x7FFFFFFF) % tab.length;
0355:
0356: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
0357: A entryKey = e.getKey();
0358:
0359: if (entryKey == null) {
0360: // Clean up after a cleared Reference.
0361: mModCount++;
0362: if (prev != null) {
0363: prev.mNext = e.mNext;
0364: } else {
0365: tab[index] = e.mNext;
0366: }
0367: mCount--;
0368: } else if (e.mHash == hash && key == entryKey) {
0369: return true;
0370: } else {
0371: prev = e;
0372: }
0373: }
0374:
0375: return false;
0376: }
0377:
0378: /**
0379: * Returns the value to which this map maps the specified key. Returns
0380: * <tt>null</tt> if the map contains no mapping for this key. A return
0381: * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
0382: * map contains no mapping for the key; it's also possible that the map
0383: * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
0384: * operation may be used to distinguish these two cases.
0385: *
0386: * @return the value to which this map maps the specified key.
0387: * @param key key whose associated value is to be returned.
0388: */
0389: public B get(A key) {
0390: if (key == null) {
0391: return null;
0392: }
0393:
0394: Entry<A, B> tab[] = mTable;
0395: int hash = System.identityHashCode(key);
0396: int index = (hash & 0x7FFFFFFF) % tab.length;
0397:
0398: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
0399: A entryKey = e.getKey();
0400:
0401: if (entryKey == null) {
0402: // Clean up after a cleared Reference.
0403: mModCount++;
0404: if (prev != null) {
0405: prev.mNext = e.mNext;
0406: } else {
0407: tab[index] = e.mNext;
0408: }
0409: mCount--;
0410: } else if (e.mHash == hash && key == entryKey) {
0411: return e.mValue;
0412: } else {
0413: prev = e;
0414: }
0415: }
0416:
0417: return null;
0418: }
0419:
0420: /**
0421: * Scans the contents of this map, removing all entries that have a
0422: * cleared weak key.
0423: */
0424: private void cleanup() {
0425: Entry tab[] = mTable;
0426:
0427: for (int i = tab.length; i-- > 0;) {
0428: for (Entry e = tab[i], prev = null; e != null; e = e.mNext) {
0429: if (e.getKey() == null) {
0430: // Clean up after a cleared Reference.
0431: mModCount++;
0432: if (prev != null) {
0433: prev.mNext = e.mNext;
0434: } else {
0435: tab[i] = e.mNext;
0436: }
0437: mCount--;
0438: } else {
0439: prev = e;
0440: }
0441: }
0442: }
0443: }
0444:
0445: /**
0446: * Rehashes the contents of this map into a new <tt>HashMap</tt> instance
0447: * with a larger capacity. This method is called automatically when the
0448: * number of keys in this map exceeds its capacity and load factor.
0449: */
0450: private void rehash() {
0451: int oldCapacity = mTable.length;
0452: Entry oldMap[] = mTable;
0453:
0454: int newCapacity = oldCapacity * 2 + 1;
0455: Entry newMap[] = new Entry[newCapacity];
0456:
0457: mModCount++;
0458: mThreshold = (int) (newCapacity * mLoadFactor);
0459: mTable = newMap;
0460:
0461: for (int i = oldCapacity; i-- > 0;) {
0462: for (Entry old = oldMap[i]; old != null;) {
0463: Entry e = old;
0464: old = old.mNext;
0465:
0466: // Only copy entry if its key hasn't been cleared.
0467: if (e.getKey() == null) {
0468: mCount--;
0469: } else {
0470: int index = (e.mHash & 0x7FFFFFFF) % newCapacity;
0471: e.mNext = newMap[index];
0472: newMap[index] = e;
0473: }
0474: }
0475: }
0476: }
0477:
0478: /**
0479: * Associates the specified value with the specified key in this map.
0480: * If the map previously contained a mapping for this key, the old
0481: * value is replaced.
0482: *
0483: * @param key key with which the specified value is to be associated.
0484: * @param value value to be associated with the specified key.
0485: * @return previous value associated with specified key, or <tt>null</tt>
0486: * if there was no mapping for key. A <tt>null</tt> return can
0487: * also indicate that the HashMap previously associated
0488: * <tt>null</tt> with the specified key.
0489: */
0490: public B put(A key, B value) {
0491: if (key == null) {
0492: throw new NullPointerException("Null key is not permitted");
0493: }
0494:
0495: // Makes sure the key is not already in the HashMap.
0496: Entry<A, B> tab[] = mTable;
0497: int hash = System.identityHashCode(key);
0498: int index = (hash & 0x7FFFFFFF) % tab.length;
0499:
0500: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
0501: Object entryKey = e.getKey();
0502:
0503: if (entryKey == null) {
0504: // Clean up after a cleared Reference.
0505: mModCount++;
0506: if (prev != null) {
0507: prev.mNext = e.mNext;
0508: } else {
0509: tab[index] = e.mNext;
0510: }
0511: mCount--;
0512: } else if (e.mHash == hash && key == entryKey) {
0513: B old = e.mValue;
0514: e.mValue = value;
0515: return old;
0516: } else {
0517: prev = e;
0518: }
0519: }
0520:
0521: mModCount++;
0522:
0523: if (mCount >= mThreshold) {
0524: // Cleanup the table if the threshold is exceeded.
0525: cleanup();
0526: }
0527:
0528: if (mCount >= mThreshold) {
0529: // Rehash the table if the threshold is still exceeded.
0530: rehash();
0531: tab = mTable;
0532: index = (hash & 0x7FFFFFFF) % tab.length;
0533: }
0534:
0535: // Creates the new entry.
0536: Entry e = new Entry(hash, key, value, tab[index]);
0537: tab[index] = e;
0538: mCount++;
0539: return null;
0540: }
0541:
0542: /**
0543: * Removes the mapping for this key from this map if present.
0544: *
0545: * @param key key whose mapping is to be removed from the map.
0546: * @return previous value associated with specified key, or <tt>null</tt>
0547: * if there was no mapping for key. A <tt>null</tt> return can
0548: * also indicate that the map previously associated <tt>null</tt>
0549: * with the specified key.
0550: */
0551: public B remove(A key) {
0552: Entry<A, B> tab[] = mTable;
0553: int hash = System.identityHashCode(key);
0554: int index = (hash & 0x7FFFFFFF) % tab.length;
0555:
0556: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
0557: A entryKey = e.getKey();
0558:
0559: if (entryKey == null) {
0560: // Clean up after a cleared Reference.
0561: mModCount++;
0562: if (prev != null) {
0563: prev.mNext = e.mNext;
0564: } else {
0565: tab[index] = e.mNext;
0566: }
0567: mCount--;
0568: } else if (e.mHash == hash && key == entryKey) {
0569: mModCount++;
0570: if (prev != null) {
0571: prev.mNext = e.mNext;
0572: } else {
0573: tab[index] = e.mNext;
0574: }
0575: mCount--;
0576:
0577: B oldValue = e.mValue;
0578: e.mValue = null;
0579: return oldValue;
0580: } else {
0581: prev = e;
0582: }
0583: }
0584:
0585: return null;
0586: }
0587:
0588: /**
0589: * Copies all of the mappings from the specified map to this one.
0590: *
0591: * These mappings replace any mappings that this map had for any of the
0592: * keys currently in the specified Map.
0593: *
0594: * @param t Mappings to be stored in this map.
0595: */
0596: public void putAll(Map<A, B> t) {
0597: Iterator<Map.Entry<A, B>> i = t.entrySet().iterator();
0598: while (i.hasNext()) {
0599: Map.Entry<A, B> e = i.next();
0600: put(e.getKey(), e.getValue());
0601: }
0602: }
0603:
0604: /**
0605: * Removes all mappings from this map.
0606: */
0607: public void clear() {
0608: Entry tab[] = mTable;
0609: mModCount++;
0610: for (int index = tab.length; --index >= 0;) {
0611: tab[index] = null;
0612: }
0613: mCount = 0;
0614: }
0615:
0616: /**
0617: * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
0618: * values themselves are not cloned.
0619: *
0620: * @return a shallow copy of this map.
0621: */
0622: public Object clone() {
0623: try {
0624: IdentityMap t = (IdentityMap) super .clone();
0625: t.mTable = new Entry[mTable.length];
0626: for (int i = mTable.length; i-- > 0;) {
0627: t.mTable[i] = (mTable[i] != null) ? (Entry) mTable[i]
0628: .clone() : null;
0629: }
0630: t.mKeySet = null;
0631: t.mEntrySet = null;
0632: t.mValues = null;
0633: t.mModCount = 0;
0634: return t;
0635: } catch (CloneNotSupportedException e) {
0636: // this shouldn't happen, since we are Cloneable
0637: throw new InternalError();
0638: }
0639: }
0640:
0641: /**
0642: * Returns a set view of the keys contained in this map. The set is
0643: * backed by the map, so changes to the map are reflected in the set, and
0644: * vice-versa. The set supports element removal, which removes the
0645: * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
0646: * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
0647: * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
0648: * <tt>addAll</tt> operations.
0649: *
0650: * @return a set view of the keys contained in this map.
0651: */
0652: public Set<A> keySet() {
0653: if (mKeySet == null) {
0654: mKeySet = new AbstractSet<A>() {
0655: public Iterator<A> iterator() {
0656: return getHashIterator(KEYS);
0657: }
0658:
0659: public int size() {
0660: return mCount;
0661: }
0662:
0663: public boolean contains(A o) {
0664: return containsKey(o);
0665: }
0666:
0667: public boolean remove(A o) {
0668: return o == null ? false : IdentityMap.this
0669: .remove(o) == o;
0670: }
0671:
0672: public void clear() {
0673: IdentityMap.this .clear();
0674: }
0675:
0676: public String toString() {
0677: return IdentityMap.this .toString(this );
0678: }
0679: };
0680: }
0681: return mKeySet;
0682: }
0683:
0684: /**
0685: * Returns a collection view of the values contained in this map. The
0686: * collection is backed by the map, so changes to the map are reflected in
0687: * the collection, and vice-versa. The collection supports element
0688: * removal, which removes the corresponding mapping from this map, via the
0689: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0690: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
0691: * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
0692: *
0693: * @return a collection view of the values contained in this map.
0694: */
0695: public Collection<B> values() {
0696: if (mValues == null) {
0697: mValues = new AbstractCollection<B>() {
0698: public Iterator<B> iterator() {
0699: return getHashIterator(VALUES);
0700: }
0701:
0702: public int size() {
0703: return mCount;
0704: }
0705:
0706: public boolean contains(B o) {
0707: return containsValue(o);
0708: }
0709:
0710: public void clear() {
0711: IdentityMap.this .clear();
0712: }
0713:
0714: public String toString() {
0715: return IdentityMap.this .toString(this );
0716: }
0717: };
0718: }
0719: return mValues;
0720: }
0721:
0722: /**
0723: * Returns a collection view of the mappings contained in this map. Each
0724: * element in the returned collection is a <tt>Map.Entry</tt>. The
0725: * collection is backed by the map, so changes to the map are reflected in
0726: * the collection, and vice-versa. The collection supports element
0727: * removal, which removes the corresponding mapping from the map, via the
0728: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0729: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
0730: * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
0731: *
0732: * @return a collection view of the mappings contained in this map.
0733: * @see Map.Entry
0734: */
0735: public Set<Map.Entry<A, B>> entrySet() {
0736: if (mEntrySet == null) {
0737: mEntrySet = new AbstractSet<Map.Entry<A, B>>() {
0738: public Iterator<Map.Entry<A, B>> iterator() {
0739: return getHashIterator(ENTRIES);
0740: }
0741:
0742: public boolean contains(Map.Entry<A, B> entry) {
0743: A key = entry.getKey();
0744:
0745: Entry<A, B> tab[] = mTable;
0746: int hash = System.identityHashCode(key);
0747: int index = (hash & 0x7FFFFFFF) % tab.length;
0748:
0749: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
0750: A entryKey = e.getKey();
0751:
0752: if (entryKey == null) {
0753: // Clean up after a cleared Reference.
0754: mModCount++;
0755: if (prev != null) {
0756: prev.mNext = e.mNext;
0757: } else {
0758: tab[index] = e.mNext;
0759: }
0760: mCount--;
0761: } else if (e.mHash == hash
0762: && e.identityEquals(entry)) {
0763: return true;
0764: } else {
0765: prev = e;
0766: }
0767: }
0768:
0769: return false;
0770: }
0771:
0772: public boolean remove(Map.Entry<A, B> entry) {
0773: A key = entry.getKey();
0774: Entry<A, B> tab[] = mTable;
0775: int hash = System.identityHashCode(key);
0776: int index = (hash & 0x7FFFFFFF) % tab.length;
0777:
0778: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
0779: A entryKey = e.getKey();
0780:
0781: if (entryKey == null) {
0782: // Clean up after a cleared Reference.
0783: mModCount++;
0784: if (prev != null) {
0785: prev.mNext = e.mNext;
0786: } else {
0787: tab[index] = e.mNext;
0788: }
0789: mCount--;
0790: } else if (e.mHash == hash
0791: && e.identityEquals(entry)) {
0792: mModCount++;
0793: if (prev != null) {
0794: prev.mNext = e.mNext;
0795: } else {
0796: tab[index] = e.mNext;
0797: }
0798: mCount--;
0799:
0800: e.mValue = null;
0801: return true;
0802: } else {
0803: prev = e;
0804: }
0805: }
0806: return false;
0807: }
0808:
0809: public int size() {
0810: return mCount;
0811: }
0812:
0813: public void clear() {
0814: IdentityMap.this .clear();
0815: }
0816:
0817: public String toString() {
0818: return IdentityMap.this .toString(this );
0819: }
0820: };
0821: }
0822:
0823: return mEntrySet;
0824: }
0825:
0826: public String toString() {
0827: StringBuffer buf = new StringBuffer();
0828: Iterator it = entrySet().iterator();
0829:
0830: buf.append("{");
0831: for (int i = 0; it.hasNext(); i++) {
0832: if (i > 0) {
0833: buf.append(", ");
0834: }
0835: Map.Entry e = (Map.Entry) it.next();
0836: buf.append(e.getKey() + "=" + e.getValue());
0837: }
0838: buf.append("}");
0839: return buf.toString();
0840: }
0841:
0842: private Iterator getHashIterator(int type) {
0843: if (mCount == 0) {
0844: return cEmptyHashIterator;
0845: } else {
0846: return new HashIterator(type);
0847: }
0848: }
0849:
0850: /**
0851: * HashMap collision list entry.
0852: */
0853: private static class Entry<A, B> extends WeakReference<A> implements
0854: Map.Entry<A, B> {
0855: int mHash;
0856: B mValue;
0857: Entry<A, B> mNext;
0858:
0859: Entry(int hash, A key, B value, Entry<A, B> next) {
0860: super (key);
0861: mHash = hash;
0862: mValue = value;
0863: mNext = next;
0864: }
0865:
0866: protected Object clone() {
0867: return new Entry<A, B>(mHash, getKey(), mValue,
0868: (mNext == null ? null : (Entry) mNext.clone()));
0869: }
0870:
0871: // Map.Entry Ops
0872:
0873: public A getKey() {
0874: return Entry.this .get();
0875: }
0876:
0877: public B getValue() {
0878: return mValue;
0879: }
0880:
0881: public B setValue(B value) {
0882: B oldValue = mValue;
0883: mValue = value;
0884: return oldValue;
0885: }
0886:
0887: public boolean equals(Object o) {
0888: if (!(o instanceof Map.Entry)) {
0889: return false;
0890: }
0891: Map.Entry<A, B> e = (Map.Entry) o;
0892:
0893: A key = getKey();
0894:
0895: return (key == null ? e.getKey() == null : key.equals(e
0896: .getKey()))
0897: && (mValue == null ? e.getValue() == null : mValue
0898: .equals(e.getValue()));
0899: }
0900:
0901: public boolean identityEquals(Map.Entry<A, B> e) {
0902: return (getKey() == e.getKey())
0903: && (mValue == null ? e.getValue() == null : mValue
0904: .equals(e.getValue()));
0905: }
0906:
0907: public int hashCode() {
0908: return mHash ^ (mValue == null ? 0 : mValue.hashCode());
0909: }
0910:
0911: public String toString() {
0912: return getKey() + "=" + mValue;
0913: }
0914: }
0915:
0916: private class HashIterator implements Iterator {
0917: private Entry<A, B>[] mTable = IdentityMap.this .mTable;
0918: private int mIndex = mTable.length;
0919: private Entry<A, B> mEntry;
0920: // To ensure that the iterator doesn't return cleared entries, keep a
0921: // hard reference to the key. Its existence will prevent the weak
0922: // key from being cleared.
0923: private A mEntryKey;
0924: private Entry<A, B> mLastReturned;
0925: private int mType;
0926:
0927: /**
0928: * The modCount value that the iterator believes that the backing
0929: * List should have. If this expectation is violated, the iterator
0930: * has detected concurrent modification.
0931: */
0932: private int expectedModCount = mModCount;
0933:
0934: HashIterator(int type) {
0935: mType = type;
0936: }
0937:
0938: public boolean hasNext() {
0939: while (mEntry == null
0940: || (mEntryKey = mEntry.getKey()) == null) {
0941: if (mEntry != null) {
0942: // Clean up after a cleared Reference.
0943: remove(mEntry);
0944: mEntry = mEntry.mNext;
0945: } else {
0946: if (mIndex <= 0) {
0947: return false;
0948: } else {
0949: mEntry = mTable[--mIndex];
0950: }
0951: }
0952: }
0953:
0954: return true;
0955: }
0956:
0957: public Object next() {
0958: if (mModCount != expectedModCount) {
0959: throw new ConcurrentModificationException();
0960: }
0961:
0962: if (!hasNext()) {
0963: throw new NoSuchElementException();
0964: }
0965:
0966: mLastReturned = mEntry;
0967: mEntry = mEntry.mNext;
0968:
0969: return mType == KEYS ? (Object) mLastReturned.getKey()
0970: : (mType == VALUES ? (Object) mLastReturned
0971: .getValue() : mLastReturned);
0972: }
0973:
0974: public void remove() {
0975: if (mLastReturned == null) {
0976: throw new IllegalStateException();
0977: }
0978: if (mModCount != expectedModCount) {
0979: throw new ConcurrentModificationException();
0980: }
0981: remove(mLastReturned);
0982: mLastReturned = null;
0983: }
0984:
0985: private void remove(Entry<A, B> toRemove) {
0986: Entry<A, B>[] tab = mTable;
0987: int index = (toRemove.mHash & 0x7FFFFFFF) % tab.length;
0988:
0989: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
0990: if (e == toRemove) {
0991: mModCount++;
0992: expectedModCount++;
0993: if (prev == null) {
0994: tab[index] = e.mNext;
0995: } else {
0996: prev.mNext = e.mNext;
0997: }
0998: mCount--;
0999: return;
1000: } else {
1001: prev = e;
1002: }
1003: }
1004: throw new ConcurrentModificationException();
1005: }
1006: }
1007: }
|