Java/Collections Data Structure/WeakHashMap
Содержание
- 1 A hashtable-based Map implementation with weak keys and using reference-equality in place of object-equality when comparing keys (and values).
- 2 A WeakValueHashMap is implemented as a HashMap that maps keys to Weak Values
- 3 Create a WeakHashMap with a single element in it
- 4 Implements a combination of WeakHashMap and IdentityHashMap
- 5 To enable automatically release of the value, the value must be wrapped in a WeakReference object
- 6 Weak Identity Map
- 7 Weak Valued HashMap
- 8 Weak Value HashMap
- 9 Weak ValueMap
A hashtable-based Map implementation with weak keys and using reference-equality in place of object-equality when comparing keys (and values).
<source lang="java">
/*
* JBoss, Home of Professional Open Source * Copyright 2005, JBoss Inc., and individual contributors as indicated * by the @authors tag. See the copyright.txt in the distribution for a * full listing of individual contributors. * * This is free software; you can redistribute it and/or modify it * under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * This software is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this software; if not, write to the Free * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA * 02110-1301 USA, or see the FSF site: http://www.fsf.org. */
import java.lang.ref.ReferenceQueue; import java.lang.ref.WeakReference; import java.util.AbstractCollection; import java.util.AbstractSet; import java.util.ArrayList; import java.util.Collection; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; /**
* A hashtable-based Map implementation with weak keys and * using reference-equality in place of object-equality when comparing keys (and * values). In an WeakIdentityHashMap, two keys k1 and * k2 are considered equal if and only if (k1==k2). An * entry in a WeakIdentityHashMap will automatically be removed when * its key is no longer in ordinary use. More precisely, the presence of a * mapping for a given key will not prevent the key from being discarded by the * garbage collector, that is, made finalizable, finalized, and then reclaimed. * When a key has been discarded its entry is effectively removed from the map. **
* Based on java.util.WeakHashMap *
* * @author Dawid Kurzyniec * @version $Revision: 2787 $ * @author * @see java.util.IdentityHashMap * @see java.util.WeakHashMap */
@SuppressWarnings("unchecked") public class WeakIdentityHashMap /* extends AbstractMap */implements Map {
/**
* The default initial capacity -- MUST be a power of two.
*/
private static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* The maximum capacity, used if a higher value is implicitly specified by
* either of the constructors with arguments. MUST be a power of two <= 1<<30.
*/
private static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load fast used when none specified in constructor.
*/
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
private Entry[] table;
/**
* The number of key-value mappings contained in this weak hash map.
*/
private int size;
/**
* The next size value at which to resize (capacity * load factor).
*/
private int threshold;
/**
* The load factor for the hash table.
*/
private final float loadFactor;
/**
* Reference queue for cleared WeakEntries
*/
private final ReferenceQueue queue = new ReferenceQueue();
/**
* 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 volatile int modCount;
/**
* Each of these fields are initialized to contain an instance of the
* appropriate view the first time this view is requested. The views are
* stateless, so there"s no reason to create more than one of each.
*/
transient volatile Set keySet = null;
transient volatile Collection values = null;
/**
* Constructs a new, empty WeakIdentityHashMap with the given
* initial capacity and the given load factor.
*
* @param initialCapacity
* The initial capacity of the WeakIdentityHashMap
* @param loadFactor
* The load factor of the WeakIdentityHashMap
* @throws IllegalArgumentException
* If the initial capacity is negative, or if the load factor is
* nonpositive.
*/
public WeakIdentityHashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Initial Capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load factor: " + loadFactor);
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
table = new Entry[capacity];
this.loadFactor = loadFactor;
threshold = (int) (capacity * loadFactor);
}
/**
* Constructs a new, empty WeakIdentityHashMap with the given
* initial capacity and the default load factor, which is 0.75.
*
* @param initialCapacity
* The initial capacity of the WeakIdentityHashMap
* @throws IllegalArgumentException
* If the initial capacity is negative.
*/
public WeakIdentityHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs a new, empty WeakIdentityHashMap with the default
* initial capacity (16) and the default load factor (0.75).
*/
public WeakIdentityHashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = DEFAULT_INITIAL_CAPACITY;
table = new Entry[DEFAULT_INITIAL_CAPACITY];
}
/**
* Constructs a new WeakIdentityHashMap with the same mappings as
* the specified Map. The WeakIdentityHashMap is
* created with default load factor, which is 0.75 and an initial
* capacity sufficient to hold the mappings in the specified Map.
*
* @param t
* the map whose mappings are to be placed in this map.
* @throws NullPointerException
* if the specified map is null.
*/
public WeakIdentityHashMap(Map t) {
this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 16), DEFAULT_LOAD_FACTOR);
putAll(t);
}
// internal utilities
/**
* Value representing null keys inside tables.
*/
private static final Object NULL_KEY = new Object();
/**
* Use NULL_KEY for key if it is null.
*/
private static Object maskNull(Object key) {
return (key == null ? NULL_KEY : key);
}
/**
* Return internal representation of null key back to caller as null
*/
private static Object unmaskNull(Object key) {
return (key == NULL_KEY ? null : key);
}
/**
* Return a hash code for non-null Object x.
*/
int hash(Object x) {
int h = System.identityHashCode(x);
return h - (h << 7); // that is,, -127 * h
}
/**
* Return index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length - 1);
}
/**
* Expunge stale entries from the table.
*/
private void expungeStaleEntries() {
Object r;
while ((r = queue.poll()) != null) {
Entry e = (Entry) r;
int h = e.hash;
int i = indexFor(h, table.length);
Entry prev = table[i];
Entry p = prev;
while (p != null) {
Entry next = p.next;
if (p == e) {
if (prev == e)
table[i] = next;
else
prev.next = next;
e.next = null; // Help GC
e.value = null; // " "
size--;
break;
}
prev = p;
p = next;
}
}
}
/**
* Return the table after first expunging stale entries
*/
private Entry[] getTable() {
expungeStaleEntries();
return table;
}
/**
* Returns the number of key-value mappings in this map. This result is a
* snapshot, and may not reflect unprocessed entries that will be removed
* before next attempted access because they are no longer referenced.
*/
public int size() {
if (size == 0)
return 0;
expungeStaleEntries();
return size;
}
/**
* Returns true if this map contains no key-value mappings. This
* result is a snapshot, and may not reflect unprocessed entries that will be
* removed before next attempted access because they are no longer referenced.
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* Returns the value to which the specified key is mapped in this weak hash
* map, or null if the map contains no mapping for this key. A
* return value of null does not necessarily indicate that
* the map contains no mapping for the key; it is also possible that the map
* explicitly maps the key to null. The containsKey
* method may be used to distinguish these two cases.
*
* @param key
* the key whose associated value is to be returned.
* @return the value to which this map maps the specified key, or
* null if the map contains no mapping for this key.
* @see #put(Object, Object)
*/
public Object get(Object key) {
Object k = maskNull(key);
int h = hash(k);
Entry[] tab = getTable();
int index = indexFor(h, tab.length);
Entry e = tab[index];
while (e != null) {
if (e.hash == h && k == e.get())
return e.value;
e = e.next;
}
return null;
}
/**
* Returns true if this map contains a mapping for the specified
* key.
*
* @param key
* The key whose presence in this map is to be tested
* @return true if there is a mapping for key;
* false otherwise
*/
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
/**
* Returns the entry associated with the specified key in the HashMap. Returns
* null if the HashMap contains no mapping for this key.
*/
Entry getEntry(Object key) {
Object k = maskNull(key);
int h = hash(k);
Entry[] tab = getTable();
int index = indexFor(h, tab.length);
Entry e = tab[index];
while (e != null && !(e.hash == h && k == e.get()))
e = e.next;
return 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 null if
* there was no mapping for key. A null return can also
* indicate that the HashMap previously associated null
* with the specified key.
*/
public Object put(Object key, Object value) {
Object k = maskNull(key);
int h = hash(k);
Entry[] tab = getTable();
int i = indexFor(h, tab.length);
for (Entry e = tab[i]; e != null; e = e.next) {
if (h == e.hash && k == e.get()) {
Object oldValue = e.value;
if (value != oldValue)
e.value = value;
return oldValue;
}
}
modCount++;
tab[i] = new Entry(k, value, queue, h, tab[i]);
if (++size >= threshold)
resize(tab.length * 2);
return null;
}
/**
* Rehashes the contents of this map into a new HashMap instance
* with a larger capacity. This method is called automatically when the number
* of keys in this map exceeds its capacity and load factor.
*
* Note that this method is a no-op if it"s called with newCapacity ==
* 2*MAXIMUM_CAPACITY (which is Integer.MIN_VALUE).
*
* @param newCapacity
* the new capacity, MUST be a power of two.
*/
void resize(int newCapacity) {
// assert (newCapacity & -newCapacity) == newCapacity; // power of 2
Entry[] oldTable = getTable();
int oldCapacity = oldTable.length;
// check if needed
if (size < threshold || oldCapacity > newCapacity)
return;
Entry[] newTable = new Entry[newCapacity];
transfer(oldTable, newTable);
table = newTable;
/*
* If ignoring null elements and processing ref queue caused massive
* shrinkage, then restore old table. This should be rare, but avoids
* unbounded expansion of garbage-filled tables.
*/
if (size >= threshold / 2) {
threshold = (int) (newCapacity * loadFactor);
} else {
expungeStaleEntries();
transfer(newTable, oldTable);
table = oldTable;
}
}
/** Transfer all entries from src to dest tables */
private void transfer(Entry[] src, Entry[] dest) {
for (int j = 0; j < src.length; ++j) {
Entry e = src[j];
src[j] = null;
while (e != null) {
Entry next = e.next;
Object key = e.get();
if (key == null) {
e.next = null; // Help GC
e.value = null; // " "
size--;
} else {
int i = indexFor(e.hash, dest.length);
e.next = dest[i];
dest[i] = e;
}
e = next;
}
}
}
/**
* Copies all of the mappings from the specified map to this map These
* mappings will 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. * @throws NullPointerException * if the specified map is null. */ public void putAll(Map t) { // Expand enough to hold t"s elements without resizing. int n = t.size(); if (n == 0) return; if (n >= threshold) { n = (int) (n / loadFactor + 1); if (n > MAXIMUM_CAPACITY) n = MAXIMUM_CAPACITY; int capacity = table.length; while (capacity < n) capacity <<= 1; resize(capacity); } for (Iterator i = t.entrySet().iterator(); i.hasNext();) { Map.Entry e = (Map.Entry) i.next(); put(e.getKey(), e.getValue()); } } /** * 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 null if * there was no mapping for key. A null return can also * indicate that the map previously associated null with * the specified key. */ public Object remove(Object key) { Object k = maskNull(key); int h = hash(k); Entry[] tab = getTable(); int i = indexFor(h, tab.length); Entry prev = tab[i]; Entry e = prev; while (e != null) { Entry next = e.next; if (h == e.hash && k == e.get()) { modCount++; size--; if (prev == e) tab[i] = next; else prev.next = next; return e.value; } prev = e; e = next; } return null; } /** Special version of remove needed by Entry set */ Entry removeMapping(Object o) { if (!(o instanceof Map.Entry)) return null; Entry[] tab = getTable(); Map.Entry entry = (Map.Entry) o; Object k = maskNull(entry.getKey()); int h = hash(k); int i = indexFor(h, tab.length); Entry prev = tab[i]; Entry e = prev; while (e != null) { Entry next = e.next; if (h == e.hash && e.equals(entry)) { modCount++; size--; if (prev == e) tab[i] = next; else prev.next = next; return e; } prev = e; e = next; } return null; } /** * Removes all mappings from this map. */ public void clear() { // clear out ref queue. We don"t need to expunge entries // since table is getting cleared. while (queue.poll() != null) ; modCount++; Entry tab[] = table; for (int i = 0; i < tab.length; ++i) tab[i] = null; size = 0; // Allocation of array may have caused GC, which may have caused // additional entries to go stale. Removing these entries from the // reference queue will make them eligible for reclamation. while (queue.poll() != null) ; } /** * Returns true 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 true if this map maps one or more keys to the specified * value. */ public boolean containsValue(Object value) { if (value == null) return containsNullValue(); Entry tab[] = getTable(); for (int i = tab.length; i-- > 0;) for (Entry e = tab[i]; e != null; e = e.next) if (value.equals(e.value)) return true; return false; } /** * Special-case code for containsValue with null argument */ private boolean containsNullValue() { Entry tab[] = getTable(); for (int i = tab.length; i-- > 0;) for (Entry e = tab[i]; e != null; e = e.next) if (e.value == null) return true; return false; } /** * The entries in this hash table extend WeakReference, using its main ref * field as the key. */ private static class Entry extends WeakReference implements Map.Entry { private Object value; private final int hash; private Entry next; /** * Create new entry. */ Entry(Object key, Object value, ReferenceQueue queue, int hash, Entry next) { super(key, queue); this.value = value; this.hash = hash; this.next = next; } public Object getKey() { return unmaskNull(this.get()); } public Object getValue() { return value; } public Object setValue(Object newValue) { Object oldValue = value; value = newValue; return oldValue; } public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry) o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public int hashCode() { Object k = getKey(); Object v = getValue(); return ((k == null ? 0 : System.identityHashCode(k)) ^ (v == null ? 0 : v.hashCode())); } public String toString() { return getKey() + "=" + getValue(); } } private abstract class HashIterator implements Iterator { int index; Entry entry = null; Entry lastReturned = null; int expectedModCount = modCount; /** * Strong reference needed to avoid disappearance of key between hasNext and * next */ Object nextKey = null; /** * Strong reference needed to avoid disappearance of key between nextEntry() * and any use of the entry */ Object currentKey = null; HashIterator() { index = (size() != 0 ? table.length : 0); } public boolean hasNext() { Entry[] t = table; while (nextKey == null) { Entry e = entry; int i = index; while (e == null && i > 0) e = t[--i]; entry = e; index = i; if (e == null) { currentKey = null; return false; } nextKey = e.get(); // hold on to key in strong ref if (nextKey == null) entry = entry.next; } return true; } protected Entry nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (nextKey == null && !hasNext()) throw new NoSuchElementException(); lastReturned = entry; entry = entry.next; currentKey = nextKey; nextKey = null; return lastReturned; } public void remove() { if (lastReturned == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); WeakIdentityHashMap.this.remove(currentKey); expectedModCount = modCount; lastReturned = null; currentKey = null; } } private class ValueIterator extends HashIterator { public Object next() { return nextEntry().value; } } private class KeyIterator extends HashIterator { public Object next() { return nextEntry().getKey(); } } private class EntryIterator extends HashIterator { public Object next() { return nextEntry(); } } // Views private transient Set entrySet = null; /** * 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 Iterator.remove, Set.remove, * removeAll, retainAll, and clear * operations. It does not support the add or addAll * operations. * * @return a set view of the keys contained in this map. */ public Set keySet() { Set ks = keySet; return (ks != null ? ks : (keySet = new KeySet())); } private class KeySet extends AbstractSet { public Iterator iterator() { return new KeyIterator(); } public int size() { return WeakIdentityHashMap.this.size(); } public boolean contains(Object o) { return containsKey(o); } public boolean remove(Object o) { if (containsKey(o)) { WeakIdentityHashMap.this.remove(o); return true; } else return false; } public void clear() { WeakIdentityHashMap.this.clear(); } public Object[] toArray() { Collection c = new ArrayList(size()); for (Iterator i = iterator(); i.hasNext();) c.add(i.next()); return c.toArray(); } public Object[] toArray(Object a[]) { Collection c = new ArrayList(size()); for (Iterator i = iterator(); i.hasNext();) c.add(i.next()); return c.toArray(a); } } /** * 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 * Iterator.remove, Collection.remove, * removeAll, retainAll, and clear * operations. It does not support the add or addAll * operations. * * @return a collection view of the values contained in this map. */ public Collection values() { Collection vs = values; return (vs != null ? vs : (values = new Values())); } private class Values extends AbstractCollection { public Iterator iterator() { return new ValueIterator(); } public int size() { return WeakIdentityHashMap.this.size(); } public boolean contains(Object o) { return containsValue(o); } public void clear() { WeakIdentityHashMap.this.clear(); } public Object[] toArray() { Collection c = new ArrayList(size()); for (Iterator i = iterator(); i.hasNext();) c.add(i.next()); return c.toArray(); } public Object[] toArray(Object a[]) { Collection c = new ArrayList(size()); for (Iterator i = iterator(); i.hasNext();) c.add(i.next()); return c.toArray(a); } } /** * Returns a collection view of the mappings contained in this map. Each * element in the returned collection is a Map.Entry. 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 * Iterator.remove, Collection.remove, * removeAll, retainAll, and clear * operations. It does not support the add or addAll * operations. * * @return a collection view of the mappings contained in this map. * @see java.util.Map.Entry */ public Set entrySet() { Set es = entrySet; return (es != null ? es : (entrySet = new EntrySet())); } private class EntrySet extends AbstractSet { public Iterator iterator() { return new EntryIterator(); } public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry) o; Entry candidate = getEntry(e.getKey()); return candidate != null && candidate.equals(e); } public boolean remove(Object o) { return removeMapping(o) != null; } public int size() { return WeakIdentityHashMap.this.size(); } public void clear() { WeakIdentityHashMap.this.clear(); } public Object[] toArray() { Collection c = new ArrayList(size()); for (Iterator i = iterator(); i.hasNext();) c.add(new SimpleEntry((Map.Entry) i.next())); return c.toArray(); } public Object[] toArray(Object a[]) { Collection c = new ArrayList(size()); for (Iterator i = iterator(); i.hasNext();) c.add(new SimpleEntry((Map.Entry) i.next())); return c.toArray(a); } } static class SimpleEntry implements Map.Entry { Object key; Object value; public SimpleEntry(Object key, Object value) { this.key = key; this.value = value; } public SimpleEntry(Map.Entry e) { this.key = e.getKey(); this.value = e.getValue(); } public Object getKey() { return key; } public Object getValue() { return value; } public Object setValue(Object value) { Object oldValue = this.value; this.value = value; return oldValue; } public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry) o; return eq(key, e.getKey()) && eq(value, e.getValue()); } public int hashCode() { return ((key == null) ? 0 : key.hashCode()) ^ ((value == null) ? 0 : value.hashCode()); } public String toString() { return key + "=" + value; } private static boolean eq(Object o1, Object o2) { return (o1 == null ? o2 == null : o1.equals(o2)); } } } </source>
A WeakValueHashMap is implemented as a HashMap that maps keys to Weak Values
<source lang="java">
/*
* Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You 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. */
import java.lang.ref.ReferenceQueue; import java.lang.ref.WeakReference; import java.util.AbstractCollection; import java.util.AbstractSet; import java.util.Collection; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; /**
* A WeakValueHashMap is implemented as a HashMap that maps keys to * WeakValues. Because we don"t have access to the innards of the * HashMap, we have to wrap/unwrap value objects with WeakValues on * every operation. Fortunately WeakValues are small, short-lived * objects, so the added allocation overhead is tolerable. This * implementaton directly extends java.util.HashMap. * * @author Markus Fuchs * @see java.util.HashMap * @see java.lang.ref.WeakReference */
public class WeakValueHashMap extends HashMap {
/* Reference queue for cleared WeakValues */
private ReferenceQueue queue = new ReferenceQueue();
/**
* Returns the number of key-value mappings in this map.<p>
* @return the number of key-value mappings in this map.
*/
public int size() {
// delegate to entrySet, as super.size() also counts WeakValues
return entrySet().size();
}
/**
* Returns true if this map contains no key-value mappings.<p>
* @return true if this map contains no key-value mappings.
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* Returns true if this map contains a mapping for the specified
* key.<p>
* @param key key whose presence in this map is to be tested
* @return true if this map contains a mapping for the specified
* key.
*/
public boolean containsKey(Object key) {
// need to clean up gc"ed values before invoking super method
processQueue();
return super.containsKey(key);
}
/**
* Returns true if this map maps one or more keys to the
* specified value.<p>
* @param value value whose presence in this map is to be tested
* @return true if this map maps one or more keys to this value.
*/
public boolean containsValue(Object value) {
return super.containsValue(WeakValue.create(value));
}
/**
* Gets the value for the given key.<p>
* @param key key whose associated value, if any, is to be returned
* @return the value to which this map maps the specified key.
*/
public Object get(Object key) {
// We don"t need to remove garbage collected values here;
// if they are garbage collected, the get() method returns null;
// the next put() call with the same key removes the old value
// automatically so that it can be completely garbage collected
return getReferenceObject((WeakReference) super.get(key));
}
/**
* Puts a new (key,value) into the map.<p>
* @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 null
* if there was no mapping for key or the value has been garbage
* collected by the garbage collector.
*/
public Object put(Object key, Object value) {
// If the map already contains an equivalent key, the new key
// of a (key, value) pair is NOT stored in the map but the new
// value only. But as the key is strongly referenced by the
// map, it can not be removed from the garbage collector, even
// if the key becomes weakly reachable due to the old
// value. So, it isn"t necessary to remove all garbage
// collected values with their keys from the map before the
// new entry is made. We only clean up here to distribute
// clean up calls on different operations.
processQueue();
WeakValue oldValue =
(WeakValue)super.put(key, WeakValue.create(key, value, queue));
return getReferenceObject(oldValue);
}
/**
* Removes key and value for the given key.<p>
* @param key key whose mapping is to be removed from the map.
* @return previous value associated with specified key, or null
* if there was no mapping for key or the value has been garbage
* collected by the garbage collector.
*/
public Object remove(Object key) {
return getReferenceObject((WeakReference) super.remove(key));
}
/**
* A convenience method to return the object held by the
* weak reference or null if it does not exist.
*/
private final Object getReferenceObject(WeakReference ref) {
return (ref == null) ? null : ref.get();
}
/**
* Removes all garbage collected values with their keys from the map.
* Since we don"t know how much the ReferenceQueue.poll() operation
* costs, we should not call it every map operation.
*/
private void processQueue() {
WeakValue wv = null;
while ((wv = (WeakValue) this.queue.poll()) != null) {
// "super" is not really necessary but use it
// to be on the safe side
super.remove(wv.key);
}
}
/* -- Helper classes -- */
/**
* We need this special class to keep the backward reference from
* the value to the key, so that we are able to remove the key if
* the value is garbage collected.
*/
private static class WeakValue extends WeakReference {
/**
* It"s the same as the key in the map. We need the key to remove
* the value if it is garbage collected.
*/
private Object key;
private WeakValue(Object value) {
super(value);
}
/**
* Creates a new weak reference without adding it to a
* ReferenceQueue.
*/
private static WeakValue create(Object value) {
if (value == null) return null;
else return new WeakValue(value);
}
private WeakValue(Object key, Object value, ReferenceQueue queue) {
super(value, queue);
this.key = key;
}
/**
* Creates a new weak reference and adds it to the given queue.
*/
private static WeakValue create(Object key, Object value,
ReferenceQueue queue) {
if (value == null) return null;
else return new WeakValue(key, value, queue);
}
/**
* A WeakValue is equal to another WeakValue iff they both refer
* to objects that are, in turn, equal according to their own
* equals methods.
*/
public boolean equals(Object obj) {
if (this == obj)
return true;
if (!(obj instanceof WeakValue))
return false;
Object ref1 = this.get();
Object ref2 = ((WeakValue) obj).get();
if (ref1 == ref2)
return true;
if ((ref1 == null) || (ref2 == null))
return false;
return ref1.equals(ref2);
}
/**
*
*/
public int hashCode() {
Object ref = this.get();
return (ref == null) ? 0 : ref.hashCode();
}
}
/**
* Internal class for entries. This class wraps/unwraps the
* values of the Entry objects returned from the underlying map.
*/
private class Entry implements Map.Entry {
private Map.Entry ent;
private Object value; /* Strong reference to value, so that the
GC will leave it alone as long as this
Entry exists */
Entry(Map.Entry ent, Object value) {
this.ent = ent;
this.value = value;
}
public Object getKey() {
return ent.getKey();
}
public Object getValue() {
return value;
}
public Object setValue(Object value) {
// This call changes the map. Please see the comment on
// the put method for the correctness remark.
Object oldValue = this.value;
this.value = value;
ent.setValue(WeakValue.create(getKey(), value, queue));
return oldValue;
}
private boolean valEquals(Object o1, Object o2) {
return (o1 == null) ? (o2 == null) : o1.equals(o2);
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry)) return false;
Map.Entry e = (Map.Entry) o;
return (valEquals(ent.getKey(), e.getKey())
&& valEquals(value, e.getValue()));
}
public int hashCode() {
Object k;
return ((((k = ent.getKey()) == null) ? 0 : k.hashCode())
^ ((value == null) ? 0 : value.hashCode()));
}
}
/**
* Internal class for entry sets to unwrap/wrap WeakValues stored
* in the map.
*/
private class EntrySet extends AbstractSet {
public Iterator iterator() {
// remove garbage collected elements
processQueue();
return new Iterator() {
Iterator hashIterator = hashEntrySet.iterator();
Entry next = null;
public boolean hasNext() {
if (hashIterator.hasNext()) {
// since we removed garbage collected elements,
// we can simply return the next entry.
Map.Entry ent = (Map.Entry) hashIterator.next();
WeakValue wv = (WeakValue) ent.getValue();
Object v = (wv == null) ? null : wv.get();
next = new Entry(ent, v);
return true;
}
return false;
}
public Object next() {
if ((next == null) && !hasNext())
throw new NoSuchElementException();
Entry e = next;
next = null;
return e;
}
public void remove() {
hashIterator.remove();
}
};
}
public boolean isEmpty() {
return !(iterator().hasNext());
}
public int size() {
int j = 0;
for (Iterator i = iterator(); i.hasNext(); i.next()) j++;
return j;
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry)) return false;
Map.Entry e = (Map.Entry) o;
Object ek = e.getKey();
Object ev = e.getValue();
Object hv = WeakValueHashMap.this.get(ek);
if (hv == null) {
// if the map"s value is null, we have to check, if the
// entry"s value is null and the map contains the key
if ((ev == null) && WeakValueHashMap.this.containsKey(ek)) {
WeakValueHashMap.this.remove(ek);
return true;
} else {
return false;
}
// otherwise, simply compare the values
} else if (hv.equals(ev)) {
WeakValueHashMap.this.remove(ek);
return true;
}
return false;
}
public int hashCode() {
int h = 0;
for (Iterator i = hashEntrySet.iterator(); i.hasNext(); ) {
Map.Entry ent = (Map.Entry) i.next();
Object k;
WeakValue wv = (WeakValue) ent.getValue();
if (wv == null) continue;
h += ((((k = ent.getKey()) == null) ? 0 : k.hashCode())
^ wv.hashCode());
}
return h;
}
}
// internal helper variable, because we can"t access
// entrySet from the superclass inside the EntrySet class
private Set hashEntrySet = null;
// stores the EntrySet instance
private Set entrySet = null;
/**
* Returns a Set view of the mappings in this map.<p>
* @return a Set view of the mappings in this map.
*/
public Set entrySet() {
if (entrySet == null) {
hashEntrySet = super.entrySet();
entrySet = new EntrySet();
}
return entrySet;
}
// stores the value collection
private transient Collection values = null;
/**
* Returns a Collection view of the values contained
* in this map.<p>
* @return a Collection view of the values contained
* in this map.
*/
public Collection values() {
// delegates to entrySet, because super method returns
// WeakValues instead of value objects
if (values == null) {
values = new AbstractCollection() {
public Iterator iterator() {
return new Iterator() {
private Iterator i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public Object next() {
return ((Entry)i.next()).getValue();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return WeakValueHashMap.this.size();
}
public boolean contains(Object v) {
return WeakValueHashMap.this.containsValue(v);
}
};
}
return values;
}
}
</source>
Create a WeakHashMap with a single element in it
<source lang="java">
import java.util.Map; import java.util.WeakHashMap; public class Main {
public static void main(String args[]) {
final Map<String, String> map = new WeakHashMap<String, String>();
map.put(new String("A"), "B");
Runnable runner = new Runnable() {
public void run() {
while (map.containsKey("A")) {
try {
Thread.sleep(500);
} catch (InterruptedException ignored) {
}
System.gc();
}
}
};
Thread t = new Thread(runner);
t.start();
try {
t.join();
} catch (InterruptedException ignored) {
}
}
}
</source>
Implements a combination of WeakHashMap and IdentityHashMap
<source lang="java">
/**
* Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you 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. */
import java.lang.ref.ReferenceQueue; import java.lang.ref.WeakReference; import java.util.Collection; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set;
/**
* Implements a combination of WeakHashMap and IdentityHashMap. * Useful for caches that need to key off of a == comparison * instead of a .equals. * * * This class is not a general-purpose Map implementation! While * this class implements the Map interface, it intentionally violates * Map"s general contract, which mandates the use of the equals method * when comparing objects. This class is designed for use only in the * rare cases wherein reference-equality semantics are required. * * Note that this implementation is not synchronized. * */
public class WeakIdentityHashMap<K, V> implements Map<K, V> {
private final ReferenceQueue<K> queue = new ReferenceQueue<K>(); private Map<IdentityWeakReference, V> backingStore = new HashMap<IdentityWeakReference, V>();
public WeakIdentityHashMap() {
}
public void clear() {
backingStore.clear();
reap();
}
public boolean containsKey(Object key) {
reap();
return backingStore.containsKey(new IdentityWeakReference(key));
}
public boolean containsValue(Object value) {
reap();
return backingStore.containsValue(value);
}
public Set<Map.Entry<K, V>> entrySet() {
reap();
Set<Map.Entry<K, V>> ret = new HashSet<Map.Entry<K, V>>();
for (Map.Entry<IdentityWeakReference, V> ref : backingStore.entrySet()) {
final K key = ref.getKey().get();
final V value = ref.getValue();
Map.Entry<K, V> entry = new Map.Entry<K, V>() {
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
throw new UnsupportedOperationException();
}
};
ret.add(entry);
}
return Collections.unmodifiableSet(ret);
}
public Set<K> keySet() {
reap();
Set<K> ret = new HashSet<K>();
for (IdentityWeakReference ref : backingStore.keySet()) {
ret.add(ref.get());
}
return Collections.unmodifiableSet(ret);
}
public boolean equals(Object o) {
return backingStore.equals(((WeakIdentityHashMap)o).backingStore);
}
public V get(Object key) {
reap();
return backingStore.get(new IdentityWeakReference(key));
}
public V put(K key, V value) {
reap();
return backingStore.put(new IdentityWeakReference(key), value);
}
public int hashCode() {
reap();
return backingStore.hashCode();
}
public boolean isEmpty() {
reap();
return backingStore.isEmpty();
}
public void putAll(Map t) {
throw new UnsupportedOperationException();
}
public V remove(Object key) {
reap();
return backingStore.remove(new IdentityWeakReference(key));
}
public int size() {
reap();
return backingStore.size();
}
public Collection<V> values() {
reap();
return backingStore.values();
}
private synchronized void reap() {
Object zombie = queue.poll();
while (zombie != null) {
IdentityWeakReference victim = (IdentityWeakReference)zombie;
backingStore.remove(victim);
zombie = queue.poll();
}
}
class IdentityWeakReference extends WeakReference<K> {
int hash;
@SuppressWarnings("unchecked")
IdentityWeakReference(Object obj) {
super((K)obj, queue);
hash = System.identityHashCode(obj);
}
public int hashCode() {
return hash;
}
public boolean equals(Object o) {
if (this == o) {
return true;
}
IdentityWeakReference ref = (IdentityWeakReference)o;
if (this.get() == ref.get()) {
return true;
}
return false;
}
}
}
</source>
To enable automatically release of the value, the value must be wrapped in a WeakReference object
<source lang="java">
import java.lang.ref.WeakReference; import java.util.Iterator; import java.util.Map; import java.util.WeakHashMap; public class Main {
public static void main(String[] argv) throws Exception {
Object keyObject = "";
Object valueObject = "";
Map weakMap = new WeakHashMap();
weakMap.put(keyObject, valueObject);
WeakReference weakValue = new WeakReference(valueObject);
weakMap.put(keyObject, weakValue);
Iterator it = weakMap.keySet().iterator();
while (it.hasNext()) {
Object key = it.next();
weakValue = (WeakReference) weakMap.get(key);
if (weakValue == null) {
System.out.println("Value has been garbage-collected");
} else {
System.out.println("Get value");
valueObject = weakValue.get();
}
}
}
}
</source>
Weak Identity Map
<source lang="java">
/*
* Copyright 2004 Brian S O"Neill * * 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. */
//revised from cojen import java.lang.ref.Reference; import java.lang.ref.ReferenceQueue; import java.lang.ref.WeakReference; import java.util.AbstractCollection; import java.util.AbstractMap; import java.util.AbstractSet; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; /**
* WeakIdentityMap is like WeakHashMap, except it uses a key"s identity * hashcode and equals methods. WeakIdentityMap is not thread-safe and must be * wrapped with Collections.synchronizedMap to be made thread-safe. * <p> * The documentation for WeakHashMap states that it is intended primarily for * use with key objects whose equals methods test for object identity using the * == operator. Because WeakIdentityMap strictly follows this behavior, it is * better suited for this purpose. * <p> * Note: Weakly 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 */
public class WeakIdentityMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable {
// Types of Iterators
static final int KEYS = 0;
static final int VALUES = 1;
static final int ENTRIES = 2;
/**
* Converts a collection to string, supporting collections that contain
* self references
*/
static String toString(Collection c) {
if (c.size() == 0) {
return "[]";
}
StringBuffer buf = new StringBuffer(32 * c.size());
buf.append("[");
Iterator it = c.iterator();
boolean hasNext = it.hasNext();
while (hasNext) {
Object obj = it.next();
buf.append(obj == c ? "(this Collection)" : obj);
if (hasNext) {
buf.append(", ");
}
}
buf.append("]");
return buf.toString();
}
/**
* Converts a map to string, supporting maps that contain self references
*/
static String toString(Map m) {
if (m.size() == 0) {
return "{}";
}
StringBuffer buf = new StringBuffer(32 * m.size());
buf.append("{");
Iterator it = m.entrySet().iterator();
boolean hasNext = it.hasNext();
while (hasNext) {
Map.Entry entry = (Map.Entry)it.next();
Object key = entry.getKey();
Object value = entry.getValue();
buf.append(key == m ? "(this Map)" : key)
.append("=")
.append(value == m ? "(this Map)" : value);
hasNext = it.hasNext();
if (hasNext) {
buf.append(",").append(" ");
}
}
buf.append("}");
return buf.toString();
}
private transient Entry<K, V>[] table;
private transient int count;
private int threshold;
private final float loadFactor;
private final ReferenceQueue<K> queue;
private transient volatile int modCount;
// Views
private transient Set<K> keySet;
private transient Set<Map.Entry<K, V>> entrySet;
private transient Collection<V> values;
public WeakIdentityMap(int initialCapacity, float loadFactor) {
if (initialCapacity <= 0) {
throw new IllegalArgumentException("Initial capacity must be greater than 0");
}
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Load factor must be greater than 0");
}
this.loadFactor = loadFactor;
this.table = new Entry[initialCapacity];
this.threshold = (int)(initialCapacity * loadFactor);
this.queue = new ReferenceQueue();
}
public WeakIdentityMap(int initialCapacity) {
this(initialCapacity, 0.75f);
}
public WeakIdentityMap() {
this(11, 0.75f);
}
public WeakIdentityMap(Map<? extends K, ? extends V> t) {
this(Math.max(2 * t.size(), 11), 0.75f);
putAll(t);
}
public int size() {
// Cleanup right before, to report a more accurate size.
cleanup();
return this.count;
}
public boolean isEmpty() {
return this.count == 0;
}
public boolean containsValue(Object value) {
Entry[] tab = this.table;
if (value == null) {
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[i] = e.next;
}
this.count--;
} else if (e.value == null) {
return true;
} else {
prev = e;
}
}
}
} else {
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[i] = e.next;
}
this.count--;
} else if (value.equals(e.value)) {
return true;
} else {
prev = e;
}
}
}
}
return false;
}
public boolean containsKey(Object key) {
if (key == null) {
key = KeyFactory.NULL;
}
Entry[] tab = this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key == entryKey) {
return true;
} else {
prev = e;
}
}
return false;
}
public V get(Object key) {
if (key == null) {
key = KeyFactory.NULL;
}
Entry<K, V>[] tab = this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key == entryKey) {
return e.value;
} else {
prev = e;
}
}
return null;
}
private void cleanup() {
// Cleanup after cleared References.
Entry[] tab = this.table;
ReferenceQueue queue = this.queue;
Reference ref;
while ((ref = queue.poll()) != null) {
// Since buckets are single-linked, traverse entire list and
// cleanup all cleared references in it.
int index = (((Entry) ref).hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
if (e.get() == null) {
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else {
prev = e;
}
}
}
}
private void rehash() {
int oldCapacity = this.table.length;
Entry[] oldMap = this.table;
int newCapacity = oldCapacity * 2 + 1;
if (newCapacity <= 0) {
// Overflow.
if ((newCapacity = Integer.MAX_VALUE) == oldCapacity) {
return;
}
}
Entry[] newMap = new Entry[newCapacity];
this.modCount++;
this.threshold = (int)(newCapacity * this.loadFactor);
this.table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry old = oldMap[i] ; old != null ; ) {
Entry e = old;
old = old.next;
// Only copy entry if its key hasn"t been cleared.
if (e.get() == null) {
this.count--;
} else {
int index = (e.hash & 0x7fffffff) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}
}
public V put(K key, V value) {
if (key == null) {
key = (K) KeyFactory.NULL;
}
cleanup();
// Make sure the key is not already in the WeakIdentityMap.
Entry[] tab = this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key == entryKey) {
Object old = e.value;
e.value = value;
return (V) old;
} else {
prev = e;
}
}
this.modCount++;
if (this.count >= this.threshold) {
// Rehash the table if the threshold is still exceeded.
rehash();
tab = this.table;
index = (hash & 0x7fffffff) % tab.length;
}
// Creates the new entry.
Entry e = new Entry(hash, key, this.queue, value, tab[index]);
tab[index] = e;
this.count++;
return null;
}
public V remove(Object key) {
if (key == null) {
key = KeyFactory.NULL;
}
Entry<K, V>[] tab = this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key == entryKey) {
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
V oldValue = e.value;
e.value = null;
return oldValue;
} else {
prev = e;
}
}
return null;
}
public void putAll(Map<? extends K, ? extends V> t) {
Iterator i = t.entrySet().iterator();
while (i.hasNext()) {
Map.Entry e = (Map.Entry) i.next();
put((K) e.getKey(), (V) e.getValue());
}
}
public void clear() {
Entry[] tab = this.table;
this.modCount++;
for (int index = tab.length; --index >= 0; ) {
tab[index] = null;
}
this.count = 0;
}
public Object clone() {
try {
WeakIdentityMap t = (WeakIdentityMap)super.clone();
t.table = new Entry[this.table.length];
for (int i = this.table.length ; i-- > 0 ; ) {
t.table[i] = (this.table[i] != null)
? (Entry)this.table[i].copy(this.queue) : null;
}
t.keySet = null;
t.entrySet = null;
t.values = null;
t.modCount = 0;
return t;
}
catch (CloneNotSupportedException e) {
// this shouldn"t happen, since we are Cloneable
throw new InternalError();
}
}
public Set<K> keySet() {
if (this.keySet == null) {
this.keySet = new AbstractSet<K>() {
public Iterator iterator() {
return createHashIterator(KEYS);
}
public int size() {
return WeakIdentityMap.this.count;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return o == null ? false : WeakIdentityMap.this.remove(o) == o;
}
public void clear() {
WeakIdentityMap.this.clear();
}
public String toString() {
return WeakIdentityMap.this.toString(this);
}
};
}
return this.keySet;
}
public Collection<V> values() {
if (this.values==null) {
this.values = new AbstractCollection<V>() {
public Iterator<V> iterator() {
return createHashIterator(VALUES);
}
public int size() {
return WeakIdentityMap.this.count;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
WeakIdentityMap.this.clear();
}
public String toString() {
return WeakIdentityMap.this.toString(this);
}
};
}
return this.values;
}
public Set<Map.Entry<K, V>> entrySet() {
if (this.entrySet==null) {
this.entrySet = new AbstractSet<Map.Entry<K, V>>() {
public Iterator<Map.Entry<K, V>> iterator() {
return createHashIterator(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 = WeakIdentityMap.this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
WeakIdentityMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
WeakIdentityMap.this.count--;
} else if (e.hash == 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 = WeakIdentityMap.this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
WeakIdentityMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
WeakIdentityMap.this.count--;
} else if (e.hash == hash && e.equals(entry)) {
WeakIdentityMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
WeakIdentityMap.this.count--;
e.value = null;
return true;
} else {
prev = e;
}
}
return false;
}
public int size() {
return WeakIdentityMap.this.count;
}
public void clear() {
WeakIdentityMap.this.clear();
}
public String toString() {
return WeakIdentityMap.toString(this);
}
};
}
return this.entrySet;
}
/**
* Gets the map as a String.
*
* @return a string version of the map
*/
public String toString() {
return toString(this);
}
private Iterator createHashIterator(int type) {
if (this.count == 0) {
return Collections.EMPTY_SET.iterator();
} else {
return new HashIterator(type);
}
}
/**
* WeakIdentityMap collision list entry.
*/
private static class Entry<K, V> extends WeakReference<K> implements Map.Entry<K, V> {
int hash;
V value;
Entry<K, V> next;
Entry(int hash, K key, ReferenceQueue<K> queue, V value, Entry<K, V> next) {
super(key, queue);
this.hash = hash;
this.value = value;
this.next = next;
}
public void clear() {
// Do nothing if reference is explicity cleared. This prevents
// backdoor modification of map entries.
}
public K getKey() {
K key = Entry.this.get();
return key == KeyFactory.NULL ? null : key;
}
public V getValue() {
return this.value;
}
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object obj) {
if (!(obj instanceof Map.Entry)) {
return false;
}
return equals((Map.Entry)obj);
}
boolean equals(Map.Entry<K, V> e) {
Object thisKey = get();
if (thisKey == null) {
return false;
} else if (thisKey == KeyFactory.NULL) {
thisKey = null;
}
return (thisKey == e.getKey()) &&
(this.value == null ? e.getValue() == null : this.value.equals(e.getValue()));
}
public int hashCode() {
return this.hash ^ (this.value == null ? 0 : this.value.hashCode());
}
public String toString() {
return getKey() + "=" + this.value;
}
protected Object copy(ReferenceQueue queue) {
return new Entry(this.hash, get(), queue, this.value,
(this.next == null ? null : (Entry)this.next.copy(queue)));
}
}
private class HashIterator implements Iterator {
private final int type;
private final Entry[] table;
private int index;
// To ensure that the iterator doesn"t return cleared entries, keep a
// hard reference to the key. Its existence will prevent the weak
// key from being cleared.
Object entryKey;
Entry entry;
Entry last;
/**
* 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 = WeakIdentityMap.this.modCount;
HashIterator(int type) {
this.table = WeakIdentityMap.this.table;
this.type = type;
this.index = table.length;
}
public boolean hasNext() {
while (this.entry == null || (this.entryKey = this.entry.get()) == null) {
if (this.entry != null) {
// Clean up after a cleared Reference.
remove(this.entry);
this.entry = this.entry.next;
}
else {
if (this.index <= 0) {
return false;
}
else {
this.entry = this.table[--this.index];
}
}
}
return true;
}
public Object next() {
if (WeakIdentityMap.this.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
}
if (!hasNext()) {
throw new NoSuchElementException();
}
this.last = this.entry;
this.entry = this.entry.next;
return this.type == KEYS ? this.last.getKey() :
(this.type == VALUES ? this.last.getValue() : this.last);
}
public void remove() {
if (this.last == null) {
throw new IllegalStateException();
}
if (WeakIdentityMap.this.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
}
remove(this.last);
this.last = null;
}
private void remove(Entry toRemove) {
Entry[] tab = this.table;
int index = (toRemove.hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
if (e == toRemove) {
WeakIdentityMap.this.modCount++;
expectedModCount++;
if (prev == null) {
tab[index] = e.next;
} else {
prev.next = e.next;
}
WeakIdentityMap.this.count--;
return;
} else {
prev = e;
}
}
throw new ConcurrentModificationException();
}
public String toString() {
if (this.last != null) {
return "Iterator[" + this.last + "]";
} else {
return "Iterator[]";
}
}
}
} /*
* Copyright 2004 Brian S O"Neill * * 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. */
/**
* KeyFactory generates keys which can be hashed or compared for any kind of * object including arrays, arrays of arrays, and null. All hashcode * computations, equality tests, and ordering comparsisons fully recurse into * arrays. * * @author Brian S O"Neill */
class KeyFactory {
static final Object NULL = new Comparable() {
public int compareTo(Object obj) {
return obj == this || obj == null ? 0 : 1;
}
};
public static Object createKey(boolean[] obj) {
return obj == null ? NULL : new BooleanArrayKey(obj);
}
public static Object createKey(byte[] obj) {
return obj == null ? NULL : new ByteArrayKey(obj);
}
public static Object createKey(char[] obj) {
return obj == null ? NULL : new CharArrayKey(obj);
}
public static Object createKey(double[] obj) {
return obj == null ? NULL : new DoubleArrayKey(obj);
}
public static Object createKey(float[] obj) {
return obj == null ? NULL : new FloatArrayKey(obj);
}
public static Object createKey(int[] obj) {
return obj == null ? NULL : new IntArrayKey(obj);
}
public static Object createKey(long[] obj) {
return obj == null ? NULL : new LongArrayKey(obj);
}
public static Object createKey(short[] obj) {
return obj == null ? NULL : new ShortArrayKey(obj);
}
public static Object createKey(Object[] obj) {
return obj == null ? NULL : new ObjectArrayKey(obj);
}
public static Object createKey(Object obj) {
if (obj == null) {
return NULL;
}
if (!obj.getClass().isArray()) {
return obj;
}
if (obj instanceof Object[]) {
return createKey((Object[])obj);
} else if (obj instanceof int[]) {
return createKey((int[])obj);
} else if (obj instanceof float[]) {
return createKey((float[])obj);
} else if (obj instanceof long[]) {
return createKey((long[])obj);
} else if (obj instanceof double[]) {
return createKey((double[])obj);
} else if (obj instanceof byte[]) {
return createKey((byte[])obj);
} else if (obj instanceof char[]) {
return createKey((char[])obj);
} else if (obj instanceof boolean[]) {
return createKey((boolean[])obj);
} else if (obj instanceof short[]) {
return createKey((short[])obj);
} else {
return obj;
}
}
static int hashCode(boolean[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + (a[i] ? 0 : 1);
}
return hash == 0 ? -1 : hash;
}
static int hashCode(byte[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + a[i];
}
return hash == 0 ? -1 : hash;
}
static int hashCode(char[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + a[i];
}
return hash == 0 ? -1 : hash;
}
static int hashCode(double[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
long v = Double.doubleToLongBits(a[i]);
hash = hash * 31 + (int)(v ^ v >>> 32);
}
return hash == 0 ? -1 : hash;
}
static int hashCode(float[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = hash * 31 + Float.floatToIntBits(a[i]);
}
return hash == 0 ? -1 : hash;
}
static int hashCode(int[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + a[i];
}
return hash == 0 ? -1 : hash;
}
static int hashCode(long[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
long v = a[i];
hash = hash * 31 + (int)(v ^ v >>> 32);
}
return hash == 0 ? -1 : hash;
}
static int hashCode(short[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + a[i];
}
return hash == 0 ? -1 : hash;
}
static int hashCode(Object[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = hash * 31 + hashCode(a[i]);
}
return hash == 0 ? -1 : hash;
}
// Compute object or array hashcode and recurses into arrays within.
static int hashCode(Object a) {
if (a == null) {
return -1;
}
if (!a.getClass().isArray()) {
return a.hashCode();
}
if (a instanceof Object[]) {
return hashCode((Object[])a);
} else if (a instanceof int[]) {
return hashCode((int[])a);
} else if (a instanceof float[]) {
return hashCode((float[])a);
} else if (a instanceof long[]) {
return hashCode((long[])a);
} else if (a instanceof double[]) {
return hashCode((double[])a);
} else if (a instanceof byte[]) {
return hashCode((byte[])a);
} else if (a instanceof char[]) {
return hashCode((char[])a);
} else if (a instanceof boolean[]) {
return hashCode((boolean[])a);
} else if (a instanceof short[]) {
return hashCode((short[])a);
} else {
int hash = a.getClass().hashCode();
return hash == 0 ? -1 : hash;
}
}
// Compares object arrays and recurses into arrays within.
static boolean equals(Object[] a, Object[] b) {
if (a == b) {
return true;
}
if (a == null || b == null) {
return false;
}
int i;
if ((i = a.length) != b.length) {
return false;
}
while (--i >= 0) {
if (!equals(a[i], b[i])) {
return false;
}
}
return true;
}
// Compares objects or arrays and recurses into arrays within.
static boolean equals(Object a, Object b) {
if (a == b) {
return true;
}
if (a == null || b == null) {
return false;
}
Class ac = a.getClass();
if (!(ac.isArray())) {
return a.equals(b);
}
if (ac != b.getClass()) {
return false;
}
if (a instanceof Object[]) {
return equals((Object[])a, (Object[])b);
} else if (a instanceof int[]) {
return Arrays.equals((int[])a, (int[])b);
} else if (a instanceof float[]) {
return Arrays.equals((float[])a, (float[])b);
} else if (a instanceof long[]) {
return Arrays.equals((long[])a, (long[])b);
} else if (a instanceof double[]) {
return Arrays.equals((double[])a, (double[])b);
} else if (a instanceof byte[]) {
return Arrays.equals((byte[])a, (byte[])b);
} else if (a instanceof char[]) {
return Arrays.equals((char[])a, (char[])b);
} else if (a instanceof boolean[]) {
return Arrays.equals((boolean[])a, (boolean[])b);
} else if (a instanceof short[]) {
return Arrays.equals((short[])a, (short[])b);
} else {
return a.equals(b);
}
}
static int compare(boolean[] a, boolean[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int av = a[i] ? 0 : 1;
int bv = b[i] ? 0 : 1;
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(byte[] a, byte[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
byte av = a[i];
byte bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(char[] a, char[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
char av = a[i];
char bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(double[] a, double[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int v = Double.rupare(a[i], b[i]);
if (v != 0) {
return v;
}
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(float[] a, float[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int v = Float.rupare(a[i], b[i]);
if (v != 0) {
return v;
}
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(int[] a, int[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int av = a[i];
int bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(long[] a, long[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
long av = a[i];
long bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(short[] a, short[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
short av = a[i];
short bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
// Compares object arrays and recurses into arrays within.
static int compare(Object[] a, Object[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int v = compare(a[i], b[i]);
if (v != 0) {
return v;
}
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
// Compares objects or arrays and recurses into arrays within.
static int compare(Object a, Object b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
Class ac = a.getClass();
if (!(ac.isArray())) {
return ((Comparable)a).rupareTo(b);
}
if (ac != b.getClass()) {
throw new ClassCastException();
}
if (a instanceof Object[]) {
return compare((Object[])a, (Object[])b);
} else if (a instanceof int[]) {
return compare((int[])a, (int[])b);
} else if (a instanceof float[]) {
return compare((float[])a, (float[])b);
} else if (a instanceof long[]) {
return compare((long[])a, (long[])b);
} else if (a instanceof double[]) {
return compare((double[])a, (double[])b);
} else if (a instanceof byte[]) {
return compare((byte[])a, (byte[])b);
} else if (a instanceof char[]) {
return compare((char[])a, (char[])b);
} else if (a instanceof boolean[]) {
return compare((boolean[])a, (boolean[])b);
} else if (a instanceof short[]) {
return compare((short[])a, (short[])b);
} else {
throw new ClassCastException();
}
}
protected KeyFactory() {
}
private static interface ArrayKey extends Comparable, java.io.Serializable {
int hashCode();
boolean equals(Object obj);
int compareTo(Object obj);
}
private static class BooleanArrayKey implements ArrayKey {
protected final boolean[] mArray;
private transient int mHash;
BooleanArrayKey(boolean[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof BooleanArrayKey ?
Arrays.equals(mArray, ((BooleanArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((BooleanArrayKey) obj).mArray);
}
}
private static class ByteArrayKey implements ArrayKey {
protected final byte[] mArray;
private transient int mHash;
ByteArrayKey(byte[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof ByteArrayKey ?
Arrays.equals(mArray, ((ByteArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((ByteArrayKey) obj).mArray);
}
}
private static class CharArrayKey implements ArrayKey {
protected final char[] mArray;
private transient int mHash;
CharArrayKey(char[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof CharArrayKey ?
Arrays.equals(mArray, ((CharArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((CharArrayKey) obj).mArray);
}
}
private static class DoubleArrayKey implements ArrayKey {
protected final double[] mArray;
private transient int mHash;
DoubleArrayKey(double[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof DoubleArrayKey ?
Arrays.equals(mArray, ((DoubleArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((DoubleArrayKey) obj).mArray);
}
}
private static class FloatArrayKey implements ArrayKey {
protected final float[] mArray;
private transient int mHash;
FloatArrayKey(float[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof FloatArrayKey ?
Arrays.equals(mArray, ((FloatArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((FloatArrayKey) obj).mArray);
}
}
private static class IntArrayKey implements ArrayKey {
protected final int[] mArray;
private transient int mHash;
IntArrayKey(int[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof IntArrayKey ?
Arrays.equals(mArray, ((IntArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((IntArrayKey) obj).mArray);
}
}
private static class LongArrayKey implements ArrayKey {
protected final long[] mArray;
private transient int mHash;
LongArrayKey(long[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof LongArrayKey ?
Arrays.equals(mArray, ((LongArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((LongArrayKey) obj).mArray);
}
}
private static class ShortArrayKey implements ArrayKey {
protected final short[] mArray;
private transient int mHash;
ShortArrayKey(short[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof ShortArrayKey ?
Arrays.equals(mArray, ((ShortArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((ShortArrayKey) obj).mArray);
}
}
private static class ObjectArrayKey implements ArrayKey {
protected final Object[] mArray;
private transient int mHash;
ObjectArrayKey(Object[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof ObjectArrayKey ?
KeyFactory.equals(mArray, ((ObjectArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((ObjectArrayKey) obj).mArray);
}
}
}
</source>
Weak Valued HashMap
<source lang="java">
/*
* Copyright 2006 Brian S O"Neill * * 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. */
//revised from cojen import java.lang.ref.Reference; import java.lang.ref.ReferenceQueue; import java.lang.ref.WeakReference; import java.util.AbstractCollection; import java.util.AbstractMap; import java.util.AbstractSet; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set;
//revised from cojen
/**
* A Map that weakly references its values and can be used as a simple cache. * WeakValuedHashMap is not thread-safe and must be wrapped with * Collections.synchronizedMap to be made thread-safe. * <p> * Note: Weakly 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 * @since 2.1 */
public class WeakValuedHashMap<K, V> extends ReferencedValueHashMap<K, V> {
/**
* 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 WeakValuedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
}
/**
* Constructs a new, empty map with the specified initial capacity
* and default load factor, which is 0.75.
*
* @param initialCapacity the initial capacity of the HashMap.
* @throws IllegalArgumentException if the initial capacity is less
* than zero.
*/
public WeakValuedHashMap(int initialCapacity) {
super(initialCapacity);
}
/**
* Constructs a new, empty map with a default capacity and load
* factor, which is 0.75.
*/
public WeakValuedHashMap() {
super();
}
/**
* 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 0.75.
*/
public WeakValuedHashMap(Map<? extends K, ? extends V> t) {
super(t);
}
Entry<K, V> newEntry(int hash, K key, V value, Entry<K, V> next) {
return new WeakEntry<K, V>(hash, key, value, next);
}
static class WeakEntry<K, V> extends ReferencedValueHashMap.Entry<K, V> {
WeakEntry(int hash, K key, V value, Entry<K, V> next) {
super(hash, key, value, next);
}
WeakEntry(int hash, K key, Reference<V> value, Entry<K, V> next) {
super(hash, key, value, next);
}
Entry newEntry(int hash, K key, Reference<V> value, Entry<K, V> next) {
return new WeakEntry<K, V>(hash, key, value, next);
}
Reference<V> newReference(V value) {
return new WeakReference<V>(value);
}
}
} /**
* A Map that references its values and can be used as a simple cache. * Instances are not thread-safe and must be wrapped with * Collections.synchronizedMap to be made thread-safe. * <p> * Note: 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 */ abstract class ReferencedValueHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable
{
private transient Entry<K, V>[] table;
private transient int count;
private int threshold;
private final float loadFactor;
private transient volatile int modCount;
// Views
private transient Set<K> keySet;
private transient Set<Map.Entry<K, V>> entrySet;
private transient Collection<V> values;
/**
* 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 ReferencedValueHashMap(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;
}
this.loadFactor = loadFactor;
this.table = new Entry[initialCapacity];
this.threshold = (int)(initialCapacity * loadFactor);
}
/**
* Constructs a new, empty map with the specified initial capacity
* and default load factor, which is 0.75.
*
* @param initialCapacity the initial capacity of the HashMap.
* @throws IllegalArgumentException if the initial capacity is less
* than zero.
*/
public ReferencedValueHashMap(int initialCapacity) {
this(initialCapacity, 0.75f);
}
/**
* Constructs a new, empty map with a default capacity and load
* factor, which is 0.75.
*/
public ReferencedValueHashMap() {
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 0.75.
*/
public ReferencedValueHashMap(Map<? extends K, ? extends V> t) {
this(Math.max(2 * t.size(), 11), 0.75f);
putAll(t);
}
public int size() {
return this.count;
}
public boolean isEmpty() {
return this.count == 0;
}
public boolean containsValue(Object value) {
if (value == null) {
value = KeyFactory.NULL;
}
Entry[] tab = this.table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i], prev = null; e != null; e = e.next) {
Object entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[i] = e.next;
}
this.count--;
} else if (value.equals(entryValue)) {
return true;
} else {
prev = e;
}
}
}
return false;
}
public boolean containsKey(Object key) {
Entry<K, V>[] tab = this.table;
if (key != null) {
int hash = key.hashCode();
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key.equals(e.key)) {
return true;
} else {
prev = e;
}
}
} else {
for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[0] = e.next;
}
this.count--;
} else if (e.key == null) {
return true;
} else {
prev = e;
}
}
}
return false;
}
public V get(Object key) {
Entry<K, V>[] tab = this.table;
if (key != null) {
int hash = key.hashCode();
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
V entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
count--;
} else if (e.hash == hash && key.equals(e.key)) {
return (entryValue == KeyFactory.NULL) ? null : entryValue;
} else {
prev = e;
}
}
} else {
for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
V entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
}
else {
tab[0] = e.next;
}
this.count--;
} else if (e.key == null) {
return (entryValue == KeyFactory.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<K, V>[] tab = this.table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry<K, V> e = tab[i], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[i] = e.next;
}
this.count--;
} else {
prev = e;
}
}
}
}
/**
* Rehashes the contents of this map into a new HashMap 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 = this.table.length;
Entry<K, V>[] oldMap = this.table;
int newCapacity = oldCapacity * 2 + 1;
Entry<K, V>[] newMap = new Entry[newCapacity];
this.modCount++;
this.threshold = (int)(newCapacity * this.loadFactor);
this.table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K, V> old = oldMap[i] ; old != null ; ) {
Entry<K, V> e = old;
old = old.next;
// Only copy entry if its value hasn"t been cleared.
if (e.get() == null) {
this.count--;
} else {
int index = (e.hash & 0x7fffffff) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}
}
public V put(K key, V value) {
if (value == null) {
value = (V) KeyFactory.NULL;
}
// Makes sure the key is not already in the HashMap.
Entry<K, V>[] tab = this.table;
int hash;
int index;
if (key != null) {
hash = key.hashCode();
index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
V entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key.equals(e.key)) {
e.setValue(value);
return (entryValue == KeyFactory.NULL) ? null : entryValue;
} else {
prev = e;
}
}
} else {
hash = 0;
index = 0;
for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
V entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[0] = e.next;
}
this.count--;
} else if (e.key == null) {
e.setValue(value);
return (entryValue == KeyFactory.NULL) ? null : entryValue;
} else {
prev = e;
}
}
}
this.modCount++;
if (this.count >= this.threshold) {
// Cleanup the table if the threshold is exceeded.
cleanup();
}
if (this.count >= this.threshold) {
// Rehash the table if the threshold is still exceeded.
rehash();
tab = this.table;
index = (hash & 0x7fffffff) % tab.length;
}
// Creates the new entry.
Entry<K, V> e = newEntry(hash, key, (V)value, tab[index]);
tab[index] = e;
this.count++;
return null;
}
public V remove(Object key) {
Entry<K, V>[] tab = this.table;
if (key != null) {
int hash = key.hashCode();
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
V entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key.equals(e.key)) {
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
e.setValue(null);
return (entryValue == KeyFactory.NULL) ? null : entryValue;
} else {
prev = e;
}
}
} else {
for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
V entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[0] = e.next;
}
this.count--;
} else if (e.key == null) {
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[0] = e.next;
}
this.count--;
e.setValue(null);
return (entryValue == KeyFactory.NULL) ? null : entryValue;
} else {
prev = e;
}
}
}
return null;
}
public void putAll(Map<? extends K, ? extends V> t) {
Iterator i = t.entrySet().iterator();
while (i.hasNext()) {
Map.Entry<K, V> e = (Map.Entry<K, V>) i.next();
put(e.getKey(), e.getValue());
}
}
public void clear() {
Entry[] tab = this.table;
this.modCount++;
for (int index = tab.length; --index >= 0; ) {
tab[index] = null;
}
this.count = 0;
}
public Object clone() {
try {
ReferencedValueHashMap t = (ReferencedValueHashMap)super.clone();
t.table = new Entry[this.table.length];
for (int i = this.table.length ; i-- > 0 ; ) {
t.table[i] = (this.table[i] != null)
? (Entry)this.table[i].clone() : null;
}
t.keySet = null;
t.entrySet = null;
t.values = null;
t.modCount = 0;
return t;
} catch (CloneNotSupportedException e) {
// this shouldn"t happen, since we are Cloneable
throw new InternalError();
}
}
public Set<K> keySet() {
if (this.keySet == null) {
this.keySet = new AbstractSet<K>() {
public Iterator iterator() {
return createHashIterator(WeakIdentityMap.KEYS);
}
public int size() {
return ReferencedValueHashMap.this.count;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
if (o == null) {
if (ReferencedValueHashMap.this.containsKey(null)) {
ReferencedValueHashMap.this.remove(null);
return true;
} else {
return false;
}
} else {
return ReferencedValueHashMap.this.remove(o) != null;
}
}
public void clear() {
ReferencedValueHashMap.this.clear();
}
public String toString() {
return WeakIdentityMap.toString(this);
}
};
}
return this.keySet;
}
public Collection<V> values() {
if (this.values==null) {
this.values = new AbstractCollection<V>() {
public Iterator iterator() {
return createHashIterator(WeakIdentityMap.VALUES);
}
public int size() {
return ReferencedValueHashMap.this.count;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
ReferencedValueHashMap.this.clear();
}
public String toString() {
return WeakIdentityMap.toString(this);
}
};
}
return this.values;
}
public Set<Map.Entry<K, V>> entrySet() {
if (this.entrySet==null) {
this.entrySet = new AbstractSet<Map.Entry<K, V>>() {
public Iterator iterator() {
return createHashIterator(WeakIdentityMap.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 = ReferencedValueHashMap.this.table;
int hash = key == null ? 0 : key.hashCode();
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
Object entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
ReferencedValueHashMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
ReferencedValueHashMap.this.count--;
} else if (e.hash == 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 = ReferencedValueHashMap.this.table;
int hash = key == null ? 0 : key.hashCode();
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
Object entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
ReferencedValueHashMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
ReferencedValueHashMap.this.count--;
} else if (e.hash == hash && e.equals(entry)) {
ReferencedValueHashMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
ReferencedValueHashMap.this.count--;
e.setValue(null);
return true;
} else {
prev = e;
}
}
return false;
}
public int size() {
return ReferencedValueHashMap.this.count;
}
public void clear() {
ReferencedValueHashMap.this.clear();
}
public String toString() {
return WeakIdentityMap.toString(this);
}
};
}
return this.entrySet;
}
public String toString() {
// Cleanup stale entries first, so as not to allocate a larger than
// necessary StringBuffer.
cleanup();
return WeakIdentityMap.toString(this);
}
abstract Entry<K, V> newEntry(int hash, K key, V value, Entry<K, V> next);
private Iterator createHashIterator(int type) {
if (this.count == 0) {
return Collections.EMPTY_SET.iterator();
} else {
return new HashIterator(type);
}
}
/**
* Collision list entry.
*/
abstract static class Entry<K, V> implements Map.Entry<K, V> {
int hash;
K key;
Entry<K, V> next;
private Reference<V> value;
Entry(int hash, K key, V value, Entry<K, V> next) {
this.hash = hash;
this.key = key;
this.value = newReference(value);
this.next = next;
}
Entry(int hash, K key, Reference<V> value, Entry<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// Map.Entry Ops
public K getKey() {
return this.key;
}
public V getValue() {
V value = this.value.get();
return value == KeyFactory.NULL ? null : value;
}
public V setValue(V value) {
V oldValue = getValue();
this.value = newReference(value == null ? ((V) KeyFactory.NULL) : value);
return oldValue;
}
public boolean equals(Object obj) {
if (!(obj instanceof Map.Entry)) {
return false;
}
return equals((Map.Entry)obj);
}
boolean equals(Map.Entry e) {
Object thisValue = get();
if (thisValue == null) {
return false;
} else if (thisValue == KeyFactory.NULL) {
thisValue = null;
}
return (this.key == null ? e.getKey() == null : this.key.equals(e.getKey())) &&
(thisValue == null ? e.getValue() == null : thisValue.equals(e.getValue()));
}
public int hashCode() {
return this.hash ^ get().hashCode();
}
public String toString() {
return this.key + "=" + getValue();
}
protected Object clone() {
return newEntry(this.hash, this.key, (Reference)this.value,
(this.next == null ? null : (Entry)this.next.clone()));
}
abstract Entry newEntry(int hash, K key, Reference<V> value, Entry<K, V> next);
abstract Reference<V> newReference(V value);
// Like getValue(), except does not convert NULL to null.
V get() {
return this.value.get();
}
}
private class HashIterator implements Iterator {
private final int type;
private final Entry[] table;
private int index;
// 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 entryValue;
private Entry entry;
private Entry last;
/**
* 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 = ReferencedValueHashMap.this.modCount;
HashIterator(int type) {
this.table = ReferencedValueHashMap.this.table;
this.type = type;
this.index = table.length;
}
public boolean hasNext() {
while (this.entry == null || (this.entryValue = this.entry.get()) == null) {
if (this.entry != null) {
// Clean up after a cleared Reference.
remove(this.entry);
this.entry = this.entry.next;
}
if (this.entry == null) {
if (this.index <= 0) {
return false;
} else {
this.entry = this.table[--this.index];
}
}
}
return true;
}
public Object next() {
if (ReferencedValueHashMap.this.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (!hasNext()) {
throw new NoSuchElementException();
}
this.last = this.entry;
this.entry = this.entry.next;
return this.type == WeakIdentityMap.KEYS ? this.last.getKey() :
(this.type == WeakIdentityMap.VALUES ? this.last.getValue() : this.last);
}
public void remove() {
if (this.last == null) {
throw new IllegalStateException();
}
if (ReferencedValueHashMap.this.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
remove(this.last);
this.last = null;
}
private void remove(Entry toRemove) {
Entry[] tab = this.table;
int index = (toRemove.hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
if (e == toRemove) {
ReferencedValueHashMap.this.modCount++;
expectedModCount++;
if (prev == null) {
tab[index] = e.next;
} else {
prev.next = e.next;
}
ReferencedValueHashMap.this.count--;
return;
} else {
prev = e;
}
}
throw new ConcurrentModificationException();
}
}
}
class WeakIdentityMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable {
// Types of Iterators
static final int KEYS = 0;
static final int VALUES = 1;
static final int ENTRIES = 2;
/**
* Converts a collection to string, supporting collections that contain
* self references
*/
static String toString(Collection c) {
if (c.size() == 0) {
return "[]";
}
StringBuffer buf = new StringBuffer(32 * c.size());
buf.append("[");
Iterator it = c.iterator();
boolean hasNext = it.hasNext();
while (hasNext) {
Object obj = it.next();
buf.append(obj == c ? "(this Collection)" : obj);
if (hasNext) {
buf.append(", ");
}
}
buf.append("]");
return buf.toString();
}
/**
* Converts a map to string, supporting maps that contain self references
*/
static String toString(Map m) {
if (m.size() == 0) {
return "{}";
}
StringBuffer buf = new StringBuffer(32 * m.size());
buf.append("{");
Iterator it = m.entrySet().iterator();
boolean hasNext = it.hasNext();
while (hasNext) {
Map.Entry entry = (Map.Entry)it.next();
Object key = entry.getKey();
Object value = entry.getValue();
buf.append(key == m ? "(this Map)" : key)
.append("=")
.append(value == m ? "(this Map)" : value);
hasNext = it.hasNext();
if (hasNext) {
buf.append(",").append(" ");
}
}
buf.append("}");
return buf.toString();
}
private transient Entry<K, V>[] table;
private transient int count;
private int threshold;
private final float loadFactor;
private final ReferenceQueue<K> queue;
private transient volatile int modCount;
// Views
private transient Set<K> keySet;
private transient Set<Map.Entry<K, V>> entrySet;
private transient Collection<V> values;
public WeakIdentityMap(int initialCapacity, float loadFactor) {
if (initialCapacity <= 0) {
throw new IllegalArgumentException("Initial capacity must be greater than 0");
}
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Load factor must be greater than 0");
}
this.loadFactor = loadFactor;
this.table = new Entry[initialCapacity];
this.threshold = (int)(initialCapacity * loadFactor);
this.queue = new ReferenceQueue();
}
public WeakIdentityMap(int initialCapacity) {
this(initialCapacity, 0.75f);
}
public WeakIdentityMap() {
this(11, 0.75f);
}
public WeakIdentityMap(Map<? extends K, ? extends V> t) {
this(Math.max(2 * t.size(), 11), 0.75f);
putAll(t);
}
public int size() {
// Cleanup right before, to report a more accurate size.
cleanup();
return this.count;
}
public boolean isEmpty() {
return this.count == 0;
}
public boolean containsValue(Object value) {
Entry[] tab = this.table;
if (value == null) {
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[i] = e.next;
}
this.count--;
} else if (e.value == null) {
return true;
} else {
prev = e;
}
}
}
} else {
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[i] = e.next;
}
this.count--;
} else if (value.equals(e.value)) {
return true;
} else {
prev = e;
}
}
}
}
return false;
}
public boolean containsKey(Object key) {
if (key == null) {
key = KeyFactory.NULL;
}
Entry[] tab = this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key == entryKey) {
return true;
} else {
prev = e;
}
}
return false;
}
public V get(Object key) {
if (key == null) {
key = KeyFactory.NULL;
}
Entry<K, V>[] tab = this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key == entryKey) {
return e.value;
} else {
prev = e;
}
}
return null;
}
private void cleanup() {
// Cleanup after cleared References.
Entry[] tab = this.table;
ReferenceQueue queue = this.queue;
Reference ref;
while ((ref = queue.poll()) != null) {
// Since buckets are single-linked, traverse entire list and
// cleanup all cleared references in it.
int index = (((Entry) ref).hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
if (e.get() == null) {
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else {
prev = e;
}
}
}
}
private void rehash() {
int oldCapacity = this.table.length;
Entry[] oldMap = this.table;
int newCapacity = oldCapacity * 2 + 1;
if (newCapacity <= 0) {
// Overflow.
if ((newCapacity = Integer.MAX_VALUE) == oldCapacity) {
return;
}
}
Entry[] newMap = new Entry[newCapacity];
this.modCount++;
this.threshold = (int)(newCapacity * this.loadFactor);
this.table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry old = oldMap[i] ; old != null ; ) {
Entry e = old;
old = old.next;
// Only copy entry if its key hasn"t been cleared.
if (e.get() == null) {
this.count--;
} else {
int index = (e.hash & 0x7fffffff) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}
}
public V put(K key, V value) {
if (key == null) {
key = (K) KeyFactory.NULL;
}
cleanup();
// Make sure the key is not already in the WeakIdentityMap.
Entry[] tab = this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key == entryKey) {
Object old = e.value;
e.value = value;
return (V) old;
} else {
prev = e;
}
}
this.modCount++;
if (this.count >= this.threshold) {
// Rehash the table if the threshold is still exceeded.
rehash();
tab = this.table;
index = (hash & 0x7fffffff) % tab.length;
}
// Creates the new entry.
Entry e = new Entry(hash, key, this.queue, value, tab[index]);
tab[index] = e;
this.count++;
return null;
}
public V remove(Object key) {
if (key == null) {
key = KeyFactory.NULL;
}
Entry<K, V>[] tab = this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key == entryKey) {
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
V oldValue = e.value;
e.value = null;
return oldValue;
} else {
prev = e;
}
}
return null;
}
public void putAll(Map<? extends K, ? extends V> t) {
Iterator i = t.entrySet().iterator();
while (i.hasNext()) {
Map.Entry e = (Map.Entry) i.next();
put((K) e.getKey(), (V) e.getValue());
}
}
public void clear() {
Entry[] tab = this.table;
this.modCount++;
for (int index = tab.length; --index >= 0; ) {
tab[index] = null;
}
this.count = 0;
}
public Object clone() {
try {
WeakIdentityMap t = (WeakIdentityMap)super.clone();
t.table = new Entry[this.table.length];
for (int i = this.table.length ; i-- > 0 ; ) {
t.table[i] = (this.table[i] != null)
? (Entry)this.table[i].copy(this.queue) : null;
}
t.keySet = null;
t.entrySet = null;
t.values = null;
t.modCount = 0;
return t;
}
catch (CloneNotSupportedException e) {
// this shouldn"t happen, since we are Cloneable
throw new InternalError();
}
}
public Set<K> keySet() {
if (this.keySet == null) {
this.keySet = new AbstractSet<K>() {
public Iterator iterator() {
return createHashIterator(KEYS);
}
public int size() {
return WeakIdentityMap.this.count;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return o == null ? false : WeakIdentityMap.this.remove(o) == o;
}
public void clear() {
WeakIdentityMap.this.clear();
}
public String toString() {
return WeakIdentityMap.this.toString(this);
}
};
}
return this.keySet;
}
public Collection<V> values() {
if (this.values==null) {
this.values = new AbstractCollection<V>() {
public Iterator<V> iterator() {
return createHashIterator(VALUES);
}
public int size() {
return WeakIdentityMap.this.count;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
WeakIdentityMap.this.clear();
}
public String toString() {
return WeakIdentityMap.this.toString(this);
}
};
}
return this.values;
}
public Set<Map.Entry<K, V>> entrySet() {
if (this.entrySet==null) {
this.entrySet = new AbstractSet<Map.Entry<K, V>>() {
public Iterator<Map.Entry<K, V>> iterator() {
return createHashIterator(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 = WeakIdentityMap.this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
WeakIdentityMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
WeakIdentityMap.this.count--;
} else if (e.hash == 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 = WeakIdentityMap.this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
WeakIdentityMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
WeakIdentityMap.this.count--;
} else if (e.hash == hash && e.equals(entry)) {
WeakIdentityMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
WeakIdentityMap.this.count--;
e.value = null;
return true;
} else {
prev = e;
}
}
return false;
}
public int size() {
return WeakIdentityMap.this.count;
}
public void clear() {
WeakIdentityMap.this.clear();
}
public String toString() {
return WeakIdentityMap.toString(this);
}
};
}
return this.entrySet;
}
/**
* Gets the map as a String.
*
* @return a string version of the map
*/
public String toString() {
return toString(this);
}
private Iterator createHashIterator(int type) {
if (this.count == 0) {
return Collections.EMPTY_SET.iterator();
} else {
return new HashIterator(type);
}
}
/**
* WeakIdentityMap collision list entry.
*/
private static class Entry<K, V> extends WeakReference<K> implements Map.Entry<K, V> {
int hash;
V value;
Entry<K, V> next;
Entry(int hash, K key, ReferenceQueue<K> queue, V value, Entry<K, V> next) {
super(key, queue);
this.hash = hash;
this.value = value;
this.next = next;
}
public void clear() {
// Do nothing if reference is explicity cleared. This prevents
// backdoor modification of map entries.
}
public K getKey() {
K key = Entry.this.get();
return key == KeyFactory.NULL ? null : key;
}
public V getValue() {
return this.value;
}
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object obj) {
if (!(obj instanceof Map.Entry)) {
return false;
}
return equals((Map.Entry)obj);
}
boolean equals(Map.Entry<K, V> e) {
Object thisKey = get();
if (thisKey == null) {
return false;
} else if (thisKey == KeyFactory.NULL) {
thisKey = null;
}
return (thisKey == e.getKey()) &&
(this.value == null ? e.getValue() == null : this.value.equals(e.getValue()));
}
public int hashCode() {
return this.hash ^ (this.value == null ? 0 : this.value.hashCode());
}
public String toString() {
return getKey() + "=" + this.value;
}
protected Object copy(ReferenceQueue queue) {
return new Entry(this.hash, get(), queue, this.value,
(this.next == null ? null : (Entry)this.next.copy(queue)));
}
}
private class HashIterator implements Iterator {
private final int type;
private final Entry[] table;
private int index;
// To ensure that the iterator doesn"t return cleared entries, keep a
// hard reference to the key. Its existence will prevent the weak
// key from being cleared.
Object entryKey;
Entry entry;
Entry last;
/**
* 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 = WeakIdentityMap.this.modCount;
HashIterator(int type) {
this.table = WeakIdentityMap.this.table;
this.type = type;
this.index = table.length;
}
public boolean hasNext() {
while (this.entry == null || (this.entryKey = this.entry.get()) == null) {
if (this.entry != null) {
// Clean up after a cleared Reference.
remove(this.entry);
this.entry = this.entry.next;
}
else {
if (this.index <= 0) {
return false;
}
else {
this.entry = this.table[--this.index];
}
}
}
return true;
}
public Object next() {
if (WeakIdentityMap.this.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
}
if (!hasNext()) {
throw new NoSuchElementException();
}
this.last = this.entry;
this.entry = this.entry.next;
return this.type == KEYS ? this.last.getKey() :
(this.type == VALUES ? this.last.getValue() : this.last);
}
public void remove() {
if (this.last == null) {
throw new IllegalStateException();
}
if (WeakIdentityMap.this.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
}
remove(this.last);
this.last = null;
}
private void remove(Entry toRemove) {
Entry[] tab = this.table;
int index = (toRemove.hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
if (e == toRemove) {
WeakIdentityMap.this.modCount++;
expectedModCount++;
if (prev == null) {
tab[index] = e.next;
} else {
prev.next = e.next;
}
WeakIdentityMap.this.count--;
return;
} else {
prev = e;
}
}
throw new ConcurrentModificationException();
}
public String toString() {
if (this.last != null) {
return "Iterator[" + this.last + "]";
} else {
return "Iterator[]";
}
}
}
} /*
- Copyright 2004 Brian S O"Neill
- 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.
- /
/**
- KeyFactory generates keys which can be hashed or compared for any kind of
- object including arrays, arrays of arrays, and null. All hashcode
- computations, equality tests, and ordering comparsisons fully recurse into
- arrays.
- @author Brian S O"Neill
- /
class KeyFactory {
static final Object NULL = new Comparable() {
public int compareTo(Object obj) {
return obj == this || obj == null ? 0 : 1;
}
};
public static Object createKey(boolean[] obj) {
return obj == null ? NULL : new BooleanArrayKey(obj);
}
public static Object createKey(byte[] obj) {
return obj == null ? NULL : new ByteArrayKey(obj);
}
public static Object createKey(char[] obj) {
return obj == null ? NULL : new CharArrayKey(obj);
}
public static Object createKey(double[] obj) {
return obj == null ? NULL : new DoubleArrayKey(obj);
}
public static Object createKey(float[] obj) {
return obj == null ? NULL : new FloatArrayKey(obj);
}
public static Object createKey(int[] obj) {
return obj == null ? NULL : new IntArrayKey(obj);
}
public static Object createKey(long[] obj) {
return obj == null ? NULL : new LongArrayKey(obj);
}
public static Object createKey(short[] obj) {
return obj == null ? NULL : new ShortArrayKey(obj);
}
public static Object createKey(Object[] obj) {
return obj == null ? NULL : new ObjectArrayKey(obj);
}
public static Object createKey(Object obj) {
if (obj == null) {
return NULL;
}
if (!obj.getClass().isArray()) {
return obj;
}
if (obj instanceof Object[]) {
return createKey((Object[])obj);
} else if (obj instanceof int[]) {
return createKey((int[])obj);
} else if (obj instanceof float[]) {
return createKey((float[])obj);
} else if (obj instanceof long[]) {
return createKey((long[])obj);
} else if (obj instanceof double[]) {
return createKey((double[])obj);
} else if (obj instanceof byte[]) {
return createKey((byte[])obj);
} else if (obj instanceof char[]) {
return createKey((char[])obj);
} else if (obj instanceof boolean[]) {
return createKey((boolean[])obj);
} else if (obj instanceof short[]) {
return createKey((short[])obj);
} else {
return obj;
}
}
static int hashCode(boolean[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + (a[i] ? 0 : 1);
}
return hash == 0 ? -1 : hash;
}
static int hashCode(byte[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + a[i];
}
return hash == 0 ? -1 : hash;
}
static int hashCode(char[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + a[i];
}
return hash == 0 ? -1 : hash;
}
static int hashCode(double[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
long v = Double.doubleToLongBits(a[i]);
hash = hash * 31 + (int)(v ^ v >>> 32);
}
return hash == 0 ? -1 : hash;
}
static int hashCode(float[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = hash * 31 + Float.floatToIntBits(a[i]);
}
return hash == 0 ? -1 : hash;
}
static int hashCode(int[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + a[i];
}
return hash == 0 ? -1 : hash;
}
static int hashCode(long[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
long v = a[i];
hash = hash * 31 + (int)(v ^ v >>> 32);
}
return hash == 0 ? -1 : hash;
}
static int hashCode(short[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + a[i];
}
return hash == 0 ? -1 : hash;
}
static int hashCode(Object[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = hash * 31 + hashCode(a[i]);
}
return hash == 0 ? -1 : hash;
}
// Compute object or array hashcode and recurses into arrays within.
static int hashCode(Object a) {
if (a == null) {
return -1;
}
if (!a.getClass().isArray()) {
return a.hashCode();
}
if (a instanceof Object[]) {
return hashCode((Object[])a);
} else if (a instanceof int[]) {
return hashCode((int[])a);
} else if (a instanceof float[]) {
return hashCode((float[])a);
} else if (a instanceof long[]) {
return hashCode((long[])a);
} else if (a instanceof double[]) {
return hashCode((double[])a);
} else if (a instanceof byte[]) {
return hashCode((byte[])a);
} else if (a instanceof char[]) {
return hashCode((char[])a);
} else if (a instanceof boolean[]) {
return hashCode((boolean[])a);
} else if (a instanceof short[]) {
return hashCode((short[])a);
} else {
int hash = a.getClass().hashCode();
return hash == 0 ? -1 : hash;
}
}
// Compares object arrays and recurses into arrays within.
static boolean equals(Object[] a, Object[] b) {
if (a == b) {
return true;
}
if (a == null || b == null) {
return false;
}
int i;
if ((i = a.length) != b.length) {
return false;
}
while (--i >= 0) {
if (!equals(a[i], b[i])) {
return false;
}
}
return true;
}
// Compares objects or arrays and recurses into arrays within.
static boolean equals(Object a, Object b) {
if (a == b) {
return true;
}
if (a == null || b == null) {
return false;
}
Class ac = a.getClass();
if (!(ac.isArray())) {
return a.equals(b);
}
if (ac != b.getClass()) {
return false;
}
if (a instanceof Object[]) {
return equals((Object[])a, (Object[])b);
} else if (a instanceof int[]) {
return Arrays.equals((int[])a, (int[])b);
} else if (a instanceof float[]) {
return Arrays.equals((float[])a, (float[])b);
} else if (a instanceof long[]) {
return Arrays.equals((long[])a, (long[])b);
} else if (a instanceof double[]) {
return Arrays.equals((double[])a, (double[])b);
} else if (a instanceof byte[]) {
return Arrays.equals((byte[])a, (byte[])b);
} else if (a instanceof char[]) {
return Arrays.equals((char[])a, (char[])b);
} else if (a instanceof boolean[]) {
return Arrays.equals((boolean[])a, (boolean[])b);
} else if (a instanceof short[]) {
return Arrays.equals((short[])a, (short[])b);
} else {
return a.equals(b);
}
}
static int compare(boolean[] a, boolean[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int av = a[i] ? 0 : 1;
int bv = b[i] ? 0 : 1;
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(byte[] a, byte[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
byte av = a[i];
byte bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(char[] a, char[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
char av = a[i];
char bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(double[] a, double[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int v = Double.rupare(a[i], b[i]);
if (v != 0) {
return v;
}
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(float[] a, float[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int v = Float.rupare(a[i], b[i]);
if (v != 0) {
return v;
}
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(int[] a, int[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int av = a[i];
int bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(long[] a, long[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
long av = a[i];
long bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(short[] a, short[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
short av = a[i];
short bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
// Compares object arrays and recurses into arrays within.
static int compare(Object[] a, Object[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int v = compare(a[i], b[i]);
if (v != 0) {
return v;
}
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
// Compares objects or arrays and recurses into arrays within.
static int compare(Object a, Object b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
Class ac = a.getClass();
if (!(ac.isArray())) {
return ((Comparable)a).rupareTo(b);
}
if (ac != b.getClass()) {
throw new ClassCastException();
}
if (a instanceof Object[]) {
return compare((Object[])a, (Object[])b);
} else if (a instanceof int[]) {
return compare((int[])a, (int[])b);
} else if (a instanceof float[]) {
return compare((float[])a, (float[])b);
} else if (a instanceof long[]) {
return compare((long[])a, (long[])b);
} else if (a instanceof double[]) {
return compare((double[])a, (double[])b);
} else if (a instanceof byte[]) {
return compare((byte[])a, (byte[])b);
} else if (a instanceof char[]) {
return compare((char[])a, (char[])b);
} else if (a instanceof boolean[]) {
return compare((boolean[])a, (boolean[])b);
} else if (a instanceof short[]) {
return compare((short[])a, (short[])b);
} else {
throw new ClassCastException();
}
}
protected KeyFactory() {
}
private static interface ArrayKey extends Comparable, java.io.Serializable {
int hashCode();
boolean equals(Object obj);
int compareTo(Object obj);
}
private static class BooleanArrayKey implements ArrayKey {
protected final boolean[] mArray;
private transient int mHash;
BooleanArrayKey(boolean[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof BooleanArrayKey ?
Arrays.equals(mArray, ((BooleanArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((BooleanArrayKey) obj).mArray);
}
}
private static class ByteArrayKey implements ArrayKey {
protected final byte[] mArray;
private transient int mHash;
ByteArrayKey(byte[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof ByteArrayKey ?
Arrays.equals(mArray, ((ByteArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((ByteArrayKey) obj).mArray);
}
}
private static class CharArrayKey implements ArrayKey {
protected final char[] mArray;
private transient int mHash;
CharArrayKey(char[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof CharArrayKey ?
Arrays.equals(mArray, ((CharArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((CharArrayKey) obj).mArray);
}
}
private static class DoubleArrayKey implements ArrayKey {
protected final double[] mArray;
private transient int mHash;
DoubleArrayKey(double[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof DoubleArrayKey ?
Arrays.equals(mArray, ((DoubleArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((DoubleArrayKey) obj).mArray);
}
}
private static class FloatArrayKey implements ArrayKey {
protected final float[] mArray;
private transient int mHash;
FloatArrayKey(float[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof FloatArrayKey ?
Arrays.equals(mArray, ((FloatArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((FloatArrayKey) obj).mArray);
}
}
private static class IntArrayKey implements ArrayKey {
protected final int[] mArray;
private transient int mHash;
IntArrayKey(int[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof IntArrayKey ?
Arrays.equals(mArray, ((IntArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((IntArrayKey) obj).mArray);
}
}
private static class LongArrayKey implements ArrayKey {
protected final long[] mArray;
private transient int mHash;
LongArrayKey(long[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof LongArrayKey ?
Arrays.equals(mArray, ((LongArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((LongArrayKey) obj).mArray);
}
}
private static class ShortArrayKey implements ArrayKey {
protected final short[] mArray;
private transient int mHash;
ShortArrayKey(short[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof ShortArrayKey ?
Arrays.equals(mArray, ((ShortArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((ShortArrayKey) obj).mArray);
}
}
private static class ObjectArrayKey implements ArrayKey {
protected final Object[] mArray;
private transient int mHash;
ObjectArrayKey(Object[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof ObjectArrayKey ?
KeyFactory.equals(mArray, ((ObjectArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((ObjectArrayKey) obj).mArray);
}
}
}
</source>
Weak Value HashMap
<source lang="java">
/*
* The contents of this file are subject to the terms * of the Common Development and Distribution License * (the "License"). You may not use this file except * in compliance with the License. * * You can obtain a copy of the license at * glassfish/bootstrap/legal/CDDLv1.0.txt or * https://glassfish.dev.java.net/public/CDDLv1.0.html. * See the License for the specific language governing * permissions and limitations under the License. * * When distributing Covered Code, include this CDDL * HEADER in each file and include the License file at * glassfish/bootstrap/legal/CDDLv1.0.txt. If applicable, * add the following below this CDDL HEADER, with the * fields enclosed by brackets "[]" replaced with your * own identifying information: Portions Copyright [yyyy] * [name of copyright owner] */
/*
* Copyright 2005 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. */
import java.lang.ref.ReferenceQueue; import java.lang.ref.WeakReference; import java.util.AbstractCollection; import java.util.AbstractSet; import java.util.Collection; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; /**
* A WeakValueHashMap is implemented as a HashMap that maps keys to * WeakValues. Because we don"t have access to the innards of the * HashMap, we have to wrap/unwrap value objects with WeakValues on * every operation. Fortunately WeakValues are small, short-lived * objects, so the added allocation overhead is tolerable. This * implementaton directly extends java.util.HashMap. * * @author Markus Fuchs * @see java.util.HashMap * @see java.lang.ref.WeakReference */
public class WeakValueHashMap extends HashMap {
/* Reference queue for cleared WeakValues */
private ReferenceQueue queue = new ReferenceQueue();
/**
* Returns the number of key-value mappings in this map.<p>
* @return the number of key-value mappings in this map.
*/
public int size() {
// delegate to entrySet, as super.size() also counts WeakValues
return entrySet().size();
}
/**
* Returns true if this map contains no key-value mappings.<p>
* @return true if this map contains no key-value mappings.
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* Returns true if this map contains a mapping for the specified
* key.<p>
* @param key key whose presence in this map is to be tested
* @return true if this map contains a mapping for the specified
* key.
*/
public boolean containsKey(Object key) {
// need to clean up gc"ed values before invoking super method
processQueue();
return super.containsKey(key);
}
/**
* Returns true if this map maps one or more keys to the
* specified value.<p>
* @param value value whose presence in this map is to be tested
* @return true if this map maps one or more keys to this value.
*/
public boolean containsValue(Object value) {
return super.containsValue(WeakValue.create(value));
}
/**
* Gets the value for the given key.<p>
* @param key key whose associated value, if any, is to be returned
* @return the value to which this map maps the specified key.
*/
public Object get(Object key) {
// We don"t need to remove garbage collected values here;
// if they are garbage collected, the get() method returns null;
// the next put() call with the same key removes the old value
// automatically so that it can be completely garbage collected
return getReferenceObject((WeakReference) super.get(key));
}
/**
* Puts a new (key,value) into the map.<p>
* @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 null
* if there was no mapping for key or the value has been garbage
* collected by the garbage collector.
*/
public Object put(Object key, Object value) {
// If the map already contains an equivalent key, the new key
// of a (key, value) pair is NOT stored in the map but the new
// value only. But as the key is strongly referenced by the
// map, it can not be removed from the garbage collector, even
// if the key becomes weakly reachable due to the old
// value. So, it isn"t necessary to remove all garbage
// collected values with their keys from the map before the
// new entry is made. We only clean up here to distribute
// clean up calls on different operations.
processQueue();
WeakValue oldValue =
(WeakValue)super.put(key, WeakValue.create(key, value, queue));
return getReferenceObject(oldValue);
}
/**
* Removes key and value for the given key.<p>
* @param key key whose mapping is to be removed from the map.
* @return previous value associated with specified key, or null
* if there was no mapping for key or the value has been garbage
* collected by the garbage collector.
*/
public Object remove(Object key) {
return getReferenceObject((WeakReference) super.remove(key));
}
/**
* A convenience method to return the object held by the
* weak reference or null if it does not exist.
*/
private final Object getReferenceObject(WeakReference ref) {
return (ref == null) ? null : ref.get();
}
/**
* Removes all garbage collected values with their keys from the map.
* Since we don"t know how much the ReferenceQueue.poll() operation
* costs, we should not call it every map operation.
*/
private void processQueue() {
WeakValue wv = null;
while ((wv = (WeakValue) this.queue.poll()) != null) {
// "super" is not really necessary but use it
// to be on the safe side
super.remove(wv.key);
}
}
/* -- Helper classes -- */
/**
* We need this special class to keep the backward reference from
* the value to the key, so that we are able to remove the key if
* the value is garbage collected.
*/
private static class WeakValue extends WeakReference {
/**
* It"s the same as the key in the map. We need the key to remove
* the value if it is garbage collected.
*/
private Object key;
private WeakValue(Object value) {
super(value);
}
/**
* Creates a new weak reference without adding it to a
* ReferenceQueue.
*/
private static WeakValue create(Object value) {
if (value == null) return null;
else return new WeakValue(value);
}
private WeakValue(Object key, Object value, ReferenceQueue queue) {
super(value, queue);
this.key = key;
}
/**
* Creates a new weak reference and adds it to the given queue.
*/
private static WeakValue create(Object key, Object value,
ReferenceQueue queue) {
if (value == null) return null;
else return new WeakValue(key, value, queue);
}
/**
* A WeakValue is equal to another WeakValue iff they both refer
* to objects that are, in turn, equal according to their own
* equals methods.
*/
public boolean equals(Object obj) {
if (this == obj)
return true;
if (!(obj instanceof WeakValue))
return false;
Object ref1 = this.get();
Object ref2 = ((WeakValue) obj).get();
if (ref1 == ref2)
return true;
if ((ref1 == null) || (ref2 == null))
return false;
return ref1.equals(ref2);
}
/**
*
*/
public int hashCode() {
Object ref = this.get();
return (ref == null) ? 0 : ref.hashCode();
}
}
/**
* Internal class for entries. This class wraps/unwraps the
* values of the Entry objects returned from the underlying map.
*/
private class Entry implements Map.Entry {
private Map.Entry ent;
private Object value; /* Strong reference to value, so that the
GC will leave it alone as long as this
Entry exists */
Entry(Map.Entry ent, Object value) {
this.ent = ent;
this.value = value;
}
public Object getKey() {
return ent.getKey();
}
public Object getValue() {
return value;
}
public Object setValue(Object value) {
// This call changes the map. Please see the comment on
// the put method for the correctness remark.
Object oldValue = this.value;
this.value = value;
ent.setValue(WeakValue.create(getKey(), value, queue));
return oldValue;
}
private boolean valEquals(Object o1, Object o2) {
return (o1 == null) ? (o2 == null) : o1.equals(o2);
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry)) return false;
Map.Entry e = (Map.Entry) o;
return (valEquals(ent.getKey(), e.getKey())
&& valEquals(value, e.getValue()));
}
public int hashCode() {
Object k;
return ((((k = ent.getKey()) == null) ? 0 : k.hashCode())
^ ((value == null) ? 0 : value.hashCode()));
}
}
/**
* Internal class for entry sets to unwrap/wrap WeakValues stored
* in the map.
*/
private class EntrySet extends AbstractSet {
public Iterator iterator() {
// remove garbage collected elements
processQueue();
return new Iterator() {
Iterator hashIterator = hashEntrySet.iterator();
Entry next = null;
public boolean hasNext() {
if (hashIterator.hasNext()) {
// since we removed garbage collected elements,
// we can simply return the next entry.
Map.Entry ent = (Map.Entry) hashIterator.next();
WeakValue wv = (WeakValue) ent.getValue();
Object v = (wv == null) ? null : wv.get();
next = new Entry(ent, v);
return true;
}
return false;
}
public Object next() {
if ((next == null) && !hasNext())
throw new NoSuchElementException();
Entry e = next;
next = null;
return e;
}
public void remove() {
hashIterator.remove();
}
};
}
public boolean isEmpty() {
return !(iterator().hasNext());
}
public int size() {
int j = 0;
for (Iterator i = iterator(); i.hasNext(); i.next()) j++;
return j;
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry)) return false;
Map.Entry e = (Map.Entry) o;
Object ek = e.getKey();
Object ev = e.getValue();
Object hv = WeakValueHashMap.this.get(ek);
if (hv == null) {
// if the map"s value is null, we have to check, if the
// entry"s value is null and the map contains the key
if ((ev == null) && WeakValueHashMap.this.containsKey(ek)) {
WeakValueHashMap.this.remove(ek);
return true;
} else {
return false;
}
// otherwise, simply compare the values
} else if (hv.equals(ev)) {
WeakValueHashMap.this.remove(ek);
return true;
}
return false;
}
public int hashCode() {
int h = 0;
for (Iterator i = hashEntrySet.iterator(); i.hasNext(); ) {
Map.Entry ent = (Map.Entry) i.next();
Object k;
WeakValue wv = (WeakValue) ent.getValue();
if (wv == null) continue;
h += ((((k = ent.getKey()) == null) ? 0 : k.hashCode())
^ wv.hashCode());
}
return h;
}
}
// internal helper variable, because we can"t access
// entrySet from the superclass inside the EntrySet class
private Set hashEntrySet = null;
// stores the EntrySet instance
private Set entrySet = null;
/**
* Returns a Set view of the mappings in this map.<p>
* @return a Set view of the mappings in this map.
*/
public Set entrySet() {
if (entrySet == null) {
hashEntrySet = super.entrySet();
entrySet = new EntrySet();
}
return entrySet;
}
// stores the value collection
private transient Collection values = null;
/**
* Returns a Collection view of the values contained
* in this map.<p>
* @return a Collection view of the values contained
* in this map.
*/
public Collection values() {
// delegates to entrySet, because super method returns
// WeakValues instead of value objects
if (values == null) {
values = new AbstractCollection() {
public Iterator iterator() {
return new Iterator() {
private Iterator i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public Object next() {
return ((Entry)i.next()).getValue();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return WeakValueHashMap.this.size();
}
public boolean contains(Object v) {
return WeakValueHashMap.this.containsValue(v);
}
};
}
return values;
}
}
</source>
Weak ValueMap
<source lang="java">
/*
* Copyright 2002-2006 (C) TJDO. * All rights reserved. * * This software is distributed under the terms of the TJDO License version 1.0. * See the terms of the TJDO License in the documentation provided with this software. * * $Id: WeakValueMap.java,v 1.5 2006/09/08 16:11:28 jackknifebarber Exp $ */
import java.lang.ref.Reference; import java.lang.ref.ReferenceQueue; import java.lang.ref.WeakReference; import java.util.AbstractMap; import java.util.AbstractSet; import java.util.Collection; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Set;
/**
* A java.util.Map implementation with weak values.
* <p>
* The values are stored in the map as weak references.
* If the garbage collector clears the reference, the corresponding key is
* automatically removed from the map.
*
* @author
* @version $Revision: 1.8 $
*/
abstract class ReferenceValueMap extends AbstractMap {
protected final ReferenceQueue refQueue = new ReferenceQueue();
/** Backing map. */
private final Map backing;
ReferenceValueMap(Map backing)
{
this.backing = backing;
}
/**
* Returns a new Reference object to be inserted into the map.
* Subclasses must implement this method to construct Reference
* objects of the desired type (e.g. SoftReference, etc.).
*
* @param value
* The associated value to be referenced.
*
* @return
* A new Reference object to be inserted into the map.
*/
protected abstract Reference newReference(Object value);
private void reap()
{
Reference ref;
while ((ref = refQueue.poll()) != null)
backing.values().remove(ref);
}
public Object put(Object key, Object value)
{
reap();
return backing.put(key, newReference(value));
}
public Object get(Object key)
{
reap();
Object v = backing.get(key);
return (v instanceof Reference) ? ((Reference)v).get() : v;
}
public int size()
{
reap();
return backing.size();
}
public boolean isEmpty()
{
reap();
return backing.isEmpty();
}
public boolean containsKey(Object key)
{
reap();
return backing.containsKey(key);
}
public boolean containsValue(Object value)
{
reap();
return super.containsValue(value);
}
public Set keySet()
{
reap();
return backing.keySet();
}
public Collection values()
{
reap();
return super.values();
}
public Set entrySet()
{
reap();
return new EntrySet();
}
public Object remove(Object key)
{
reap();
return backing.remove(key);
}
public int hashCode()
{
reap();
return super.hashCode();
}
public boolean equals(Object o)
{
reap();
return super.equals(o);
}
public String toString()
{
reap();
return super.toString();
}
static boolean eq(Object o1, Object o2)
{
return o1 == null ? o2 == null : o1.equals(o2);
}
private class EntrySet extends AbstractSet
{
/** Backing set. */
private final Set set = backing.entrySet();
public Iterator iterator()
{
return new Iterator()
{
private Iterator i = set.iterator();
public boolean hasNext()
{
return i.hasNext();
}
public void remove()
{
i.remove();
}
public Object next()
{
final Map.Entry ent = (Map.Entry)i.next();
return new Map.Entry()
{
public Object getKey()
{
return ent.getKey();
}
public Object getValue()
{
Object v = ent.getValue();
return (v instanceof Reference) ? ((Reference)v).get() : v;
}
public Object setValue(Object v)
{
Object oldVal = getValue();
ent.setValue(newReference(v));
return oldVal;
}
public boolean equals(Object o)
{
if (o == this)
return true;
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
return eq(ent.getKey(), e.getKey())
&& eq(ent.getValue(), e.getValue());
}
public int hashCode()
{
Object key = ent.getKey();
Object val = ent.getValue();
return (key == null ? 0 : key.hashCode())
^ (val == null ? 0 : val.hashCode());
}
public String toString()
{
return ent.getKey() + "=" + ent.getValue();
}
};
}
};
}
public int size()
{
reap();
return set.size();
}
public boolean isEmpty()
{
reap();
return set.isEmpty();
}
public boolean contains(Object o)
{
reap();
return super.contains(o);
}
public Object[] toArray()
{
reap();
return super.toArray();
}
public Object[] toArray(Object[] a)
{
reap();
return super.toArray(a);
}
public boolean remove(Object o)
{
reap();
return super.remove(o);
}
public boolean containsAll(Collection c)
{
reap();
return super.containsAll(c);
}
public boolean removeAll(Collection c)
{
reap();
return super.removeAll(c);
}
public boolean retainAll(Collection c)
{
reap();
return super.retainAll(c);
}
public void clear()
{
set.clear();
}
public String toString()
{
reap();
return super.toString();
}
}
}
</source>
