--- jsr166/src/jsr166e/ConcurrentHashMapV8.java 2012/08/13 18:25:53 1.55
+++ jsr166/src/jsr166e/ConcurrentHashMapV8.java 2012/10/21 04:14:30 1.68
@@ -47,19 +47,22 @@ import java.io.Serializable;
* block, so may overlap with update operations (including {@code put}
* and {@code remove}). Retrievals reflect the results of the most
* recently completed update operations holding upon their
- * onset. For aggregate operations such as {@code putAll} and {@code
- * clear}, concurrent retrievals may reflect insertion or removal of
- * only some entries. Similarly, Iterators and Enumerations return
- * elements reflecting the state of the hash table at some point at or
- * since the creation of the iterator/enumeration. They do
- * not throw {@link ConcurrentModificationException}.
- * However, iterators are designed to be used by only one thread at a
- * time. Bear in mind that the results of aggregate status methods
- * including {@code size}, {@code isEmpty}, and {@code containsValue}
- * are typically useful only when a map is not undergoing concurrent
- * updates in other threads. Otherwise the results of these methods
- * reflect transient states that may be adequate for monitoring
- * or estimation purposes, but not for program control.
+ * onset. (More formally, an update operation for a given key bears a
+ * happens-before relation with any (non-null) retrieval for
+ * that key reporting the updated value.) For aggregate operations
+ * such as {@code putAll} and {@code clear}, concurrent retrievals may
+ * reflect insertion or removal of only some entries. Similarly,
+ * Iterators and Enumerations return elements reflecting the state of
+ * the hash table at some point at or since the creation of the
+ * iterator/enumeration. They do not throw {@link
+ * ConcurrentModificationException}. However, iterators are designed
+ * to be used by only one thread at a time. Bear in mind that the
+ * results of aggregate status methods including {@code size}, {@code
+ * isEmpty}, and {@code containsValue} are typically useful only when
+ * a map is not undergoing concurrent updates in other threads.
+ * Otherwise the results of these methods reflect transient states
+ * that may be adequate for monitoring or estimation purposes, but not
+ * for program control.
*
*
The table is dynamically expanded when there are too many
* collisions (i.e., keys that have distinct hash codes but fall into
@@ -537,9 +540,13 @@ public class ConcurrentHashMapV8
* unlocking lock (via a failed CAS from non-waiting LOCKED
* state), unlockers acquire the sync lock and perform a
* notifyAll.
+ *
+ * The initial sanity check on tab and bounds is not currently
+ * necessary in the only usages of this method, but enables
+ * use in other future contexts.
*/
final void tryAwaitLock(Node[] tab, int i) {
- if (tab != null && i >= 0 && i < tab.length) { // bounds check
+ if (tab != null && i >= 0 && i < tab.length) { // sanity check
int r = ThreadLocalRandom.current().nextInt(); // randomize spins
int spins = MAX_SPINS, h;
while (tabAt(tab, i) == this && ((h = hash) & LOCKED) != 0) {
@@ -712,11 +719,11 @@ public class ConcurrentHashMapV8
}
/**
- * Return the TreeNode (or null if not found) for the given key
+ * Returns the TreeNode (or null if not found) for the given key
* starting at given root.
*/
- @SuppressWarnings("unchecked") // suppress Comparable cast warning
- final TreeNode getTreeNode(int h, Object k, TreeNode p) {
+ @SuppressWarnings("unchecked") final TreeNode getTreeNode
+ (int h, Object k, TreeNode p) {
Class> c = k.getClass();
while (p != null) {
int dir, ph; Object pk; Class> pc;
@@ -776,8 +783,8 @@ public class ConcurrentHashMapV8
* Finds or adds a node.
* @return null if added
*/
- @SuppressWarnings("unchecked") // suppress Comparable cast warning
- final TreeNode putTreeNode(int h, Object k, Object v) {
+ @SuppressWarnings("unchecked") final TreeNode putTreeNode
+ (int h, Object k, Object v) {
Class> c = k.getClass();
TreeNode pp = root, p = null;
int dir = 0;
@@ -1204,7 +1211,7 @@ public class ConcurrentHashMapV8
}
/*
- * Internal versions of the five insertion methods, each a
+ * Internal versions of the six insertion methods, each a
* little more complicated than the last. All have
* the same basic structure as the first (internalPut):
* 1. If table uninitialized, create
@@ -1222,6 +1229,8 @@ public class ConcurrentHashMapV8
* returns from function call.
* * compute uses the same function-call mechanics, but without
* the prescans
+ * * merge acts as putIfAbsent in the absent case, but invokes the
+ * update function if present
* * putAll attempts to pre-allocate enough table space
* and more lazily performs count updates and checks.
*
@@ -1545,9 +1554,8 @@ public class ConcurrentHashMapV8
}
/** Implementation for compute */
- @SuppressWarnings("unchecked")
- private final Object internalCompute(K k, boolean onlyIfPresent,
- BiFun super K, ? super V, ? extends V> mf) {
+ @SuppressWarnings("unchecked") private final Object internalCompute
+ (K k, boolean onlyIfPresent, BiFun super K, ? super V, ? extends V> mf) {
int h = spread(k.hashCode());
Object val = null;
int delta = 0;
@@ -1670,8 +1678,9 @@ public class ConcurrentHashMapV8
return val;
}
- private final Object internalMerge(K k, V v,
- BiFun super V, ? super V, ? extends V> mf) {
+ /** Implementation for merge */
+ @SuppressWarnings("unchecked") private final Object internalMerge
+ (K k, V v, BiFun super V, ? super V, ? extends V> mf) {
int h = spread(k.hashCode());
Object val = null;
int delta = 0;
@@ -2001,7 +2010,7 @@ public class ConcurrentHashMapV8
for (int i = bin;;) { // start upwards sweep
int fh; Node f;
if ((f = tabAt(tab, i)) == null) {
- if (bin >= 0) { // no lock needed (or available)
+ if (bin >= 0) { // Unbuffered; no lock needed (or available)
if (!casTabAt(tab, i, f, fwd))
continue;
}
@@ -2177,8 +2186,10 @@ public class ConcurrentHashMapV8
try {
if (tabAt(tab, i) == f) {
for (Node p = t.first; p != null; p = p.next) {
- p.val = null;
- --delta;
+ if (p.val != null) { // (currently always true)
+ p.val = null;
+ --delta;
+ }
}
t.first = null;
t.root = null;
@@ -2200,8 +2211,10 @@ public class ConcurrentHashMapV8
try {
if (tabAt(tab, i) == f) {
for (Node e = f; e != null; e = e.next) {
- e.val = null;
- --delta;
+ if (e.val != null) { // (currently always true)
+ e.val = null;
+ --delta;
+ }
}
setTabAt(tab, i, null);
++i;
@@ -2222,7 +2235,7 @@ public class ConcurrentHashMapV8
/**
* Encapsulates traversal for methods such as containsValue; also
- * serves as a base class for other iterators.
+ * serves as a base class for other iterators and bulk tasks.
*
* At each step, the iterator snapshots the key ("nextKey") and
* value ("nextVal") of a valid node (i.e., one that, at point of
@@ -2260,9 +2273,11 @@ public class ConcurrentHashMapV8
* This class extends ForkJoinTask to streamline parallel
* iteration in bulk operations (see BulkTask). This adds only an
* int of space overhead, which is close enough to negligible in
- * cases where it is not needed to not worry about it.
+ * cases where it is not needed to not worry about it. Because
+ * ForkJoinTask is Serializable, but iterators need not be, we
+ * need to add warning suppressions.
*/
- static class Traverser extends ForkJoinTask {
+ @SuppressWarnings("serial") static class Traverser extends ForkJoinTask {
final ConcurrentHashMapV8 map;
Node next; // the next entry to use
Node last; // the last entry used
@@ -2272,27 +2287,25 @@ public class ConcurrentHashMapV8
int index; // index of bin to use next
int baseIndex; // current index of initial table
int baseLimit; // index bound for initial table
- final int baseSize; // initial table size
+ int baseSize; // initial table size
/** Creates iterator for all entries in the table. */
Traverser(ConcurrentHashMapV8 map) {
- this.tab = (this.map = map).table;
- baseLimit = baseSize = (tab == null) ? 0 : tab.length;
+ this.map = map;
}
/** Creates iterator for split() methods */
- Traverser(Traverser it, boolean split) {
- this.map = it.map;
- this.tab = it.tab;
+ Traverser(Traverser it) {
+ ConcurrentHashMapV8 m; Node[] t;
+ if ((m = this.map = it.map) == null)
+ t = null;
+ else if ((t = it.tab) == null && // force parent tab initialization
+ (t = it.tab = m.table) != null)
+ it.baseLimit = it.baseSize = t.length;
+ this.tab = t;
this.baseSize = it.baseSize;
- int lo = it.baseIndex;
- int hi = this.baseLimit = it.baseLimit;
- int i;
- if (split) // adjust parent
- i = it.baseLimit = (lo + hi + 1) >>> 1;
- else // clone parent
- i = lo;
- this.index = this.baseIndex = i;
+ it.baseLimit = this.index = this.baseIndex =
+ ((this.baseLimit = it.baseLimit) + it.baseIndex + 1) >>> 1;
}
/**
@@ -2306,11 +2319,18 @@ public class ConcurrentHashMapV8
if (e != null) // advance past used/skipped node
e = e.next;
while (e == null) { // get to next non-null bin
+ ConcurrentHashMapV8 m;
Node[] t; int b, i, n; Object ek; // checks must use locals
- if ((b = baseIndex) >= baseLimit || (i = index) < 0 ||
- (t = tab) == null || i >= (n = t.length))
+ if ((t = tab) != null)
+ n = t.length;
+ else if ((m = map) != null && (t = tab = m.table) != null)
+ n = baseLimit = baseSize = t.length;
+ else
+ break outer;
+ if ((b = baseIndex) >= baseLimit ||
+ (i = index) < 0 || i >= n)
break outer;
- else if ((e = tabAt(t, i)) != null && e.hash == MOVED) {
+ if ((e = tabAt(t, i)) != null && e.hash == MOVED) {
if ((ek = e.key) instanceof TreeBin)
e = ((TreeBin)ek).first;
else {
@@ -2327,7 +2347,7 @@ public class ConcurrentHashMapV8
}
public final void remove() {
- if (nextVal == null)
+ if (nextVal == null && last == null)
advance();
Node e = last;
if (e == null)
@@ -2458,13 +2478,13 @@ public class ConcurrentHashMapV8
* instead of {@link #size} because a ConcurrentHashMap may
* contain more mappings than can be represented as an int. The
* value returned is a snapshot; the actual count may differ if
- * there are ongoing concurrent insertions of removals.
+ * there are ongoing concurrent insertions or removals.
*
* @return the number of mappings
*/
public long mappingCount() {
long n = counter.sum();
- return (n < 0L) ? 0L : n;
+ return (n < 0L) ? 0L : n; // ignore transient negative values
}
/**
@@ -2478,14 +2498,30 @@ public class ConcurrentHashMapV8
*
* @throws NullPointerException if the specified key is null
*/
- @SuppressWarnings("unchecked")
- public V get(Object key) {
+ @SuppressWarnings("unchecked") public V get(Object key) {
if (key == null)
throw new NullPointerException();
return (V)internalGet(key);
}
/**
+ * Returns the value to which the specified key is mapped,
+ * or the given defaultValue if this map contains no mapping for the key.
+ *
+ * @param key the key
+ * @param defaultValue the value to return if this map contains
+ * no mapping for the given key
+ * @return the mapping for the key, if present; else the defaultValue
+ * @throws NullPointerException if the specified key is null
+ */
+ @SuppressWarnings("unchecked") public V getValueOrDefault(Object key, V defaultValue) {
+ if (key == null)
+ throw new NullPointerException();
+ V v = (V) internalGet(key);
+ return v == null ? defaultValue : v;
+ }
+
+ /**
* Tests if the specified object is a key in this table.
*
* @param key possible key
@@ -2554,8 +2590,7 @@ public class ConcurrentHashMapV8
* {@code null} if there was no mapping for {@code key}
* @throws NullPointerException if the specified key or value is null
*/
- @SuppressWarnings("unchecked")
- public V put(K key, V value) {
+ @SuppressWarnings("unchecked") public V put(K key, V value) {
if (key == null || value == null)
throw new NullPointerException();
return (V)internalPut(key, value);
@@ -2568,8 +2603,7 @@ public class ConcurrentHashMapV8
* or {@code null} if there was no mapping for the key
* @throws NullPointerException if the specified key or value is null
*/
- @SuppressWarnings("unchecked")
- public V putIfAbsent(K key, V value) {
+ @SuppressWarnings("unchecked") public V putIfAbsent(K key, V value) {
if (key == null || value == null)
throw new NullPointerException();
return (V)internalPutIfAbsent(key, value);
@@ -2616,7 +2650,7 @@ public class ConcurrentHashMapV8
* @param key key with which the specified value is to be associated
* @param mappingFunction the function to compute a value
* @return the current (existing or computed) value associated with
- * the specified key, or null if the computed value is null.
+ * the specified key, or null if the computed value is null
* @throws NullPointerException if the specified key or mappingFunction
* is null
* @throws IllegalStateException if the computation detectably
@@ -2625,8 +2659,8 @@ public class ConcurrentHashMapV8
* @throws RuntimeException or Error if the mappingFunction does so,
* in which case the mapping is left unestablished
*/
- @SuppressWarnings("unchecked")
- public V computeIfAbsent(K key, Fun super K, ? extends V> mappingFunction) {
+ @SuppressWarnings("unchecked") public V computeIfAbsent
+ (K key, Fun super K, ? extends V> mappingFunction) {
if (key == null || mappingFunction == null)
throw new NullPointerException();
return (V)internalComputeIfAbsent(key, mappingFunction);
@@ -2657,8 +2691,7 @@ public class ConcurrentHashMapV8
*
* @param key key with which the specified value is to be associated
* @param remappingFunction the function to compute a value
- * @return the new value associated with
- * the specified key, or null if none.
+ * @return the new value associated with the specified key, or null if none
* @throws NullPointerException if the specified key or remappingFunction
* is null
* @throws IllegalStateException if the computation detectably
@@ -2667,7 +2700,8 @@ public class ConcurrentHashMapV8
* @throws RuntimeException or Error if the remappingFunction does so,
* in which case the mapping is unchanged
*/
- public V computeIfPresent(K key, BiFun super K, ? super V, ? extends V> remappingFunction) {
+ @SuppressWarnings("unchecked") public V computeIfPresent
+ (K key, BiFun super K, ? super V, ? extends V> remappingFunction) {
if (key == null || remappingFunction == null)
throw new NullPointerException();
return (V)internalCompute(key, true, remappingFunction);
@@ -2704,8 +2738,7 @@ public class ConcurrentHashMapV8
*
* @param key key with which the specified value is to be associated
* @param remappingFunction the function to compute a value
- * @return the new value associated with
- * the specified key, or null if none.
+ * @return the new value associated with the specified key, or null if none
* @throws NullPointerException if the specified key or remappingFunction
* is null
* @throws IllegalStateException if the computation detectably
@@ -2714,8 +2747,8 @@ public class ConcurrentHashMapV8
* @throws RuntimeException or Error if the remappingFunction does so,
* in which case the mapping is unchanged
*/
- // @SuppressWarnings("unchecked")
- public V compute(K key, BiFun super K, ? super V, ? extends V> remappingFunction) {
+ @SuppressWarnings("unchecked") public V compute
+ (K key, BiFun super K, ? super V, ? extends V> remappingFunction) {
if (key == null || remappingFunction == null)
throw new NullPointerException();
return (V)internalCompute(key, false, remappingFunction);
@@ -2746,8 +2779,8 @@ public class ConcurrentHashMapV8
* so the computation should be short and simple, and must not
* attempt to update any other mappings of this Map.
*/
- // @SuppressWarnings("unchecked")
- public V merge(K key, V value, BiFun super V, ? super V, ? extends V> remappingFunction) {
+ @SuppressWarnings("unchecked") public V merge
+ (K key, V value, BiFun super V, ? super V, ? extends V> remappingFunction) {
if (key == null || value == null || remappingFunction == null)
throw new NullPointerException();
return (V)internalMerge(key, value, remappingFunction);
@@ -2762,8 +2795,7 @@ public class ConcurrentHashMapV8
* {@code null} if there was no mapping for {@code key}
* @throws NullPointerException if the specified key is null
*/
- @SuppressWarnings("unchecked")
- public V remove(Object key) {
+ @SuppressWarnings("unchecked") public V remove(Object key) {
if (key == null)
throw new NullPointerException();
return (V)internalReplace(key, null, null);
@@ -2800,8 +2832,7 @@ public class ConcurrentHashMapV8
* or {@code null} if there was no mapping for the key
* @throws NullPointerException if the specified key or value is null
*/
- @SuppressWarnings("unchecked")
- public V replace(K key, V value) {
+ @SuppressWarnings("unchecked") public V replace(K key, V value) {
if (key == null || value == null)
throw new NullPointerException();
return (V)internalReplace(key, value, null);
@@ -3007,19 +3038,18 @@ public class ConcurrentHashMapV8
/* ----------------Iterators -------------- */
- static final class KeyIterator extends Traverser
+ @SuppressWarnings("serial") static final class KeyIterator extends Traverser
implements Spliterator, Enumeration {
KeyIterator(ConcurrentHashMapV8 map) { super(map); }
- KeyIterator(Traverser it, boolean split) {
- super(it, split);
+ KeyIterator(Traverser it) {
+ super(it);
}
public KeyIterator split() {
if (last != null || (next != null && nextVal == null))
throw new IllegalStateException();
- return new KeyIterator(this, true);
+ return new KeyIterator(this);
}
- @SuppressWarnings("unchecked")
- public final K next() {
+ @SuppressWarnings("unchecked") public final K next() {
if (nextVal == null && advance() == null)
throw new NoSuchElementException();
Object k = nextKey;
@@ -3030,20 +3060,19 @@ public class ConcurrentHashMapV8
public final K nextElement() { return next(); }
}
- static final class ValueIterator extends Traverser
+ @SuppressWarnings("serial") static final class ValueIterator extends Traverser
implements Spliterator, Enumeration {
ValueIterator(ConcurrentHashMapV8 map) { super(map); }
- ValueIterator(Traverser it, boolean split) {
- super(it, split);
+ ValueIterator(Traverser it) {
+ super(it);
}
public ValueIterator split() {
if (last != null || (next != null && nextVal == null))
throw new IllegalStateException();
- return new ValueIterator(this, true);
+ return new ValueIterator(this);
}
- @SuppressWarnings("unchecked")
- public final V next() {
+ @SuppressWarnings("unchecked") public final V next() {
Object v;
if ((v = nextVal) == null && (v = advance()) == null)
throw new NoSuchElementException();
@@ -3054,20 +3083,19 @@ public class ConcurrentHashMapV8
public final V nextElement() { return next(); }
}
- static final class EntryIterator extends Traverser
+ @SuppressWarnings("serial") static final class EntryIterator extends Traverser
implements Spliterator> {
EntryIterator(ConcurrentHashMapV8 map) { super(map); }
- EntryIterator(Traverser it, boolean split) {
- super(it, split);
+ EntryIterator(Traverser it) {
+ super(it);
}
public EntryIterator split() {
if (last != null || (next != null && nextVal == null))
throw new IllegalStateException();
- return new EntryIterator(this, true);
+ return new EntryIterator(this);
}
- @SuppressWarnings("unchecked")
- public final Map.Entry next() {
+ @SuppressWarnings("unchecked") public final Map.Entry next() {
Object v;
if ((v = nextVal) == null && (v = advance()) == null)
throw new NoSuchElementException();
@@ -3162,8 +3190,7 @@ public class ConcurrentHashMapV8
return (i == n) ? r : Arrays.copyOf(r, i);
}
- @SuppressWarnings("unchecked")
- public final T[] toArray(T[] a) {
+ @SuppressWarnings("unchecked") public final T[] toArray(T[] a) {
long sz = map.mappingCount();
if (sz > (long)(MAX_ARRAY_SIZE))
throw new OutOfMemoryError(oomeMsg);
@@ -3359,8 +3386,7 @@ public class ConcurrentHashMapV8
* for each key-value mapping, followed by a null pair.
* The key-value mappings are emitted in no particular order.
*/
- @SuppressWarnings("unchecked")
- private void writeObject(java.io.ObjectOutputStream s)
+ @SuppressWarnings("unchecked") private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
if (segments == null) { // for serialization compatibility
segments = (Segment[])
@@ -3384,8 +3410,7 @@ public class ConcurrentHashMapV8
* Reconstitutes the instance from a stream (that is, deserializes it).
* @param s the stream
*/
- @SuppressWarnings("unchecked")
- private void readObject(java.io.ObjectInputStream s)
+ @SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
s.defaultReadObject();
this.segments = null; // unneeded
@@ -3646,8 +3671,8 @@ public class ConcurrentHashMapV8
* of each (key, value).
*
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
- * which case the action is not applied).
+ * for an element, or null if there is no transformation (in
+ * which case the action is not applied)
* @param action the action
*/
public void forEach(BiFun super K, ? super V, ? extends U> transformer,
@@ -3658,10 +3683,10 @@ public class ConcurrentHashMapV8
/**
* Returns a non-null result from applying the given search
- * function on each (key, value), or null if none. Further
- * element processing is suppressed upon success. However,
- * this method does not return until other in-progress
- * parallel invocations of the search function also complete.
+ * function on each (key, value), or null if none. Upon
+ * success, further element processing is suppressed and the
+ * results of any other parallel invocations of the search
+ * function are ignored.
*
* @param searchFunction a function returning a non-null
* result on success, else null
@@ -3679,8 +3704,8 @@ public class ConcurrentHashMapV8
* combine values, or null if none.
*
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
- * which case it is not combined).
+ * for an element, or null if there is no transformation (in
+ * which case it is not combined)
* @param reducer a commutative associative combining function
* @return the result of accumulating the given transformation
* of all (key, value) pairs
@@ -3720,8 +3745,7 @@ public class ConcurrentHashMapV8
* @param basis the identity (initial default value) for the reduction
* @param reducer a commutative associative combining function
* @return the result of accumulating the given transformation
- * of all (key, value) pairs using the given reducer to
- * combine values, and the given basis as an identity value.
+ * of all (key, value) pairs
*/
public long reduceToLong(ObjectByObjectToLong super K, ? super V> transformer,
long basis,
@@ -3750,7 +3774,7 @@ public class ConcurrentHashMapV8
}
/**
- * Performs the given action for each key
+ * Performs the given action for each key.
*
* @param action the action
*/
@@ -3761,11 +3785,11 @@ public class ConcurrentHashMapV8
/**
* Performs the given action for each non-null transformation
- * of each key
+ * of each key.
*
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
- * which case the action is not applied).
+ * for an element, or null if there is no transformation (in
+ * which case the action is not applied)
* @param action the action
*/
public void forEachKey(Fun super K, ? extends U> transformer,
@@ -3776,10 +3800,10 @@ public class ConcurrentHashMapV8
/**
* Returns a non-null result from applying the given search
- * function on each key, or null if none. Further element
- * processing is suppressed upon success. However, this method
- * does not return until other in-progress parallel
- * invocations of the search function also complete.
+ * function on each key, or null if none. Upon success,
+ * further element processing is suppressed and the results of
+ * any other parallel invocations of the search function are
+ * ignored.
*
* @param searchFunction a function returning a non-null
* result on success, else null
@@ -3810,8 +3834,8 @@ public class ConcurrentHashMapV8
* null if none.
*
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
- * which case it is not combined).
+ * for an element, or null if there is no transformation (in
+ * which case it is not combined)
* @param reducer a commutative associative combining function
* @return the result of accumulating the given transformation
* of all keys
@@ -3880,7 +3904,7 @@ public class ConcurrentHashMapV8
}
/**
- * Performs the given action for each value
+ * Performs the given action for each value.
*
* @param action the action
*/
@@ -3891,11 +3915,11 @@ public class ConcurrentHashMapV8
/**
* Performs the given action for each non-null transformation
- * of each value
+ * of each value.
*
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
- * which case the action is not applied).
+ * for an element, or null if there is no transformation (in
+ * which case the action is not applied)
*/
public void forEachValue(Fun super V, ? extends U> transformer,
Action action) {
@@ -3905,10 +3929,10 @@ public class ConcurrentHashMapV8
/**
* Returns a non-null result from applying the given search
- * function on each value, or null if none. Further element
- * processing is suppressed upon success. However, this method
- * does not return until other in-progress parallel
- * invocations of the search function also complete.
+ * function on each value, or null if none. Upon success,
+ * further element processing is suppressed and the results of
+ * any other parallel invocations of the search function are
+ * ignored.
*
* @param searchFunction a function returning a non-null
* result on success, else null
@@ -3939,8 +3963,8 @@ public class ConcurrentHashMapV8
* null if none.
*
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
- * which case it is not combined).
+ * for an element, or null if there is no transformation (in
+ * which case it is not combined)
* @param reducer a commutative associative combining function
* @return the result of accumulating the given transformation
* of all values
@@ -4009,7 +4033,7 @@ public class ConcurrentHashMapV8
}
/**
- * Perform the given action for each entry
+ * Performs the given action for each entry.
*
* @param action the action
*/
@@ -4019,12 +4043,12 @@ public class ConcurrentHashMapV8
}
/**
- * Perform the given action for each non-null transformation
- * of each entry
+ * Performs the given action for each non-null transformation
+ * of each entry.
*
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
- * which case the action is not applied).
+ * for an element, or null if there is no transformation (in
+ * which case the action is not applied)
* @param action the action
*/
public void forEachEntry(Fun, ? extends U> transformer,
@@ -4035,10 +4059,10 @@ public class ConcurrentHashMapV8
/**
* Returns a non-null result from applying the given search
- * function on each entry, or null if none. Further element
- * processing is suppressed upon success. However, this method
- * does not return until other in-progress parallel
- * invocations of the search function also complete.
+ * function on each entry, or null if none. Upon success,
+ * further element processing is suppressed and the results of
+ * any other parallel invocations of the search function are
+ * ignored.
*
* @param searchFunction a function returning a non-null
* result on success, else null
@@ -4068,7 +4092,7 @@ public class ConcurrentHashMapV8
* or null if none.
*
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
+ * for an element, or null if there is no transformation (in
* which case it is not combined).
* @param reducer a commutative associative combining function
* @return the result of accumulating the given transformation
@@ -4163,7 +4187,7 @@ public class ConcurrentHashMapV8
(ConcurrentHashMapV8 map,
BiAction action) {
if (action == null) throw new NullPointerException();
- return new ForEachMappingTask(map, action);
+ return new ForEachMappingTask(map, null, -1, action);
}
/**
@@ -4172,8 +4196,8 @@ public class ConcurrentHashMapV8
*
* @param map the map
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
- * which case the action is not applied).
+ * for an element, or null if there is no transformation (in
+ * which case the action is not applied)
* @param action the action
* @return the task
*/
@@ -4184,16 +4208,15 @@ public class ConcurrentHashMapV8
if (transformer == null || action == null)
throw new NullPointerException();
return new ForEachTransformedMappingTask
- (map, transformer, action);
+ (map, null, -1, transformer, action);
}
/**
- * Returns a task that when invoked, returns a non-null
- * result from applying the given search function on each
- * (key, value), or null if none. Further element processing
- * is suppressed upon success. However, this method does not
- * return until other in-progress parallel invocations of the
- * search function also complete.
+ * Returns a task that when invoked, returns a non-null result
+ * from applying the given search function on each (key,
+ * value), or null if none. Upon success, further element
+ * processing is suppressed and the results of any other
+ * parallel invocations of the search function are ignored.
*
* @param map the map
* @param searchFunction a function returning a non-null
@@ -4205,7 +4228,7 @@ public class ConcurrentHashMapV8
BiFun super K, ? super V, ? extends U> searchFunction) {
if (searchFunction == null) throw new NullPointerException();
return new SearchMappingsTask
- (map, searchFunction,
+ (map, null, -1, searchFunction,
new AtomicReference());
}
@@ -4216,7 +4239,7 @@ public class ConcurrentHashMapV8
*
* @param map the map
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
+ * for an element, or null if there is no transformation (in
* which case it is not combined).
* @param reducer a commutative associative combining function
* @return the task
@@ -4228,7 +4251,7 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceMappingsTask
- (map, transformer, reducer);
+ (map, null, -1, null, transformer, reducer);
}
/**
@@ -4252,7 +4275,7 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceMappingsToDoubleTask
- (map, transformer, basis, reducer);
+ (map, null, -1, null, transformer, basis, reducer);
}
/**
@@ -4276,7 +4299,7 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceMappingsToLongTask
- (map, transformer, basis, reducer);
+ (map, null, -1, null, transformer, basis, reducer);
}
/**
@@ -4299,12 +4322,12 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceMappingsToIntTask
- (map, transformer, basis, reducer);
+ (map, null, -1, null, transformer, basis, reducer);
}
/**
* Returns a task that when invoked, performs the given action
- * for each key
+ * for each key.
*
* @param map the map
* @param action the action
@@ -4314,17 +4337,17 @@ public class ConcurrentHashMapV8
(ConcurrentHashMapV8 map,
Action action) {
if (action == null) throw new NullPointerException();
- return new ForEachKeyTask(map, action);
+ return new ForEachKeyTask(map, null, -1, action);
}
/**
* Returns a task that when invoked, performs the given action
- * for each non-null transformation of each key
+ * for each non-null transformation of each key.
*
* @param map the map
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
- * which case the action is not applied).
+ * for an element, or null if there is no transformation (in
+ * which case the action is not applied)
* @param action the action
* @return the task
*/
@@ -4335,16 +4358,15 @@ public class ConcurrentHashMapV8
if (transformer == null || action == null)
throw new NullPointerException();
return new ForEachTransformedKeyTask
- (map, transformer, action);
+ (map, null, -1, transformer, action);
}
/**
* Returns a task that when invoked, returns a non-null result
* from applying the given search function on each key, or
- * null if none. Further element processing is suppressed
- * upon success. However, this method does not return until
- * other in-progress parallel invocations of the search
- * function also complete.
+ * null if none. Upon success, further element processing is
+ * suppressed and the results of any other parallel
+ * invocations of the search function are ignored.
*
* @param map the map
* @param searchFunction a function returning a non-null
@@ -4356,7 +4378,7 @@ public class ConcurrentHashMapV8
Fun super K, ? extends U> searchFunction) {
if (searchFunction == null) throw new NullPointerException();
return new SearchKeysTask
- (map, searchFunction,
+ (map, null, -1, searchFunction,
new AtomicReference());
}
@@ -4374,8 +4396,9 @@ public class ConcurrentHashMapV8
BiFun super K, ? super K, ? extends K> reducer) {
if (reducer == null) throw new NullPointerException();
return new ReduceKeysTask
- (map, reducer);
+ (map, null, -1, null, reducer);
}
+
/**
* Returns a task that when invoked, returns the result of
* accumulating the given transformation of all keys using the given
@@ -4383,7 +4406,7 @@ public class ConcurrentHashMapV8
*
* @param map the map
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
+ * for an element, or null if there is no transformation (in
* which case it is not combined).
* @param reducer a commutative associative combining function
* @return the task
@@ -4395,7 +4418,7 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceKeysTask
- (map, transformer, reducer);
+ (map, null, -1, null, transformer, reducer);
}
/**
@@ -4419,7 +4442,7 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceKeysToDoubleTask
- (map, transformer, basis, reducer);
+ (map, null, -1, null, transformer, basis, reducer);
}
/**
@@ -4443,7 +4466,7 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceKeysToLongTask
- (map, transformer, basis, reducer);
+ (map, null, -1, null, transformer, basis, reducer);
}
/**
@@ -4467,12 +4490,12 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceKeysToIntTask
- (map, transformer, basis, reducer);
+ (map, null, -1, null, transformer, basis, reducer);
}
/**
* Returns a task that when invoked, performs the given action
- * for each value
+ * for each value.
*
* @param map the map
* @param action the action
@@ -4481,17 +4504,17 @@ public class ConcurrentHashMapV8
(ConcurrentHashMapV8 map,
Action action) {
if (action == null) throw new NullPointerException();
- return new ForEachValueTask(map, action);
+ return new ForEachValueTask(map, null, -1, action);
}
/**
* Returns a task that when invoked, performs the given action
- * for each non-null transformation of each value
+ * for each non-null transformation of each value.
*
* @param map the map
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
- * which case the action is not applied).
+ * for an element, or null if there is no transformation (in
+ * which case the action is not applied)
* @param action the action
*/
public static ForkJoinTask forEachValue
@@ -4501,16 +4524,15 @@ public class ConcurrentHashMapV8
if (transformer == null || action == null)
throw new NullPointerException();
return new ForEachTransformedValueTask
- (map, transformer, action);
+ (map, null, -1, transformer, action);
}
/**
* Returns a task that when invoked, returns a non-null result
* from applying the given search function on each value, or
- * null if none. Further element processing is suppressed
- * upon success. However, this method does not return until
- * other in-progress parallel invocations of the search
- * function also complete.
+ * null if none. Upon success, further element processing is
+ * suppressed and the results of any other parallel
+ * invocations of the search function are ignored.
*
* @param map the map
* @param searchFunction a function returning a non-null
@@ -4523,7 +4545,7 @@ public class ConcurrentHashMapV8
Fun super V, ? extends U> searchFunction) {
if (searchFunction == null) throw new NullPointerException();
return new SearchValuesTask
- (map, searchFunction,
+ (map, null, -1, searchFunction,
new AtomicReference());
}
@@ -4541,7 +4563,7 @@ public class ConcurrentHashMapV8
BiFun super V, ? super V, ? extends V> reducer) {
if (reducer == null) throw new NullPointerException();
return new ReduceValuesTask
- (map, reducer);
+ (map, null, -1, null, reducer);
}
/**
@@ -4551,7 +4573,7 @@ public class ConcurrentHashMapV8
*
* @param map the map
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
+ * for an element, or null if there is no transformation (in
* which case it is not combined).
* @param reducer a commutative associative combining function
* @return the task
@@ -4563,7 +4585,7 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceValuesTask
- (map, transformer, reducer);
+ (map, null, -1, null, transformer, reducer);
}
/**
@@ -4587,7 +4609,7 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceValuesToDoubleTask
- (map, transformer, basis, reducer);
+ (map, null, -1, null, transformer, basis, reducer);
}
/**
@@ -4611,7 +4633,7 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceValuesToLongTask
- (map, transformer, basis, reducer);
+ (map, null, -1, null, transformer, basis, reducer);
}
/**
@@ -4635,12 +4657,12 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceValuesToIntTask
- (map, transformer, basis, reducer);
+ (map, null, -1, null, transformer, basis, reducer);
}
/**
* Returns a task that when invoked, perform the given action
- * for each entry
+ * for each entry.
*
* @param map the map
* @param action the action
@@ -4649,17 +4671,17 @@ public class ConcurrentHashMapV8
(ConcurrentHashMapV8 map,
Action> action) {
if (action == null) throw new NullPointerException();
- return new ForEachEntryTask(map, action);
+ return new ForEachEntryTask(map, null, -1, action);
}
/**
* Returns a task that when invoked, perform the given action
- * for each non-null transformation of each entry
+ * for each non-null transformation of each entry.
*
* @param map the map
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
- * which case the action is not applied).
+ * for an element, or null if there is no transformation (in
+ * which case the action is not applied)
* @param action the action
*/
public static ForkJoinTask forEachEntry
@@ -4669,16 +4691,15 @@ public class ConcurrentHashMapV8
if (transformer == null || action == null)
throw new NullPointerException();
return new ForEachTransformedEntryTask
- (map, transformer, action);
+ (map, null, -1, transformer, action);
}
/**
* Returns a task that when invoked, returns a non-null result
* from applying the given search function on each entry, or
- * null if none. Further element processing is suppressed
- * upon success. However, this method does not return until
- * other in-progress parallel invocations of the search
- * function also complete.
+ * null if none. Upon success, further element processing is
+ * suppressed and the results of any other parallel
+ * invocations of the search function are ignored.
*
* @param map the map
* @param searchFunction a function returning a non-null
@@ -4691,7 +4712,7 @@ public class ConcurrentHashMapV8
Fun, ? extends U> searchFunction) {
if (searchFunction == null) throw new NullPointerException();
return new SearchEntriesTask
- (map, searchFunction,
+ (map, null, -1, searchFunction,
new AtomicReference());
}
@@ -4709,7 +4730,7 @@ public class ConcurrentHashMapV8
BiFun, Map.Entry, ? extends Map.Entry> reducer) {
if (reducer == null) throw new NullPointerException();
return new ReduceEntriesTask
- (map, reducer);
+ (map, null, -1, null, reducer);
}
/**
@@ -4719,7 +4740,7 @@ public class ConcurrentHashMapV8
*
* @param map the map
* @param transformer a function returning the transformation
- * for an element, or null of there is no transformation (in
+ * for an element, or null if there is no transformation (in
* which case it is not combined).
* @param reducer a commutative associative combining function
* @return the task
@@ -4731,7 +4752,7 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceEntriesTask
- (map, transformer, reducer);
+ (map, null, -1, null, transformer, reducer);
}
/**
@@ -4755,7 +4776,7 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceEntriesToDoubleTask
- (map, transformer, basis, reducer);
+ (map, null, -1, null, transformer, basis, reducer);
}
/**
@@ -4779,7 +4800,7 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceEntriesToLongTask
- (map, transformer, basis, reducer);
+ (map, null, -1, null, transformer, basis, reducer);
}
/**
@@ -4803,7 +4824,7 @@ public class ConcurrentHashMapV8
if (transformer == null || reducer == null)
throw new NullPointerException();
return new MapReduceEntriesToIntTask
- (map, transformer, basis, reducer);
+ (map, null, -1, null, transformer, basis, reducer);
}
}
@@ -4820,29 +4841,33 @@ public class ConcurrentHashMapV8
* exceptions are handled in a simpler manner, by just trying to
* complete root task exceptionally.
*/
- static abstract class BulkTask extends Traverser {
+ @SuppressWarnings("serial") static abstract class BulkTask extends Traverser {
final BulkTask parent; // completion target
- int batch; // split control
+ int batch; // split control; -1 for unknown
int pending; // completion control
- /** Constructor for root tasks */
- BulkTask(ConcurrentHashMapV8 map) {
+ BulkTask(ConcurrentHashMapV8 map, BulkTask parent,
+ int batch) {
super(map);
- this.parent = null;
- this.batch = -1; // force call to batch() on execution
- }
-
- /** Constructor for subtasks */
- BulkTask(BulkTask parent, int batch, boolean split) {
- super(parent, split);
this.parent = parent;
this.batch = batch;
+ if (parent != null && map != null) { // split parent
+ Node[] t;
+ if ((t = parent.tab) == null &&
+ (t = parent.tab = map.table) != null)
+ parent.baseLimit = parent.baseSize = t.length;
+ this.tab = t;
+ this.baseSize = parent.baseSize;
+ int hi = this.baseLimit = parent.baseLimit;
+ parent.baseLimit = this.index = this.baseIndex =
+ (hi + parent.baseIndex + 1) >>> 1;
+ }
}
// FJ methods
/**
- * Propagate completion. Note that all reduce actions
+ * Propagates completion. Note that all reduce actions
* bypass this method to combine while completing.
*/
final void tryComplete() {
@@ -4860,31 +4885,31 @@ public class ConcurrentHashMapV8
}
/**
- * Force root task to throw exception unless already complete.
+ * Forces root task to complete.
+ * @param ex if null, complete normally, else exceptionally
+ * @return false to simplify use
*/
- final void tryAbortComputation(Throwable ex) {
+ final boolean tryCompleteComputation(Throwable ex) {
for (BulkTask a = this;;) {
BulkTask p = a.parent;
if (p == null) {
- a.completeExceptionally(ex);
- break;
+ if (ex != null)
+ a.completeExceptionally(ex);
+ else
+ a.quietlyComplete();
+ return false;
}
a = p;
}
}
- public final boolean exec() {
- try {
- compute();
- }
- catch (Throwable ex) {
- tryAbortComputation(ex);
- }
- return false;
+ /**
+ * Version of tryCompleteComputation for function screening checks
+ */
+ final boolean abortOnNullFunction() {
+ return tryCompleteComputation(new Error("Unexpected null function"));
}
- public abstract void compute();
-
// utilities
/** CompareAndSet pending count */
@@ -4893,33 +4918,31 @@ public class ConcurrentHashMapV8
}
/**
- * Return approx exp2 of the number of times (minus one) to
+ * Returns approx exp2 of the number of times (minus one) to
* split task by two before executing leaf action. This value
* is faster to compute and more convenient to use as a guide
* to splitting than is the depth, since it is used while
* dividing by two anyway.
*/
final int batch() {
- int b = batch;
- if (b < 0) {
- long n = map.counter.sum();
- int sp = getPool().getParallelism() << 3; // slack of 8
- b = batch = (n <= 0L) ? 0 : (n < (long)sp) ? (int)n : sp;
+ ConcurrentHashMapV8 m; int b; Node[] t;
+ if ((b = batch) < 0 && (m = map) != null) { // force initialization
+ if ((t = tab) == null && (t = tab = m.table) != null)
+ baseLimit = baseSize = t.length;
+ if (t != null) {
+ long n = m.counter.sum();
+ int sp = getPool().getParallelism() << 3; // slack of 8
+ b = batch = (n <= 0L) ? 0 : (n < (long)sp) ? (int)n : sp;
+ }
}
return b;
}
/**
- * Error message for hoisted null checks of functions
- */
- static final String NullFunctionMessage =
- "Unexpected null function";
-
- /**
- * Return exportable snapshot entry
+ * Returns exportable snapshot entry.
*/
static AbstractMap.SimpleEntry entryFor(K k, V v) {
- return new AbstractMap.SimpleEntry(k, v);
+ return new AbstractMap.SimpleEntry(k, v);
}
// Unsafe mechanics
@@ -4927,7 +4950,7 @@ public class ConcurrentHashMapV8
private static final long PENDING;
static {
try {
- U = sun.misc.Unsafe.getUnsafe();
+ U = getUnsafe();
PENDING = U.objectFieldOffset
(BulkTask.class.getDeclaredField("pending"));
} catch (Exception e) {
@@ -4942,1763 +4965,1550 @@ public class ConcurrentHashMapV8
* others.
*/
- static final class ForEachKeyTask
+ @SuppressWarnings("serial") static final class ForEachKeyTask
extends BulkTask {
final Action action;
ForEachKeyTask
- (ConcurrentHashMapV8 m,
- Action action) {
- super(m);
- this.action = action;
- }
- ForEachKeyTask
- (BulkTask p, int b, boolean split,
+ (ConcurrentHashMapV8 m, BulkTask p, int b,
Action action) {
- super(p, b, split);
+ super(m, p, b);
this.action = action;
}
- public final void compute() {
+ @SuppressWarnings("unchecked") public final boolean exec() {
final Action action = this.action;
if (action == null)
- throw new Error(NullFunctionMessage);
- int b = batch(), c;
- while (b > 1 && baseIndex != baseLimit) {
- do {} while (!casPending(c = pending, c+1));
- new ForEachKeyTask(this, b >>>= 1, true, action).fork();
+ return abortOnNullFunction();
+ try {
+ int b = batch(), c;
+ while (b > 1 && baseIndex != baseLimit) {
+ do {} while (!casPending(c = pending, c+1));
+ new ForEachKeyTask(map, this, b >>>= 1, action).fork();
+ }
+ while (advance() != null)
+ action.apply((K)nextKey);
+ tryComplete();
+ } catch (Throwable ex) {
+ return tryCompleteComputation(ex);
}
- while (advance() != null)
- action.apply((K)nextKey);
- tryComplete();
+ return false;
}
}
- static final class ForEachValueTask
+ @SuppressWarnings("serial") static final class ForEachValueTask
extends BulkTask {
final Action action;
ForEachValueTask
- (ConcurrentHashMapV8 m,
- Action action) {
- super(m);
- this.action = action;
- }
- ForEachValueTask
- (BulkTask p, int b, boolean split,
+ (ConcurrentHashMapV8 m, BulkTask p, int b,
Action action) {
- super(p, b, split);
+ super(m, p, b);
this.action = action;
}
- public final void compute() {
+ @SuppressWarnings("unchecked") public final boolean exec() {
final Action action = this.action;
if (action == null)
- throw new Error(NullFunctionMessage);
- int b = batch(), c;
- while (b > 1 && baseIndex != baseLimit) {
- do {} while (!casPending(c = pending, c+1));
- new ForEachValueTask(this, b >>>= 1, true, action).fork();
+ return abortOnNullFunction();
+ try {
+ int b = batch(), c;
+ while (b > 1 && baseIndex != baseLimit) {
+ do {} while (!casPending(c = pending, c+1));
+ new ForEachValueTask(map, this, b >>>= 1, action).fork();
+ }
+ Object v;
+ while ((v = advance()) != null)
+ action.apply((V)v);
+ tryComplete();
+ } catch (Throwable ex) {
+ return tryCompleteComputation(ex);
}
- Object v;
- while ((v = advance()) != null)
- action.apply((V)v);
- tryComplete();
+ return false;
}
}
- static final class ForEachEntryTask
+ @SuppressWarnings("serial") static final class ForEachEntryTask
extends BulkTask {
final Action> action;
ForEachEntryTask
- (ConcurrentHashMapV8 m,
+ (ConcurrentHashMapV8 m, BulkTask p, int b,
Action> action) {
- super(m);
+ super(m, p, b);
this.action = action;
}
- ForEachEntryTask
- (BulkTask p, int b, boolean split,
- Action