Mercurial > hg > blitz_condensed
diff src/com/go/trove/util/SoftHashMap.java @ 0:3dc0c5604566
Initial checkin of blitz 2.0 fcs - no installer yet.
author | Dan Creswell <dan.creswell@gmail.com> |
---|---|
date | Sat, 21 Mar 2009 11:00:06 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/com/go/trove/util/SoftHashMap.java Sat Mar 21 11:00:06 2009 +0000 @@ -0,0 +1,1117 @@ +/* ==================================================================== + * Trove - Copyright (c) 1997-2000 Walt Disney Internet Group + * ==================================================================== + * The Tea Software License, Version 1.1 + * + * Copyright (c) 2000 Walt Disney Internet Group. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. The end-user documentation included with the redistribution, + * if any, must include the following acknowledgment: + * "This product includes software developed by the + * Walt Disney Internet Group (http://opensource.go.com/)." + * Alternately, this acknowledgment may appear in the software itself, + * if and wherever such third-party acknowledgments normally appear. + * + * 4. The names "Tea", "TeaServlet", "Kettle", "Trove" and "BeanDoc" must + * not be used to endorse or promote products derived from this + * software without prior written permission. For written + * permission, please contact opensource@dig.com. + * + * 5. Products derived from this software may not be called "Tea", + * "TeaServlet", "Kettle" or "Trove", nor may "Tea", "TeaServlet", + * "Kettle", "Trove" or "BeanDoc" appear in their name, without prior + * written permission of the Walt Disney Internet Group. + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE WALT DISNEY INTERNET GROUP OR ITS + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * For more information about Tea, please see http://opensource.go.com/. + */ + +package com.go.trove.util; + +import java.lang.ref.*; +import java.util.*; + +/****************************************************************************** + * A Map that softly references its values and can be used as a simple cache. + * SoftHashMap is not thread-safe and must be wrapped with + * Collections.synchronizedMap to be made thread-safe. Most of the + * implementation for this class is ripped off from java.util.HashMap + * <p> + * Note: Softly referenced entries may be automatically removed during + * either accessor or mutator operations, possibly causing a concurrent + * modification to be detected. Therefore, even if multiple threads are only + * accessing this map, be sure to synchronize this map first. Also, do not + * rely on the value returned by size() when using an iterator from this map. + * The iterators may return less entries than the amount reported by size(). + * + * @author Brian S O'Neill + * @version + * <!--$$Revision: 1.1 $-->, <!--$$JustDate:--> 9/07/00 <!-- $--> + * @see Cache + */ +public class SoftHashMap extends AbstractMap implements Map, Cloneable { + /** + * Test program. + */ + /* + public static void main(String[] arg) throws Exception { + Map cache = new SoftHashMap(); + + for (int i = 0, j = 0; i < 100000; i++, j += 15) { + if (i % 100 == 0) { + System.out.println("Size = " + cache.size()); + } + + //Thread.sleep(1); + + Integer key = new Integer(i); + Integer value = new Integer(j); + + cache.put(key, value); + } + + Map.Entry entry = (Map.Entry)cache.entrySet().iterator().next(); + System.out.println(entry); + //entry = null; + + System.out.println(cache); + + int originalSize = cache.size(); + + //cache = null; + + for (int i=0; i<100; i++) { + System.gc(); + } + + System.out.println(cache); + + System.out.println(originalSize); + System.out.println(cache.size()); + System.out.println(entry); + + Thread.sleep(1000000); + } + */ + + /** + * The hash table data. + */ + private transient Entry mTable[]; + + /** + * The total number of mappings in the hash table. + */ + private transient int mCount; + + /** + * The table is rehashed when its size exceeds this threshold. (The + * value of this field is (int)(capacity * loadFactor).) + * + * @serial + */ + private int mThreshold; + + /** + * The load factor for the hashtable. + * + * @serial + */ + private float mLoadFactor; + + /** + * The number of times this HashMap has been structurally modified + * Structural modifications are those that change the number of mappings in + * the HashMap or otherwise modify its internal structure (e.g., + * rehash). This field is used to make iterators on Collection-views of + * the HashMap fail-fast. (See ConcurrentModificationException). + */ + private transient int mModCount = 0; + + // Views + + private transient Set mKeySet = null; + private transient Set mEntrySet = null; + private transient Collection mValues = null; + + /** + * Constructs a new, empty map with the specified initial + * capacity and the specified load factor. + * + * @param initialCapacity the initial capacity of the HashMap. + * @param loadFactor the load factor of the HashMap + * @throws IllegalArgumentException if the initial capacity is less + * than zero, or if the load factor is nonpositive. + */ + public SoftHashMap(int initialCapacity, float loadFactor) { + if (initialCapacity < 0) { + throw new IllegalArgumentException("Illegal Initial Capacity: "+ + initialCapacity); + } + + if (loadFactor <= 0 || Float.isNaN(loadFactor)) { + throw new IllegalArgumentException("Illegal Load factor: "+ + loadFactor); + } + + if (initialCapacity == 0) { + initialCapacity = 1; + } + + mLoadFactor = loadFactor; + mTable = new Entry[initialCapacity]; + mThreshold = (int)(initialCapacity * loadFactor); + } + + /** + * Constructs a new, empty map with the specified initial capacity + * and default load factor, which is <tt>0.75</tt>. + * + * @param initialCapacity the initial capacity of the HashMap. + * @throws IllegalArgumentException if the initial capacity is less + * than zero. + */ + public SoftHashMap(int initialCapacity) { + this(initialCapacity, 0.75f); + } + + /** + * Constructs a new, empty map with a default capacity and load + * factor, which is <tt>0.75</tt>. + */ + public SoftHashMap() { + this(11, 0.75f); + } + + /** + * Constructs a new map with the same mappings as the given map. The + * map is created with a capacity of twice the number of mappings in + * the given map or 11 (whichever is greater), and a default load factor, + * which is <tt>0.75</tt>. + */ + public SoftHashMap(Map t) { + this(Math.max(2 * t.size(), 11), 0.75f); + putAll(t); + } + + /** + * Returns the number of key-value mappings in this map, but this value + * may be larger than actual amount of entries produced by an iterator. + * + * @return the number of key-value mappings in this map. + */ + public int size() { + return mCount; + } + + /** + * Returns <tt>true</tt> if this map contains no key-value mappings. + * + * @return <tt>true</tt> if this map contains no key-value mappings. + */ + public boolean isEmpty() { + return mCount == 0; + } + + /** + * Returns <tt>true</tt> if this map maps one or more keys to the + * specified value. + * + * @param value value whose presence in this map is to be tested. + * @return <tt>true</tt> if this map maps one or more keys to the + * specified value. + */ + public boolean containsValue(Object value) { + if (value == null) { + value = new Null(); + } + + Entry tab[] = mTable; + + for (int i = tab.length ; i-- > 0 ;) { + for (Entry e = tab[i], prev = null; e != null; e = e.mNext) { + Object entryValue = e.getValue(); + + if (entryValue == null) { + // Clean up after a cleared Reference. + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[i] = e.mNext; + } + mCount--; + } + else if (value.equals(entryValue)) { + return true; + } + else { + prev = e; + } + } + } + + return false; + } + + /** + * Returns <tt>true</tt> if this map contains a mapping for the specified + * key. + * + * @return <tt>true</tt> if this map contains a mapping for the specified + * key. + * @param key key whose presence in this Map is to be tested. + */ + public boolean containsKey(Object key) { + Entry tab[] = mTable; + + if (key != null) { + int hash = key.hashCode(); + int index = (hash & 0x7FFFFFFF) % tab.length; + for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { + if (e.getValue() == null) { + // Clean up after a cleared Reference. + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[index] = e.mNext; + } + mCount--; + } + else if (e.mHash == hash && key.equals(e.mKey)) { + return true; + } + else { + prev = e; + } + } + } + else { + for (Entry e = tab[0], prev = null; e != null; e = e.mNext) { + if (e.getValue() == null) { + // Clean up after a cleared Reference. + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[0] = e.mNext; + } + mCount--; + } + else if (e.mKey == null) { + return true; + } + else { + prev = e; + } + } + } + + return false; + } + + /** + * Returns the value to which this map maps the specified key. Returns + * <tt>null</tt> if the map contains no mapping for this key. A return + * value of <tt>null</tt> does not <i>necessarily</i> indicate that the + * map contains no mapping for the key; it's also possible that the map + * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt> + * operation may be used to distinguish these two cases. + * + * @return the value to which this map maps the specified key. + * @param key key whose associated value is to be returned. + */ + public Object get(Object key) { + Entry tab[] = mTable; + + if (key != null) { + int hash = key.hashCode(); + int index = (hash & 0x7FFFFFFF) % tab.length; + + for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { + Object entryValue = e.getValue(); + + if (entryValue == null) { + // Clean up after a cleared Reference. + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[index] = e.mNext; + } + mCount--; + } + else if (e.mHash == hash && key.equals(e.mKey)) { + return (entryValue instanceof Null) ? null : entryValue; + } + else { + prev = e; + } + } + } + else { + for (Entry e = tab[0], prev = null; e != null; e = e.mNext) { + Object entryValue = e.getValue(); + + if (entryValue == null) { + // Clean up after a cleared Reference. + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[0] = e.mNext; + } + mCount--; + } + else if (e.mKey == null) { + return (entryValue instanceof Null) ? null : entryValue; + } + else { + prev = e; + } + } + } + + return null; + } + + /** + * Scans the contents of this map, removing all entries that have a + * cleared soft value. + */ + private void cleanup() { + Entry tab[] = mTable; + + for (int i = tab.length ; i-- > 0 ;) { + for (Entry e = tab[i], prev = null; e != null; e = e.mNext) { + if (e.getValue() == null) { + // Clean up after a cleared Reference. + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[i] = e.mNext; + } + mCount--; + } + else { + prev = e; + } + } + } + } + + /** + * Rehashes the contents of this map into a new <tt>HashMap</tt> instance + * with a larger capacity. This method is called automatically when the + * number of keys in this map exceeds its capacity and load factor. + */ + private void rehash() { + int oldCapacity = mTable.length; + Entry oldMap[] = mTable; + + int newCapacity = oldCapacity * 2 + 1; + Entry newMap[] = new Entry[newCapacity]; + + mModCount++; + mThreshold = (int)(newCapacity * mLoadFactor); + mTable = newMap; + + for (int i = oldCapacity ; i-- > 0 ;) { + for (Entry old = oldMap[i] ; old != null ; ) { + Entry e = old; + old = old.mNext; + + // Only copy entry if its value hasn't been cleared. + if (e.getValue() == null) { + mCount--; + } + else { + int index = (e.mHash & 0x7FFFFFFF) % newCapacity; + e.mNext = newMap[index]; + newMap[index] = e; + } + } + } + } + + /** + * Associates the specified value with the specified key in this map. + * If the map previously contained a mapping for this key, the old + * value is replaced. + * + * @param key key with which the specified value is to be associated. + * @param value value to be associated with the specified key. + * @return previous value associated with specified key, or <tt>null</tt> + * if there was no mapping for key. A <tt>null</tt> return can + * also indicate that the HashMap previously associated + * <tt>null</tt> with the specified key. + */ + public Object put(Object key, Object value) { + if (value == null) { + value = new Null(); + } + + // Makes sure the key is not already in the HashMap. + Entry tab[] = mTable; + int hash; + int index; + + if (key != null) { + hash = key.hashCode(); + index = (hash & 0x7FFFFFFF) % tab.length; + for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { + Object entryValue = e.getValue(); + + if (e.getValue() == null) { + // Clean up after a cleared Reference. + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[index] = e.mNext; + } + mCount--; + } + else if (e.mHash == hash && key.equals(e.mKey)) { + e.setValue(value); + return (entryValue instanceof Null) ? null : entryValue; + } + else { + prev = e; + } + } + } + else { + hash = 0; + index = 0; + for (Entry e = tab[0], prev = null; e != null; e = e.mNext) { + Object entryValue = e.getValue(); + + if (entryValue == null) { + // Clean up after a cleared Reference. + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[0] = e.mNext; + } + mCount--; + } + else if (e.mKey == null) { + e.setValue(value); + return (entryValue instanceof Null) ? null : entryValue; + } + else { + prev = e; + } + } + } + + mModCount++; + + if (mCount >= mThreshold) { + // Cleanup the table if the threshold is exceeded. + cleanup(); + } + + if (mCount >= mThreshold) { + // Rehash the table if the threshold is still exceeded. + rehash(); + tab = mTable; + index = (hash & 0x7FFFFFFF) % tab.length; + } + + // Creates the new entry. + Entry e = new Entry(hash, key, (Object)value, tab[index]); + tab[index] = e; + mCount++; + return null; + } + + /** + * Removes the mapping for this key from this map if present. + * + * @param key key whose mapping is to be removed from the map. + * @return previous value associated with specified key, or <tt>null</tt> + * if there was no mapping for key. A <tt>null</tt> return can + * also indicate that the map previously associated <tt>null</tt> + * with the specified key. + */ + public Object remove(Object key) { + Entry tab[] = mTable; + + if (key != null) { + int hash = key.hashCode(); + int index = (hash & 0x7FFFFFFF) % tab.length; + + for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { + Object entryValue = e.getValue(); + + if (entryValue == null) { + // Clean up after a cleared Reference. + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[index] = e.mNext; + } + mCount--; + } + else if (e.mHash == hash && key.equals(e.mKey)) { + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[index] = e.mNext; + } + mCount--; + + e.setValue(null); + return (entryValue instanceof Null) ? null : entryValue; + } + else { + prev = e; + } + } + } + else { + for (Entry e = tab[0], prev = null; e != null; e = e.mNext) { + Object entryValue = e.getValue(); + + if (entryValue == null) { + // Clean up after a cleared Reference. + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[0] = e.mNext; + } + mCount--; + } + else if (e.mKey == null) { + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[0] = e.mNext; + } + mCount--; + + e.setValue(null); + return (entryValue instanceof Null) ? null : entryValue; + } + else { + prev = e; + } + } + } + + return null; + } + + /** + * Copies all of the mappings from the specified map to this one. + * + * These mappings replace any mappings that this map had for any of the + * keys currently in the specified Map. + * + * @param t Mappings to be stored in this map. + */ + public void putAll(Map t) { + Iterator i = t.entrySet().iterator(); + while (i.hasNext()) { + Map.Entry e = (Map.Entry) i.next(); + put(e.getKey(), e.getValue()); + } + } + + /** + * Removes all mappings from this map. + */ + public void clear() { + Entry tab[] = mTable; + mModCount++; + for (int index = tab.length; --index >= 0; ) { + tab[index] = null; + } + mCount = 0; + } + + /** + * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and + * values themselves are not cloned. + * + * @return a shallow copy of this map. + */ + public Object clone() { + try { + SoftHashMap t = (SoftHashMap)super.clone(); + t.mTable = new Entry[mTable.length]; + for (int i = mTable.length ; i-- > 0 ; ) { + t.mTable[i] = (mTable[i] != null) + ? (Entry)mTable[i].clone() : null; + } + t.mKeySet = null; + t.mEntrySet = null; + t.mValues = null; + t.mModCount = 0; + return t; + } + catch (CloneNotSupportedException e) { + // this shouldn't happen, since we are Cloneable + throw new InternalError(); + } + } + + /** + * Returns a set view of the keys contained in this map. The set is + * backed by the map, so changes to the map are reflected in the set, and + * vice-versa. The set supports element removal, which removes the + * corresponding mapping from this map, via the <tt>Iterator.remove</tt>, + * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and + * <tt>clear</tt> operations. It does not support the <tt>add</tt> or + * <tt>addAll</tt> operations. + * + * @return a set view of the keys contained in this map. + */ + public Set keySet() { + if (mKeySet == null) { + mKeySet = new AbstractSet() { + public Iterator iterator() { + return getHashIterator(IdentityMap.KEYS); + } + public int size() { + return mCount; + } + public boolean contains(Object o) { + return containsKey(o); + } + public boolean remove(Object o) { + if (o == null) { + if (SoftHashMap.this.containsKey(null)) { + SoftHashMap.this.remove(null); + return true; + } + else { + return false; + } + } + else { + return SoftHashMap.this.remove(o) != null; + } + } + public void clear() { + SoftHashMap.this.clear(); + } + public String toString() { + return IdentityMap.toString(this); + } + }; + } + return mKeySet; + } + + /** + * Returns a collection view of the values contained in this map. The + * collection is backed by the map, so changes to the map are reflected in + * the collection, and vice-versa. The collection supports element + * removal, which removes the corresponding mapping from this map, via the + * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, + * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. + * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. + * + * @return a collection view of the values contained in this map. + */ + public Collection values() { + if (mValues==null) { + mValues = new AbstractCollection() { + public Iterator iterator() { + return getHashIterator(IdentityMap.VALUES); + } + public int size() { + return mCount; + } + public boolean contains(Object o) { + return containsValue(o); + } + public void clear() { + SoftHashMap.this.clear(); + } + public String toString() { + return IdentityMap.toString(this); + } + }; + } + return mValues; + } + + /** + * Returns a collection view of the mappings contained in this map. Each + * element in the returned collection is a <tt>Map.Entry</tt>. The + * collection is backed by the map, so changes to the map are reflected in + * the collection, and vice-versa. The collection supports element + * removal, which removes the corresponding mapping from the map, via the + * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, + * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. + * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. + * + * @return a collection view of the mappings contained in this map. + * @see Map.Entry + */ + public Set entrySet() { + if (mEntrySet==null) { + mEntrySet = new AbstractSet() { + public Iterator iterator() { + return getHashIterator(IdentityMap.ENTRIES); + } + + public boolean contains(Object o) { + if (!(o instanceof Map.Entry)) { + return false; + } + Map.Entry entry = (Map.Entry)o; + Object key = entry.getKey(); + + Entry tab[] = mTable; + int hash = key == null ? 0 : key.hashCode(); + int index = (hash & 0x7FFFFFFF) % tab.length; + + for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { + Object entryValue = e.getValue(); + + if (entryValue == null) { + // Clean up after a cleared Reference. + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[index] = e.mNext; + } + mCount--; + } + else if (e.mHash == hash && e.equals(entry)) { + return true; + } + else { + prev = e; + } + } + + return false; + } + + public boolean remove(Object o) { + if (!(o instanceof Map.Entry)) { + return false; + } + Map.Entry entry = (Map.Entry)o; + Object key = entry.getKey(); + Entry tab[] = mTable; + int hash = key == null ? 0 : key.hashCode(); + int index = (hash & 0x7FFFFFFF) % tab.length; + + for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { + Object entryValue = e.getValue(); + + if (entryValue == null) { + // Clean up after a cleared Reference. + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[index] = e.mNext; + } + mCount--; + } + else if (e.mHash == hash && e.equals(entry)) { + mModCount++; + if (prev != null) { + prev.mNext = e.mNext; + } + else { + tab[index] = e.mNext; + } + mCount--; + + e.setValue(null); + return true; + } + else { + prev = e; + } + } + return false; + } + + public int size() { + return mCount; + } + + public void clear() { + SoftHashMap.this.clear(); + } + + public String toString() { + return IdentityMap.toString(this); + } + }; + } + + return mEntrySet; + } + + public String toString() { + StringBuffer buf = new StringBuffer(); + Iterator it = entrySet().iterator(); + + buf.append("{"); + for (int i = 0; it.hasNext(); i++) { + if (i > 0) { + buf.append(", "); + } + Map.Entry e = (Map.Entry)it.next(); + buf.append(e.getKey() + "=" + e.getValue()); + } + buf.append("}"); + return buf.toString(); + } + + private Iterator getHashIterator(int type) { + if (mCount == 0) { + return IdentityMap.cEmptyHashIterator; + } + else { + return new HashIterator(type); + } + } + + /** + * HashMap collision list entry. + */ + private static class Entry implements Map.Entry { + int mHash; + Object mKey; + Entry mNext; + + private Reference mValue; + + Entry(int hash, Object key, Object value, Entry next) { + mHash = hash; + mKey = key; + mValue = new SoftReference(value); + mNext = next; + } + + private Entry(int hash, Object key, Reference value, Entry next) { + mHash = hash; + mKey = key; + mValue = value; + mNext = next; + } + + protected Object clone() { + return new Entry(mHash, mKey, (Reference)mValue, + (mNext==null ? null : (Entry)mNext.clone())); + } + + // Map.Entry Ops + + public Object getKey() { + return mKey; + } + + public Object getValue() { + return mValue.get(); + } + + public Object setValue(Object value) { + Object oldValue = getValue(); + if (value == null) { + mValue.clear(); + } + else { + mValue = new SoftReference(value); + } + return oldValue; + } + + public boolean equals(Object o) { + if (!(o instanceof Map.Entry)) { + return false; + } + Map.Entry e = (Map.Entry)o; + + Object value = getValue(); + + return (mKey==null ? e.getKey()==null : mKey.equals(e.getKey())) && + (value==null ? e.getValue()==null : value.equals(e.getValue())); + } + + public int hashCode() { + Object value = getValue(); + return mHash ^ (value==null ? 0 : value.hashCode()); + } + + public String toString() { + return mKey + "=" + getValue(); + } + } + + private class HashIterator implements Iterator { + private Entry[] mTable = SoftHashMap.this.mTable; + private int mIndex = mTable.length; + private Entry mEntry; + // To ensure that the iterator doesn't return cleared entries, keep a + // hard reference to the value. Its existence will prevent the soft + // value from being cleared. + private Object mEntryValue; + private Entry mLastReturned; + private int mType; + + /** + * The modCount value that the iterator believes that the backing + * List should have. If this expectation is violated, the iterator + * has detected concurrent modification. + */ + private int expectedModCount = mModCount; + + HashIterator(int type) { + mType = type; + } + + public boolean hasNext() { + while (mEntry == null || + (mEntryValue = mEntry.getValue()) == null) { + if (mEntry != null) { + // Clean up after a cleared Reference. + remove(mEntry); + mEntry = mEntry.mNext; + } + + if (mEntry == null) { + if (mIndex <= 0) { + return false; + } + else { + mEntry = mTable[--mIndex]; + } + } + } + + return true; + } + + public Object next() { + if (mModCount != expectedModCount) { + throw new ConcurrentModificationException(); + } + + if (!hasNext()) { + throw new NoSuchElementException(); + } + + mLastReturned = mEntry; + mEntry = mEntry.mNext; + + if (mType == IdentityMap.KEYS) { + return mLastReturned.getKey(); + } + else if (mType == IdentityMap.VALUES) { + Object value = mLastReturned.getValue(); + return (value instanceof Null) ? null : value; + } + else { + return mLastReturned; + } + } + + public void remove() { + if (mLastReturned == null) { + throw new IllegalStateException(); + } + if (mModCount != expectedModCount) { + throw new ConcurrentModificationException(); + } + remove(mLastReturned); + mLastReturned = null; + } + + private void remove(Entry toRemove) { + Entry[] tab = mTable; + int index = (toRemove.mHash & 0x7FFFFFFF) % tab.length; + + for (Entry e = tab[index], prev = null; e != null; e = e.mNext) { + if (e == toRemove) { + mModCount++; + expectedModCount++; + if (prev == null) { + tab[index] = e.mNext; + } + else { + prev.mNext = e.mNext; + } + mCount--; + return; + } + else { + prev = e; + } + } + throw new ConcurrentModificationException(); + } + } + + /** + * This allows null references to be saved into SoftHashMap and allow + * entries to still be garbage collected. + */ + static class Null { + public boolean equals(Object other) { + return other == null || other instanceof Null; + } + + public String toString() { + return "null"; + } + } +}