--- jsr166/src/jsr166e/ConcurrentHashMapV8.java 2011/09/19 12:31:07 1.25 +++ jsr166/src/jsr166e/ConcurrentHashMapV8.java 2012/07/06 23:45:09 1.49 @@ -20,7 +20,9 @@ import java.util.Enumeration; import java.util.ConcurrentModificationException; import java.util.NoSuchElementException; import java.util.concurrent.ConcurrentMap; +import java.util.concurrent.ThreadLocalRandom; import java.util.concurrent.locks.LockSupport; +import java.util.concurrent.locks.AbstractQueuedSynchronizer; import java.io.Serializable; /** @@ -71,7 +73,7 @@ import java.io.Serializable; * versions of this class, constructors may optionally specify an * expected {@code concurrencyLevel} as an additional hint for * internal sizing. Note that using many keys with exactly the same - * {@code hashCode{}} is a sure way to slow down performance of any + * {@code hashCode()} is a sure way to slow down performance of any * hash table. * *

This class and its views and iterators implement all of the @@ -98,26 +100,103 @@ public class ConcurrentHashMapV8 private static final long serialVersionUID = 7249069246763182397L; /** - * A function computing a mapping from the given key to a value, - * or {@code null} if there is no mapping. This is a place-holder - * for an upcoming JDK8 interface. + * 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 value for the given key, or null if there is no - * mapping. If this function throws an (unchecked) exception, - * the exception is rethrown to its caller, and no mapping is - * recorded. Because this function is invoked within - * atomicity control, the computation should be short and - * simple. The most common usage is to construct a new object - * serving as an initial mapped value. + * Returns a value for the given key, or null if there is no mapping. * * @param key the (non-null) key - * @return a value, or null if none + * @return a value for the key, or null if none */ 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. + */ + public static interface RemappingFunction { + /** + * Returns a new value given a key and its current value. + * + * @param key the (non-null) key + * @param value the current value, or null if there is no mapping + * @return a value for the key, or null if none + */ + V remap(K key, V value); + } + + /** + * 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 = ...
+     * // Uses parallel depth of log2 of size / (parallelism * slack of 8).
+     * int depth = 32 - Integer.numberOfLeadingZeros(m.size() / (aForkJoinPool.getParallelism() * 8));
+     * long sum = aForkJoinPool.invoke(new SumValues(m.valueSpliterator(), depth, null));
+     * // ...
+     * static class SumValues extends RecursiveTask {
+     *   final Spliterator s;
+     *   final int depth;             // number of splits before processing
+     *   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 d = depth - 1; d >= 0; --d)
+     *       (subtasks = new SumValues(s.split(), d, 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 Spliterator extends Iterator { + /** + * 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. + * + * @return a Spliterator covering approximately half of the + * elements + * @throws IllegalStateException if this Spliterator has + * already commenced traversing elements + */ + Spliterator split(); + } + /* * Overview: * @@ -134,83 +213,112 @@ public class ConcurrentHashMapV8 * work off Object types. And similarly, so do the internal * methods of auxiliary iterator and view classes. All public * generic typed methods relay in/out of these internal methods, - * supplying null-checks and casts as needed. + * supplying null-checks and casts as needed. This also allows + * many of the public methods to be factored into a smaller number + * of internal methods (although sadly not so for the five + * variants of put-related operations). The validation-based + * approach explained below leads to a lot of code sprawl because + * retry-control precludes factoring into smaller methods. * * The table is lazily initialized to a power-of-two size upon the - * first insertion. Each bin in the table contains a list of - * Nodes (most often, zero or one Node). Table accesses require - * volatile/atomic reads, writes, and CASes. Because there is no - * other way to arrange this without adding further indirections, - * we use intrinsics (sun.misc.Unsafe) operations. The lists of - * nodes within bins are always accurately traversable under - * volatile reads, so long as lookups check hash code and - * non-nullness of value before checking key equality. + * first insertion. Each bin in the table normally contains a + * list of Nodes (most often, the list has only zero or one Node). + * Table accesses require volatile/atomic reads, writes, and + * CASes. Because there is no other way to arrange this without + * adding further indirections, we use intrinsics + * (sun.misc.Unsafe) operations. The lists of nodes within bins + * are always accurately traversable under volatile reads, so long + * as lookups check hash code and non-nullness of value before + * checking key equality. * * We use the top two bits of Node hash fields for control * purposes -- they are available anyway because of addressing * constraints. As explained further below, these top bits are - * usd as follows: + * used as follows: * 00 - Normal * 01 - Locked * 11 - Locked and may have a thread waiting for lock * 10 - Node is a forwarding node * * The lower 30 bits of each Node's hash field contain a - * transformation (for better randomization -- method "spread") of - * the key's hash code, except for forwarding nodes, for which the - * lower bits are zero (and so always have hash field == "MOVED"). + * transformation of the key's hash code, except for forwarding + * nodes, for which the lower bits are zero (and so always have + * hash field == MOVED). * - * Insertion (via put or putIfAbsent) of the first node in an + * Insertion (via put or its variants) of the first node in an * empty bin is performed by just CASing it to the bin. This is - * by far the most common case for put operations. Other update - * operations (insert, delete, and replace) require locks. We do - * not want to waste the space required to associate a distinct - * lock object with each bin, so instead use the first node of a - * bin list itself as a lock. Blocking support for these locks - * relies on the builtin "synchronized" monitors. However, we - * also need a tryLock construction, so we overlay these by using - * bits of the Node hash field for lock control (see above), and - * so normally use builtin monitors only for blocking and - * signalling using wait/notifyAll constructions. See - * Node.tryAwaitLock. + * by far the most common case for put operations under most + * key/hash distributions. Other update operations (insert, + * delete, and replace) require locks. We do not want to waste + * the space required to associate a distinct lock object with + * each bin, so instead use the first node of a bin list itself as + * a lock. Blocking support for these locks relies on the builtin + * "synchronized" monitors. However, we also need a tryLock + * construction, so we overlay these by using bits of the Node + * hash field for lock control (see above), and so normally use + * builtin monitors only for blocking and signalling using + * wait/notifyAll constructions. See Node.tryAwaitLock. * * Using the first node of a list as a lock does not by itself * suffice though: When a node is locked, any update must first * validate that it is still the first node after locking it, and * retry if not. Because new nodes are always appended to lists, * once a node is first in a bin, it remains first until deleted - * or the bin becomes invalidated. However, operations that only - * conditionally update may inspect nodes until the point of - * update. This is a converse of sorts to the lazy locking - * technique described by Herlihy & Shavit. + * or the bin becomes invalidated (upon resizing). However, + * operations that only conditionally update may inspect nodes + * until the point of update. This is a converse of sorts to the + * lazy locking technique described by Herlihy & Shavit. * * The main disadvantage of per-bin locks is that other update * operations on other nodes in a bin list protected by the same * lock can stall, for example when user equals() or mapping - * functions take a long time. However, statistically, this is - * not a common enough problem to outweigh the time/space overhead - * of alternatives: Under random hash codes, the frequency of - * nodes in bins follows a Poisson distribution + * functions take a long time. However, statistically, under + * random hash codes, this is not a common problem. Ideally, the + * frequency of nodes in bins follows a Poisson distribution * (http://en.wikipedia.org/wiki/Poisson_distribution) with a * parameter of about 0.5 on average, given the resizing threshold * of 0.75, although with a large variance because of resizing * granularity. Ignoring variance, the expected occurrences of * list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The - * first few values are: + * first values are: * - * 0: 0.607 - * 1: 0.303 - * 2: 0.076 - * 3: 0.012 - * more: 0.002 + * 0: 0.60653066 + * 1: 0.30326533 + * 2: 0.07581633 + * 3: 0.01263606 + * 4: 0.00157952 + * 5: 0.00015795 + * 6: 0.00001316 + * 7: 0.00000094 + * 8: 0.00000006 + * more: less than 1 in ten million * * Lock contention probability for two threads accessing distinct - * elements is roughly 1 / (8 * #elements). Function "spread" - * performs hashCode randomization that improves the likelihood - * that these assumptions hold unless users define exactly the - * same value for too many hashCodes. + * elements is roughly 1 / (8 * #elements) under random hashes. * - * The table is resized when occupancy exceeds an occupancy + * Actual hash code distributions encountered in practice + * sometimes deviate significantly from uniform randomness. This + * includes the case when N > (1<<30), so some keys MUST collide. + * Similarly for dumb or hostile usages in which multiple keys are + * designed to have identical hash codes. Also, although we guard + * against the worst effects of this (see method spread), sets of + * hashes may differ only in bits that do not impact their bin + * index for a given power-of-two mask. So we use a secondary + * strategy that applies when the number of nodes in a bin exceeds + * a threshold, and at least one of the keys implements + * Comparable. These TreeBins use a balanced tree to hold nodes + * (a specialized form of red-black trees), bounding search time + * to O(log N). Each search step in a TreeBin is around twice as + * slow as in a regular list, but given that N cannot exceed + * (1<<64) (before running out of addresses) this bounds search + * steps, lock hold times, etc, to reasonable constants (roughly + * 100 nodes inspected per operation worst case) so long as keys + * are Comparable (which is very common -- String, Long, etc). + * TreeBin nodes (TreeNodes) also maintain the same "next" + * traversal pointers as regular nodes, so can be traversed in + * iterators in the same way. + * + * The table is resized when occupancy exceeds a percentage * threshold (nominally, 0.75, but see below). Only a single * thread performs the resize (using field "sizeCtl", to arrange * exclusion), but the table otherwise remains usable for reads @@ -231,31 +339,30 @@ public class ConcurrentHashMapV8 * * Each bin transfer requires its bin lock. However, unlike other * cases, a transfer can skip a bin if it fails to acquire its - * lock, and revisit it later. Method rebuild maintains a buffer - * of TRANSFER_BUFFER_SIZE bins that have been skipped because of - * failure to acquire a lock, and blocks only if none are - * available (i.e., only very rarely). The transfer operation - * must also ensure that all accessible bins in both the old and - * new table are usable by any traversal. 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 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 to the old - * table until the new ones are established. (This sometimes - * requires transiently locking a forwarding node, which is - * possible under the above encoding.) These more expensive + * lock, and revisit it later (unless it is a TreeBin). Method + * rebuild maintains a buffer of TRANSFER_BUFFER_SIZE bins that + * have been skipped because of failure to acquire a lock, and + * blocks only if none are available (i.e., only very rarely). + * The transfer operation must also ensure that all accessible + * bins in both the old and new table are usable by any traversal. + * 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 + * 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 + * to the old table until the new ones are established. (This + * sometimes requires transiently locking a forwarding node, which + * is possible under the above encoding.) These more expensive * 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. + * 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 @@ -266,13 +373,17 @@ public class ConcurrentHashMapV8 * The element count is maintained using a LongAdder, which avoids * contention on updates but can encounter cache thrashing if read * too frequently during concurrent access. To avoid reading so - * often, resizing is normally attempted only upon adding to a bin - * already holding two or more nodes. Under uniform hash - * distributions, the probability of this occurring at threshold - * is around 13%, meaning that only about 1 in 8 puts check - * threshold (and after resizing, many fewer do so). But this - * approximation has high variance for small table sizes, so we - * check on any collision for sizes <= 64. + * often, resizing is attempted either when a bin lock is + * contended, or upon adding to a bin already holding two or more + * nodes (checked before adding in the xIfAbsent methods, after + * adding in others). Under uniform hash distributions, the + * probability of this occurring at threshold is around 13%, + * meaning that only about 1 in 8 puts check threshold (and after + * resizing, many fewer do so). But this approximation has high + * variance for small table sizes, so we check on any collision + * for sizes <= 64. The bulk putAll operation further reduces + * contention by only committing count updates upon these size + * checks. * * Maintaining API and serialization compatibility with previous * versions of this class introduces several oddities. Mainly: We @@ -329,11 +440,18 @@ public class ConcurrentHashMapV8 */ private static final int TRANSFER_BUFFER_SIZE = 32; + /** + * The bin count threshold for using a tree rather than list for a + * bin. The value reflects the approximate break-even point for + * using tree-based operations. + */ + private static final int TREE_THRESHOLD = 8; + /* * Encodings for special uses of Node hash fields. See above for * explanation. */ - static final int MOVED = 0x80000000; // hash field for fowarding nodes + static final int MOVED = 0x80000000; // hash field for forwarding nodes static final int LOCKED = 0x40000000; // set/tested only as a bit static final int WAITING = 0xc0000000; // both bits set/tested together static final int HASH_BITS = 0x3fffffff; // usable bits of normal node hash @@ -368,19 +486,45 @@ public class ConcurrentHashMapV8 /** For serialization compatibility. Null unless serialized; see below */ private Segment[] segments; + /* ---------------- Table element access -------------- */ + + /* + * Volatile access methods are used for table elements as well as + * elements of in-progress next table while resizing. Uses are + * null checked by callers, and implicitly bounds-checked, relying + * on the invariants that tab arrays have non-zero size, and all + * indices are masked with (tab.length - 1) which is never + * negative and always less than length. Note that, to be correct + * wrt arbitrary concurrency errors by users, bounds checks must + * operate on local variables, which accounts for some odd-looking + * inline assignments below. + */ + + static final Node tabAt(Node[] tab, int i) { // used by InternalIterator + return (Node)UNSAFE.getObjectVolatile(tab, ((long)i< */ final void tryAwaitLock(Node[] tab, int i) { if (tab != null && i >= 0 && i < tab.length) { // bounds check + int r = ThreadLocalRandom.current().nextInt(); // randomize spins int spins = MAX_SPINS, h; while (tabAt(tab, i) == this && ((h = hash) & LOCKED) != 0) { if (spins >= 0) { - if (--spins == MAX_SPINS >>> 1) - Thread.yield(); // heuristically yield mid-way + r ^= r << 1; r ^= r >>> 3; r ^= r << 10; // xorshift + if (r >= 0 && --spins == 0) + Thread.yield(); // yield before block } else if (casHash(h, h | WAITING)) { - synchronized(this) { + synchronized (this) { if (tabAt(tab, i) == this && (hash & WAITING) == WAITING) { try { @@ -458,134 +604,527 @@ public class ConcurrentHashMapV8 } } - /* ---------------- Table element access -------------- */ + /* ---------------- TreeBins -------------- */ - /* - * Volatile access methods are used for table elements as well as - * elements of in-progress next table while resizing. Uses are - * null checked by callers, and implicitly bounds-checked, relying - * on the invariants that tab arrays have non-zero size, and all - * indices are masked with (tab.length - 1) which is never - * negative and always less than length. Note that, to be correct - * wrt arbitrary concurrency errors by users, bounds checks must - * operate on local variables, which accounts for some odd-looking - * inline assignments below. + /** + * Nodes for use in TreeBins */ - - static final Node tabAt(Node[] tab, int i) { // used by InternalIterator - return (Node)UNSAFE.getObjectVolatile(tab, ((long)i< + * for the same T, so we cannot invoke compareTo among them. To + * 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 + * 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 + * 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 + * locks. However, lookups use shared read-lock mechanics to allow + * multiple readers in the absence of writers. Additionally, + * these lookups do not ever block: While the lock is not + * available, they proceed along the slow traversal path (via + * next-pointers) until the lock becomes available or the list is + * exhausted, whichever comes first. (These cases are not fast, + * but maximize aggregate expected throughput.) The AQS mechanics + * for doing this are straightforward. The lock state is held as + * AQS getState(). Read counts are negative; the write count (1) + * is positive. There are no signalling preferences among readers + * and writers. Since we don't need to export full Lock API, we + * just override the minimal AQS methods and use them directly. + */ + static final class TreeBin extends AbstractQueuedSynchronizer { + private static final long serialVersionUID = 2249069246763182397L; + transient TreeNode root; // root of tree + transient TreeNode first; // head of next-pointer list - private static final void setTabAt(Node[] tab, int i, Node v) { - UNSAFE.putObjectVolatile(tab, ((long)i< 0; } + public final boolean tryAcquire(int ignore) { + if (compareAndSetState(0, 1)) { + setExclusiveOwnerThread(Thread.currentThread()); + return true; + } + return false; + } + public final boolean tryRelease(int ignore) { + setExclusiveOwnerThread(null); + setState(0); + return true; + } + public final int tryAcquireShared(int ignore) { + for (int c;;) { + if ((c = getState()) > 0) + return -1; + if (compareAndSetState(c, c -1)) + return 1; + } + } + public final boolean tryReleaseShared(int ignore) { + int c; + do {} while (!compareAndSetState(c = getState(), c + 1)); + 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; + } + } - /* ---------------- Internal access and update methods -------------- */ + /** 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; + } + } - /** - * Applies a supplemental hash function to a given hashCode, which - * defends against poor quality hash functions. The result must - * be have the top 2 bits clear. For reasonable performance, this - * function must have good avalanche properties; i.e., that each - * bit of the argument affects each bit of the result. (Although - * we don't care about the unused top 2 bits.) - */ - private static final int spread(int h) { - // Apply base step of MurmurHash; see http://code.google.com/p/smhasher/ - h ^= h >>> 16; - h *= 0x85ebca6b; - h ^= h >>> 13; - h *= 0xc2b2ae35; - return ((h >>> 16) ^ h) & HASH_BITS; // mask out top bits - } + /** + * Return 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) { + Class c = k.getClass(); + while (p != null) { + 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 + dir = (h < ph) ? -1 : 1; + p = (dir > 0) ? p.right : p.left; + } + return null; + } - /** Implementation for get and containsKey */ - private final Object internalGet(Object k) { - int h = spread(k.hashCode()); - retry: for (Node[] tab = table; tab != null;) { - Node e; Object ek, ev; int eh; // locals to read fields once - for (e = tabAt(tab, (tab.length - 1) & h); e != null; e = e.next) { - if ((eh = e.hash) == MOVED) { - tab = (Node[])e.key; // restart with new table - continue retry; + /** + * Wrapper for getTreeNode used by CHM.get. Tries to obtain + * read-lock to call getTreeNode, but during failure to get + * lock, searches along next links. + */ + final Object getValue(int h, Object k) { + Node r = null; + int c = getState(); // Must read lock state first + for (Node e = first; e != null; e = e.next) { + if (c <= 0 && compareAndSetState(c, c - 1)) { + try { + r = getTreeNode(h, k, root); + } finally { + releaseShared(0); + } + break; } - if ((eh & HASH_BITS) == h && (ev = e.val) != null && - ((ek = e.key) == k || k.equals(ek))) - return ev; + else if ((e.hash & HASH_BITS) == h && k.equals(e.key)) { + r = e; + break; + } + else + c = getState(); } - break; + return r == null ? null : r.val; } - return null; - } - /** Implementation for put and putIfAbsent */ - private final Object internalPut(Object k, Object v, boolean replace) { - int h = spread(k.hashCode()); - Object oldVal = null; // previous value or null if none - 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))) - break; // no lock when adding to empty bin + /** + * Finds or adds a node. + * @return null if added + */ + @SuppressWarnings("unchecked") // suppress Comparable cast warning + final TreeNode putTreeNode(int h, Object k, Object v) { + Class c = k.getClass(); + TreeNode pp = root, p = null; + int dir = 0; + 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; + 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 + dir = (h < ph) ? -1 : 1; + pp = (dir > 0) ? p.right : p.left; + } + + TreeNode f = first; + TreeNode x = first = new TreeNode(h, k, v, f, p); + if (p == null) + root = x; + else { // attach and rebalance; adapted from CLR + TreeNode xp, xpp; + if (f != null) + f.prev = x; + if (dir <= 0) + p.left = x; + else + 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; } - else if ((fh = f.hash) == MOVED) - tab = (Node[])f.key; - else if (!replace && (fh & HASH_BITS) == h && (fv = f.val) != null && - ((fk = f.key) == k || k.equals(fk))) { - oldVal = fv; // precheck 1st node for putIfAbsent - break; + return null; + } + + /** + * Removes the given node, that must be present before this + * call. This is messier than typical red-black deletion code + * because we cannot swap the contents of an interior node + * with a leaf successor that is pinned by "next" pointers + * that are accessible independently of lock. So instead we + * swap the tree linkages. + */ + final void deleteTreeNode(TreeNode p) { + TreeNode next = (TreeNode)p.next; // unlink traversal pointers + TreeNode pred = p.prev; + if (pred == null) + first = next; + else + pred.next = next; + if (next != null) + next.prev = pred; + TreeNode replacement; + TreeNode pl = p.left; + TreeNode pr = p.right; + if (pl != null && pr != null) { + 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; + if (s == pr) { // p was s's direct parent + p.parent = s; + s.right = p; + } + else { + TreeNode sp = s.parent; + if ((p.parent = sp) != null) { + if (s == sp.left) + sp.left = p; + else + sp.right = p; + } + if ((s.right = pr) != null) + pr.parent = s; + } + p.left = null; + if ((p.right = sr) != null) + sr.parent = p; + if ((s.left = pl) != null) + pl.parent = s; + if ((s.parent = pp) == null) + root = s; + else if (p == pp.left) + pp.left = s; + else + pp.right = s; + replacement = sr; } - else if ((fh & LOCKED) != 0) - f.tryAwaitLock(tab, i); - else if (f.casHash(fh, fh | LOCKED)) { - boolean validated = false; - boolean checkSize = false; - try { - if (tabAt(tab, i) == f) { - validated = true; // retry if 1st already deleted - for (Node e = f;;) { - Object ek, ev; - if ((e.hash & HASH_BITS) == h && - (ev = e.val) != null && - ((ek = e.key) == k || k.equals(ek))) { - oldVal = ev; - if (replace) - e.val = v; - break; + else + replacement = (pl != null) ? pl : pr; + TreeNode pp = p.parent; + if (replacement == null) { + if (pp == null) { + root = null; + return; + } + replacement = p; + } + else { + replacement.parent = pp; + if (pp == null) + root = replacement; + else if (p == pp.left) + pp.left = replacement; + else + pp.right = replacement; + p.left = p.right = p.parent = null; + } + 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; + } + 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; + x = xp; } - Node last = e; - if ((e = e.next) == null) { - last.next = new Node(h, k, v, null); - if (last != f || tab.length <= 64) - checkSize = true; - break; + 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; } } } - } finally { // unlock and signal if needed - if (!f.casHash(fh | LOCKED, fh)) { - f.hash = fh; - synchronized(f) { f.notifyAll(); }; + 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 { + 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; + } + } } } - if (validated) { - int sc; - if (checkSize && tab.length < MAXIMUM_CAPACITY && - (sc = sizeCtl) >= 0 && counter.sum() >= (long)sc) - growTable(); - break; + } + 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; + } + } + } + + /* ---------------- Collision reduction methods -------------- */ + + /** + * Spreads higher bits to lower, and also forces top 2 bits to 0. + * Because the table uses power-of-two masking, sets of hashes + * that vary only in bits above the current mask will always + * collide. (Among known examples are sets of Float keys holding + * consecutive whole numbers in small tables.) To counter this, + * 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 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. + */ + private static final int spread(int h) { + h ^= (h >>> 18) ^ (h >>> 12); + return (h ^ (h >>> 10)) & HASH_BITS; + } + + /** + * Replaces a list bin with a tree bin. Call only when locked. + * Fails to replace if the given key is non-comparable or table + * is, or needs, resizing. + */ + private final void replaceWithTreeBin(Node[] tab, int index, Object key) { + if ((key instanceof Comparable) && + (tab.length >= MAXIMUM_CAPACITY || counter.sum() < (long)sizeCtl)) { + TreeBin t = new TreeBin(); + for (Node e = tabAt(tab, index); e != null; e = e.next) + t.putTreeNode(e.hash & HASH_BITS, e.key, e.val); + setTabAt(tab, index, new Node(MOVED, t, null, null)); + } + } + + /* ---------------- Internal access and update methods -------------- */ + + /** Implementation for get and containsKey */ + private final Object internalGet(Object k) { + int h = spread(k.hashCode()); + retry: for (Node[] tab = table; tab != null;) { + Node e, p; Object ek, ev; int eh; // locals to read fields once + for (e = tabAt(tab, (tab.length - 1) & h); e != null; e = e.next) { + if ((eh = e.hash) == MOVED) { + if ((ek = e.key) instanceof TreeBin) // search TreeBin + return ((TreeBin)ek).getValue(h, k); + else { // restart with new table + tab = (Node[])ek; + continue retry; + } } + else if ((eh & HASH_BITS) == h && (ev = e.val) != null && + ((ek = e.key) == k || k.equals(ek))) + return ev; } + break; } - if (oldVal == null) - counter.increment(); // update counter outside of locks - return oldVal; + return null; } /** @@ -597,16 +1136,49 @@ public class ConcurrentHashMapV8 int h = spread(k.hashCode()); Object oldVal = null; for (Node[] tab = table;;) { - Node f; int i, fh; + Node f; int i, fh; Object fk; if (tab == null || (f = tabAt(tab, i = (tab.length - 1) & h)) == null) break; - else if ((fh = f.hash) == MOVED) - tab = (Node[])f.key; + else if ((fh = f.hash) == MOVED) { + if ((fk = f.key) instanceof TreeBin) { + TreeBin t = (TreeBin)fk; + boolean validated = false; + boolean deleted = false; + t.acquire(0); + try { + if (tabAt(tab, i) == f) { + validated = true; + TreeNode p = t.getTreeNode(h, k, t.root); + if (p != null) { + Object pv = p.val; + if (cv == null || cv == pv || cv.equals(pv)) { + oldVal = pv; + if ((p.val = v) == null) { + deleted = true; + t.deleteTreeNode(p); + } + } + } + } + } finally { + t.release(0); + } + if (validated) { + if (deleted) + counter.add(-1L); + break; + } + } + else + tab = (Node[])fk; + } else if ((fh & HASH_BITS) != h && f.next == null) // precheck break; // rules out possible existence - else if ((fh & LOCKED) != 0) + else if ((fh & LOCKED) != 0) { + checkForResize(); // try resizing if can't get lock f.tryAwaitLock(tab, i); + } else if (f.casHash(fh, fh | LOCKED)) { boolean validated = false; boolean deleted = false; @@ -639,12 +1211,12 @@ public class ConcurrentHashMapV8 } finally { if (!f.casHash(fh | LOCKED, fh)) { f.hash = fh; - synchronized(f) { f.notifyAll(); }; + synchronized (f) { f.notifyAll(); }; } } if (validated) { if (deleted) - counter.decrement(); + counter.add(-1L); break; } } @@ -652,77 +1224,445 @@ public class ConcurrentHashMapV8 return oldVal; } - /** Implementation for computeIfAbsent and compute. Like put, but messier. */ - // Todo: Somehow reinstate non-termination check - @SuppressWarnings("unchecked") - private final V internalCompute(K k, - MappingFunction fn, - boolean replace) { + /* + * Internal versions of the five insertion methods, each a + * little more complicated than the last. All have + * the same basic structure as the first (internalPut): + * 1. If table uninitialized, create + * 2. If bin empty, try to CAS new node + * 3. If bin stale, use new table + * 4. if bin converted to TreeBin, validate and relay to TreeBin methods + * 5. Lock and validate; if valid, scan and add or update + * + * The others interweave other checks and/or alternative actions: + * * Plain put checks for and performs resize after insertion. + * * putIfAbsent prescans for mapping without lock (and fails to add + * if present), which also makes pre-emptive resize checks worthwhile. + * * computeIfAbsent extends form used in putIfAbsent with additional + * mechanics to deal with, calls, potential exceptions and null + * returns from function call. + * * compute uses the same function-call mechanics, but without + * the prescans + * * putAll attempts to pre-allocate enough table space + * and more lazily performs count updates and checks. + * + * Someday when details settle down a bit more, it might be worth + * some factoring to reduce sprawl. + */ + + /** Implementation for put */ + private final Object internalPut(Object k, Object v) { int h = spread(k.hashCode()); - V val = null; - boolean added = false; - Node[] tab = table; - outer:for (;;) { + int count = 0; + for (Node[] tab = table;;) { + int i; Node f; int fh; Object fk; + 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))) + break; // no lock when adding to empty bin + } + else if ((fh = f.hash) == MOVED) { + if ((fk = f.key) instanceof TreeBin) { + TreeBin t = (TreeBin)fk; + Object oldVal = null; + t.acquire(0); + try { + if (tabAt(tab, i) == f) { + count = 2; + TreeNode p = t.putTreeNode(h, k, v); + if (p != null) { + oldVal = p.val; + p.val = v; + } + } + } finally { + t.release(0); + } + if (count != 0) { + if (oldVal != null) + return oldVal; + break; + } + } + else + tab = (Node[])fk; + } + else if ((fh & LOCKED) != 0) { + checkForResize(); + f.tryAwaitLock(tab, i); + } + else if (f.casHash(fh, fh | LOCKED)) { + Object oldVal = null; + try { // needed in case equals() throws + if (tabAt(tab, i) == f) { + count = 1; + for (Node e = f;; ++count) { + Object ek, ev; + if ((e.hash & HASH_BITS) == h && + (ev = e.val) != null && + ((ek = e.key) == k || k.equals(ek))) { + oldVal = ev; + e.val = v; + break; + } + Node last = e; + if ((e = e.next) == null) { + last.next = new Node(h, k, v, null); + if (count >= TREE_THRESHOLD) + replaceWithTreeBin(tab, i, k); + break; + } + } + } + } finally { // unlock and signal if needed + if (!f.casHash(fh | LOCKED, fh)) { + f.hash = fh; + synchronized (f) { f.notifyAll(); }; + } + } + if (count != 0) { + if (oldVal != null) + return oldVal; + if (tab.length <= 64) + count = 2; + break; + } + } + } + counter.add(1L); + if (count > 1) + checkForResize(); + return null; + } + + /** Implementation for putIfAbsent */ + private final Object internalPutIfAbsent(Object k, Object v) { + int h = spread(k.hashCode()); + 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))) + break; + } + else if ((fh = f.hash) == MOVED) { + if ((fk = f.key) instanceof TreeBin) { + TreeBin t = (TreeBin)fk; + Object oldVal = null; + t.acquire(0); + try { + if (tabAt(tab, i) == f) { + count = 2; + TreeNode p = t.putTreeNode(h, k, v); + if (p != null) + oldVal = p.val; + } + } finally { + t.release(0); + } + if (count != 0) { + if (oldVal != null) + return oldVal; + break; + } + } + else + tab = (Node[])fk; + } + else if ((fh & HASH_BITS) == h && (fv = f.val) != null && + ((fk = f.key) == k || k.equals(fk))) + return fv; + else { + Node g = f.next; + if (g != null) { // at least 2 nodes -- search and maybe resize + for (Node e = g;;) { + Object ek, ev; + if ((e.hash & HASH_BITS) == h && (ev = e.val) != null && + ((ek = e.key) == k || k.equals(ek))) + return ev; + if ((e = e.next) == null) { + checkForResize(); + break; + } + } + } + if (((fh = f.hash) & LOCKED) != 0) { + checkForResize(); + f.tryAwaitLock(tab, i); + } + else if (tabAt(tab, i) == f && f.casHash(fh, fh | LOCKED)) { + Object oldVal = null; + try { + if (tabAt(tab, i) == f) { + count = 1; + for (Node e = f;; ++count) { + Object ek, ev; + if ((e.hash & HASH_BITS) == h && + (ev = e.val) != null && + ((ek = e.key) == k || k.equals(ek))) { + oldVal = ev; + break; + } + Node last = e; + if ((e = e.next) == null) { + last.next = new Node(h, k, v, null); + 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 (oldVal != null) + return oldVal; + if (tab.length <= 64) + count = 2; + break; + } + } + } + } + counter.add(1L); + if (count > 1) + checkForResize(); + return null; + } + + /** Implementation for computeIfAbsent */ + private final Object internalComputeIfAbsent(K k, + MappingFunction mf) { + int h = spread(k.hashCode()); + Object val = null; + int count = 0; + for (Node[] tab = table;;) { Node f; int i, fh; Object fk, fv; if (tab == null) tab = initTable(); else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) { Node node = new Node(fh = h | LOCKED, k, null, null); - boolean validated = false; if (casTabAt(tab, i, null, node)) { - validated = true; + count = 1; try { - val = fn.map(k); - if (val != null) { + if ((val = mf.map(k)) != null) node.val = val; - added = true; + } finally { + if (val == null) + setTabAt(tab, i, null); + if (!node.casHash(fh, h)) { + node.hash = h; + synchronized (node) { node.notifyAll(); }; + } + } + } + if (count != 0) + break; + } + else if ((fh = f.hash) == MOVED) { + if ((fk = f.key) instanceof TreeBin) { + TreeBin t = (TreeBin)fk; + boolean added = false; + t.acquire(0); + try { + if (tabAt(tab, i) == f) { + count = 1; + TreeNode p = t.getTreeNode(h, k, t.root); + if (p != null) + val = p.val; + else if ((val = mf.map(k)) != null) { + added = true; + count = 2; + t.putTreeNode(h, k, val); + } + } + } finally { + t.release(0); + } + if (count != 0) { + if (!added) + return val; + break; + } + } + else + tab = (Node[])fk; + } + else if ((fh & HASH_BITS) == h && (fv = f.val) != null && + ((fk = f.key) == k || k.equals(fk))) + return fv; + else { + Node g = f.next; + if (g != null) { + for (Node e = g;;) { + Object ek, ev; + if ((e.hash & HASH_BITS) == h && (ev = e.val) != null && + ((ek = e.key) == k || k.equals(ek))) + return ev; + if ((e = e.next) == null) { + checkForResize(); + break; + } + } + } + if (((fh = f.hash) & LOCKED) != 0) { + checkForResize(); + f.tryAwaitLock(tab, i); + } + else if (tabAt(tab, i) == f && f.casHash(fh, fh | LOCKED)) { + boolean added = false; + try { + if (tabAt(tab, i) == f) { + count = 1; + for (Node e = f;; ++count) { + Object ek, ev; + if ((e.hash & HASH_BITS) == h && + (ev = e.val) != null && + ((ek = e.key) == k || k.equals(ek))) { + val = ev; + break; + } + Node last = e; + if ((e = e.next) == null) { + if ((val = mf.map(k)) != null) { + added = true; + last.next = new Node(h, k, val, null); + 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 (!added) + return val; + if (tab.length <= 64) + count = 2; + break; + } + } + } + } + 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) { + int h = spread(k.hashCode()); + Object val = null; + 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) { + 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) { + node.val = val; + delta = 1; + } + } finally { + if (delta == 0) setTabAt(tab, i, null); if (!node.casHash(fh, h)) { node.hash = h; - synchronized(node) { node.notifyAll(); }; + synchronized (node) { node.notifyAll(); }; } } } - if (validated) + if (count != 0) break; } - else if ((fh = f.hash) == MOVED) - tab = (Node[])f.key; - else if (!replace && (fh & HASH_BITS) == h && (fv = f.val) != null && - ((fk = f.key) == k || k.equals(fk))) { - if (tabAt(tab, i) == f) { - val = (V)fv; - 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); + Object pv = (p == null) ? null : p.val; + if ((val = mf.remap(k, (V)pv)) != 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) + else if ((fh & LOCKED) != 0) { + checkForResize(); f.tryAwaitLock(tab, i); + } else if (f.casHash(fh, fh | LOCKED)) { - boolean validated = false; - boolean checkSize = false; try { if (tabAt(tab, i) == f) { - validated = true; - for (Node e = f;;) { - Object ek, ev, v; + 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))) { - if (replace && (v = fn.map(k)) != null) - ev = e.val = v; - val = (V)ev; + val = mf.remap(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 = fn.map(k)) != null) { - last.next = new Node(h, k, val, null); - added = true; - if (last != f || tab.length <= 64) - checkSize = true; + if ((val = mf.remap(k, null)) != null) { + pred.next = new Node(h, k, val, null); + delta = 1; + if (count >= TREE_THRESHOLD) + replaceWithTreeBin(tab, i, k); } break; } @@ -731,66 +1671,128 @@ public class ConcurrentHashMapV8 } finally { if (!f.casHash(fh | LOCKED, fh)) { f.hash = fh; - synchronized(f) { f.notifyAll(); }; + synchronized (f) { f.notifyAll(); }; } } - if (validated) { - int sc; - if (checkSize && tab.length < MAXIMUM_CAPACITY && - (sc = sizeCtl) >= 0 && counter.sum() >= (long)sc) - growTable(); + if (count != 0) { + if (tab.length <= 64) + count = 2; break; } } } - if (added) - counter.increment(); + if (delta != 0) { + counter.add((long)delta); + if (count > 1) + checkForResize(); + } return val; } - /** - * Implementation for clear. Steps through each bin, removing all nodes. - */ - private final void internalClear() { - long delta = 0L; // negative number of deletions - int i = 0; - Node[] tab = table; - while (tab != null && i < tab.length) { - int fh; - Node f = tabAt(tab, i); - if (f == null) - ++i; - else if ((fh = f.hash) == MOVED) - tab = (Node[])f.key; - else if ((fh & LOCKED) != 0) - f.tryAwaitLock(tab, i); - else if (f.casHash(fh, fh | LOCKED)) { - boolean validated = false; - try { - if (tabAt(tab, i) == f) { - validated = true; - for (Node e = f; e != null; e = e.next) { - if (e.val != null) { // currently always true - e.val = null; - --delta; + /** Implementation for putAll */ + private final void internalPutAll(Map m) { + tryPresize(m.size()); + long delta = 0L; // number of uncommitted additions + boolean npe = false; // to throw exception on exit for nulls + try { // to clean up counts on other exceptions + for (Map.Entry entry : m.entrySet()) { + Object k, v; + if (entry == null || (k = entry.getKey()) == null || + (v = entry.getValue()) == null) { + npe = true; + break; + } + int h = spread(k.hashCode()); + for (Node[] tab = table;;) { + int i; Node f; int fh; Object fk; + 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; + break; + } + } + else if ((fh = f.hash) == MOVED) { + if ((fk = f.key) instanceof TreeBin) { + TreeBin t = (TreeBin)fk; + boolean validated = false; + t.acquire(0); + try { + if (tabAt(tab, i) == f) { + validated = true; + TreeNode p = t.getTreeNode(h, k, t.root); + if (p != null) + p.val = v; + else { + t.putTreeNode(h, k, v); + ++delta; + } + } + } finally { + t.release(0); } + if (validated) + break; } - setTabAt(tab, i, null); + else + tab = (Node[])fk; } - } finally { - if (!f.casHash(fh | LOCKED, fh)) { - f.hash = fh; - synchronized(f) { f.notifyAll(); }; + else if ((fh & LOCKED) != 0) { + counter.add(delta); + delta = 0L; + checkForResize(); + f.tryAwaitLock(tab, i); + } + else if (f.casHash(fh, fh | LOCKED)) { + int count = 0; + try { + if (tabAt(tab, i) == f) { + count = 1; + for (Node e = f;; ++count) { + Object ek, ev; + if ((e.hash & HASH_BITS) == h && + (ev = e.val) != null && + ((ek = e.key) == k || k.equals(ek))) { + e.val = v; + break; + } + Node last = e; + if ((e = e.next) == null) { + ++delta; + last.next = new Node(h, k, v, null); + 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 (count > 1) { + counter.add(delta); + delta = 0L; + checkForResize(); + } + break; + } } } - if (validated) - ++i; } + } finally { + if (delta != 0) + counter.add(delta); } - counter.add(delta); + if (npe) + throw new NullPointerException(); } - /* ----------------Table Initialization and Resizing -------------- */ + /* ---------------- Table Initialization and Resizing -------------- */ /** * Returns a power of two table size for the given desired capacity. @@ -819,7 +1821,7 @@ public class ConcurrentHashMapV8 if ((tab = table) == null) { int n = (sc > 0) ? sc : DEFAULT_CAPACITY; tab = table = new Node[n]; - sc = n - (n >>> 2) - 1; + sc = n - (n >>> 2); } } finally { sizeCtl = sc; @@ -831,20 +1833,21 @@ public class ConcurrentHashMapV8 } /** - * If not already resizing, creates next table and transfers bins. - * Rechecks occupancy after a transfer to see if another resize is - * already needed because resizings are lagging additions. - */ - private final void growTable() { - int sc = sizeCtl; - if (sc >= 0 && UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) { + * If table is too small and not already resizing, creates next + * table and transfers bins. Rechecks occupancy after a transfer + * to see if another resize is already needed because resizings + * are lagging additions. + */ + private final void checkForResize() { + Node[] tab; int n, sc; + while ((tab = table) != null && + (n = tab.length) < MAXIMUM_CAPACITY && + (sc = sizeCtl) >= 0 && counter.sum() >= (long)sc && + UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) { try { - Node[] tab; int n; - while ((tab = table) != null && - (n = tab.length) > 0 && n < MAXIMUM_CAPACITY && - counter.sum() >= (long)sc) { + if (tab == table) { table = rebuild(tab); - sc = (n << 1) - (n >>> 1) - 1; + sc = (n << 1) - (n >>> 1); } } finally { sizeCtl = sc; @@ -852,6 +1855,45 @@ public class ConcurrentHashMapV8 } } + /** + * Tries to presize table to accommodate the given number of elements. + * + * @param size number of elements (doesn't need to be perfectly accurate) + */ + private final void tryPresize(int size) { + int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : + tableSizeFor(size + (size >>> 1) + 1); + int sc; + while ((sc = sizeCtl) >= 0) { + Node[] tab = table; int n; + if (tab == null || (n = tab.length) == 0) { + n = (sc > c) ? sc : c; + if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) { + try { + if (table == tab) { + table = new Node[n]; + sc = n - (n >>> 2); + } + } finally { + sizeCtl = sc; + } + } + } + else if (c <= sc || n >= MAXIMUM_CAPACITY) + break; + else if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) { + try { + if (table == tab) { + table = rebuild(tab); + sc = (n << 1) - (n >>> 1); + } + } finally { + sizeCtl = sc; + } + } + } + } + /* * Moves and/or copies the nodes in each bin to new table. See * above for explanation. @@ -876,7 +1918,7 @@ public class ConcurrentHashMapV8 continue; } else { // transiently use a locked forwarding node - Node g = new Node(MOVED|LOCKED, nextTab, null, null); + Node g = new Node(MOVED|LOCKED, nextTab, null, null); if (!casTabAt(tab, i, f, g)) continue; setTabAt(nextTab, i, null); @@ -884,45 +1926,41 @@ public class ConcurrentHashMapV8 setTabAt(tab, i, fwd); if (!g.casHash(MOVED|LOCKED, MOVED)) { g.hash = MOVED; - synchronized(g) { g.notifyAll(); } + synchronized (g) { g.notifyAll(); } + } + } + } + else if ((fh = f.hash) == MOVED) { + Object fk = f.key; + if (fk instanceof TreeBin) { + TreeBin t = (TreeBin)fk; + boolean validated = false; + t.acquire(0); + try { + if (tabAt(tab, i) == f) { + validated = true; + splitTreeBin(nextTab, i, t); + setTabAt(tab, i, fwd); + } + } finally { + t.release(0); } + if (!validated) + continue; } } - else if (((fh = f.hash) & LOCKED) == 0 && f.casHash(fh, fh|LOCKED)) { + else if ((fh & LOCKED) == 0 && f.casHash(fh, fh|LOCKED)) { boolean validated = false; try { // split to lo and hi lists; copying as needed if (tabAt(tab, i) == f) { validated = true; - Node e = f, lastRun = f; - Node lo = null, hi = null; - int runBit = e.hash & n; - for (Node p = e.next; p != null; p = p.next) { - int b = p.hash & n; - if (b != runBit) { - runBit = b; - lastRun = p; - } - } - if (runBit == 0) - lo = lastRun; - else - hi = lastRun; - for (Node p = e; p != lastRun; p = p.next) { - int ph = p.hash & HASH_BITS; - Object pk = p.key, pv = p.val; - if ((ph & n) == 0) - lo = new Node(ph, pk, pv, lo); - else - hi = new Node(ph, pk, pv, hi); - } - setTabAt(nextTab, i, lo); - setTabAt(nextTab, i + n, hi); + splitBin(nextTab, i, f); setTabAt(tab, i, fwd); } } finally { if (!f.casHash(fh | LOCKED, fh)) { f.hash = fh; - synchronized(f) { f.notifyAll(); }; + synchronized (f) { f.notifyAll(); }; } } if (!validated) @@ -961,6 +1999,137 @@ public class ConcurrentHashMapV8 } } + /** + * 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 + int runBit = e.hash & bit; + Node lastRun = e, lo = null, hi = null; + for (Node p = e.next; p != null; p = p.next) { + int b = p.hash & bit; + if (b != runBit) { + runBit = b; + lastRun = p; + } + } + if (runBit == 0) + lo = lastRun; + else + hi = lastRun; + for (Node p = e; p != lastRun; p = p.next) { + int ph = p.hash & HASH_BITS; + Object pk = p.key, pv = p.val; + if ((ph & bit) == 0) + lo = new Node(ph, pk, pv, lo); + else + hi = new Node(ph, pk, pv, hi); + } + setTabAt(nextTab, i, lo); + setTabAt(nextTab, i + bit, hi); + } + + /** + * 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; + TreeBin lt = new TreeBin(); + TreeBin ht = new TreeBin(); + int lc = 0, hc = 0; + for (Node e = t.first; e != null; e = e.next) { + int h = e.hash & HASH_BITS; + Object k = e.key, v = e.val; + if ((h & bit) == 0) { + ++lc; + lt.putTreeNode(h, k, v); + } + else { + ++hc; + ht.putTreeNode(h, k, v); + } + } + Node ln, hn; // throw away trees if too small + if (lc <= (TREE_THRESHOLD >>> 1)) { + ln = null; + for (Node p = lt.first; p != null; p = p.next) + ln = new Node(p.hash, p.key, p.val, ln); + } + else + ln = new Node(MOVED, lt, null, null); + setTabAt(nextTab, i, ln); + if (hc <= (TREE_THRESHOLD >>> 1)) { + hn = null; + for (Node p = ht.first; p != null; p = p.next) + hn = new Node(p.hash, p.key, p.val, hn); + } + else + hn = new Node(MOVED, ht, null, null); + setTabAt(nextTab, i + bit, hn); + } + + /** + * Implementation for clear. Steps through each bin, removing all + * nodes. + */ + private final void internalClear() { + long delta = 0L; // negative number of deletions + int i = 0; + Node[] tab = table; + while (tab != null && i < tab.length) { + int fh; Object fk; + Node f = tabAt(tab, i); + if (f == null) + ++i; + 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) { + for (Node p = t.first; p != null; p = p.next) { + p.val = null; + --delta; + } + t.first = null; + t.root = null; + ++i; + } + } finally { + t.release(0); + } + } + else + tab = (Node[])fk; + } + else if ((fh & LOCKED) != 0) { + counter.add(delta); // opportunistically update count + delta = 0L; + f.tryAwaitLock(tab, i); + } + else if (f.casHash(fh, fh | LOCKED)) { + try { + if (tabAt(tab, i) == f) { + for (Node e = f; e != null; e = e.next) { + e.val = null; + --delta; + } + setTabAt(tab, i, null); + ++i; + } + } finally { + if (!f.casHash(fh | LOCKED, fh)) { + f.hash = fh; + synchronized (f) { f.notifyAll(); }; + } + } + } + } + if (delta != 0) + counter.add(delta); + } + /* ----------------Table Traversal -------------- */ /** @@ -969,26 +2138,28 @@ public class ConcurrentHashMapV8 * * At each step, the iterator snapshots the key ("nextKey") and * value ("nextVal") of a valid node (i.e., one that, at point of - * snapshot, has a nonnull user value). Because val fields can + * snapshot, has a non-null user value). Because val fields can * change (including to null, indicating deletion), field nextVal * might not be accurate at point of use, but still maintains the * weak consistency property of holding a value that was once * 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(); - * - * The iterator visits each valid node that was reachable upon - * iterator construction once. It might miss some that were added - * to a bin after the bin was visited, which is OK wrt consistency - * guarantees. Maintaining this property in the face of possible - * ongoing resizes requires a fair amount of bookkeeping state - * that is difficult to optimize away amidst volatile accesses. - * Even so, traversal maintains reasonable throughput. + * 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 + * were added to a bin after the bin was visited, which is OK wrt + * consistency guarantees. Maintaining this property in the face + * of possible ongoing resizes requires a fair amount of + * bookkeeping state that is difficult to optimize away amidst + * volatile accesses. Even so, traversal maintains reasonable + * throughput. * * Normally, iteration proceeds bin-by-bin traversing lists. * However, if the table has been resized, then all future steps @@ -997,11 +2168,9 @@ public class ConcurrentHashMapV8 * paranoically cope with potential sharing by users of iterators * 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.) */ - static class InternalIterator { + static class InternalIterator { + final ConcurrentHashMapV8 map; Node next; // the next entry to use Node last; // the last entry used Object nextKey; // cached key field of next @@ -1009,54 +2178,78 @@ 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; + InternalIterator(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; - next = null; - advance(); } - /** Advances next. See above for explanation. */ - final void advance() { + /** Creates iterator for clone() and split() methods. */ + InternalIterator(InternalIterator 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; + this.index = this.baseIndex = + (split) ? (it.baseLimit = (lo + hi + 1) >>> 1) : lo; + } + + /** + * 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; while (e == null) { // get to next non-null bin - Node[] t; int b, i, n; // checks must use locals + Node[] t; int b, i, n; Object ek; // checks must use locals if ((b = baseIndex) >= baseLimit || (i = index) < 0 || (t = tab) == null || i >= (n = t.length)) break outer; - else if ((e = tabAt(t, i)) != null && e.hash == MOVED) - tab = (Node[])e.key; // restarts due to null val - else // visit upper slots if present - index = (i += baseSize) < n ? i : (baseIndex = b + 1); + else if ((e = tabAt(t, i)) != null && e.hash == MOVED) { + if ((ek = e.key) instanceof TreeBin) + e = ((TreeBin)ek).first; + else { + tab = (Node[])ek; + continue; // restarts due to null val + } + } // visit upper slots if present + 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 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(); @@ -1090,7 +2283,7 @@ public class ConcurrentHashMapV8 public ConcurrentHashMapV8(Map m) { this.counter = new LongAdder(); this.sizeCtl = DEFAULT_CAPACITY; - putAll(m); + internalPutAll(m); } /** @@ -1137,8 +2330,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; } @@ -1212,11 +2405,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)) + InternalIterator it = new InternalIterator(this); + while ((v = it.advance()) != null) { + if (v == value || value.equals(v)) return true; - it.advance(); } return false; } @@ -1257,7 +2449,7 @@ public class ConcurrentHashMapV8 public V put(K key, V value) { if (key == null || value == null) throw new NullPointerException(); - return (V)internalPut(key, value, true); + return (V)internalPut(key, value); } /** @@ -1271,7 +2463,7 @@ public class ConcurrentHashMapV8 public V putIfAbsent(K key, V value) { if (key == null || value == null) throw new NullPointerException(); - return (V)internalPut(key, value, false); + return (V)internalPutIfAbsent(key, value); } /** @@ -1282,43 +2474,14 @@ public class ConcurrentHashMapV8 * @param m mappings to be stored in this map */ public void putAll(Map m) { - if (m == null) - throw new NullPointerException(); - /* - * If uninitialized, try to preallocate big enough table - */ - if (table == null) { - int size = m.size(); - int n = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : - tableSizeFor(size + (size >>> 1) + 1); - int sc = sizeCtl; - if (n < sc) - n = sc; - if (sc >= 0 && - UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) { - try { - if (table == null) { - table = new Node[n]; - sc = n - (n >>> 2) - 1; - } - } finally { - sizeCtl = sc; - } - } - } - for (Map.Entry e : m.entrySet()) { - Object ek = e.getKey(), ev = e.getValue(); - if (ek == null || ev == null) - throw new NullPointerException(); - internalPut(ek, ev, true); - } + internalPutAll(m); } /** * If the specified key is not already associated with a value, - * computes its value using the given mappingFunction, and if - * non-null, enters it into the map. This is equivalent to - * 
 {@code
+     * 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);
@@ -1326,13 +2489,17 @@ public class ConcurrentHashMapV8
      *   map.put(key, value);
      * return value;}

      *
-     * except that the action is performed atomically.  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
+     * except that the action is performed atomically.  If the
+     * 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() {
      *   public V map(K k) { return new Value(f(k)); }});}

@@ -1340,8 +2507,7 @@ public class ConcurrentHashMapV8
      * @param key key with which the specified value is to be associated
      * @param mappingFunction the function to compute a value
      * @return the current (existing or computed) value associated with
-     *         the specified key, or {@code null} if the computation
-     *         returned {@code 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
@@ -1350,47 +2516,59 @@ public class ConcurrentHashMapV8
      * @throws RuntimeException or Error if the mappingFunction does so,
      *         in which case the mapping is left unestablished
      */
+    @SuppressWarnings("unchecked")
     public V computeIfAbsent(K key, MappingFunction mappingFunction) {
         if (key == null || mappingFunction == null)
             throw new NullPointerException();
-        return internalCompute(key, mappingFunction, false);
+        return (V)internalComputeIfAbsent(key, mappingFunction);
     }
 
     /**
-     * Computes the value associated with the given key using the given
-     * mappingFunction, and if non-null, enters it into the map.  This
-     * is equivalent to
+     * 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
-     * value = mappingFunction.map(key);
-     * if (value != null)
-     *   map.put(key, value);
-     * else
-     *   value = map.get(key);
-     * return value;}

-     *
-     * except that the action is performed atomically.  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.
+     *   value = remappingFunction.remap(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: + * + * 
 {@code
+     * Map map = ...;
+     * final String msg = ...;
+     * map.compute(key, new RemappingFunction() {
+     *   public String remap(Key k, String v) {
+     *    return (v == null) ? msg : v + msg;});}}
* * @param key key with which the specified value is to be associated - * @param mappingFunction the function to compute a value - * @return the current value associated with - * the specified key, or {@code null} if the computation - * returned {@code null} and the value was not otherwise present - * @throws NullPointerException if the specified key or mappingFunction + * @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 mappingFunction does so, + * @throws RuntimeException or Error if the remappingFunction does so, * in which case the mapping is unchanged */ - public V compute(K key, MappingFunction mappingFunction) { - if (key == null || mappingFunction == null) + @SuppressWarnings("unchecked") + public V compute(K key, RemappingFunction remappingFunction) { + if (key == null || remappingFunction == null) throw new NullPointerException(); - return internalCompute(key, mappingFunction, true); + return (V)internalCompute(key, remappingFunction); } /** @@ -1538,6 +2716,33 @@ public class ConcurrentHashMapV8 } /** + * Returns a partionable iterator of the keys in this map. + * + * @return a partionable iterator of the keys in this map + */ + public Spliterator keySpliterator() { + return new KeyIterator(this); + } + + /** + * Returns a partionable iterator of the values in this map. + * + * @return a partionable iterator of the values in this map + */ + public Spliterator valueSpliterator() { + return new ValueIterator(this); + } + + /** + * Returns a partionable iterator of the entries in this map. + * + * @return a partionable 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()}. @@ -1546,10 +2751,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(); + InternalIterator it = new InternalIterator(this); + Object v; + while ((v = it.advance()) != null) { + h += it.nextKey.hashCode() ^ v.hashCode(); } return h; } @@ -1566,17 +2771,17 @@ public class ConcurrentHashMapV8 * @return a string representation of this map */ public String toString() { - InternalIterator it = new InternalIterator(table); + InternalIterator it = new InternalIterator(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(' '); } @@ -1599,13 +2804,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; + InternalIterator it = new InternalIterator(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; @@ -1621,97 +2825,105 @@ 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 InternalIterator + implements Spliterator, Enumeration { + KeyIterator(ConcurrentHashMapV8 map) { super(map); } + KeyIterator(InternalIterator 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 KeyIterator clone() { + if (last != null || (next != null && nextVal == null)) + throw new IllegalStateException(); + return new KeyIterator(this, false); } - - 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) + 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 InternalIterator + implements Spliterator, Enumeration { ValueIterator(ConcurrentHashMapV8 map) { super(map); } + ValueIterator(InternalIterator it, boolean split) { + super(it, split); + } + public ValueIterator split() { + if (last != null || (next != null && nextVal == null)) + throw new IllegalStateException(); + return new ValueIterator(this, true); + } + + public ValueIterator clone() { + if (last != null || (next != null && nextVal == null)) + throw new IllegalStateException(); + return new ValueIterator(this, false); + } @SuppressWarnings("unchecked") public final V next() { - if (next == null) + 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 InternalIterator + 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(InternalIterator it, boolean split) { + super(it, split); + } + public EntryIterator split() { + if (last != null || (next != null && nextVal == null)) + throw new IllegalStateException(); + return new EntryIterator(this, true); + } + public EntryIterator clone() { + if (last != null || (next != null && nextVal == null)) + throw new IllegalStateException(); + return new EntryIterator(this, false); } - } - - static final class SnapshotEntryIterator extends ViewIterator - implements Iterator> { - SnapshotEntryIterator(ConcurrentHashMapV8 map) { super(map); } @SuppressWarnings("unchecked") public final Map.Entry next() { - if (next == null) + 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(); } @@ -1726,29 +2938,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 a 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(); @@ -1759,25 +2955,10 @@ 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 { final ConcurrentHashMapV8 map; @@ -1787,7 +2968,7 @@ public class ConcurrentHashMapV8 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); @@ -1800,7 +2981,7 @@ public class ConcurrentHashMapV8 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) @@ -1827,7 +3008,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) @@ -1849,7 +3030,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; } @@ -1857,7 +3038,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(); @@ -1881,9 +3062,9 @@ public class ConcurrentHashMapV8 return true; } - public final boolean removeAll(Collection c) { + 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; @@ -1894,7 +3075,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; @@ -1909,13 +3090,9 @@ public class ConcurrentHashMapV8 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(); } @@ -1931,10 +3108,9 @@ public class ConcurrentHashMapV8 } static final class Values extends MapView - implements Collection { + 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); @@ -1950,9 +3126,6 @@ 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(); } @@ -1961,10 +3134,9 @@ public class ConcurrentHashMapV8 } } - static final class EntrySet extends MapView + static final class EntrySet extends MapView 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) && @@ -1973,7 +3145,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) && @@ -1981,13 +3152,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(); } @@ -2033,11 +3200,11 @@ public class ConcurrentHashMapV8 segments[i] = new Segment(LOAD_FACTOR); } s.defaultWriteObject(); - InternalIterator it = new InternalIterator(table); - while (it.next != null) { + InternalIterator it = new InternalIterator(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); @@ -2063,7 +3230,8 @@ public class ConcurrentHashMapV8 K k = (K) s.readObject(); V v = (V) s.readObject(); if (k != null && v != null) { - p = new Node(spread(k.hashCode()), k, v, p); + int h = spread(k.hashCode()); + p = new Node(h, k, v, p); ++size; } else @@ -2079,6 +3247,7 @@ public class ConcurrentHashMapV8 n = tableSizeFor(sz + (sz >>> 1) + 1); } int sc = sizeCtl; + boolean collide = false; if (n > sc && UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) { try { @@ -2089,21 +3258,36 @@ public class ConcurrentHashMapV8 while (p != null) { int j = p.hash & mask; Node next = p.next; - p.next = tabAt(tab, j); + Node q = p.next = tabAt(tab, j); setTabAt(tab, j, p); + if (!collide && q != null && q.hash == p.hash) + collide = true; p = next; } table = tab; counter.add(size); - sc = n - (n >>> 2) - 1; + sc = n - (n >>> 2); } } finally { sizeCtl = sc; } + if (collide) { // rescan and convert to TreeBins + Node[] tab = table; + for (int i = 0; i < tab.length; ++i) { + int c = 0; + for (Node e = tabAt(tab, i); e != null; e = e.next) { + if (++c > TREE_THRESHOLD && + (e.key instanceof Comparable)) { + replaceWithTreeBin(tab, i, e.key); + break; + } + } + } + } } if (!init) { // Can only happen if unsafely published. while (p != null) { - internalPut(p.key, p.val, true); + internalPut(p.key, p.val); p = p.next; } }