* portion of the elements, and so may be amenable to parallel
* execution.
*
- * This interface exports a subset of expected JDK8
+ *
This interface exports a subset of expected JDK8
* functionality.
*
*
Sample usage: Here is one (of the several) ways to compute
@@ -285,76 +309,6 @@ public class ConcurrentHashMapV8
Spliterator split();
}
- /**
- * A view of a ConcurrentHashMapV8 as a {@link Set} of keys, in
- * which additions may optionally be enabled by mapping to a
- * common value. This class cannot be directly instantiated. See
- * {@link #keySet}, {@link #keySet(Object)}, {@link #newKeySet()},
- * {@link #newKeySet(int)}.
- *
- * The view's {@code iterator} is a "weakly consistent" iterator
- * that will never throw {@link ConcurrentModificationException},
- * and guarantees to traverse elements as they existed upon
- * construction of the iterator, and may (but is not guaranteed to)
- * reflect any modifications subsequent to construction.
- */
- public static class KeySetView extends CHMView implements Set, java.io.Serializable {
- private static final long serialVersionUID = 7249069246763182397L;
- private final V value;
- KeySetView(ConcurrentHashMapV8 map, V value) { // non-public
- super(map);
- this.value = value;
- }
-
- /**
- * Returns the map backing this view.
- *
- * @return the map backing this view
- */
- public ConcurrentHashMapV8 getMap() { return map; }
-
- /**
- * Returns the default mapped value for additions,
- * or {@code null} if additions are not supported.
- *
- * @return the default mapped value for additions, or {@code null}
- * if not supported.
- */
- public V getMappedValue() { return value; }
-
- // implement Set API
-
- public boolean contains(Object o) { return map.containsKey(o); }
- public boolean remove(Object o) { return map.remove(o) != null; }
- public Iterator iterator() { return new KeyIterator(map); }
- public boolean add(K e) {
- V v;
- if ((v = value) == null)
- throw new UnsupportedOperationException();
- if (e == null)
- throw new NullPointerException();
- return map.internalPutIfAbsent(e, v) == null;
- }
- public boolean addAll(Collection c) {
- boolean added = false;
- V v;
- if ((v = value) == null)
- throw new UnsupportedOperationException();
- for (K e : c) {
- if (e == null)
- throw new NullPointerException();
- if (map.internalPutIfAbsent(e, v) == null)
- added = true;
- }
- return added;
- }
- public boolean equals(Object o) {
- Set c;
- return ((o instanceof Set) &&
- ((c = (Set)o) == this ||
- (containsAll(c) && c.containsAll(this))));
- }
- }
/*
* Overview:
@@ -639,8 +593,8 @@ public class ConcurrentHashMapV8
// views
private transient KeySetView keySet;
- private transient Values values;
- private transient EntrySet entrySet;
+ private transient ValuesView values;
+ private transient EntrySetView entrySet;
/** For serialization compatibility. Null unless serialized; see below */
private Segment[] segments;
@@ -739,7 +693,10 @@ public class ConcurrentHashMapV8
try {
wait();
} catch (InterruptedException ie) {
- Thread.currentThread().interrupt();
+ try {
+ Thread.currentThread().interrupt();
+ } catch (SecurityException ignore) {
+ }
}
}
else
@@ -2448,14 +2405,14 @@ public class ConcurrentHashMapV8
* across threads, iteration terminates if a bounds checks fails
* for a table read.
*
- * 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. Because
- * ForkJoinTask is Serializable, but iterators need not be, we
- * need to add warning suppressions.
+ * This class extends CountedCompleter to streamline parallel
+ * iteration in bulk operations. This adds only a few fields of
+ * space overhead, which is small enough in cases where it is not
+ * needed to not worry about it. Because CountedCompleter is
+ * Serializable, but iterators need not be, we need to add warning
+ * suppressions.
*/
- @SuppressWarnings("serial") static class Traverser extends ForkJoinTask {
+ @SuppressWarnings("serial") static class Traverser extends CountedCompleter {
final ConcurrentHashMapV8 map;
Node next; // the next entry to use
Object nextKey; // cached key field of next
@@ -2465,24 +2422,28 @@ public class ConcurrentHashMapV8
int baseIndex; // current index of initial table
int baseLimit; // index bound for initial table
int baseSize; // initial table size
+ int batch; // split control
/** Creates iterator for all entries in the table. */
Traverser(ConcurrentHashMapV8 map) {
this.map = map;
}
- /** Creates iterator for split() methods */
- 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;
- it.baseLimit = this.index = this.baseIndex =
- ((this.baseLimit = it.baseLimit) + it.baseIndex + 1) >>> 1;
+ /** Creates iterator for split() methods and task constructors */
+ Traverser(ConcurrentHashMapV8 map, Traverser it, int batch) {
+ super(it);
+ this.batch = batch;
+ if ((this.map = map) != null && it != null) { // split parent
+ Node[] t;
+ if ((t = it.tab) == null &&
+ (t = it.tab = map.table) != null)
+ it.baseLimit = it.baseSize = t.length;
+ this.tab = t;
+ this.baseSize = it.baseSize;
+ int hi = this.baseLimit = it.baseLimit;
+ it.baseLimit = this.index = this.baseIndex =
+ (hi + it.baseIndex + 1) >>> 1;
+ }
}
/**
@@ -2535,9 +2496,39 @@ public class ConcurrentHashMapV8
}
public final boolean hasMoreElements() { return hasNext(); }
- public final void setRawResult(Object x) { }
- public R getRawResult() { return null; }
- public boolean exec() { return true; }
+
+ public void compute() { } // default no-op CountedCompleter body
+
+ /**
+ * Returns a batch value > 0 if this task should (and must) be
+ * split, if so, adding to pending count, and in any case
+ * updating batch value. The initial batch value is 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 preSplit() {
+ ConcurrentHashMapV8 m; int b; Node[] t; ForkJoinPool pool;
+ 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 par = ((pool = getPool()) == null) ?
+ ForkJoinPool.getCommonPoolParallelism() :
+ pool.getParallelism();
+ int sp = par << 3; // slack of 8
+ b = (n <= 0L) ? 0 : (n < (long)sp) ? (int)n : sp;
+ }
+ }
+ b = (b <= 1 || baseIndex == baseLimit) ? 0 : (b >>> 1);
+ if ((batch = b) > 0)
+ addToPendingCount(1);
+ return b;
+ }
+
}
/* ---------------- Public operations -------------- */
@@ -2677,8 +2668,8 @@ public class ConcurrentHashMapV8
* Returns the number of mappings. This method should be used
* instead of {@link #size} because a ConcurrentHashMapV8 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 or removals.
+ * value returned is an estimate; the actual count may differ if
+ * there are concurrent insertions or removals.
*
* @return the number of mappings
*/
@@ -2781,7 +2772,7 @@ public class ConcurrentHashMapV8
* Maps the specified key to the specified value in this table.
* Neither the key nor the value can be null.
*
- * The value can be retrieved by calling the {@code get} method
+ *
The value can be retrieved by calling the {@code get} method
* with a key that is equal to the original key.
*
* @param key key with which the specified value is to be associated
@@ -3078,22 +3069,11 @@ public class ConcurrentHashMapV8
/**
* Returns a {@link 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 {@code Iterator.remove},
- * {@code Collection.remove}, {@code removeAll},
- * {@code retainAll}, and {@code clear} operations. It does not
- * support the {@code add} or {@code addAll} operations.
- *
- * The view's {@code iterator} is a "weakly consistent" iterator
- * that will never throw {@link ConcurrentModificationException},
- * and guarantees to traverse elements as they existed upon
- * construction of the iterator, and may (but is not guaranteed to)
- * reflect any modifications subsequent to construction.
+ * reflected in the collection, and vice-versa.
*/
- public Collection values() {
- Values vs = values;
- return (vs != null) ? vs : (values = new Values(this));
+ public ValuesView values() {
+ ValuesView vs = values;
+ return (vs != null) ? vs : (values = new ValuesView(this));
}
/**
@@ -3113,8 +3093,8 @@ public class ConcurrentHashMapV8
* reflect any modifications subsequent to construction.
*/
public Set> entrySet() {
- EntrySet es = entrySet;
- return (es != null) ? es : (entrySet = new EntrySet(this));
+ EntrySetView es = entrySet;
+ return (es != null) ? es : (entrySet = new EntrySetView(this));
}
/**
@@ -3250,13 +3230,13 @@ public class ConcurrentHashMapV8
@SuppressWarnings("serial") static final class KeyIterator extends Traverser
implements Spliterator, Enumeration {
KeyIterator(ConcurrentHashMapV8 map) { super(map); }
- KeyIterator(Traverser it) {
- super(it);
+ KeyIterator(ConcurrentHashMapV8 map, Traverser it) {
+ super(map, it, -1);
}
public KeyIterator split() {
if (nextKey != null)
throw new IllegalStateException();
- return new KeyIterator(this);
+ return new KeyIterator(map, this);
}
@SuppressWarnings("unchecked") public final K next() {
if (nextVal == null && advance() == null)
@@ -3272,13 +3252,13 @@ public class ConcurrentHashMapV8
@SuppressWarnings("serial") static final class ValueIterator extends Traverser
implements Spliterator, Enumeration {
ValueIterator(ConcurrentHashMapV8 map) { super(map); }
- ValueIterator(Traverser it) {
- super(it);
+ ValueIterator(ConcurrentHashMapV8 map, Traverser it) {
+ super(map, it, -1);
}
public ValueIterator split() {
if (nextKey != null)
throw new IllegalStateException();
- return new ValueIterator(this);
+ return new ValueIterator(map, this);
}
@SuppressWarnings("unchecked") public final V next() {
@@ -3295,13 +3275,13 @@ public class ConcurrentHashMapV8
@SuppressWarnings("serial") static final class EntryIterator extends Traverser
implements Spliterator> {
EntryIterator(ConcurrentHashMapV8 map) { super(map); }
- EntryIterator(Traverser it) {
- super(it);
+ EntryIterator(ConcurrentHashMapV8 map, Traverser it) {
+ super(map, it, -1);
}
public EntryIterator split() {
if (nextKey != null)
throw new IllegalStateException();
- return new EntryIterator(this);
+ return new EntryIterator(map, this);
}
@SuppressWarnings("unchecked") public final Map.Entry next() {
@@ -3357,197 +3337,12 @@ public class ConcurrentHashMapV8
}
}
- /* ----------------Views -------------- */
-
/**
- * Base class for views.
+ * Returns exportable snapshot entry for the given key and value
+ * when write-through can't or shouldn't be used.
*/
- static abstract class CHMView {
- final ConcurrentHashMapV8 map;
- CHMView(ConcurrentHashMapV8 map) { this.map = map; }
- public final int size() { return map.size(); }
- public final boolean isEmpty() { return map.isEmpty(); }
- public final void clear() { map.clear(); }
-
- // implementations below rely on concrete classes supplying these
- abstract public Iterator iterator();
- abstract public boolean contains(Object o);
- abstract public boolean remove(Object o);
-
- private static final String oomeMsg = "Required array size too large";
-
- public final Object[] toArray() {
- long sz = map.mappingCount();
- if (sz > (long)(MAX_ARRAY_SIZE))
- throw new OutOfMemoryError(oomeMsg);
- int n = (int)sz;
- Object[] r = new Object[n];
- int i = 0;
- Iterator it = iterator();
- while (it.hasNext()) {
- if (i == n) {
- if (n >= MAX_ARRAY_SIZE)
- throw new OutOfMemoryError(oomeMsg);
- if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
- n = MAX_ARRAY_SIZE;
- else
- n += (n >>> 1) + 1;
- r = Arrays.copyOf(r, n);
- }
- r[i++] = it.next();
- }
- return (i == n) ? r : Arrays.copyOf(r, i);
- }
-
- @SuppressWarnings("unchecked") public final T[] toArray(T[] a) {
- long sz = map.mappingCount();
- if (sz > (long)(MAX_ARRAY_SIZE))
- throw new OutOfMemoryError(oomeMsg);
- int m = (int)sz;
- T[] r = (a.length >= m) ? a :
- (T[])java.lang.reflect.Array
- .newInstance(a.getClass().getComponentType(), m);
- int n = r.length;
- int i = 0;
- Iterator it = iterator();
- while (it.hasNext()) {
- if (i == n) {
- if (n >= MAX_ARRAY_SIZE)
- throw new OutOfMemoryError(oomeMsg);
- if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
- n = MAX_ARRAY_SIZE;
- else
- n += (n >>> 1) + 1;
- r = Arrays.copyOf(r, n);
- }
- r[i++] = (T)it.next();
- }
- if (a == r && i < n) {
- r[i] = null; // null-terminate
- return r;
- }
- return (i == n) ? r : Arrays.copyOf(r, i);
- }
-
- public final int hashCode() {
- int h = 0;
- for (Iterator it = iterator(); it.hasNext();)
- h += it.next().hashCode();
- return h;
- }
-
- public final String toString() {
- StringBuilder sb = new StringBuilder();
- sb.append('[');
- Iterator it = iterator();
- if (it.hasNext()) {
- for (;;) {
- Object e = it.next();
- sb.append(e == this ? "(this Collection)" : e);
- if (!it.hasNext())
- break;
- sb.append(',').append(' ');
- }
- }
- return sb.append(']').toString();
- }
-
- public final boolean containsAll(Collection c) {
- if (c != this) {
- for (Iterator it = c.iterator(); it.hasNext();) {
- Object e = it.next();
- if (e == null || !contains(e))
- return false;
- }
- }
- return true;
- }
-
- public final boolean removeAll(Collection c) {
- boolean modified = false;
- for (Iterator it = iterator(); it.hasNext();) {
- if (c.contains(it.next())) {
- it.remove();
- modified = true;
- }
- }
- return modified;
- }
-
- public final boolean retainAll(Collection c) {
- boolean modified = false;
- for (Iterator it = iterator(); it.hasNext();) {
- if (!c.contains(it.next())) {
- it.remove();
- modified = true;
- }
- }
- return modified;
- }
-
- }
-
- static final class Values extends CHMView
- implements Collection {
- Values(ConcurrentHashMapV8 map) { super(map); }
- public final boolean contains(Object o) { return map.containsValue(o); }
- public final boolean remove(Object o) {
- if (o != null) {
- Iterator it = new ValueIterator(map);
- while (it.hasNext()) {
- if (o.equals(it.next())) {
- it.remove();
- return true;
- }
- }
- }
- return false;
- }
- public final Iterator iterator() {
- return new ValueIterator(map);
- }
- public final boolean add(V e) {
- throw new UnsupportedOperationException();
- }
- public final boolean addAll(Collection c) {
- throw new UnsupportedOperationException();
- }
-
- }
-
- static final class EntrySet extends CHMView
- implements Set> {
- EntrySet(ConcurrentHashMapV8 map) { super(map); }
- public final boolean contains(Object o) {
- Object k, v, r; Map.Entry e;
- return ((o instanceof Map.Entry) &&
- (k = (e = (Map.Entry)o).getKey()) != null &&
- (r = map.get(k)) != null &&
- (v = e.getValue()) != null &&
- (v == r || v.equals(r)));
- }
- public final boolean remove(Object o) {
- Object k, v; Map.Entry e;
- return ((o instanceof Map.Entry) &&
- (k = (e = (Map.Entry)o).getKey()) != null &&
- (v = e.getValue()) != null &&
- map.remove(k, v));
- }
- public final Iterator> iterator() {
- return new EntryIterator(map);
- }
- public final boolean add(Entry e) {
- throw new UnsupportedOperationException();
- }
- public final boolean addAll(Collection> c) {
- throw new UnsupportedOperationException();
- }
- public boolean equals(Object o) {
- Set c;
- return ((o instanceof Set) &&
- ((c = (Set)o) == this ||
- (containsAll(c) && c.containsAll(this))));
- }
+ static AbstractMap.SimpleEntry entryFor(K k, V v) {
+ return new AbstractMap.SimpleEntry(k, v);
}
/* ---------------- Serialization Support -------------- */
@@ -4220,6 +4015,697 @@ public class ConcurrentHashMapV8
(this, transformer, basis, reducer).invoke();
}
+ /* ----------------Views -------------- */
+
+ /**
+ * Base class for views.
+ */
+ static abstract class CHMView {
+ final ConcurrentHashMapV8 map;
+ CHMView(ConcurrentHashMapV8 map) { this.map = map; }
+
+ /**
+ * Returns the map backing this view.
+ *
+ * @return the map backing this view
+ */
+ public ConcurrentHashMapV8 getMap() { return map; }
+
+ public final int size() { return map.size(); }
+ public final boolean isEmpty() { return map.isEmpty(); }
+ public final void clear() { map.clear(); }
+
+ // implementations below rely on concrete classes supplying these
+ abstract public Iterator iterator();
+ abstract public boolean contains(Object o);
+ abstract public boolean remove(Object o);
+
+ private static final String oomeMsg = "Required array size too large";
+
+ public final Object[] toArray() {
+ long sz = map.mappingCount();
+ if (sz > (long)(MAX_ARRAY_SIZE))
+ throw new OutOfMemoryError(oomeMsg);
+ int n = (int)sz;
+ Object[] r = new Object[n];
+ int i = 0;
+ Iterator it = iterator();
+ while (it.hasNext()) {
+ if (i == n) {
+ if (n >= MAX_ARRAY_SIZE)
+ throw new OutOfMemoryError(oomeMsg);
+ if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
+ n = MAX_ARRAY_SIZE;
+ else
+ n += (n >>> 1) + 1;
+ r = Arrays.copyOf(r, n);
+ }
+ r[i++] = it.next();
+ }
+ return (i == n) ? r : Arrays.copyOf(r, i);
+ }
+
+ @SuppressWarnings("unchecked") public final T[] toArray(T[] a) {
+ long sz = map.mappingCount();
+ if (sz > (long)(MAX_ARRAY_SIZE))
+ throw new OutOfMemoryError(oomeMsg);
+ int m = (int)sz;
+ T[] r = (a.length >= m) ? a :
+ (T[])java.lang.reflect.Array
+ .newInstance(a.getClass().getComponentType(), m);
+ int n = r.length;
+ int i = 0;
+ Iterator it = iterator();
+ while (it.hasNext()) {
+ if (i == n) {
+ if (n >= MAX_ARRAY_SIZE)
+ throw new OutOfMemoryError(oomeMsg);
+ if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
+ n = MAX_ARRAY_SIZE;
+ else
+ n += (n >>> 1) + 1;
+ r = Arrays.copyOf(r, n);
+ }
+ r[i++] = (T)it.next();
+ }
+ if (a == r && i < n) {
+ r[i] = null; // null-terminate
+ return r;
+ }
+ return (i == n) ? r : Arrays.copyOf(r, i);
+ }
+
+ public final int hashCode() {
+ int h = 0;
+ for (Iterator it = iterator(); it.hasNext();)
+ h += it.next().hashCode();
+ return h;
+ }
+
+ public final String toString() {
+ StringBuilder sb = new StringBuilder();
+ sb.append('[');
+ Iterator it = iterator();
+ if (it.hasNext()) {
+ for (;;) {
+ Object e = it.next();
+ sb.append(e == this ? "(this Collection)" : e);
+ if (!it.hasNext())
+ break;
+ sb.append(',').append(' ');
+ }
+ }
+ return sb.append(']').toString();
+ }
+
+ public final boolean containsAll(Collection c) {
+ if (c != this) {
+ for (Iterator it = c.iterator(); it.hasNext();) {
+ Object e = it.next();
+ if (e == null || !contains(e))
+ return false;
+ }
+ }
+ return true;
+ }
+
+ public final boolean removeAll(Collection c) {
+ boolean modified = false;
+ for (Iterator it = iterator(); it.hasNext();) {
+ if (c.contains(it.next())) {
+ it.remove();
+ modified = true;
+ }
+ }
+ return modified;
+ }
+
+ public final boolean retainAll(Collection c) {
+ boolean modified = false;
+ for (Iterator it = iterator(); it.hasNext();) {
+ if (!c.contains(it.next())) {
+ it.remove();
+ modified = true;
+ }
+ }
+ return modified;
+ }
+
+ }
+
+ /**
+ * A view of a ConcurrentHashMapV8 as a {@link Set} of keys, in
+ * which additions may optionally be enabled by mapping to a
+ * common value. This class cannot be directly instantiated. See
+ * {@link #keySet}, {@link #keySet(Object)}, {@link #newKeySet()},
+ * {@link #newKeySet(int)}.
+ */
+ public static class KeySetView extends CHMView implements Set, java.io.Serializable {
+ private static final long serialVersionUID = 7249069246763182397L;
+ private final V value;
+ KeySetView(ConcurrentHashMapV8 map, V value) { // non-public
+ super(map);
+ this.value = value;
+ }
+
+ /**
+ * Returns the default mapped value for additions,
+ * or {@code null} if additions are not supported.
+ *
+ * @return the default mapped value for additions, or {@code null}
+ * if not supported.
+ */
+ public V getMappedValue() { return value; }
+
+ // implement Set API
+
+ public boolean contains(Object o) { return map.containsKey(o); }
+ public boolean remove(Object o) { return map.remove(o) != null; }
+
+ /**
+ * Returns a "weakly consistent" iterator that will never
+ * throw {@link ConcurrentModificationException}, and
+ * guarantees to traverse elements as they existed upon
+ * construction of the iterator, and may (but is not
+ * guaranteed to) reflect any modifications subsequent to
+ * construction.
+ *
+ * @return an iterator over the keys of this map
+ */
+ public Iterator iterator() { return new KeyIterator(map); }
+ public boolean add(K e) {
+ V v;
+ if ((v = value) == null)
+ throw new UnsupportedOperationException();
+ if (e == null)
+ throw new NullPointerException();
+ return map.internalPutIfAbsent(e, v) == null;
+ }
+ public boolean addAll(Collection c) {
+ boolean added = false;
+ V v;
+ if ((v = value) == null)
+ throw new UnsupportedOperationException();
+ for (K e : c) {
+ if (e == null)
+ throw new NullPointerException();
+ if (map.internalPutIfAbsent(e, v) == null)
+ added = true;
+ }
+ return added;
+ }
+ public boolean equals(Object o) {
+ Set c;
+ return ((o instanceof Set) &&
+ ((c = (Set)o) == this ||
+ (containsAll(c) && c.containsAll(this))));
+ }
+
+ /**
+ * Performs the given action for each key.
+ *
+ * @param action the action
+ */
+ public void forEach(Action action) {
+ ForkJoinTasks.forEachKey
+ (map, action).invoke();
+ }
+
+ /**
+ * Performs the given action for each non-null transformation
+ * 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).
+ * @param action the action
+ */
+ public void forEach(Fun transformer,
+ Action action) {
+ ForkJoinTasks.forEachKey
+ (map, transformer, action).invoke();
+ }
+
+ /**
+ * Returns a non-null result from applying the given search
+ * 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
+ * @return a non-null result from applying the given search
+ * function on each key, or null if none
+ */
+ public U search(Fun searchFunction) {
+ return ForkJoinTasks.searchKeys
+ (map, searchFunction).invoke();
+ }
+
+ /**
+ * Returns the result of accumulating all keys using the given
+ * reducer to combine values, or null if none.
+ *
+ * @param reducer a commutative associative combining function
+ * @return the result of accumulating all keys using the given
+ * reducer to combine values, or null if none
+ */
+ public K reduce(BiFun reducer) {
+ return ForkJoinTasks.reduceKeys
+ (map, reducer).invoke();
+ }
+
+ /**
+ * Returns the result of accumulating the given transformation
+ * of all keys using the given reducer to combine values, and
+ * the given basis as an identity value.
+ *
+ * @param transformer a function returning the transformation
+ * for an element
+ * @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 keys
+ */
+ public double reduceToDouble(ObjectToDouble transformer,
+ double basis,
+ DoubleByDoubleToDouble reducer) {
+ return ForkJoinTasks.reduceKeysToDouble
+ (map, transformer, basis, reducer).invoke();
+ }
+
+
+ /**
+ * Returns the result of accumulating the given transformation
+ * of all keys using the given reducer to combine values, and
+ * the given basis as an identity value.
+ *
+ * @param transformer a function returning the transformation
+ * for an element
+ * @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 keys
+ */
+ public long reduceToLong(ObjectToLong transformer,
+ long basis,
+ LongByLongToLong reducer) {
+ return ForkJoinTasks.reduceKeysToLong
+ (map, transformer, basis, reducer).invoke();
+ }
+
+ /**
+ * Returns the result of accumulating the given transformation
+ * of all keys using the given reducer to combine values, and
+ * the given basis as an identity value.
+ *
+ * @param transformer a function returning the transformation
+ * for an element
+ * @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 keys
+ */
+ public int reduceToInt(ObjectToInt transformer,
+ int basis,
+ IntByIntToInt reducer) {
+ return ForkJoinTasks.reduceKeysToInt
+ (map, transformer, basis, reducer).invoke();
+ }
+
+ }
+
+ /**
+ * A view of a ConcurrentHashMapV8 as a {@link Collection} of
+ * values, in which additions are disabled. This class cannot be
+ * directly instantiated. See {@link #values},
+ *
+ * The view's {@code iterator} is a "weakly consistent" iterator
+ * that will never throw {@link ConcurrentModificationException},
+ * and guarantees to traverse elements as they existed upon
+ * construction of the iterator, and may (but is not guaranteed to)
+ * reflect any modifications subsequent to construction.
+ */
+ public static final class ValuesView extends CHMView
+ implements Collection {
+ ValuesView(ConcurrentHashMapV8 map) { super(map); }
+ public final boolean contains(Object o) { return map.containsValue(o); }
+ public final boolean remove(Object o) {
+ if (o != null) {
+ Iterator it = new ValueIterator(map);
+ while (it.hasNext()) {
+ if (o.equals(it.next())) {
+ it.remove();
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Returns a "weakly consistent" iterator that will never
+ * throw {@link ConcurrentModificationException}, and
+ * guarantees to traverse elements as they existed upon
+ * construction of the iterator, and may (but is not
+ * guaranteed to) reflect any modifications subsequent to
+ * construction.
+ *
+ * @return an iterator over the values of this map
+ */
+ public final Iterator iterator() {
+ return new ValueIterator(map);
+ }
+ public final boolean add(V e) {
+ throw new UnsupportedOperationException();
+ }
+ public final boolean addAll(Collection c) {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * Performs the given action for each value.
+ *
+ * @param action the action
+ */
+ public void forEach(Action action) {
+ ForkJoinTasks.forEachValue
+ (map, action).invoke();
+ }
+
+ /**
+ * Performs the given action for each non-null transformation
+ * 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).
+ */
+ public void forEach(Fun transformer,
+ Action action) {
+ ForkJoinTasks.forEachValue
+ (map, transformer, action).invoke();
+ }
+
+ /**
+ * Returns a non-null result from applying the given search
+ * 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
+ * @return a non-null result from applying the given search
+ * function on each value, or null if none
+ *
+ */
+ public U search(Fun searchFunction) {
+ return ForkJoinTasks.searchValues
+ (map, searchFunction).invoke();
+ }
+
+ /**
+ * Returns the result of accumulating all values using the
+ * given reducer to combine values, or null if none.
+ *
+ * @param reducer a commutative associative combining function
+ * @return the result of accumulating all values
+ */
+ public V reduce(BiFun reducer) {
+ return ForkJoinTasks.reduceValues
+ (map, reducer).invoke();
+ }
+
+ /**
+ * Returns the result of accumulating the given transformation
+ * of all values using the given reducer to 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).
+ * @param reducer a commutative associative combining function
+ * @return the result of accumulating the given transformation
+ * of all values
+ */
+ public U reduce(Fun transformer,
+ BiFun reducer) {
+ return ForkJoinTasks.reduceValues
+ (map, transformer, reducer).invoke();
+ }
+
+ /**
+ * Returns the result of accumulating the given transformation
+ * of all values using the given reducer to combine values,
+ * and the given basis as an identity value.
+ *
+ * @param transformer a function returning the transformation
+ * for an element
+ * @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 values
+ */
+ public double reduceToDouble(ObjectToDouble transformer,
+ double basis,
+ DoubleByDoubleToDouble reducer) {
+ return ForkJoinTasks.reduceValuesToDouble
+ (map, transformer, basis, reducer).invoke();
+ }
+
+ /**
+ * Returns the result of accumulating the given transformation
+ * of all values using the given reducer to combine values,
+ * and the given basis as an identity value.
+ *
+ * @param transformer a function returning the transformation
+ * for an element
+ * @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 values
+ */
+ public long reduceToLong(ObjectToLong transformer,
+ long basis,
+ LongByLongToLong reducer) {
+ return ForkJoinTasks.reduceValuesToLong
+ (map, transformer, basis, reducer).invoke();
+ }
+
+ /**
+ * Returns the result of accumulating the given transformation
+ * of all values using the given reducer to combine values,
+ * and the given basis as an identity value.
+ *
+ * @param transformer a function returning the transformation
+ * for an element
+ * @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 values
+ */
+ public int reduceToInt(ObjectToInt transformer,
+ int basis,
+ IntByIntToInt reducer) {
+ return ForkJoinTasks.reduceValuesToInt
+ (map, transformer, basis, reducer).invoke();
+ }
+
+ }
+
+ /**
+ * A view of a ConcurrentHashMapV8 as a {@link Set} of (key, value)
+ * entries. This class cannot be directly instantiated. See
+ * {@link #entrySet}.
+ */
+ public static final class EntrySetView extends CHMView
+ implements Set> {
+ EntrySetView(ConcurrentHashMapV8 map) { super(map); }
+ public final boolean contains(Object o) {
+ Object k, v, r; Map.Entry e;
+ return ((o instanceof Map.Entry) &&
+ (k = (e = (Map.Entry)o).getKey()) != null &&
+ (r = map.get(k)) != null &&
+ (v = e.getValue()) != null &&
+ (v == r || v.equals(r)));
+ }
+ public final boolean remove(Object o) {
+ Object k, v; Map.Entry e;
+ return ((o instanceof Map.Entry) &&
+ (k = (e = (Map.Entry)o).getKey()) != null &&
+ (v = e.getValue()) != null &&
+ map.remove(k, v));
+ }
+
+ /**
+ * Returns a "weakly consistent" iterator that will never
+ * throw {@link ConcurrentModificationException}, and
+ * guarantees to traverse elements as they existed upon
+ * construction of the iterator, and may (but is not
+ * guaranteed to) reflect any modifications subsequent to
+ * construction.
+ *
+ * @return an iterator over the entries of this map
+ */
+ public final Iterator> iterator() {
+ return new EntryIterator(map);
+ }
+
+ public final boolean add(Entry e) {
+ K key = e.getKey();
+ V value = e.getValue();
+ if (key == null || value == null)
+ throw new NullPointerException();
+ return map.internalPut(key, value) == null;
+ }
+ public final boolean addAll(Collection> c) {
+ boolean added = false;
+ for (Entry e : c) {
+ if (add(e))
+ added = true;
+ }
+ return added;
+ }
+ public boolean equals(Object o) {
+ Set c;
+ return ((o instanceof Set) &&
+ ((c = (Set)o) == this ||
+ (containsAll(c) && c.containsAll(this))));
+ }
+
+ /**
+ * Performs the given action for each entry.
+ *
+ * @param action the action
+ */
+ public void forEach(Action> action) {
+ ForkJoinTasks.forEachEntry
+ (map, action).invoke();
+ }
+
+ /**
+ * 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).
+ * @param action the action
+ */
+ public void forEach(Fun, ? extends U> transformer,
+ Action action) {
+ ForkJoinTasks.forEachEntry
+ (map, transformer, action).invoke();
+ }
+
+ /**
+ * Returns a non-null result from applying the given search
+ * 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
+ * @return a non-null result from applying the given search
+ * function on each entry, or null if none
+ */
+ public U search(Fun, ? extends U> searchFunction) {
+ return ForkJoinTasks.searchEntries
+ (map, searchFunction).invoke();
+ }
+
+ /**
+ * Returns the result of accumulating all entries using the
+ * given reducer to combine values, or null if none.
+ *
+ * @param reducer a commutative associative combining function
+ * @return the result of accumulating all entries
+ */
+ public Map.Entry reduce(BiFun, Map.Entry, ? extends Map.Entry> reducer) {
+ return ForkJoinTasks.reduceEntries
+ (map, reducer).invoke();
+ }
+
+ /**
+ * Returns the result of accumulating the given transformation
+ * of all entries using the given reducer to 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).
+ * @param reducer a commutative associative combining function
+ * @return the result of accumulating the given transformation
+ * of all entries
+ */
+ public U reduce(Fun, ? extends U> transformer,
+ BiFun reducer) {
+ return ForkJoinTasks.reduceEntries
+ (map, transformer, reducer).invoke();
+ }
+
+ /**
+ * Returns the result of accumulating the given transformation
+ * of all entries using the given reducer to combine values,
+ * and the given basis as an identity value.
+ *
+ * @param transformer a function returning the transformation
+ * for an element
+ * @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 entries
+ */
+ public double reduceToDouble(ObjectToDouble> transformer,
+ double basis,
+ DoubleByDoubleToDouble reducer) {
+ return ForkJoinTasks.reduceEntriesToDouble
+ (map, transformer, basis, reducer).invoke();
+ }
+
+ /**
+ * Returns the result of accumulating the given transformation
+ * of all entries using the given reducer to combine values,
+ * and the given basis as an identity value.
+ *
+ * @param transformer a function returning the transformation
+ * for an element
+ * @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 entries
+ */
+ public long reduceToLong(ObjectToLong> transformer,
+ long basis,
+ LongByLongToLong reducer) {
+ return ForkJoinTasks.reduceEntriesToLong
+ (map, transformer, basis, reducer).invoke();
+ }
+
+ /**
+ * Returns the result of accumulating the given transformation
+ * of all entries using the given reducer to combine values,
+ * and the given basis as an identity value.
+ *
+ * @param transformer a function returning the transformation
+ * for an element
+ * @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 entries
+ */
+ public int reduceToInt(ObjectToInt> transformer,
+ int basis,
+ IntByIntToInt reducer) {
+ return ForkJoinTasks.reduceEntriesToInt
+ (map, transformer, basis, reducer).invoke();
+ }
+
+ }
+
// ---------------------------------------------------------------------
/**
@@ -4246,7 +4732,7 @@ public class ConcurrentHashMapV8
(ConcurrentHashMapV8 map,
BiAction action) {
if (action == null) throw new NullPointerException();
- return new ForEachMappingTask(map, null, -1, null, action);
+ return new ForEachMappingTask(map, null, -1, action);
}
/**
@@ -4267,7 +4753,7 @@ public class ConcurrentHashMapV8
if (transformer == null || action == null)
throw new NullPointerException();
return new ForEachTransformedMappingTask
- (map, null, -1, null, transformer, action);
+ (map, null, -1, transformer, action);
}
/**
@@ -4287,7 +4773,7 @@ public class ConcurrentHashMapV8
BiFun searchFunction) {
if (searchFunction == null) throw new NullPointerException();
return new SearchMappingsTask
- (map, null, -1, null, searchFunction,
+ (map, null, -1, searchFunction,
new AtomicReference());
}
@@ -4396,7 +4882,7 @@ public class ConcurrentHashMapV8
(ConcurrentHashMapV8 map,
Action action) {
if (action == null) throw new NullPointerException();
- return new ForEachKeyTask(map, null, -1, null, action);
+ return new ForEachKeyTask(map, null, -1, action);
}
/**
@@ -4417,7 +4903,7 @@ public class ConcurrentHashMapV8
if (transformer == null || action == null)
throw new NullPointerException();
return new ForEachTransformedKeyTask
- (map, null, -1, null, transformer, action);
+ (map, null, -1, transformer, action);
}
/**
@@ -4437,7 +4923,7 @@ public class ConcurrentHashMapV8
Fun searchFunction) {
if (searchFunction == null) throw new NullPointerException();
return new SearchKeysTask
- (map, null, -1, null, searchFunction,
+ (map, null, -1, searchFunction,
new AtomicReference());
}
@@ -4563,7 +5049,7 @@ public class ConcurrentHashMapV8
(ConcurrentHashMapV8 map,
Action action) {
if (action == null) throw new NullPointerException();
- return new ForEachValueTask(map, null, -1, null, action);
+ return new ForEachValueTask(map, null, -1, action);
}
/**
@@ -4583,7 +5069,7 @@ public class ConcurrentHashMapV8
if (transformer == null || action == null)
throw new NullPointerException();
return new ForEachTransformedValueTask
- (map, null, -1, null, transformer, action);
+ (map, null, -1, transformer, action);
}
/**
@@ -4603,7 +5089,7 @@ public class ConcurrentHashMapV8
Fun searchFunction) {
if (searchFunction == null) throw new NullPointerException();
return new SearchValuesTask
- (map, null, -1, null, searchFunction,
+ (map, null, -1, searchFunction,
new AtomicReference());
}
@@ -4729,7 +5215,7 @@ public class ConcurrentHashMapV8
(ConcurrentHashMapV8 map,
Action> action) {
if (action == null) throw new NullPointerException();
- return new ForEachEntryTask(map, null, -1, null, action);
+ return new ForEachEntryTask(map, null, -1, action);
}
/**
@@ -4749,7 +5235,7 @@ public class ConcurrentHashMapV8
if (transformer == null || action == null)
throw new NullPointerException();
return new ForEachTransformedEntryTask
- (map, null, -1, null, transformer, action);
+ (map, null, -1, transformer, action);
}
/**
@@ -4769,7 +5255,7 @@ public class ConcurrentHashMapV8
Fun, ? extends U> searchFunction) {
if (searchFunction == null) throw new NullPointerException();
return new SearchEntriesTask
- (map, null, -1, null, searchFunction,
+ (map, null, -1, searchFunction,
new AtomicReference());
}
@@ -4887,162 +5373,6 @@ public class ConcurrentHashMapV8
// -------------------------------------------------------
- /**
- * Base for FJ tasks for bulk operations. This adds a variant of
- * CountedCompleters and some split and merge bookkeeping to
- * iterator functionality. The forEach and reduce methods are
- * similar to those illustrated in CountedCompleter documentation,
- * except that bottom-up reduction completions perform them within
- * their compute methods. The search methods are like forEach
- * except they continually poll for success and exit early. Also,
- * exceptions are handled in a simpler manner, by just trying to
- * complete root task exceptionally.
- */
- @SuppressWarnings("serial") static abstract class BulkTask extends Traverser {
- final BulkTask parent; // completion target
- int batch; // split control; -1 for unknown
- int pending; // completion control
-
- BulkTask(ConcurrentHashMapV8 map, BulkTask parent,
- int batch) {
- super(map);
- 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;
- }
- }
-
- /**
- * Forces root task to complete.
- * @param ex if null, complete normally, else exceptionally
- * @return false to simplify use
- */
- final boolean tryCompleteComputation(Throwable ex) {
- for (BulkTask a = this;;) {
- BulkTask p = a.parent;
- if (p == null) {
- if (ex != null)
- a.completeExceptionally(ex);
- else
- a.quietlyComplete();
- return false;
- }
- a = p;
- }
- }
-
- /**
- * Version of tryCompleteComputation for function screening checks
- */
- final boolean abortOnNullFunction() {
- return tryCompleteComputation(new Error("Unexpected null function"));
- }
-
- // utilities
-
- /** CompareAndSet pending count */
- final boolean casPending(int cmp, int val) {
- return U.compareAndSwapInt(this, PENDING, cmp, val);
- }
-
- /**
- * 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() {
- ConcurrentHashMapV8 m; int b; Node[] t; ForkJoinPool pool;
- 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 par = ((pool = getPool()) == null) ?
- ForkJoinPool.getCommonPoolParallelism() :
- pool.getParallelism();
- int sp = par << 3; // slack of 8
- b = batch = (n <= 0L) ? 0 : (n < (long)sp) ? (int)n : sp;
- }
- }
- return b;
- }
-
- /**
- * Returns exportable snapshot entry.
- */
- static AbstractMap.SimpleEntry entryFor(K k, V v) {
- return new AbstractMap.SimpleEntry(k, v);
- }
-
- // Unsafe mechanics
- private static final sun.misc.Unsafe U;
- private static final long PENDING;
- static {
- try {
- U = getUnsafe();
- PENDING = U.objectFieldOffset
- (BulkTask.class.getDeclaredField("pending"));
- } catch (Exception e) {
- throw new Error(e);
- }
- }
- }
-
- /**
- * Base class for non-reductive actions
- */
- @SuppressWarnings("serial") static abstract class BulkAction extends BulkTask {
- BulkAction nextTask;
- BulkAction(ConcurrentHashMapV8 map, BulkTask parent,
- int batch, BulkAction nextTask) {
- super(map, parent, batch);
- this.nextTask = nextTask;
- }
-
- /**
- * Try to complete task and upward parents. Upon hitting
- * non-completed parent, if a non-FJ task, try to help out the
- * computation.
- */
- final void tryComplete(BulkAction subtasks) {
- BulkTask a = this, s = a;
- for (int c;;) {
- if ((c = a.pending) == 0) {
- if ((a = (s = a).parent) == null) {
- s.quietlyComplete();
- break;
- }
- }
- else if (a.casPending(c, c - 1)) {
- if (subtasks != null && !inForkJoinPool()) {
- while ((s = a.parent) != null)
- a = s;
- while (!a.isDone()) {
- BulkAction next = subtasks.nextTask;
- if (subtasks.tryUnfork())
- subtasks.exec();
- if ((subtasks = next) == null)
- break;
- }
- }
- break;
- }
- }
- }
-
- }
-
/*
* Task classes. Coded in a regular but ugly format/style to
* simplify checks that each variant differs in the right way from
@@ -5050,665 +5380,508 @@ public class ConcurrentHashMapV8
*/
@SuppressWarnings("serial") static final class ForEachKeyTask
- extends BulkAction {
+ extends Traverser {
final Action action;
ForEachKeyTask
- (ConcurrentHashMapV8 m, BulkTask p, int b,
- ForEachKeyTask nextTask,
+ (ConcurrentHashMapV8 m, Traverser p, int b,
Action action) {
- super(m, p, b, nextTask);
+ super(m, p, b);
this.action = action;
}
- @SuppressWarnings("unchecked") public final boolean exec() {
- final Action action = this.action;
- if (action == null)
- return abortOnNullFunction();
- ForEachKeyTask subtasks = null;
- try {
- int b = batch(), c;
- while (b > 1 && baseIndex != baseLimit) {
- do {} while (!casPending(c = pending, c+1));
- (subtasks = new ForEachKeyTask
- (map, this, b >>>= 1, subtasks, action)).fork();
- }
- while (advance() != null)
- action.apply((K)nextKey);
- } catch (Throwable ex) {
- return tryCompleteComputation(ex);
- }
- tryComplete(subtasks);
- return false;
+ @SuppressWarnings("unchecked") public final void compute() {
+ final Action action;
+ if ((action = this.action) == null)
+ throw new NullPointerException();
+ for (int b; (b = preSplit()) > 0;)
+ new ForEachKeyTask(map, this, b, action).fork();
+ while (advance() != null)
+ action.apply((K)nextKey);
+ propagateCompletion();
}
}
@SuppressWarnings("serial") static final class ForEachValueTask
- extends BulkAction {
+ extends Traverser {
final Action action;
ForEachValueTask
- (ConcurrentHashMapV8 m, BulkTask p, int b,
- ForEachValueTask nextTask,
+ (ConcurrentHashMapV8 m, Traverser p, int b,
Action action) {
- super(m, p, b, nextTask);
+ super(m, p, b);
this.action = action;
}
- @SuppressWarnings("unchecked") public final boolean exec() {
- final Action