/* * Copyright 2001-2004 The Apache Software Foundation * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package org.apache.qpid.collections; 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.qpid.collections.keyvalue.DefaultMapEntry; /** * Hash-based {@link Map} implementation that allows * mappings to be removed by the garbage collector.
*
* When you construct a ReferenceMap
, 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}.
*
* 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
* WeakHashMap
. 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.
* * 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.
*
* However, this {@link Map} implementation does not
* allow null elements. Attempting to add a null key or
* or a null value to the map will raise a
* NullPointerException
.
*
* As usual, this implementation is not synchronized. You
* can use {@link java.util.Collections#synchronizedMap} to
* provide synchronized access to a ReferenceMap
.
*
* @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$
*
* @author Paul Jack
*/
public class ReferenceMap extends AbstractMap {
/**
* For serialization.
*/
private static final long serialVersionUID = -3370601314380922368L;
/**
* Constant indicating that hard references should be used.
*/
final public static int HARD = 0;
/**
* Constant indicating that soft references should be used.
*/
final public static int SOFT = 1;
/**
* Constant indicating that weak references should be used.
*/
final public static 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 ReferenceMap
that will
* use hard references to keys and soft references to values.
*/
public ReferenceMap() {
this(HARD, SOFT);
}
/**
* Constructs a new ReferenceMap
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 ReferenceMap
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 ReferenceMap
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 ReferenceMap
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 key 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.
*
* 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. *
* 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 true
if this map is empty.
*
* @return true
if this map is empty
*/
public boolean isEmpty() {
purge();
return size == 0;
}
/**
* Returns true
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 null
* 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.
* 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 ReferenceMap.this.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(); } public Object[] toArray() { return toArray(new Object[0]); } public Object[] toArray(Object[] array) { Collection c = new ArrayList(size()); for (Iterator it = iterator(); it.hasNext(); ) { c.add(it.next()); } return c.toArray(array); } }; 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 ReferenceMap.this.size(); } public void clear() { ReferenceMap.this.clear(); } public Iterator iterator() { return new ValueIterator(); } public Object[] toArray() { return toArray(new Object[0]); } public Object[] toArray(Object[] array) { Collection c = new ArrayList(size()); for (Iterator it = iterator(); it.hasNext(); ) { c.add(it.next()); } return c.toArray(array); } }; return values; } // If getKey() or getValue() returns null, it means // the mapping is stale and should be removed. private class Entry implements Map.Entry, KeyValue { 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; } } }