--- jsr166/src/jsr166e/ConcurrentHashMapV8.java 2013/06/19 17:00:58 1.104 +++ jsr166/src/jsr166e/ConcurrentHashMapV8.java 2013/07/19 19:34:43 1.111 @@ -299,7 +299,7 @@ public class ConcurrentHashMapV8 * because they have negative hash fields and null key and value * fields. (These special nodes are either uncommon or transient, * so the impact of carrying around some unused fields is - * insignficant.) + * insignificant.) * * The table is lazily initialized to a power-of-two size upon the * first insertion. Each bin in the table normally contains a @@ -462,7 +462,7 @@ public class ConcurrentHashMapV8 * * TreeBins also require an additional locking mechanism. While * list traversal is always possible by readers even during - * updates, tree traversal is not, mainly beause of tree-rotations + * updates, tree traversal is not, mainly because of tree-rotations * that may change the root node and/or its linkages. TreeBins * include a simple read-write lock mechanism parasitic on the * main bin-synchronization strategy: Structural adjustments @@ -568,9 +568,9 @@ public class ConcurrentHashMapV8 /* * Encodings for Node hash fields. See above for explanation. */ - static final int MOVED = 0x8fffffff; // (-1) hash for forwarding nodes - static final int TREEBIN = 0x80000000; // hash for heads of treea - static final int RESERVED = 0x80000001; // hash for transient reservations + static final int MOVED = -1; // hash for forwarding nodes + static final int TREEBIN = -2; // hash for roots of trees + static final int RESERVED = -3; // hash for transient reservations static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash /** Number of CPUS, to place bounds on some sizings */ @@ -589,7 +589,7 @@ public class ConcurrentHashMapV8 * Key-value entry. This class is never exported out as a * user-mutable Map.Entry (i.e., one supporting setValue; see * MapEntry below), but can be used for read-only traversals used - * in bulk tasks. Subclasses of Node with a negativehash field + * in bulk tasks. Subclasses of Node with a negative hash field * are special, and contain null keys and values (but are never * exported). Otherwise, keys and vals are never null. */ @@ -597,7 +597,7 @@ public class ConcurrentHashMapV8 final int hash; final K key; volatile V val; - Node next; + volatile Node next; Node(int hash, K key, V val, Node next) { this.hash = hash; @@ -722,8 +722,9 @@ public class ConcurrentHashMapV8 * errors by users, these checks must operate on local variables, * which accounts for some odd-looking inline assignments below. * Note that calls to setTabAt always occur within locked regions, - * and so do not need full volatile semantics, but still require - * ordering to maintain concurrent readability. + * and so in principle require only release ordering, not need + * full volatile semantics, but are currently coded as volatile + * writes to be conservative. */ @SuppressWarnings("unchecked") @@ -737,7 +738,7 @@ public class ConcurrentHashMapV8 } static final void setTabAt(Node[] tab, int i, Node v) { - U.putOrderedObject(tab, ((long)i << ASHIFT) + ABASE, v); + U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v); } /* ---------------- Fields -------------- */ @@ -2100,9 +2101,9 @@ public class ConcurrentHashMapV8 * * @param initialCapacity The implementation performs internal * sizing to accommodate this many elements. + * @return the new set * @throws IllegalArgumentException if the initial capacity of * elements is negative - * @return the new set * @since 1.8 */ public static KeySetView newKeySet(int initialCapacity) { @@ -2140,20 +2141,29 @@ public class ConcurrentHashMapV8 } Node find(int h, Object k) { - Node e; int n; - Node[] tab = nextTable; - if (k != null && tab != null && (n = tab.length) > 0 && - (e = tabAt(tab, (n - 1) & h)) != null) { - do { + // loop to avoid arbitrarily deep recursion on forwarding nodes + outer: for (Node[] tab = nextTable;;) { + Node e; int n; + if (k == null || tab == null || (n = tab.length) == 0 || + (e = tabAt(tab, (n - 1) & h)) == null) + return null; + for (;;) { int eh; K ek; if ((eh = e.hash) == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; - if (eh < 0) - return e.find(h, k); - } while ((e = e.next) != null); + if (eh < 0) { + if (e instanceof ForwardingNode) { + tab = ((ForwardingNode)e).nextTable; + continue outer; + } + else + return e.find(h, k); + } + if ((e = e.next) == null) + return null; + } } - return null; } } @@ -2327,10 +2337,11 @@ public class ConcurrentHashMapV8 int nextn = nextTab.length; ForwardingNode fwd = new ForwardingNode(nextTab); boolean advance = true; + boolean finishing = false; // to ensure sweep before committing nextTab for (int i = 0, bound = 0;;) { int nextIndex, nextBound, fh; Node f; while (advance) { - if (--i >= bound) + if (--i >= bound || finishing) advance = false; else if ((nextIndex = transferIndex) <= transferOrigin) { i = -1; @@ -2346,14 +2357,19 @@ public class ConcurrentHashMapV8 } } if (i < 0 || i >= n || i + n >= nextn) { + if (finishing) { + nextTable = null; + table = nextTab; + sizeCtl = (n << 1) - (n >>> 1); + return; + } for (int sc;;) { if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) { - if (sc == -1) { - nextTable = null; - table = nextTab; - sizeCtl = (n << 1) - (n >>> 1); - } - return; + if (sc != -1) + return; + finishing = advance = true; + i = n; // recheck before commit + break; } } } @@ -2395,6 +2411,10 @@ public class ConcurrentHashMapV8 else hn = new Node(ph, pk, pv, hn); } + setTabAt(nextTab, i, ln); + setTabAt(nextTab, i + n, hn); + setTabAt(tab, i, fwd); + advance = true; } else if (f instanceof TreeBin) { TreeBin t = (TreeBin)f; @@ -2426,13 +2446,11 @@ public class ConcurrentHashMapV8 (hc != 0) ? new TreeBin(lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new TreeBin(hi) : t; + setTabAt(nextTab, i, ln); + setTabAt(nextTab, i + n, hn); + setTabAt(tab, i, fwd); + advance = true; } - else - ln = hn = null; - setTabAt(nextTab, i, ln); - setTabAt(nextTab, i + n, hn); - setTabAt(tab, i, fwd); - advance = true; } } } @@ -2453,7 +2471,7 @@ public class ConcurrentHashMapV8 U.compareAndSwapInt(this, SIZECTL, sc, -2)) transfer(tab, null); } - else if ((b = tabAt(tab, index)) != null) { + else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { synchronized (b) { if (tabAt(tab, index) == b) { TreeNode hd = null, tl = null; @@ -2475,7 +2493,7 @@ public class ConcurrentHashMapV8 } /** - * Returns a list on non-TreeNodes replacing those in given list + * Returns a list on non-TreeNodes replacing those in given list. */ static Node untreeify(Node b) { Node hd = null, tl = null; @@ -2613,7 +2631,7 @@ public class ConcurrentHashMapV8 } /** - * Acquires write lock for tree restructuring + * Acquires write lock for tree restructuring. */ private final void lockRoot() { if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER)) @@ -2621,14 +2639,14 @@ public class ConcurrentHashMapV8 } /** - * Releases write lock for tree restructuring + * Releases write lock for tree restructuring. */ private final void unlockRoot() { lockState = 0; } /** - * Possibly blocks awaiting root lock + * Possibly blocks awaiting root lock. */ private final void contendedLock() { boolean waiting = false; @@ -2653,7 +2671,7 @@ public class ConcurrentHashMapV8 /** * Returns matching node or null if none. Tries to search - * using tree compareisons from root, but continues linear + * using tree comparisons from root, but continues linear * search when lock not available. */ final Node find(int h, Object k) { @@ -2751,7 +2769,7 @@ public class ConcurrentHashMapV8 * that are accessible independently of lock. So instead we * swap the tree linkages. * - * @return true if now too small so should be untreeified. + * @return true if now too small, so should be untreeified */ final boolean removeTreeNode(TreeNode p) { TreeNode next = (TreeNode)p.next; @@ -3146,7 +3164,7 @@ public class ConcurrentHashMapV8 /** * Base of key, value, and entry Iterators. Adds fields to - * Traverser to support iterator.remove + * Traverser to support iterator.remove. */ static class BaseIterator extends Traverser { final ConcurrentHashMapV8 map; @@ -3498,10 +3516,10 @@ public class ConcurrentHashMapV8 * of all (key, value) pairs * @since 1.8 */ - public double reduceToDoubleIn(long parallelismThreshold, - ObjectByObjectToDouble transformer, - double basis, - DoubleByDoubleToDouble reducer) { + public double reduceToDouble(long parallelismThreshold, + ObjectByObjectToDouble transformer, + double basis, + DoubleByDoubleToDouble reducer) { if (transformer == null || reducer == null) throw new NullPointerException(); return new MapReduceMappingsToDoubleTask @@ -5986,7 +6004,7 @@ public class ConcurrentHashMapV8 } /** - * Generates initial value for per-thread CounterHashCodes + * Generates initial value for per-thread CounterHashCodes. */ static final AtomicInteger counterHashCodeGenerator = new AtomicInteger();