newFirst = tab[index];
if (e != null || first != newFirst) {
for (e = newFirst; e != null; e = e.next) {
if (e.hash == hash && eq(key, e.key))
return e.value;
}
}
return null;
}
}
/**
* Tests if the specified object is a key in this table.
*
* @param key possible key.
* @return true if and only if the specified object
* is a key in this table, as determined by the
* equals method; false otherwise.
* @exception NullPointerException if the key is
* null.
* @see #contains(Object)
*/
public boolean containsKey(Object key) {
return get(key) != null;
}
/**
* Maps the specified key to the specified
* value in this table. Neither the key nor the
* value can be null. (Note that this policy is
* the same as for java.util.Hashtable, but unlike java.util.HashMap,
* which does accept nulls as valid keys and values.)
*
* The value can be retrieved by calling the get 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 null if it did not have one.
* @exception NullPointerException if the key or value is
* null.
* @see Object#equals(Object)
* @see #get(Object)
*/
public V put(K key, V value) {
if (value == null)
throw new NullPointerException();
int hash = hash(key);
Segment seg = segments[hash & SEGMENT_MASK];
int segcount;
Entry[] tab;
int votes;
synchronized(seg) {
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)) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// Add to front of list
Entry newEntry = new Entry(hash, key, value, first);
tab[index] = newEntry;
if ((segcount = ++seg.count) < threshold)
return null;
int bit = (1 << (hash & SEGMENT_MASK));
votes = votesForResize;
if ((votes & bit) == 0)
votes = votesForResize |= bit;
}
// Attempt resize if 1/4 segs vote,
// or if this seg itself reaches the overall threshold.
// (The latter check is just a safeguard to avoid pathological cases.)
if (bitcount(votes) >= CONCURRENCY_LEVEL / 4 ||
segcount > (threshold * CONCURRENCY_LEVEL))
resize(0, tab);
return null;
}
public V putIfAbsent(K key, V value) {
if (value == null)
throw new NullPointerException();
int hash = hash(key);
Segment seg = segments[hash & SEGMENT_MASK];
int segcount;
Entry[] tab;
int votes;
synchronized(seg) {
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)) {
V oldValue = e.value;
return oldValue;
}
}
// Add to front of list
Entry newEntry = new Entry(hash, key, value, first);
tab[index] = newEntry;
if ((segcount = ++seg.count) < threshold)
return null;
int bit = (1 << (hash & SEGMENT_MASK));
votes = votesForResize;
if ((votes & bit) == 0)
votes = votesForResize |= bit;
}
// Attempt resize if 1/4 segs vote,
// or if this seg itself reaches the overall threshold.
// (The latter check is just a safeguard to avoid pathological cases.)
if (bitcount(votes) >= CONCURRENCY_LEVEL / 4 ||
segcount > (threshold * CONCURRENCY_LEVEL))
resize(0, tab);
return value;
}
/**
* Gather all locks in order to call rehash, by
* recursing within synch blocks for each segment index.
* @param index the current segment. initially call value must be 0
* @param assumedTab the state of table on first call to resize. If
* this changes on any call, the attempt is aborted because the
* table has already been resized by another thread.
*/
private void resize(int index, Entry[] assumedTab) {
Segment seg = segments[index];
synchronized(seg) {
if (assumedTab == table) {
int next = index+1;
if (next < segments.length)
resize(next, assumedTab);
else
rehash();
}
}
}
/**
* Rehashes the contents of this map into a new table
* with a larger capacity.
*/
private void rehash() {
votesForResize = 0; // reset
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE; // avoid retriggering
return;
}
int newCapacity = oldCapacity << 1;
Entry[] newTable = newTable(newCapacity);
int mask = newCapacity - 1;
/*
* 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 threshhold, only about one-sixth of them need
* cloning. (The nodes they replace will be garbage
* collectable 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;
}
/**
* 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 null if the key did not have a mapping.
* @exception NullPointerException if the key is
* null.
*/
public V remove(Object key) {
return remove(key, null);
}
/**
* Removes the (key, value) pair from this
* table. This method does nothing if the key is not in the table,
* or if the key is associated with a different value. This method
* is needed by EntrySet.
*
* @param key the key that needs to be removed.
* @param value the associated value. If the value is null,
* it means "any value".
* @return the value to which the key had been mapped in this table,
* or null if the key did not have a mapping.
* @exception NullPointerException if the key is
* null.
*/
private V remove(Object key, V value) {
/*
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 preceeding ones need to be cloned. Traversals rely
on this strategy to ensure that elements will not be
repeated during iteration.
*/
int hash = hash(key);
Segment seg = segments[hash & SEGMENT_MASK];
synchronized(seg) {
Entry[] tab = table;
int index = hash & (tab.length-1);
Entry first = tab[index];
Entry e = first;
for (;;) {
if (e == null)
return null;
if (e.hash == hash && eq(key, e.key))
break;
e = e.next;
}
V oldValue = e.value;
if (value != null && !value.equals(oldValue))
return null;
e.value = null;
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;
seg.count--;
return oldValue;
}
}
/**
* Returns true 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 containsKey.
*
* @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.
* @exception NullPointerException if the value is null.
*/
public boolean containsValue(Object value) {
if (value == null) throw new NullPointerException();
for (int s = 0; s < segments.length; ++s) {
Segment seg = segments[s];
Entry[] tab;
synchronized(seg) { tab = table; }
for (int i = s; i < tab.length; i+= segments.length) {
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 containsKey
* method.
*
* 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 true if and only if some key maps to the
* value argument in this table as
* determined by the equals method;
* false otherwise.
* @exception NullPointerException if the value is null.
* @see #containsKey(Object)
* @see #containsValue(Object)
* @see Map
*/
public boolean contains(V 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 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.
for(;;) {
Entry[] tab;
int max;
synchronized(segments[0]) { // must synch on some segment. pick 0.
tab = table;
max = threshold * CONCURRENCY_LEVEL;
}
if (n < max)
break;
resize(0, tab);
}
for (Iterator> it = t.entrySet().iterator(); it.hasNext();) {
Map.Entry entry = (Map.Entry) it.next();
put(entry.getKey(), entry.getValue());
}
}
/**
* Removes all mappings from this map.
*/
public void clear() {
// We don't need all locks at once so long as locks
// are obtained in low to high order
for (int s = 0; s < segments.length; ++s) {
Segment seg = segments[s];
synchronized(seg) {
Entry[] tab = table;
for (int i = s; i < tab.length; i+= segments.length) {
for (Entry e = tab[i]; e != null; e = e.next)
e.value = null;
tab[i] = null;
seg.count = 0;
}
}
}
}
/**
* Returns a shallow copy of this
* ConcurrentHashMap instance: the keys and
* values themselves are not cloned.
*
* @return a shallow copy of this map.
*/
public Object clone() {
// We cannot call super.clone, since it would share final segments array,
// and there's no way to reassign finals.
return new ConcurrentHashMap(this);
}
// Views
private transient Set keySet = null;
private transient Set> entrySet = null;
private 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 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 ConcurrentHashMap.this.size();
}
public boolean contains(Object o) {
return ConcurrentHashMap.this.containsKey(o);
}
public boolean remove(Object o) {
return ConcurrentHashMap.this.remove(o) != null;
}
public void clear() {
ConcurrentHashMap.this.clear();
}
}
/**
* 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 ConcurrentHashMap.this.size();
}
public boolean contains(Object o) {
return ConcurrentHashMap.this.containsValue(o);
}
public void clear() {
ConcurrentHashMap.this.clear();
}
}
/**
* 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.
*/
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(Map.Entry entry) {
V v = ConcurrentHashMap.this.get(entry.getKey());
return v != null && v.equals(entry.getValue());
}
public boolean remove(Map.Entry e) {
return ConcurrentHashMap.this.remove(e.getKey(), e.getValue()) != null;
}
public int size() {
return ConcurrentHashMap.this.size();
}
public void clear() {
ConcurrentHashMap.this.clear();
}
}
/**
* 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();
}
/**
* ConcurrentHashMap collision list entry.
*/
private 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.
*/
private final K key;
private volatile V value;
private final int hash;
private final Entry next;
Entry(int hash, K key, V value, Entry next) {
this.value = value;
this.hash = hash;
this.key = key;
this.next = next;
}
// Map.Entry Ops
public K getKey() {
return key;
}
/**
* Get the value. Note: In an entrySet or entrySet.iterator,
* unless you can guarantee lack of concurrent modification,
* getValue might 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 V getValue() {
return value;
}
/**
* Set the value of this entry. Note: In an entrySet or
* entrySet.iterator), unless you can guarantee lack of concurrent
* modification, setValue is not strictly guaranteed to
* actually replace the value field obtained via the get
* operation of the underlying hash table in multithreaded
* applications. If iterator-wide synchronization is not used,
* and any other concurrent put or remove
* operations occur, sometimes even to other 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 null.
*
**/
public V setValue(V value) {
if (value == null)
throw new NullPointerException();
V 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;
}
}
private abstract class HashIterator implements Iterator, Enumeration {
private final Entry[] tab; // snapshot of table
private int index; // current slot
Entry entry = null; // current node of slot
K currentKey; // key for current node
V currentValue; // value for current node
private Entry lastReturned = null; // last node returned by next
private HashIterator() {
// force all segments to synch
synchronized(segments[0]) { tab = table; }
for (int i = 1; i < segments.length; ++i) segments[i].synch();
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.
*/
while (true) {
if (entry != null) {
V 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 = null;
currentValue = null;
return false;
}
}
}
abstract T returnValueOfNext();
public T next() {
if (currentKey == null && !hasNext())
throw new NoSuchElementException();
T result = returnValueOfNext();
lastReturned = entry;
currentKey = null;
currentValue = null;
entry = entry.next;
return result;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
ConcurrentHashMap.this.remove(lastReturned.key);
lastReturned = null;
}
}
private class KeyIterator extends HashIterator {
K returnValueOfNext() { return currentKey; }
public K next() { return super.next(); }
}
private class ValueIterator extends HashIterator {
V returnValueOfNext() { return currentValue; }
public V next() { return super.next(); }
}
private class EntryIterator extends HashIterator> {
Map.Entry returnValueOfNext() { return entry; }
public Map.Entry next() { return super.next(); }
}
/**
* Save the state of the ConcurrentHashMap
* instance to a stream (i.e.,
* serialize it).
*
* @serialData
* An estimate of the table size, followed by
* the key (Object) and value (Object)
* for each key-value mapping, followed by a null pair.
* The key-value mappings are emitted in no particular order.
*/
private void writeObject(java.io.ObjectOutputStream s) throws IOException {
// Write out the loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out capacity estimate. It is OK if this
// changes during the write, since it is only used by
// readObject to set initial capacity, to avoid needless resizings.
int cap;
synchronized(segments[0]) { cap = table.length; }
s.writeInt(cap);
// Write out keys and values (alternating)
for (int k = 0; k < segments.length; ++k) {
Segment seg = segments[k];
Entry[] tab;
synchronized(seg) { tab = table; }
for (int i = k; i < tab.length; i+= segments.length) {
for (Entry e = tab[i]; e != null; e = e.next) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
}
s.writeObject(null);
s.writeObject(null);
}
/**
* Reconstitute the ConcurrentHashMap
* instance from a stream (i.e.,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException {
// Read in the threshold, loadfactor, and any hidden stuff
s.defaultReadObject();
int cap = s.readInt();
table = newTable(cap);
for (int i = 0; i < segments.length; ++i)
segments[i] = new Segment();
// Read the keys and values, and put the mappings in the table
while (true) {
K key = (K) s.readObject();
V value = (V) s.readObject();
if (key == null)
break;
put(key, value);
}
}
}