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: * A Map that softly references its values and can be used as a simple cache.
0060: * SoftHashMap is not thread-safe and must be wrapped with
0061: * Collections.synchronizedMap to be made thread-safe. Most of the
0062: * implementation for this class is ripped off from java.util.HashMap
0063: * <p>
0064: * Note: Softly referenced entries may be automatically removed during
0065: * either accessor or mutator operations, possibly causing a concurrent
0066: * modification to be detected. Therefore, even if multiple threads are only
0067: * accessing this map, be sure to synchronize this map first. Also, do not
0068: * rely on the value returned by size() when using an iterator from this map.
0069: * The iterators may return less entries than the amount reported by size().
0070: *
0071: * parametrized for GJ by Stefan Reich (doc@drjava.de); removed Null
0072: * class because it defeats type safety
0073: *
0074: * @author Brian S O'Neill
0075: * @version
0076: * <!--$$Revision: 1.2 $-->, <!--$$JustDate:--> 9/07/00 <!-- $-->
0077: * @see Cache
0078: */
0079: public class SoftHashMap<A, B> extends AbstractMap<A, B> implements
0080: Cloneable {
0081: /**
0082: * Test program.
0083: */
0084: /*
0085: public static void main(String[] arg) throws Exception {
0086: Map cache = new SoftHashMap();
0087:
0088: for (int i = 0, j = 0; i < 100000; i++, j += 15) {
0089: if (i % 100 == 0) {
0090: System.out.println("Size = " + cache.size());
0091: }
0092:
0093: //Thread.sleep(1);
0094:
0095: Integer key = new Integer(i);
0096: Integer value = new Integer(j);
0097:
0098: cache.put(key, value);
0099: }
0100:
0101: Map.Entry entry = (Map.Entry)cache.entrySet().iterator().next();
0102: System.out.println(entry);
0103: //entry = null;
0104:
0105: System.out.println(cache);
0106:
0107: int originalSize = cache.size();
0108:
0109: //cache = null;
0110:
0111: for (int i=0; i<100; i++) {
0112: System.gc();
0113: }
0114:
0115: System.out.println(cache);
0116:
0117: System.out.println(originalSize);
0118: System.out.println(cache.size());
0119: System.out.println(entry);
0120:
0121: Thread.sleep(1000000);
0122: }
0123: */
0124:
0125: /**
0126: * The hash table data.
0127: */
0128: private transient Entry<A, B> mTable[];
0129:
0130: /**
0131: * The total number of mappings in the hash table.
0132: */
0133: private transient int mCount;
0134:
0135: /**
0136: * The table is rehashed when its size exceeds this threshold. (The
0137: * value of this field is (int)(capacity * loadFactor).)
0138: *
0139: * @serial
0140: */
0141: private int mThreshold;
0142:
0143: /**
0144: * The load factor for the hashtable.
0145: *
0146: * @serial
0147: */
0148: private float mLoadFactor;
0149:
0150: /**
0151: * The number of times this HashMap has been structurally modified
0152: * Structural modifications are those that change the number of mappings in
0153: * the HashMap or otherwise modify its internal structure (e.g.,
0154: * rehash). This field is used to make iterators on Collection-views of
0155: * the HashMap fail-fast. (See ConcurrentModificationException).
0156: */
0157: private transient int mModCount = 0;
0158:
0159: // Views
0160:
0161: private transient Set mKeySet = null;
0162: private transient Set mEntrySet = null;
0163: private transient Collection mValues = null;
0164:
0165: /**
0166: * Constructs a new, empty map with the specified initial
0167: * capacity and the specified load factor.
0168: *
0169: * @param initialCapacity the initial capacity of the HashMap.
0170: * @param loadFactor the load factor of the HashMap
0171: * @throws IllegalArgumentException if the initial capacity is less
0172: * than zero, or if the load factor is nonpositive.
0173: */
0174: public SoftHashMap(int initialCapacity, float loadFactor) {
0175: if (initialCapacity < 0) {
0176: throw new IllegalArgumentException(
0177: "Illegal Initial Capacity: " + initialCapacity);
0178: }
0179:
0180: if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
0181: throw new IllegalArgumentException("Illegal Load factor: "
0182: + loadFactor);
0183: }
0184:
0185: if (initialCapacity == 0) {
0186: initialCapacity = 1;
0187: }
0188:
0189: mLoadFactor = loadFactor;
0190: mTable = new Entry<A, B>[initialCapacity];
0191: mThreshold = (int) (initialCapacity * loadFactor);
0192: }
0193:
0194: /**
0195: * Constructs a new, empty map with the specified initial capacity
0196: * and default load factor, which is <tt>0.75</tt>.
0197: *
0198: * @param initialCapacity the initial capacity of the HashMap.
0199: * @throws IllegalArgumentException if the initial capacity is less
0200: * than zero.
0201: */
0202: public SoftHashMap(int initialCapacity) {
0203: this (initialCapacity, 0.75f);
0204: }
0205:
0206: /**
0207: * Constructs a new, empty map with a default capacity and load
0208: * factor, which is <tt>0.75</tt>.
0209: */
0210: public SoftHashMap() {
0211: this (11, 0.75f);
0212: }
0213:
0214: /**
0215: * Constructs a new map with the same mappings as the given map. The
0216: * map is created with a capacity of twice the number of mappings in
0217: * the given map or 11 (whichever is greater), and a default load factor,
0218: * which is <tt>0.75</tt>.
0219: */
0220: public SoftHashMap(Map t) {
0221: this (Math.max(2 * t.size(), 11), 0.75f);
0222: putAll(t);
0223: }
0224:
0225: /**
0226: * Returns the number of key-value mappings in this map, but this value
0227: * may be larger than actual amount of entries produced by an iterator.
0228: *
0229: * @return the number of key-value mappings in this map.
0230: */
0231: public int size() {
0232: return mCount;
0233: }
0234:
0235: /**
0236: * Returns <tt>true</tt> if this map contains no key-value mappings.
0237: *
0238: * @return <tt>true</tt> if this map contains no key-value mappings.
0239: */
0240: public boolean isEmpty() {
0241: return mCount == 0;
0242: }
0243:
0244: /**
0245: * Returns <tt>true</tt> if this map maps one or more keys to the
0246: * specified value.
0247: *
0248: * @param value value whose presence in this map is to be tested.
0249: * @return <tt>true</tt> if this map maps one or more keys to the
0250: * specified value.
0251: */
0252: public boolean containsValue(B value) {
0253: /*if (value == null) {
0254: value = new Null();
0255: }*/
0256:
0257: Entry<A, B> tab[] = mTable;
0258:
0259: for (int i = tab.length; i-- > 0;) {
0260: for (Entry<A, B> e = tab[i], prev = null; e != null; e = e.mNext) {
0261: B entryValue = e.getValue();
0262:
0263: if (entryValue == null) {
0264: // Clean up after a cleared Reference.
0265: mModCount++;
0266: if (prev != null) {
0267: prev.mNext = e.mNext;
0268: } else {
0269: tab[i] = e.mNext;
0270: }
0271: mCount--;
0272: } else if (value.equals(entryValue)) {
0273: return true;
0274: } else {
0275: prev = e;
0276: }
0277: }
0278: }
0279:
0280: return false;
0281: }
0282:
0283: /**
0284: * Returns <tt>true</tt> if this map contains a mapping for the specified
0285: * key.
0286: *
0287: * @return <tt>true</tt> if this map contains a mapping for the specified
0288: * key.
0289: * @param key key whose presence in this Map is to be tested.
0290: */
0291: public boolean containsKey(A key) {
0292: Entry<A, B> tab[] = mTable;
0293:
0294: if (key != null) {
0295: int hash = key.hashCode();
0296: int index = (hash & 0x7FFFFFFF) % tab.length;
0297: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
0298: if (e.getValue() == null) {
0299: // Clean up after a cleared Reference.
0300: mModCount++;
0301: if (prev != null) {
0302: prev.mNext = e.mNext;
0303: } else {
0304: tab[index] = e.mNext;
0305: }
0306: mCount--;
0307: } else if (e.mHash == hash && key.equals(e.mKey)) {
0308: return true;
0309: } else {
0310: prev = e;
0311: }
0312: }
0313: } else {
0314: for (Entry<A, B> e = tab[0], prev = null; e != null; e = e.mNext) {
0315: if (e.getValue() == null) {
0316: // Clean up after a cleared Reference.
0317: mModCount++;
0318: if (prev != null) {
0319: prev.mNext = e.mNext;
0320: } else {
0321: tab[0] = e.mNext;
0322: }
0323: mCount--;
0324: } else if (e.mKey == null) {
0325: return true;
0326: } else {
0327: prev = e;
0328: }
0329: }
0330: }
0331:
0332: return false;
0333: }
0334:
0335: /**
0336: * Returns the value to which this map maps the specified key. Returns
0337: * <tt>null</tt> if the map contains no mapping for this key. A return
0338: * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
0339: * map contains no mapping for the key; it's also possible that the map
0340: * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
0341: * operation may be used to distinguish these two cases.
0342: *
0343: * @return the value to which this map maps the specified key.
0344: * @param key key whose associated value is to be returned.
0345: */
0346: public B get(A key) {
0347: Entry<A, B> tab[] = mTable;
0348:
0349: if (key != null) {
0350: int hash = key.hashCode();
0351: int index = (hash & 0x7FFFFFFF) % tab.length;
0352:
0353: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
0354: B entryValue = e.getValue();
0355:
0356: if (entryValue == null) {
0357: // Clean up after a cleared Reference.
0358: mModCount++;
0359: if (prev != null) {
0360: prev.mNext = e.mNext;
0361: } else {
0362: tab[index] = e.mNext;
0363: }
0364: mCount--;
0365: } else if (e.mHash == hash && key.equals(e.mKey)) {
0366: return /*(entryValue instanceof Null) ? null :*/entryValue;
0367: } else {
0368: prev = e;
0369: }
0370: }
0371: } else {
0372: for (Entry<A, B> e = tab[0], prev = null; e != null; e = e.mNext) {
0373: B entryValue = e.getValue();
0374:
0375: if (entryValue == null) {
0376: // Clean up after a cleared Reference.
0377: mModCount++;
0378: if (prev != null) {
0379: prev.mNext = e.mNext;
0380: } else {
0381: tab[0] = e.mNext;
0382: }
0383: mCount--;
0384: } else if (e.mKey == null) {
0385: return /*(entryValue instanceof Null) ? null :*/entryValue;
0386: } else {
0387: prev = e;
0388: }
0389: }
0390: }
0391:
0392: return null;
0393: }
0394:
0395: /**
0396: * Scans the contents of this map, removing all entries that have a
0397: * cleared soft value.
0398: */
0399: private void cleanup() {
0400: Entry<A, B> tab[] = mTable;
0401:
0402: for (int i = tab.length; i-- > 0;) {
0403: for (Entry<A, B> e = tab[i], prev = null; e != null; e = e.mNext) {
0404: if (e.getValue() == null) {
0405: // Clean up after a cleared Reference.
0406: mModCount++;
0407: if (prev != null) {
0408: prev.mNext = e.mNext;
0409: } else {
0410: tab[i] = e.mNext;
0411: }
0412: mCount--;
0413: } else {
0414: prev = e;
0415: }
0416: }
0417: }
0418: }
0419:
0420: /**
0421: * Rehashes the contents of this map into a new <tt>HashMap</tt> instance
0422: * with a larger capacity. This method is called automatically when the
0423: * number of keys in this map exceeds its capacity and load factor.
0424: */
0425: private void rehash() {
0426: int oldCapacity = mTable.length;
0427: Entry<A, B> oldMap[] = mTable;
0428:
0429: int newCapacity = oldCapacity * 2 + 1;
0430: Entry<A, B> newMap[] = new Entry<A, B>[newCapacity];
0431:
0432: mModCount++;
0433: mThreshold = (int) (newCapacity * mLoadFactor);
0434: mTable = newMap;
0435:
0436: for (int i = oldCapacity; i-- > 0;) {
0437: for (Entry<A, B> old = oldMap[i]; old != null;) {
0438: Entry<A, B> e = old;
0439: old = old.mNext;
0440:
0441: // Only copy entry if its value hasn't been cleared.
0442: if (e.getValue() == null) {
0443: mCount--;
0444: } else {
0445: int index = (e.mHash & 0x7FFFFFFF) % newCapacity;
0446: e.mNext = newMap[index];
0447: newMap[index] = e;
0448: }
0449: }
0450: }
0451: }
0452:
0453: /**
0454: * Associates the specified value with the specified key in this map.
0455: * If the map previously contained a mapping for this key, the old
0456: * value is replaced.
0457: *
0458: * @param key key with which the specified value is to be associated.
0459: * @param value value to be associated with the specified key.
0460: * @return previous value associated with specified key, or <tt>null</tt>
0461: * if there was no mapping for key. A <tt>null</tt> return can
0462: * also indicate that the HashMap previously associated
0463: * <tt>null</tt> with the specified key.
0464: */
0465: public B put(A key, B value) {
0466: /*if (value == null) {
0467: value = new Null();
0468: }*/
0469:
0470: // Makes sure the key is not already in the HashMap.
0471: Entry<A, B> tab[] = mTable;
0472: int hash;
0473: int index;
0474:
0475: if (key != null) {
0476: hash = key.hashCode();
0477: index = (hash & 0x7FFFFFFF) % tab.length;
0478: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
0479: B entryValue = e.getValue();
0480:
0481: if (e.getValue() == null) {
0482: // Clean up after a cleared Reference.
0483: mModCount++;
0484: if (prev != null) {
0485: prev.mNext = e.mNext;
0486: } else {
0487: tab[index] = e.mNext;
0488: }
0489: mCount--;
0490: } else if (e.mHash == hash && key.equals(e.mKey)) {
0491: e.setValue(value);
0492: return /*(entryValue instanceof Null) ? null :*/entryValue;
0493: } else {
0494: prev = e;
0495: }
0496: }
0497: } else {
0498: hash = 0;
0499: index = 0;
0500: for (Entry<A, B> e = tab[0], prev = null; e != null; e = e.mNext) {
0501: B entryValue = e.getValue();
0502:
0503: if (entryValue == null) {
0504: // Clean up after a cleared Reference.
0505: mModCount++;
0506: if (prev != null) {
0507: prev.mNext = e.mNext;
0508: } else {
0509: tab[0] = e.mNext;
0510: }
0511: mCount--;
0512: } else if (e.mKey == null) {
0513: e.setValue(value);
0514: return /*(entryValue instanceof Null) ? null :*/entryValue;
0515: } else {
0516: prev = e;
0517: }
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<A, B> e = new Entry<A, B>(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:
0554: if (key != null) {
0555: int hash = key.hashCode();
0556: int index = (hash & 0x7FFFFFFF) % tab.length;
0557:
0558: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
0559: B entryValue = e.getValue();
0560:
0561: if (entryValue == null) {
0562: // Clean up after a cleared Reference.
0563: mModCount++;
0564: if (prev != null) {
0565: prev.mNext = e.mNext;
0566: } else {
0567: tab[index] = e.mNext;
0568: }
0569: mCount--;
0570: } else if (e.mHash == hash && key.equals(e.mKey)) {
0571: mModCount++;
0572: if (prev != null) {
0573: prev.mNext = e.mNext;
0574: } else {
0575: tab[index] = e.mNext;
0576: }
0577: mCount--;
0578:
0579: e.setValue(null);
0580: return /*(entryValue instanceof Null) ? null :*/entryValue;
0581: } else {
0582: prev = e;
0583: }
0584: }
0585: } else {
0586: for (Entry<A, B> e = tab[0], prev = null; e != null; e = e.mNext) {
0587: B entryValue = e.getValue();
0588:
0589: if (entryValue == null) {
0590: // Clean up after a cleared Reference.
0591: mModCount++;
0592: if (prev != null) {
0593: prev.mNext = e.mNext;
0594: } else {
0595: tab[0] = e.mNext;
0596: }
0597: mCount--;
0598: } else if (e.mKey == null) {
0599: mModCount++;
0600: if (prev != null) {
0601: prev.mNext = e.mNext;
0602: } else {
0603: tab[0] = e.mNext;
0604: }
0605: mCount--;
0606:
0607: e.setValue(null);
0608: return /*(entryValue instanceof Null) ? null :*/entryValue;
0609: } else {
0610: prev = e;
0611: }
0612: }
0613: }
0614:
0615: return null;
0616: }
0617:
0618: /**
0619: * Copies all of the mappings from the specified map to this one.
0620: *
0621: * These mappings replace any mappings that this map had for any of the
0622: * keys currently in the specified Map.
0623: *
0624: * @param t Mappings to be stored in this map.
0625: */
0626: public void putAll(Map<A, B> t) {
0627: Iterator<Map.Entry<A, B>> i = t.entrySet().iterator();
0628: while (i.hasNext()) {
0629: Map.Entry<A, B> e = i.next();
0630: put(e.getKey(), e.getValue());
0631: }
0632: }
0633:
0634: /**
0635: * Removes all mappings from this map.
0636: */
0637: public void clear() {
0638: Entry<A, B> tab[] = mTable;
0639: mModCount++;
0640: for (int index = tab.length; --index >= 0;) {
0641: tab[index] = null;
0642: }
0643: mCount = 0;
0644: }
0645:
0646: /**
0647: * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
0648: * values themselves are not cloned.
0649: *
0650: * @return a shallow copy of this map.
0651: */
0652: public Object clone() {
0653: try {
0654: SoftHashMap t = (SoftHashMap) super .clone();
0655: t.mTable = new Entry<A, B>[mTable.length];
0656: for (int i = mTable.length; i-- > 0;) {
0657: t.mTable[i] = (mTable[i] != null) ? (Entry) mTable[i]
0658: .clone() : null;
0659: }
0660: t.mKeySet = null;
0661: t.mEntrySet = null;
0662: t.mValues = null;
0663: t.mModCount = 0;
0664: return t;
0665: } catch (CloneNotSupportedException e) {
0666: // this shouldn't happen, since we are Cloneable
0667: throw new InternalError();
0668: }
0669: }
0670:
0671: /**
0672: * Returns a set view of the keys contained in this map. The set is
0673: * backed by the map, so changes to the map are reflected in the set, and
0674: * vice-versa. The set supports element removal, which removes the
0675: * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
0676: * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
0677: * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
0678: * <tt>addAll</tt> operations.
0679: *
0680: * @return a set view of the keys contained in this map.
0681: */
0682: public Set<A> keySet() {
0683: if (mKeySet == null) {
0684: mKeySet = new AbstractSet<A>() {
0685: public Iterator<A> iterator() {
0686: return getHashIterator(IdentityMap.KEYS);
0687: }
0688:
0689: public int size() {
0690: return mCount;
0691: }
0692:
0693: public boolean contains(A o) {
0694: return containsKey(o);
0695: }
0696:
0697: public boolean remove(A o) {
0698: if (o == null) {
0699: if (SoftHashMap.this .containsKey(null)) {
0700: SoftHashMap.this .remove(null);
0701: return true;
0702: } else {
0703: return false;
0704: }
0705: } else {
0706: return SoftHashMap.this .remove(o) != null;
0707: }
0708: }
0709:
0710: public void clear() {
0711: SoftHashMap.this .clear();
0712: }
0713:
0714: public String toString() {
0715: return IdentityMap.toString(this );
0716: }
0717: };
0718: }
0719: return mKeySet;
0720: }
0721:
0722: /**
0723: * Returns a collection view of the values contained in this map. The
0724: * collection is backed by the map, so changes to the map are reflected in
0725: * the collection, and vice-versa. The collection supports element
0726: * removal, which removes the corresponding mapping from this map, via the
0727: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0728: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
0729: * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
0730: *
0731: * @return a collection view of the values contained in this map.
0732: */
0733: public Collection<B> values() {
0734: if (mValues == null) {
0735: mValues = new AbstractCollection<B>() {
0736: public Iterator<B> iterator() {
0737: return getHashIterator(IdentityMap.VALUES);
0738: }
0739:
0740: public int size() {
0741: return mCount;
0742: }
0743:
0744: public boolean contains(B o) {
0745: return containsValue(o);
0746: }
0747:
0748: public void clear() {
0749: SoftHashMap.this .clear();
0750: }
0751:
0752: public String toString() {
0753: return IdentityMap.toString(this );
0754: }
0755: };
0756: }
0757: return mValues;
0758: }
0759:
0760: /**
0761: * Returns a collection view of the mappings contained in this map. Each
0762: * element in the returned collection is a <tt>Map.Entry</tt>. The
0763: * collection is backed by the map, so changes to the map are reflected in
0764: * the collection, and vice-versa. The collection supports element
0765: * removal, which removes the corresponding mapping from the map, via the
0766: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0767: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
0768: * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
0769: *
0770: * @return a collection view of the mappings contained in this map.
0771: * @see Map.Entry
0772: */
0773: public Set<Map.Entry<A, B>> entrySet() {
0774: if (mEntrySet == null) {
0775: mEntrySet = new AbstractSet<Map.Entry<A, B>>() {
0776: public Iterator<Map.Entry<A, B>> iterator() {
0777: return getHashIterator(IdentityMap.ENTRIES);
0778: }
0779:
0780: public boolean contains(Map.Entry<A, B> entry) {
0781: A key = entry.getKey();
0782:
0783: Entry<A, B> tab[] = mTable;
0784: int hash = key == null ? 0 : key.hashCode();
0785: int index = (hash & 0x7FFFFFFF) % tab.length;
0786:
0787: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
0788: B entryValue = e.getValue();
0789:
0790: if (entryValue == null) {
0791: // Clean up after a cleared Reference.
0792: mModCount++;
0793: if (prev != null) {
0794: prev.mNext = e.mNext;
0795: } else {
0796: tab[index] = e.mNext;
0797: }
0798: mCount--;
0799: } else if (e.mHash == hash && e.equals(entry)) {
0800: return true;
0801: } else {
0802: prev = e;
0803: }
0804: }
0805:
0806: return false;
0807: }
0808:
0809: public boolean remove(Map.Entry<A, B> entry) {
0810: A key = entry.getKey();
0811: Entry<A, B> tab[] = mTable;
0812: int hash = key == null ? 0 : key.hashCode();
0813: int index = (hash & 0x7FFFFFFF) % tab.length;
0814:
0815: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
0816: B entryValue = e.getValue();
0817:
0818: if (entryValue == null) {
0819: // Clean up after a cleared Reference.
0820: mModCount++;
0821: if (prev != null) {
0822: prev.mNext = e.mNext;
0823: } else {
0824: tab[index] = e.mNext;
0825: }
0826: mCount--;
0827: } else if (e.mHash == hash && e.equals(entry)) {
0828: mModCount++;
0829: if (prev != null) {
0830: prev.mNext = e.mNext;
0831: } else {
0832: tab[index] = e.mNext;
0833: }
0834: mCount--;
0835:
0836: e.setValue(null);
0837: return true;
0838: } else {
0839: prev = e;
0840: }
0841: }
0842: return false;
0843: }
0844:
0845: public int size() {
0846: return mCount;
0847: }
0848:
0849: public void clear() {
0850: SoftHashMap.this .clear();
0851: }
0852:
0853: public String toString() {
0854: return IdentityMap.toString(this );
0855: }
0856: };
0857: }
0858:
0859: return mEntrySet;
0860: }
0861:
0862: public String toString() {
0863: StringBuffer buf = new StringBuffer();
0864: Iterator it = entrySet().iterator();
0865:
0866: buf.append("{");
0867: for (int i = 0; it.hasNext(); i++) {
0868: if (i > 0) {
0869: buf.append(", ");
0870: }
0871: Map.Entry<A, B> e = (Map.Entry) it.next();
0872: buf.append(e.getKey() + "=" + e.getValue());
0873: }
0874: buf.append("}");
0875: return buf.toString();
0876: }
0877:
0878: private Iterator getHashIterator(int type) {
0879: if (mCount == 0) {
0880: return IdentityMap.cEmptyHashIterator;
0881: } else {
0882: return new HashIterator(type);
0883: }
0884: }
0885:
0886: /**
0887: * HashMap collision list entry.
0888: */
0889: private static class Entry<A, B> implements Map.Entry<A, B> {
0890: int mHash;
0891: A mKey;
0892: Entry<A, B> mNext;
0893:
0894: private Reference<B> mValue;
0895:
0896: Entry(int hash, A key, B value, Entry<A, B> next) {
0897: mHash = hash;
0898: mKey = key;
0899: mValue = new SoftReference<B>(value);
0900: mNext = next;
0901: }
0902:
0903: private Entry(int hash, A key, Reference<B> value,
0904: Entry<A, B> next) {
0905: mHash = hash;
0906: mKey = key;
0907: mValue = value;
0908: mNext = next;
0909: }
0910:
0911: protected Object clone() {
0912: return new Entry<A, B>(mHash, mKey, mValue,
0913: (mNext == null ? null : (Entry) mNext.clone()));
0914: }
0915:
0916: // Map.Entry Ops
0917:
0918: public A getKey() {
0919: return mKey;
0920: }
0921:
0922: public B getValue() {
0923: return mValue.get();
0924: }
0925:
0926: public B setValue(B value) {
0927: B oldValue = getValue();
0928: if (value == null) {
0929: mValue.clear();
0930: } else {
0931: mValue = new SoftReference<B>(value);
0932: }
0933: return oldValue;
0934: }
0935:
0936: public boolean equals(Object o) {
0937: if (!(o instanceof Map.Entry)) {
0938: return false;
0939: }
0940: Map.Entry e = (Map.Entry) o;
0941:
0942: B value = getValue();
0943:
0944: return (mKey == null ? e.getKey() == null : mKey.equals(e
0945: .getKey()))
0946: && (value == null ? e.getValue() == null : value
0947: .equals(e.getValue()));
0948: }
0949:
0950: public int hashCode() {
0951: B value = getValue();
0952: return mHash ^ (value == null ? 0 : value.hashCode());
0953: }
0954:
0955: public String toString() {
0956: return mKey + "=" + getValue();
0957: }
0958: }
0959:
0960: private class HashIterator implements Iterator {
0961: private Entry<A, B>[] mTable = SoftHashMap.this .mTable;
0962: private int mIndex = mTable.length;
0963: private Entry<A, B> mEntry;
0964: // To ensure that the iterator doesn't return cleared entries, keep a
0965: // hard reference to the value. Its existence will prevent the soft
0966: // value from being cleared.
0967: private B mEntryValue;
0968: private Entry mLastReturned;
0969: private int mType;
0970:
0971: /**
0972: * The modCount value that the iterator believes that the backing
0973: * List should have. If this expectation is violated, the iterator
0974: * has detected concurrent modification.
0975: */
0976: private int expectedModCount = mModCount;
0977:
0978: HashIterator(int type) {
0979: mType = type;
0980: }
0981:
0982: public boolean hasNext() {
0983: while (mEntry == null
0984: || (mEntryValue = mEntry.getValue()) == null) {
0985: if (mEntry != null) {
0986: // Clean up after a cleared Reference.
0987: remove(mEntry);
0988: mEntry = mEntry.mNext;
0989: }
0990:
0991: if (mEntry == null) {
0992: if (mIndex <= 0) {
0993: return false;
0994: } else {
0995: mEntry = mTable[--mIndex];
0996: }
0997: }
0998: }
0999:
1000: return true;
1001: }
1002:
1003: public Object next() {
1004: if (mModCount != expectedModCount) {
1005: throw new ConcurrentModificationException();
1006: }
1007:
1008: if (!hasNext()) {
1009: throw new NoSuchElementException();
1010: }
1011:
1012: mLastReturned = mEntry;
1013: mEntry = mEntry.mNext;
1014:
1015: if (mType == IdentityMap.KEYS) {
1016: return mLastReturned.getKey();
1017: } else if (mType == IdentityMap.VALUES) {
1018: Object value = mLastReturned.getValue();
1019: return /*(value instanceof Null) ? null :*/value;
1020: } else {
1021: return mLastReturned;
1022: }
1023: }
1024:
1025: public void remove() {
1026: if (mLastReturned == null) {
1027: throw new IllegalStateException();
1028: }
1029: if (mModCount != expectedModCount) {
1030: throw new ConcurrentModificationException();
1031: }
1032: remove(mLastReturned);
1033: mLastReturned = null;
1034: }
1035:
1036: private void remove(Entry<A, B> toRemove) {
1037: Entry<A, B>[] tab = mTable;
1038: int index = (toRemove.mHash & 0x7FFFFFFF) % tab.length;
1039:
1040: for (Entry<A, B> e = tab[index], prev = null; e != null; e = e.mNext) {
1041: if (e == toRemove) {
1042: mModCount++;
1043: expectedModCount++;
1044: if (prev == null) {
1045: tab[index] = e.mNext;
1046: } else {
1047: prev.mNext = e.mNext;
1048: }
1049: mCount--;
1050: return;
1051: } else {
1052: prev = e;
1053: }
1054: }
1055: throw new ConcurrentModificationException();
1056: }
1057: }
1058:
1059: /**
1060: * This allows null references to be saved into SoftHashMap and allow
1061: * entries to still be garbage collected.
1062: */
1063: /*static class Null {
1064: public boolean equals(Object other) {
1065: return other == null || other instanceof Null;
1066: }
1067:
1068: public String toString() {
1069: return "null";
1070: }
1071: }*/
1072: }
|