--- jsr166/src/jsr166e/ConcurrentHashMapV8.java 2012/06/09 16:54:12 1.39 +++ jsr166/src/jsr166e/ConcurrentHashMapV8.java 2012/08/13 18:49:36 1.56 @@ -4,10 +4,12 @@ * http://creativecommons.org/publicdomain/zero/1.0/ */ -// Snapshot Tue Jun 5 14:56:09 2012 Doug Lea (dl at altair) - package jsr166e; import jsr166e.LongAdder; +import jsr166e.ForkJoinPool; +import jsr166e.ForkJoinTask; + +import java.util.Comparator; import java.util.Arrays; import java.util.Map; import java.util.Set; @@ -25,6 +27,8 @@ import java.util.concurrent.ConcurrentMa import java.util.concurrent.ThreadLocalRandom; import java.util.concurrent.locks.LockSupport; import java.util.concurrent.locks.AbstractQueuedSynchronizer; +import java.util.concurrent.atomic.AtomicReference; + import java.io.Serializable; /** @@ -90,7 +94,9 @@ import java.io.Serializable; * Java Collections Framework. * *

jsr166e note: This class is a candidate replacement for - * java.util.concurrent.ConcurrentHashMap. + * java.util.concurrent.ConcurrentHashMap. During transition, this + * class declares and uses nested functional interfaces with different + * names but the same forms as those expected for JDK8. * * @since 1.5 * @author Doug Lea @@ -98,38 +104,76 @@ import java.io.Serializable; * @param the type of mapped values */ public class ConcurrentHashMapV8 - implements ConcurrentMap, Serializable { + implements ConcurrentMap, Serializable { private static final long serialVersionUID = 7249069246763182397L; /** - * A function computing a mapping from the given key to a value. - * This is a place-holder for an upcoming JDK8 interface. - */ - public static interface MappingFunction { - /** - * Returns a non-null value for the given key. - * - * @param key the (non-null) key - * @return a non-null value - */ - V map(K key); - } - - /** - * A function computing a new mapping given a key and its current - * mapped value (or {@code null} if there is no current - * mapping). This is a place-holder for an upcoming JDK8 - * interface. + * A partitionable iterator. A Spliterator can be traversed + * directly, but can also be partitioned (before traversal) by + * creating another Spliterator that covers a non-overlapping + * portion of the elements, and so may be amenable to parallel + * execution. + * + *

This interface exports a subset of expected JDK8 + * functionality. + * + *

Sample usage: Here is one (of the several) ways to compute + * the sum of the values held in a map using the ForkJoin + * framework. As illustrated here, Spliterators are well suited to + * designs in which a task repeatedly splits off half its work + * into forked subtasks until small enough to process directly, + * and then joins these subtasks. Variants of this style can also + * be used in completion-based designs. + * + * 

+     * {@code ConcurrentHashMapV8 m = ...
+     * // split as if have 8 * parallelism, for load balance
+     * int n = m.size();
+     * int p = aForkJoinPool.getParallelism() * 8;
+     * int split = (n < p)? n : p;
+     * long sum = aForkJoinPool.invoke(new SumValues(m.valueSpliterator(), split, null));
+     * // ...
+     * static class SumValues extends RecursiveTask {
+     *   final Spliterator s;
+     *   final int split;             // split while > 1
+     *   final SumValues nextJoin;    // records forked subtasks to join
+     *   SumValues(Spliterator s, int depth, SumValues nextJoin) {
+     *     this.s = s; this.depth = depth; this.nextJoin = nextJoin;
+     *   }
+     *   public Long compute() {
+     *     long sum = 0;
+     *     SumValues subtasks = null; // fork subtasks
+     *     for (int s = split >>> 1; s > 0; s >>>= 1)
+     *       (subtasks = new SumValues(s.split(), s, subtasks)).fork();
+     *     while (s.hasNext())        // directly process remaining elements
+     *       sum += s.next();
+     *     for (SumValues t = subtasks; t != null; t = t.nextJoin)
+     *       sum += t.join();         // collect subtask results
+     *     return sum;
+     *   }
+     * }
+     * }
*/ - public static interface RemappingFunction { + public static interface Spliterator extends Iterator { /** - * Returns a new value given a key and its current value. + * Returns a Spliterator covering approximately half of the + * elements, guaranteed not to overlap with those subsequently + * returned by this Spliterator. After invoking this method, + * the current Spliterator will not produce any of + * the elements of the returned Spliterator, but the two + * Spliterators together will produce all of the elements that + * would have been produced by this Spliterator had this + * method not been called. The exact number of elements + * produced by the returned Spliterator is not guaranteed, and + * may be zero (i.e., with {@code hasNext()} reporting {@code + * false}) if this Spliterator cannot be further split. * - * @param key the (non-null) key - * @param value the current value, or null if there is no mapping - * @return a non-null value + * @return a Spliterator covering approximately half of the + * elements + * @throws IllegalStateException if this Spliterator has + * already commenced traversing elements */ - V remap(K key, V value); + Spliterator split(); } /* @@ -283,7 +327,7 @@ public class ConcurrentHashMapV8 * When there are no lock acquisition failures, this is arranged * simply by proceeding from the last bin (table.length - 1) up * towards the first. Upon seeing a forwarding node, traversals - * (see class InternalIterator) arrange to move to the new table + * (see class Iter) arrange to move to the new table * without revisiting nodes. However, when any node is skipped * during a transfer, all earlier table bins may have become * visible, so are initialized with a reverse-forwarding node back @@ -293,12 +337,11 @@ public class ConcurrentHashMapV8 * mechanics trigger only when necessary. * * The traversal scheme also applies to partial traversals of - * ranges of bins (via an alternate InternalIterator constructor) - * to support partitioned aggregate operations (that are not - * otherwise implemented yet). Also, read-only operations give up - * if ever forwarded to a null table, which provides support for - * shutdown-style clearing, which is also not currently - * implemented. + * ranges of bins (via an alternate Traverser constructor) + * to support partitioned aggregate operations. Also, read-only + * operations give up if ever forwarded to a null table, which + * provides support for shutdown-style clearing, which is also not + * currently implemented. * * Lazy table initialization minimizes footprint until first use, * and also avoids resizings when the first operation is from a @@ -436,7 +479,7 @@ public class ConcurrentHashMapV8 * inline assignments below. */ - static final Node tabAt(Node[] tab, int i) { // used by InternalIterator + static final Node tabAt(Node[] tab, int i) { // used by Iter return (Node)UNSAFE.getObjectVolatile(tab, ((long)i< /** * Key-value entry. Note that this is never exported out as a - * user-visible Map.Entry (see WriteThroughEntry and SnapshotEntry - * below). Nodes with a hash field of MOVED are special, and do - * not contain user keys or values. Otherwise, keys are never - * null, and null val fields indicate that a node is in the - * process of being deleted or created. For purposes of read-only - * access, a key may be read before a val, but can only be used - * after checking val to be non-null. + * user-visible Map.Entry (see MapEntry below). Nodes with a hash + * field of MOVED are special, and do not contain user keys or + * values. Otherwise, keys are never null, and null val fields + * indicate that a node is in the process of being deleted or + * created. For purposes of read-only access, a key may be read + * before a val, but can only be used after checking val to be + * non-null. */ static class Node { volatile int hash; @@ -571,15 +614,20 @@ public class ConcurrentHashMapV8 * handle this, the tree is ordered primarily by hash value, then * by getClass().getName() order, and then by Comparator order * among elements of the same class. On lookup at a node, if - * non-Comparable, both left and right children may need to be - * searched in the case of tied hash values. (This corresponds to - * the full list search that would be necessary if all elements - * were non-Comparable and had tied hashes.) + * elements are not comparable or compare as 0, both left and + * right children may need to be searched in the case of tied hash + * values. (This corresponds to the full list search that would be + * necessary if all elements were non-Comparable and had tied + * hashes.) The red-black balancing code is updated from + * pre-jdk-collections + * (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java) + * based in turn on Cormen, Leiserson, and Rivest "Introduction to + * Algorithms" (CLR). * * TreeBins also maintain a separate locking discipline than * regular bins. Because they are forwarded via special MOVED * nodes at bin heads (which can never change once established), - * we cannot use use those nodes as locks. Instead, TreeBin + * we cannot use those nodes as locks. Instead, TreeBin * extends AbstractQueuedSynchronizer to support a simple form of * read-write lock. For update operations and table validation, * the exclusive form of lock behaves in the same way as bin-head @@ -598,8 +646,8 @@ public class ConcurrentHashMapV8 */ static final class TreeBin extends AbstractQueuedSynchronizer { private static final long serialVersionUID = 2249069246763182397L; - TreeNode root; // root of tree - TreeNode first; // head of next-pointer list + transient TreeNode root; // root of tree + transient TreeNode first; // head of next-pointer list /* AQS overrides */ public final boolean isHeldExclusively() { return getState() > 0; } @@ -629,35 +677,70 @@ public class ConcurrentHashMapV8 return c == -1; } + /** From CLR */ + private void rotateLeft(TreeNode p) { + if (p != null) { + TreeNode r = p.right, pp, rl; + if ((rl = p.right = r.left) != null) + rl.parent = p; + if ((pp = r.parent = p.parent) == null) + root = r; + else if (pp.left == p) + pp.left = r; + else + pp.right = r; + r.left = p; + p.parent = r; + } + } + + /** From CLR */ + private void rotateRight(TreeNode p) { + if (p != null) { + TreeNode l = p.left, pp, lr; + if ((lr = p.left = l.right) != null) + lr.parent = p; + if ((pp = l.parent = p.parent) == null) + root = l; + else if (pp.right == p) + pp.right = l; + else + pp.left = l; + l.right = p; + p.parent = l; + } + } + /** - * 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) { + final TreeNode getTreeNode(int h, Object k, TreeNode p) { Class c = k.getClass(); while (p != null) { - int dir, ph; Object pk; Class pc; TreeNode r; - if (h < (ph = p.hash)) - dir = -1; - else if (h > ph) - dir = 1; - else if ((pk = p.key) == k || k.equals(pk)) - return p; - else if (c != (pc = pk.getClass())) - dir = c.getName().compareTo(pc.getName()); - else if (k instanceof Comparable) - dir = ((Comparable)k).compareTo((Comparable)pk); - else - dir = 0; - TreeNode pr = p.right; - if (dir > 0) - p = pr; - else if (dir == 0 && pr != null && h >= pr.hash && - (r = getTreeNode(h, k, pr)) != null) - return r; + int dir, ph; Object pk; Class pc; + if ((ph = p.hash) == h) { + if ((pk = p.key) == k || k.equals(pk)) + return p; + if (c != (pc = pk.getClass()) || + !(k instanceof Comparable) || + (dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) { + dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName()); + TreeNode r = null, s = null, pl, pr; + if (dir >= 0) { + if ((pl = p.left) != null && h <= pl.hash) + s = pl; + } + else if ((pr = p.right) != null && h >= pr.hash) + s = pr; + if (s != null && (r = getTreeNode(h, k, s)) != null) + return r; + } + } else - p = p.left; + dir = (h < ph) ? -1 : 1; + p = (dir > 0) ? p.right : p.left; } return null; } @@ -690,56 +773,104 @@ public class ConcurrentHashMapV8 } /** - * Find or add a node + * Finds or adds a node. * @return null if added */ @SuppressWarnings("unchecked") // suppress Comparable cast warning - final TreeNode putTreeNode(int h, Object k, Object v) { + final TreeNode putTreeNode(int h, Object k, Object v) { Class c = k.getClass(); - TreeNode p = root; + TreeNode pp = root, p = null; int dir = 0; - if (p != null) { - for (;;) { - int ph; Object pk; Class pc; TreeNode r; - if (h < (ph = p.hash)) - dir = -1; - else if (h > ph) - dir = 1; - else if ((pk = p.key) == k || k.equals(pk)) + while (pp != null) { // find existing node or leaf to insert at + int ph; Object pk; Class pc; + p = pp; + if ((ph = p.hash) == h) { + if ((pk = p.key) == k || k.equals(pk)) return p; - else if (c != (pc = (pk = p.key).getClass())) - dir = c.getName().compareTo(pc.getName()); - else if (k instanceof Comparable) - dir = ((Comparable)k).compareTo((Comparable)pk); - else - dir = 0; - TreeNode pr = p.right, pl; - if (dir > 0) { - if (pr == null) - break; - p = pr; + if (c != (pc = pk.getClass()) || + !(k instanceof Comparable) || + (dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) { + dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName()); + TreeNode r = null, s = null, pl, pr; + if (dir >= 0) { + if ((pl = p.left) != null && h <= pl.hash) + s = pl; + } + else if ((pr = p.right) != null && h >= pr.hash) + s = pr; + if (s != null && (r = getTreeNode(h, k, s)) != null) + return r; } - else if (dir == 0 && pr != null && h >= pr.hash && - (r = getTreeNode(h, k, pr)) != null) - return r; - else if ((pl = p.left) == null) - break; - else - p = pl; } + else + dir = (h < ph) ? -1 : 1; + pp = (dir > 0) ? p.right : p.left; } + TreeNode f = first; - TreeNode r = first = new TreeNode(h, k, v, f, p); + TreeNode x = first = new TreeNode(h, k, v, f, p); if (p == null) - root = r; - else { + root = x; + else { // attach and rebalance; adapted from CLR + TreeNode xp, xpp; + if (f != null) + f.prev = x; if (dir <= 0) - p.left = r; + p.left = x; else - p.right = r; - if (f != null) - f.prev = r; - fixAfterInsertion(r); + p.right = x; + x.red = true; + while (x != null && (xp = x.parent) != null && xp.red && + (xpp = xp.parent) != null) { + TreeNode xppl = xpp.left; + if (xp == xppl) { + TreeNode y = xpp.right; + if (y != null && y.red) { + y.red = false; + xp.red = false; + xpp.red = true; + x = xpp; + } + else { + if (x == xp.right) { + rotateLeft(x = xp); + xpp = (xp = x.parent) == null ? null : xp.parent; + } + if (xp != null) { + xp.red = false; + if (xpp != null) { + xpp.red = true; + rotateRight(xpp); + } + } + } + } + else { + TreeNode y = xppl; + if (y != null && y.red) { + y.red = false; + xp.red = false; + xpp.red = true; + x = xpp; + } + else { + if (x == xp.left) { + rotateRight(x = xp); + xpp = (xp = x.parent) == null ? null : xp.parent; + } + if (xp != null) { + xp.red = false; + if (xpp != null) { + xpp.red = true; + rotateLeft(xpp); + } + } + } + } + } + TreeNode r = root; + if (r != null && r.red) + r.red = false; } return null; } @@ -765,9 +896,9 @@ public class ConcurrentHashMapV8 TreeNode pl = p.left; TreeNode pr = p.right; if (pl != null && pr != null) { - TreeNode s = pr; - while (s.left != null) // find successor - s = s.left; + TreeNode s = pr, sl; + while ((sl = s.left) != null) // find successor + s = sl; boolean c = s.red; s.red = p.red; p.red = c; // swap colors TreeNode sr = s.right; TreeNode pp = p.parent; @@ -819,198 +950,99 @@ public class ConcurrentHashMapV8 pp.right = replacement; p.left = p.right = p.parent = null; } - if (!p.red) - fixAfterDeletion(replacement); - if (p == replacement && (pp = p.parent) != null) { - if (p == pp.left) // detach pointers - pp.left = null; - else if (p == pp.right) - pp.right = null; - p.parent = null; - } - } - - // CLR code updated from pre-jdk-collections version at - // http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java - - /** From CLR */ - private void rotateLeft(TreeNode p) { - if (p != null) { - TreeNode r = p.right, pp, rl; - if ((rl = p.right = r.left) != null) - rl.parent = p; - if ((pp = r.parent = p.parent) == null) - root = r; - else if (pp.left == p) - pp.left = r; - else - pp.right = r; - r.left = p; - p.parent = r; - } - } - - /** From CLR */ - private void rotateRight(TreeNode p) { - if (p != null) { - TreeNode l = p.left, pp, lr; - if ((lr = p.left = l.right) != null) - lr.parent = p; - if ((pp = l.parent = p.parent) == null) - root = l; - else if (pp.right == p) - pp.right = l; - else - pp.left = l; - l.right = p; - p.parent = l; - } - } - - /** From CLR */ - private void fixAfterInsertion(TreeNode x) { - x.red = true; - TreeNode xp, xpp; - while (x != null && (xp = x.parent) != null && xp.red && - (xpp = xp.parent) != null) { - TreeNode xppl = xpp.left; - if (xp == xppl) { - TreeNode y = xpp.right; - if (y != null && y.red) { - y.red = false; - xp.red = false; - xpp.red = true; - x = xpp; - } - else { - if (x == xp.right) { - x = xp; - rotateLeft(x); - xpp = (xp = x.parent) == null ? null : xp.parent; - } - if (xp != null) { - xp.red = false; - if (xpp != null) { - xpp.red = true; - rotateRight(xpp); - } - } - } - } - else { - TreeNode y = xppl; - if (y != null && y.red) { - y.red = false; - xp.red = false; - xpp.red = true; - x = xpp; + if (!p.red) { // rebalance, from CLR + TreeNode x = replacement; + while (x != null) { + TreeNode xp, xpl; + if (x.red || (xp = x.parent) == null) { + x.red = false; + break; } - else { - if (x == xp.left) { - x = xp; - rotateRight(x); - xpp = (xp = x.parent) == null ? null : xp.parent; - } - if (xp != null) { - xp.red = false; - if (xpp != null) { - xpp.red = true; - rotateLeft(xpp); - } + if (x == (xpl = xp.left)) { + TreeNode sib = xp.right; + if (sib != null && sib.red) { + sib.red = false; + xp.red = true; + rotateLeft(xp); + sib = (xp = x.parent) == null ? null : xp.right; } - } - } - } - TreeNode r = root; - if (r != null && r.red) - r.red = false; - } - - /** From CLR */ - private void fixAfterDeletion(TreeNode x) { - while (x != null) { - TreeNode xp, xpl; - if (x.red || (xp = x.parent) == null) { - x.red = false; - break; - } - if (x == (xpl = xp.left)) { - TreeNode sib = xp.right; - if (sib != null && sib.red) { - sib.red = false; - xp.red = true; - rotateLeft(xp); - sib = (xp = x.parent) == null ? null : xp.right; - } - if (sib == null) - x = xp; - else { - TreeNode sl = sib.left, sr = sib.right; - if ((sr == null || !sr.red) && - (sl == null || !sl.red)) { - sib.red = true; + if (sib == null) x = xp; - } else { - if (sr == null || !sr.red) { - if (sl != null) - sl.red = false; + TreeNode sl = sib.left, sr = sib.right; + if ((sr == null || !sr.red) && + (sl == null || !sl.red)) { sib.red = true; - rotateRight(sib); - sib = (xp = x.parent) == null ? null : xp.right; + x = xp; } - if (sib != null) { - sib.red = (xp == null) ? false : xp.red; - if ((sr = sib.right) != null) - sr.red = false; - } - if (xp != null) { - xp.red = false; - rotateLeft(xp); + else { + if (sr == null || !sr.red) { + if (sl != null) + sl.red = false; + sib.red = true; + rotateRight(sib); + sib = (xp = x.parent) == null ? null : xp.right; + } + if (sib != null) { + sib.red = (xp == null) ? false : xp.red; + if ((sr = sib.right) != null) + sr.red = false; + } + if (xp != null) { + xp.red = false; + rotateLeft(xp); + } + x = root; } - x = root; } } - } - else { // symmetric - TreeNode sib = xpl; - if (sib != null && sib.red) { - sib.red = false; - xp.red = true; - rotateRight(xp); - sib = (xp = x.parent) == null ? null : xp.left; - } - if (sib == null) - x = xp; - else { - TreeNode sl = sib.left, sr = sib.right; - if ((sl == null || !sl.red) && - (sr == null || !sr.red)) { - sib.red = true; - x = xp; + else { // symmetric + TreeNode sib = xpl; + if (sib != null && sib.red) { + sib.red = false; + xp.red = true; + rotateRight(xp); + sib = (xp = x.parent) == null ? null : xp.left; } + if (sib == null) + x = xp; else { - if (sl == null || !sl.red) { - if (sr != null) - sr.red = false; + TreeNode sl = sib.left, sr = sib.right; + if ((sl == null || !sl.red) && + (sr == null || !sr.red)) { sib.red = true; - rotateLeft(sib); - sib = (xp = x.parent) == null ? null : xp.left; - } - if (sib != null) { - sib.red = (xp == null) ? false : xp.red; - if ((sl = sib.left) != null) - sl.red = false; + x = xp; } - if (xp != null) { - xp.red = false; - rotateRight(xp); + else { + if (sl == null || !sl.red) { + if (sr != null) + sr.red = false; + sib.red = true; + rotateLeft(sib); + sib = (xp = x.parent) == null ? null : xp.left; + } + if (sib != null) { + sib.red = (xp == null) ? false : xp.red; + if ((sl = sib.left) != null) + sl.red = false; + } + if (xp != null) { + xp.red = false; + rotateRight(xp); + } + x = root; } - x = root; } } } } + if (p == replacement && (pp = p.parent) != null) { + if (p == pp.left) // detach pointers + pp.left = null; + else if (p == pp.right) + pp.right = null; + p.parent = null; + } } } @@ -1025,7 +1057,7 @@ public class ConcurrentHashMapV8 * we apply a transform that spreads the impact of higher bits * downward. There is a tradeoff between speed, utility, and * quality of bit-spreading. Because many common sets of hashes - * are already reaonably distributed across bits (so don't benefit + * are already reasonably distributed across bits (so don't benefit * from spreading), and because we use trees to handle large sets * of collisions in bins, we don't need excessively high quality. */ @@ -1386,7 +1418,7 @@ public class ConcurrentHashMapV8 /** Implementation for computeIfAbsent */ private final Object internalComputeIfAbsent(K k, - MappingFunction mf) { + Fun mf) { int h = spread(k.hashCode()); Object val = null; int count = 0; @@ -1399,7 +1431,7 @@ public class ConcurrentHashMapV8 if (casTabAt(tab, i, null, node)) { count = 1; try { - if ((val = mf.map(k)) != null) + if ((val = mf.apply(k)) != null) node.val = val; } finally { if (val == null) @@ -1424,7 +1456,7 @@ public class ConcurrentHashMapV8 TreeNode p = t.getTreeNode(h, k, t.root); if (p != null) val = p.val; - else if ((val = mf.map(k)) != null) { + else if ((val = mf.apply(k)) != null) { added = true; count = 2; t.putTreeNode(h, k, val); @@ -1478,7 +1510,7 @@ public class ConcurrentHashMapV8 } Node last = e; if ((e = e.next) == null) { - if ((val = mf.map(k)) != null) { + if ((val = mf.apply(k)) != null) { added = true; last.next = new Node(h, k, val, null); if (count >= TREE_THRESHOLD) @@ -1504,37 +1536,39 @@ public class ConcurrentHashMapV8 } } } - if (val == null) - throw new NullPointerException(); - counter.add(1L); - if (count > 1) - checkForResize(); + if (val != null) { + counter.add(1L); + if (count > 1) + checkForResize(); + } return val; } /** Implementation for compute */ @SuppressWarnings("unchecked") - private final Object internalCompute(K k, - RemappingFunction mf) { + private final Object internalCompute(K k, boolean onlyIfPresent, + BiFun mf) { int h = spread(k.hashCode()); Object val = null; - boolean added = false; + int delta = 0; int count = 0; for (Node[] tab = table;;) { Node f; int i, fh; Object fk; if (tab == null) tab = initTable(); else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) { + if (onlyIfPresent) + break; Node node = new Node(fh = h | LOCKED, k, null, null); if (casTabAt(tab, i, null, node)) { try { count = 1; - if ((val = mf.remap(k, null)) != null) { + if ((val = mf.apply(k, null)) != null) { node.val = val; - added = true; + delta = 1; } } finally { - if (!added) + if (delta == 0) setTabAt(tab, i, null); if (!node.casHash(fh, h)) { node.hash = h; @@ -1554,15 +1588,19 @@ public class ConcurrentHashMapV8 count = 1; TreeNode p = t.getTreeNode(h, k, t.root); Object pv = (p == null) ? null : p.val; - if ((val = mf.remap(k, (V)pv)) != null) { + if ((val = mf.apply(k, (V)pv)) != null) { if (p != null) p.val = val; else { count = 2; - added = true; + delta = 1; t.putTreeNode(h, k, val); } } + else if (p != null) { + delta = -1; + t.deleteTreeNode(p); + } } } finally { t.release(0); @@ -1581,21 +1619,29 @@ public class ConcurrentHashMapV8 try { if (tabAt(tab, i) == f) { count = 1; - for (Node e = f;; ++count) { + for (Node e = f, pred = null;; ++count) { Object ek, ev; if ((e.hash & HASH_BITS) == h && (ev = e.val) != null && ((ek = e.key) == k || k.equals(ek))) { - val = mf.remap(k, (V)ev); + val = mf.apply(k, (V)ev); if (val != null) e.val = val; + else { + delta = -1; + Node en = e.next; + if (pred != null) + pred.next = en; + else + setTabAt(tab, i, en); + } break; } - Node last = e; + pred = e; if ((e = e.next) == null) { - if ((val = mf.remap(k, null)) != null) { - last.next = new Node(h, k, val, null); - added = true; + if (!onlyIfPresent && (val = mf.apply(k, null)) != null) { + pred.next = new Node(h, k, val, null); + delta = 1; if (count >= TREE_THRESHOLD) replaceWithTreeBin(tab, i, k); } @@ -1616,10 +1662,115 @@ public class ConcurrentHashMapV8 } } } - if (val == null) - throw new NullPointerException(); - if (added) { - counter.add(1L); + if (delta != 0) { + counter.add((long)delta); + if (count > 1) + checkForResize(); + } + return val; + } + + private final Object internalMerge(K k, V v, + BiFun mf) { + int h = spread(k.hashCode()); + Object val = null; + int delta = 0; + int count = 0; + for (Node[] tab = table;;) { + int i; Node f; int fh; Object fk, fv; + if (tab == null) + tab = initTable(); + else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) { + if (casTabAt(tab, i, null, new Node(h, k, v, null))) { + delta = 1; + val = v; + break; + } + } + else if ((fh = f.hash) == MOVED) { + if ((fk = f.key) instanceof TreeBin) { + TreeBin t = (TreeBin)fk; + t.acquire(0); + try { + if (tabAt(tab, i) == f) { + count = 1; + TreeNode p = t.getTreeNode(h, k, t.root); + val = (p == null) ? v : mf.apply((V)p.val, v); + if (val != null) { + if (p != null) + p.val = val; + else { + count = 2; + delta = 1; + t.putTreeNode(h, k, val); + } + } + else if (p != null) { + delta = -1; + t.deleteTreeNode(p); + } + } + } finally { + t.release(0); + } + if (count != 0) + break; + } + else + tab = (Node[])fk; + } + else if ((fh & LOCKED) != 0) { + checkForResize(); + f.tryAwaitLock(tab, i); + } + else if (f.casHash(fh, fh | LOCKED)) { + try { + if (tabAt(tab, i) == f) { + count = 1; + for (Node e = f, pred = null;; ++count) { + Object ek, ev; + if ((e.hash & HASH_BITS) == h && + (ev = e.val) != null && + ((ek = e.key) == k || k.equals(ek))) { + val = mf.apply(v, (V)ev); + if (val != null) + e.val = val; + else { + delta = -1; + Node en = e.next; + if (pred != null) + pred.next = en; + else + setTabAt(tab, i, en); + } + break; + } + pred = e; + if ((e = e.next) == null) { + val = v; + pred.next = new Node(h, k, val, null); + delta = 1; + if (count >= TREE_THRESHOLD) + replaceWithTreeBin(tab, i, k); + break; + } + } + } + } finally { + if (!f.casHash(fh | LOCKED, fh)) { + f.hash = fh; + synchronized (f) { f.notifyAll(); }; + } + } + if (count != 0) { + if (tab.length <= 64) + count = 2; + break; + } + } + } + if (delta != 0) { + counter.add((long)delta); if (count > 1) checkForResize(); } @@ -1937,8 +2088,8 @@ public class ConcurrentHashMapV8 } /** - * Split a normal bin with list headed by e into lo and hi parts; - * install in given table + * Splits a normal bin with list headed by e into lo and hi parts; + * installs in given table. */ private static void splitBin(Node[] nextTab, int i, Node e) { int bit = nextTab.length >>> 1; // bit to split on @@ -1968,7 +2119,7 @@ public class ConcurrentHashMapV8 } /** - * Split a tree bin into lo and hi parts; install in given table + * Splits a tree bin into lo and hi parts; installs in given table. */ private static void splitTreeBin(Node[] nextTab, int i, TreeBin t) { int bit = nextTab.length >>> 1; @@ -2082,11 +2233,12 @@ public class ConcurrentHashMapV8 * valid. * * Internal traversals directly access these fields, as in: - * {@code while (it.next != null) { process(it.nextKey); it.advance(); }} + * {@code while (it.advance() != null) { process(it.nextKey); }} * - * Exported iterators (subclasses of ViewIterator) extract key, - * value, or key-value pairs as return values of Iterator.next(), - * and encapsulate the it.next check as hasNext(); + * Exported iterators must track whether the iterator has advanced + * (in hasNext vs next) (by setting/checking/nulling field + * nextVal), and then extract key, value, or key-value pairs as + * return values of next(). * * The iterator visits once each still-valid node that was * reachable upon iterator construction. It might miss some that @@ -2105,10 +2257,13 @@ public class ConcurrentHashMapV8 * across threads, iteration terminates if a bounds checks fails * for a table read. * - * The range-based constructor enables creation of parallel - * range-splitting traversals. (Not yet implemented.) + * 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. */ - static class InternalIterator { + static class Traverser extends ForkJoinTask { + final ConcurrentHashMapV8 map; Node next; // the next entry to use Node last; // the last entry used Object nextKey; // cached key field of next @@ -2116,31 +2271,37 @@ public class ConcurrentHashMapV8 Node[] tab; // current table; updated if resized int index; // index of bin to use next int baseIndex; // current index of initial table - final int baseLimit; // index bound for initial table + int baseLimit; // index bound for initial table final int baseSize; // initial table size /** Creates iterator for all entries in the table. */ - InternalIterator(Node[] tab) { - this.tab = tab; + Traverser(ConcurrentHashMapV8 map) { + this.tab = (this.map = map).table; baseLimit = baseSize = (tab == null) ? 0 : tab.length; - index = baseIndex = 0; - next = null; - advance(); - } - - /** Creates iterator for the given range of the table */ - InternalIterator(Node[] tab, int lo, int hi) { - this.tab = tab; - baseSize = (tab == null) ? 0 : tab.length; - baseLimit = (hi <= baseSize) ? hi : baseSize; - index = baseIndex = (lo >= 0) ? lo : 0; - next = null; - advance(); } - /** Advances next. See above for explanation. */ - final void advance() { + /** Creates iterator for split() methods */ + Traverser(Traverser it, boolean split) { + this.map = it.map; + this.tab = it.tab; + 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; + } + + /** + * Advances next; returns nextVal or null if terminated. + * See above for explanation. + */ + final Object advance() { Node e = last = next; + Object ev = null; outer: do { if (e != null) // advance past used/skipped node e = e.next; @@ -2160,15 +2321,35 @@ public class ConcurrentHashMapV8 index = (i += baseSize) < n ? i : (baseIndex = b + 1); } nextKey = e.key; - } while ((nextVal = e.val) == null);// skip deleted or special nodes + } while ((ev = e.val) == null); // skip deleted or special nodes next = e; + return nextVal = ev; + } + + public final void remove() { + if (nextVal == null) + advance(); + Node e = last; + if (e == null) + throw new IllegalStateException(); + last = null; + map.remove(e.key); + } + + public final boolean hasNext() { + return nextVal != null || advance() != null; } + + public final boolean hasMoreElements() { return hasNext(); } + public final void setRawResult(Object x) { } + public R getRawResult() { return null; } + public boolean exec() { return true; } } /* ---------------- Public operations -------------- */ /** - * Creates a new, empty map with the default initial table size (16), + * Creates a new, empty map with the default initial table size (16). */ public ConcurrentHashMapV8() { this.counter = new LongAdder(); @@ -2249,8 +2430,8 @@ public class ConcurrentHashMapV8 if (initialCapacity < concurrencyLevel) // Use at least as many bins initialCapacity = concurrencyLevel; // as estimated threads long size = (long)(1.0 + (long)initialCapacity / loadFactor); - int cap = ((size >= (long)MAXIMUM_CAPACITY) ? - MAXIMUM_CAPACITY: tableSizeFor((int)size)); + int cap = (size >= (long)MAXIMUM_CAPACITY) ? + MAXIMUM_CAPACITY : tableSizeFor((int)size); this.counter = new LongAdder(); this.sizeCtl = cap; } @@ -2272,7 +2453,16 @@ public class ConcurrentHashMapV8 (int)n); } - final long longSize() { // accurate version of size needed for views + /** + * Returns the number of mappings. This method should be used + * 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. + * + * @return the number of mappings + */ + public long mappingCount() { long n = counter.sum(); return (n < 0L) ? 0L : n; } @@ -2289,7 +2479,7 @@ public class ConcurrentHashMapV8 * @throws NullPointerException if the specified key is null */ @SuppressWarnings("unchecked") - public V get(Object key) { + public V get(Object key) { if (key == null) throw new NullPointerException(); return (V)internalGet(key); @@ -2324,11 +2514,10 @@ public class ConcurrentHashMapV8 if (value == null) throw new NullPointerException(); Object v; - InternalIterator it = new InternalIterator(table); - while (it.next != null) { - if ((v = it.nextVal) == value || value.equals(v)) + Traverser it = new Traverser(this); + while ((v = it.advance()) != null) { + if (v == value || value.equals(v)) return true; - it.advance(); } return false; } @@ -2366,7 +2555,7 @@ public class ConcurrentHashMapV8 * @throws NullPointerException if the specified key or value is null */ @SuppressWarnings("unchecked") - public V put(K key, V value) { + public V put(K key, V value) { if (key == null || value == null) throw new NullPointerException(); return (V)internalPut(key, value); @@ -2380,7 +2569,7 @@ public class ConcurrentHashMapV8 * @throws NullPointerException if the specified key or value is null */ @SuppressWarnings("unchecked") - public V putIfAbsent(K key, V value) { + public V putIfAbsent(K key, V value) { if (key == null || value == null) throw new NullPointerException(); return (V)internalPutIfAbsent(key, value); @@ -2399,37 +2588,37 @@ public class ConcurrentHashMapV8 /** * If the specified key is not already associated with a value, - * computes its value using the given mappingFunction and - * enters it into the map. This is equivalent to + * computes its value using the given mappingFunction and enters + * it into the map unless null. This is equivalent to * 
 {@code
      * if (map.containsKey(key))
      *   return map.get(key);
-     * value = mappingFunction.map(key);
-     * map.put(key, value);
+     * value = mappingFunction.apply(key);
+     * if (value != null)
+     *   map.put(key, value);
      * return value;}
* * except that the action is performed atomically. If the - * function returns {@code null} (in which case a {@code - * NullPointerException} is thrown), or the function itself throws - * an (unchecked) exception, the exception is rethrown to its - * caller, and no mapping is recorded. Some attempted update - * operations on this map by other threads may be blocked while - * computation is in progress, so the computation should be short - * and simple, and must not attempt to update any other mappings - * of this Map. The most appropriate usage is to construct a new - * object serving as an initial mapped value, or memoized result, - * as in: + * function returns {@code null} no mapping is recorded. If the + * function itself throws an (unchecked) exception, the exception + * is rethrown to its caller, and no mapping is recorded. Some + * attempted update operations on this map by other threads may be + * blocked while computation is in progress, so the computation + * should be short and simple, and must not attempt to update any + * other mappings of this Map. The most appropriate usage is to + * construct a new object serving as an initial mapped value, or + * memoized result, as in: * * 
 {@code
-     * map.computeIfAbsent(key, new MappingFunction() {
+     * map.computeIfAbsent(key, new Fun() {
      *   public V map(K k) { return new Value(f(k)); }});}
* * @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. - * @throws NullPointerException if the specified key, mappingFunction, - * or 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 * attempts a recursive update to this map that would * otherwise never complete @@ -2437,55 +2626,129 @@ public class ConcurrentHashMapV8 * in which case the mapping is left unestablished */ @SuppressWarnings("unchecked") - public V computeIfAbsent(K key, MappingFunction mappingFunction) { + public V computeIfAbsent(K key, Fun mappingFunction) { if (key == null || mappingFunction == null) throw new NullPointerException(); return (V)internalComputeIfAbsent(key, mappingFunction); } /** - * Computes and enters a new mapping value given a key and + * If the given key is present, computes a new mapping value given a key and + * its current mapped value. This is equivalent to + * 
 {@code
+     *   if (map.containsKey(key)) {
+     *     value = remappingFunction.apply(key, map.get(key));
+     *     if (value != null)
+     *       map.put(key, value);
+     *     else
+     *       map.remove(key);
+     *   }
+     * }
+ * + * except that the action is performed atomically. If the + * function returns {@code null}, the mapping is removed. If the + * function itself throws an (unchecked) exception, the exception + * is rethrown to its caller, and the current mapping is left + * unchanged. Some attempted update operations on this map by + * other threads may be blocked while computation is in progress, + * so the computation should be short and simple, and must not + * attempt to update any other mappings of this Map. For example, + * to either create or append new messages to a value mapping: + * + * @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 + * @throws NullPointerException if the specified key or remappingFunction + * is null + * @throws IllegalStateException if the computation detectably + * attempts a recursive update to this map that would + * otherwise never complete + * @throws RuntimeException or Error if the remappingFunction does so, + * in which case the mapping is unchanged + */ + public V computeIfPresent(K key, BiFun remappingFunction) { + if (key == null || remappingFunction == null) + throw new NullPointerException(); + return (V)internalCompute(key, true, remappingFunction); + } + + /** + * Computes a new mapping value given a key and * its current mapped value (or {@code null} if there is no current * mapping). This is equivalent to * 
 {@code
-     *  map.put(key, remappingFunction.remap(key, map.get(key));
+     *   value = remappingFunction.apply(key, map.get(key));
+     *   if (value != null)
+     *     map.put(key, value);
+     *   else
+     *     map.remove(key);
      * }
* * except that the action is performed atomically. If the - * function returns {@code null} (in which case a {@code - * NullPointerException} is thrown), or the function itself throws - * an (unchecked) exception, the exception is rethrown to its - * caller, and current mapping is left unchanged. Some attempted - * update operations on this map by other threads may be blocked - * while computation is in progress, so the computation should be - * short and simple, and must not attempt to update any other - * mappings of this Map. For example, to either create or - * append new messages to a value mapping: + * function returns {@code null}, the mapping is removed. If the + * function itself throws an (unchecked) exception, the exception + * is rethrown to its caller, and the current mapping is left + * unchanged. Some attempted update operations on this map by + * other threads may be blocked while computation is in progress, + * so the computation should be short and simple, and must not + * attempt to update any other mappings of this Map. For example, + * to either create or append new messages to a value mapping: * * 
 {@code
      * Map map = ...;
      * final String msg = ...;
-     * map.compute(key, new RemappingFunction() {
-     *   public String remap(Key k, String v) {
+     * map.compute(key, new BiFun() {
+     *   public String apply(Key k, String v) {
      *    return (v == null) ? msg : v + msg;});}}
* * @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. + * @return the new value associated with the specified key, or null if none * @throws NullPointerException if the specified key or remappingFunction - * or computed value is null + * is null * @throws IllegalStateException if the computation detectably * attempts a recursive update to this map that would * otherwise never complete * @throws RuntimeException or Error if the remappingFunction does so, * in which case the mapping is unchanged */ - @SuppressWarnings("unchecked") - public V compute(K key, RemappingFunction remappingFunction) { + // @SuppressWarnings("unchecked") + public V compute(K key, BiFun remappingFunction) { if (key == null || remappingFunction == null) throw new NullPointerException(); - return (V)internalCompute(key, remappingFunction); + return (V)internalCompute(key, false, remappingFunction); + } + + /** + * If the specified key is not already associated + * with a value, associate it with the given value. + * Otherwise, replace the value with the results of + * the given remapping function. This is equivalent to: + * 
 {@code
+     *   if (!map.containsKey(key))
+     *     map.put(value);
+     *   else {
+     *     newValue = remappingFunction.apply(map.get(key), value);
+     *     if (value != null)
+     *       map.put(key, value);
+     *     else
+     *       map.remove(key);
+     *   }
+     * }
+ * except that the action is performed atomically. If the + * function returns {@code null}, the mapping is removed. If the + * function itself throws an (unchecked) exception, the exception + * is rethrown to its caller, and the current mapping is left + * unchanged. Some attempted update operations on this map by + * other threads may be blocked while computation is in progress, + * 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 remappingFunction) { + if (key == null || value == null || remappingFunction == null) + throw new NullPointerException(); + return (V)internalMerge(key, value, remappingFunction); } /** @@ -2498,7 +2761,7 @@ public class ConcurrentHashMapV8 * @throws NullPointerException if the specified key is null */ @SuppressWarnings("unchecked") - public V remove(Object key) { + public V remove(Object key) { if (key == null) throw new NullPointerException(); return (V)internalReplace(key, null, null); @@ -2536,7 +2799,7 @@ public class ConcurrentHashMapV8 * @throws NullPointerException if the specified key or value is null */ @SuppressWarnings("unchecked") - public V replace(K key, V value) { + public V replace(K key, V value) { if (key == null || value == null) throw new NullPointerException(); return (V)internalReplace(key, value, null); @@ -2633,6 +2896,33 @@ public class ConcurrentHashMapV8 } /** + * Returns a partitionable iterator of the keys in this map. + * + * @return a partitionable iterator of the keys in this map + */ + public Spliterator keySpliterator() { + return new KeyIterator(this); + } + + /** + * Returns a partitionable iterator of the values in this map. + * + * @return a partitionable iterator of the values in this map + */ + public Spliterator valueSpliterator() { + return new ValueIterator(this); + } + + /** + * Returns a partitionable iterator of the entries in this map. + * + * @return a partitionable iterator of the entries in this map + */ + public Spliterator> entrySpliterator() { + return new EntryIterator(this); + } + + /** * Returns the hash code value for this {@link Map}, i.e., * the sum of, for each key-value pair in the map, * {@code key.hashCode() ^ value.hashCode()}. @@ -2641,10 +2931,10 @@ public class ConcurrentHashMapV8 */ public int hashCode() { int h = 0; - InternalIterator it = new InternalIterator(table); - while (it.next != null) { - h += it.nextKey.hashCode() ^ it.nextVal.hashCode(); - it.advance(); + Traverser it = new Traverser(this); + Object v; + while ((v = it.advance()) != null) { + h += it.nextKey.hashCode() ^ v.hashCode(); } return h; } @@ -2661,17 +2951,17 @@ public class ConcurrentHashMapV8 * @return a string representation of this map */ public String toString() { - InternalIterator it = new InternalIterator(table); + Traverser it = new Traverser(this); StringBuilder sb = new StringBuilder(); sb.append('{'); - if (it.next != null) { + Object v; + if ((v = it.advance()) != null) { for (;;) { - Object k = it.nextKey, v = it.nextVal; + Object k = it.nextKey; sb.append(k == this ? "(this Map)" : k); sb.append('='); sb.append(v == this ? "(this Map)" : v); - it.advance(); - if (it.next == null) + if ((v = it.advance()) == null) break; sb.append(',').append(' '); } @@ -2694,13 +2984,12 @@ public class ConcurrentHashMapV8 if (!(o instanceof Map)) return false; Map m = (Map) o; - InternalIterator it = new InternalIterator(table); - while (it.next != null) { - Object val = it.nextVal; + Traverser it = new Traverser(this); + Object val; + while ((val = it.advance()) != null) { Object v = m.get(it.nextKey); if (v == null || (v != val && !v.equals(val))) return false; - it.advance(); } for (Map.Entry e : m.entrySet()) { Object mk, mv, v; @@ -2716,97 +3005,88 @@ public class ConcurrentHashMapV8 /* ----------------Iterators -------------- */ - /** - * Base class for key, value, and entry iterators. Adds a map - * reference to InternalIterator to support Iterator.remove. - */ - static abstract class ViewIterator extends InternalIterator { - final ConcurrentHashMapV8 map; - ViewIterator(ConcurrentHashMapV8 map) { - super(map.table); - this.map = map; + static final class KeyIterator extends Traverser + implements Spliterator, Enumeration { + KeyIterator(ConcurrentHashMapV8 map) { super(map); } + KeyIterator(Traverser it, boolean split) { + super(it, split); } - - public final void remove() { - if (last == null) + public KeyIterator split() { + if (last != null || (next != null && nextVal == null)) throw new IllegalStateException(); - map.remove(last.key); - last = null; + return new KeyIterator(this, true); } - - public final boolean hasNext() { return next != null; } - public final boolean hasMoreElements() { return next != null; } - } - - static final class KeyIterator extends ViewIterator - implements Iterator, Enumeration { - KeyIterator(ConcurrentHashMapV8 map) { super(map); } - @SuppressWarnings("unchecked") - public final K next() { - if (next == null) + public final K next() { + if (nextVal == null && advance() == null) throw new NoSuchElementException(); Object k = nextKey; - advance(); - return (K)k; + nextVal = null; + return (K) k; } public final K nextElement() { return next(); } } - static final class ValueIterator extends ViewIterator - implements Iterator, Enumeration { + static final class ValueIterator extends Traverser + implements Spliterator, Enumeration { ValueIterator(ConcurrentHashMapV8 map) { super(map); } + ValueIterator(Traverser it, boolean split) { + super(it, split); + } + public ValueIterator split() { + if (last != null || (next != null && nextVal == null)) + throw new IllegalStateException(); + return new ValueIterator(this, true); + } @SuppressWarnings("unchecked") - public final V next() { - if (next == null) + public final V next() { + Object v; + if ((v = nextVal) == null && (v = advance()) == null) throw new NoSuchElementException(); - Object v = nextVal; - advance(); - return (V)v; + nextVal = null; + return (V) v; } public final V nextElement() { return next(); } } - static final class EntryIterator extends ViewIterator - implements Iterator> { + static final class EntryIterator extends Traverser + implements Spliterator> { EntryIterator(ConcurrentHashMapV8 map) { super(map); } - - @SuppressWarnings("unchecked") - public final Map.Entry next() { - if (next == null) - throw new NoSuchElementException(); - Object k = nextKey; - Object v = nextVal; - advance(); - return new WriteThroughEntry((K)k, (V)v, map); + EntryIterator(Traverser it, boolean split) { + super(it, split); + } + public EntryIterator split() { + if (last != null || (next != null && nextVal == null)) + throw new IllegalStateException(); + return new EntryIterator(this, true); } - } - - static final class SnapshotEntryIterator extends ViewIterator - implements Iterator> { - SnapshotEntryIterator(ConcurrentHashMapV8 map) { super(map); } @SuppressWarnings("unchecked") - public final Map.Entry next() { - if (next == null) + public final Map.Entry next() { + Object v; + if ((v = nextVal) == null && (v = advance()) == null) throw new NoSuchElementException(); Object k = nextKey; - Object v = nextVal; - advance(); - return new SnapshotEntry((K)k, (V)v); + nextVal = null; + return new MapEntry((K)k, (V)v, map); } } /** - * Base of writeThrough and Snapshot entry classes + * Exported Entry for iterators */ - static abstract class MapEntry implements Map.Entry { + static final class MapEntry implements Map.Entry { final K key; // non-null V val; // non-null - MapEntry(K key, V val) { this.key = key; this.val = val; } + final ConcurrentHashMapV8 map; + MapEntry(K key, V val, ConcurrentHashMapV8 map) { + this.key = key; + this.val = val; + this.map = map; + } public final K getKey() { return key; } public final V getValue() { return val; } public final int hashCode() { return key.hashCode() ^ val.hashCode(); } @@ -2821,29 +3101,13 @@ public class ConcurrentHashMapV8 (v == val || v.equals(val))); } - public abstract V setValue(V value); - } - - /** - * Entry used by EntryIterator.next(), that relays setValue - * changes to the underlying map. - */ - static final class WriteThroughEntry extends MapEntry - implements Map.Entry { - final ConcurrentHashMapV8 map; - WriteThroughEntry(K key, V val, ConcurrentHashMapV8 map) { - super(key, val); - this.map = map; - } - /** * Sets our entry's value and writes through to the map. The - * value to return is somewhat arbitrary here. Since a - * WriteThroughEntry does not necessarily track asynchronous - * changes, the most recent "previous" value could be - * different from what we return (or could even have been - * removed in which case the put will re-establish). We do not - * and cannot guarantee more. + * value to return is somewhat arbitrary here. Since we do not + * necessarily track asynchronous changes, the most recent + * "previous" value could be different from what we return (or + * could even have been removed in which case the put will + * re-establish). We do not and cannot guarantee more. */ public final V setValue(V value) { if (value == null) throw new NullPointerException(); @@ -2854,48 +3118,33 @@ public class ConcurrentHashMapV8 } } - /** - * Internal version of entry, that doesn't write though changes - */ - static final class SnapshotEntry extends MapEntry - implements Map.Entry { - SnapshotEntry(K key, V val) { super(key, val); } - public final V setValue(V value) { // only locally update - if (value == null) throw new NullPointerException(); - V v = val; - val = value; - return v; - } - } - /* ----------------Views -------------- */ /** - * Base class for views. This is done mainly to allow adding - * customized parallel traversals (not yet implemented.) + * Base class for views. */ - static abstract class MapView { + static abstract class CHMView { final ConcurrentHashMapV8 map; - MapView(ConcurrentHashMapV8 map) { this.map = 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 Iterator iter(); + 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.longSize(); + 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 = iter(); + Iterator it = iterator(); while (it.hasNext()) { if (i == n) { if (n >= MAX_ARRAY_SIZE) @@ -2912,8 +3161,8 @@ public class ConcurrentHashMapV8 } @SuppressWarnings("unchecked") - public final T[] toArray(T[] a) { - long sz = map.longSize(); + public final T[] toArray(T[] a) { + long sz = map.mappingCount(); if (sz > (long)(MAX_ARRAY_SIZE)) throw new OutOfMemoryError(oomeMsg); int m = (int)sz; @@ -2922,7 +3171,7 @@ public class ConcurrentHashMapV8 .newInstance(a.getClass().getComponentType(), m); int n = r.length; int i = 0; - Iterator it = iter(); + Iterator it = iterator(); while (it.hasNext()) { if (i == n) { if (n >= MAX_ARRAY_SIZE) @@ -2944,7 +3193,7 @@ public class ConcurrentHashMapV8 public final int hashCode() { int h = 0; - for (Iterator it = iter(); it.hasNext();) + for (Iterator it = iterator(); it.hasNext();) h += it.next().hashCode(); return h; } @@ -2952,7 +3201,7 @@ public class ConcurrentHashMapV8 public final String toString() { StringBuilder sb = new StringBuilder(); sb.append('['); - Iterator it = iter(); + Iterator it = iterator(); if (it.hasNext()) { for (;;) { Object e = it.next(); @@ -2978,7 +3227,7 @@ public class ConcurrentHashMapV8 public final boolean removeAll(Collection c) { boolean modified = false; - for (Iterator it = iter(); it.hasNext();) { + for (Iterator it = iterator(); it.hasNext();) { if (c.contains(it.next())) { it.remove(); modified = true; @@ -2989,7 +3238,7 @@ public class ConcurrentHashMapV8 public final boolean retainAll(Collection c) { boolean modified = false; - for (Iterator it = iter(); it.hasNext();) { + for (Iterator it = iterator(); it.hasNext();) { if (!c.contains(it.next())) { it.remove(); modified = true; @@ -3000,17 +3249,15 @@ public class ConcurrentHashMapV8 } - static final class KeySet extends MapView implements Set { - KeySet(ConcurrentHashMapV8 map) { super(map); } + static final class KeySet extends CHMView implements Set { + KeySet(ConcurrentHashMapV8 map) { + super(map); + } public final boolean contains(Object o) { return map.containsKey(o); } public final boolean remove(Object o) { return map.remove(o) != null; } - public final Iterator iterator() { return new KeyIterator(map); } - final Iterator iter() { - return new KeyIterator(map); - } public final boolean add(K e) { throw new UnsupportedOperationException(); } @@ -3025,11 +3272,11 @@ public class ConcurrentHashMapV8 } } - static final class Values extends MapView + + 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); @@ -3045,21 +3292,18 @@ public class ConcurrentHashMapV8 public final Iterator iterator() { return new ValueIterator(map); } - final Iterator iter() { - 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 MapView + 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) && @@ -3068,7 +3312,6 @@ public class ConcurrentHashMapV8 (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) && @@ -3076,13 +3319,9 @@ public class ConcurrentHashMapV8 (v = e.getValue()) != null && map.remove(k, v)); } - public final Iterator> iterator() { return new EntryIterator(map); } - final Iterator iter() { - return new SnapshotEntryIterator(map); - } public final boolean add(Entry e) { throw new UnsupportedOperationException(); } @@ -3119,8 +3358,8 @@ public class ConcurrentHashMapV8 * The key-value mappings are emitted in no particular order. */ @SuppressWarnings("unchecked") - private void writeObject(java.io.ObjectOutputStream s) - throws java.io.IOException { + private void writeObject(java.io.ObjectOutputStream s) + throws java.io.IOException { if (segments == null) { // for serialization compatibility segments = (Segment[]) new Segment[DEFAULT_CONCURRENCY_LEVEL]; @@ -3128,11 +3367,11 @@ public class ConcurrentHashMapV8 segments[i] = new Segment(LOAD_FACTOR); } s.defaultWriteObject(); - InternalIterator it = new InternalIterator(table); - while (it.next != null) { + Traverser it = new Traverser(this); + Object v; + while ((v = it.advance()) != null) { s.writeObject(it.nextKey); - s.writeObject(it.nextVal); - it.advance(); + s.writeObject(v); } s.writeObject(null); s.writeObject(null); @@ -3144,8 +3383,8 @@ public class ConcurrentHashMapV8 * @param s the stream */ @SuppressWarnings("unchecked") - private void readObject(java.io.ObjectInputStream s) - throws java.io.IOException, ClassNotFoundException { + private void readObject(java.io.ObjectInputStream s) + throws java.io.IOException, ClassNotFoundException { s.defaultReadObject(); this.segments = null; // unneeded // initialize transient final field @@ -3219,10 +3458,3250 @@ public class ConcurrentHashMapV8 p = p.next; } } + } + } + + + // ------------------------------------------------------- + + // Sams + /** Interface describing a void action of one argument */ + public interface Action { void apply(A a); } + /** Interface describing a void action of two arguments */ + public interface BiAction { void apply(A a, B b); } + /** Interface describing a function of one argument */ + public interface Fun { T apply(A a); } + /** Interface describing a function of two arguments */ + public interface BiFun { T apply(A a, B b); } + /** Interface describing a function of no arguments */ + public interface Generator { T apply(); } + /** Interface describing a function mapping its argument to a double */ + public interface ObjectToDouble { double apply(A a); } + /** Interface describing a function mapping its argument to a long */ + public interface ObjectToLong { long apply(A a); } + /** Interface describing a function mapping its argument to an int */ + public interface ObjectToInt {int apply(A a); } + /** Interface describing a function mapping two arguments to a double */ + public interface ObjectByObjectToDouble { double apply(A a, B b); } + /** Interface describing a function mapping two arguments to a long */ + public interface ObjectByObjectToLong { long apply(A a, B b); } + /** Interface describing a function mapping two arguments to an int */ + public interface ObjectByObjectToInt {int apply(A a, B b); } + /** Interface describing a function mapping a double to a double */ + public interface DoubleToDouble { double apply(double a); } + /** Interface describing a function mapping a long to a long */ + public interface LongToLong { long apply(long a); } + /** Interface describing a function mapping an int to an int */ + public interface IntToInt { int apply(int a); } + /** Interface describing a function mapping two doubles to a double */ + public interface DoubleByDoubleToDouble { double apply(double a, double b); } + /** Interface describing a function mapping two longs to a long */ + public interface LongByLongToLong { long apply(long a, long b); } + /** Interface describing a function mapping two ints to an int */ + public interface IntByIntToInt { int apply(int a, int b); } + + + // ------------------------------------------------------- + + /** + * Returns an extended {@link Parallel} view of this map using the + * given executor for bulk parallel operations. + * + * @param executor the executor + * @return a parallel view + */ + public Parallel parallel(ForkJoinPool executor) { + return new Parallel(executor); + } + + /** + * An extended view of a ConcurrentHashMap supporting bulk + * parallel operations. These operations are designed to be + * safely, and often sensibly, applied even with maps that are + * being concurrently updated by other threads; for example, when + * computing a snapshot summary of the values in a shared + * registry. There are three kinds of operation, each with four + * forms, accepting functions with Keys, Values, Entries, and + * (Key, Value) arguments and/or return values. Because the + * elements of a ConcurrentHashMap are not ordered in any + * particular way, and may be processed in different orders in + * different parallel executions, the correctness of supplied + * functions should not depend on any ordering, or on any other + * objects or values that may transiently change while computation + * is in progress; and except for forEach actions, should ideally + * be side-effect-free. + * + *
    + *
  • forEach: Perform a given action on each element. + * A variant form applies a given transformation on each element + * before performing the action.
    • + * + *
  • search: Return the first available non-null result of + * applying a given function on each element; skipping further + * search when a result is found.
    • + * + *
  • reduce: Accumulate each element. The supplied reduction + * function cannot rely on ordering (more formally, it should be + * both associative and commutative). There are five variants: + * + *
      + * + *
    • Plain reductions. (There is not a form of this method for + * (key, value) function arguments since there is no corresponding + * return type.)
      • + * + *
    • Mapped reductions that accumulate the results of a given + * function applied to each element.
      • + * + *
    • Reductions to scalar doubles, longs, and ints, using a + * given basis value.
      • + * + * + *
    + *
+ * + *

The concurrency properties of the bulk operations follow + * from those of ConcurrentHashMap: Any non-null result returned + * from {@code get(key)} and related access methods bears a + * happens-before relation with the associated insertion or + * update. The result of any bulk operation reflects the + * composition of these per-element relations (but is not + * necessarily atomic with respect to the map as a whole unless it + * is somehow known to be quiescent). Conversely, because keys + * and values in the map are never null, null serves as a reliable + * atomic indicator of the current lack of any result. To + * maintain this property, null serves as an implicit basis for + * all non-scalar reduction operations. For the double, long, and + * int versions, the basis should be one that, when combined with + * any other value, returns that other value (more formally, it + * should be the identity element for the reduction). Most common + * reductions have these properties; for example, computing a sum + * with basis 0 or a minimum with basis MAX_VALUE. + * + *

Search and transformation functions provided as arguments + * should similarly return null to indicate the lack of any result + * (in which case it is not used). In the case of mapped + * reductions, this also enables transformations to serve as + * filters, returning null (or, in the case of primitive + * specializations, the identity basis) if the element should not + * be combined. You can create compound transformations and + * filterings by composing them yourself under this "null means + * there is nothing there now" rule before using them in search or + * reduce operations. + * + *

Methods accepting and/or returning Entry arguments maintain + * key-value associations. They may be useful for example when + * finding the key for the greatest value. Note that "plain" Entry + * arguments can be supplied using {@code new + * AbstractMap.SimpleEntry(k,v)}. + * + *

Bulk operations may complete abruptly, throwing an + * exception encountered in the application of a supplied + * function. Bear in mind when handling such exceptions that other + * concurrently executing functions could also have thrown + * exceptions, or would have done so if the first exception had + * not occurred. + * + *

Parallel speedups compared to sequential processing are + * common but not guaranteed. Operations involving brief + * functions on small maps may execute more slowly than sequential + * loops if the underlying work to parallelize the computation is + * more expensive than the computation itself. Similarly, + * parallelization may not lead to much actual parallelism if all + * processors are busy performing unrelated tasks. + * + *

All arguments to all task methods must be non-null. + * + *

jsr166e note: During transition, this class + * uses nested functional interfaces with different names but the + * same forms as those expected for JDK8. + */ + public class Parallel { + final ForkJoinPool fjp; + + /** + * Returns an extended view of this map using the given + * executor for bulk parallel operations. + * + * @param executor the executor + */ + public Parallel(ForkJoinPool executor) { + this.fjp = executor; + } + + /** + * Performs the given action for each (key, value). + * + * @param action the action + */ + public void forEach(BiAction action) { + fjp.invoke(ForkJoinTasks.forEach + (ConcurrentHashMapV8.this, action)); + } + + /** + * Performs the given action for each non-null transformation + * 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). + * @param action the action + */ + public void forEach(BiFun transformer, + Action action) { + fjp.invoke(ForkJoinTasks.forEach + (ConcurrentHashMapV8.this, transformer, action)); + } + + /** + * 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. + * + * @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, value), or null if none + */ + public U search(BiFun searchFunction) { + return fjp.invoke(ForkJoinTasks.search + (ConcurrentHashMapV8.this, searchFunction)); + } + + /** + * Returns the result of accumulating the given transformation + * of all (key, value) pairs 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 (key, value) pairs + */ + public U reduce(BiFun transformer, + BiFun reducer) { + return fjp.invoke(ForkJoinTasks.reduce + (ConcurrentHashMapV8.this, transformer, reducer)); + } + + /** + * Returns 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. + * + * @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 (key, value) pairs + */ + public double reduceToDouble(ObjectByObjectToDouble transformer, + double basis, + DoubleByDoubleToDouble reducer) { + return fjp.invoke(ForkJoinTasks.reduceToDouble + (ConcurrentHashMapV8.this, transformer, basis, reducer)); + } + + /** + * Returns 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. + * + * @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 (key, value) pairs using the given reducer to + * combine values, and the given basis as an identity value. + */ + public long reduceToLong(ObjectByObjectToLong transformer, + long basis, + LongByLongToLong reducer) { + return fjp.invoke(ForkJoinTasks.reduceToLong + (ConcurrentHashMapV8.this, transformer, basis, reducer)); + } + + /** + * Returns 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. + * + * @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 (key, value) pairs + */ + public int reduceToInt(ObjectByObjectToInt transformer, + int basis, + IntByIntToInt reducer) { + return fjp.invoke(ForkJoinTasks.reduceToInt + (ConcurrentHashMapV8.this, transformer, basis, reducer)); + } + + /** + * Performs the given action for each key. + * + * @param action the action + */ + public void forEachKey(Action action) { + fjp.invoke(ForkJoinTasks.forEachKey + (ConcurrentHashMapV8.this, action)); + } + + /** + * 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 forEachKey(Fun transformer, + Action action) { + fjp.invoke(ForkJoinTasks.forEachKey + (ConcurrentHashMapV8.this, transformer, action)); + } + + /** + * 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. + * + * @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 searchKeys(Fun searchFunction) { + return fjp.invoke(ForkJoinTasks.searchKeys + (ConcurrentHashMapV8.this, searchFunction)); + } + + /** + * 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 reduceKeys(BiFun reducer) { + return fjp.invoke(ForkJoinTasks.reduceKeys + (ConcurrentHashMapV8.this, reducer)); + } + + /** + * Returns the result of accumulating the given transformation + * of all keys 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 keys + */ + public U reduceKeys(Fun transformer, + BiFun reducer) { + return fjp.invoke(ForkJoinTasks.reduceKeys + (ConcurrentHashMapV8.this, transformer, reducer)); + } + + /** + * 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 reduceKeysToDouble(ObjectToDouble transformer, + double basis, + DoubleByDoubleToDouble reducer) { + return fjp.invoke(ForkJoinTasks.reduceKeysToDouble + (ConcurrentHashMapV8.this, transformer, basis, reducer)); + } + + /** + * 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 reduceKeysToLong(ObjectToLong transformer, + long basis, + LongByLongToLong reducer) { + return fjp.invoke(ForkJoinTasks.reduceKeysToLong + (ConcurrentHashMapV8.this, transformer, basis, reducer)); + } + + /** + * 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 reduceKeysToInt(ObjectToInt transformer, + int basis, + IntByIntToInt reducer) { + return fjp.invoke(ForkJoinTasks.reduceKeysToInt + (ConcurrentHashMapV8.this, transformer, basis, reducer)); + } + + /** + * Performs the given action for each value. + * + * @param action the action + */ + public void forEachValue(Action action) { + fjp.invoke(ForkJoinTasks.forEachValue + (ConcurrentHashMapV8.this, action)); + } + + /** + * 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 forEachValue(Fun transformer, + Action action) { + fjp.invoke(ForkJoinTasks.forEachValue + (ConcurrentHashMapV8.this, transformer, action)); + } + + /** + * 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. + * + * @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 searchValues(Fun searchFunction) { + return fjp.invoke(ForkJoinTasks.searchValues + (ConcurrentHashMapV8.this, searchFunction)); + } + + /** + * 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 reduceValues(BiFun reducer) { + return fjp.invoke(ForkJoinTasks.reduceValues + (ConcurrentHashMapV8.this, reducer)); + } + + /** + * 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 reduceValues(Fun transformer, + BiFun reducer) { + return fjp.invoke(ForkJoinTasks.reduceValues + (ConcurrentHashMapV8.this, transformer, reducer)); + } + + /** + * 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 reduceValuesToDouble(ObjectToDouble transformer, + double basis, + DoubleByDoubleToDouble reducer) { + return fjp.invoke(ForkJoinTasks.reduceValuesToDouble + (ConcurrentHashMapV8.this, transformer, basis, reducer)); + } + + /** + * 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 reduceValuesToLong(ObjectToLong transformer, + long basis, + LongByLongToLong reducer) { + return fjp.invoke(ForkJoinTasks.reduceValuesToLong + (ConcurrentHashMapV8.this, transformer, basis, reducer)); + } + + /** + * 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 reduceValuesToInt(ObjectToInt transformer, + int basis, + IntByIntToInt reducer) { + return fjp.invoke(ForkJoinTasks.reduceValuesToInt + (ConcurrentHashMapV8.this, transformer, basis, reducer)); + } + + /** + * Performs the given action for each entry. + * + * @param action the action + */ + public void forEachEntry(Action> action) { + fjp.invoke(ForkJoinTasks.forEachEntry + (ConcurrentHashMapV8.this, action)); + } + + /** + * 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 forEachEntry(Fun, ? extends U> transformer, + Action action) { + fjp.invoke(ForkJoinTasks.forEachEntry + (ConcurrentHashMapV8.this, transformer, action)); + } + + /** + * 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. + * + * @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 searchEntries(Fun, ? extends U> searchFunction) { + return fjp.invoke(ForkJoinTasks.searchEntries + (ConcurrentHashMapV8.this, searchFunction)); + } + + /** + * 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 reduceEntries(BiFun, Map.Entry, ? extends Map.Entry> reducer) { + return fjp.invoke(ForkJoinTasks.reduceEntries + (ConcurrentHashMapV8.this, reducer)); + } + + /** + * 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 reduceEntries(Fun, ? extends U> transformer, + BiFun reducer) { + return fjp.invoke(ForkJoinTasks.reduceEntries + (ConcurrentHashMapV8.this, transformer, reducer)); + } + + /** + * 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 reduceEntriesToDouble(ObjectToDouble> transformer, + double basis, + DoubleByDoubleToDouble reducer) { + return fjp.invoke(ForkJoinTasks.reduceEntriesToDouble + (ConcurrentHashMapV8.this, transformer, basis, reducer)); + } + + /** + * 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 reduceEntriesToLong(ObjectToLong> transformer, + long basis, + LongByLongToLong reducer) { + return fjp.invoke(ForkJoinTasks.reduceEntriesToLong + (ConcurrentHashMapV8.this, transformer, basis, reducer)); + } + + /** + * 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 reduceEntriesToInt(ObjectToInt> transformer, + int basis, + IntByIntToInt reducer) { + return fjp.invoke(ForkJoinTasks.reduceEntriesToInt + (ConcurrentHashMapV8.this, transformer, basis, reducer)); + } + } + + // --------------------------------------------------------------------- + + /** + * Predefined tasks for performing bulk parallel operations on + * ConcurrentHashMaps. These tasks follow the forms and rules used + * in class {@link Parallel}. Each method has the same name, but + * returns a task rather than invoking it. These methods may be + * useful in custom applications such as submitting a task without + * waiting for completion, or combining with other tasks. + */ + public static class ForkJoinTasks { + private ForkJoinTasks() {} + + /** + * Returns a task that when invoked, performs the given + * action for each (key, value) + * + * @param map the map + * @param action the action + * @return the task + */ + public static ForkJoinTask forEach + (ConcurrentHashMapV8 map, + BiAction action) { + if (action == null) throw new NullPointerException(); + return new ForEachMappingTask(map, action); + } + + /** + * Returns a task that when invoked, performs the given + * action for each non-null transformation of each (key, 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). + * @param action the action + * @return the task + */ + public static ForkJoinTask forEach + (ConcurrentHashMapV8 map, + BiFun transformer, + Action action) { + if (transformer == null || action == null) + throw new NullPointerException(); + return new ForEachTransformedMappingTask + (map, 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. + * + * @param map the map + * @param searchFunction a function returning a non-null + * result on success, else null + * @return the task + */ + public static ForkJoinTask search + (ConcurrentHashMapV8 map, + BiFun searchFunction) { + if (searchFunction == null) throw new NullPointerException(); + return new SearchMappingsTask + (map, searchFunction, + new AtomicReference()); + } + + /** + * Returns a task that when invoked, returns the result of + * accumulating the given transformation of all (key, value) pairs + * using the given reducer to combine values, or null if none. + * + * @param map the map + * @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 task + */ + public static ForkJoinTask reduce + (ConcurrentHashMapV8 map, + BiFun transformer, + BiFun reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceMappingsTask + (map, transformer, reducer); + } + + /** + * Returns a task that when invoked, returns 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. + * + * @param map the map + * @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 task + */ + public static ForkJoinTask reduceToDouble + (ConcurrentHashMapV8 map, + ObjectByObjectToDouble transformer, + double basis, + DoubleByDoubleToDouble reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceMappingsToDoubleTask + (map, transformer, basis, reducer); + } + + /** + * Returns a task that when invoked, returns 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. + * + * @param map the map + * @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 task + */ + public static ForkJoinTask reduceToLong + (ConcurrentHashMapV8 map, + ObjectByObjectToLong transformer, + long basis, + LongByLongToLong reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceMappingsToLongTask + (map, transformer, basis, reducer); + } + + /** + * Returns a task that when invoked, returns 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. + * + * @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 task + */ + public static ForkJoinTask reduceToInt + (ConcurrentHashMapV8 map, + ObjectByObjectToInt transformer, + int basis, + IntByIntToInt reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceMappingsToIntTask + (map, transformer, basis, reducer); + } + + /** + * Returns a task that when invoked, performs the given action + * for each key. + * + * @param map the map + * @param action the action + * @return the task + */ + public static ForkJoinTask forEachKey + (ConcurrentHashMapV8 map, + Action action) { + if (action == null) throw new NullPointerException(); + return new ForEachKeyTask(map, action); + } + + /** + * Returns a task that when invoked, performs the given action + * 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). + * @param action the action + * @return the task + */ + public static ForkJoinTask forEachKey + (ConcurrentHashMapV8 map, + Fun transformer, + Action action) { + if (transformer == null || action == null) + throw new NullPointerException(); + return new ForEachTransformedKeyTask + (map, 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. + * + * @param map the map + * @param searchFunction a function returning a non-null + * result on success, else null + * @return the task + */ + public static ForkJoinTask searchKeys + (ConcurrentHashMapV8 map, + Fun searchFunction) { + if (searchFunction == null) throw new NullPointerException(); + return new SearchKeysTask + (map, searchFunction, + new AtomicReference()); + } + + /** + * Returns a task that when invoked, returns the result of + * accumulating all keys using the given reducer to combine + * values, or null if none. + * + * @param map the map + * @param reducer a commutative associative combining function + * @return the task + */ + public static ForkJoinTask reduceKeys + (ConcurrentHashMapV8 map, + BiFun reducer) { + if (reducer == null) throw new NullPointerException(); + return new ReduceKeysTask + (map, reducer); + } + /** + * Returns a task that when invoked, returns the result of + * accumulating the given transformation of all keys using the given + * reducer to combine values, or null if none. + * + * @param map the map + * @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 task + */ + public static ForkJoinTask reduceKeys + (ConcurrentHashMapV8 map, + Fun transformer, + BiFun reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceKeysTask + (map, transformer, reducer); + } + + /** + * Returns a task that when invoked, 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 map the map + * @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 task + */ + public static ForkJoinTask reduceKeysToDouble + (ConcurrentHashMapV8 map, + ObjectToDouble transformer, + double basis, + DoubleByDoubleToDouble reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceKeysToDoubleTask + (map, transformer, basis, reducer); + } + + /** + * Returns a task that when invoked, 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 map the map + * @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 task + */ + public static ForkJoinTask reduceKeysToLong + (ConcurrentHashMapV8 map, + ObjectToLong transformer, + long basis, + LongByLongToLong reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceKeysToLongTask + (map, transformer, basis, reducer); + } + + /** + * Returns a task that when invoked, 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 map the map + * @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 task + */ + public static ForkJoinTask reduceKeysToInt + (ConcurrentHashMapV8 map, + ObjectToInt transformer, + int basis, + IntByIntToInt reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceKeysToIntTask + (map, transformer, basis, reducer); + } + + /** + * Returns a task that when invoked, performs the given action + * for each value. + * + * @param map the map + * @param action the action + */ + public static ForkJoinTask forEachValue + (ConcurrentHashMapV8 map, + Action action) { + if (action == null) throw new NullPointerException(); + return new ForEachValueTask(map, action); + } + + /** + * Returns a task that when invoked, performs the given action + * 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). + * @param action the action + */ + public static ForkJoinTask forEachValue + (ConcurrentHashMapV8 map, + Fun transformer, + Action action) { + if (transformer == null || action == null) + throw new NullPointerException(); + return new ForEachTransformedValueTask + (map, 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. + * + * @param map the map + * @param searchFunction a function returning a non-null + * result on success, else null + * @return the task + * + */ + public static ForkJoinTask searchValues + (ConcurrentHashMapV8 map, + Fun searchFunction) { + if (searchFunction == null) throw new NullPointerException(); + return new SearchValuesTask + (map, searchFunction, + new AtomicReference()); + } + + /** + * Returns a task that when invoked, returns the result of + * accumulating all values using the given reducer to combine + * values, or null if none. + * + * @param map the map + * @param reducer a commutative associative combining function + * @return the task + */ + public static ForkJoinTask reduceValues + (ConcurrentHashMapV8 map, + BiFun reducer) { + if (reducer == null) throw new NullPointerException(); + return new ReduceValuesTask + (map, reducer); + } + + /** + * Returns a task that when invoked, returns the result of + * accumulating the given transformation of all values using the + * given reducer to combine values, or null if none. + * + * @param map the map + * @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 task + */ + public static ForkJoinTask reduceValues + (ConcurrentHashMapV8 map, + Fun transformer, + BiFun reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceValuesTask + (map, transformer, reducer); + } + + /** + * Returns a task that when invoked, 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 map the map + * @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 task + */ + public static ForkJoinTask reduceValuesToDouble + (ConcurrentHashMapV8 map, + ObjectToDouble transformer, + double basis, + DoubleByDoubleToDouble reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceValuesToDoubleTask + (map, transformer, basis, reducer); + } + + /** + * Returns a task that when invoked, 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 map the map + * @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 task + */ + public static ForkJoinTask reduceValuesToLong + (ConcurrentHashMapV8 map, + ObjectToLong transformer, + long basis, + LongByLongToLong reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceValuesToLongTask + (map, transformer, basis, reducer); + } + + /** + * Returns a task that when invoked, 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 map the map + * @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 task + */ + public static ForkJoinTask reduceValuesToInt + (ConcurrentHashMapV8 map, + ObjectToInt transformer, + int basis, + IntByIntToInt reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceValuesToIntTask + (map, transformer, basis, reducer); + } + + /** + * Returns a task that when invoked, perform the given action + * for each entry. + * + * @param map the map + * @param action the action + */ + public static ForkJoinTask forEachEntry + (ConcurrentHashMapV8 map, + Action> action) { + if (action == null) throw new NullPointerException(); + return new ForEachEntryTask(map, action); + } + + /** + * Returns a task that when invoked, perform the given action + * 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). + * @param action the action + */ + public static ForkJoinTask forEachEntry + (ConcurrentHashMapV8 map, + Fun, ? extends U> transformer, + Action action) { + if (transformer == null || action == null) + throw new NullPointerException(); + return new ForEachTransformedEntryTask + (map, 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. + * + * @param map the map + * @param searchFunction a function returning a non-null + * result on success, else null + * @return the task + * + */ + public static ForkJoinTask searchEntries + (ConcurrentHashMapV8 map, + Fun, ? extends U> searchFunction) { + if (searchFunction == null) throw new NullPointerException(); + return new SearchEntriesTask + (map, searchFunction, + new AtomicReference()); + } + + /** + * Returns a task that when invoked, returns the result of + * accumulating all entries using the given reducer to combine + * values, or null if none. + * + * @param map the map + * @param reducer a commutative associative combining function + * @return the task + */ + public static ForkJoinTask> reduceEntries + (ConcurrentHashMapV8 map, + BiFun, Map.Entry, ? extends Map.Entry> reducer) { + if (reducer == null) throw new NullPointerException(); + return new ReduceEntriesTask + (map, reducer); + } + + /** + * Returns a task that when invoked, returns the result of + * accumulating the given transformation of all entries using the + * given reducer to combine values, or null if none. + * + * @param map the map + * @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 task + */ + public static ForkJoinTask reduceEntries + (ConcurrentHashMapV8 map, + Fun, ? extends U> transformer, + BiFun reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceEntriesTask + (map, transformer, reducer); + } + + /** + * Returns a task that when invoked, 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 map the map + * @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 task + */ + public static ForkJoinTask reduceEntriesToDouble + (ConcurrentHashMapV8 map, + ObjectToDouble> transformer, + double basis, + DoubleByDoubleToDouble reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceEntriesToDoubleTask + (map, transformer, basis, reducer); + } + + /** + * Returns a task that when invoked, 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 map the map + * @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 task + */ + public static ForkJoinTask reduceEntriesToLong + (ConcurrentHashMapV8 map, + ObjectToLong> transformer, + long basis, + LongByLongToLong reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceEntriesToLongTask + (map, transformer, basis, reducer); + } + + /** + * Returns a task that when invoked, 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 map the map + * @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 task + */ + public static ForkJoinTask reduceEntriesToInt + (ConcurrentHashMapV8 map, + ObjectToInt> transformer, + int basis, + IntByIntToInt reducer) { + if (transformer == null || reducer == null) + throw new NullPointerException(); + return new MapReduceEntriesToIntTask + (map, transformer, basis, reducer); + } + } + + // ------------------------------------------------------- + + /** + * 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. + */ + static abstract class BulkTask extends Traverser { + final BulkTask parent; // completion target + int batch; // split control + int pending; // completion control + + /** Constructor for root tasks */ + BulkTask(ConcurrentHashMapV8 map) { + 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; + } + + // FJ methods + + /** + * Propagates completion. Note that all reduce actions + * bypass this method to combine while completing. + */ + final void tryComplete() { + BulkTask a = this, s = a; + for (int c;;) { + if ((c = a.pending) == 0) { + if ((a = (s = a).parent) == null) { + s.quietlyComplete(); + break; + } + } + else if (U.compareAndSwapInt(a, PENDING, c, c - 1)) + break; + } + } + + /** + * Forces root task to throw exception unless already complete. + */ + final void tryAbortComputation(Throwable ex) { + for (BulkTask a = this;;) { + BulkTask p = a.parent; + if (p == null) { + a.completeExceptionally(ex); + break; + } + a = p; + } + } + + public final boolean exec() { + try { + compute(); + } + catch (Throwable ex) { + tryAbortComputation(ex); + } + return false; + } + + public abstract void compute(); + + // 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() { + 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; + } + return b; + } + + /** + * Error message for hoisted null checks of functions + */ + static final String NullFunctionMessage = + "Unexpected null function"; + + /** + * 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 = sun.misc.Unsafe.getUnsafe(); + PENDING = U.objectFieldOffset + (BulkTask.class.getDeclaredField("pending")); + } catch (Exception e) { + throw new Error(e); + } + } + } + + /* + * Task classes. Coded in a regular but ugly format/style to + * simplify checks that each variant differs in the right way from + * others. + */ + + 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, + Action action) { + super(p, b, split); + this.action = action; + } + public final void compute() { + 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(); + } + while (advance() != null) + action.apply((K)nextKey); + tryComplete(); + } + } + + 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, + Action action) { + super(p, b, split); + this.action = action; + } + public final void compute() { + 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(); + } + Object v; + while ((v = advance()) != null) + action.apply((V)v); + tryComplete(); + } + } + + static final class ForEachEntryTask + extends BulkTask { + final Action> action; + ForEachEntryTask + (ConcurrentHashMapV8 m, + Action> action) { + super(m); + this.action = action; + } + ForEachEntryTask + (BulkTask p, int b, boolean split, + Action> action) { + super(p, b, split); + this.action = action; + } + public final void compute() { + 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 ForEachEntryTask(this, b >>>= 1, true, action).fork(); + } + Object v; + while ((v = advance()) != null) + action.apply(entryFor((K)nextKey, (V)v)); + tryComplete(); + } + } + + static final class ForEachMappingTask + extends BulkTask { + final BiAction action; + ForEachMappingTask + (ConcurrentHashMapV8 m, + BiAction action) { + super(m); + this.action = action; + } + ForEachMappingTask + (BulkTask p, int b, boolean split, + BiAction action) { + super(p, b, split); + this.action = action; + } + + public final void compute() { + final BiAction 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 ForEachMappingTask(this, b >>>= 1, true, + action).fork(); + } + Object v; + while ((v = advance()) != null) + action.apply((K)nextKey, (V)v); + tryComplete(); + } + } + + static final class ForEachTransformedKeyTask + extends BulkTask { + final Fun transformer; + final Action action; + ForEachTransformedKeyTask + (ConcurrentHashMapV8 m, + Fun transformer, + Action action) { + super(m); + this.transformer = transformer; + this.action = action; + + } + ForEachTransformedKeyTask + (BulkTask p, int b, boolean split, + Fun transformer, + Action action) { + super(p, b, split); + this.transformer = transformer; + this.action = action; + } + public final void compute() { + final Fun transformer = + this.transformer; + final Action action = this.action; + if (transformer == null || action == null) + throw new Error(NullFunctionMessage); + int b = batch(), c; + while (b > 1 && baseIndex != baseLimit) { + do {} while (!casPending(c = pending, c+1)); + new ForEachTransformedKeyTask + (this, b >>>= 1, true, transformer, action).fork(); + } + U u; + while (advance() != null) { + if ((u = transformer.apply((K)nextKey)) != null) + action.apply(u); + } + tryComplete(); + } + } + + static final class ForEachTransformedValueTask + extends BulkTask { + final Fun transformer; + final Action action; + ForEachTransformedValueTask + (ConcurrentHashMapV8 m, + Fun transformer, + Action action) { + super(m); + this.transformer = transformer; + this.action = action; + + } + ForEachTransformedValueTask + (BulkTask p, int b, boolean split, + Fun transformer, + Action action) { + super(p, b, split); + this.transformer = transformer; + this.action = action; + } + public final void compute() { + final Fun transformer = + this.transformer; + final Action action = this.action; + if (transformer == null || action == null) + throw new Error(NullFunctionMessage); + int b = batch(), c; + while (b > 1 && baseIndex != baseLimit) { + do {} while (!casPending(c = pending, c+1)); + new ForEachTransformedValueTask + (this, b >>>= 1, true, transformer, action).fork(); + } + Object v; U u; + while ((v = advance()) != null) { + if ((u = transformer.apply((V)v)) != null) + action.apply(u); + } + tryComplete(); + } + } + + static final class ForEachTransformedEntryTask + extends BulkTask { + final Fun, ? extends U> transformer; + final Action action; + ForEachTransformedEntryTask + (ConcurrentHashMapV8 m, + Fun, ? extends U> transformer, + Action action) { + super(m); + this.transformer = transformer; + this.action = action; + + } + ForEachTransformedEntryTask + (BulkTask p, int b, boolean split, + Fun, ? extends U> transformer, + Action action) { + super(p, b, split); + this.transformer = transformer; + this.action = action; + } + public final void compute() { + final Fun, ? extends U> transformer = + this.transformer; + final Action action = this.action; + if (transformer == null || action == null) + throw new Error(NullFunctionMessage); + int b = batch(), c; + while (b > 1 && baseIndex != baseLimit) { + do {} while (!casPending(c = pending, c+1)); + new ForEachTransformedEntryTask + (this, b >>>= 1, true, transformer, action).fork(); + } + Object v; U u; + while ((v = advance()) != null) { + if ((u = transformer.apply(entryFor((K)nextKey, (V)v))) != null) + action.apply(u); + } + tryComplete(); + } + } + + static final class ForEachTransformedMappingTask + extends BulkTask { + final BiFun transformer; + final Action action; + ForEachTransformedMappingTask + (ConcurrentHashMapV8 m, + BiFun transformer, + Action action) { + super(m); + this.transformer = transformer; + this.action = action; + + } + ForEachTransformedMappingTask + (BulkTask p, int b, boolean split, + BiFun transformer, + Action action) { + super(p, b, split); + this.transformer = transformer; + this.action = action; + } + public final void compute() { + final BiFun transformer = + this.transformer; + final Action action = this.action; + if (transformer == null || action == null) + throw new Error(NullFunctionMessage); + int b = batch(), c; + while (b > 1 && baseIndex != baseLimit) { + do {} while (!casPending(c = pending, c+1)); + new ForEachTransformedMappingTask + (this, b >>>= 1, true, transformer, action).fork(); + } + Object v; U u; + while ((v = advance()) != null) { + if ((u = transformer.apply((K)nextKey, (V)v)) != null) + action.apply(u); + } + tryComplete(); + } + } + + static final class SearchKeysTask + extends BulkTask { + final Fun searchFunction; + final AtomicReference result; + SearchKeysTask + (ConcurrentHashMapV8 m, + Fun searchFunction, + AtomicReference result) { + super(m); + this.searchFunction = searchFunction; this.result = result; + } + SearchKeysTask + (BulkTask p, int b, boolean split, + Fun searchFunction, + AtomicReference result) { + super(p, b, split); + this.searchFunction = searchFunction; this.result = result; + } + public final void compute() { + AtomicReference result = this.result; + final Fun searchFunction = + this.searchFunction; + if (searchFunction == null || result == null) + throw new Error(NullFunctionMessage); + int b = batch(), c; + while (b > 1 && baseIndex != baseLimit && result.get() == null) { + do {} while (!casPending(c = pending, c+1)); + new SearchKeysTask(this, b >>>= 1, true, + searchFunction, result).fork(); + } + U u; + while (result.get() == null && advance() != null) { + if ((u = searchFunction.apply((K)nextKey)) != null) { + result.compareAndSet(null, u); + break; + } + } + tryComplete(); + } + public final U getRawResult() { return result.get(); } + } + static final class SearchValuesTask + extends BulkTask { + final Fun searchFunction; + final AtomicReference result; + SearchValuesTask + (ConcurrentHashMapV8 m, + Fun searchFunction, + AtomicReference result) { + super(m); + this.searchFunction = searchFunction; this.result = result; + } + SearchValuesTask + (BulkTask p, int b, boolean split, + Fun searchFunction, + AtomicReference result) { + super(p, b, split); + this.searchFunction = searchFunction; this.result = result; + } + public final void compute() { + AtomicReference result = this.result; + final Fun searchFunction = + this.searchFunction; + if (searchFunction == null || result == null) + throw new Error(NullFunctionMessage); + int b = batch(), c; + while (b > 1 && baseIndex != baseLimit && result.get() == null) { + do {} while (!casPending(c = pending, c+1)); + new SearchValuesTask(this, b >>>= 1, true, + searchFunction, result).fork(); + } + Object v; U u; + while (result.get() == null && (v = advance()) != null) { + if ((u = searchFunction.apply((V)v)) != null) { + result.compareAndSet(null, u); + break; + } + } + tryComplete(); } + public final U getRawResult() { return result.get(); } } + static final class SearchEntriesTask + extends BulkTask { + final Fun, ? extends U> searchFunction; + final AtomicReference result; + SearchEntriesTask + (ConcurrentHashMapV8 m, + Fun, ? extends U> searchFunction, + AtomicReference result) { + super(m); + this.searchFunction = searchFunction; this.result = result; + } + SearchEntriesTask + (BulkTask p, int b, boolean split, + Fun, ? extends U> searchFunction, + AtomicReference result) { + super(p, b, split); + this.searchFunction = searchFunction; this.result = result; + } + public final void compute() { + AtomicReference result = this.result; + final Fun, ? extends U> searchFunction = + this.searchFunction; + if (searchFunction == null || result == null) + throw new Error(NullFunctionMessage); + int b = batch(), c; + while (b > 1 && baseIndex != baseLimit && result.get() == null) { + do {} while (!casPending(c = pending, c+1)); + new SearchEntriesTask(this, b >>>= 1, true, + searchFunction, result).fork(); + } + Object v; U u; + while (result.get() == null && (v = advance()) != null) { + if ((u = searchFunction.apply(entryFor((K)nextKey, (V)v))) != null) { + result.compareAndSet(null, u); + break; + } + } + tryComplete(); + } + public final U getRawResult() { return result.get(); } + } + + static final class SearchMappingsTask + extends BulkTask { + final BiFun searchFunction; + final AtomicReference result; + SearchMappingsTask + (ConcurrentHashMapV8 m, + BiFun searchFunction, + AtomicReference result) { + super(m); + this.searchFunction = searchFunction; this.result = result; + } + SearchMappingsTask + (BulkTask p, int b, boolean split, + BiFun searchFunction, + AtomicReference result) { + super(p, b, split); + this.searchFunction = searchFunction; this.result = result; + } + public final void compute() { + AtomicReference result = this.result; + final BiFun searchFunction = + this.searchFunction; + if (searchFunction == null || result == null) + throw new Error(NullFunctionMessage); + int b = batch(), c; + while (b > 1 && baseIndex != baseLimit && result.get() == null) { + do {} while (!casPending(c = pending, c+1)); + new SearchMappingsTask(this, b >>>= 1, true, + searchFunction, result).fork(); + } + Object v; U u; + while (result.get() == null && (v = advance()) != null) { + if ((u = searchFunction.apply((K)nextKey, (V)v)) != null) { + result.compareAndSet(null, u); + break; + } + } + tryComplete(); + } + public final U getRawResult() { return result.get(); } + } + + static final class ReduceKeysTask + extends BulkTask { + final BiFun reducer; + K result; + ReduceKeysTask sibling; + ReduceKeysTask + (ConcurrentHashMapV8 m, + BiFun reducer) { + super(m); + this.reducer = reducer; + } + ReduceKeysTask + (BulkTask p, int b, boolean split, + BiFun reducer) { + super(p, b, split); + this.reducer = reducer; + } + + public final void compute() { + ReduceKeysTask t = this; + final BiFun reducer = + this.reducer; + if (reducer == null) + throw new Error(NullFunctionMessage); + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + ReduceKeysTask rt = + new ReduceKeysTask + (t, b, true, reducer); + t = new ReduceKeysTask + (t, b, false, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + K r = null; + while (t.advance() != null) { + K u = (K)t.nextKey; + r = (r == null) ? u : reducer.apply(r, u); + } + t.result = r; + for (;;) { + int c; BulkTask par; ReduceKeysTask s, p; K u; + if ((par = t.parent) == null || + !(par instanceof ReduceKeysTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (ReduceKeysTask)par).pending) == 0) { + if ((s = t.sibling) != null && (u = s.result) != null) + r = (r == null) ? u : reducer.apply(r, u); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final K getRawResult() { return result; } + } + + static final class ReduceValuesTask + extends BulkTask { + final BiFun reducer; + V result; + ReduceValuesTask sibling; + ReduceValuesTask + (ConcurrentHashMapV8 m, + BiFun reducer) { + super(m); + this.reducer = reducer; + } + ReduceValuesTask + (BulkTask p, int b, boolean split, + BiFun reducer) { + super(p, b, split); + this.reducer = reducer; + } + + public final void compute() { + ReduceValuesTask t = this; + final BiFun reducer = + this.reducer; + if (reducer == null) + throw new Error(NullFunctionMessage); + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + ReduceValuesTask rt = + new ReduceValuesTask + (t, b, true, reducer); + t = new ReduceValuesTask + (t, b, false, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + V r = null; + Object v; + while ((v = t.advance()) != null) { + V u = (V)v; + r = (r == null) ? u : reducer.apply(r, u); + } + t.result = r; + for (;;) { + int c; BulkTask par; ReduceValuesTask s, p; V u; + if ((par = t.parent) == null || + !(par instanceof ReduceValuesTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (ReduceValuesTask)par).pending) == 0) { + if ((s = t.sibling) != null && (u = s.result) != null) + r = (r == null) ? u : reducer.apply(r, u); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final V getRawResult() { return result; } + } + + static final class ReduceEntriesTask + extends BulkTask> { + final BiFun, Map.Entry, ? extends Map.Entry> reducer; + Map.Entry result; + ReduceEntriesTask sibling; + ReduceEntriesTask + (ConcurrentHashMapV8 m, + BiFun, Map.Entry, ? extends Map.Entry> reducer) { + super(m); + this.reducer = reducer; + } + ReduceEntriesTask + (BulkTask p, int b, boolean split, + BiFun, Map.Entry, ? extends Map.Entry> reducer) { + super(p, b, split); + this.reducer = reducer; + } + + public final void compute() { + ReduceEntriesTask t = this; + final BiFun, Map.Entry, ? extends Map.Entry> reducer = + this.reducer; + if (reducer == null) + throw new Error(NullFunctionMessage); + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + ReduceEntriesTask rt = + new ReduceEntriesTask + (t, b, true, reducer); + t = new ReduceEntriesTask + (t, b, false, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + Map.Entry r = null; + Object v; + while ((v = t.advance()) != null) { + Map.Entry u = entryFor((K)t.nextKey, (V)v); + r = (r == null) ? u : reducer.apply(r, u); + } + t.result = r; + for (;;) { + int c; BulkTask par; ReduceEntriesTask s, p; + Map.Entry u; + if ((par = t.parent) == null || + !(par instanceof ReduceEntriesTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (ReduceEntriesTask)par).pending) == 0) { + if ((s = t.sibling) != null && (u = s.result) != null) + r = (r == null) ? u : reducer.apply(r, u); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final Map.Entry getRawResult() { return result; } + } + + static final class MapReduceKeysTask + extends BulkTask { + final Fun transformer; + final BiFun reducer; + U result; + MapReduceKeysTask sibling; + MapReduceKeysTask + (ConcurrentHashMapV8 m, + Fun transformer, + BiFun reducer) { + super(m); + this.transformer = transformer; + this.reducer = reducer; + } + MapReduceKeysTask + (BulkTask p, int b, boolean split, + Fun transformer, + BiFun reducer) { + super(p, b, split); + this.transformer = transformer; + this.reducer = reducer; + } + public final void compute() { + MapReduceKeysTask t = this; + final Fun transformer = + this.transformer; + final BiFun reducer = + this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceKeysTask rt = + new MapReduceKeysTask + (t, b, true, transformer, reducer); + t = new MapReduceKeysTask + (t, b, false, transformer, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + U r = null, u; + while (t.advance() != null) { + if ((u = transformer.apply((K)t.nextKey)) != null) + r = (r == null) ? u : reducer.apply(r, u); + } + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceKeysTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceKeysTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceKeysTask)par).pending) == 0) { + if ((s = t.sibling) != null && (u = s.result) != null) + r = (r == null) ? u : reducer.apply(r, u); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final U getRawResult() { return result; } + } + + static final class MapReduceValuesTask + extends BulkTask { + final Fun transformer; + final BiFun reducer; + U result; + MapReduceValuesTask sibling; + MapReduceValuesTask + (ConcurrentHashMapV8 m, + Fun transformer, + BiFun reducer) { + super(m); + this.transformer = transformer; + this.reducer = reducer; + } + MapReduceValuesTask + (BulkTask p, int b, boolean split, + Fun transformer, + BiFun reducer) { + super(p, b, split); + this.transformer = transformer; + this.reducer = reducer; + } + public final void compute() { + MapReduceValuesTask t = this; + final Fun transformer = + this.transformer; + final BiFun reducer = + this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceValuesTask rt = + new MapReduceValuesTask + (t, b, true, transformer, reducer); + t = new MapReduceValuesTask + (t, b, false, transformer, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + U r = null, u; + Object v; + while ((v = t.advance()) != null) { + if ((u = transformer.apply((V)v)) != null) + r = (r == null) ? u : reducer.apply(r, u); + } + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceValuesTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceValuesTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceValuesTask)par).pending) == 0) { + if ((s = t.sibling) != null && (u = s.result) != null) + r = (r == null) ? u : reducer.apply(r, u); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final U getRawResult() { return result; } + } + + static final class MapReduceEntriesTask + extends BulkTask { + final Fun, ? extends U> transformer; + final BiFun reducer; + U result; + MapReduceEntriesTask sibling; + MapReduceEntriesTask + (ConcurrentHashMapV8 m, + Fun, ? extends U> transformer, + BiFun reducer) { + super(m); + this.transformer = transformer; + this.reducer = reducer; + } + MapReduceEntriesTask + (BulkTask p, int b, boolean split, + Fun, ? extends U> transformer, + BiFun reducer) { + super(p, b, split); + this.transformer = transformer; + this.reducer = reducer; + } + public final void compute() { + MapReduceEntriesTask t = this; + final Fun, ? extends U> transformer = + this.transformer; + final BiFun reducer = + this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceEntriesTask rt = + new MapReduceEntriesTask + (t, b, true, transformer, reducer); + t = new MapReduceEntriesTask + (t, b, false, transformer, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + U r = null, u; + Object v; + while ((v = t.advance()) != null) { + if ((u = transformer.apply(entryFor((K)t.nextKey, (V)v))) != null) + r = (r == null) ? u : reducer.apply(r, u); + } + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceEntriesTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceEntriesTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceEntriesTask)par).pending) == 0) { + if ((s = t.sibling) != null && (u = s.result) != null) + r = (r == null) ? u : reducer.apply(r, u); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final U getRawResult() { return result; } + } + + static final class MapReduceMappingsTask + extends BulkTask { + final BiFun transformer; + final BiFun reducer; + U result; + MapReduceMappingsTask sibling; + MapReduceMappingsTask + (ConcurrentHashMapV8 m, + BiFun transformer, + BiFun reducer) { + super(m); + this.transformer = transformer; + this.reducer = reducer; + } + MapReduceMappingsTask + (BulkTask p, int b, boolean split, + BiFun transformer, + BiFun reducer) { + super(p, b, split); + this.transformer = transformer; + this.reducer = reducer; + } + public final void compute() { + MapReduceMappingsTask t = this; + final BiFun transformer = + this.transformer; + final BiFun reducer = + this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceMappingsTask rt = + new MapReduceMappingsTask + (t, b, true, transformer, reducer); + t = new MapReduceMappingsTask + (t, b, false, transformer, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + U r = null, u; + Object v; + while ((v = t.advance()) != null) { + if ((u = transformer.apply((K)t.nextKey, (V)v)) != null) + r = (r == null) ? u : reducer.apply(r, u); + } + for (;;) { + int c; BulkTask par; MapReduceMappingsTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceMappingsTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceMappingsTask)par).pending) == 0) { + if ((s = t.sibling) != null && (u = s.result) != null) + r = (r == null) ? u : reducer.apply(r, u); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final U getRawResult() { return result; } + } + + static final class MapReduceKeysToDoubleTask + extends BulkTask { + final ObjectToDouble transformer; + final DoubleByDoubleToDouble reducer; + final double basis; + double result; + MapReduceKeysToDoubleTask sibling; + MapReduceKeysToDoubleTask + (ConcurrentHashMapV8 m, + ObjectToDouble transformer, + double basis, + DoubleByDoubleToDouble reducer) { + super(m); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + MapReduceKeysToDoubleTask + (BulkTask p, int b, boolean split, + ObjectToDouble transformer, + double basis, + DoubleByDoubleToDouble reducer) { + super(p, b, split); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + public final void compute() { + MapReduceKeysToDoubleTask t = this; + final ObjectToDouble transformer = + this.transformer; + final DoubleByDoubleToDouble reducer = this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + final double id = this.basis; + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceKeysToDoubleTask rt = + new MapReduceKeysToDoubleTask + (t, b, true, transformer, id, reducer); + t = new MapReduceKeysToDoubleTask + (t, b, false, transformer, id, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + double r = id; + while (t.advance() != null) + r = reducer.apply(r, transformer.apply((K)t.nextKey)); + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceKeysToDoubleTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceKeysToDoubleTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceKeysToDoubleTask)par).pending) == 0) { + if ((s = t.sibling) != null) + r = reducer.apply(r, s.result); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final Double getRawResult() { return result; } + } + + static final class MapReduceValuesToDoubleTask + extends BulkTask { + final ObjectToDouble transformer; + final DoubleByDoubleToDouble reducer; + final double basis; + double result; + MapReduceValuesToDoubleTask sibling; + MapReduceValuesToDoubleTask + (ConcurrentHashMapV8 m, + ObjectToDouble transformer, + double basis, + DoubleByDoubleToDouble reducer) { + super(m); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + MapReduceValuesToDoubleTask + (BulkTask p, int b, boolean split, + ObjectToDouble transformer, + double basis, + DoubleByDoubleToDouble reducer) { + super(p, b, split); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + public final void compute() { + MapReduceValuesToDoubleTask t = this; + final ObjectToDouble transformer = + this.transformer; + final DoubleByDoubleToDouble reducer = this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + final double id = this.basis; + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceValuesToDoubleTask rt = + new MapReduceValuesToDoubleTask + (t, b, true, transformer, id, reducer); + t = new MapReduceValuesToDoubleTask + (t, b, false, transformer, id, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + double r = id; + Object v; + while ((v = t.advance()) != null) + r = reducer.apply(r, transformer.apply((V)v)); + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceValuesToDoubleTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceValuesToDoubleTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceValuesToDoubleTask)par).pending) == 0) { + if ((s = t.sibling) != null) + r = reducer.apply(r, s.result); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final Double getRawResult() { return result; } + } + + static final class MapReduceEntriesToDoubleTask + extends BulkTask { + final ObjectToDouble> transformer; + final DoubleByDoubleToDouble reducer; + final double basis; + double result; + MapReduceEntriesToDoubleTask sibling; + MapReduceEntriesToDoubleTask + (ConcurrentHashMapV8 m, + ObjectToDouble> transformer, + double basis, + DoubleByDoubleToDouble reducer) { + super(m); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + MapReduceEntriesToDoubleTask + (BulkTask p, int b, boolean split, + ObjectToDouble> transformer, + double basis, + DoubleByDoubleToDouble reducer) { + super(p, b, split); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + public final void compute() { + MapReduceEntriesToDoubleTask t = this; + final ObjectToDouble> transformer = + this.transformer; + final DoubleByDoubleToDouble reducer = this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + final double id = this.basis; + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceEntriesToDoubleTask rt = + new MapReduceEntriesToDoubleTask + (t, b, true, transformer, id, reducer); + t = new MapReduceEntriesToDoubleTask + (t, b, false, transformer, id, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + double r = id; + Object v; + while ((v = t.advance()) != null) + r = reducer.apply(r, transformer.apply(entryFor((K)t.nextKey, (V)v))); + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceEntriesToDoubleTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceEntriesToDoubleTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceEntriesToDoubleTask)par).pending) == 0) { + if ((s = t.sibling) != null) + r = reducer.apply(r, s.result); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final Double getRawResult() { return result; } + } + + static final class MapReduceMappingsToDoubleTask + extends BulkTask { + final ObjectByObjectToDouble transformer; + final DoubleByDoubleToDouble reducer; + final double basis; + double result; + MapReduceMappingsToDoubleTask sibling; + MapReduceMappingsToDoubleTask + (ConcurrentHashMapV8 m, + ObjectByObjectToDouble transformer, + double basis, + DoubleByDoubleToDouble reducer) { + super(m); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + MapReduceMappingsToDoubleTask + (BulkTask p, int b, boolean split, + ObjectByObjectToDouble transformer, + double basis, + DoubleByDoubleToDouble reducer) { + super(p, b, split); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + public final void compute() { + MapReduceMappingsToDoubleTask t = this; + final ObjectByObjectToDouble transformer = + this.transformer; + final DoubleByDoubleToDouble reducer = this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + final double id = this.basis; + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceMappingsToDoubleTask rt = + new MapReduceMappingsToDoubleTask + (t, b, true, transformer, id, reducer); + t = new MapReduceMappingsToDoubleTask + (t, b, false, transformer, id, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + double r = id; + Object v; + while ((v = t.advance()) != null) + r = reducer.apply(r, transformer.apply((K)t.nextKey, (V)v)); + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceMappingsToDoubleTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceMappingsToDoubleTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceMappingsToDoubleTask)par).pending) == 0) { + if ((s = t.sibling) != null) + r = reducer.apply(r, s.result); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final Double getRawResult() { return result; } + } + + static final class MapReduceKeysToLongTask + extends BulkTask { + final ObjectToLong transformer; + final LongByLongToLong reducer; + final long basis; + long result; + MapReduceKeysToLongTask sibling; + MapReduceKeysToLongTask + (ConcurrentHashMapV8 m, + ObjectToLong transformer, + long basis, + LongByLongToLong reducer) { + super(m); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + MapReduceKeysToLongTask + (BulkTask p, int b, boolean split, + ObjectToLong transformer, + long basis, + LongByLongToLong reducer) { + super(p, b, split); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + public final void compute() { + MapReduceKeysToLongTask t = this; + final ObjectToLong transformer = + this.transformer; + final LongByLongToLong reducer = this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + final long id = this.basis; + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceKeysToLongTask rt = + new MapReduceKeysToLongTask + (t, b, true, transformer, id, reducer); + t = new MapReduceKeysToLongTask + (t, b, false, transformer, id, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + long r = id; + while (t.advance() != null) + r = reducer.apply(r, transformer.apply((K)t.nextKey)); + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceKeysToLongTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceKeysToLongTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceKeysToLongTask)par).pending) == 0) { + if ((s = t.sibling) != null) + r = reducer.apply(r, s.result); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final Long getRawResult() { return result; } + } + + static final class MapReduceValuesToLongTask + extends BulkTask { + final ObjectToLong transformer; + final LongByLongToLong reducer; + final long basis; + long result; + MapReduceValuesToLongTask sibling; + MapReduceValuesToLongTask + (ConcurrentHashMapV8 m, + ObjectToLong transformer, + long basis, + LongByLongToLong reducer) { + super(m); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + MapReduceValuesToLongTask + (BulkTask p, int b, boolean split, + ObjectToLong transformer, + long basis, + LongByLongToLong reducer) { + super(p, b, split); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + public final void compute() { + MapReduceValuesToLongTask t = this; + final ObjectToLong transformer = + this.transformer; + final LongByLongToLong reducer = this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + final long id = this.basis; + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceValuesToLongTask rt = + new MapReduceValuesToLongTask + (t, b, true, transformer, id, reducer); + t = new MapReduceValuesToLongTask + (t, b, false, transformer, id, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + long r = id; + Object v; + while ((v = t.advance()) != null) + r = reducer.apply(r, transformer.apply((V)v)); + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceValuesToLongTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceValuesToLongTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceValuesToLongTask)par).pending) == 0) { + if ((s = t.sibling) != null) + r = reducer.apply(r, s.result); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final Long getRawResult() { return result; } + } + + static final class MapReduceEntriesToLongTask + extends BulkTask { + final ObjectToLong> transformer; + final LongByLongToLong reducer; + final long basis; + long result; + MapReduceEntriesToLongTask sibling; + MapReduceEntriesToLongTask + (ConcurrentHashMapV8 m, + ObjectToLong> transformer, + long basis, + LongByLongToLong reducer) { + super(m); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + MapReduceEntriesToLongTask + (BulkTask p, int b, boolean split, + ObjectToLong> transformer, + long basis, + LongByLongToLong reducer) { + super(p, b, split); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + public final void compute() { + MapReduceEntriesToLongTask t = this; + final ObjectToLong> transformer = + this.transformer; + final LongByLongToLong reducer = this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + final long id = this.basis; + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceEntriesToLongTask rt = + new MapReduceEntriesToLongTask + (t, b, true, transformer, id, reducer); + t = new MapReduceEntriesToLongTask + (t, b, false, transformer, id, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + long r = id; + Object v; + while ((v = t.advance()) != null) + r = reducer.apply(r, transformer.apply(entryFor((K)t.nextKey, (V)v))); + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceEntriesToLongTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceEntriesToLongTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceEntriesToLongTask)par).pending) == 0) { + if ((s = t.sibling) != null) + r = reducer.apply(r, s.result); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final Long getRawResult() { return result; } + } + + static final class MapReduceMappingsToLongTask + extends BulkTask { + final ObjectByObjectToLong transformer; + final LongByLongToLong reducer; + final long basis; + long result; + MapReduceMappingsToLongTask sibling; + MapReduceMappingsToLongTask + (ConcurrentHashMapV8 m, + ObjectByObjectToLong transformer, + long basis, + LongByLongToLong reducer) { + super(m); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + MapReduceMappingsToLongTask + (BulkTask p, int b, boolean split, + ObjectByObjectToLong transformer, + long basis, + LongByLongToLong reducer) { + super(p, b, split); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + public final void compute() { + MapReduceMappingsToLongTask t = this; + final ObjectByObjectToLong transformer = + this.transformer; + final LongByLongToLong reducer = this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + final long id = this.basis; + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceMappingsToLongTask rt = + new MapReduceMappingsToLongTask + (t, b, true, transformer, id, reducer); + t = new MapReduceMappingsToLongTask + (t, b, false, transformer, id, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + long r = id; + Object v; + while ((v = t.advance()) != null) + r = reducer.apply(r, transformer.apply((K)t.nextKey, (V)v)); + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceMappingsToLongTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceMappingsToLongTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceMappingsToLongTask)par).pending) == 0) { + if ((s = t.sibling) != null) + r = reducer.apply(r, s.result); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final Long getRawResult() { return result; } + } + + static final class MapReduceKeysToIntTask + extends BulkTask { + final ObjectToInt transformer; + final IntByIntToInt reducer; + final int basis; + int result; + MapReduceKeysToIntTask sibling; + MapReduceKeysToIntTask + (ConcurrentHashMapV8 m, + ObjectToInt transformer, + int basis, + IntByIntToInt reducer) { + super(m); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + MapReduceKeysToIntTask + (BulkTask p, int b, boolean split, + ObjectToInt transformer, + int basis, + IntByIntToInt reducer) { + super(p, b, split); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + public final void compute() { + MapReduceKeysToIntTask t = this; + final ObjectToInt transformer = + this.transformer; + final IntByIntToInt reducer = this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + final int id = this.basis; + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceKeysToIntTask rt = + new MapReduceKeysToIntTask + (t, b, true, transformer, id, reducer); + t = new MapReduceKeysToIntTask + (t, b, false, transformer, id, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + int r = id; + while (t.advance() != null) + r = reducer.apply(r, transformer.apply((K)t.nextKey)); + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceKeysToIntTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceKeysToIntTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceKeysToIntTask)par).pending) == 0) { + if ((s = t.sibling) != null) + r = reducer.apply(r, s.result); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final Integer getRawResult() { return result; } + } + + static final class MapReduceValuesToIntTask + extends BulkTask { + final ObjectToInt transformer; + final IntByIntToInt reducer; + final int basis; + int result; + MapReduceValuesToIntTask sibling; + MapReduceValuesToIntTask + (ConcurrentHashMapV8 m, + ObjectToInt transformer, + int basis, + IntByIntToInt reducer) { + super(m); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + MapReduceValuesToIntTask + (BulkTask p, int b, boolean split, + ObjectToInt transformer, + int basis, + IntByIntToInt reducer) { + super(p, b, split); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + public final void compute() { + MapReduceValuesToIntTask t = this; + final ObjectToInt transformer = + this.transformer; + final IntByIntToInt reducer = this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + final int id = this.basis; + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceValuesToIntTask rt = + new MapReduceValuesToIntTask + (t, b, true, transformer, id, reducer); + t = new MapReduceValuesToIntTask + (t, b, false, transformer, id, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + int r = id; + Object v; + while ((v = t.advance()) != null) + r = reducer.apply(r, transformer.apply((V)v)); + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceValuesToIntTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceValuesToIntTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceValuesToIntTask)par).pending) == 0) { + if ((s = t.sibling) != null) + r = reducer.apply(r, s.result); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final Integer getRawResult() { return result; } + } + + static final class MapReduceEntriesToIntTask + extends BulkTask { + final ObjectToInt> transformer; + final IntByIntToInt reducer; + final int basis; + int result; + MapReduceEntriesToIntTask sibling; + MapReduceEntriesToIntTask + (ConcurrentHashMapV8 m, + ObjectToInt> transformer, + int basis, + IntByIntToInt reducer) { + super(m); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + MapReduceEntriesToIntTask + (BulkTask p, int b, boolean split, + ObjectToInt> transformer, + int basis, + IntByIntToInt reducer) { + super(p, b, split); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + public final void compute() { + MapReduceEntriesToIntTask t = this; + final ObjectToInt> transformer = + this.transformer; + final IntByIntToInt reducer = this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + final int id = this.basis; + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceEntriesToIntTask rt = + new MapReduceEntriesToIntTask + (t, b, true, transformer, id, reducer); + t = new MapReduceEntriesToIntTask + (t, b, false, transformer, id, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + int r = id; + Object v; + while ((v = t.advance()) != null) + r = reducer.apply(r, transformer.apply(entryFor((K)t.nextKey, (V)v))); + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceEntriesToIntTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceEntriesToIntTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceEntriesToIntTask)par).pending) == 0) { + if ((s = t.sibling) != null) + r = reducer.apply(r, s.result); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final Integer getRawResult() { return result; } + } + + static final class MapReduceMappingsToIntTask + extends BulkTask { + final ObjectByObjectToInt transformer; + final IntByIntToInt reducer; + final int basis; + int result; + MapReduceMappingsToIntTask sibling; + MapReduceMappingsToIntTask + (ConcurrentHashMapV8 m, + ObjectByObjectToInt transformer, + int basis, + IntByIntToInt reducer) { + super(m); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + MapReduceMappingsToIntTask + (BulkTask p, int b, boolean split, + ObjectByObjectToInt transformer, + int basis, + IntByIntToInt reducer) { + super(p, b, split); + this.transformer = transformer; + this.basis = basis; this.reducer = reducer; + } + public final void compute() { + MapReduceMappingsToIntTask t = this; + final ObjectByObjectToInt transformer = + this.transformer; + final IntByIntToInt reducer = this.reducer; + if (transformer == null || reducer == null) + throw new Error(NullFunctionMessage); + final int id = this.basis; + int b = batch(); + while (b > 1 && t.baseIndex != t.baseLimit) { + b >>>= 1; + t.pending = 1; + MapReduceMappingsToIntTask rt = + new MapReduceMappingsToIntTask + (t, b, true, transformer, id, reducer); + t = new MapReduceMappingsToIntTask + (t, b, false, transformer, id, reducer); + t.sibling = rt; + rt.sibling = t; + rt.fork(); + } + int r = id; + Object v; + while ((v = t.advance()) != null) + r = reducer.apply(r, transformer.apply((K)t.nextKey, (V)v)); + t.result = r; + for (;;) { + int c; BulkTask par; MapReduceMappingsToIntTask s, p; + if ((par = t.parent) == null || + !(par instanceof MapReduceMappingsToIntTask)) { + t.quietlyComplete(); + break; + } + else if ((c = (p = (MapReduceMappingsToIntTask)par).pending) == 0) { + if ((s = t.sibling) != null) + r = reducer.apply(r, s.result); + (t = p).result = r; + } + else if (p.casPending(c, 0)) + break; + } + } + public final Integer getRawResult() { return result; } + } + + // Unsafe mechanics private static final sun.misc.Unsafe UNSAFE; private static final long counterOffset; @@ -3277,5 +6756,4 @@ public class ConcurrentHashMapV8 } } } - }