scolebourne 2003/12/03 07:50:12 Modified: collections/src/test/org/apache/commons/collections/map TestAll.java collections/src/java/org/apache/commons/collections ReferenceMap.java collections/src/java/org/apache/commons/collections/map package.html Added: collections/src/test/org/apache/commons/collections/map TestReferenceMap.java collections/src/java/org/apache/commons/collections/map ReferenceMap.java Log: Refactor ReferenceMap to map subpackage Revision Changes Path 1.8 +3 -2 jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestAll.java Index: TestAll.java =================================================================== RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestAll.java,v retrieving revision 1.7 retrieving revision 1.8 diff -u -r1.7 -r1.8 --- TestAll.java 3 Dec 2003 15:16:49 -0000 1.7 +++ TestAll.java 3 Dec 2003 15:50:12 -0000 1.8 @@ -86,6 +86,7 @@ suite.addTest(TestFlat3Map.suite()); suite.addTest(TestHashedMap.suite()); suite.addTest(TestIdentityMap.suite()); + suite.addTest(TestReferenceMap.suite()); suite.addTest(TestStaticBucketMap.suite()); suite.addTest(TestFixedSizeMap.suite()); 1.1 jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestReferenceMap.java Index: TestReferenceMap.java =================================================================== /* * $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/map/TestReferenceMap.java,v 1.1 2003/12/03 15:50:12 scolebourne Exp $ * ==================================================================== * * The Apache Software License, Version 1.1 * * Copyright (c) 2001-2003 The Apache Software Foundation. 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 acknowledgement: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgement may appear in the software itself, * if and wherever such third-party acknowledgements normally appear. * * 4. The names "The Jakarta Project", "Commons", and "Apache Software * Foundation" must not be used to endorse or promote products derived * from this software without prior written permission. For written * permission, please contact [EMAIL PROTECTED] * * 5. Products derived from this software may not be called "Apache" * nor may "Apache" appear in their names without prior written * permission of the Apache Software Foundation. * * 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 APACHE SOFTWARE FOUNDATION 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. * ==================================================================== * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. * */ package org.apache.commons.collections.map; import java.lang.ref.WeakReference; import java.util.Map; import junit.framework.Test; import org.apache.commons.collections.BulkTest; /** * Tests for ReferenceMap. * * @version $Revision: 1.1 $ $Date: 2003/12/03 15:50:12 $ * * @author Paul Jack */ public class TestReferenceMap extends AbstractTestMap { public TestReferenceMap(String testName) { super(testName); } public static Test suite() { return BulkTest.makeSuite(TestReferenceMap.class); } public static void main(String args[]) { String[] testCaseName = { TestReferenceMap.class.getName() }; junit.textui.TestRunner.main(testCaseName); } public Map makeEmptyMap() { ReferenceMap map = new ReferenceMap(ReferenceMap.WEAK, ReferenceMap.WEAK); return map; } public boolean isAllowNullKey() { return false; } public boolean isAllowNullValue() { return false; } /* // Unfortunately, these tests all rely on System.gc(), which is // not reliable across platforms. Not sure how to code the tests // without using System.gc() though... // They all passed on my platform though. :) public void testPurge() { ReferenceMap map = new ReferenceMap(ReferenceMap.WEAK, ReferenceMap.WEAK); Object[] hard = new Object[10]; for (int i = 0; i < hard.length; i++) { hard[i] = new Object(); map.put(hard[i], new Object()); } System.gc(); assertTrue("map should be empty after purge of weak values", map.isEmpty()); for (int i = 0; i < hard.length; i++) { map.put(new Object(), hard[i]); } System.gc(); assertTrue("map should be empty after purge of weak keys", map.isEmpty()); for (int i = 0; i < hard.length; i++) { map.put(new Object(), hard[i]); map.put(hard[i], new Object()); } System.gc(); assertTrue("map should be empty after purge of weak keys and values", map.isEmpty()); } public void testGetAfterGC() { ReferenceMap map = new ReferenceMap(ReferenceMap.WEAK, ReferenceMap.WEAK); for (int i = 0; i < 10; i++) { map.put(new Integer(i), new Integer(i)); } System.gc(); for (int i = 0; i < 10; i++) { Integer I = new Integer(i); assertTrue("map.containsKey should return false for GC'd element", !map.containsKey(I)); assertTrue("map.get should return null for GC'd element", map.get(I) == null); } } public void testEntrySetIteratorAfterGC() { ReferenceMap map = new ReferenceMap(ReferenceMap.WEAK, ReferenceMap.WEAK); Object[] hard = new Object[10]; for (int i = 0; i < 10; i++) { hard[i] = new Integer(10 + i); map.put(new Integer(i), new Integer(i)); map.put(hard[i], hard[i]); } System.gc(); Iterator iterator = map.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry entry = (Map.Entry)iterator.next(); Integer key = (Integer)entry.getKey(); Integer value = (Integer)entry.getValue(); assertTrue("iterator should skip GC'd keys", key.intValue() >= 10); assertTrue("iterator should skip GC'd values", value.intValue() >= 10); } } */ /* // Uncomment to create test files in /data/test public void testCreateTestFiles() throws Exception { ReferenceMap m = (ReferenceMap)makeEmptyMap(); writeExternalFormToDisk(m, getCanonicalEmptyCollectionName(m)); m = (ReferenceMap)makeFullMap(); writeExternalFormToDisk(m, getCanonicalFullCollectionName(m)); } */ public String getCompatibilityVersion() { return "2.1"; // previously in main package } /** Tests whether purge values setting works */ public void testPurgeValues() throws Exception { // many thanks to Juozas Baliuka for suggesting this method Object key = new Object(); Object value = new Object(); WeakReference keyReference = new WeakReference(key); WeakReference valueReference = new WeakReference(value); Map testMap = new ReferenceMap(ReferenceMap.WEAK, ReferenceMap.HARD, true); testMap.put(key, value); assertEquals("In map", value, testMap.get(key)); assertNotNull("Weak reference released early (1)", keyReference.get()); assertNotNull("Weak reference released early (2)", valueReference.get()); // dereference strong references key = null; value = null; int iterations = 0; int bytz = 2; while(true) { System.gc(); if(iterations++ > 50){ fail("Max iterations reached before resource released."); } testMap.isEmpty(); if( keyReference.get() == null && valueReference.get() == null) { break; } else { // create garbage: byte[] b = new byte[bytz]; bytz = bytz * 2; } } } } 1.17 +4 -3 jakarta-commons/collections/src/java/org/apache/commons/collections/ReferenceMap.java Index: ReferenceMap.java =================================================================== RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/ReferenceMap.java,v retrieving revision 1.16 retrieving revision 1.17 diff -u -r1.16 -r1.17 --- ReferenceMap.java 9 Oct 2003 20:58:52 -0000 1.16 +++ ReferenceMap.java 3 Dec 2003 15:50:12 -0000 1.17 @@ -79,7 +79,7 @@ import org.apache.commons.collections.pairs.DefaultMapEntry; /** - * Hashtable-based [EMAIL PROTECTED] Map} implementation that allows + * Hash-based [EMAIL PROTECTED] Map} implementation that allows * mappings to be removed by the garbage collector.<p> * * When you construct a <code>ReferenceMap</code>, you can @@ -117,6 +117,7 @@ * * @see java.lang.ref.Reference * + * @deprecated Moved to map subpackage. Due to be removed in v4.0. * @since Commons Collections 2.1 * @version $Revision$ $Date$ * 1.4 +1 -0 jakarta-commons/collections/src/java/org/apache/commons/collections/map/package.html Index: package.html =================================================================== RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/map/package.html,v retrieving revision 1.3 retrieving revision 1.4 diff -u -r1.3 -r1.4 --- package.html 3 Dec 2003 15:16:49 -0000 1.3 +++ package.html 3 Dec 2003 15:50:12 -0000 1.4 @@ -8,6 +8,7 @@ <li>HashedMap - general purpose HashMap replacement supporting MapIterator <li>IdentityMap - Map that uses == for comparison instead of equals() <li>Flat3Map - designed for good performance at size 3 or less +<li>ReferenceMap - allows the garbage collector to collect keys and values <li>StaticBucketMap - internally synchronized and designed for thread-contentious environments </ul> <p> 1.1 jakarta-commons/collections/src/java/org/apache/commons/collections/map/ReferenceMap.java Index: ReferenceMap.java =================================================================== /* * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/map/ReferenceMap.java,v 1.1 2003/12/03 15:50:12 scolebourne Exp $ * ==================================================================== * * The Apache Software License, Version 1.1 * * Copyright (c) 2001-2003 The Apache Software Foundation. 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 acknowledgement: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgement may appear in the software itself, * if and wherever such third-party acknowledgements normally appear. * * 4. The names "The Jakarta Project", "Commons", and "Apache Software * Foundation" must not be used to endorse or promote products derived * from this software without prior written permission. For written * permission, please contact [EMAIL PROTECTED] * * 5. Products derived from this software may not be called "Apache" * nor may "Apache" appear in their names without prior written * permission of the Apache Software Foundation. * * 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 APACHE SOFTWARE FOUNDATION 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. * ==================================================================== * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. * */ package org.apache.commons.collections.map; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.lang.ref.Reference; import java.lang.ref.ReferenceQueue; import java.lang.ref.SoftReference; import java.lang.ref.WeakReference; import java.util.AbstractCollection; import java.util.AbstractMap; import java.util.AbstractSet; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; import org.apache.commons.collections.pairs.DefaultMapEntry; /** * Hash-based [EMAIL PROTECTED] Map} implementation that allows * mappings to be removed by the garbage collector.<p> * * When you construct a <code>ReferenceMap</code>, you can * specify what kind of references are used to store the * map's keys and values. If non-hard references are * used, then the garbage collector can remove mappings * if a key or value becomes unreachable, or if the * JVM's memory is running low. For information on how * the different reference types behave, see * [EMAIL PROTECTED] Reference}.<p> * * Different types of references can be specified for keys * and values. The keys can be configured to be weak but * the values hard, in which case this class will behave * like a <a href="http://java.sun.com/j2se/1.4/docs/api/java/util/WeakHashMap.html"> * <code>WeakHashMap</code></a>. However, you * can also specify hard keys and weak values, or any other * combination. The default constructor uses hard keys * and soft values, providing a memory-sensitive cache.<p> * * The algorithms used are basically the same as those * in [EMAIL PROTECTED] java.util.HashMap}. In particular, you * can specify a load factor and capacity to suit your * needs. All optional [EMAIL PROTECTED] Map} operations are * supported.<p> * * However, this [EMAIL PROTECTED] Map} implementation does <I>not</I> * allow null elements. Attempting to add a null key or * or a null value to the map will raise a * <code>NullPointerException</code>.<p> * * As usual, this implementation is not synchronized. You * can use [EMAIL PROTECTED] java.util.Collections#synchronizedMap} to * provide synchronized access to a <code>ReferenceMap</code>. * * @see java.lang.ref.Reference * * @since Commons Collections 3.0 * @version $Revision: 1.1 $ $Date: 2003/12/03 15:50:12 $ * * @author Paul Jack */ public class ReferenceMap extends AbstractMap { /** * For serialization. */ private static final long serialVersionUID = -3370601314380922368L; /** * Constant indicating that hard references should be used. */ public static final int HARD = 0; /** * Constant indicating that soft references should be used. */ public static final int SOFT = 1; /** * Constant indicating that weak references should be used. */ public static final int WEAK = 2; // --- serialized instance variables: /** * The reference type for keys. Must be HARD, SOFT, WEAK. * Note: I originally marked this field as final, but then this class * didn't compile under JDK1.2.2. * @serial */ private int keyType; /** * The reference type for values. Must be HARD, SOFT, WEAK. * Note: I originally marked this field as final, but then this class * didn't compile under JDK1.2.2. * @serial */ private int valueType; /** * The threshold variable is calculated by multiplying * table.length and loadFactor. * Note: I originally marked this field as final, but then this class * didn't compile under JDK1.2.2. * @serial */ private float loadFactor; /** * Should the value be automatically purged when the associated key has been collected? */ private boolean purgeValues = false; // -- Non-serialized instance variables /** * ReferenceQueue used to eliminate stale mappings. * See purge. */ private transient ReferenceQueue queue = new ReferenceQueue(); /** * The hash table. Its length is always a power of two. */ private transient Entry[] table; /** * Number of mappings in this map. */ private transient int size; /** * When size reaches threshold, the map is resized. * See resize(). */ private transient int threshold; /** * Number of times this map has been modified. */ private transient volatile int modCount; /** * Cached key set. May be null if key set is never accessed. */ private transient Set keySet; /** * Cached entry set. May be null if entry set is never accessed. */ private transient Set entrySet; /** * Cached values. May be null if values() is never accessed. */ private transient Collection values; /** * Constructs a new <code>ReferenceMap</code> that will * use hard references to keys and soft references to values. */ public ReferenceMap() { this(HARD, SOFT); } /** * Constructs a new <code>ReferenceMap</code> that will * use the specified types of references. * * @param keyType the type of reference to use for keys; * must be [EMAIL PROTECTED] #HARD}, [EMAIL PROTECTED] #SOFT}, [EMAIL PROTECTED] #WEAK} * @param valueType the type of reference to use for values; * must be [EMAIL PROTECTED] #HARD}, [EMAIL PROTECTED] #SOFT}, [EMAIL PROTECTED] #WEAK} * @param purgeValues should the value be automatically purged when the * key is garbage collected */ public ReferenceMap(int keyType, int valueType, boolean purgeValues) { this(keyType, valueType); this.purgeValues = purgeValues; } /** * Constructs a new <code>ReferenceMap</code> that will * use the specified types of references. * * @param keyType the type of reference to use for keys; * must be [EMAIL PROTECTED] #HARD}, [EMAIL PROTECTED] #SOFT}, [EMAIL PROTECTED] #WEAK} * @param valueType the type of reference to use for values; * must be [EMAIL PROTECTED] #HARD}, [EMAIL PROTECTED] #SOFT}, [EMAIL PROTECTED] #WEAK} */ public ReferenceMap(int keyType, int valueType) { this(keyType, valueType, 16, 0.75f); } /** * Constructs a new <code>ReferenceMap</code> with the * specified reference types, load factor and initial * capacity. * * @param keyType the type of reference to use for keys; * must be [EMAIL PROTECTED] #HARD}, [EMAIL PROTECTED] #SOFT}, [EMAIL PROTECTED] #WEAK} * @param valueType the type of reference to use for values; * must be [EMAIL PROTECTED] #HARD}, [EMAIL PROTECTED] #SOFT}, [EMAIL PROTECTED] #WEAK} * @param capacity the initial capacity for the map * @param loadFactor the load factor for the map * @param purgeValues should the value be automatically purged when the * key is garbage collected */ public ReferenceMap( int keyType, int valueType, int capacity, float loadFactor, boolean purgeValues) { this(keyType, valueType, capacity, loadFactor); this.purgeValues = purgeValues; } /** * Constructs a new <code>ReferenceMap</code> with the * specified reference types, load factor and initial * capacity. * * @param keyType the type of reference to use for keys; * must be [EMAIL PROTECTED] #HARD}, [EMAIL PROTECTED] #SOFT}, [EMAIL PROTECTED] #WEAK} * @param valueType the type of reference to use for values; * must be [EMAIL PROTECTED] #HARD}, [EMAIL PROTECTED] #SOFT}, [EMAIL PROTECTED] #WEAK} * @param capacity the initial capacity for the map * @param loadFactor the load factor for the map */ public ReferenceMap(int keyType, int valueType, int capacity, float loadFactor) { super(); verify("keyType", keyType); verify("valueType", valueType); if (capacity <= 0) { throw new IllegalArgumentException("capacity must be positive"); } if ((loadFactor <= 0.0f) || (loadFactor >= 1.0f)) { throw new IllegalArgumentException("Load factor must be greater than 0 and less than 1."); } this.keyType = keyType; this.valueType = valueType; int v = 1; while (v < capacity) v *= 2; this.table = new Entry[v]; this.loadFactor = loadFactor; this.threshold = (int)(v * loadFactor); } // used by constructor private static void verify(String name, int type) { if ((type < HARD) || (type > WEAK)) { throw new IllegalArgumentException(name + " must be HARD, SOFT, WEAK."); } } /** * Writes this object to the given output stream. * * @param out the output stream to write to * @throws IOException if the stream raises it */ private void writeObject(ObjectOutputStream out) throws IOException { out.defaultWriteObject(); out.writeInt(table.length); // Have to use null-terminated list because size might shrink // during iteration for (Iterator iter = entrySet().iterator(); iter.hasNext();) { Map.Entry entry = (Map.Entry)iter.next(); out.writeObject(entry.getKey()); out.writeObject(entry.getValue()); } out.writeObject(null); } /** * Reads the contents of this object from the given input stream. * * @param inp the input stream to read from * @throws IOException if the stream raises it * @throws ClassNotFoundException if the stream raises it */ private void readObject(ObjectInputStream inp) throws IOException, ClassNotFoundException { inp.defaultReadObject(); table = new Entry[inp.readInt()]; threshold = (int)(table.length * loadFactor); queue = new ReferenceQueue(); Object key = inp.readObject(); while (key != null) { Object value = inp.readObject(); put(key, value); key = inp.readObject(); } } /** * Constructs a reference of the given type to the given * referent. The reference is registered with the queue * for later purging. * * @param type HARD, SOFT or WEAK * @param referent the object to refer to * @param hash the hash code of the <I>key</I> of the mapping; * this number might be different from referent.hashCode() if * the referent represents a value and not a key */ private Object toReference(int type, Object referent, int hash) { switch (type) { case HARD: return referent; case SOFT: return new SoftRef(hash, referent, queue); case WEAK: return new WeakRef(hash, referent, queue); default: throw new Error(); } } /** * Returns the entry associated with the given key. * * @param key the key of the entry to look up * @return the entry associated with that key, or null * if the key is not in this map */ private Entry getEntry(Object key) { if (key == null) return null; int hash = key.hashCode(); int index = indexFor(hash); for (Entry entry = table[index]; entry != null; entry = entry.next) { if ((entry.hash == hash) && key.equals(entry.getKey())) { return entry; } } return null; } /** * Converts the given hash code into an index into the * hash table. */ private int indexFor(int hash) { // mix the bits to avoid bucket collisions... hash += ~(hash << 15); hash ^= (hash >>> 10); hash += (hash << 3); hash ^= (hash >>> 6); hash += ~(hash << 11); hash ^= (hash >>> 16); return hash & (table.length - 1); } /** * Resizes this hash table by doubling its capacity. * This is an expensive operation, as entries must * be copied from the old smaller table to the new * bigger table. */ private void resize() { Entry[] old = table; table = new Entry[old.length * 2]; for (int i = 0; i < old.length; i++) { Entry next = old[i]; while (next != null) { Entry entry = next; next = next.next; int index = indexFor(entry.hash); entry.next = table[index]; table[index] = entry; } old[i] = null; } threshold = (int)(table.length * loadFactor); } /** * Purges stale mappings from this map. * <p> * Ordinarily, stale mappings are only removed during * a write operation, although this method is called for both * read and write operations to maintain a consistent state. * <p> * Note that this method is not synchronized! Special * care must be taken if, for instance, you want stale * mappings to be removed on a periodic basis by some * background thread. */ private void purge() { Reference ref = queue.poll(); while (ref != null) { purge(ref); ref = queue.poll(); } } private void purge(Reference ref) { // The hashCode of the reference is the hashCode of the // mapping key, even if the reference refers to the // mapping value... int hash = ref.hashCode(); int index = indexFor(hash); Entry previous = null; Entry entry = table[index]; while (entry != null) { if (entry.purge(ref)) { if (previous == null) table[index] = entry.next; else previous.next = entry.next; this.size--; return; } previous = entry; entry = entry.next; } } /** * Returns the size of this map. * * @return the size of this map */ public int size() { purge(); return size; } /** * Returns <code>true</code> if this map is empty. * * @return <code>true</code> if this map is empty */ public boolean isEmpty() { purge(); return size == 0; } /** * Returns <code>true</code> if this map contains the given key. * * @return true if the given key is in this map */ public boolean containsKey(Object key) { purge(); Entry entry = getEntry(key); if (entry == null) return false; return entry.getValue() != null; } /** * Returns the value associated with the given key, if any. * * @return the value associated with the given key, or <code>null</code> * if the key maps to no value */ public Object get(Object key) { purge(); Entry entry = getEntry(key); if (entry == null) return null; return entry.getValue(); } /** * Associates the given key with the given value.<p> * Neither the key nor the value may be null. * * @param key the key of the mapping * @param value the value of the mapping * @return the last value associated with that key, or * null if no value was associated with the key * @throws NullPointerException if either the key or value * is null */ public Object put(Object key, Object value) { if (key == null) throw new NullPointerException("null keys not allowed"); if (value == null) throw new NullPointerException("null values not allowed"); purge(); if (size + 1 > threshold) resize(); int hash = key.hashCode(); int index = indexFor(hash); Entry entry = table[index]; while (entry != null) { if ((hash == entry.hash) && key.equals(entry.getKey())) { Object result = entry.getValue(); entry.setValue(value); return result; } entry = entry.next; } this.size++; modCount++; key = toReference(keyType, key, hash); value = toReference(valueType, value, hash); table[index] = new Entry(key, hash, value, table[index]); return null; } /** * Removes the key and its associated value from this map. * * @param key the key to remove * @return the value associated with that key, or null if * the key was not in the map */ public Object remove(Object key) { if (key == null) return null; purge(); int hash = key.hashCode(); int index = indexFor(hash); Entry previous = null; Entry entry = table[index]; while (entry != null) { if ((hash == entry.hash) && key.equals(entry.getKey())) { if (previous == null) table[index] = entry.next; else previous.next = entry.next; this.size--; modCount++; return entry.getValue(); } previous = entry; entry = entry.next; } return null; } /** * Clears this map. */ public void clear() { Arrays.fill(table, null); size = 0; while (queue.poll() != null); // drain the queue } /** * Returns a set view of this map's entries. * * @return a set view of this map's entries */ public Set entrySet() { if (entrySet != null) { return entrySet; } entrySet = new AbstractSet() { public int size() { return ReferenceMap.this.size(); } public void clear() { ReferenceMap.this.clear(); } public boolean contains(Object o) { if (o == null) return false; if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Entry e2 = getEntry(e.getKey()); return (e2 != null) && e.equals(e2); } public boolean remove(Object o) { boolean r = contains(o); if (r) { Map.Entry e = (Map.Entry)o; ReferenceMap.this.remove(e.getKey()); } return r; } public Iterator iterator() { return new EntryIterator(); } public Object[] toArray() { return toArray(new Object[0]); } public Object[] toArray(Object[] arr) { ArrayList list = new ArrayList(); Iterator iterator = iterator(); while (iterator.hasNext()) { Entry e = (Entry)iterator.next(); list.add(new DefaultMapEntry(e.getKey(), e.getValue())); } return list.toArray(arr); } }; return entrySet; } /** * Returns a set view of this map's keys. * * @return a set view of this map's keys */ public Set keySet() { if (keySet != null) return keySet; keySet = new AbstractSet() { public int size() { return size; } public Iterator iterator() { return new KeyIterator(); } public boolean contains(Object o) { return containsKey(o); } public boolean remove(Object o) { Object r = ReferenceMap.this.remove(o); return r != null; } public void clear() { ReferenceMap.this.clear(); } }; return keySet; } /** * Returns a collection view of this map's values. * * @return a collection view of this map's values. */ public Collection values() { if (values != null) return values; values = new AbstractCollection() { public int size() { return size; } public void clear() { ReferenceMap.this.clear(); } public Iterator iterator() { return new ValueIterator(); } }; return values; } // If getKey() or getValue() returns null, it means // the mapping is stale and should be removed. private class Entry implements Map.Entry { Object key; Object value; int hash; Entry next; public Entry(Object key, int hash, Object value, Entry next) { this.key = key; this.hash = hash; this.value = value; this.next = next; } public Object getKey() { return (keyType > HARD) ? ((Reference)key).get() : key; } public Object getValue() { return (valueType > HARD) ? ((Reference)value).get() : value; } public Object setValue(Object object) { Object old = getValue(); if (valueType > HARD) ((Reference)value).clear(); value = toReference(valueType, object, hash); return old; } public boolean equals(Object o) { if (o == null) return false; if (o == this) return true; if (!(o instanceof Map.Entry)) return false; Map.Entry entry = (Map.Entry)o; Object key = entry.getKey(); Object value = entry.getValue(); if ((key == null) || (value == null)) return false; return key.equals(getKey()) && value.equals(getValue()); } public int hashCode() { Object v = getValue(); return hash ^ ((v == null) ? 0 : v.hashCode()); } public String toString() { return getKey() + "=" + getValue(); } boolean purge(Reference ref) { boolean r = (keyType > HARD) && (key == ref); r = r || ((valueType > HARD) && (value == ref)); if (r) { if (keyType > HARD) ((Reference)key).clear(); if (valueType > HARD) { ((Reference)value).clear(); } else if (purgeValues) { value = null; } } return r; } } private class EntryIterator implements Iterator { // These fields keep track of where we are in the table. int index; Entry entry; Entry previous; // These Object fields provide hard references to the // current and next entry; this assures that if hasNext() // returns true, next() will actually return a valid element. Object nextKey, nextValue; Object currentKey, currentValue; int expectedModCount; public EntryIterator() { index = (size() != 0 ? table.length : 0); // have to do this here! size() invocation above // may have altered the modCount. expectedModCount = modCount; } public boolean hasNext() { checkMod(); while (nextNull()) { Entry e = entry; int i = index; while ((e == null) && (i > 0)) { i--; e = table[i]; } entry = e; index = i; if (e == null) { currentKey = null; currentValue = null; return false; } nextKey = e.getKey(); nextValue = e.getValue(); if (nextNull()) entry = entry.next; } return true; } private void checkMod() { if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } private boolean nextNull() { return (nextKey == null) || (nextValue == null); } protected Entry nextEntry() { checkMod(); if (nextNull() && !hasNext()) throw new NoSuchElementException(); previous = entry; entry = entry.next; currentKey = nextKey; currentValue = nextValue; nextKey = null; nextValue = null; return previous; } public Object next() { return nextEntry(); } public void remove() { checkMod(); if (previous == null) throw new IllegalStateException(); ReferenceMap.this.remove(currentKey); previous = null; currentKey = null; currentValue = null; expectedModCount = modCount; } } private class ValueIterator extends EntryIterator { public Object next() { return nextEntry().getValue(); } } private class KeyIterator extends EntryIterator { public Object next() { return nextEntry().getKey(); } } // These two classes store the hashCode of the key of // of the mapping, so that after they're dequeued a quick // lookup of the bucket in the table can occur. private static class SoftRef extends SoftReference { private int hash; public SoftRef(int hash, Object r, ReferenceQueue q) { super(r, q); this.hash = hash; } public int hashCode() { return hash; } } private static class WeakRef extends WeakReference { private int hash; public WeakRef(int hash, Object r, ReferenceQueue q) { super(r, q); this.hash = hash; } public int hashCode() { return hash; } } }
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]