You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by sc...@apache.org on 2003/12/03 16:50:12 UTC
cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections/map ReferenceMap.java package.html
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 apache@apache.org.
*
* 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 {@link Map} implementation that allows
+ * Hash-based {@link 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 apache@apache.org.
*
* 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 {@link 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
* {@link 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 {@link java.util.HashMap}. In particular, you
* can specify a load factor and capacity to suit your
* needs. All optional {@link Map} operations are
* supported.<p>
*
* However, this {@link 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 {@link 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 {@link #HARD}, {@link #SOFT}, {@link #WEAK}
* @param valueType the type of reference to use for values;
* must be {@link #HARD}, {@link #SOFT}, {@link #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 {@link #HARD}, {@link #SOFT}, {@link #WEAK}
* @param valueType the type of reference to use for values;
* must be {@link #HARD}, {@link #SOFT}, {@link #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 {@link #HARD}, {@link #SOFT}, {@link #WEAK}
* @param valueType the type of reference to use for values;
* must be {@link #HARD}, {@link #SOFT}, {@link #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 {@link #HARD}, {@link #SOFT}, {@link #WEAK}
* @param valueType the type of reference to use for values;
* must be {@link #HARD}, {@link #SOFT}, {@link #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: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org