--- jsr166/src/jsr166e/ConcurrentHashMapV8.java 2013/07/19 19:34:43 1.111 +++ jsr166/src/jsr166e/ConcurrentHashMapV8.java 2013/07/20 16:50:04 1.112 @@ -12,6 +12,7 @@ import java.io.ObjectStreamField; import java.io.Serializable; import java.lang.reflect.ParameterizedType; import java.lang.reflect.Type; +import java.util.AbstractMap; import java.util.Arrays; import java.util.Collection; import java.util.Comparator; @@ -218,7 +219,7 @@ import java.util.concurrent.locks.Reentr * @param the type of keys maintained by this map * @param the type of mapped values */ -public class ConcurrentHashMapV8 +public class ConcurrentHashMapV8 extends AbstractMap implements ConcurrentMap, Serializable { private static final long serialVersionUID = 7249069246763182397L; @@ -446,16 +447,18 @@ public class ConcurrentHashMapV8 * related operations (which is the main reason we cannot use * existing collections such as TreeMaps). TreeBins contain * Comparable elements, but may contain others, as well as - * elements that are Comparable but not necessarily Comparable - * for the same T, so we cannot invoke compareTo among them. To - * handle this, the tree is ordered primarily by hash value, then - * by Comparable.compareTo order if applicable. On lookup at a - * node, if elements are not comparable or compare as 0 then 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 + * elements that are Comparable but not necessarily Comparable for + * the same T, so we cannot invoke compareTo among them. To handle + * this, the tree is ordered primarily by hash value, then by + * Comparable.compareTo order if applicable. On lookup at a node, + * if elements are not comparable or compare as 0 then 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.) On insertion, to keep a total ordering (or as + * close as is required here) across rebalancings, we compare + * classes and identityHashCodes as tie-breakers. 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). @@ -485,6 +488,10 @@ public class ConcurrentHashMapV8 * unused "Segment" class that is instantiated in minimal form * only when serializing. * + * Also, solely for compatibility with previous versions of this + * class, it extends AbstractMap, even though all of its methods + * are overridden, so it is just useless baggage. + * * This file is organized to make things a little easier to follow * while reading than they might otherwise: First the main static * declarations and utilities, then fields, then main public @@ -2546,19 +2553,18 @@ public class ConcurrentHashMapV8 p = pr; else if ((pk = p.key) == k || (pk != null && k.equals(pk))) return p; - else if (pl == null && pr == null) - break; + else if (pl == null) + p = pr; + else if (pr == null) + p = pl; else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0) p = (dir < 0) ? pl : pr; - else if (pl == null) - p = pr; - else if (pr == null || - (q = pr.findTreeNode(h, k, kc)) == null) - p = pl; - else + else if ((q = pr.findTreeNode(h, k, kc)) != null) return q; + else + p = pl; } while (p != null); } return null; @@ -2585,6 +2591,23 @@ public class ConcurrentHashMapV8 static final int READER = 4; // increment value for setting read lock /** + * Tie-breaking utility for ordering insertions when equal + * hashCodes and non-comparable. We don't require a total + * order, just a consistent insertion rule to maintain + * equivalence across rebalancings. Tie-breaking further than + * necessary simplifies testing a bit. + */ + static int tieBreakOrder(Object a, Object b) { + int d; + if (a == null || b == null || + (d = a.getClass().getName(). + compareTo(b.getClass().getName())) == 0) + d = (System.identityHashCode(a) <= System.identityHashCode(b) ? + -1 : 1); + return d; + } + + /** * Creates bin with initial set of nodes headed by b. */ TreeBin(TreeNode b) { @@ -2600,21 +2623,21 @@ public class ConcurrentHashMapV8 r = x; } else { - Object key = x.key; - int hash = x.hash; + K k = x.key; + int h = x.hash; Class kc = null; for (TreeNode p = r;;) { int dir, ph; - if ((ph = p.hash) > hash) + K pk = p.key; + if ((ph = p.hash) > h) dir = -1; - else if (ph < hash) + else if (ph < h) dir = 1; - else if ((kc != null || - (kc = comparableClassFor(key)) != null)) - dir = compareComparables(kc, key, p.key); - else - dir = 0; - TreeNode xp = p; + else if ((kc == null && + (kc = comparableClassFor(k)) == null) || + (dir = compareComparables(kc, k, pk)) == 0) + dir = tieBreakOrder(k, pk); + TreeNode xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) @@ -2628,6 +2651,7 @@ public class ConcurrentHashMapV8 } } this.root = r; + assert checkInvariants(root); } /** @@ -2674,7 +2698,7 @@ public class ConcurrentHashMapV8 * using tree comparisons from root, but continues linear * search when lock not available. */ - final Node find(int h, Object k) { +final Node find(int h, Object k) { if (k != null) { for (Node e = first; e != null; e = e.next) { int s; K ek; @@ -2711,8 +2735,9 @@ public class ConcurrentHashMapV8 */ final TreeNode putTreeVal(int h, K k, V v) { Class kc = null; + boolean searched = false; for (TreeNode p = root;;) { - int dir, ph; K pk; TreeNode q, pr; + int dir, ph; K pk; if (p == null) { first = root = new TreeNode(h, k, v, null, null); break; @@ -2726,21 +2751,25 @@ public class ConcurrentHashMapV8 else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) { - if (p.left == null) - dir = 1; - else if ((pr = p.right) == null || - (q = pr.findTreeNode(h, k, kc)) == null) - dir = -1; - else - return q; + if (!searched) { + TreeNode q, ch; + searched = true; + if (((ch = p.left) != null && + (q = ch.findTreeNode(h, k, kc)) != null) || + ((ch = p.right) != null && + (q = ch.findTreeNode(h, k, kc)) != null)) + return q; + } + dir = tieBreakOrder(k, pk); } + TreeNode xp = p; - if ((p = (dir < 0) ? p.left : p.right) == null) { + if ((p = (dir <= 0) ? p.left : p.right) == null) { TreeNode x, f = first; first = x = new TreeNode(h, k, v, f, xp); if (f != null) f.prev = x; - if (dir < 0) + if (dir <= 0) xp.left = x; else xp.right = x;