changeset 8911:9a719172fc80

Sync docs/code of classes from 166.
author psandoz
date Thu, 27 Jun 2013 15:09:09 +0200
parents 5acf515f2c63
children da84789ac473
files src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java src/share/classes/java/util/concurrent/CopyOnWriteArraySet.java
diffstat 3 files changed, 784 insertions(+), 1245 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java	Thu Jun 27 14:34:57 2013 +0200
+++ b/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java	Thu Jun 27 15:09:09 2013 +0200
@@ -34,12 +34,25 @@
  */
 
 package java.util.concurrent;
-import java.util.*;
-import java.util.stream.Stream;
+import java.util.AbstractCollection;
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NavigableSet;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.SortedMap;
 import java.util.Spliterator;
+import java.util.function.BiFunction;
 import java.util.function.Consumer;
+import java.util.function.BiConsumer;
 import java.util.function.Function;
-import java.util.function.BiFunction;
 
 /**
  * A scalable concurrent {@link ConcurrentNavigableMap} implementation.
@@ -56,9 +69,9 @@
  * multiple threads.  Iterators are <i>weakly consistent</i>, returning
  * elements reflecting the state of the map at some point at or since
  * the creation of the iterator.  They do <em>not</em> throw {@link
- * ConcurrentModificationException}, and may proceed concurrently with
- * other operations. Ascending key ordered views and their iterators
- * are faster than descending ones.
+ * java.util.ConcurrentModificationException ConcurrentModificationException},
+ * and may proceed concurrently with other operations. Ascending key ordered
+ * views and their iterators are faster than descending ones.
  *
  * <p>All {@code Map.Entry} pairs returned by methods in this class
  * and its views represent snapshots of mappings at the time they were
@@ -261,7 +274,7 @@
      *
      * Indexing uses skip list parameters that maintain good search
      * performance while using sparser-than-usual indices: The
-     * hardwired parameters k=1, p=0.5 (see method addIndex) mean
+     * hardwired parameters k=1, p=0.5 (see method doPut) mean
      * that about one-quarter of the nodes have indices. Of those that
      * do, half have one level, a quarter have two, and so on (see
      * Pugh's Skip List Cookbook, sec 3.4).  The expected total space
@@ -306,16 +319,12 @@
      *
      * A previous version of this class wrapped non-comparable keys
      * with their comparators to emulate Comparables when using
-     * comparators vs Comparables.  This saved the need to choose
-     * among the unpleasant options of either possibly re-reading a
-     * comparator on each comparison (which suffers when among all of
-     * the volatile read snapshots) versus code duplication, at the
-     * cost of usually requiring an object construction per operation
-     * when not naturally ordered. However, as usage evolves, use of
-     * comparators has become more common, so we have to settle for
-     * code duplication as the lesser evil. Thus, there are "xxxCmp"
-     * versions of many of the xxx methods, all bundled later in this
-     * file.
+     * comparators vs Comparables.  However, JVMs now appear to better
+     * handle infusing comparator-vs-comparable choice into search
+     * loops. Static method cpr(comparator, x, y) is used for all
+     * comparisons, which works well as long as the comparator
+     * argument is set up outside of loops (thus sometimes passed as
+     * an argument to internal methods) to avoid field re-reads.
      *
      * For explanation of algorithms sharing at least a couple of
      * features with this one, see Mikhail Fomitchev's thesis
@@ -355,14 +364,15 @@
     private transient volatile HeadIndex<K,V> head;
 
     /**
-     * The comparator used to maintain order in this map, or null
-     * if using natural ordering.
+     * The comparator used to maintain order in this map, or null if
+     * using natural ordering.  (Non-private to simplify access in
+     * nested classes.)
      * @serial
      */
-    private final Comparator<? super K> comparator;
+    final Comparator<? super K> comparator;
 
     /** Lazily initialized key set */
-    private transient KeySetView<K,V> keySet;
+    private transient KeySet<K> keySet;
     /** Lazily initialized entry set */
     private transient EntrySet<K,V> entrySet;
     /** Lazily initialized values collection */
@@ -375,7 +385,7 @@
      * clear, readObject. and ConcurrentSkipListSet.clone.
      * (Note that comparator must be separately initialized.)
      */
-    final void initialize() {
+    private void initialize() {
         keySet = null;
         entrySet = null;
         values = null;
@@ -486,7 +496,7 @@
              */
             if (f == next && this == b.next) {
                 if (f == null || f.value != f) // not already marked
-                    appendMarker(f);
+                    casNext(f, new Node<K,V>(f));
                 else
                     b.casNext(this, f.next);
             }
@@ -496,14 +506,14 @@
          * Returns value if this node contains a valid key-value pair,
          * else null.
          * @return this node's value if it isn't a marker or header or
-         * is deleted, else null.
+         * is deleted, else null
          */
-        @SuppressWarnings("unchecked")
         V getValidValue() {
             Object v = value;
             if (v == this || v == BASE_HEADER)
                 return null;
-            return (V)v;
+            @SuppressWarnings("unchecked") V vv = (V)v;
+            return vv;
         }
 
         /**
@@ -512,10 +522,11 @@
          * @return new entry or null
          */
         AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
-            V v = getValidValue();
-            if (v == null)
+            Object v = value;
+            if (v == null || v == this || v == BASE_HEADER)
                 return null;
-            return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
+            @SuppressWarnings("unchecked") V vv = (V)v;
+            return new AbstractMap.SimpleImmutableEntry<K,V>(key, vv);
         }
 
         // UNSAFE mechanics
@@ -598,7 +609,7 @@
          * @return true if successful
          */
         final boolean unlink(Index<K,V> succ) {
-            return !indexesDeletedNode() && casRight(succ, succ.right);
+            return node.value != null && casRight(succ, succ.right);
         }
 
         // Unsafe mechanics
@@ -632,39 +643,12 @@
     /* ---------------- Comparison utilities -------------- */
 
     /**
-     * Compares using comparator or natural ordering. Used in cases
-     * where it isn't worthwhile to use multiple code paths.
+     * Compares using comparator or natural ordering if null.
+     * Called only by methods that have performed required type checks.
      */
-    @SuppressWarnings("unchecked")
-    int compare(K k1, K k2) throws ClassCastException {
-        Comparator<? super K> cmp = comparator;
-        if (cmp != null)
-            return cmp.compare(k1, k2);
-        else
-            return ((Comparable<? super K>)k1).compareTo(k2);
-    }
-
-    /**
-     * Returns true if given key greater than or equal to least and
-     * strictly less than fence, bypassing either test if least or
-     * fence are null. Needed mainly in submap operations.
-     */
-    boolean inHalfOpenRange(K key, K least, K fence) {
-        if (key == null)
-            throw new NullPointerException();
-        return ((least == null || compare(key, least) >= 0) &&
-                (fence == null || compare(key, fence) <  0));
-    }
-
-    /**
-     * Returns true if given key greater than or equal to least and less
-     * or equal to fence. Needed mainly in submap operations.
-     */
-    boolean inOpenRange(K key, K least, K fence) {
-        if (key == null)
-            throw new NullPointerException();
-        return ((least == null || compare(key, least) >= 0) &&
-                (fence == null || compare(key, fence) <= 0));
+    @SuppressWarnings({"unchecked", "rawtypes"})
+    static final int cpr(Comparator c, Object x, Object y) {
+        return (c != null) ? c.compare(x, y) : ((Comparable)x).compareTo(y);
     }
 
     /* ---------------- Traversal -------------- */
@@ -677,13 +661,11 @@
      * @param key the key
      * @return a predecessor of key
      */
-    private Node<K,V> findPredecessor(Comparable<? super K> key) {
+    private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
         if (key == null)
             throw new NullPointerException(); // don't postpone errors
         for (;;) {
-            Index<K,V> q = head;
-            Index<K,V> r = q.right;
-            for (;;) {
+            for (Index<K,V> q = head, r = q.right, d;;) {
                 if (r != null) {
                     Node<K,V> n = r.node;
                     K k = n.key;
@@ -693,18 +675,16 @@
                         r = q.right;         // reread r
                         continue;
                     }
-                    if (key.compareTo(k) > 0) {
+                    if (cpr(cmp, key, k) > 0) {
                         q = r;
                         r = r.right;
                         continue;
                     }
                 }
-                Index<K,V> d = q.down;
-                if (d != null) {
-                    q = d;
-                    r = d.right;
-                } else
+                if ((d = q.down) == null)
                     return q.node;
+                q = d;
+                r = d.right;
             }
         }
     }
@@ -753,149 +733,124 @@
      * @param key the key
      * @return node holding key, or null if no such
      */
-    private Node<K,V> findNode(Comparable<? super K> key) {
+    private Node<K,V> findNode(Object key) {
         if (key == null)
             throw new NullPointerException(); // don't postpone errors
-        for (;;) {
-            Node<K,V> b = findPredecessor(key);
-            Node<K,V> n = b.next;
-            for (;;) {
+        Comparator<? super K> cmp = comparator;
+        outer: for (;;) {
+            for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
+                Object v; int c;
                 if (n == null)
-                    return null;
+                    break outer;
                 Node<K,V> f = n.next;
                 if (n != b.next)                // inconsistent read
                     break;
-                Object v = n.value;
-                if (v == null) {                // n is deleted
+                if ((v = n.value) == null) {    // n is deleted
                     n.helpDelete(b, f);
                     break;
                 }
-                if (v == n || b.value == null)  // b is deleted
+                if (b.value == null || v == n)  // b is deleted
                     break;
-                int c = key.compareTo(n.key);
-                if (c == 0)
+                if ((c = cpr(cmp, key, n.key)) == 0)
                     return n;
                 if (c < 0)
-                    return null;
+                    break outer;
                 b = n;
                 n = f;
             }
         }
+        return null;
     }
 
     /**
      * Gets value for key. Almost the same as findNode, but returns
      * the found value (to avoid retries during re-reads)
      *
-     * @param okey the key
+     * @param key the key
      * @return the value, or null if absent
      */
-    private V doGet(Object okey) {
-        if (okey == null)
+    private V doGet(Object key) {
+        if (key == null)
             throw new NullPointerException();
-        @SuppressWarnings("unchecked") Comparable<? super K> key =
-            (Comparable<? super K>)okey;
-        for (;;) {
-            Node<K,V> b = findPredecessor(key);
-            Node<K,V> n = b.next;
-            for (;;) {
+        Comparator<? super K> cmp = comparator;
+        outer: for (;;) {
+            for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
+                Object v; int c;
                 if (n == null)
-                    return null;
+                    break outer;
                 Node<K,V> f = n.next;
                 if (n != b.next)                // inconsistent read
                     break;
-                Object v = n.value;
-                if (v == null) {                // n is deleted
+                if ((v = n.value) == null) {    // n is deleted
                     n.helpDelete(b, f);
                     break;
                 }
-                if (v == n || b.value == null)  // b is deleted
+                if (b.value == null || v == n)  // b is deleted
                     break;
-                @SuppressWarnings("unchecked") V vv = (V)v;
-                int c = key.compareTo(n.key);
-                if (c == 0)
+                if ((c = cpr(cmp, key, n.key)) == 0) {
+                    @SuppressWarnings("unchecked") V vv = (V)v;
                     return vv;
+                }
                 if (c < 0)
-                    return null;
+                    break outer;
                 b = n;
                 n = f;
             }
         }
+        return null;
     }
 
-
     /* ---------------- Insertion -------------- */
 
     /**
      * Main insertion method.  Adds element if not present, or
      * replaces value if present and onlyIfAbsent is false.
-     * @param kkey the key
+     * @param key the key
      * @param value the value that must be associated with key
      * @param onlyIfAbsent if should not insert if already present
      * @return the old value, or null if newly inserted
      */
-    private V doPut(K kkey, V value, boolean onlyIfAbsent) {
-        if (kkey == null)
+    private V doPut(K key, V value, boolean onlyIfAbsent) {
+        Node<K,V> z;             // added node
+        if (key == null)
             throw new NullPointerException();
-        @SuppressWarnings("unchecked") Comparable<? super K> key =
-            (Comparable<? super K>)kkey;
-        for (;;) {
-            Node<K,V> b = findPredecessor(key);
-            Node<K,V> n = b.next;
-            for (;;) {
+        Comparator<? super K> cmp = comparator;
+        outer: for (;;) {
+            for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
                 if (n != null) {
+                    Object v; int c;
                     Node<K,V> f = n.next;
                     if (n != b.next)               // inconsistent read
                         break;
-                    Object v = n.value;
-                    if (v == null) {               // n is deleted
+                    if ((v = n.value) == null) {   // n is deleted
                         n.helpDelete(b, f);
                         break;
                     }
-                    if (v == n || b.value == null) // b is deleted
+                    if (b.value == null || v == n) // b is deleted
                         break;
-                    int c = key.compareTo(n.key);
-                    if (c > 0) {
+                    if ((c = cpr(cmp, key, n.key)) > 0) {
                         b = n;
                         n = f;
                         continue;
                     }
-
                     if (c == 0) {
-                        @SuppressWarnings("unchecked") V vv = (V)v;
-                        if (onlyIfAbsent || n.casValue(vv, value))
+                        if (onlyIfAbsent || n.casValue(v, value)) {
+                            @SuppressWarnings("unchecked") V vv = (V)v;
                             return vv;
-                        else
-                            break; // restart if lost race to replace value
+                        }
+                        break; // restart if lost race to replace value
                     }
                     // else c < 0; fall through
                 }
 
-                Node<K,V> z = new Node<K,V>(kkey, value, n);
+                z = new Node<K,V>(key, value, n);
                 if (!b.casNext(n, z))
                     break;         // restart if lost race to append to b
-                addIndex(kkey, z);
-                return null;
+                break outer;
             }
         }
-    }
 
-    /**
-     * Adds zero or more index nodes for the given key and node.
-     * Shared by plain and Cmp versions of put
-     */
-    @SuppressWarnings("unchecked")
-    private void addIndex(K key, Node<K,V> z) {
-        if (key == null || z == null) // don't postpone errors
-            throw new NullPointerException();
-        int rnd; // generate a random level
-        Thread thread = Thread.currentThread();
-        if ((rnd = UNSAFE.getInt(thread, SECONDARY)) == 0)  // initialize
-            rnd = ThreadLocalRandom.current().nextInt();
-        rnd ^= rnd << 13;   // xorshift
-        rnd ^= rnd >>> 17;
-        rnd ^= rnd << 5;
-        UNSAFE.putInt(thread, SECONDARY, rnd);
+        int rnd = ThreadLocalRandom.nextSecondarySeed();
         if ((rnd & 0x80000001) == 0) { // test highest and lowest bits
             int level = 1, max;
             while (((rnd >>>= 1) & 1) != 0)
@@ -908,7 +863,8 @@
             }
             else { // try to grow by one level
                 level = max + 1; // hold in array and later pick the one to use
-                Index<K,V>[] idxs = (Index<K,V>[])new Index<?,?>[level+1];
+                @SuppressWarnings("unchecked")Index<K,V>[] idxs =
+                    (Index<K,V>[])new Index<?,?>[level+1];
                 for (int i = 1; i <= level; ++i)
                     idxs[i] = idx = new Index<K,V>(z, idx, null);
                 for (;;) {
@@ -927,21 +883,16 @@
                     }
                 }
             }
-            Comparator<? super K> cmp = comparator;
-            for (int insertionLevel = level;;) { // find insertion points; splice
+            // find insertion points and splice in
+            splice: for (int insertionLevel = level;;) {
                 int j = h.level;
-                Index<K,V> q = h;
-                Index<K,V> r = q.right;
-                Index<K,V> t = idx;
-                for (;;) {
+                for (Index<K,V> q = h, r = q.right, t = idx;;) {
                     if (q == null || t == null)
-                        return;
+                        break splice;
                     if (r != null) {
                         Node<K,V> n = r.node;
                         // compare before deletion check avoids needing recheck
-                        int c = (cmp == null) ?
-                            ((Comparable<? super K>)key).compareTo(n.key) :
-                            cmp.compare(key, n.key);
+                        int c = cpr(cmp, key, n.key);
                         if (n.value == null) {
                             if (!q.unlink(r))
                                 break;
@@ -959,14 +910,11 @@
                         if (!q.link(r, t))
                             break; // restart
                         if (t.node.value == null) {
-                            if (cmp == null) // node deleted; clean up
-                                findNode((Comparable<? super K>)key);
-                            else
-                                findNodeCmp(cmp, key);
-                            return;
+                            findNode(key);
+                            break splice;
                         }
                         if (--insertionLevel == 0)
-                            return;
+                            break splice;
                     }
 
                     if (--j >= insertionLevel && j < level)
@@ -976,6 +924,7 @@
                 }
             }
         }
+        return null;
     }
 
     /* ---------------- Deletion -------------- */
@@ -994,48 +943,44 @@
      * search for it, and we'd like to ensure lack of garbage
      * retention, so must call to be sure.
      *
-     * @param okey the key
+     * @param key the key
      * @param value if non-null, the value that must be
      * associated with key
      * @return the node, or null if not found
      */
-    final V doRemove(Object okey, Object value) {
-        if (okey == null)
+    final V doRemove(Object key, Object value) {
+        if (key == null)
             throw new NullPointerException();
-        @SuppressWarnings("unchecked") Comparable<? super K> key =
-            (Comparable<? super K>)okey;
-        for (;;) {
-            Node<K,V> b = findPredecessor(key);
-            Node<K,V> n = b.next;
-            for (;;) {
+        Comparator<? super K> cmp = comparator;
+        outer: for (;;) {
+            for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
+                Object v; int c;
                 if (n == null)
-                    return null;
+                    break outer;
                 Node<K,V> f = n.next;
                 if (n != b.next)                    // inconsistent read
                     break;
-                Object v = n.value;
-                if (v == null) {                    // n is deleted
+                if ((v = n.value) == null) {        // n is deleted
                     n.helpDelete(b, f);
                     break;
                 }
-                if (v == n || b.value == null)      // b is deleted
+                if (b.value == null || v == n)      // b is deleted
                     break;
-                int c = key.compareTo(n.key);
-                if (c < 0)
-                    return null;
+                if ((c = cpr(cmp, key, n.key)) < 0)
+                    break outer;
                 if (c > 0) {
                     b = n;
                     n = f;
                     continue;
                 }
                 if (value != null && !value.equals(v))
-                    return null;
+                    break outer;
                 if (!n.casValue(v, null))
                     break;
                 if (!n.appendMarker(f) || !b.casNext(n, f))
-                    findNode(key);                  // Retry via findNode
+                    findNode(key);                  // retry via findNode
                 else {
-                    findPredecessor(key);           // Clean index
+                    findPredecessor(key, cmp);      // clean index
                     if (head.right == null)
                         tryReduceLevel();
                 }
@@ -1043,6 +988,7 @@
                 return vv;
             }
         }
+        return null;
     }
 
     /**
@@ -1086,11 +1032,9 @@
      * Specialized variant of findNode to get first valid node.
      * @return first node or null if empty
      */
-    Node<K,V> findFirst() {
-        for (;;) {
-            Node<K,V> b = head.node;
-            Node<K,V> n = b.next;
-            if (n == null)
+    final Node<K,V> findFirst() {
+        for (Node<K,V> b, n;;) {
+            if ((n = (b = head.node).next) == null)
                 return null;
             if (n.value != null)
                 return n;
@@ -1102,11 +1046,9 @@
      * Removes first entry; returns its snapshot.
      * @return null if empty, else snapshot of first entry
      */
-    Map.Entry<K,V> doRemoveFirstEntry() {
-        for (;;) {
-            Node<K,V> b = head.node;
-            Node<K,V> n = b.next;
-            if (n == null)
+    private Map.Entry<K,V> doRemoveFirstEntry() {
+        for (Node<K,V> b, n;;) {
+            if ((n = (b = head.node).next) == null)
                 return null;
             Node<K,V> f = n.next;
             if (n != b.next)
@@ -1131,8 +1073,7 @@
      */
     private void clearIndexToFirst() {
         for (;;) {
-            Index<K,V> q = head;
-            for (;;) {
+            for (Index<K,V> q = head;;) {
                 Index<K,V> r = q.right;
                 if (r != null && r.indexesDeletedNode() && !q.unlink(r))
                     break;
@@ -1150,8 +1091,7 @@
      * Specialized variant of doRemove.
      * @return null if empty, else snapshot of last entry
      */
-    @SuppressWarnings("unchecked")
-    Map.Entry<K,V> doRemoveLastEntry() {
+    private Map.Entry<K,V> doRemoveLastEntry() {
         for (;;) {
             Node<K,V> b = findPredecessorOfLast();
             Node<K,V> n = b.next;
@@ -1170,7 +1110,7 @@
                     n.helpDelete(b, f);
                     break;
                 }
-                if (v == n || b.value == null)      // b is deleted
+                if (b.value == null || v == n)      // b is deleted
                     break;
                 if (f != null) {
                     b = n;
@@ -1180,22 +1120,15 @@
                 if (!n.casValue(v, null))
                     break;
                 K key = n.key;
-                Comparator<? super K> cmp = comparator;
-                if (!n.appendMarker(f) || !b.casNext(n, f)) {
-                    if (cmp == null)                // Retry via findNode
-                        findNode((Comparable<? super K>)key);
-                    else
-                        findNodeCmp(cmp, key);
-                }
-                else {                              // Clean index
-                    if (cmp == null)
-                        findPredecessor((Comparable<? super K>)key);
-                    else
-                        findPredecessorCmp(cmp, key);
+                if (!n.appendMarker(f) || !b.casNext(n, f))
+                    findNode(key);                  // retry via findNode
+                else {                              // clean index
+                    findPredecessor(key, comparator);
                     if (head.right == null)
                         tryReduceLevel();
                 }
-                return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v);
+                @SuppressWarnings("unchecked") V vv = (V)v;
+                return new AbstractMap.SimpleImmutableEntry<K,V>(key, vv);
             }
         }
     }
@@ -1206,7 +1139,7 @@
      * Specialized version of find to get last valid node.
      * @return last node or null if empty
      */
-    Node<K,V> findLast() {
+    final Node<K,V> findLast() {
         /*
          * findPredecessor can't be used to traverse index level
          * because this doesn't use comparisons.  So traversals of
@@ -1225,9 +1158,7 @@
             } else if ((d = q.down) != null) {
                 q = d;
             } else {
-                Node<K,V> b = q.node;
-                Node<K,V> n = b.next;
-                for (;;) {
+                for (Node<K,V> b = q.node, n = b.next;;) {
                     if (n == null)
                         return b.isBaseHeader() ? null : b;
                     Node<K,V> f = n.next;            // inconsistent read
@@ -1238,7 +1169,7 @@
                         n.helpDelete(b, f);
                         break;
                     }
-                    if (v == n || b.value == null)   // b is deleted
+                    if (b.value == null || v == n)      // b is deleted
                         break;
                     b = n;
                     n = f;
@@ -1257,8 +1188,7 @@
      */
     private Node<K,V> findPredecessorOfLast() {
         for (;;) {
-            Index<K,V> q = head;
-            for (;;) {
+            for (Index<K,V> q = head;;) {
                 Index<K,V> d, r;
                 if ((r = q.right) != null) {
                     if (r.indexesDeletedNode()) {
@@ -1289,30 +1219,28 @@
 
     /**
      * Utility for ceiling, floor, lower, higher methods.
-     * @param kkey the key
+     * @param key the key
      * @param rel the relation -- OR'ed combination of EQ, LT, GT
      * @return nearest node fitting relation, or null if no such
      */
-    Node<K,V> doFindNear(K kkey, int rel) {
-        @SuppressWarnings("unchecked") Comparable<? super K> key =
-            (Comparable<? super K>)kkey;
+    final Node<K,V> findNear(K key, int rel, Comparator<? super K> cmp) {
+        if (key == null)
+            throw new NullPointerException();
         for (;;) {
-            Node<K,V> b = findPredecessor(key);
-            Node<K,V> n = b.next;
-            for (;;) {
+            for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
+                Object v;
                 if (n == null)
                     return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
                 Node<K,V> f = n.next;
                 if (n != b.next)                  // inconsistent read
                     break;
-                Object v = n.value;
-                if (v == null) {                  // n is deleted
+                if ((v = n.value) == null) {      // n is deleted
                     n.helpDelete(b, f);
                     break;
                 }
-                if (v == n || b.value == null)    // b is deleted
+                if (b.value == null || v == n)      // b is deleted
                     break;
-                int c = key.compareTo(n.key);
+                int c = cpr(cmp, key, n.key);
                 if ((c == 0 && (rel & EQ) != 0) ||
                     (c <  0 && (rel & LT) == 0))
                     return n;
@@ -1324,242 +1252,16 @@
         }
     }
 
-    /* ---------------- cmp versions -------------- */
-
-    // Boringly almost the same as natural-Comparable ones
-
-    private Node<K,V> findPredecessorCmp(Comparator<? super K> cmp, Object okey) {
-        if (cmp == null)
-            throw new NullPointerException(); // don't postpone errors
-        @SuppressWarnings("unchecked") K key = (K) okey;
-        for (;;) {
-            Index<K,V> q = head;
-            Index<K,V> r = q.right;
-            for (;;) {
-                if (r != null) {
-                    Node<K,V> n = r.node;
-                    K k = n.key;
-                    if (n.value == null) {
-                        if (!q.unlink(r))
-                            break;           // restart
-                        r = q.right;         // reread r
-                        continue;
-                    }
-                    if (cmp.compare(key, k) > 0) {
-                        q = r;
-                        r = r.right;
-                        continue;
-                    }
-                }
-                Index<K,V> d = q.down;
-                if (d != null) {
-                    q = d;
-                    r = d.right;
-                } else
-                    return q.node;
-            }
-        }
-    }
-
-    private Node<K,V> findNodeCmp(Comparator<? super K> cmp, Object okey) {
-        if (cmp == null)
-            throw new NullPointerException(); // don't postpone errors
-        @SuppressWarnings("unchecked") K key = (K) okey;
-        for (;;) {
-            Node<K,V> b = findPredecessorCmp(cmp, key);
-            Node<K,V> n = b.next;
-            for (;;) {
-                if (n == null)
-                    return null;
-                Node<K,V> f = n.next;
-                if (n != b.next)                // inconsistent read
-                    break;
-                Object v = n.value;
-                if (v == null) {                // n is deleted
-                    n.helpDelete(b, f);
-                    break;
-                }
-                if (v == n || b.value == null)  // b is deleted
-                    break;
-                int c = cmp.compare(key, n.key);
-                if (c == 0)
-                    return n;
-                if (c < 0)
-                    return null;
-                b = n;
-                n = f;
-            }
-        }
-    }
-
-    private V doGetCmp(Comparator<? super K> cmp, Object okey) {
-        if (cmp == null)
-            throw new NullPointerException(); // don't postpone errors
-        @SuppressWarnings("unchecked") K key = (K) okey;
-        for (;;) {
-            Node<K,V> b = findPredecessorCmp(cmp, key);
-            Node<K,V> n = b.next;
-            for (;;) {
-                if (n == null)
-                    return null;
-                Node<K,V> f = n.next;
-                if (n != b.next)                // inconsistent read
-                    break;
-                Object v = n.value;
-                if (v == null) {                // n is deleted
-                    n.helpDelete(b, f);
-                    break;
-                }
-                if (v == n || b.value == null)  // b is deleted
-                    break;
-                @SuppressWarnings("unchecked") V vv = (V)v;
-                int c = cmp.compare(key, n.key);
-                if (c == 0)
-                    return vv;
-                if (c < 0)
-                    return null;
-                b = n;
-                n = f;
-            }
-        }
-    }
-
-    private V doPutCmp(Comparator<? super K> cmp, K key, V value, boolean onlyIfAbsent) {
-        if (cmp == null)
-            throw new NullPointerException(); // don't postpone errors
-        for (;;) {
-            Node<K,V> b = findPredecessorCmp(cmp, key);
-            Node<K,V> n = b.next;
-            for (;;) {
-                if (n != null) {
-                    Node<K,V> f = n.next;
-                    if (n != b.next)               // inconsistent read
-                        break;
-                    Object v = n.value;
-                    if (v == null) {               // n is deleted
-                        n.helpDelete(b, f);
-                        break;
-                    }
-                    if (v == n || b.value == null) // b is deleted
-                        break;
-                    int c = cmp.compare(key, n.key);
-                    if (c > 0) {
-                        b = n;
-                        n = f;
-                        continue;
-                    }
-                    if (c == 0) {
-                        @SuppressWarnings("unchecked") V vv = (V)v;
-                        if (onlyIfAbsent || n.casValue(vv, value))
-                            return vv;
-                        else
-                            break; // restart if lost race to replace value
-                    }
-                    // else c < 0; fall through
-                }
-
-                Node<K,V> z = new Node<K,V>(key, value, n);
-                if (!b.casNext(n, z))
-                    break;         // restart if lost race to append to b
-                addIndex(key, z);
-                return null;
-            }
-        }
-    }
-
-    final V doRemoveCmp(Comparator<? super K> cmp, Object okey, Object value) {
-        if (cmp == null)
-            throw new NullPointerException(); // don't postpone errors
-        @SuppressWarnings("unchecked") K key = (K) okey;
-        for (;;) {
-            Node<K,V> b = findPredecessorCmp(cmp, key);
-            Node<K,V> n = b.next;
-            for (;;) {
-                if (n == null)
-                    return null;
-                Node<K,V> f = n.next;
-                if (n != b.next)                    // inconsistent read
-                    break;
-                Object v = n.value;
-                if (v == null) {                    // n is deleted
-                    n.helpDelete(b, f);
-                    break;
-                }
-                if (v == n || b.value == null)      // b is deleted
-                    break;
-                int c = cmp.compare(key, n.key);
-                if (c < 0)
-                    return null;
-                if (c > 0) {
-                    b = n;
-                    n = f;
-                    continue;
-                }
-                if (value != null && !value.equals(v))
-                    return null;
-                if (!n.casValue(v, null))
-                    break;
-                if (!n.appendMarker(f) || !b.casNext(n, f))
-                    findNodeCmp(cmp, key);          // Retry via findNode
-                else {
-                    findPredecessorCmp(cmp, key);   // Clean index
-                    if (head.right == null)
-                        tryReduceLevel();
-                }
-                @SuppressWarnings("unchecked") V vv = (V)v;
-                return vv;
-            }
-        }
-    }
-
-    Node<K,V> doFindNearCmp(Comparator<? super K> cmp, K key, int rel) {
-        if (cmp == null)
-            throw new NullPointerException(); // don't postpone errors
-        for (;;) {
-            Node<K,V> b = findPredecessorCmp(cmp, key);
-            Node<K,V> n = b.next;
-            for (;;) {
-                if (n == null)
-                    return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
-                Node<K,V> f = n.next;
-                if (n != b.next)                  // inconsistent read
-                    break;
-                Object v = n.value;
-                if (v == null) {                  // n is deleted
-                    n.helpDelete(b, f);
-                    break;
-                }
-                if (v == n || b.value == null)    // b is deleted
-                    break;
-                int c = cmp.compare(key, n.key);
-                if ((c == 0 && (rel & EQ) != 0) ||
-                    (c <  0 && (rel & LT) == 0))
-                    return n;
-                if ( c <= 0 && (rel & LT) != 0)
-                    return b.isBaseHeader() ? null : b;
-                b = n;
-                n = f;
-            }
-        }
-    }
-
-    /* ---------------- Relays to natural vs cmp methods -------------- */
-
-    Node<K,V> findNear(K key, int rel) {
-        Comparator<? super K> cmp;
-        return (cmp = comparator) == null ? doFindNear(key, rel) :
-                doFindNearCmp(cmp, key, rel);
-    }
-
     /**
      * Returns SimpleImmutableEntry for results of findNear.
      * @param key the key
      * @param rel the relation -- OR'ed combination of EQ, LT, GT
      * @return Entry fitting relation, or null if no such
      */
-    AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
+    final AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
+        Comparator<? super K> cmp = comparator;
         for (;;) {
-            Node<K,V> n = findNear(key, rel);
+            Node<K,V> n = findNear(key, rel, cmp);
             if (n == null)
                 return null;
             AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
@@ -1813,10 +1515,7 @@
      * @throws NullPointerException if the specified key is null
      */
     public boolean containsKey(Object key) {
-        Comparator<? super K> cmp;
-        Object v  = ((cmp = comparator) == null ? doGet(key) :
-                     doGetCmp(cmp, key));
-        return v != null;
+        return doGet(key) != null;
     }
 
     /**
@@ -1834,8 +1533,7 @@
      * @throws NullPointerException if the specified key is null
      */
     public V get(Object key) {
-        Comparator<? super K> cmp;
-        return ((cmp = comparator) == null) ? doGet(key) : doGetCmp(cmp, key);
+        return doGet(key);
     }
 
     /**
@@ -1851,7 +1549,7 @@
      */
     public V getOrDefault(Object key, V defaultValue) {
         V v;
-        return (v = get(key)) == null ? defaultValue : v;
+        return (v = doGet(key)) == null ? defaultValue : v;
     }
 
     /**
@@ -1868,11 +1566,9 @@
      * @throws NullPointerException if the specified key or value is null
      */
     public V put(K key, V value) {
-        Comparator<? super K> cmp;
         if (value == null)
             throw new NullPointerException();
-        return ((cmp = comparator) == null) ?
-            doPut(key, value, false) : doPutCmp(cmp, key, value, false);
+        return doPut(key, value, false);
     }
 
     /**
@@ -1886,9 +1582,7 @@
      * @throws NullPointerException if the specified key is null
      */
     public V remove(Object key) {
-        Comparator<? super K> cmp;
-        return ((cmp = comparator) == null) ? doRemove(key, null) :
-            doRemoveCmp(cmp, key, null);
+        return doRemove(key, null);
     }
 
     /**
@@ -1973,18 +1667,10 @@
                              Function<? super K, ? extends V> mappingFunction) {
         if (key == null || mappingFunction == null)
             throw new NullPointerException();
-        Comparator<? super K> cmp;
         V v, p, r;
-        if ((cmp = comparator) == null) {
-            if ((v = doGet(key)) == null &&
-                (r = mappingFunction.apply(key)) != null)
-                v = (p = doPut(key, r, true)) == null ? r : p;
-        }
-        else {
-            if ((v = doGetCmp(cmp, key)) == null &&
-                (r = mappingFunction.apply(key)) != null)
-                v = (p = doPutCmp(cmp, key, r, true)) == null ? r : p;
-        }
+        if ((v = doGet(key)) == null &&
+            (r = mappingFunction.apply(key)) != null)
+            v = (p = doPut(key, r, true)) == null ? r : p;
         return v;
     }
 
@@ -2005,37 +1691,17 @@
                               BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
         if (key == null || remappingFunction == null)
             throw new NullPointerException();
-        Comparator<? super K> cmp;
-        if ((cmp = comparator) == null) {
-            Node<K,V> n; Object v;
-            @SuppressWarnings("unchecked") Comparable<? super K> k =
-                (Comparable<? super K>) key;
-            while ((n = findNode(k)) != null) {
-                if ((v = n.value) != null) {
-                    @SuppressWarnings("unchecked") V vv = (V) v;
-                    V r = remappingFunction.apply(key, vv);
-                    if (r != null) {
-                        if (n.casValue(vv, r))
-                            return r;
-                    }
-                    else if (doRemove(k, vv) != null)
-                        break;
+        Node<K,V> n; Object v;
+        while ((n = findNode(key)) != null) {
+            if ((v = n.value) != null) {
+                @SuppressWarnings("unchecked") V vv = (V) v;
+                V r = remappingFunction.apply(key, vv);
+                if (r != null) {
+                    if (n.casValue(vv, r))
+                        return r;
                 }
-            }
-        }
-        else {
-            Node<K,V> n; Object v;
-            while ((n = findNodeCmp(cmp, key)) != null) {
-                if ((v = n.value) != null) {
-                    @SuppressWarnings("unchecked") V vv = (V) v;
-                    V r = remappingFunction.apply(key, vv);
-                    if (r != null) {
-                        if (n.casValue(vv, r))
-                            return r;
-                    }
-                    else if (doRemoveCmp(cmp, key, vv) != null)
-                        break;
-                }
+                else if (doRemove(key, vv) != null)
+                    break;
             }
         }
         return null;
@@ -2058,47 +1724,22 @@
                      BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
         if (key == null || remappingFunction == null)
             throw new NullPointerException();
-        Comparator<? super K> cmp;
-        if ((cmp = comparator) == null) {
-            @SuppressWarnings("unchecked") Comparable<? super K> k =
-                (Comparable<? super K>) key;
-            for (;;) {
-                Node<K,V> n; Object v; V r;
-                if ((n = findNode(k)) == null) {
-                    if ((r = remappingFunction.apply(key, null)) == null)
-                        break;
-                    if (doPut(key, r, false) == null)
+        for (;;) {
+            Node<K,V> n; Object v; V r;
+            if ((n = findNode(key)) == null) {
+                if ((r = remappingFunction.apply(key, null)) == null)
+                    break;
+                if (doPut(key, r, true) == null)
+                    return r;
+            }
+            else if ((v = n.value) != null) {
+                @SuppressWarnings("unchecked") V vv = (V) v;
+                if ((r = remappingFunction.apply(key, vv)) != null) {
+                    if (n.casValue(vv, r))
                         return r;
                 }
-                else if ((v = n.value) != null) {
-                    @SuppressWarnings("unchecked") V vv = (V) v;
-                    if ((r = remappingFunction.apply(key, vv)) != null) {
-                        if (n.casValue(vv, r))
-                            return r;
-                    }
-                    else if (doRemove(k, vv) != null)
-                        break;
-                }
-            }
-        }
-        else {
-            for (;;) {
-                Node<K,V> n; Object v; V r;
-                if ((n = findNodeCmp(cmp, key)) == null) {
-                    if ((r = remappingFunction.apply(key, null)) == null)
-                        break;
-                    if (doPutCmp(cmp, key, r, false) == null)
-                        return r;
-                }
-                else if ((v = n.value) != null) {
-                    @SuppressWarnings("unchecked") V vv = (V) v;
-                    if ((r = remappingFunction.apply(key, vv)) != null) {
-                        if (n.casValue(vv, r))
-                            return r;
-                    }
-                    else if (doRemoveCmp(cmp, key, vv) != null)
-                        break;
-                }
+                else if (doRemove(key, vv) != null)
+                    break;
             }
         }
         return null;
@@ -2123,43 +1764,20 @@
                    BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
         if (key == null || value == null || remappingFunction == null)
             throw new NullPointerException();
-        Comparator<? super K> cmp;
-        if ((cmp = comparator) == null) {
-            @SuppressWarnings("unchecked") Comparable<? super K> k =
-                (Comparable<? super K>) key;
-            for (;;) {
-                Node<K,V> n; Object v; V r;
-                if ((n = findNode(k)) == null) {
-                    if (doPut(key, value, true) == null)
-                        return value;
+        for (;;) {
+            Node<K,V> n; Object v; V r;
+            if ((n = findNode(key)) == null) {
+                if (doPut(key, value, true) == null)
+                    return value;
+            }
+            else if ((v = n.value) != null) {
+                @SuppressWarnings("unchecked") V vv = (V) v;
+                if ((r = remappingFunction.apply(vv, value)) != null) {
+                    if (n.casValue(vv, r))
+                        return r;
                 }
-                else if ((v = n.value) != null) {
-                    @SuppressWarnings("unchecked") V vv = (V) v;
-                    if ((r = remappingFunction.apply(vv, value)) != null) {
-                        if (n.casValue(vv, r))
-                            return r;
-                    }
-                    else if (doRemove(k, vv) != null)
-                        return null;
-                }
-            }
-        }
-        else {
-            for (;;) {
-                Node<K,V> n; Object v; V r;
-                if ((n = findNodeCmp(cmp, key)) == null) {
-                    if (doPutCmp(cmp, key, value, true) == null)
-                        return value;
-                }
-                else if ((v = n.value) != null) {
-                    @SuppressWarnings("unchecked") V vv = (V) v;
-                    if ((r = remappingFunction.apply(vv, value)) != null) {
-                        if (n.casValue(vv, r))
-                            return r;
-                    }
-                    else if (doRemoveCmp(cmp, key, vv) != null)
-                        return null;
-                }
+                else if (doRemove(key, vv) != null)
+                    return null;
             }
         }
     }
@@ -2186,24 +1804,24 @@
      * operations.  It does not support the {@code add} or {@code addAll}
      * operations.
      *
-     * <p>The view's {@code iterator} is a "weakly consistent" iterator
-     * that will never throw {@link ConcurrentModificationException},
-     * and guarantees to traverse elements as they existed upon
-     * construction of the iterator, and may (but is not guaranteed to)
-     * reflect any modifications subsequent to construction.
+     * <p>The view's {@code iterator} is a "weakly consistent" iterator that
+     * will never throw {@link java.util.ConcurrentModificationException
+     * ConcurrentModificationException}, and guarantees to traverse elements
+     * as they existed upon construction of the iterator, and may (but is not
+     * guaranteed to) reflect any modifications subsequent to construction.
      *
      * <p>This method is equivalent to method {@code navigableKeySet}.
      *
      * @return a navigable set view of the keys in this map
      */
     public NavigableSet<K> keySet() {
-        KeySetView<K,V> ks = keySet;
-        return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
+        KeySet<K> ks = keySet;
+        return (ks != null) ? ks : (keySet = new KeySet<K>(this));
     }
 
     public NavigableSet<K> navigableKeySet() {
-        KeySetView<K,V> ks = keySet;
-        return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
+        KeySet<K> ks = keySet;
+        return (ks != null) ? ks : (keySet = new KeySet<K>(this));
     }
 
     /**
@@ -2218,11 +1836,11 @@
      * {@code retainAll} and {@code clear} operations.  It does not
      * support the {@code add} or {@code addAll} operations.
      *
-     * <p>The view's {@code iterator} is a "weakly consistent" iterator
-     * that will never throw {@link ConcurrentModificationException},
-     * and guarantees to traverse elements as they existed upon
-     * construction of the iterator, and may (but is not guaranteed to)
-     * reflect any modifications subsequent to construction.
+     * <p>The view's {@code iterator} is a "weakly consistent" iterator that
+     * will never throw {@link java.util.ConcurrentModificationException
+     * ConcurrentModificationException}, and guarantees to traverse elements
+     * as they existed upon construction of the iterator, and may (but is not
+     * guaranteed to) reflect any modifications subsequent to construction.
      */
     public Collection<V> values() {
         Values<V> vs = values;
@@ -2240,11 +1858,11 @@
      * operations.  It does not support the {@code add} or
      * {@code addAll} operations.
      *
-     * <p>The view's {@code iterator} is a "weakly consistent" iterator
-     * that will never throw {@link ConcurrentModificationException},
-     * and guarantees to traverse elements as they existed upon
-     * construction of the iterator, and may (but is not guaranteed to)
-     * reflect any modifications subsequent to construction.
+     * <p>The view's {@code iterator} is a "weakly consistent" iterator that
+     * will never throw {@link java.util.ConcurrentModificationException
+     * ConcurrentModificationException}, and guarantees to traverse elements
+     * as they existed upon construction of the iterator, and may (but is not
+     * guaranteed to) reflect any modifications subsequent to construction.
      *
      * <p>The {@code Map.Entry} elements returned by
      * {@code iterator.next()} do <em>not</em> support the
@@ -2318,11 +1936,9 @@
      * @throws NullPointerException if the specified key or value is null
      */
     public V putIfAbsent(K key, V value) {
-        Comparator<? super K> cmp;
         if (value == null)
             throw new NullPointerException();
-        return ((cmp = comparator) == null) ?
-            doPut(key, value, true) : doPutCmp(cmp, key, value, true);
+        return doPut(key, value, true);
     }
 
     /**
@@ -2335,12 +1951,7 @@
     public boolean remove(Object key, Object value) {
         if (key == null)
             throw new NullPointerException();
-        if (value == null)
-            return false;
-        Comparator<? super K> cmp;
-        Object v = ((cmp = comparator) == null) ? doRemove(key, value) :
-            doRemoveCmp(cmp, key, value);
-        return v != null;
+        return value != null && doRemove(key, value) != null;
     }
 
     /**
@@ -2351,18 +1962,13 @@
      * @throws NullPointerException if any of the arguments are null
      */
     public boolean replace(K key, V oldValue, V newValue) {
-        if (oldValue == null || newValue == null)
+        if (key == null || oldValue == null || newValue == null)
             throw new NullPointerException();
-        Comparator<? super K> cmp = comparator;
         for (;;) {
-            @SuppressWarnings("unchecked")
-            Node<K,V> n = (cmp == null) ?
-                findNode((Comparable<? super K>)key) :
-                findNodeCmp(cmp, key);
-            if (n == null)
+            Node<K,V> n; Object v;
+            if ((n = findNode(key)) == null)
                 return false;
-            Object v = n.value;
-            if (v != null) {
+            if ((v = n.value) != null) {
                 if (!oldValue.equals(v))
                     return false;
                 if (n.casValue(v, newValue))
@@ -2381,19 +1987,16 @@
      * @throws NullPointerException if the specified key or value is null
      */
     public V replace(K key, V value) {
-        if (value == null)
+        if (key == null || value == null)
             throw new NullPointerException();
-        Comparator<? super K> cmp = comparator;
         for (;;) {
-            @SuppressWarnings("unchecked")
-            Node<K,V> n = (cmp == null) ?
-                findNode((Comparable<? super K>)key) :
-                findNodeCmp(cmp, key);
-            if (n == null)
+            Node<K,V> n; Object v;
+            if ((n = findNode(key)) == null)
                 return null;
-            @SuppressWarnings("unchecked") V v = (V)n.value;
-            if (v != null && n.casValue(v, value))
-                return v;
+            if ((v = n.value) != null && n.casValue(v, value)) {
+                @SuppressWarnings("unchecked") V vv = (V)v;
+                return vv;
+            }
         }
     }
 
@@ -2511,8 +2114,7 @@
      * @throws NullPointerException if the specified key is null
      */
     public K lowerKey(K key) {
-        Comparator<? super K> cmp;
-        Node<K,V> n = findNear(key, LT);
+        Node<K,V> n = findNear(key, LT, comparator);
         return (n == null) ? null : n.key;
     }
 
@@ -2536,7 +2138,7 @@
      * @throws NullPointerException if the specified key is null
      */
     public K floorKey(K key) {
-        Node<K,V> n = findNear(key, LT|EQ);
+        Node<K,V> n = findNear(key, LT|EQ, comparator);
         return (n == null) ? null : n.key;
     }
 
@@ -2558,7 +2160,7 @@
      * @throws NullPointerException if the specified key is null
      */
     public K ceilingKey(K key) {
-        Node<K,V> n = findNear(key, GT|EQ);
+        Node<K,V> n = findNear(key, GT|EQ, comparator);
         return (n == null) ? null : n.key;
     }
 
@@ -2582,7 +2184,7 @@
      * @throws NullPointerException if the specified key is null
      */
     public K higherKey(K key) {
-        Node<K,V> n = findNear(key, GT);
+        Node<K,V> n = findNear(key, GT, comparator);
         return (n == null) ? null : n.key;
     }
 
@@ -2656,10 +2258,7 @@
 
         /** Initializes ascending iterator for entire range. */
         Iter() {
-            for (;;) {
-                next = findFirst();
-                if (next == null)
-                    break;
+            while ((next = findFirst()) != null) {
                 Object x = next.value;
                 if (x != null && x != next) {
                     @SuppressWarnings("unchecked") V vv = (V)x;
@@ -2678,10 +2277,7 @@
             if (next == null)
                 throw new NoSuchElementException();
             lastReturned = next;
-            for (;;) {
-                next = next.next;
-                if (next == null)
-                    break;
+            while ((next = next.next) != null) {
                 Object x = next.value;
                 if (x != null && x != next) {
                     @SuppressWarnings("unchecked") V vv = (V)x;
@@ -2760,7 +2356,7 @@
 
     static final class KeySet<E>
             extends AbstractSet<E> implements NavigableSet<E> {
-        private final ConcurrentNavigableMap<E,?> m;
+        final ConcurrentNavigableMap<E,?> m;
         KeySet(ConcurrentNavigableMap<E,?> map) { m = map; }
         public int size() { return m.size(); }
         public boolean isEmpty() { return m.isEmpty(); }
@@ -2843,7 +2439,7 @@
     }
 
     static final class Values<E> extends AbstractCollection<E> {
-        private final ConcurrentNavigableMap<?, E> m;
+        final ConcurrentNavigableMap<?, E> m;
         Values(ConcurrentNavigableMap<?, E> map) {
             m = map;
         }
@@ -2878,7 +2474,7 @@
     }
 
     static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> {
-        private final ConcurrentNavigableMap<K1, V1> m;
+        final ConcurrentNavigableMap<K1, V1> m;
         EntrySet(ConcurrentNavigableMap<K1, V1> map) {
             m = map;
         }
@@ -2981,8 +2577,9 @@
                K fromKey, boolean fromInclusive,
                K toKey, boolean toInclusive,
                boolean isDescending) {
+            Comparator<? super K> cmp = map.comparator;
             if (fromKey != null && toKey != null &&
-                map.compare(fromKey, toKey) > 0)
+                cpr(cmp, fromKey, toKey) > 0)
                 throw new IllegalArgumentException("inconsistent range");
             this.m = map;
             this.lo = fromKey;
@@ -2994,39 +2591,34 @@
 
         /* ----------------  Utilities -------------- */
 
-        private boolean tooLow(K key) {
-            if (lo != null) {
-                int c = m.compare(key, lo);
-                if (c < 0 || (c == 0 && !loInclusive))
-                    return true;
-            }
-            return false;
+        boolean tooLow(Object key, Comparator<? super K> cmp) {
+            int c;
+            return (lo != null && ((c = cpr(cmp, key, lo)) < 0 ||
+                                   (c == 0 && !loInclusive)));
         }
 
-        private boolean tooHigh(K key) {
-            if (hi != null) {
-                int c = m.compare(key, hi);
-                if (c > 0 || (c == 0 && !hiInclusive))
-                    return true;
-            }
-            return false;
+        boolean tooHigh(Object key, Comparator<? super K> cmp) {
+            int c;
+            return (hi != null && ((c = cpr(cmp, key, hi)) > 0 ||
+                                   (c == 0 && !hiInclusive)));
         }
 
-        private boolean inBounds(K key) {
-            return !tooLow(key) && !tooHigh(key);
+        boolean inBounds(Object key, Comparator<? super K> cmp) {
+            return !tooLow(key, cmp) && !tooHigh(key, cmp);
         }
 
-        private void checkKeyBounds(K key) throws IllegalArgumentException {
+        void checkKeyBounds(K key, Comparator<? super K> cmp) {
             if (key == null)
                 throw new NullPointerException();
-            if (!inBounds(key))
+            if (!inBounds(key, cmp))
                 throw new IllegalArgumentException("key out of range");
         }
 
         /**
          * Returns true if node key is less than upper bound of range.
          */
-        private boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
+        boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n,
+                            Comparator<? super K> cmp) {
             if (n == null)
                 return false;
             if (hi == null)
@@ -3034,7 +2626,7 @@
             K k = n.key;
             if (k == null) // pass by markers and headers
                 return true;
-            int c = m.compare(k, hi);
+            int c = cpr(cmp, k, hi);
             if (c > 0 || (c == 0 && !hiInclusive))
                 return false;
             return true;
@@ -3044,34 +2636,35 @@
          * Returns lowest node. This node might not be in range, so
          * most usages need to check bounds.
          */
-        private ConcurrentSkipListMap.Node<K,V> loNode() {
+        ConcurrentSkipListMap.Node<K,V> loNode(Comparator<? super K> cmp) {
             if (lo == null)
                 return m.findFirst();
             else if (loInclusive)
-                return m.findNear(lo, GT|EQ);
+                return m.findNear(lo, GT|EQ, cmp);
             else
-                return m.findNear(lo, GT);
+                return m.findNear(lo, GT, cmp);
         }
 
         /**
          * Returns highest node. This node might not be in range, so
          * most usages need to check bounds.
          */
-        private ConcurrentSkipListMap.Node<K,V> hiNode() {
+        ConcurrentSkipListMap.Node<K,V> hiNode(Comparator<? super K> cmp) {
             if (hi == null)
                 return m.findLast();
             else if (hiInclusive)
-                return m.findNear(hi, LT|EQ);
+                return m.findNear(hi, LT|EQ, cmp);
             else
-                return m.findNear(hi, LT);
+                return m.findNear(hi, LT, cmp);
         }
 
         /**
          * Returns lowest absolute key (ignoring directonality).
          */
-        private K lowestKey() {
-            ConcurrentSkipListMap.Node<K,V> n = loNode();
-            if (isBeforeEnd(n))
+        K lowestKey() {
+            Comparator<? super K> cmp = m.comparator;
+            ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
+            if (isBeforeEnd(n, cmp))
                 return n.key;
             else
                 throw new NoSuchElementException();
@@ -3080,20 +2673,22 @@
         /**
          * Returns highest absolute key (ignoring directonality).
          */
-        private K highestKey() {
-            ConcurrentSkipListMap.Node<K,V> n = hiNode();
+        K highestKey() {
+            Comparator<? super K> cmp = m.comparator;
+            ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp);
             if (n != null) {
                 K last = n.key;
-                if (inBounds(last))
+                if (inBounds(last, cmp))
                     return last;
             }
             throw new NoSuchElementException();
         }
 
-        private Map.Entry<K,V> lowestEntry() {
+        Map.Entry<K,V> lowestEntry() {
+            Comparator<? super K> cmp = m.comparator;
             for (;;) {
-                ConcurrentSkipListMap.Node<K,V> n = loNode();
-                if (!isBeforeEnd(n))
+                ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
+                if (!isBeforeEnd(n, cmp))
                     return null;
                 Map.Entry<K,V> e = n.createSnapshot();
                 if (e != null)
@@ -3101,10 +2696,11 @@
             }
         }
 
-        private Map.Entry<K,V> highestEntry() {
+        Map.Entry<K,V> highestEntry() {
+            Comparator<? super K> cmp = m.comparator;
             for (;;) {
-                ConcurrentSkipListMap.Node<K,V> n = hiNode();
-                if (n == null || !inBounds(n.key))
+                ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp);
+                if (n == null || !inBounds(n.key, cmp))
                     return null;
                 Map.Entry<K,V> e = n.createSnapshot();
                 if (e != null)
@@ -3112,31 +2708,31 @@
             }
         }
 
-        private Map.Entry<K,V> removeLowest() {
+        Map.Entry<K,V> removeLowest() {
+            Comparator<? super K> cmp = m.comparator;
             for (;;) {
-                Node<K,V> n = loNode();
+                Node<K,V> n = loNode(cmp);
                 if (n == null)
                     return null;
                 K k = n.key;
-                if (!inBounds(k))
+                if (!inBounds(k, cmp))
                     return null;
-                V v = (m.comparator == null) ? m.doRemove(k, null) :
-                    m.doRemoveCmp(m.comparator, k, null);
+                V v = m.doRemove(k, null);
                 if (v != null)
                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
             }
         }
 
-        private Map.Entry<K,V> removeHighest() {
+        Map.Entry<K,V> removeHighest() {
+            Comparator<? super K> cmp = m.comparator;
             for (;;) {
-                Node<K,V> n = hiNode();
+                Node<K,V> n = hiNode(cmp);
                 if (n == null)
                     return null;
                 K k = n.key;
-                if (!inBounds(k))
+                if (!inBounds(k, cmp))
                     return null;
-                V v = (m.comparator == null) ? m.doRemove(k, null) :
-                    m.doRemoveCmp(m.comparator, k, null);
+                V v = m.doRemove(k, null);
                 if (v != null)
                     return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
             }
@@ -3145,20 +2741,21 @@
         /**
          * Submap version of ConcurrentSkipListMap.getNearEntry
          */
-        private Map.Entry<K,V> getNearEntry(K key, int rel) {
+        Map.Entry<K,V> getNearEntry(K key, int rel) {
+            Comparator<? super K> cmp = m.comparator;
             if (isDescending) { // adjust relation for direction
                 if ((rel & LT) == 0)
                     rel |= LT;
                 else
                     rel &= ~LT;
             }
-            if (tooLow(key))
+            if (tooLow(key, cmp))
                 return ((rel & LT) != 0) ? null : lowestEntry();
-            if (tooHigh(key))
+            if (tooHigh(key, cmp))
                 return ((rel & LT) != 0) ? highestEntry() : null;
             for (;;) {
-                Node<K,V> n = m.findNear(key, rel);
-                if (n == null || !inBounds(n.key))
+                Node<K,V> n = m.findNear(key, rel, cmp);
+                if (n == null || !inBounds(n.key, cmp))
                     return null;
                 K k = n.key;
                 V v = n.getValidValue();
@@ -3168,35 +2765,36 @@
         }
 
         // Almost the same as getNearEntry, except for keys
-        private K getNearKey(K key, int rel) {
+        K getNearKey(K key, int rel) {
+            Comparator<? super K> cmp = m.comparator;
             if (isDescending) { // adjust relation for direction
                 if ((rel & LT) == 0)
                     rel |= LT;
                 else
                     rel &= ~LT;
             }
-            if (tooLow(key)) {
+            if (tooLow(key, cmp)) {
                 if ((rel & LT) == 0) {
-                    ConcurrentSkipListMap.Node<K,V> n = loNode();
-                    if (isBeforeEnd(n))
+                    ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
+                    if (isBeforeEnd(n, cmp))
                         return n.key;
                 }
                 return null;
             }
-            if (tooHigh(key)) {
+            if (tooHigh(key, cmp)) {
                 if ((rel & LT) != 0) {
-                    ConcurrentSkipListMap.Node<K,V> n = hiNode();
+                    ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp);
                     if (n != null) {
                         K last = n.key;
-                        if (inBounds(last))
+                        if (inBounds(last, cmp))
                             return last;
                     }
                 }
                 return null;
             }
             for (;;) {
-                Node<K,V> n = m.findNear(key, rel);
-                if (n == null || !inBounds(n.key))
+                Node<K,V> n = m.findNear(key, rel, cmp);
+                if (n == null || !inBounds(n.key, cmp))
                     return null;
                 K k = n.key;
                 V v = n.getValidValue();
@@ -3209,30 +2807,28 @@
 
         public boolean containsKey(Object key) {
             if (key == null) throw new NullPointerException();
-            @SuppressWarnings("unchecked") K k = (K)key;
-            return inBounds(k) && m.containsKey(k);
+            return inBounds(key, m.comparator) && m.containsKey(key);
         }
 
         public V get(Object key) {
             if (key == null) throw new NullPointerException();
-            @SuppressWarnings("unchecked") K k = (K)key;
-            return (!inBounds(k)) ? null : m.get(k);
+            return (!inBounds(key, m.comparator)) ? null : m.get(key);
         }
 
         public V put(K key, V value) {
-            checkKeyBounds(key);
+            checkKeyBounds(key, m.comparator);
             return m.put(key, value);
         }
 
         public V remove(Object key) {
-            @SuppressWarnings("unchecked") K k = (K)key;
-            return (!inBounds(k)) ? null : m.remove(k);
+            return (!inBounds(key, m.comparator)) ? null : m.remove(key);
         }
 
         public int size() {
+            Comparator<? super K> cmp = m.comparator;
             long count = 0;
-            for (ConcurrentSkipListMap.Node<K,V> n = loNode();
-                 isBeforeEnd(n);
+            for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
+                 isBeforeEnd(n, cmp);
                  n = n.next) {
                 if (n.getValidValue() != null)
                     ++count;
@@ -3241,14 +2837,16 @@
         }
 
         public boolean isEmpty() {
-            return !isBeforeEnd(loNode());
+            Comparator<? super K> cmp = m.comparator;
+            return !isBeforeEnd(loNode(cmp), cmp);
         }
 
         public boolean containsValue(Object value) {
             if (value == null)
                 throw new NullPointerException();
-            for (ConcurrentSkipListMap.Node<K,V> n = loNode();
-                 isBeforeEnd(n);
+            Comparator<? super K> cmp = m.comparator;
+            for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
+                 isBeforeEnd(n, cmp);
                  n = n.next) {
                 V v = n.getValidValue();
                 if (v != null && value.equals(v))
@@ -3258,8 +2856,9 @@
         }
 
         public void clear() {
-            for (ConcurrentSkipListMap.Node<K,V> n = loNode();
-                 isBeforeEnd(n);
+            Comparator<? super K> cmp = m.comparator;
+            for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
+                 isBeforeEnd(n, cmp);
                  n = n.next) {
                 if (n.getValidValue() != null)
                     m.remove(n.key);
@@ -3269,22 +2868,21 @@
         /* ----------------  ConcurrentMap API methods -------------- */
 
         public V putIfAbsent(K key, V value) {
-            checkKeyBounds(key);
+            checkKeyBounds(key, m.comparator);
             return m.putIfAbsent(key, value);
         }
 
         public boolean remove(Object key, Object value) {
-            @SuppressWarnings("unchecked") K k = (K)key;
-            return inBounds(k) && m.remove(k, value);
+            return inBounds(key, m.comparator) && m.remove(key, value);
         }
 
         public boolean replace(K key, V oldValue, V newValue) {
-            checkKeyBounds(key);
+            checkKeyBounds(key, m.comparator);
             return m.replace(key, oldValue, newValue);
         }
 
         public V replace(K key, V value) {
-            checkKeyBounds(key);
+            checkKeyBounds(key, m.comparator);
             return m.replace(key, value);
         }
 
@@ -3302,10 +2900,9 @@
          * Utility to create submaps, where given bounds override
          * unbounded(null) ones and/or are checked against bounded ones.
          */
-        private SubMap<K,V> newSubMap(K fromKey,
-                                      boolean fromInclusive,
-                                      K toKey,
-                                      boolean toInclusive) {
+        SubMap<K,V> newSubMap(K fromKey, boolean fromInclusive,
+                              K toKey, boolean toInclusive) {
+            Comparator<? super K> cmp = m.comparator;
             if (isDescending) { // flip senses
                 K tk = fromKey;
                 fromKey = toKey;
@@ -3320,7 +2917,7 @@
                     fromInclusive = loInclusive;
                 }
                 else {
-                    int c = m.compare(fromKey, lo);
+                    int c = cpr(cmp, fromKey, lo);
                     if (c < 0 || (c == 0 && !loInclusive && fromInclusive))
                         throw new IllegalArgumentException("key out of range");
                 }
@@ -3331,7 +2928,7 @@
                     toInclusive = hiInclusive;
                 }
                 else {
-                    int c = m.compare(toKey, hi);
+                    int c = cpr(cmp, toKey, hi);
                     if (c > 0 || (c == 0 && !hiInclusive && toInclusive))
                         throw new IllegalArgumentException("key out of range");
                 }
@@ -3340,24 +2937,20 @@
                                    toKey, toInclusive, isDescending);
         }
 
-        public SubMap<K,V> subMap(K fromKey,
-                                  boolean fromInclusive,
-                                  K toKey,
-                                  boolean toInclusive) {
+        public SubMap<K,V> subMap(K fromKey, boolean fromInclusive,
+                                  K toKey, boolean toInclusive) {
             if (fromKey == null || toKey == null)
                 throw new NullPointerException();
             return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
         }
 
-        public SubMap<K,V> headMap(K toKey,
-                                   boolean inclusive) {
+        public SubMap<K,V> headMap(K toKey, boolean inclusive) {
             if (toKey == null)
                 throw new NullPointerException();
             return newSubMap(null, false, toKey, inclusive);
         }
 
-        public SubMap<K,V> tailMap(K fromKey,
-                                   boolean inclusive) {
+        public SubMap<K,V> tailMap(K fromKey, boolean inclusive) {
             if (fromKey == null)
                 throw new NullPointerException();
             return newSubMap(fromKey, inclusive, null, false);
@@ -3489,17 +3082,19 @@
             V nextValue;
 
             SubMapIter() {
+                Comparator<? super K> cmp = m.comparator;
                 for (;;) {
-                    next = isDescending ? hiNode() : loNode();
+                    next = isDescending ? hiNode(cmp) : loNode(cmp);
                     if (next == null)
                         break;
                     Object x = next.value;
                     if (x != null && x != next) {
-                        @SuppressWarnings("unchecked") V vv = (V)x;
-                        if (! inBounds(next.key))
+                        if (! inBounds(next.key, cmp))
                             next = null;
-                        else
+                        else {
+                            @SuppressWarnings("unchecked") V vv = (V)x;
                             nextValue = vv;
+                        }
                         break;
                     }
                 }
@@ -3520,17 +3115,19 @@
             }
 
             private void ascend() {
+                Comparator<? super K> cmp = m.comparator;
                 for (;;) {
                     next = next.next;
                     if (next == null)
                         break;
                     Object x = next.value;
                     if (x != null && x != next) {
-                        @SuppressWarnings("unchecked") V vv = (V)x;
-                        if (tooHigh(next.key))
+                        if (tooHigh(next.key, cmp))
                             next = null;
-                        else
+                        else {
+                            @SuppressWarnings("unchecked") V vv = (V)x;
                             nextValue = vv;
+                        }
                         break;
                     }
                 }
@@ -3539,17 +3136,17 @@
             private void descend() {
                 Comparator<? super K> cmp = m.comparator;
                 for (;;) {
-                    next = (cmp == null) ? m.doFindNear(lastReturned.key, LT) :
-                        m.doFindNearCmp(cmp, lastReturned.key, LT);
+                    next = m.findNear(lastReturned.key, LT, cmp);
                     if (next == null)
                         break;
                     Object x = next.value;
                     if (x != null && x != next) {
-                        @SuppressWarnings("unchecked") V vv = (V)x;
-                        if (tooLow(next.key))
+                        if (tooLow(next.key, cmp))
                             next = null;
-                        else
+                        else {
+                            @SuppressWarnings("unchecked") V vv = (V)x;
                             nextValue = vv;
+                        }
                         break;
                     }
                 }
@@ -3624,135 +3221,27 @@
         }
     }
 
-    /**
-     * A view of a ConcurrentSkipListMap as a {@link Set} of keys, in
-     * which additions may optionally be enabled by mapping to a
-     * common value.
-     */
-    static class KeySetView<K,V> extends AbstractSet<K>
-        implements NavigableSet<K>, java.io.Serializable {
+    // default Map method overrides
 
-        /*
-         * This class overlaps in functionality with the
-         * relative-scoped KeySet class, but must be distinct and
-         * unrelated. So we repeat most of the boring delegation code.
-         */
+    public void forEach(BiConsumer<? super K, ? super V> action) {
+        if (action == null) throw new NullPointerException();
+        V v;
+        for (Node<K,V> n = findFirst(); n != null; n = n.next) {
+            if ((v = n.getValidValue()) != null)
+                action.accept(n.key, v);
+        }
+    }
 
-        private static final long serialVersionUID = 7249069246763182397L;
-        private final ConcurrentSkipListMap<K,V> m;
-        private final V value;
-
-        KeySetView(ConcurrentSkipListMap<K,V> map, V value) {  // non-public
-            this.m = map;
-            this.value = value;
-        }
-
-        /**
-         * Returns the map backing this view.
-         *
-         * @return the map backing this view
-         */
-        public ConcurrentSkipListMap<K,V> getMap() { return m; }
-
-        /**
-         * Returns the default mapped value for additions,
-         * or {@code null} if additions are not supported.
-         *
-         * @return the default mapped value for additions, or {@code null}
-         * if not supported.
-         */
-        public V getMappedValue() { return value; }
-
-        public boolean add(K e) {
-            V v;
-            if ((v = value) == null)
-                throw new UnsupportedOperationException();
-            if (e == null)
-                throw new NullPointerException();
-            return m.put(e, v) == null;
-        }
-
-        public boolean addAll(Collection<? extends K> c) {
-            boolean added = false;
-            V v;
-            if ((v = value) == null)
-                throw new UnsupportedOperationException();
-            for (K e : c) {
-                if (e == null)
-                    throw new NullPointerException();
-                if (m.put(e, v) == null)
-                    added = true;
+    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
+        if (function == null) throw new NullPointerException();
+        V v;
+        for (Node<K,V> n = findFirst(); n != null; n = n.next) {
+            while ((v = n.getValidValue()) != null) {
+                V r = function.apply(n.key, v);
+                if (r == null) throw new NullPointerException();
+                if (n.casValue(v, r))
+                    break;
             }
-            return added;
-        }
-
-        public int size() { return m.size(); }
-        public boolean isEmpty() { return m.isEmpty(); }
-        public boolean contains(Object o) { return m.containsKey(o); }
-        public boolean remove(Object o) { return m.remove(o) != null; }
-        public void clear() { m.clear(); }
-        public K lower(K e) { return m.lowerKey(e); }
-        public K floor(K e) { return m.floorKey(e); }
-        public K ceiling(K e) { return m.ceilingKey(e); }
-        public K higher(K e) { return m.higherKey(e); }
-        public Comparator<? super K> comparator() { return m.comparator(); }
-        public K first() { return m.firstKey(); }
-        public K last() { return m.lastKey(); }
-        public Iterator<K> iterator() { return m.keyIterator(); }
-        public K pollFirst() {
-            Map.Entry<K,?> e = m.pollFirstEntry();
-            return (e == null) ? null : e.getKey();
-        }
-        public K pollLast() {
-            Map.Entry<K,?> e = m.pollLastEntry();
-            return (e == null) ? null : e.getKey();
-        }
-        public boolean equals(Object o) {
-            if (o == this)
-                return true;
-            if (!(o instanceof Set))
-                return false;
-            Collection<?> c = (Collection<?>) o;
-            try {
-                return containsAll(c) && c.containsAll(this);
-            } catch (ClassCastException unused) {
-                return false;
-            } catch (NullPointerException unused) {
-                return false;
-            }
-        }
-        public Object[] toArray()     { return toList(this).toArray();  }
-        public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
-        public Iterator<K> descendingIterator() {
-            return descendingSet().iterator();
-        }
-        public NavigableSet<K> subSet(K fromElement,
-                                      boolean fromInclusive,
-                                      K toElement,
-                                      boolean toInclusive) {
-            return new KeySet<K>(m.subMap(fromElement, fromInclusive,
-                                          toElement,   toInclusive));
-        }
-        public NavigableSet<K> headSet(K toElement, boolean inclusive) {
-            return new KeySet<K>(m.headMap(toElement, inclusive));
-        }
-        public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
-            return new KeySet<K>(m.tailMap(fromElement, inclusive));
-        }
-        public NavigableSet<K> subSet(K fromElement, K toElement) {
-            return subSet(fromElement, true, toElement, false);
-        }
-        public NavigableSet<K> headSet(K toElement) {
-            return headSet(toElement, false);
-        }
-        public NavigableSet<K> tailSet(K fromElement) {
-            return tailSet(fromElement, true);
-        }
-        public NavigableSet<K> descendingSet() {
-            return new KeySet<K>(m.descendingMap());
-        }
-        public Spliterator<K> spliterator() {
-            return m.keySpliterator();
         }
     }
 
@@ -3773,101 +3262,44 @@
      * don't. But we can just use Integer.MAX_VALUE so that we
      * don't prematurely zero out while splitting.
      */
-    static class CSLMSpliterator<K,V> {
+    abstract static class CSLMSpliterator<K,V> {
         final Comparator<? super K> comparator;
         final K fence;     // exclusive upper bound for keys, or null if to end
         Index<K,V> row;    // the level to split out
         Node<K,V> current; // current traversal node; initialize at origin
         int est;           // pseudo-size estimate
-
-        CSLMSpliterator(ConcurrentSkipListMap<K,V> m) {
-            this.comparator = m.comparator;
-            this.fence = null;
-            for (;;) { // ensure h corresponds to origin p
-                HeadIndex<K,V> h; Node<K,V> p;
-                Node<K,V> b = (h = m.head).node;
-                if ((p = b.next) == null || p.value != null) {
-                    this.est = (p == null) ? 0 : Integer.MAX_VALUE;
-                    this.current = p;
-                    this.row = h;
-                    break;
-                }
-                p.helpDelete(b, p.next);
-            }
-        }
-
         CSLMSpliterator(Comparator<? super K> comparator, Index<K,V> row,
                         Node<K,V> origin, K fence, int est) {
             this.comparator = comparator; this.row = row;
             this.current = origin; this.fence = fence; this.est = est;
         }
 
-        /** Return >= 0 if key is too large (out of bounds) */
-        @SuppressWarnings("unchecked")
-        final int compareBounds(K k) {
-            Comparator<? super K> cmp; K f;
-            if (k == null || (f = fence) == null)
-                return -1;
-            else if ((cmp = comparator) != null)
-                return cmp.compare(k, f);
-            else
-                return ((Comparable<? super K>)k).compareTo(f);
-        }
-
         public final long estimateSize() { return (long)est; }
-
-    }
-
-    // factory methods
-    final KeySpliterator<K,V> keySpliterator() {
-        return new KeySpliterator<K,V>(this);
-    }
-
-    final ValueSpliterator<K,V> valueSpliterator() {
-        return new ValueSpliterator<K,V>(this);
-    }
-
-    final EntrySpliterator<K,V> entrySpliterator() {
-        return new EntrySpliterator<K,V>(this);
     }
 
     static final class KeySpliterator<K,V> extends CSLMSpliterator<K,V>
         implements Spliterator<K> {
-        KeySpliterator(ConcurrentSkipListMap<K,V> m) { super(m); }
         KeySpliterator(Comparator<? super K> comparator, Index<K,V> row,
                        Node<K,V> origin, K fence, int est) {
             super(comparator, row, origin, fence, est);
         }
 
-        @SuppressWarnings("unchecked")
         public Spliterator<K> trySplit() {
             Node<K,V> e; K ek;
             Comparator<? super K> cmp = comparator;
             K f = fence;
             if ((e = current) != null && (ek = e.key) != null) {
                 for (Index<K,V> q = row; q != null; q = row = q.down) {
-                    Index<K,V> s; Node<K,V> n; K sk;
-                    if ((s = q.right) != null) {
-                        for (;;) {
-                            Node<K,V> b = s.node;
-                            if ((n = b.next) == null || n.value != null)
-                                break;
-                            n.helpDelete(b, n.next);
-                        }
-                        if (n != null && (sk = n.key) != null &&
-                            (cmp != null ?
-                             (cmp.compare(sk, ek) > 0) :
-                             ((Comparable<? super K>)sk).compareTo(ek) > 0) &&
-                            (f == null ||
-                             (cmp != null ?
-                              (cmp.compare(sk, f) < 0) :
-                              ((Comparable<? super K>)sk).compareTo(f) < 0))) {
-                            current = n;
-                            Index<K,V> r = q.down;
-                            row = (s.right != null) ? s : s.down;
-                            est -= est >>> 2;
-                            return new KeySpliterator<K,V>(cmp, r, e, sk, est);
-                        }
+                    Index<K,V> s; Node<K,V> b, n; K sk;
+                    if ((s = q.right) != null && (b = s.node) != null &&
+                        (n = b.next) != null && n.value != null &&
+                        (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
+                        (f == null || cpr(cmp, sk, f) < 0)) {
+                        current = n;
+                        Index<K,V> r = q.down;
+                        row = (s.right != null) ? s : s.down;
+                        est -= est >>> 2;
+                        return new KeySpliterator<K,V>(cmp, r, e, sk, est);
                     }
                 }
             }
@@ -3876,18 +3308,13 @@
 
         public void forEachRemaining(Consumer<? super K> action) {
             if (action == null) throw new NullPointerException();
+            Comparator<? super K> cmp = comparator;
             K f = fence;
-            Comparator<? super K> cmp = comparator;
-            @SuppressWarnings("unchecked")
-            Comparable<? super K> cf = (f != null && cmp == null) ?
-                (Comparable<? super K>)f : null;
             Node<K,V> e = current;
             current = null;
             for (; e != null; e = e.next) {
                 K k; Object v;
-                if ((k = e.key) != null &&
-                    (cf != null ? (cf.compareTo(k) <= 0) :
-                     (f != null && cmp.compare(f, k) <= 0)))
+                if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
                     break;
                 if ((v = e.value) != null && v != e)
                     action.accept(k);
@@ -3896,10 +3323,12 @@
 
         public boolean tryAdvance(Consumer<? super K> action) {
             if (action == null) throw new NullPointerException();
-            Node<K,V> e;
-            for (e = current; e != null; e = e.next) {
+            Comparator<? super K> cmp = comparator;
+            K f = fence;
+            Node<K,V> e = current;
+            for (; e != null; e = e.next) {
                 K k; Object v;
-                if (compareBounds(k = e.key) >= 0) {
+                if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
                     e = null;
                     break;
                 }
@@ -3923,44 +3352,42 @@
             return comparator;
         }
     }
+    // factory method for KeySpliterator
+    final KeySpliterator<K,V> keySpliterator() {
+        Comparator<? super K> cmp = comparator;
+        for (;;) { // ensure h corresponds to origin p
+            HeadIndex<K,V> h; Node<K,V> p;
+            Node<K,V> b = (h = head).node;
+            if ((p = b.next) == null || p.value != null)
+                return new KeySpliterator<K,V>(cmp, h, p, null, (p == null) ?
+                                               0 : Integer.MAX_VALUE);
+            p.helpDelete(b, p.next);
+        }
+    }
 
     static final class ValueSpliterator<K,V> extends CSLMSpliterator<K,V>
         implements Spliterator<V> {
-        ValueSpliterator(ConcurrentSkipListMap<K,V> m) { super(m); }
         ValueSpliterator(Comparator<? super K> comparator, Index<K,V> row,
                        Node<K,V> origin, K fence, int est) {
             super(comparator, row, origin, fence, est);
         }
 
-        @SuppressWarnings("unchecked")
         public Spliterator<V> trySplit() {
             Node<K,V> e; K ek;
             Comparator<? super K> cmp = comparator;
             K f = fence;
             if ((e = current) != null && (ek = e.key) != null) {
                 for (Index<K,V> q = row; q != null; q = row = q.down) {
-                    Index<K,V> s; Node<K,V> n; K sk;
-                    if ((s = q.right) != null) {
-                        for (;;) {
-                            Node<K,V> b = s.node;
-                            if ((n = b.next) == null || n.value != null)
-                                break;
-                            n.helpDelete(b, n.next);
-                        }
-                        if (n != null && (sk = n.key) != null &&
-                            (cmp != null ?
-                             (cmp.compare(sk, ek) > 0) :
-                             ((Comparable<? super K>)sk).compareTo(ek) > 0) &&
-                            (f == null ||
-                             (cmp != null ?
-                              (cmp.compare(sk, f) < 0) :
-                              ((Comparable<? super K>)sk).compareTo(f) < 0))) {
-                            current = n;
-                            Index<K,V> r = q.down;
-                            row = (s.right != null) ? s : s.down;
-                            est -= est >>> 2;
-                            return new ValueSpliterator<K,V>(cmp, r, e, sk, est);
-                        }
+                    Index<K,V> s; Node<K,V> b, n; K sk;
+                    if ((s = q.right) != null && (b = s.node) != null &&
+                        (n = b.next) != null && n.value != null &&
+                        (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
+                        (f == null || cpr(cmp, sk, f) < 0)) {
+                        current = n;
+                        Index<K,V> r = q.down;
+                        row = (s.right != null) ? s : s.down;
+                        est -= est >>> 2;
+                        return new ValueSpliterator<K,V>(cmp, r, e, sk, est);
                     }
                 }
             }
@@ -3969,18 +3396,13 @@
 
         public void forEachRemaining(Consumer<? super V> action) {
             if (action == null) throw new NullPointerException();
+            Comparator<? super K> cmp = comparator;
             K f = fence;
-            Comparator<? super K> cmp = comparator;
-            @SuppressWarnings("unchecked")
-            Comparable<? super K> cf = (f != null && cmp == null) ?
-                (Comparable<? super K>)f : null;
             Node<K,V> e = current;
             current = null;
             for (; e != null; e = e.next) {
                 K k; Object v;
-                if ((k = e.key) != null &&
-                    (cf != null ? (cf.compareTo(k) <= 0) :
-                     (f != null && cmp.compare(f, k) <= 0)))
+                if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
                     break;
                 if ((v = e.value) != null && v != e) {
                     @SuppressWarnings("unchecked") V vv = (V)v;
@@ -3991,11 +3413,12 @@
 
         public boolean tryAdvance(Consumer<? super V> action) {
             if (action == null) throw new NullPointerException();
-            boolean advanced = false;
-            Node<K,V> e;
-            for (e = current; e != null; e = e.next) {
+            Comparator<? super K> cmp = comparator;
+            K f = fence;
+            Node<K,V> e = current;
+            for (; e != null; e = e.next) {
                 K k; Object v;
-                if (compareBounds(k = e.key) >= 0) {
+                if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
                     e = null;
                     break;
                 }
@@ -4015,43 +3438,42 @@
         }
     }
 
+    // Almost the same as keySpliterator()
+    final ValueSpliterator<K,V> valueSpliterator() {
+        Comparator<? super K> cmp = comparator;
+        for (;;) {
+            HeadIndex<K,V> h; Node<K,V> p;
+            Node<K,V> b = (h = head).node;
+            if ((p = b.next) == null || p.value != null)
+                return new ValueSpliterator<K,V>(cmp, h, p, null, (p == null) ?
+                                                 0 : Integer.MAX_VALUE);
+            p.helpDelete(b, p.next);
+        }
+    }
+
     static final class EntrySpliterator<K,V> extends CSLMSpliterator<K,V>
         implements Spliterator<Map.Entry<K,V>> {
-        EntrySpliterator(ConcurrentSkipListMap<K,V> m) { super(m); }
         EntrySpliterator(Comparator<? super K> comparator, Index<K,V> row,
                          Node<K,V> origin, K fence, int est) {
             super(comparator, row, origin, fence, est);
         }
 
-        @SuppressWarnings("unchecked")
         public Spliterator<Map.Entry<K,V>> trySplit() {
             Node<K,V> e; K ek;
             Comparator<? super K> cmp = comparator;
             K f = fence;
             if ((e = current) != null && (ek = e.key) != null) {
                 for (Index<K,V> q = row; q != null; q = row = q.down) {
-                    Index<K,V> s; Node<K,V> n; K sk;
-                    if ((s = q.right) != null) {
-                        for (;;) {
-                            Node<K,V> b = s.node;
-                            if ((n = b.next) == null || n.value != null)
-                                break;
-                            n.helpDelete(b, n.next);
-                        }
-                        if (n != null && (sk = n.key) != null &&
-                            (cmp != null ?
-                             (cmp.compare(sk, ek) > 0) :
-                             ((Comparable<? super K>)sk).compareTo(ek) > 0) &&
-                            (f == null ||
-                             (cmp != null ?
-                              (cmp.compare(sk, f) < 0) :
-                              ((Comparable<? super K>)sk).compareTo(f) < 0))) {
-                            current = n;
-                            Index<K,V> r = q.down;
-                            row = (s.right != null) ? s : s.down;
-                            est -= est >>> 2;
-                            return new EntrySpliterator<K,V>(cmp, r, e, sk, est);
-                        }
+                    Index<K,V> s; Node<K,V> b, n; K sk;
+                    if ((s = q.right) != null && (b = s.node) != null &&
+                        (n = b.next) != null && n.value != null &&
+                        (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
+                        (f == null || cpr(cmp, sk, f) < 0)) {
+                        current = n;
+                        Index<K,V> r = q.down;
+                        row = (s.right != null) ? s : s.down;
+                        est -= est >>> 2;
+                        return new EntrySpliterator<K,V>(cmp, r, e, sk, est);
                     }
                 }
             }
@@ -4060,19 +3482,13 @@
 
         public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
             if (action == null) throw new NullPointerException();
+            Comparator<? super K> cmp = comparator;
             K f = fence;
-            Comparator<? super K> cmp = comparator;
-            @SuppressWarnings("unchecked")
-            Comparable<? super K> cf = (f != null && cmp == null) ?
-                (Comparable<? super K>)f : null;
             Node<K,V> e = current;
             current = null;
             for (; e != null; e = e.next) {
                 K k; Object v;
-                if ((k = e.key) != null &&
-                    (cf != null ?
-                     (cf.compareTo(k) <= 0) :
-                     (f != null && cmp.compare(f, k) <= 0)))
+                if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
                     break;
                 if ((v = e.value) != null && v != e) {
                     @SuppressWarnings("unchecked") V vv = (V)v;
@@ -4084,10 +3500,12 @@
 
         public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
             if (action == null) throw new NullPointerException();
-            Node<K,V> e;
-            for (e = current; e != null; e = e.next) {
+            Comparator<? super K> cmp = comparator;
+            K f = fence;
+            Node<K,V> e = current;
+            for (; e != null; e = e.next) {
                 K k; Object v;
-                if (compareBounds(k = e.key) >= 0) {
+                if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
                     e = null;
                     break;
                 }
@@ -4111,9 +3529,21 @@
 
         public final Comparator<Map.Entry<K,V>> getComparator() {
             return comparator == null ? null :
-                Map.Entry.comparingByKey(comparator);
+                Entry.comparingByKey(comparator);
         }
+    }
 
+    // Almost the same as keySpliterator()
+    final EntrySpliterator<K,V> entrySpliterator() {
+        Comparator<? super K> cmp = comparator;
+        for (;;) { // almost same as key version
+            HeadIndex<K,V> h; Node<K,V> p;
+            Node<K,V> b = (h = head).node;
+            if ((p = b.next) == null || p.value != null)
+                return new EntrySpliterator<K,V>(cmp, h, p, null, (p == null) ?
+                                                 0 : Integer.MAX_VALUE);
+            p.helpDelete(b, p.next);
+        }
     }
 
     // Unsafe mechanics
--- a/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java	Thu Jun 27 14:34:57 2013 +0200
+++ b/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java	Thu Jun 27 15:09:09 2013 +0200
@@ -40,7 +40,6 @@
 package java.util.concurrent;
 import java.util.AbstractList;
 import java.util.Arrays;
-import java.util.BitSet;
 import java.util.Collection;
 import java.util.Comparator;
 import java.util.ConcurrentModificationException;
@@ -135,10 +134,15 @@
      * @throws NullPointerException if the specified collection is null
      */
     public CopyOnWriteArrayList(Collection<? extends E> c) {
-        Object[] elements = c.toArray();
-        // c.toArray might (incorrectly) not return Object[] (see 6260652)
-        if (elements.getClass() != Object[].class)
-            elements = Arrays.copyOf(elements, elements.length, Object[].class);
+        Object[] elements;
+        if (c.getClass() == CopyOnWriteArrayList.class)
+            elements = ((CopyOnWriteArrayList<?>)c).getArray();
+        else {
+            elements = c.toArray();
+            // c.toArray might (incorrectly) not return Object[] (see 6260652)
+            if (elements.getClass() != Object[].class)
+                elements = Arrays.copyOf(elements, elements.length, Object[].class);
+        }
         setArray(elements);
     }
 
@@ -523,35 +527,44 @@
      * @return {@code true} if this list contained the specified element
      */
     public boolean remove(Object o) {
+        Object[] snapshot = getArray();
+        int index = indexOf(o, snapshot, 0, snapshot.length);
+        return (index < 0) ? false : remove(o, snapshot, index);
+    }
+
+    /**
+     * A version of remove(Object) using the strong hint that given
+     * recent snapshot contains o at the given index.
+     */
+    private boolean remove(Object o, Object[] snapshot, int index) {
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            Object[] elements = getArray();
-            int len = elements.length;
-            if (len != 0) {
-                // Copy while searching for element to remove
-                // This wins in the normal case of element being present
-                int newlen = len - 1;
-                Object[] newElements = new Object[newlen];
-
-                for (int i = 0; i < newlen; ++i) {
-                    if (eq(o, elements[i])) {
-                        // found one;  copy remaining and exit
-                        for (int k = i + 1; k < len; ++k)
-                            newElements[k-1] = elements[k];
-                        setArray(newElements);
-                        return true;
-                    } else
-                        newElements[i] = elements[i];
+            Object[] current = getArray();
+            int len = current.length;
+            if (snapshot != current) findIndex: {
+                int prefix = Math.min(index, len);
+                for (int i = 0; i < prefix; i++) {
+                    if (current[i] != snapshot[i] && eq(o, current[i])) {
+                        index = i;
+                        break findIndex;
+                    }
                 }
-
-                // special handling for last cell
-                if (eq(o, elements[newlen])) {
-                    setArray(newElements);
-                    return true;
-                }
+                if (index >= len)
+                    return false;
+                if (current[index] == o)
+                    break findIndex;
+                index = indexOf(o, current, index, len);
+                if (index < 0)
+                    return false;
             }
-            return false;
+            Object[] newElements = new Object[len - 1];
+            System.arraycopy(current, 0, newElements, 0, index);
+            System.arraycopy(current, index + 1,
+                             newElements, index,
+                             len - index - 1);
+            setArray(newElements);
+            return true;
         } finally {
             lock.unlock();
         }
@@ -601,20 +614,31 @@
      * @return {@code true} if the element was added
      */
     public boolean addIfAbsent(E e) {
+        Object[] snapshot = getArray();
+        return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
+            addIfAbsent(e, snapshot);
+    }
+
+    /**
+     * A version of addIfAbsent using the strong hint that given
+     * recent snapshot does not contain e.
+     */
+    private boolean addIfAbsent(E e, Object[] snapshot) {
         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];
+            Object[] current = getArray();
+            int len = current.length;
+            if (snapshot != current) {
+                // Optimize for lost race to another addXXX operation
+                int common = Math.min(snapshot.length, len);
+                for (int i = 0; i < common; i++)
+                    if (current[i] != snapshot[i] && eq(e, current[i]))
+                        return false;
+                if (indexOf(e, current, common, len) >= 0)
+                        return false;
             }
+            Object[] newElements = Arrays.copyOf(current, len + 1);
             newElements[len] = e;
             setArray(newElements);
             return true;
@@ -744,22 +768,22 @@
         Object[] cs = c.toArray();
         if (cs.length == 0)
             return 0;
-        Object[] uniq = new Object[cs.length];
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
             Object[] elements = getArray();
             int len = elements.length;
             int added = 0;
-            for (int i = 0; i < cs.length; ++i) { // scan for duplicates
+            // uniquify and compact elements in cs
+            for (int i = 0; i < cs.length; ++i) {
                 Object e = cs[i];
                 if (indexOf(e, elements, 0, len) < 0 &&
-                    indexOf(e, uniq, 0, added) < 0)
-                    uniq[added++] = e;
+                    indexOf(e, cs, 0, added) < 0)
+                    cs[added++] = e;
             }
             if (added > 0) {
                 Object[] newElements = Arrays.copyOf(elements, len + added);
-                System.arraycopy(uniq, 0, newElements, len, added);
+                System.arraycopy(cs, 0, newElements, len, added);
                 setArray(newElements);
             }
             return added;
@@ -793,7 +817,8 @@
      * @see #add(Object)
      */
     public boolean addAll(Collection<? extends E> c) {
-        Object[] cs = c.toArray();
+        Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ?
+            ((CopyOnWriteArrayList<?>)c).getArray() : c.toArray();
         if (cs.length == 0)
             return false;
         final ReentrantLock lock = this.lock;
@@ -801,9 +826,13 @@
         try {
             Object[] elements = getArray();
             int len = elements.length;
-            Object[] newElements = Arrays.copyOf(elements, len + cs.length);
-            System.arraycopy(cs, 0, newElements, len, cs.length);
-            setArray(newElements);
+            if (len == 0 && cs.getClass() == Object[].class)
+                setArray(cs);
+            else {
+                Object[] newElements = Arrays.copyOf(elements, len + cs.length);
+                System.arraycopy(cs, 0, newElements, len, cs.length);
+                setArray(newElements);
+            }
             return true;
         } finally {
             lock.unlock();
@@ -857,6 +886,74 @@
         }
     }
 
+    public void forEach(Consumer<? super E> action) {
+        if (action == null) throw new NullPointerException();
+        Object[] elements = getArray();
+        int len = elements.length;
+        for (int i = 0; i < len; ++i) {
+            @SuppressWarnings("unchecked") E e = (E) elements[i];
+            action.accept(e);
+        }
+    }
+
+    public boolean removeIf(Predicate<? super E> filter) {
+        if (filter == null) throw new NullPointerException();
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            Object[] elements = getArray();
+            int len = elements.length;
+            if (len != 0) {
+                int newlen = 0;
+                Object[] temp = new Object[len];
+                for (int i = 0; i < len; ++i) {
+                    @SuppressWarnings("unchecked") E e = (E) elements[i];
+                    if (!filter.test(e))
+                        temp[newlen++] = e;
+                }
+                if (newlen != len) {
+                    setArray(Arrays.copyOf(temp, newlen));
+                    return true;
+                }
+            }
+            return false;
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    public void replaceAll(UnaryOperator<E> operator) {
+        if (operator == null) throw new NullPointerException();
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            Object[] elements = getArray();
+            int len = elements.length;
+            Object[] newElements = Arrays.copyOf(elements, len);
+            for (int i = 0; i < len; ++i) {
+                @SuppressWarnings("unchecked") E e = (E) elements[i];
+                newElements[i] = operator.apply(e);
+            }
+            setArray(newElements);
+        } finally {
+            lock.unlock();
+        }
+    }
+
+    public void sort(Comparator<? super E> c) {
+        final ReentrantLock lock = this.lock;
+        lock.lock();
+        try {
+            Object[] elements = getArray();
+            Object[] newElements = Arrays.copyOf(elements, elements.length);
+            @SuppressWarnings("unchecked") E[] es = (E[])newElements;
+            Arrays.sort(es, c);
+            setArray(newElements);
+        } finally {
+            lock.unlock();
+        }
+    }
+
     /**
      * Saves this list to a stream (that is, serializes it).
      *
@@ -1083,12 +1180,13 @@
         }
 
         @Override
-        @SuppressWarnings("unchecked")
         public void forEachRemaining(Consumer<? super E> action) {
             Objects.requireNonNull(action);
-            final int size = snapshot.length;
-            for (int i=cursor; i < size; i++) {
-                action.accept((E) snapshot[i]);
+            Object[] elements = snapshot;
+            final int size = elements.length;
+            for (int i = cursor; i < size; i++) {
+                @SuppressWarnings("unchecked") E e = (E) elements[i];
+                action.accept(e);
             }
             cursor = size;
         }
@@ -1296,55 +1394,184 @@
             }
         }
 
-        @Override
         public void forEach(Consumer<? super E> action) {
-            @SuppressWarnings("unchecked")
-            final E[] elements = (E[]) l.getArray();
-            checkForComodification();
-            l.forEach(action, elements, offset, offset + size);
+            if (action == null) throw new NullPointerException();
+            int lo = offset;
+            int hi = offset + size;
+            Object[] a = expectedArray;
+            if (l.getArray() != a)
+                throw new ConcurrentModificationException();
+            if (lo < 0 || hi > a.length)
+                throw new IndexOutOfBoundsException();
+            for (int i = lo; i < hi; ++i) {
+                @SuppressWarnings("unchecked") E e = (E) a[i];
+                action.accept(e);
+            }
         }
 
-        @Override
-        public void sort(Comparator<? super E> c) {
+        public void replaceAll(UnaryOperator<E> operator) {
+            if (operator == null) throw new NullPointerException();
             final ReentrantLock lock = l.lock;
             lock.lock();
             try {
-                checkForComodification();
-                l.sort(c, offset, offset + size);
-                expectedArray = l.getArray();
+                int lo = offset;
+                int hi = offset + size;
+                Object[] elements = expectedArray;
+                if (l.getArray() != elements)
+                    throw new ConcurrentModificationException();
+                int len = elements.length;
+                if (lo < 0 || hi > len)
+                    throw new IndexOutOfBoundsException();
+                Object[] newElements = Arrays.copyOf(elements, len);
+                for (int i = lo; i < hi; ++i) {
+                    @SuppressWarnings("unchecked") E e = (E) elements[i];
+                    newElements[i] = operator.apply(e);
+                }
+                l.setArray(expectedArray = newElements);
             } finally {
                 lock.unlock();
             }
         }
 
-        @Override
-        public boolean removeIf(Predicate<? super E> filter) {
-            Objects.requireNonNull(filter);
+        public void sort(Comparator<? super E> c) {
             final ReentrantLock lock = l.lock;
             lock.lock();
             try {
-                checkForComodification();
-                final int removeCount =
-                        l.removeIf(filter, offset, offset + size);
-                expectedArray = l.getArray();
-                size -= removeCount;
-                return removeCount > 0;
+                int lo = offset;
+                int hi = offset + size;
+                Object[] elements = expectedArray;
+                if (l.getArray() != elements)
+                    throw new ConcurrentModificationException();
+                int len = elements.length;
+                if (lo < 0 || hi > len)
+                    throw new IndexOutOfBoundsException();
+                Object[] newElements = Arrays.copyOf(elements, len);
+                @SuppressWarnings("unchecked") E[] es = (E[])newElements;
+                Arrays.sort(es, lo, hi, c);
+                l.setArray(expectedArray = newElements);
             } finally {
                 lock.unlock();
             }
         }
 
-        @Override
-        public void replaceAll(UnaryOperator<E> operator) {
+        public boolean removeAll(Collection<?> c) {
+            if (c == null) throw new NullPointerException();
+            boolean removed = false;
             final ReentrantLock lock = l.lock;
             lock.lock();
             try {
-                checkForComodification();
-                l.replaceAll(operator, offset, offset + size);
-                expectedArray = l.getArray();
+                int n = size;
+                if (n > 0) {
+                    int lo = offset;
+                    int hi = offset + n;
+                    Object[] elements = expectedArray;
+                    if (l.getArray() != elements)
+                        throw new ConcurrentModificationException();
+                    int len = elements.length;
+                    if (lo < 0 || hi > len)
+                        throw new IndexOutOfBoundsException();
+                    int newSize = 0;
+                    Object[] temp = new Object[n];
+                    for (int i = lo; i < hi; ++i) {
+                        Object element = elements[i];
+                        if (!c.contains(element))
+                            temp[newSize++] = element;
+                    }
+                    if (newSize != n) {
+                        Object[] newElements = new Object[len - n + newSize];
+                        System.arraycopy(elements, 0, newElements, 0, lo);
+                        System.arraycopy(temp, 0, newElements, lo, newSize);
+                        System.arraycopy(elements, hi, newElements,
+                                         lo + newSize, len - hi);
+                        size = newSize;
+                        removed = true;
+                        l.setArray(expectedArray = newElements);
+                    }
+                }
             } finally {
                 lock.unlock();
             }
+            return removed;
+        }
+
+        public boolean retainAll(Collection<?> c) {
+            if (c == null) throw new NullPointerException();
+            boolean removed = false;
+            final ReentrantLock lock = l.lock;
+            lock.lock();
+            try {
+                int n = size;
+                if (n > 0) {
+                    int lo = offset;
+                    int hi = offset + n;
+                    Object[] elements = expectedArray;
+                    if (l.getArray() != elements)
+                        throw new ConcurrentModificationException();
+                    int len = elements.length;
+                    if (lo < 0 || hi > len)
+                        throw new IndexOutOfBoundsException();
+                    int newSize = 0;
+                    Object[] temp = new Object[n];
+                    for (int i = lo; i < hi; ++i) {
+                        Object element = elements[i];
+                        if (c.contains(element))
+                            temp[newSize++] = element;
+                    }
+                    if (newSize != n) {
+                        Object[] newElements = new Object[len - n + newSize];
+                        System.arraycopy(elements, 0, newElements, 0, lo);
+                        System.arraycopy(temp, 0, newElements, lo, newSize);
+                        System.arraycopy(elements, hi, newElements,
+                                         lo + newSize, len - hi);
+                        size = newSize;
+                        removed = true;
+                        l.setArray(expectedArray = newElements);
+                    }
+                }
+            } finally {
+                lock.unlock();
+            }
+            return removed;
+        }
+
+        public boolean removeIf(Predicate<? super E> filter) {
+            if (filter == null) throw new NullPointerException();
+            boolean removed = false;
+            final ReentrantLock lock = l.lock;
+            lock.lock();
+            try {
+                int n = size;
+                if (n > 0) {
+                    int lo = offset;
+                    int hi = offset + n;
+                    Object[] elements = expectedArray;
+                    if (l.getArray() != elements)
+                        throw new ConcurrentModificationException();
+                    int len = elements.length;
+                    if (lo < 0 || hi > len)
+                        throw new IndexOutOfBoundsException();
+                    int newSize = 0;
+                    Object[] temp = new Object[n];
+                    for (int i = lo; i < hi; ++i) {
+                        @SuppressWarnings("unchecked") E e = (E) elements[i];
+                        if (!filter.test(e))
+                            temp[newSize++] = e;
+                    }
+                    if (newSize != n) {
+                        Object[] newElements = new Object[len - n + newSize];
+                        System.arraycopy(elements, 0, newElements, 0, lo);
+                        System.arraycopy(temp, 0, newElements, lo, newSize);
+                        System.arraycopy(elements, hi, newElements,
+                                         lo + newSize, len - hi);
+                        size = newSize;
+                        removed = true;
+                        l.setArray(expectedArray = newElements);
+                    }
+                }
+            } finally {
+                lock.unlock();
+            }
+            return removed;
         }
 
         public Spliterator<E> spliterator() {
@@ -1414,11 +1641,12 @@
         }
 
         @Override
-        @SuppressWarnings("unchecked")
         public void forEachRemaining(Consumer<? super E> action) {
             Objects.requireNonNull(action);
-            while (nextIndex() < size) {
-                action.accept(it.next());
+            int s = size;
+            ListIterator<E> i = it;
+            while (nextIndex() < s) {
+                action.accept(i.next());
             }
         }
     }
@@ -1439,139 +1667,4 @@
             throw new Error(e);
         }
     }
-
-    @Override
-    @SuppressWarnings("unchecked")
-    public void forEach(Consumer<? super E> action) {
-        forEach(action, (E[]) getArray(), 0, size());
-    }
-
-    private void forEach(Consumer<? super E> action,
-                         final E[] elements,
-                         final int from, final int to) {
-        Objects.requireNonNull(action);
-        for (int i = from; i < to; i++) {
-            action.accept(elements[i]);
-        }
-    }
-
-    @Override
-    public void sort(Comparator<? super E> c) {
-        final ReentrantLock lock = this.lock;
-        lock.lock();
-        try {
-            sort(c, 0, size());
-        } finally {
-            lock.unlock();
-        }
-    }
-
-    // must be called with this.lock held
-    @SuppressWarnings("unchecked")
-    private void sort(Comparator<? super E> c, final int from, final int to) {
-        final E[] elements = (E[]) getArray();
-        final E[] newElements = Arrays.copyOf(elements, elements.length);
-        // only elements [from, to) are sorted
-        Arrays.sort(newElements, from, to, c);
-        setArray(newElements);
-    }
-
-    @Override
-    public boolean removeIf(Predicate<? super E> filter) {
-        Objects.requireNonNull(filter);
-        final ReentrantLock lock = this.lock;
-        lock.lock();
-        try {
-            return removeIf(filter, 0, size()) > 0;
-        } finally {
-            lock.unlock();
-        }
-    }
-
-    // must be called with this.lock held
-    private int removeIf(Predicate<? super E> filter, final int from, final int to) {
-        Objects.requireNonNull(filter);
-        final ReentrantLock lock = this.lock;
-        lock.lock();
-        try {
-            @SuppressWarnings("unchecked")
-            final E[] elements = (E[]) getArray();
-
-            // figure out which elements are to be removed
-            // any exception thrown from the filter predicate at this stage
-            // will leave the collection unmodified
-            int removeCount = 0;
-            final int range = to - from;
-            final BitSet removeSet = new BitSet(range);
-            for (int i = 0; i < range; i++) {
-                final E element = elements[from + i];
-                if (filter.test(element)) {
-                    // removeSet is zero-based to keep its size small
-                    removeSet.set(i);
-                    removeCount++;
-                }
-            }
-
-            // copy surviving elements into a new array
-            if (removeCount > 0) {
-                final int newSize = elements.length - removeCount;
-                final int newRange = newSize - from;
-                @SuppressWarnings("unchecked")
-                final E[] newElements = (E[]) new Object[newSize];
-                // copy elements before [from, to) unmodified
-                for (int i = 0; i < from; i++) {
-                    newElements[i] = elements[i];
-                }
-                // elements [from, to) are subject to removal
-                int j = 0;
-                for (int i = 0; (i < range) && (j < newRange); i++) {
-                    i = removeSet.nextClearBit(i);
-                    if (i >= range) {
-                        break;
-                    }
-                    newElements[from + (j++)] = elements[from + i];
-                }
-                // copy any remaining elements beyond [from, to)
-                j += from;
-                for (int i = to; (i < elements.length) && (j < newSize); i++) {
-                    newElements[j++] = elements[i];
-                }
-                setArray(newElements);
-            }
-
-            return removeCount;
-        } finally {
-            lock.unlock();
-        }
-    }
-
-    @Override
-    public void replaceAll(UnaryOperator<E> operator) {
-        Objects.requireNonNull(operator);
-        final ReentrantLock lock = this.lock;
-        lock.lock();
-        try {
-            replaceAll(operator, 0, size());
-        } finally {
-            lock.unlock();
-        }
-    }
-
-    // must be called with this.lock held
-    @SuppressWarnings("unchecked")
-    private void replaceAll(UnaryOperator<E> operator, final int from, final int to) {
-        final E[] elements = (E[]) getArray();
-        final E[] newElements = (E[]) new Object[elements.length];
-        for (int i = 0; i < from; i++) {
-            newElements[i] = elements[i];
-        }
-        // the operator is only applied to elements [from, to)
-        for (int i = from; i < to; i++) {
-            newElements[i] = operator.apply(elements[i]);
-        }
-        for (int i = to; i < elements.length; i++) {
-            newElements[i] = elements[i];
-        }
-        setArray(newElements);
-    }
 }
--- a/src/share/classes/java/util/concurrent/CopyOnWriteArraySet.java	Thu Jun 27 14:34:57 2013 +0200
+++ b/src/share/classes/java/util/concurrent/CopyOnWriteArraySet.java	Thu Jun 27 15:09:09 2013 +0200
@@ -40,6 +40,8 @@
 import java.util.Iterator;
 import java.util.Spliterator;
 import java.util.Spliterators;
+import java.util.function.Predicate;
+import java.util.function.Consumer;
 
 /**
  * A {@link java.util.Set} that uses an internal {@link CopyOnWriteArrayList}
@@ -112,8 +114,15 @@
      * @throws NullPointerException if the specified collection is null
      */
     public CopyOnWriteArraySet(Collection<? extends E> c) {
-        al = new CopyOnWriteArrayList<E>();
-        al.addAllAbsent(c);
+        if (c.getClass() == CopyOnWriteArraySet.class) {
+            @SuppressWarnings("unchecked") CopyOnWriteArraySet<E> cc =
+                (CopyOnWriteArraySet<E>)c;
+            al = new CopyOnWriteArrayList<E>(cc.al);
+        }
+        else {
+            al = new CopyOnWriteArrayList<E>();
+            al.addAllAbsent(c);
+        }
     }
 
     /**
@@ -387,10 +396,17 @@
         return k == len;
     }
 
+    public boolean removeIf(Predicate<? super E> filter) {
+        return al.removeIf(filter);
+    }
+
+    public void forEach(Consumer<? super E> action) {
+        al.forEach(action);
+    }
+
     public Spliterator<E> spliterator() {
         return Spliterators.spliterator
-            (al.getArray(), Spliterator.IMMUTABLE |
-             Spliterator.DISTINCT | Spliterator.ORDERED);
+            (al.getArray(), Spliterator.IMMUTABLE | Spliterator.DISTINCT);
     }
 
     /**