/* | |
* 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. | |
*/ | |
package org.codehaus.groovy.runtime.metaclass; | |
import java.util.Map; | |
import java.util.AbstractMap; | |
import java.util.AbstractSet; | |
import java.util.AbstractCollection; | |
import java.util.Collection; | |
import java.util.Set; | |
import java.util.ArrayList; | |
import java.util.Iterator; | |
import java.util.Enumeration; | |
import java.util.NoSuchElementException; | |
import java.io.Serializable; | |
import java.io.IOException; | |
/** | |
* A hash table that supports mostly-concurrent reading, but | |
* exclusive writing. Because reads are not limited to periods | |
* without writes, a concurrent reader policy is weaker than a classic | |
* reader/writer policy, but is generally faster and allows more | |
* concurrency. This class is a good choice especially for tables that | |
* are mainly created by one thread during the start-up phase of a | |
* program, and from then on, are mainly read (with perhaps occasional | |
* additions or removals) in many threads. If you also need concurrency | |
* among writes, consider instead using ConcurrentHashMap. | |
* <p> | |
* | |
* Successful retrievals using get(key) and containsKey(key) usually | |
* run without locking. Unsuccessful ones (i.e., when the key is not | |
* present) do involve brief synchronization (locking). Also, the | |
* size and isEmpty methods are always synchronized. | |
* | |
* <p> Because retrieval operations can ordinarily overlap with | |
* writing operations (i.e., put, remove, and their derivatives), | |
* retrievals can only be guaranteed to return the results of the most | |
* recently <em>completed</em> operations holding upon their | |
* onset. Retrieval operations may or may not return results | |
* reflecting in-progress writing operations. However, the retrieval | |
* operations do always return consistent results -- either those | |
* holding before any single modification or after it, but never a | |
* nonsense result. For aggregate operations such as putAll and | |
* clear, concurrent reads may reflect insertion or removal of only | |
* some entries. In those rare contexts in which you use a hash table | |
* to synchronize operations across threads (for example, to prevent | |
* reads until after clears), you should either encase operations | |
* in synchronized blocks, or instead use java.util.Hashtable. | |
* | |
* <p> | |
* | |
* This class also supports optional guaranteed | |
* exclusive reads, simply by surrounding a call within a synchronized | |
* block, as in <br> | |
* <code>ConcurrentReaderHashMap t; ... Object v; <br> | |
* synchronized(t) { v = t.get(k); } </code> <br> | |
* | |
* But this is not usually necessary in practice. For | |
* example, it is generally inefficient to write: | |
* | |
* <pre> | |
* ConcurrentReaderHashMap t; ... // Inefficient version | |
* Object key; ... | |
* Object value; ... | |
* synchronized(t) { | |
* if (!t.containsKey(key)) | |
* t.put(key, value); | |
* // other code if not previously present | |
* } | |
* else { | |
* // other code if it was previously present | |
* } | |
* } | |
*</pre> | |
* Instead, if the values are intended to be the same in each case, just take advantage of the fact that put returns | |
* null if the key was not previously present: | |
* <pre> | |
* ConcurrentReaderHashMap t; ... // Use this instead | |
* Object key; ... | |
* Object value; ... | |
* Object oldValue = t.put(key, value); | |
* if (oldValue == null) { | |
* // other code if not previously present | |
* } | |
* else { | |
* // other code if it was previously present | |
* } | |
*</pre> | |
* <p> | |
* | |
* Iterators and Enumerations (i.e., those returned by | |
* keySet().iterator(), entrySet().iterator(), values().iterator(), | |
* keys(), and elements()) return elements reflecting the state of the | |
* hash table at some point at or since the creation of the | |
* iterator/enumeration. They will return at most one instance of | |
* each element (via next()/nextElement()), but might or might not | |
* reflect puts and removes that have been processed since they were | |
* created. They do <em>not</em> throw ConcurrentModificationException. | |
* However, these iterators are designed to be used by only one | |
* thread at a time. Sharing an iterator across multiple threads may | |
* lead to unpredictable results if the table is being concurrently | |
* modified. Again, you can ensure interference-free iteration by | |
* enclosing the iteration in a synchronized block. <p> | |
* | |
* This class may be used as a direct replacement for any use of | |
* java.util.Hashtable that does not depend on readers being blocked | |
* during updates. Like Hashtable but unlike java.util.HashMap, | |
* this class does NOT allow <tt>null</tt> to be used as a key or | |
* value. This class is also typically faster than ConcurrentHashMap | |
* when there is usually only one thread updating the table, but | |
* possibly many retrieving values from it. | |
* <p> | |
* | |
* Implementation note: A slightly faster implementation of | |
* this class will be possible once planned Java Memory Model | |
* revisions are in place. | |
* | |
* <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>] | |
* | |
* @author Adapted from ConcurrentHashMap (Doug Lea) | |
* @author adapted by the Groovy community | |
*/ | |
public class ConcurrentReaderHashMap | |
extends AbstractMap | |
implements Cloneable, Serializable { | |
/* | |
The basic strategy is an optimistic-style scheme based on | |
the guarantee that the hash table and its lists are always | |
kept in a consistent enough state to be read without locking: | |
* Read operations first proceed without locking, by traversing the | |
apparently correct list of the apparently correct bin. If an | |
entry is found, but not invalidated (value field null), it is | |
returned. If not found, operations must recheck (after a memory | |
barrier) to make sure they are using both the right list and | |
the right table (which can change under re-sizes). If | |
invalidated, reads must acquire main update lock to wait out | |
the update, and then re-traverse. | |
* All list additions are at the front of each bin, making it easy | |
to check changes, and also fast to traverse. Entry next | |
pointers are never assigned. Remove() builds new nodes when | |
necessary to preserve this. | |
* Remove() (also clear()) invalidates removed nodes to alert read | |
operations that they must wait out the full modifications. | |
*/ | |
/** A Serializable class for barrier lock **/ | |
protected static class BarrierLock implements java.io.Serializable { } | |
/** | |
* Lock used only for its memory effects. | |
**/ | |
protected final BarrierLock barrierLock = new BarrierLock(); | |
/** | |
* field written to only to guarantee lock ordering. | |
**/ | |
protected transient Object lastWrite; | |
/** | |
* Force a memory synchronization that will cause | |
* all readers to see table. Call only when already | |
* holding main sync lock. | |
**/ | |
protected final void recordModification(Object x) { | |
synchronized(barrierLock) { | |
lastWrite = x; | |
} | |
} | |
/** | |
* Get ref to table; the reference and the cells it | |
* accesses will be at least as fresh as from last | |
* use of barrierLock | |
**/ | |
protected final Entry[] getTableForReading() { | |
synchronized(barrierLock) { | |
return table; | |
} | |
} | |
/** | |
* The default initial number of table slots for this table (32). | |
* Used when not otherwise specified in constructor. | |
**/ | |
public static final int DEFAULT_INITIAL_CAPACITY = 32; | |
/** | |
* The minimum capacity, used if a lower value is implicitly specified | |
* by either of the constructors with arguments. | |
* MUST be a power of two. | |
*/ | |
private static final int MINIMUM_CAPACITY = 4; | |
/** | |
* 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 default load factor for this table (1.0). | |
* Used when not otherwise specified in constructor. | |
**/ | |
public static final float DEFAULT_LOAD_FACTOR = 0.75f; | |
/** | |
* The hash table data. | |
*/ | |
protected transient Entry[] table; | |
/** | |
* The total number of mappings in the hash table. | |
*/ | |
protected transient int count; | |
/** | |
* The table is rehashed when its size exceeds this threshold. (The | |
* value of this field is always (int)(capacity * loadFactor).) | |
* | |
* @serial | |
*/ | |
protected int threshold; | |
/** | |
* The load factor for the hash table. | |
* | |
* @serial | |
*/ | |
protected float loadFactor; | |
/** | |
* Returns the appropriate capacity (power of two) for the specified | |
* initial capacity argument. | |
*/ | |
private static int p2capacity(int initialCapacity) { | |
int cap = initialCapacity; | |
// Compute the appropriate capacity | |
int result; | |
if (cap > MAXIMUM_CAPACITY || cap < 0) { | |
result = MAXIMUM_CAPACITY; | |
} else { | |
result = MINIMUM_CAPACITY; | |
while (result < cap) | |
result <<= 1; | |
} | |
return result; | |
} | |
/** | |
* Return hash code for Object x. Since we are using power-of-two | |
* tables, it is worth the effort to improve hashcode via | |
* the same multiplicative scheme as used in IdentityHashMap. | |
*/ | |
private static int hash(Object x) { | |
int h = x.hashCode(); | |
// Multiply by 127 (quickly, via shifts), and mix in some high | |
// bits to help guard against bunching of codes that are | |
// consecutive or equally spaced. | |
return ((h << 7) - h + (h >>> 9) + (h >>> 17)); | |
} | |
/** | |
* Check for equality of non-null references x and y. | |
**/ | |
protected boolean eq(Object x, Object y) { | |
return x == y || x.equals(y); | |
} | |
/** | |
* Constructs a new, empty map with the specified initial | |
* capacity and the specified load factor. | |
* | |
* @param initialCapacity the initial capacity | |
* The actual initial capacity is rounded to the nearest power of two. | |
* @param loadFactor the load factor of the ConcurrentReaderHashMap | |
* @throws IllegalArgumentException if the initial maximum number | |
* of elements is less | |
* than zero, or if the load factor is non-positive. | |
*/ | |
public ConcurrentReaderHashMap(int initialCapacity, float loadFactor) { | |
if (loadFactor <= 0) | |
throw new IllegalArgumentException("Illegal Load factor: "+ | |
loadFactor); | |
this.loadFactor = loadFactor; | |
int cap = p2capacity(initialCapacity); | |
table = new Entry[cap]; | |
threshold = (int)(cap * loadFactor); | |
} | |
/** | |
* Constructs a new, empty map with the specified initial | |
* capacity and default load factor. | |
* | |
* @param initialCapacity the initial capacity of the | |
* ConcurrentReaderHashMap. | |
* @throws IllegalArgumentException if the initial maximum number | |
* of elements is less than zero. | |
*/ | |
public ConcurrentReaderHashMap(int initialCapacity) { | |
this(initialCapacity, DEFAULT_LOAD_FACTOR); | |
} | |
/** | |
* Constructs a new, empty map with a default initial capacity | |
* and load factor. | |
*/ | |
public ConcurrentReaderHashMap() { | |
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); | |
} | |
/** | |
* 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 16 (whichever is greater), and a default load factor. | |
*/ | |
public ConcurrentReaderHashMap(Map t) { | |
this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 16), | |
DEFAULT_LOAD_FACTOR); | |
putAll(t); | |
} | |
/** | |
* Returns the number of key-value mappings in this map. | |
* | |
* @return the number of key-value mappings in this map. | |
*/ | |
public synchronized int size() { | |
return count; | |
} | |
/** | |
* Returns <tt>true</tt> if this map contains no key-value mappings. | |
* | |
* @return <tt>true</tt> if this map contains no key-value mappings. | |
*/ | |
public synchronized boolean isEmpty() { | |
return count == 0; | |
} | |
/** | |
* Returns the value to which the specified key is mapped in this table. | |
* | |
* @param key a key in the table. | |
* @return the value to which the key is mapped in this table; | |
* <code>null</code> if the key is not mapped to any value in | |
* this table. | |
* @exception NullPointerException if the key is <code>null</code>. | |
* @see #put(Object, Object) | |
*/ | |
public Object get(Object key) { | |
// throw null pointer exception if key null | |
int hash = hash(key); | |
/* | |
Start off at the apparently correct bin. If entry is found, we | |
need to check after a barrier anyway. If not found, we need a | |
barrier to check if we are actually in right bin. So either | |
way, we encounter only one barrier unless we need to retry. | |
And we only need to fully synchronize if there have been | |
concurrent modifications. | |
*/ | |
Entry[] tab = table; | |
int index = hash & (tab.length - 1); | |
Entry first = tab[index]; | |
Entry e = first; | |
for (;;) { | |
if (e == null) { | |
// If key apparently not there, check to | |
// make sure this was a valid read | |
Entry[] reread = getTableForReading(); | |
if (tab == reread && first == tab[index]) | |
return null; | |
else { | |
// Wrong list -- must restart traversal at new first | |
tab = reread; | |
e = first = tab[index = hash & (tab.length-1)]; | |
} | |
} | |
else if (e.hash == hash && eq(key, e.key)) { | |
Object value = e.value; | |
if (value != null) | |
return value; | |
// Entry was invalidated during deletion. But it could | |
// have been re-inserted, so we must re-traverse. | |
// To avoid useless contention, get lock to wait out modifications | |
// before re-traversing. | |
synchronized(this) { | |
tab = table; | |
} | |
e = first = tab[index = hash & (tab.length-1)]; | |
} | |
else | |
e = e.next; | |
} | |
} | |
/** | |
* Tests if the specified object is a key in this table. | |
* | |
* @param key possible key. | |
* @return <code>true</code> if and only if the specified object | |
* is a key in this table, as determined by the | |
* <tt>equals</tt> method; <code>false</code> otherwise. | |
* @exception NullPointerException if the key is <code>null</code>. | |
* @see #contains(Object) | |
*/ | |
public boolean containsKey(Object key) { | |
return get(key) != null; | |
} | |
/** | |
* Maps the specified <code>key</code> to the specified | |
* <code>value</code> in this table. Neither the key nor the | |
* value can be <code>null</code>. <p> | |
* | |
* The value can be retrieved by calling the <code>get</code> method | |
* with a key that is equal to the original key. | |
* | |
* @param key the table key. | |
* @param value the value. | |
* @return the previous value of the specified key in this table, | |
* or <code>null</code> if it did not have one. | |
* @exception NullPointerException if the key or value is <code>null</code>. | |
* @see Object#equals(Object) | |
* @see #get(Object) | |
*/ | |
public Object put(Object key, Object value) { | |
if (value == null) | |
throw new NullPointerException(); | |
int hash = hash(key); | |
Entry[] tab = table; | |
int index = hash & (tab.length-1); | |
Entry first = tab[index]; | |
Entry e; | |
for (e = first; e != null; e = e.next) | |
if (e.hash == hash && eq(key, e.key)) | |
break; | |
synchronized(this) { | |
if (tab == table) { | |
if (e == null) { | |
// make sure we are adding to correct list | |
if (first == tab[index]) { | |
// Add to front of list | |
Entry newEntry = new Entry(hash, key, value, first); | |
tab[index] = newEntry; | |
if (++count >= threshold) rehash(); | |
else recordModification(newEntry); | |
return null; | |
} | |
} | |
else { | |
Object oldValue = e.value; | |
if (first == tab[index] && oldValue != null) { | |
e.value = value; | |
return oldValue; | |
} | |
} | |
} | |
// retry if wrong list or lost race against concurrent remove | |
return sput(key, value, hash); | |
} | |
} | |
/** | |
* Continuation of put(), called only when sync lock is | |
* held and interference has been detected. | |
**/ | |
protected Object sput(Object key, Object value, int hash) { | |
Entry[] tab = table; | |
int index = hash & (tab.length-1); | |
Entry first = tab[index]; | |
Entry e = first; | |
for (;;) { | |
if (e == null) { | |
Entry newEntry = new Entry(hash, key, value, first); | |
tab[index] = newEntry; | |
if (++count >= threshold) rehash(); | |
else recordModification(newEntry); | |
return null; | |
} | |
else if (e.hash == hash && eq(key, e.key)) { | |
Object oldValue = e.value; | |
e.value = value; | |
return oldValue; | |
} | |
else | |
e = e.next; | |
} | |
} | |
/** | |
* Rehashes the contents of this map into a new table | |
* with a larger capacity. This method is called automatically when the | |
* number of keys in this map exceeds its capacity and load factor. | |
*/ | |
protected void rehash() { | |
Entry[] oldTable = table; | |
int oldCapacity = oldTable.length; | |
if (oldCapacity >= MAXIMUM_CAPACITY) { | |
threshold = Integer.MAX_VALUE; // avoid re-triggering | |
return; | |
} | |
int newCapacity = oldCapacity << 1; | |
int mask = newCapacity - 1; | |
threshold = (int)(newCapacity * loadFactor); | |
Entry[] newTable = new Entry[newCapacity]; | |
/* | |
* Reclassify nodes in each list to new Map. Because we are | |
* using power-of-two expansion, the elements from each bin | |
* must either stay at same index, or move to | |
* oldCapacity+index. We also eliminate unnecessary node | |
* creation by catching cases where old nodes can be reused | |
* because their next fields won't change. Statistically, at | |
* the default threshold, only about one-sixth of them need | |
* cloning. (The nodes they replace will be garbage | |
* collectible as soon as they are no longer referenced by any | |
* reader thread that may be in the midst of traversing table | |
* right now.) | |
*/ | |
for (int i = 0; i < oldCapacity ; i++) { | |
// We need to guarantee that any existing reads of old Map can | |
// proceed. So we cannot yet null out each bin. | |
Entry e = oldTable[i]; | |
if (e != null) { | |
int idx = e.hash & mask; | |
Entry next = e.next; | |
// Single node on list | |
if (next == null) | |
newTable[idx] = e; | |
else { | |
// Reuse trailing consecutive sequence of all same bit | |
Entry lastRun = e; | |
int lastIdx = idx; | |
for (Entry last = next; last != null; last = last.next) { | |
int k = last.hash & mask; | |
if (k != lastIdx) { | |
lastIdx = k; | |
lastRun = last; | |
} | |
} | |
newTable[lastIdx] = lastRun; | |
// Clone all remaining nodes | |
for (Entry p = e; p != lastRun; p = p.next) { | |
int k = p.hash & mask; | |
newTable[k] = new Entry(p.hash, p.key, | |
p.value, newTable[k]); | |
} | |
} | |
} | |
} | |
table = newTable; | |
recordModification(newTable); | |
} | |
/** | |
* Removes the key (and its corresponding value) from this | |
* table. This method does nothing if the key is not in the table. | |
* | |
* @param key the key that needs to be removed. | |
* @return the value to which the key had been mapped in this table, | |
* or <code>null</code> if the key did not have a mapping. | |
* @exception NullPointerException if the key is | |
* <code>null</code>. | |
*/ | |
public Object remove(Object key) { | |
/* | |
Find the entry, then | |
1. Set value field to null, to force get() to retry | |
2. Rebuild the list without this entry. | |
All entries following removed node can stay in list, but | |
all preceding ones need to be cloned. Traversals rely | |
on this strategy to ensure that elements will not be | |
repeated during iteration. | |
*/ | |
int hash = hash(key); | |
Entry[] tab = table; | |
int index = hash & (tab.length-1); | |
Entry first = tab[index]; | |
Entry e = first; | |
for (e = first; e != null; e = e.next) | |
if (e.hash == hash && eq(key, e.key)) | |
break; | |
synchronized(this) { | |
if (tab == table) { | |
if (e == null) { | |
if (first == tab[index]) | |
return null; | |
} | |
else { | |
Object oldValue = e.value; | |
if (first == tab[index] && oldValue != null) { | |
e.value = null; | |
count--; | |
Entry head = e.next; | |
for (Entry p = first; p != e; p = p.next) | |
head = new Entry(p.hash, p.key, p.value, head); | |
tab[index] = head; | |
recordModification(head); | |
return oldValue; | |
} | |
} | |
} | |
// Wrong list or interference | |
return sremove(key, hash); | |
} | |
} | |
/** | |
* Continuation of remove(), called only when sync lock is | |
* held and interference has been detected. | |
**/ | |
protected Object sremove(Object key, int hash) { | |
Entry[] tab = table; | |
int index = hash & (tab.length-1); | |
Entry first = tab[index]; | |
for (Entry e = first; e != null; e = e.next) { | |
if (e.hash == hash && eq(key, e.key)) { | |
Object oldValue = e.value; | |
e.value = null; | |
count--; | |
Entry head = e.next; | |
for (Entry p = first; p != e; p = p.next) | |
head = new Entry(p.hash, p.key, p.value, head); | |
tab[index] = head; | |
recordModification(head); | |
return oldValue; | |
} | |
} | |
return null; | |
} | |
/** | |
* Returns <tt>true</tt> if this map maps one or more keys to the | |
* specified value. Note: This method requires a full internal | |
* traversal of the hash table, and so is much slower than | |
* method <tt>containsKey</tt>. | |
* | |
* @param value value whose presence in this map is to be tested. | |
* @return <tt>true</tt> if this map maps one or more keys to the | |
* specified value. | |
* @exception NullPointerException if the value is <code>null</code>. | |
*/ | |
public boolean containsValue(Object value) { | |
if (value == null) throw new NullPointerException(); | |
Entry tab[] = getTableForReading(); | |
for (int i = 0 ; i < tab.length; ++i) { | |
for (Entry e = tab[i] ; e != null ; e = e.next) | |
if (value.equals(e.value)) | |
return true; | |
} | |
return false; | |
} | |
/** | |
* Tests if some key maps into the specified value in this table. | |
* This operation is more expensive than the <code>containsKey</code> | |
* method.<p> | |
* | |
* Note that this method is identical in functionality to containsValue, | |
* (which is part of the Map interface in the collections framework). | |
* | |
* @param value a value to search for. | |
* @return <code>true</code> if and only if some key maps to the | |
* <code>value</code> argument in this table as | |
* determined by the <tt>equals</tt> method; | |
* <code>false</code> otherwise. | |
* @exception NullPointerException if the value is <code>null</code>. | |
* @see #containsKey(Object) | |
* @see #containsValue(Object) | |
* @see Map | |
*/ | |
public boolean contains(Object value) { | |
return containsValue(value); | |
} | |
/** | |
* Copies all of the mappings from the specified map to this one. | |
* | |
* These mappings replace any mappings that this map had for any of the | |
* keys currently in the specified Map. | |
* | |
* @param t Mappings to be stored in this map. | |
*/ | |
public synchronized void putAll(Map t) { | |
int n = t.size(); | |
if (n == 0) | |
return; | |
// Expand enough to hold at least n elements without resizing. | |
// We can only resize table by factor of two at a time. | |
// It is faster to rehash with fewer elements, so do it now. | |
while (n >= threshold) | |
rehash(); | |
for (Iterator it = t.entrySet().iterator(); it.hasNext();) { | |
Map.Entry entry = (Map.Entry) it.next(); | |
Object key = entry.getKey(); | |
Object value = entry.getValue(); | |
put(key, value); | |
} | |
} | |
/** | |
* Removes all mappings from this map. | |
*/ | |
public synchronized void clear() { | |
Entry tab[] = table; | |
for (int i = 0; i < tab.length ; ++i) { | |
// must invalidate all to force concurrent get's to wait and then retry | |
for (Entry e = tab[i]; e != null; e = e.next) | |
e.value = null; | |
tab[i] = null; | |
} | |
count = 0; | |
recordModification(tab); | |
} | |
/** | |
* Returns a shallow copy of this | |
* <tt>ConcurrentReaderHashMap</tt> instance: the keys and | |
* values themselves are not cloned. | |
* | |
* @return a shallow copy of this map. | |
*/ | |
public synchronized Object clone() { | |
try { | |
ConcurrentReaderHashMap t = (ConcurrentReaderHashMap)super.clone(); | |
t.keySet = null; | |
t.entrySet = null; | |
t.values = null; | |
Entry[] tab = table; | |
t.table = new Entry[tab.length]; | |
Entry[] ttab = t.table; | |
for (int i = 0; i < tab.length; ++i) { | |
Entry first = null; | |
for (Entry e = tab[i]; e != null; e = e.next) | |
first = new Entry(e.hash, e.key, e.value, first); | |
ttab[i] = first; | |
} | |
return t; | |
} | |
catch (CloneNotSupportedException e) { | |
// this shouldn't happen, since we are Cloneable | |
throw new InternalError(); | |
} | |
} | |
// Views | |
protected transient Set keySet = null; | |
protected transient Set entrySet = null; | |
protected transient Collection values = 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 <tt>Iterator.remove</tt>, | |
* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and | |
* <tt>clear</tt> operations. It does not support the <tt>add</tt> or | |
* <tt>addAll</tt> operations. | |
* | |
* @return a set view of the keys contained in this map. | |
*/ | |
public Set keySet() { | |
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 ConcurrentReaderHashMap.this.size(); | |
} | |
public boolean contains(Object o) { | |
return ConcurrentReaderHashMap.this.containsKey(o); | |
} | |
public boolean remove(Object o) { | |
return ConcurrentReaderHashMap.this.remove(o) != null; | |
} | |
public void clear() { | |
ConcurrentReaderHashMap.this.clear(); | |
} | |
public Object[] toArray() { | |
Collection c = new ArrayList(); | |
for (Iterator i = iterator(); i.hasNext(); ) | |
c.add(i.next()); | |
return c.toArray(); | |
} | |
public Object[] toArray(Object[] a) { | |
Collection c = new ArrayList(); | |
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 | |
* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, | |
* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. | |
* It does not support the <tt>add</tt> or <tt>addAll</tt> operations. | |
* | |
* @return a collection view of the values contained in this map. | |
*/ | |
public Collection values() { | |
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 ConcurrentReaderHashMap.this.size(); | |
} | |
public boolean contains(Object o) { | |
return ConcurrentReaderHashMap.this.containsValue(o); | |
} | |
public void clear() { | |
ConcurrentReaderHashMap.this.clear(); | |
} | |
public Object[] toArray() { | |
Collection c = new ArrayList(); | |
for (Iterator i = iterator(); i.hasNext(); ) | |
c.add(i.next()); | |
return c.toArray(); | |
} | |
public Object[] toArray(Object[] a) { | |
Collection c = new ArrayList(); | |
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 <tt>Map.Entry</tt>. The | |
* collection is backed by the map, so changes to the map are reflected in | |
* the collection, and vice-versa. The collection supports element | |
* removal, which removes the corresponding mapping from the map, via the | |
* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, | |
* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. | |
* It does not support the <tt>add</tt> or <tt>addAll</tt> operations. | |
* | |
* @return a collection view of the mappings contained in this map. | |
*/ | |
public Set entrySet() { | |
Set es = entrySet; | |
return (es != null) ? es : (entrySet = new EntrySet()); | |
} | |
private class EntrySet extends AbstractSet { | |
public Iterator iterator() { | |
return new HashIterator(); | |
} | |
public boolean contains(Object o) { | |
if (!(o instanceof Map.Entry)) | |
return false; | |
Map.Entry entry = (Map.Entry)o; | |
Object v = ConcurrentReaderHashMap.this.get(entry.getKey()); | |
return v != null && v.equals(entry.getValue()); | |
} | |
public boolean remove(Object o) { | |
if (!(o instanceof Map.Entry)) | |
return false; | |
return ConcurrentReaderHashMap.this.findAndRemoveEntry((Map.Entry)o); | |
} | |
public int size() { | |
return ConcurrentReaderHashMap.this.size(); | |
} | |
public void clear() { | |
ConcurrentReaderHashMap.this.clear(); | |
} | |
public Object[] toArray() { | |
Collection c = new ArrayList(); | |
for (Iterator i = iterator(); i.hasNext(); ) | |
c.add(i.next()); | |
return c.toArray(); | |
} | |
public Object[] toArray(Object[] a) { | |
Collection c = new ArrayList(); | |
for (Iterator i = iterator(); i.hasNext(); ) | |
c.add(i.next()); | |
return c.toArray(a); | |
} | |
} | |
/** | |
* Helper method for entrySet.remove | |
**/ | |
protected synchronized boolean findAndRemoveEntry(Map.Entry entry) { | |
Object key = entry.getKey(); | |
Object v = get(key); | |
if (v != null && v.equals(entry.getValue())) { | |
remove(key); | |
return true; | |
} | |
else | |
return false; | |
} | |
/** | |
* Returns an enumeration of the keys in this table. | |
* | |
* @return an enumeration of the keys in this table. | |
* @see Enumeration | |
* @see #elements() | |
* @see #keySet() | |
* @see Map | |
*/ | |
public Enumeration keys() { | |
return new KeyIterator(); | |
} | |
/** | |
* Returns an enumeration of the values in this table. | |
* Use the Enumeration methods on the returned object to fetch the elements | |
* sequentially. | |
* | |
* @return an enumeration of the values in this table. | |
* @see java.util.Enumeration | |
* @see #keys() | |
* @see #values() | |
* @see Map | |
*/ | |
public Enumeration elements() { | |
return new ValueIterator(); | |
} | |
/** | |
* ConcurrentReaderHashMap collision list entry. | |
*/ | |
protected static class Entry implements Map.Entry { | |
/* | |
The use of volatile for value field ensures that | |
we can detect status changes without synchronization. | |
The other fields are never changed, and are | |
marked as final. | |
*/ | |
protected final int hash; | |
protected final Object key; | |
protected final Entry next; | |
protected volatile Object value; | |
Entry(int hash, Object key, Object value, Entry next) { | |
this.hash = hash; | |
this.key = key; | |
this.next = next; | |
this.value = value; | |
} | |
// Map.Entry Ops | |
public Object getKey() { | |
return key; | |
} | |
/** | |
* Get the value. Note: In an entrySet or entrySet.iterator, | |
* unless the set or iterator is used under synchronization of the | |
* table as a whole (or you can otherwise guarantee lack of | |
* concurrent modification), <tt>getValue</tt> <em>might</em> | |
* return null, reflecting the fact that the entry has been | |
* concurrently removed. However, there are no assurances that | |
* concurrent removals will be reflected using this method. | |
* | |
* @return the current value, or null if the entry has been | |
* detectably removed. | |
**/ | |
public Object getValue() { | |
return value; | |
} | |
/** | |
* Set the value of this entry. Note: In an entrySet or | |
* entrySet.iterator), unless the set or iterator is used under | |
* synchronization of the table as a whole (or you can otherwise | |
* guarantee lack of concurrent modification), <tt>setValue</tt> | |
* is not strictly guaranteed to actually replace the value field | |
* obtained via the <tt>get</tt> operation of the underlying hash | |
* table in multi-threaded applications. If iterator-wide | |
* synchronization is not used, and any other concurrent | |
* <tt>put</tt> or <tt>remove</tt> operations occur, sometimes | |
* even to <em>other</em> entries, then this change is not | |
* guaranteed to be reflected in the hash table. (It might, or it | |
* might not. There are no assurances either way.) | |
* | |
* @param value the new value. | |
* @return the previous value, or null if entry has been detectably | |
* removed. | |
* @exception NullPointerException if the value is <code>null</code>. | |
* | |
**/ | |
public Object setValue(Object value) { | |
if (value == null) | |
throw new NullPointerException(); | |
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 (key.equals(e.getKey()) && value.equals(e.getValue())); | |
} | |
public int hashCode() { | |
return key.hashCode() ^ value.hashCode(); | |
} | |
public String toString() { | |
return key + "=" + value; | |
} | |
} | |
protected class HashIterator implements Iterator, Enumeration { | |
protected final Entry[] tab; // snapshot of table | |
protected int index; // current slot | |
protected Entry entry = null; // current node of slot | |
protected Object currentKey; // key for current node | |
protected Object currentValue; // value for current node | |
protected Entry lastReturned = null; // last node returned by next | |
protected HashIterator() { | |
tab = ConcurrentReaderHashMap.this.getTableForReading(); | |
index = tab.length - 1; | |
} | |
public boolean hasMoreElements() { return hasNext(); } | |
public Object nextElement() { return next(); } | |
public boolean hasNext() { | |
/* | |
currentKey and currentValue are set here to ensure that next() | |
returns normally if hasNext() returns true. This avoids | |
surprises especially when final element is removed during | |
traversal -- instead, we just ignore the removal during | |
current traversal. | |
*/ | |
for (;;) { | |
if (entry != null) { | |
Object v = entry.value; | |
if (v != null) { | |
currentKey = entry.key; | |
currentValue = v; | |
return true; | |
} | |
else | |
entry = entry.next; | |
} | |
while (entry == null && index >= 0) | |
entry = tab[index--]; | |
if (entry == null) { | |
currentKey = currentValue = null; | |
return false; | |
} | |
} | |
} | |
protected Object returnValueOfNext() { return entry; } | |
public Object next() { | |
if (currentKey == null && !hasNext()) | |
throw new NoSuchElementException(); | |
Object result = returnValueOfNext(); | |
lastReturned = entry; | |
currentKey = currentValue = null; | |
entry = entry.next; | |
return result; | |
} | |
public void remove() { | |
if (lastReturned == null) | |
throw new IllegalStateException(); | |
ConcurrentReaderHashMap.this.remove(lastReturned.key); | |
lastReturned = null; | |
} | |
} | |
protected class KeyIterator extends HashIterator { | |
protected Object returnValueOfNext() { return currentKey; } | |
} | |
protected class ValueIterator extends HashIterator { | |
protected Object returnValueOfNext() { return currentValue; } | |
} | |
/** | |
* Save the state of the <tt>ConcurrentReaderHashMap</tt> | |
* instance to a stream (i.e., | |
* serialize it). | |
* | |
* @param s the stream | |
* @serialData The <i>capacity</i> of the | |
* ConcurrentReaderHashMap (the length of the | |
* bucket array) is emitted (int), followed by the | |
* <i>size</i> of the ConcurrentReaderHashMap (the number of key-value | |
* mappings), followed by the key (Object) and value (Object) | |
* for each key-value mapping represented by the ConcurrentReaderHashMap | |
* The key-value mappings are emitted in no particular order. | |
*/ | |
private synchronized void writeObject(java.io.ObjectOutputStream s) | |
throws IOException { | |
// Write out the threshold, loadfactor, and any hidden stuff | |
s.defaultWriteObject(); | |
// Write out number of buckets | |
s.writeInt(table.length); | |
// Write out size (number of Mappings) | |
s.writeInt(count); | |
// Write out keys and values (alternating) | |
for (int index = table.length-1; index >= 0; index--) { | |
Entry entry = table[index]; | |
while (entry != null) { | |
s.writeObject(entry.key); | |
s.writeObject(entry.value); | |
entry = entry.next; | |
} | |
} | |
} | |
/** | |
* Reconstitute the <tt>ConcurrentReaderHashMap</tt> | |
* instance from a stream (i.e., | |
* deserialize it). | |
* | |
* @param s the stream | |
*/ | |
private synchronized void readObject(java.io.ObjectInputStream s) | |
throws IOException, ClassNotFoundException { | |
// Read in the threshold, loadfactor, and any hidden stuff | |
s.defaultReadObject(); | |
// Read in number of buckets and allocate the bucket array; | |
int numBuckets = s.readInt(); | |
table = new Entry[numBuckets]; | |
// Read in size (number of Mappings) | |
int size = s.readInt(); | |
// Read the keys and values, and put the mappings in the table | |
for (int i=0; i<size; i++) { | |
Object key = s.readObject(); | |
Object value = s.readObject(); | |
put(key, value); | |
} | |
} | |
/** | |
* @return the number of slots in this table | |
**/ | |
public synchronized int capacity() { | |
return table.length; | |
} | |
/** | |
* @return the load factor | |
**/ | |
public float loadFactor() { | |
return loadFactor; | |
} | |
} |