changeset 8093:d48f0d4bdc57

Sync up some j.u.c collection classes.
author psandoz
date Fri, 12 Apr 2013 11:01:48 +0200
parents ef1694af47a2
children 34de21e14254
files src/share/classes/java/util/concurrent/ConcurrentHashMap.java src/share/classes/java/util/concurrent/ConcurrentSkipListSet.java src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java src/share/classes/java/util/concurrent/CopyOnWriteArraySet.java
diffstat 4 files changed, 90 insertions(+), 80 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/concurrent/ConcurrentHashMap.java	Fri Apr 12 10:36:04 2013 +0200
+++ b/src/share/classes/java/util/concurrent/ConcurrentHashMap.java	Fri Apr 12 11:01:48 2013 +0200
@@ -61,6 +61,8 @@
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.atomic.AtomicReference;
 import java.io.Serializable;
+import java.lang.reflect.Type;
+import java.lang.reflect.ParameterizedType;
 
 /**
  * A hash table supporting full concurrency of retrievals and
@@ -346,7 +348,7 @@
      * 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
+     * to O(log N).  Each search step in a TreeBin is at least 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
@@ -476,7 +478,7 @@
      * bin.  The value reflects the approximate break-even point for
      * using tree-based operations.
      */
-    private static final int TREE_THRESHOLD = 8;
+    private static final int TREE_THRESHOLD = 16;
 
     /**
      * Minimum number of rebinnings per transfer step. Ranges are
@@ -640,6 +642,32 @@
         }
     }
 
+
+    /**
+     * Returns a Class for the given object of the form "class C
+     * implements Comparable<C>", if one exists, else null.  See below
+     * for explanation.
+     */
+    static Class<?> comparableClassFor(Object x) {
+        Class<?> c, s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
+        if ((c = x.getClass()) == String.class) // bypass checks
+            return c;
+        if ((cmpc = Comparable.class).isAssignableFrom(c)) {
+            while (cmpc.isAssignableFrom(s = c.getSuperclass()))
+                c = s; // find topmost comparable class
+            if ((ts  = c.getGenericInterfaces()) != null) {
+                for (int i = 0; i < ts.length; ++i) {
+                    if (((t = ts[i]) instanceof ParameterizedType) &&
+                        ((p = (ParameterizedType)t).getRawType() == cmpc) &&
+                        (as = p.getActualTypeArguments()) != null &&
+                        as.length == 1 && as[0] == c) // type arg is c
+                        return c;
+                }
+            }
+        }
+        return null;
+    }
+
     /**
      * A specialized form of red-black tree for use in bins
      * whose size exceeds a threshold.
@@ -651,13 +679,12 @@
      * elements that are Comparable but not necessarily Comparable<T>
      * 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
+     * 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
      * (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
      * based in turn on Cormen, Leiserson, and Rivest "Introduction to
@@ -751,35 +778,34 @@
         }
 
         /**
+         * Returns the TreeNode (or null if not found) for the given
+         * key.  A front-end for recursive version.
+         */
+        final TreeNode<V> getTreeNode(int h, Object k) {
+            return getTreeNode(h, k, root, comparableClassFor(k));
+        }
+
+        /**
          * Returns the TreeNode (or null if not found) for the given key
          * starting at given root.
          */
         @SuppressWarnings("unchecked") final TreeNode<V> getTreeNode
-            (int h, Object k, TreeNode<V> p) {
-            Class<?> c = k.getClass();
+            (int h, Object k, TreeNode<V> p, Class<?> cc) {
             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) {
-                        if ((dir = (c == pc) ? 0 :
-                             c.getName().compareTo(pc.getName())) == 0) {
-                            TreeNode<V> r = null, pl, pr; // check both sides
-                            if ((pr = p.right) != null && h >= pr.hash &&
-                                (r = getTreeNode(h, k, pr)) != null)
-                                return r;
-                            else if ((pl = p.left) != null && h <= pl.hash)
-                                dir = -1;
-                            else // nothing there
-                                return null;
-                        }
-                    }
+                int dir, ph;  Object pk;
+                if ((ph = p.hash) != h)
+                    dir = (h < ph) ? -1 : 1;
+                else if ((pk = p.key) == k || k.equals(pk))
+                    return p;
+                else if (cc == null || comparableClassFor(pk) != cc ||
+                         (dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
+                    TreeNode<V> r, pr; // check both sides
+                    if ((pr = p.right) != null && h >= pr.hash &&
+                        (r = getTreeNode(h, k, pr, cc)) != null)
+                        return r;
+                    else // continue left
+                        dir = -1;
                 }
-                else
-                    dir = (h < ph) ? -1 : 1;
                 p = (dir > 0) ? p.right : p.left;
             }
             return null;
@@ -796,7 +822,7 @@
             for (Node<V> e = first; e != null; e = e.next) {
                 if (c <= 0 && compareAndSetState(c, c - 1)) {
                     try {
-                        r = getTreeNode(h, k, root);
+                        r = getTreeNode(h, k, root, comparableClassFor(k));
                     } finally {
                         releaseShared(0);
                     }
@@ -818,35 +844,25 @@
          */
         @SuppressWarnings("unchecked") final TreeNode<V> putTreeNode
             (int h, Object k, V v) {
-            Class<?> c = k.getClass();
+            Class<?> cc = comparableClassFor(k);
             TreeNode<V> pp = root, p = null;
             int dir = 0;
             while (pp != null) { // find existing node or leaf to insert at
-                int ph;  Object pk; Class<?> pc;
+                int ph; Object pk;
                 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) {
-                        TreeNode<V> s = null, r = null, pr;
-                        if ((dir = (c == pc) ? 0 :
-                             c.getName().compareTo(pc.getName())) == 0) {
-                            if ((pr = p.right) != null && h >= pr.hash &&
-                                (r = getTreeNode(h, k, pr)) != null)
-                                return r;
-                            else // continue left
-                                dir = -1;
-                        }
-                        else if ((pr = p.right) != null && h >= pr.hash)
-                            s = pr;
-                        if (s != null && (r = getTreeNode(h, k, s)) != null)
-                            return r;
-                    }
+                if ((ph = p.hash) != h)
+                    dir = (h < ph) ? -1 : 1;
+                else if ((pk = p.key) == k || k.equals(pk))
+                    return p;
+                else if (cc == null || comparableClassFor(pk) != cc ||
+                         (dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
+                    TreeNode<V> r, pr;
+                    if ((pr = p.right) != null && h >= pr.hash &&
+                        (r = getTreeNode(h, k, pr, cc)) != null)
+                        return r;
+                    else // continue left
+                        dir = -1;
                 }
-                else
-                    dir = (h < ph) ? -1 : 1;
                 pp = (dir > 0) ? p.right : p.left;
             }
 
@@ -1116,7 +1132,7 @@
      * only when locked.
      */
     private final void replaceWithTreeBin(Node<V>[] tab, int index, Object key) {
-        if (key instanceof Comparable) {
+        if (comparableClassFor(key) != null) {
             TreeBin<V> t = new TreeBin<V>();
             for (Node<V> e = tabAt(tab, index); e != null; e = e.next)
                 t.putTreeNode(e.hash, e.key, e.val);
@@ -1172,7 +1188,7 @@
                     try {
                         if (tabAt(tab, i) == f) {
                             validated = true;
-                            TreeNode<V> p = t.getTreeNode(h, k, t.root);
+                            TreeNode<V> p = t.getTreeNode(h, k);
                             if (p != null) {
                                 V pv = p.val;
                                 if (cv == null || cv == pv || cv.equals(pv)) {
@@ -1373,7 +1389,7 @@
                     try {
                         if (tabAt(tab, i) == f) {
                             len = 1;
-                            TreeNode<V> p = t.getTreeNode(h, k, t.root);
+                            TreeNode<V> p = t.getTreeNode(h, k);
                             if (p != null)
                                 val = p.val;
                             else if ((val = mf.apply(k)) != null) {
@@ -1480,7 +1496,7 @@
                     try {
                         if (tabAt(tab, i) == f) {
                             len = 1;
-                            TreeNode<V> p = t.getTreeNode(h, k, t.root);
+                            TreeNode<V> p = t.getTreeNode(h, k);
                             if (p == null && onlyIfPresent)
                                 break;
                             V pv = (p == null) ? null : p.val;
@@ -1579,7 +1595,7 @@
                     try {
                         if (tabAt(tab, i) == f) {
                             len = 1;
-                            TreeNode<V> p = t.getTreeNode(h, k, t.root);
+                            TreeNode<V> p = t.getTreeNode(h, k);
                             val = (p == null) ? v : mf.apply(p.val, v);
                             if (val != null) {
                                 if (p != null)
@@ -1680,7 +1696,7 @@
                             try {
                                 if (tabAt(tab, i) == f) {
                                     validated = true;
-                                    TreeNode<V> p = t.getTreeNode(h, k, t.root);
+                                    TreeNode<V> p = t.getTreeNode(h, k);
                                     if (p != null)
                                         p.val = v;
                                     else {
@@ -3209,7 +3225,7 @@
 
         public Iterator<Map.Entry<K,V>> iterator() { return this; }
 
-        public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
+        public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
             if (action == null) throw new NullPointerException();
             V v;
             while ((v = advanceValue()) != null)
@@ -5006,6 +5022,7 @@
         public final boolean add(Entry<K,V> e) {
             return map.internalPut(e.getKey(), e.getValue(), false) == null;
         }
+
         /**
          * Adds all of the mappings in the specified collection to this
          * set, as if by calling {@link #add(Map.Entry)} on each one.
--- a/src/share/classes/java/util/concurrent/ConcurrentSkipListSet.java	Fri Apr 12 10:36:04 2013 +0200
+++ b/src/share/classes/java/util/concurrent/ConcurrentSkipListSet.java	Fri Apr 12 11:01:48 2013 +0200
@@ -60,9 +60,9 @@
  * Iterators are <i>weakly consistent</i>, returning elements
  * reflecting the state of the set at some point at or since the
  * creation of the iterator.  They do <em>not</em> throw {@link
- * java.util.ConcurrentModificationException}, and may proceed concurrently
- * with other operations.  Ascending ordered views and their iterators are
- * faster than descending ones.
+ * java.util.ConcurrentModificationException}, and may proceed
+ * concurrently with other operations.  Ascending ordered views and
+ * their iterators are faster than descending ones.
  *
  * <p>Beware that, unlike in most collections, the {@code size}
  * method is <em>not</em> a constant-time operation. Because of the
@@ -390,14 +390,14 @@
     }
 
     /**
-     * @throws NoSuchElementException {@inheritDoc}
+     * @throws java.util.NoSuchElementException {@inheritDoc}
      */
     public E first() {
         return m.firstKey();
     }
 
     /**
-     * @throws NoSuchElementException {@inheritDoc}
+     * @throws java.util.NoSuchElementException {@inheritDoc}
      */
     public E last() {
         return m.lastKey();
--- a/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java	Fri Apr 12 10:36:04 2013 +0200
+++ b/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java	Fri Apr 12 11:01:48 2013 +0200
@@ -181,7 +181,7 @@
      * Tests for equality, coping with nulls.
      */
     private static boolean eq(Object o1, Object o2) {
-        return (o1 == null ? o2 == null : o1.equals(o2));
+        return (o1 == null) ? o2 == null : o1.equals(o2);
     }
 
     /**
@@ -610,17 +610,13 @@
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            // Copy while checking if already present.
-            // This wins in the most common case where it is not present
             Object[] elements = getArray();
             int len = elements.length;
-            Object[] newElements = new Object[len + 1];
             for (int i = 0; i < len; ++i) {
                 if (eq(e, elements[i]))
-                    return false; // exit, throwing away copy
-                else
-                    newElements[i] = elements[i];
+                    return false;
             }
+            Object[] newElements = Arrays.copyOf(elements, len + 1);
             newElements[len] = e;
             setArray(newElements);
             return true;
--- a/src/share/classes/java/util/concurrent/CopyOnWriteArraySet.java	Fri Apr 12 10:36:04 2013 +0200
+++ b/src/share/classes/java/util/concurrent/CopyOnWriteArraySet.java	Fri Apr 12 11:01:48 2013 +0200
@@ -281,10 +281,7 @@
      * @see #add(Object)
      */
     public boolean addAll(Collection<? extends E> c) {
-        if (c instanceof Set)
-            return al.addAll(c);
-        else
-            return al.addAllAbsent(c) > 0;
+        return al.addAllAbsent(c) > 0;
     }
 
     /**