changeset 7360:ad8307f9f9a2

- Spliterator updates for collections and maps. - Introduce new spliterator from iterator algorithm where left-hand split sizes follow an arithetic progression up to a max size after which no more splits occur. - TODO consolidate new spliterator from iterator algorithm and array snapshot spliterator and consolidate spliterator impls and static methods in a class java.util.Spliterators. Contributed-by: Doug Lea <dl@cs.oswego.edu>
author psandoz
date Wed, 20 Feb 2013 12:03:58 +0100
parents 812c8e032423
children 32b02cd378c7
files src/share/classes/java/util/ArrayDeque.java src/share/classes/java/util/ArrayList.java src/share/classes/java/util/Collections.java src/share/classes/java/util/HashMap.java src/share/classes/java/util/HashSet.java src/share/classes/java/util/IdentityHashMap.java src/share/classes/java/util/LinkedList.java src/share/classes/java/util/PriorityQueue.java src/share/classes/java/util/TreeMap.java src/share/classes/java/util/TreeSet.java src/share/classes/java/util/Vector.java src/share/classes/java/util/WeakHashMap.java src/share/classes/java/util/concurrent/ArrayBlockingQueue.java src/share/classes/java/util/concurrent/ConcurrentHashMap.java src/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java src/share/classes/java/util/concurrent/ConcurrentSkipListSet.java src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java src/share/classes/java/util/concurrent/CopyOnWriteArraySet.java src/share/classes/java/util/concurrent/LinkedBlockingDeque.java src/share/classes/java/util/concurrent/LinkedBlockingQueue.java src/share/classes/java/util/concurrent/LinkedTransferQueue.java src/share/classes/java/util/concurrent/PriorityBlockingQueue.java
diffstat 24 files changed, 3058 insertions(+), 1221 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/ArrayDeque.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/ArrayDeque.java	Wed Feb 20 12:03:58 2013 +0100
@@ -725,7 +725,7 @@
      * Returns {@code true} if this deque contained the specified element
      * (or equivalently, if this deque changed as a result of the call).
      *
-     * <p>This method is equivalent to {@link #removeFirstOccurrence}.
+     * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}.
      *
      * @param o element to be removed from this deque, if present
      * @return {@code true} if this deque contained the specified element
@@ -875,32 +875,41 @@
             elements[i] = s.readObject();
     }
 
+    Spliterator<E> spliterator() {
+        return new DeqSpliterator<E>(this, -1, -1);
+    }
+
     public Stream<E> stream() {
-        return Streams.stream
-            (() -> new DeqSpliterator<>(this, head, tail), DeqSpliterator.CHARACTERISTICS);
+        return Streams.stream(spliterator());
     }
 
     public Stream<E> parallelStream() {
-        return Streams.parallelStream
-            (() -> new DeqSpliterator<>(this, head, tail), DeqSpliterator.CHARACTERISTICS);
+        return Streams.parallelStream(spliterator());
     }
 
     static final class DeqSpliterator<E> implements Spliterator<E> {
-        static final int CHARACTERISTICS = Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
         private final ArrayDeque<E> deq;
-        private final int fence;  // initially tail
-        private int index;        // current index, modified on traverse/split
+        private int fence;  // -1 until first use
+        private int index;  // current index, modified on traverse/split
 
-        /** Create new spliterator covering the given array and range */
+        /** Creates new spliterator covering the given array and range */
         DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
             this.deq = deq;
             this.index = origin;
             this.fence = fence;
         }
 
+        private int getFence() { // force initialization
+            int t;
+            if ((t = fence) < 0) {
+                t = fence = deq.tail;
+                index = deq.head;
+            }
+            return t;
+        }
+
         public DeqSpliterator<E> trySplit() {
-            int n = deq.elements.length;
-            int h = index, t = fence;
+            int t = getFence(), h = index, n = deq.elements.length;
             if (h != t && ((h + 1) & (n - 1)) != t) {
                 if (h > t)
                     t += n;
@@ -914,7 +923,7 @@
             if (consumer == null)
                 throw new NullPointerException();
             Object[] a = deq.elements;
-            int m = a.length - 1, f = fence, i = index;
+            int m = a.length - 1, f = getFence(), i = index;
             index = f;
             while (i != f) {
                 @SuppressWarnings("unchecked") E e = (E)a[i];
@@ -929,7 +938,7 @@
             if (consumer == null)
                 throw new NullPointerException();
             Object[] a = deq.elements;
-            int m = a.length - 1, i = index;
+            int m = a.length - 1, f = getFence(), i = index;
             if (i != fence) {
                 @SuppressWarnings("unchecked") E e = (E)a[i];
                 index = (i + 1) & m;
@@ -941,9 +950,8 @@
             return false;
         }
 
-        // Other spliterator methods
         public long estimateSize() {
-            int n = fence - index;
+            int n = getFence() - index;
             if (n < 0)
                 n += deq.elements.length;
             return (long) n;
@@ -951,7 +959,8 @@
 
         @Override
         public int characteristics() {
-            return CHARACTERISTICS;
+            return Spliterator.ORDERED | Spliterator.SIZED |
+                Spliterator.NONNULL | Spliterator.SUBSIZED;
         }
     }
 
--- a/src/share/classes/java/util/ArrayList.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/ArrayList.java	Wed Feb 20 12:03:58 2013 +0100
@@ -1155,6 +1155,20 @@
             if (ArrayList.this.modCount != this.modCount)
                 throw new ConcurrentModificationException();
         }
+
+        Spliterator<E> spliterator() {
+            checkForComodification();
+            return new ArrayListSpliterator<E>(ArrayList.this, offset,
+                                               offset + this.size, this.modCount);
+        }
+
+        public Stream<E> stream() {
+            return Streams.stream(spliterator());
+        }
+
+        public Stream<E> parallelStream() {
+            return Streams.parallelStream(spliterator());
+        }
     }
 
     @Override
@@ -1235,75 +1249,94 @@
         modCount++;
     }
 
-    // wrapping constructor in method avoids transient javac problems
-    final ArrayListSpliterator<E> spliterator(int origin, int fence,
-                                              int expectedModCount) {
-        // Without the need to enforce concurrent modification checking,
-        // this method could be as simple as:
-        //    return new Arrays.spliterator(this.elements, origin, fence)
-        return new ArrayListSpliterator<>(this, origin, fence, expectedModCount);
+    Spliterator<E> spliterator() { // to be made public later
+        return new ArrayListSpliterator<>(this, 0, -1, 0);
     }
 
-    @Override
     public Stream<E> stream() {
-        return Streams.stream
-            (() -> spliterator(0, size, modCount), ArrayListSpliterator.CHARACTERISTICS);
+        return Streams.stream(spliterator());
     }
 
-    @Override
     public Stream<E> parallelStream() {
-        return Streams.parallelStream
-            (() -> spliterator(0, size, modCount), ArrayListSpliterator.CHARACTERISTICS);
+        return Streams.parallelStream(spliterator());
     }
 
-    /** Index-based split-by-two Spliterator */
+    /** Index-based split-by-two, lazily initialized Spliterator */
     static final class ArrayListSpliterator<E> implements Spliterator<E> {
-        static final int CHARACTERISTICS = Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
+
+        /*
+         * If ArrayLists were immutable, or structurally immutable (no
+         * adds, removes, etc), we could implement their spliterators
+         * with Arrays.spliterator. Instead we detect as much
+         * interference during traversal as practical without
+         * sacrificing much performance. We rely primarily on
+         * modCounts. These are not guaranteed to detect concurrency
+         * violations, and are sometimes overly conservative about
+         * within-thread interference, but detect enough problems to
+         * be worthwhile in practice. To carry this out, we (1) lazily
+         * initialize fence and expectedModCount until the latest
+         * point that we need to commit to the state we are checking
+         * against; thus improving precision.  (This doesn't apply to
+         * SubLists, that create spliteratora with current non-lazy
+         * values).  (2) We perform only a single
+         * ConcurrentModificationException check at the end of forEach
+         * (the most performance-sensitive method). When using forEach
+         * (as opposed to iterators), we can normally only detect
+         * interference after actions, not before. Further
+         * CME-triggering checks apply to all other possible
+         * violations of assumptions for example null or too-small
+         * elementData array given its size(), that could only have
+         * occurred due to interference.  This allows the inner loop
+         * of forEach to run without any further checks, and
+         * simplifies lambda-resolution. While this does entail a
+         * number of checks, note that in the common case of
+         * list.stream().forEach(a), no checks or other computation
+         * occur anywhere other than inside forEach itself.  The other
+         * less-often-used methods cannot take advantage of most of
+         * these streamlinings.
+         */
+
         private final ArrayList<E> list;
-        private int index;                  // current index, modified on advance/split
-        private final int fence;            // one past last index
-        private final int expectedModCount; // for comodification checks
+        private int index; // current index, modified on advance/split
+        private int fence; // -1 until used; then one past last index
+        private int expectedModCount; // initialized when fence set
 
         /** Create new spliterator covering the given  range */
         ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
                              int expectedModCount) {
-            this.list = list;
+            this.list = list; // OK if null unless traversed
             this.index = origin;
             this.fence = fence;
             this.expectedModCount = expectedModCount;
         }
 
-        public ArrayListSpliterator<E> trySplit() {
-            int lo = index;
-            int mid = (lo + fence) >>> 1;
-            return (lo >= mid)
-                   ? null
-                   : new ArrayListSpliterator<>(list, lo, index = mid,
-                                                expectedModCount);
+        private int getFence() { // initialize fence to size on first use
+            int hi; // (a specialized variant appears in method forEach)
+            ArrayList<E> lst;
+            if ((hi = fence) < 0) {
+                if ((lst = list) == null)
+                    hi = fence = 0;
+                else {
+                    expectedModCount = lst.modCount;
+                    hi = fence = lst.size;
+                }
+            }
+            return hi;
         }
 
-        public void forEach(Consumer<? super E> consumer) {
-            Object[] a;
-            int i, hi; // hoist accesses and checks from loop
-            if (consumer == null)
-                throw new NullPointerException();
-            if ((a = list.elementData).length >= (hi = fence) &&
-                (i = index) >= 0 && i < hi) {
-                index = hi;
-                do {
-                    @SuppressWarnings("unchecked") E e = (E) a[i];
-                    consumer.accept(e);
-                } while (++i < hi);
-                if (list.modCount != expectedModCount)
-                    throw new ConcurrentModificationException();
-            }
+        public ArrayListSpliterator<E> trySplit() {
+            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+            return (lo >= mid) ? null : // divide range in half unless too small
+                new ArrayListSpliterator<E>(list, lo, index = mid,
+                                            expectedModCount);
         }
 
-        public boolean tryAdvance(Consumer<? super E> consumer) {
-            if (index >= 0 && index < fence) {
-                @SuppressWarnings("unchecked") E e =
-                    (E)list.elementData[index++];
-                consumer.accept(e);
+        public boolean tryAdvance(Consumer<? super E> action) {
+            int hi = getFence(), i = index;
+            if (i < hi) {
+                index = i + 1;
+                @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
+                action.accept(e);
                 if (list.modCount != expectedModCount)
                     throw new ConcurrentModificationException();
                 return true;
@@ -1311,11 +1344,36 @@
             return false;
         }
 
-        public long estimateSize() { return (long)  (fence - index); }
+        public void forEach(Consumer<? super E> action) {
+            int i, hi, mc; // hoist accesses and checks from loop
+            ArrayList<E> lst; Object[] a;
+            if (action == null)
+                throw new NullPointerException();
+            if ((lst = list) != null && (a = lst.elementData) != null) {
+                if ((hi = fence) < 0) {
+                    mc = lst.modCount;
+                    hi = lst.size;
+                }
+                else
+                    mc = expectedModCount;
+                if ((i = index) >= 0 && (index = hi) <= a.length) {
+                    for (; i < hi; ++i) {
+                        @SuppressWarnings("unchecked") E e = (E) a[i];
+                        action.accept(e);
+                    }
+                    if (lst.modCount == mc)
+                        return;
+                }
+            }
+            throw new ConcurrentModificationException();
+        }
 
-        @Override
+        public long estimateSize() {
+            return (long) (getFence() - index);
+        }
+
         public int characteristics() {
-            return CHARACTERISTICS;
+            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
         }
     }
 
--- a/src/share/classes/java/util/Collections.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/Collections.java	Wed Feb 20 12:03:58 2013 +0100
@@ -4179,4 +4179,339 @@
         public boolean retainAll(Collection<?> c)   {return q.retainAll(c);}
         // We use inherited addAll; forwarding addAll would be wrong
     }
+
+    /**
+     * Returns a new Spliterator that covers elements obtained by the
+     * given Collection's {@link Collection#toArray} method.
+     *
+     * @param c the collection
+     * @param characteristics properties of this spliterator's
+     * source or elements ({@code SIZED} and {@code SUBSIZED}
+     * are always reported, so need not be supplied.)
+     * @since 1.8
+     */
+    public static <T> Spliterator<T> arraySnapshotSpliterator
+        (Collection<T> c, int characteristics) {
+        return new ArraySnapshotSpliterator<T>(c, characteristics);
+    }
+
+    /**
+     * Creates a new Spliterator covering all of the given array.
+     *
+     * @param array the array, assumed to be unmodified during use
+     * @param characteristics properties of this spliterator's
+     * source or elements ({@code SIZED} and {@code SUBSIZED}
+     * are always reported, so need not be supplied.)
+     * @since 1.8
+     */
+    public static <T> Spliterator<T> arraySnapshotSpliterator
+        (Object[] array, int characteristics) {
+        return  new ArraySnapshotSpliterator<T>(array, characteristics);
+    }
+
+    /**
+     * Creates a new Spliterator covering the given range of the given
+     * array.
+     *
+     * @param array the array, assumed to be unmodified during use
+     * @param characteristics properties of this spliterator's
+     * source or elements ({@code SIZED} and {@code SUBSIZED}
+     * are always reported, so need not be supplied.)
+     *
+     * @param array the array, assumed to be unmodified during use
+     * @param origin the least index (inclusive) to cover
+     * @param fence one past the greatest index to cover
+     * @param characteristics properties of this spliterator's
+     * source or elements ({@code SIZED} and {@code SUBSIZED}
+     * are always reported, so need not be supplied.)
+     * @since 1.8
+     */
+    public static <T> Spliterator<T> arraySnapshotSpliterator
+        (Object[] array, int origin, int fence, int characteristics) {
+        return  new ArraySnapshotSpliterator<T>(array, origin, fence,
+                                                characteristics);
+    }
+
+    /**
+     * Returns a new basic Spliterator using a given Iterator for
+     * element operations, and with a given initially reported
+     * size. The spliterator implements {@code trySplit} to permit
+     * limited parallelism.
+     *
+     * @param iterator the iterator for the source
+     * @param size the number of elements in the source, to be reported
+     * as initial {@code estimateSize}.
+     * @param characteristics properties of this spliterator's
+     * source or elements.
+     * @since 1.8
+     */
+    public static <T> Spliterator<T> iteratorBasedSpliterator
+        (Iterator<T> iterator, long size, int characteristics) {
+        return new IteratorSpliterator<T>(iterator, size, characteristics);
+    }
+
+    /**
+     * Returns a basic Spliterator using a given Iterator for element
+     * operations, with no initial size estimate. The spliterator
+     * implements {@code trySplit} to permit limited parallelism.
+     *
+     * @param iterator the iterator for the source
+     * @param characteristics properties of this spliterator's
+     * source or elements.
+     * @since 1.8
+     */
+    public static <T> Spliterator<T> iteratorBasedSpliterator
+        (Iterator<T> iterator, int characteristics) {
+        return new IteratorSpliterator<T>(iterator, characteristics);
+    }
+
+    /**
+     * Returns a new basic Spliterator using the given collection's
+     * {@link Collection#iterator()) for traversal, and reporting its
+     * {@link Collection#size()) as its initial size.  The spliterator
+     * implements {@code trySplit} to permit limited parallelism.
+     *
+     * @param c the collection
+     * @param characteristics properties of this spliterator's
+     * source or elements.
+     * @since 1.8
+     */
+    public static <T> Spliterator<T> iteratorBasedSpliterator
+        (Collection<T> c, int characteristics) {
+        return new IteratorSpliterator<T>(c, characteristics);
+    }
+
+    /**
+     * A Spliterator designed for use by those Collections and related
+     * sources that traverse and split elements maintained in an
+     * unmodifiable {@code Object[]} array. The spliterator covers a
+     * given array snapshotting elements; either the one returned by a
+     * Collection's toArray method, or an explicit array and range
+     * passed in a constructor.
+     */
+    static final class ArraySnapshotSpliterator<T> implements Spliterator<T> {
+        /**
+         * The array, explicitly typed as Object[]. Unlike in some other
+         * classes (see for example CR 6260652), we do not need to
+         * screen arguments to ensure they are exactly of type Object[]
+         * so long as no methods write into the array or serialize it,
+         * which we ensure here by defining this class as final.
+         */
+        private final Object[] array;
+        private int index;        // current index, modified on advance/split
+        private final int fence;  // one past last index
+        private final int characteristics;
+
+        /**
+         * Creates a new spliterator operating on the array returned
+         * by the given collection's toArray method, and with the
+         * given characteristics.
+         *
+         * @param c the collection
+         * @param characteristics properties of this spliterator's
+         * source or elements ({@code SIZED} and {@code SUBSIZED}
+         * are always reported, so need not be supplied.)
+         */
+        public ArraySnapshotSpliterator(Collection<T> c, int characteristics) {
+            this.array = c.toArray();
+            this.fence = array.length;
+            this.characteristics = characteristics;
+            this.index = 0;
+        }
+
+        /**
+         * Creates a new spliterator covering all of the given array.
+         * @param array the array, assumed to be unmodified during use
+         * @param characteristics properties of this spliterator's
+         * source or elements ({@code SIZED} and {@code SUBSIZED}
+         * are always reported, so need not be supplied.)
+         */
+        public ArraySnapshotSpliterator(Object[] array, int characteristics) {
+            this(array, 0, array.length, characteristics);
+        }
+
+        /**
+         * Creates a new spliterator covering the given array and range
+         * @param array the array, assumed to be unmodified during use
+         * @param origin the least index (inclusive) to cover
+         * @param fence one past the greatest index to cover
+         * @param characteristics properties of this spliterator's
+         * source or elements ({@code SIZED} and {@code SUBSIZED}
+         * are always reported, so need not be supplied.)
+         */
+        public ArraySnapshotSpliterator(Object[] array, int origin, int fence,
+                                        int characteristics) {
+            this.array = array;
+            this.index = origin;
+            this.fence = fence;
+            this.characteristics = characteristics;
+        }
+
+        public Spliterator<T> trySplit() {
+            int lo = index, mid = (lo + fence) >>> 1;
+            return (lo >= mid) ? null :
+                new ArraySnapshotSpliterator<T>(array, lo, index = mid,
+                                                characteristics);
+        }
+
+        @SuppressWarnings("unchecked")
+        public void forEach(Consumer<? super T> action) {
+            Object[] a; int i, hi; // hoist accesses and checks from loop
+            if (action == null)
+                throw new NullPointerException();
+            if ((a = array).length >= (hi = fence) &&
+                (i = index) >= 0 && i < (index = hi)) {
+                do { action.accept((T)a[i]); } while (++i < hi);
+            }
+        }
+
+        public boolean tryAdvance(Consumer<? super T> action) {
+            if (action == null)
+                throw new NullPointerException();
+            if (index >= 0 && index < fence) {
+                @SuppressWarnings("unchecked") T e = (T) array[index++];
+                action.accept(e);
+                return true;
+            }
+            return false;
+        }
+
+        public long estimateSize() { return (long)(fence - index); }
+
+        public int characteristics() {
+            return characteristics | Spliterator.SIZED | Spliterator.SUBSIZED;
+        }
+    }
+
+    /**
+     * A basic Spliterator using a given Iterator for element
+     * operations. The spliterator implements {@code trySplit} to
+     * permit limited parallelism.
+     */
+    static final class IteratorSpliterator<T> implements Spliterator<T> {
+        static final int MAX_BATCH = 1 << 12;  // saturate batch size; see below
+        private final Collection<T> collection; // null OK
+        private Iterator<T> it;
+        private final int characteristics;
+        private long est;             // size estimate
+        private int batch;            // batch size for splits
+
+        /**
+         * Creates a new spliterator using the given given
+         * collection's {@link Collection#iterator()) for traversal, and
+         * reporting its {@link Collection#size()) as its initial size.
+         *
+         * @param c the collection
+         * @param characteristics properties of this spliterator's
+         * source or elements.
+         */
+        public IteratorSpliterator(Collection<T> collection, int characteristics) {
+            this.collection = collection;
+            this.it = null;
+            this.characteristics = characteristics | Spliterator.SIZED |
+                Spliterator.SIZED;
+        }
+
+        /**
+         * Creates a new spliterator using the given iterator
+         * for traversal, and reporting the given initial size
+         * and characteristics.
+         *
+         * @param iterator the iterator for the source
+         * @param size the number of elements in the source
+         * @param characteristics properties of this spliterator's
+         * source or elements.
+         */
+        public IteratorSpliterator(Iterator<T> iterator, long size,
+                                   int characteristics) {
+            this.collection = null;
+            this.it = iterator;
+            this.est = size;
+            this.characteristics = characteristics | Spliterator.SIZED |
+                Spliterator.SIZED;
+        }
+
+        /**
+         * Creates a new spliterator using the given iterator for a
+         * source of unknown size, reporting the given
+         * characteristics.
+         *
+         * @param iterator the iterator for the source
+         * @param characteristics properties of this spliterator's
+         * source or elements.
+         */
+        public IteratorSpliterator(Iterator<T> iterator, int characteristics) {
+            this.collection = null;
+            this.it = iterator;
+            this.est = Long.MAX_VALUE;
+            this.characteristics = characteristics;
+        }
+
+        public Spliterator<T> trySplit() {
+            /*
+             * Split into arrays of arithmetically increasing batch
+             * sizes, giving up at MAX_BATCH.  This will only improve
+             * parallel performance if per-element Consumer actions
+             * are more costly than transfering them into an array.
+             * The use of an arithmetic progression in split sizes
+             * provides overhead vs parallelism bounds that do not
+             * particularly favor or penalize cases of lightweight vs
+             * heavyweight element operations, across combinations of
+             * #elements vs #cores, whether or not either are known.
+             * We generate O(sqrt(#elements)) splits, allowing
+             * O(sqrt(#cores)) potential speedup. The cutoff value
+             * limits asymptotic speedups for large #elements, but is
+             * needed to limit runaway overhead impact when the cost
+             * of allocating, filling, and splitting off arrays dwarfs
+             * all other processing.
+             */
+            int n;
+            if (it == null) {
+                est = (long)collection.size();
+                it = collection.iterator();
+            }
+            if (it.hasNext() && (n = batch + 1) > 0 && n <= MAX_BATCH) {
+                Object[] a = new Object[batch = n];
+                int i = 0;
+                do { a[i++] = it.next(); } while (it.hasNext() && i < n);
+                if (est != Long.MAX_VALUE)
+                    est -= i;
+                return new ArraySnapshotSpliterator<T>(a, 0, i, characteristics);
+            }
+            return null;
+        }
+
+        public void forEach(Consumer<? super T> action) {
+            if (action == null) throw new NullPointerException();
+            if (it == null) {
+                est = (long)collection.size();
+                it = collection.iterator();
+            }
+            while (it.hasNext())
+                action.accept(it.next());
+        }
+
+        public boolean tryAdvance(Consumer<? super T> action) {
+            if (action == null) throw new NullPointerException();
+            if (it == null) {
+                est = (long)collection.size();
+                it = collection.iterator();
+            }
+            if (it.hasNext()) {
+                action.accept(it.next());
+                return true;
+            }
+            return false;
+        }
+
+        public long estimateSize() {
+            if (it == null) {
+                it = collection.iterator();
+                return est = (long)collection.size();
+            }
+            return est;
+        }
+
+        public int characteristics() { return characteristics; }
+    }
 }
--- a/src/share/classes/java/util/HashMap.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/HashMap.java	Wed Feb 20 12:03:58 2013 +0100
@@ -925,22 +925,21 @@
             HashMap.this.clear();
         }
 
+        Spliterator<K> spliterator() {
+            if (HashMap.this.getClass() == HashMap.class)
+                return new KeySpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
+            else
+                return Collections.iteratorBasedSpliterator
+                    (this, Spliterator.SIZED | Spliterator.DISTINCT);
+        }
+
         public Stream<K> stream() {
-            return (HashMap.this.getClass() == HashMap.class)
-                    ? Streams.stream(() -> keySpliterator(),
-                                     Spliterator.SIZED | Spliterator.DISTINCT)
-                    : Streams.stream(() -> Streams.spliterator(iterator(), (long) size, Spliterator.SIZED | Spliterator.DISTINCT),
-                                     Spliterator.SIZED | Spliterator.DISTINCT);
+            return Streams.stream(spliterator());
         }
 
         public Stream<K> parallelStream() {
-            return (HashMap.this.getClass() == HashMap.class)
-                   ? Streams.parallelStream(() -> keySpliterator(),
-                                            Spliterator.SIZED | Spliterator.DISTINCT)
-                   : Streams.parallelStream(() -> Streams.spliterator(iterator(), (long) size, Spliterator.SIZED | Spliterator.DISTINCT),
-                                            Spliterator.SIZED | Spliterator.DISTINCT);
+            return Streams.parallelStream(spliterator());
         }
-
     }
 
     /**
@@ -975,20 +974,20 @@
             HashMap.this.clear();
         }
 
+        Spliterator<V> spliterator() {
+            if (HashMap.this.getClass() == HashMap.class)
+                return new ValueSpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
+            else
+                return Collections.iteratorBasedSpliterator
+                    (this, Spliterator.SIZED);
+        }
+
         public Stream<V> stream() {
-            return (HashMap.this.getClass() == HashMap.class)
-                   ? Streams.stream(() -> valueSpliterator(),
-                                    Spliterator.SIZED)
-                   : Streams.stream(() -> Streams.spliterator(iterator(), (long) size, Spliterator.SIZED),
-                                    Spliterator.SIZED);
+            return Streams.stream(spliterator());
         }
 
         public Stream<V> parallelStream() {
-            return (HashMap.this.getClass() == HashMap.class)
-                   ? Streams.parallelStream(() -> valueSpliterator(),
-                                            Spliterator.SIZED)
-                   : Streams.parallelStream(() -> Streams.spliterator(iterator(), (long) size, Spliterator.SIZED),
-                                            Spliterator.SIZED);
+            return Streams.parallelStream(spliterator());
         }
     }
 
@@ -1038,20 +1037,20 @@
             HashMap.this.clear();
         }
 
+        Spliterator<Map.Entry<K,V>> spliterator() {
+            if (HashMap.this.getClass() == HashMap.class)
+                return new EntrySpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
+            else
+                return Collections.iteratorBasedSpliterator
+                    (this, Spliterator.SIZED | Spliterator.DISTINCT);
+        }
+
         public Stream<Map.Entry<K,V>> stream() {
-            return (HashMap.this.getClass() == HashMap.class)
-                   ? Streams.stream(() -> entrySpliterator(),
-                                    Spliterator.SIZED | Spliterator.DISTINCT)
-                   : Streams.stream(() -> Streams.spliterator(iterator(), (long) size, Spliterator.SIZED | Spliterator.DISTINCT),
-                                    Spliterator.SIZED | Spliterator.DISTINCT);
+            return Streams.stream(spliterator());
         }
 
         public Stream<Map.Entry<K,V>> parallelStream() {
-            return (HashMap.this.getClass() == HashMap.class)
-                   ? Streams.parallelStream(() -> entrySpliterator(),
-                                            Spliterator.SIZED | Spliterator.DISTINCT)
-                   : Streams.parallelStream(() -> Streams.spliterator(iterator(), (long) size, Spliterator.SIZED | Spliterator.DISTINCT),
-                                            Spliterator.SIZED | Spliterator.DISTINCT);
+            return Streams.parallelStream(spliterator());
         }
     }
 
@@ -1149,18 +1148,6 @@
     int   capacity()     { return table.length; }
     float loadFactor()   { return loadFactor;   }
 
-    KeySpliterator<K,V> keySpliterator() {
-        return new KeySpliterator<>(this, 0, table.length, size, modCount);
-    }
-
-    ValueSpliterator<K,V> valueSpliterator() {
-        return new ValueSpliterator<>(this, 0, table.length, size, modCount);
-    }
-
-    EntrySpliterator<K,V> entrySpliterator() {
-        return new EntrySpliterator<>(this, 0, table.length, size, modCount);
-    }
-
     /**
      * Standin until HM overhaul; based loosely on Weak and Identity HM.
      */
@@ -1168,9 +1155,9 @@
         final HashMap<K,V> map;
         HashMap.Entry<K,V> current; // current node
         int index;                  // current index, modified on advance/split
-        final int fence;            // one past last index
+        int fence;                  // one past last index
         int est;                    // size estimate
-        final int expectedModCount; // for comodification checks
+        int expectedModCount;       // for comodification checks
 
         HashMapSpliterator(HashMap<K,V> m, int origin,
                                int fence, int est,
@@ -1182,9 +1169,20 @@
             this.expectedModCount = expectedModCount;
         }
 
-        public final long estimateSize() { return (long) est; }
-        public int characteristics() {
-            return est == map.size ? Spliterator.SIZED : 0;
+        final int getFence() { // initialize fence and size on first use
+            int hi;
+            if ((hi = fence) < 0) {
+                HashMap<K,V> m = map;
+                est = m.size;
+                expectedModCount = m.modCount;
+                hi = fence = m.table.length;
+            }
+            return hi;
+        }
+
+        public final long estimateSize() {
+            getFence(); // force init
+            return (long) est;
         }
     }
 
@@ -1197,50 +1195,54 @@
         }
 
         public KeySpliterator<K,V> trySplit() {
-            int lo = index;
-            int mid = (lo + fence) >>> 1;
-            return (lo >= mid || current != null)
-                   ? null
-                   : new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
-                                          expectedModCount);
+            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+            return (lo >= mid || current != null) ? null :
+                new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+                                        expectedModCount);
         }
 
         @SuppressWarnings("unchecked")
-        public void forEach(Consumer<? super K> consumer) {
-            HashMap.Entry<K,V>[] a; int i, hi;
-            if (consumer == null)
+        public void forEach(Consumer<? super K> action) {
+            int i, hi, mc;
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = (HashMap.Entry<K,V>[])map.table).length >= (hi = fence) &&
-                (i = index) >= 0 && i < hi) {
-                index = hi;
+            HashMap<K,V> m = map;
+            HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
+            if ((hi = fence) < 0) {
+                mc = expectedModCount = m.modCount;
+                hi = fence = tab.length;
+            }
+            else
+                mc = expectedModCount;
+            if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
                 HashMap.Entry<K,V> p = current;
                 do {
                     if (p == null)
-                        p = a[i++];
+                        p = tab[i++];
                     else {
-                        consumer.accept(p.getKey());
+                        action.accept(p.getKey());
                         p = p.next;
                     }
                 } while (p != null || i < hi);
-                if (map.modCount != expectedModCount)
+                if (m.modCount != mc)
                     throw new ConcurrentModificationException();
             }
         }
 
         @SuppressWarnings("unchecked")
-        public boolean tryAdvance(Consumer<? super K> consumer) {
-            HashMap.Entry<K,V>[] a;
+        public boolean tryAdvance(Consumer<? super K> action) {
             int hi;
-            if (consumer == null)
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = (HashMap.Entry<K,V>[])map.table).length >= (hi = fence) && index >= 0) {
+            HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table;
+            if (tab.length >= (hi = getFence()) && index >= 0) {
                 while (current != null || index < hi) {
                     if (current == null)
-                        current = a[index++];
+                        current = tab[index++];
                     else {
                         K k = current.getKey();
                         current = current.next;
-                        consumer.accept(k);
+                        action.accept(k);
                         if (map.modCount != expectedModCount)
                             throw new ConcurrentModificationException();
                         return true;
@@ -1251,7 +1253,8 @@
         }
 
         public int characteristics() {
-            return super.characteristics() | Spliterator.DISTINCT;
+            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
+                Spliterator.DISTINCT;
         }
     }
 
@@ -1264,51 +1267,54 @@
         }
 
         public ValueSpliterator<K,V> trySplit() {
-            int lo = index;
-            int mid = (lo + fence) >>> 1;
-            return (lo >= mid || current != null)
-                   ? null
-                   : new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
-                                            expectedModCount);
+            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+            return (lo >= mid || current != null) ? null :
+                new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+                                          expectedModCount);
         }
 
         @SuppressWarnings("unchecked")
-        public void forEach(Consumer<? super V> consumer) {
-            HashMap.Entry<K,V>[] a;
-            int i, hi;
-            if (consumer == null)
+        public void forEach(Consumer<? super V> action) {
+            int i, hi, mc;
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = (HashMap.Entry<K,V>[])map.table).length >= (hi = fence) &&
-                (i = index) >= 0 && i < hi) {
-                index = hi;
+            HashMap<K,V> m = map;
+            HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
+            if ((hi = fence) < 0) {
+                mc = expectedModCount = m.modCount;
+                hi = fence = tab.length;
+            }
+            else
+                mc = expectedModCount;
+            if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
                 HashMap.Entry<K,V> p = current;
                 do {
                     if (p == null)
-                        p = a[i++];
+                        p = tab[i++];
                     else {
-                        consumer.accept(p.getValue());
+                        action.accept(p.getValue());
                         p = p.next;
                     }
                 } while (p != null || i < hi);
-                if (map.modCount != expectedModCount)
+                if (m.modCount != mc)
                     throw new ConcurrentModificationException();
             }
         }
 
         @SuppressWarnings("unchecked")
-        public boolean tryAdvance(Consumer<? super V> consumer) {
-            HashMap.Entry<K,V>[] a;
+        public boolean tryAdvance(Consumer<? super V> action) {
             int hi;
-            if (consumer == null)
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = (HashMap.Entry<K,V>[])map.table).length >= (hi = fence) && index >= 0) {
+            HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table;
+            if (tab.length >= (hi = getFence()) && index >= 0) {
                 while (current != null || index < hi) {
                     if (current == null)
-                        current = a[index++];
+                        current = tab[index++];
                     else {
                         V v = current.getValue();
                         current = current.next;
-                        consumer.accept(v);
+                        action.accept(v);
                         if (map.modCount != expectedModCount)
                             throw new ConcurrentModificationException();
                         return true;
@@ -1317,6 +1323,10 @@
             }
             return false;
         }
+
+        public int characteristics() {
+            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);
+        }
     }
 
     static final class EntrySpliterator<K,V>
@@ -1328,51 +1338,54 @@
         }
 
         public EntrySpliterator<K,V> trySplit() {
-            int lo = index;
-            int mid = (lo + fence) >>> 1;
-            return (lo >= mid)
-                   ? null
-                   : new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
-                                            expectedModCount);
+            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+            return (lo >= mid || current != null) ? null :
+                new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+                                          expectedModCount);
         }
 
         @SuppressWarnings("unchecked")
-        public void forEach(Consumer<? super Map.Entry<K,V>> consumer) {
-            HashMap.Entry<K,V>[] a;
-            int i, hi;
-            if (consumer == null)
+        public void forEach(Consumer<? super Map.Entry<K,V>> action) {
+            int i, hi, mc;
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = (HashMap.Entry<K,V>[])map.table).length >= (hi = fence) &&
-                (i = index) >= 0 && i < hi) {
-                index = hi;
+            HashMap<K,V> m = map;
+            HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
+            if ((hi = fence) < 0) {
+                mc = expectedModCount = m.modCount;
+                hi = fence = tab.length;
+            }
+            else
+                mc = expectedModCount;
+            if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
                 HashMap.Entry<K,V> p = current;
                 do {
                     if (p == null)
-                        p = a[i++];
+                        p = tab[i++];
                     else {
-                        consumer.accept(p);
+                        action.accept(p);
                         p = p.next;
                     }
                 } while (p != null || i < hi);
-                if (map.modCount != expectedModCount)
+                if (m.modCount != mc)
                     throw new ConcurrentModificationException();
             }
         }
 
         @SuppressWarnings("unchecked")
-        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> Consumer) {
-            HashMap.Entry<K,V>[] a;
+        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
             int hi;
-            if (Consumer == null)
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = (HashMap.Entry<K,V>[])map.table).length >= (hi = fence) && index >= 0) {
+            HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table;
+            if (tab.length >= (hi = getFence()) && index >= 0) {
                 while (current != null || index < hi) {
                     if (current == null)
-                        current = a[index++];
+                        current = tab[index++];
                     else {
                         HashMap.Entry<K,V> e = current;
                         current = current.next;
-                        Consumer.accept(e);
+                        action.accept(e);
                         if (map.modCount != expectedModCount)
                             throw new ConcurrentModificationException();
                         return true;
@@ -1383,7 +1396,8 @@
         }
 
         public int characteristics() {
-            return super.characteristics() | Spliterator.DISTINCT;
+            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
+                Spliterator.DISTINCT;
         }
     }
 }
--- a/src/share/classes/java/util/HashSet.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/HashSet.java	Wed Feb 20 12:03:58 2013 +0100
@@ -25,7 +25,6 @@
 
 package java.util;
 import java.util.stream.Stream;
-import java.util.Spliterator;
 import java.util.stream.Streams;
 
 /**
@@ -315,16 +314,16 @@
         }
     }
 
-    public Stream<E> stream() {
-        return Streams.stream
-            (() -> map.keySpliterator(),
-             Spliterator.SIZED | Spliterator.DISTINCT);
+    Spliterator<E> spliterator() {
+        return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
     }
 
+    public Stream<E> stream() {
+        return Streams.stream(spliterator());
+    }
+    
     public Stream<E> parallelStream() {
-        return Streams.parallelStream
-            (() -> map.keySpliterator(),
-             Spliterator.SIZED | Spliterator.DISTINCT);
+        return Streams.parallelStream(spliterator());
     }
 
 }
--- a/src/share/classes/java/util/IdentityHashMap.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/IdentityHashMap.java	Wed Feb 20 12:03:58 2013 +0100
@@ -1014,16 +1014,16 @@
             return result;
         }
 
+        Spliterator<K> spliterator() {
+            return new KeySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+        }
+
         public Stream<K> stream() {
-            return Streams.stream
-                (() -> keySpliterator(),
-                 Spliterator.SIZED | Spliterator.DISTINCT);
+            return Streams.stream(spliterator());
         }
 
         public Stream<K> parallelStream() {
-            return Streams.parallelStream
-                (() -> keySpliterator(),
-                 Spliterator.SIZED | Spliterator.DISTINCT);
+            return Streams.parallelStream(spliterator());
         }
 
     }
@@ -1079,18 +1079,17 @@
             IdentityHashMap.this.clear();
         }
 
+        Spliterator<V> spliterator() {
+            return new ValueSpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+        }
+
         public Stream<V> stream() {
-            return Streams.stream
-                (() -> valueSpliterator(),
-                 Spliterator.SIZED);
+            return Streams.stream(spliterator());
         }
 
         public Stream<V> parallelStream() {
-            return Streams.parallelStream
-                (() -> valueSpliterator(),
-                 Spliterator.SIZED);
+            return Streams.parallelStream(spliterator());
         }
-
     }
 
     /**
@@ -1200,17 +1199,18 @@
             return a;
         }
 
+        Spliterator<Map.Entry<K,V>> spliterator() {
+            return new EntrySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+        }
+
         public Stream<Map.Entry<K,V>> stream() {
-            return Streams.stream
-                (() -> entrySpliterator(),
-                 Spliterator.SIZED | Spliterator.DISTINCT);
+            return Streams.stream(spliterator());
         }
 
         public Stream<Map.Entry<K,V>> parallelStream() {
-            return Streams.parallelStream
-                (() -> entrySpliterator(),
-                 Spliterator.SIZED | Spliterator.DISTINCT);
+            return Streams.parallelStream(spliterator());
         }
+
     }
 
 
@@ -1292,112 +1292,100 @@
         tab[i + 1] = value;
     }
 
-    KeySpliterator<K,V> keySpliterator() {
-        return new KeySpliterator<>(this, 0, table.length, size, modCount);
-    }
-
-    ValueSpliterator<K,V> valueSpliterator() {
-        return new ValueSpliterator<>(this, 0, table.length, size, modCount);
-    }
-
-    EntrySpliterator<K,V> entrySpliterator() {
-        return new EntrySpliterator<>(this, 0, table.length, size, modCount);
-    }
-
     /**
      * Similar form as array-based Spliterators, but skips blank elements,
      * and guestimates size as decreasing by half per split.
      */
     static class IdentityHashMapSpliterator<K,V> {
         final IdentityHashMap<K,V> map;
-        int index;                  // current index, modified on advance/split
-        final int fence;            // one past last index
-        int est;                    // size estimate
-        final int expectedModCount; // for comodification checks
+        int index;             // current index, modified on advance/split
+        int fence;             // -1 until first use; then one past last index
+        int est;               // size estimate
+        int expectedModCount;  // initialized when fence set
 
-        IdentityHashMapSpliterator(IdentityHashMap<K,V> m, int origin, 
-                                   int fence, int est,
-                                   int expectedModCount) {
-            this.map = m;
+        IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin,
+                                   int fence, int est, int expectedModCount) {
+            this.map = map;
             this.index = origin;
             this.fence = fence;
             this.est = est;
             this.expectedModCount = expectedModCount;
         }
 
-        public final long estimateSize() { return (long) est; }
-        public int characteristics() {
-            return est == map.size ? Spliterator.SIZED : 0;
+        final int getFence() { // initialize fence and size on first use
+            int hi;
+            if ((hi = fence) < 0) {
+                est = map.size;
+                expectedModCount = map.modCount;
+                hi = fence = map.table.length;
+            }
+            return hi;
+        }
+
+        public final long estimateSize() {
+            getFence(); // force init
+            return (long) est;
         }
     }
 
-    static final class KeySpliterator<K,V> 
+    static final class KeySpliterator<K,V>
         extends IdentityHashMapSpliterator<K,V>
         implements Spliterator<K> {
-        KeySpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
+        KeySpliterator(IdentityHashMap<K,V> map, int origin, int fence, int est,
                        int expectedModCount) {
-            super(m, origin, fence, est, expectedModCount);
+            super(map, origin, fence, est, expectedModCount);
         }
 
         public KeySpliterator<K,V> trySplit() {
-            int lo = index;
-            int mid = (lo + fence) >>> 1;
-            return (lo >= mid || (mid & 1) != 0)
-                   ? null
-                   : new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
-                                          expectedModCount);
+            int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
+            return (lo >= mid) ? null :
+                new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+                                        expectedModCount);
         }
 
-        public void forEach(Consumer<? super K> consumer) {
-            Object[] a;
-            int i, hi; // hoist accesses and checks from loop
-            if (consumer == null)
+        @SuppressWarnings("unchecked") 
+        public void forEach(Consumer<? super K> action) {
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = map.table).length >= (hi = fence) &&
-                (i = index) >= 0 && i < hi) {
-                index = hi;
-                do {
-                    Object key = a[i];
-                    if (key != null) {
-                        @SuppressWarnings("unchecked") K k =
-                            (K)unmaskNull(key);
-                        consumer.accept(k);
-                    }
-                } while ((i += 2) < hi);
-                if (map.modCount != expectedModCount)
-                    throw new ConcurrentModificationException();
+            int i, hi, mc; Object key;
+            IdentityHashMap<K,V> m; Object[] a;
+            if ((m = map) != null && (a = m.table) != null &&
+                (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
+                for (; i < hi; i += 2) {
+                    if ((key = a[i]) != null)
+                        action.accept((K)unmaskNull(key));
+                }
+                if (m.modCount == expectedModCount)
+                    return;
             }
+            throw new ConcurrentModificationException();
         }
 
-        public boolean tryAdvance(Consumer<? super K> consumer) {
-            Object[] a;
-            int i, hi;
-            if (consumer == null)
+        @SuppressWarnings("unchecked") 
+        public boolean tryAdvance(Consumer<? super K> action) {
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = map.table).length >= (hi = fence) && (i = index) >= 0) {
-                while (i < hi) {
-                    Object key = a[i];
-                    index = i += 2;
-                    if (key != null) {
-                        @SuppressWarnings("unchecked") K k =
-                            (K)unmaskNull(key);
-                        consumer.accept(k);
-                        if (map.modCount != expectedModCount)
-                            throw new ConcurrentModificationException();
-                        return true;
-                    }
+            Object[] a = map.table;
+            int hi = getFence();
+            while (index < hi) {
+                Object key = a[index];
+                index += 2;
+                if (key != null) {
+                    action.accept((K)unmaskNull(key));
+                    if (map.modCount != expectedModCount)
+                        throw new ConcurrentModificationException();
+                    return true;
                 }
             }
             return false;
         }
 
         public int characteristics() {
-            return super.characteristics() | Spliterator.DISTINCT;
+            return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
         }
     }
 
-
-    static final class ValueSpliterator<K,V> 
+    static final class ValueSpliterator<K,V>
         extends IdentityHashMapSpliterator<K,V>
         implements Spliterator<V> {
         ValueSpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
@@ -1406,56 +1394,57 @@
         }
 
         public ValueSpliterator<K,V> trySplit() {
-            int lo = index;
-            int mid = (lo + fence) >>> 1;
-            return (lo >= mid || (mid & 1) != 0)
-                   ? null
-                   : new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
-                                            expectedModCount);
+            int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
+            return (lo >= mid) ? null :
+                new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+                                          expectedModCount);
         }
 
-        public void forEach(Consumer<? super V> consumer) {
-            Object[] a;
-            int i, hi;
-            if (consumer == null)
+        public void forEach(Consumer<? super V> action) {
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = map.table).length >= (hi = fence) &&
-                (i = index) >= 0 && i < hi) {
-                index = hi;
-                do {
+            int i, hi, mc;
+            IdentityHashMap<K,V> m; Object[] a;
+            if ((m = map) != null && (a = m.table) != null &&
+                (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
+                for (; i < hi; i += 2) {
                     if (a[i] != null) {
                         @SuppressWarnings("unchecked") V v = (V)a[i+1];
-                        consumer.accept(v);
+                        action.accept(v);
                     }
-                } while ((i += 2) < hi);
-                if (map.modCount != expectedModCount)
-                    throw new ConcurrentModificationException();
+                }
+                if (m.modCount == expectedModCount)
+                    return;
             }
+            throw new ConcurrentModificationException();
         }
 
-        public boolean tryAdvance(Consumer<? super V> consumer) {
-            Object[] a;
-            int i, hi;
-            if (consumer == null)
+        public boolean tryAdvance(Consumer<? super V> action) {
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = map.table).length >= (hi = fence) && (i = index) >= 0) {
-                while (i < hi) {
-                    Object key = a[i];
-                    index = i += 2;
-                    if (key != null) {
-                        @SuppressWarnings("unchecked") V v = (V)a[i+1];
-                        consumer.accept(v);
-                        if (map.modCount != expectedModCount)
-                            throw new ConcurrentModificationException();
-                        return true;
-                    }
+            Object[] a = map.table;
+            int hi = getFence();
+            while (index < hi) {
+                Object key = a[index];
+                @SuppressWarnings("unchecked") V v = (V)a[index+1];
+                index += 2;
+                if (key != null) {
+                    action.accept(v);
+                    if (map.modCount != expectedModCount)
+                        throw new ConcurrentModificationException();
+                    return true;
                 }
             }
             return false;
         }
+
+        public int characteristics() {
+            return (fence < 0 || est == map.size ? SIZED : 0);
+        }
+
     }
 
-    static final class EntrySpliterator<K,V> 
+    static final class EntrySpliterator<K,V>
         extends IdentityHashMapSpliterator<K,V>
         implements Spliterator<Map.Entry<K,V>> {
         EntrySpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
@@ -1464,63 +1453,60 @@
         }
 
         public EntrySpliterator<K,V> trySplit() {
-            int lo = index;
-            int mid = (lo + fence) >>> 1;
-            return (lo >= mid || (mid & 1) != 0)
-                   ? null
-                   : new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
-                                            expectedModCount);
+            int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
+            return (lo >= mid) ? null :
+                new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+                                          expectedModCount);
         }
 
-        public void forEach(Consumer<? super Map.Entry<K,V>> consumer) {
-            Object[] a;
-            int i, hi; // hoist accesses and checks from loop
-            if (consumer == null)
+        public void forEach(Consumer<? super Map.Entry<K,V>> action) {
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = map.table).length >= (hi = fence) &&
-                (i = index) >= 0 && i < hi) {
-                index = hi;
-                do {
+            int i, hi, mc;
+            IdentityHashMap<K,V> m; Object[] a;
+            if ((m = map) != null && (a = m.table) != null &&
+                (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
+                for (; i < hi; i += 2) {
                     Object key = a[i];
                     if (key != null) {
                         @SuppressWarnings("unchecked") K k =
                             (K)unmaskNull(key);
                         @SuppressWarnings("unchecked") V v = (V)a[i+1];
-                        consumer.accept
-                                (new AbstractMap.SimpleImmutableEntry<>(k, v));
+                        action.accept
+                            (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
+
                     }
-                } while ((i += 2) < hi);
-                if (map.modCount != expectedModCount)
-                    throw new ConcurrentModificationException();
+                }
+                if (m.modCount == expectedModCount)
+                    return;
             }
+            throw new ConcurrentModificationException();
         }
 
-        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> Consumer) {
-            Object[] a;
-            int i, hi;
-            if (Consumer == null)
+        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = map.table).length >= (hi = fence) && (i = index) >= 0) {
-                while (i < hi) {
-                    Object key = a[i];
-                    index = i += 2;
-                    if (key != null) {
-                        @SuppressWarnings("unchecked") K k =
-                            (K)unmaskNull(key);
-                        @SuppressWarnings("unchecked") V v = (V)a[i+1];
-                        Consumer.accept
-                                (new AbstractMap.SimpleImmutableEntry<>(k, v));
-                        if (map.modCount != expectedModCount)
-                            throw new ConcurrentModificationException();
-                        return true;
-                    }
+            Object[] a = map.table;
+            int hi = getFence();
+            while (index < hi) {
+                Object key = a[index];
+                @SuppressWarnings("unchecked") V v = (V)a[index+1];
+                index += 2;
+                if (key != null) {
+                    @SuppressWarnings("unchecked") K k =
+                        (K)unmaskNull(key);
+                    action.accept
+                        (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
+                    if (map.modCount != expectedModCount)
+                        throw new ConcurrentModificationException();
+                    return true;
                 }
             }
             return false;
         }
 
         public int characteristics() {
-            return super.characteristics() | Spliterator.DISTINCT;
+            return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
         }
     }
 
--- a/src/share/classes/java/util/LinkedList.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/LinkedList.java	Wed Feb 20 12:03:58 2013 +0100
@@ -24,6 +24,9 @@
  */
 
 package java.util;
+import java.util.stream.Stream;
+import java.util.stream.Streams;
+import java.util.function.Consumer;
 
 /**
  * Doubly-linked list implementation of the {@code List} and {@code Deque}
@@ -1135,4 +1138,103 @@
         for (int i = 0; i < size; i++)
             linkLast((E)s.readObject());
     }
+
+    Spliterator<E> spliterator() { // to be made public later
+        return new LLSpliterator<E>(this, -1, 0);
+    }
+
+    public Stream<E> stream() {
+        return Streams.stream(spliterator());
+    }
+
+    public Stream<E> parallelStream() {
+        return Streams.parallelStream(spliterator());
+    }
+
+    // A specialization of iteratorBasedSpliterator
+    static final class LLSpliterator<E> implements Spliterator<E> {
+        static final int MAX_BATCH = 1 << 12;  // saturate batch size
+        final LinkedList<E> list; // null OK unless traversed
+        Node<E> current;      // current node; null until initialized
+        int est;              // size estimate; -1 until first needed
+        int expectedModCount; // initialized when est set
+        int batch;            // batch size for splits
+        
+        LLSpliterator(LinkedList<E> list, int est, int expectedModCount) { 
+            this.list = list;
+            this.est = est;
+            this.expectedModCount = expectedModCount;
+        }
+
+        final int getEst() {
+            int s; // force initialization
+            final LinkedList<E> lst;
+            if ((s = est) < 0) {
+                if ((lst = list) == null)
+                    s = est = 0;
+                else {
+                    expectedModCount = lst.modCount;
+                    current = lst.first;
+                    s = est = lst.size;
+                }
+            }
+            return s;
+        }
+
+        public long estimateSize() { return (long) getEst(); }
+
+        public Spliterator<E> trySplit() {
+            Node<E> p; int n;
+            if (getEst() > (n = batch + 1) && n > 0 && 
+                n <= MAX_BATCH && (p = current) != null) {
+                Object[] a = new Object[batch = n];
+                int i = 0;
+                do {
+                    a[i++] = p.item;
+                } while ((p = p.next) != null && i < n);
+                if ((current = p) == null)
+                    est = 0;
+                else if ((est -= i) <= 0)
+                    est = 1; // may eventually cause CME
+                return Collections.arraySnapshotSpliterator
+                    (a, 0, i, Spliterator.ORDERED);
+            }
+            return null;
+        }
+
+        public void forEach(Consumer<? super E> action) {
+            Node<E> p;
+            if (action == null) throw new NullPointerException();
+            if (getEst() > 0 && (p = current) != null) {
+                est = 0;
+                do {
+                    action.accept(p.item);
+                } while ((p = p.next) != null);
+                if (list.modCount != expectedModCount)
+                    throw new ConcurrentModificationException();
+            }
+        }
+
+        public boolean tryAdvance(Consumer<? super E> action) {
+            Node<E> p;
+            if (action == null) throw new NullPointerException();
+            if (getEst() > 0 && (p = current) != null) {
+                E e = p.item;
+                if ((current = p.next) == null)
+                    est = 0;
+                else if (est > 0)
+                    --est;
+                action.accept(e);
+                if (list.modCount != expectedModCount)
+                    throw new ConcurrentModificationException();
+                return true;
+            }
+            return false;
+        }
+
+        public int characteristics() {
+            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
+        }
+    }
+
 }
--- a/src/share/classes/java/util/PriorityQueue.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/PriorityQueue.java	Wed Feb 20 12:03:58 2013 +0100
@@ -783,34 +783,29 @@
         heapify();
     }
 
-    // wrapping constructor in method avoids transient javac problems
-    final PriorityQueueSpliterator<E> spliterator(int origin, int fence,
-                                                  int expectedModCount) {
-        return new PriorityQueueSpliterator<>(this, origin, fence,
-                                               expectedModCount);
+    final Spliterator<E> spliterator() {
+        return new PriorityQueueSpliterator<E>(this, 0, -1, 0);
     }
 
     public Stream<E> stream() {
-        return Streams.stream
-            (() -> spliterator(0, size, modCount),
-             PriorityQueueSpliterator.CHARACTERISTICS);
+        return Streams.stream(spliterator());
     }
 
     public Stream<E> parallelStream() {
-        return Streams.parallelStream
-            (() -> spliterator(0, size, modCount),
-             PriorityQueueSpliterator.CHARACTERISTICS);
+        return Streams.parallelStream(spliterator());
     }
 
-    /** Index-based split-by-two Spliterator */
     static final class PriorityQueueSpliterator<E> implements Spliterator<E> {
-        static final int CHARACTERISTICS = Spliterator.SIZED | Spliterator.SUBSIZED;
+        /*
+         * This is very similar to ArrayList Spliterator, except for
+         * extra null checks.
+         */
         private final PriorityQueue<E> pq;
-        private int index;                  // current index, modified on advance/split
-        private final int fence;            // one past last index
-        private final int expectedModCount; // for comodification checks
+        private int index;            // current index, modified on advance/split
+        private int fence;            // -1 until first use
+        private int expectedModCount; // initialized when fence set
 
-        /** Create new spliterator covering the given  range */
+        /** Creates new spliterator covering the given range */
         PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,
                              int expectedModCount) {
             this.pq = pq;
@@ -819,37 +814,60 @@
             this.expectedModCount = expectedModCount;
         }
 
-        public PriorityQueueSpliterator<E> trySplit() {
-            int lo = index;
-            int mid = (lo + fence) >>> 1;
-            return (lo >= mid)
-                   ? null
-                   : new PriorityQueueSpliterator<>(pq, lo, index = mid,
-                                                    expectedModCount);
+        private int getFence() { // initialize fence to size on first use
+            int hi;
+            if ((hi = fence) < 0) {
+                expectedModCount = pq.modCount;
+                hi = fence = pq.size;
+            }
+            return hi;
         }
 
-        public void forEach(Consumer<? super E> consumer) {
-            Object[] a;
-            int i, hi; // hoist accesses and checks from loop
-            if (consumer == null)
-                throw new NullPointerException();
-            if ((a = pq.queue).length >= (hi = fence) &&
-                (i = index) >= 0 && i < hi) {
-                index = hi;
-                do {
-                    @SuppressWarnings("unchecked") E e = (E) a[i];
-                    consumer.accept(e);
-                } while (++i < hi);
-                if (pq.modCount != expectedModCount)
-                    throw new ConcurrentModificationException();
-            }
+        public PriorityQueueSpliterator<E> trySplit() {
+            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+            return (lo >= mid) ? null :
+                new PriorityQueueSpliterator<E>(pq, lo, index = mid,
+                                                expectedModCount);
         }
 
-        public boolean tryAdvance(Consumer<? super E> consumer) {
-            if (index >= 0 && index < fence) {
-                @SuppressWarnings("unchecked") E e =
-                    (E)pq.queue[index++];
-                consumer.accept(e);
+        @SuppressWarnings("unchecked")
+        public void forEach(Consumer<? super E> action) {
+            int i, hi, mc; // hoist accesses and checks from loop
+            PriorityQueue<E> q; Object[] a;
+            if (action == null)
+                throw new NullPointerException();
+            if ((q = pq) != null && (a = q.queue) != null) {
+                if ((hi = fence) < 0) {
+                    mc = q.modCount;
+                    hi = q.size;
+                }
+                else
+                    mc = expectedModCount;
+                if ((i = index) >= 0 && (index = hi) <= a.length) {
+                    for (E e;; ++i) {
+                        if (i < hi) {
+                            if ((e = (E) a[i]) == null) // must be CME
+                                break;
+                            action.accept(e);
+                        }
+                        else if (q.modCount != mc)
+                            break;
+                        else
+                            return;
+                    }
+                }
+            }
+            throw new ConcurrentModificationException();
+        }
+
+        public boolean tryAdvance(Consumer<? super E> action) {
+            int hi = getFence(), lo = index;
+            if (lo >= 0 && lo < hi) {
+                index = lo + 1;
+                @SuppressWarnings("unchecked") E e = (E)pq.queue[lo];
+                if (e == null)
+                    throw new ConcurrentModificationException();
+                action.accept(e);
                 if (pq.modCount != expectedModCount)
                     throw new ConcurrentModificationException();
                 return true;
@@ -857,11 +875,12 @@
             return false;
         }
 
-        public long estimateSize() { return (long) (fence - index); }
+        public long estimateSize() {
+            return (long) (getFence() - index);
+        }
 
-        @Override
         public int characteristics() {
-            return CHARACTERISTICS;
+            return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL;
         }
     }
 }
--- a/src/share/classes/java/util/TreeMap.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/TreeMap.java	Wed Feb 20 12:03:58 2013 +0100
@@ -26,7 +26,6 @@
 package java.util;
 
 import java.util.function.Consumer;
-import java.util.function.Supplier;
 import java.util.stream.Stream;
 import java.util.stream.Streams;
 
@@ -977,16 +976,15 @@
             TreeMap.this.clear();
         }
 
+        Spliterator<V> spliterator() {
+            return new ValueSpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
+        }
         public Stream<V> stream() {
-            return Streams.stream
-                (() -> TreeMap.this.valueSpliterator(),
-                 Spliterator.SIZED | Spliterator.ORDERED);
+            return Streams.stream(spliterator());
         }
 
         public Stream<V> parallelStream() {
-            return Streams.parallelStream
-                (() -> TreeMap.this.valueSpliterator(),
-                 Spliterator.SIZED | Spliterator.ORDERED);
+            return Streams.parallelStream(spliterator());
         }
     }
 
@@ -1025,16 +1023,16 @@
             TreeMap.this.clear();
         }
 
+        Spliterator<Map.Entry<K,V>> spliterator() {
+            return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
+        }
+
         public Stream<Map.Entry<K,V>> stream() {
-            return Streams.stream
-                (() -> TreeMap.this.entrySpliterator(),
-                 Spliterator.SIZED | Spliterator.DISTINCT | Spliterator.ORDERED);
+            return Streams.stream(spliterator());
         }
 
         public Stream<Map.Entry<K,V>> parallelStream() {
-            return Streams.parallelStream
-                (() -> TreeMap.this.entrySpliterator(),
-                 Spliterator.SIZED | Spliterator.DISTINCT | Spliterator.ORDERED);
+            return Streams.parallelStream(spliterator());
         }
     }
 
@@ -1120,27 +1118,16 @@
             return new KeySet<>(m.descendingMap());
         }
 
+        Spliterator<E> spliterator() {
+            return keySpliteratorFor(m);
+        }
+
         public Stream<E> stream() {
-            int characteristics = Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
-            Supplier<Spliterator<E>> sks = supplierOfKeySpliteratorFor(m);
-            if (sks != null)
-                return Streams.stream
-                    (sks, characteristics | Spliterator.SIZED);
-            else
-                return Streams.stream
-                    (() -> Streams.spliteratorUnknownSize(iterator(), characteristics), characteristics);
-
+            return Streams.stream(spliterator());
         }
 
         public Stream<E> parallelStream() {
-            int characteristics = Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
-            Supplier<Spliterator<E>> sks = supplierOfKeySpliteratorFor(m);
-            if (sks != null)
-                return Streams.parallelStream
-                    (sks, characteristics | Spliterator.SIZED);
-            else
-                return Streams.parallelStream
-                    (() -> Streams.spliteratorUnknownSize(iterator(), characteristics), characteristics);
+            return Streams.parallelStream(spliterator());
         }
     }
 
@@ -1441,6 +1428,8 @@
         /** Returns ascending iterator from the perspective of this submap */
         abstract Iterator<K> keyIterator();
 
+        abstract Spliterator<K> keySpliterator();
+
         /** Returns descending iterator from the perspective of this submap */
         abstract Iterator<K> descendingKeyIterator();
 
@@ -1702,19 +1691,6 @@
             }
         }
 
-        final class SubMapKeyIterator extends SubMapIterator<K> {
-            SubMapKeyIterator(TreeMap.Entry<K,V> first,
-                              TreeMap.Entry<K,V> fence) {
-                super(first, fence);
-            }
-            public K next() {
-                return nextEntry().key;
-            }
-            public void remove() {
-                removeAscending();
-            }
-        }
-
         final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
             DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
                                           TreeMap.Entry<K,V> fence) {
@@ -1729,7 +1705,45 @@
             }
         }
 
-        final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
+        // Implement minimal Spliterator as KeySpliterator backup
+        final class SubMapKeyIterator extends SubMapIterator<K>
+            implements Spliterator<K> {
+            SubMapKeyIterator(TreeMap.Entry<K,V> first,
+                              TreeMap.Entry<K,V> fence) {
+                super(first, fence);
+            }
+            public K next() {
+                return nextEntry().key;
+            }
+            public void remove() {
+                removeAscending();
+            }
+
+            public void forEach(Consumer<? super K> action) {
+                while (hasNext())
+                    action.accept(next());
+            }
+            public boolean tryAdvance(Consumer<? super K> action) {
+                if (hasNext()) {
+                    action.accept(next());
+                    return true;
+                }
+                return false;
+            }
+
+            public int characteristics() {
+                return Spliterator.DISTINCT | Spliterator.ORDERED |
+                    Spliterator.SORTED;
+            }
+
+            public final Comparator<? super K>  getComparator() {
+                return NavigableSubMap.this.comparator();
+            }
+
+        }
+
+        final class DescendingSubMapKeyIterator extends SubMapIterator<K>
+            implements Spliterator<K> {
             DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
                                         TreeMap.Entry<K,V> fence) {
                 super(last, fence);
@@ -1740,6 +1754,20 @@
             public void remove() {
                 removeDescending();
             }
+            public void forEach(Consumer<? super K> action) {
+                while (hasNext())
+                    action.accept(next());
+            }
+            public boolean tryAdvance(Consumer<? super K> action) {
+                if (hasNext()) {
+                    action.accept(next());
+                    return true;
+                }
+                return false;
+            }
+            public int characteristics() {
+                return Spliterator.DISTINCT | Spliterator.ORDERED;
+            }
         }
     }
 
@@ -1799,6 +1827,10 @@
             return new SubMapKeyIterator(absLowest(), absHighFence());
         }
 
+        Spliterator<K> keySpliterator() {
+            return new SubMapKeyIterator(absLowest(), absHighFence());
+        }
+
         Iterator<K> descendingKeyIterator() {
             return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
         }
@@ -1880,6 +1912,10 @@
             return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
         }
 
+        Spliterator<K> keySpliterator() {
+            return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
+        }
+
         Iterator<K> descendingKeyIterator() {
             return new SubMapKeyIterator(absLowest(), absHighFence());
         }
@@ -2497,18 +2533,6 @@
         return level;
     }
 
-    // relays for spliterator constructors
-
-    final Spliterator<V> valueSpliterator() {
-        return new ValueSpliterator<>
-            (this, getFirstEntry(), null, 0, size, modCount);
-    }
-
-    final Spliterator<Map.Entry<K,V>> entrySpliterator() {
-        return new EntrySpliterator<>
-            (this, getFirstEntry(), null, 0, size, modCount);
-    }
-
     /**
      * Currently, we support Spliterator-based versions only for the
      * full map, in either plain of descending form, otherwise relying
@@ -2518,12 +2542,11 @@
      * structures. Callers must use plain default spliterators if this
      * returns null.
      */
-    static <K> Supplier<Spliterator<K>> supplierOfKeySpliteratorFor(NavigableMap<K,?> m) {
+    static <K> Spliterator<K> keySpliteratorFor(NavigableMap<K,?> m) {
         if (m instanceof TreeMap) {
             @SuppressWarnings("unchecked") TreeMap<K,Object> t =
                 (TreeMap<K,Object>) m;
-            return () -> new KeySpliterator<>
-                (t, t.getFirstEntry(), null, 0, t.size, t.modCount);
+            return t.keySpliterator();
         }
         if (m instanceof DescendingSubMap) {
             @SuppressWarnings("unchecked") DescendingSubMap<K,?> dm =
@@ -2532,11 +2555,20 @@
             if (dm == tm.descendingMap) {
                 @SuppressWarnings("unchecked") TreeMap<K,Object> t =
                     (TreeMap<K,Object>) tm;
-                return () -> new DescendingKeySpliterator<>
-                    (t, t.getLastEntry(), null, 0, t.size, t.modCount);
+                return t.descendingKeySpliterator();
             }
         }
-        return null;
+        @SuppressWarnings("unchecked") NavigableSubMap<K,?> sm =
+            (NavigableSubMap<K,?>) m;
+        return sm.keySpliterator();
+    }
+
+    final Spliterator<K> keySpliterator() {
+        return new KeySpliterator<K,V>(this, null, null, 0, -1, 0);
+    }
+
+    final Spliterator<K> descendingKeySpliterator() {
+        return new DescendingKeySpliterator<K,V>(this, null, null, 0, -2, 0);
     }
 
     /**
@@ -2560,6 +2592,9 @@
      * O(n) computations to determine size, which substantially limits
      * potential speed-ups of using custom Spliterators versus default
      * mechanics.
+     *
+     * To boostrap initialization, external constructors use
+     * negative size estimates: -1 for ascend, -2 for descend.
      */
     static class TreeMapSpliterator<K,V> {
         final TreeMap<K,V> tree;
@@ -2567,7 +2602,7 @@
         TreeMap.Entry<K,V> fence;   // one past last, or null
         int side;                   // 0: top, -1: is a left split, +1: right
         int est;                    // size estimate (exact only for top-level)
-        final int expectedModCount; // for CME checks
+        int expectedModCount;       // for CME checks
 
         TreeMapSpliterator(TreeMap<K,V> tree,
                            TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
@@ -2580,12 +2615,22 @@
             this.expectedModCount = expectedModCount;
         }
 
-        public final long estimateSize() {
-            return (long)est;
+        final int getEstimate() { // force initialization
+            int s; TreeMap<K,V> t;
+            if ((s = est) < 0) {
+                if ((t = tree) != null) {
+                    current = (s == -1) ? t.getFirstEntry() : t.getLastEntry();
+                    s = est = t.size;
+                    expectedModCount = t.modCount;
+                }
+                else
+                    s = est = 0;
+            }
+            return s;
         }
 
-        public int characteristics() {
-            return side == 0 ? Spliterator.SIZED : 0;
+        public final long estimateSize() {
+            return (long)getEstimate();
         }
     }
 
@@ -2599,6 +2644,8 @@
         }
 
         public KeySpliterator<K,V> trySplit() {
+            if (est < 0)
+                getEstimate(); // force initialization
             int d = side;
             TreeMap.Entry<K,V> e = current, f = fence,
                     s = ((e == null || e == f) ? null :      // empty
@@ -2614,14 +2661,16 @@
             return null;
         }
 
-        public void forEach(Consumer<? super K> consumer) {
-            if (consumer == null)
+        public void forEach(Consumer<? super K> action) {
+            if (action == null)
                 throw new NullPointerException();
+            if (est < 0)
+                getEstimate(); // force initialization
             TreeMap.Entry<K,V> f = fence, e, p, pl;
             if ((e = current) != null && e != f) {
                 current = f; // exhaust
                 do {
-                    consumer.accept(e.key);
+                    action.accept(e.key);
                     if ((p = e.right) != null) {
                         while ((pl = p.left) != null)
                             p = pl;
@@ -2636,22 +2685,30 @@
             }
         }
 
-        public boolean tryAdvance(Consumer<? super K> consumer) {
+        public boolean tryAdvance(Consumer<? super K> action) {
             TreeMap.Entry<K,V> e;
-            if (consumer == null)
+            if (action == null)
                 throw new NullPointerException();
+            if (est < 0)
+                getEstimate(); // force initialization
             if ((e = current) == null || e == fence)
                 return false;
             current = successor(e);
-            consumer.accept(e.key);
+            action.accept(e.key);
             if (tree.modCount != expectedModCount)
                 throw new ConcurrentModificationException();
             return true;
         }
 
         public int characteristics() {
-            return super.characteristics() | Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
+            return (side == 0 ? Spliterator.SIZED : 0) |
+                Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
         }
+
+        public final Comparator<? super K>  getComparator() {
+            return tree.comparator;
+        }
+
     }
 
     static final class DescendingKeySpliterator<K,V>
@@ -2664,6 +2721,8 @@
         }
 
         public DescendingKeySpliterator<K,V> trySplit() {
+            if (est < 0)
+                getEstimate(); // force initialization
             int d = side;
             TreeMap.Entry<K,V> e = current, f = fence,
                     s = ((e == null || e == f) ? null :      // empty
@@ -2679,14 +2738,16 @@
             return null;
         }
 
-        public void forEach(Consumer<? super K> consumer) {
-            if (consumer == null)
+        public void forEach(Consumer<? super K> action) {
+            if (action == null)
                 throw new NullPointerException();
+            if (est < 0)
+                getEstimate(); // force initialization
             TreeMap.Entry<K,V> f = fence, e, p, pr;
             if ((e = current) != null && e != f) {
                 current = f; // exhaust
                 do {
-                    consumer.accept(e.key);
+                    action.accept(e.key);
                     if ((p = e.left) != null) {
                         while ((pr = p.right) != null)
                             p = pr;
@@ -2701,21 +2762,24 @@
             }
         }
 
-        public boolean tryAdvance(Consumer<? super K> consumer) {
+        public boolean tryAdvance(Consumer<? super K> action) {
             TreeMap.Entry<K,V> e;
-            if (consumer == null)
+            if (action == null)
                 throw new NullPointerException();
+            if (est < 0)
+                getEstimate(); // force initialization
             if ((e = current) == null || e == fence)
                 return false;
             current = predecessor(e);
-            consumer.accept(e.key);
+            action.accept(e.key);
             if (tree.modCount != expectedModCount)
                 throw new ConcurrentModificationException();
             return true;
         }
 
         public int characteristics() {
-            return super.characteristics() | Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
+            return (side == 0 ? Spliterator.SIZED : 0) |
+                Spliterator.DISTINCT | Spliterator.ORDERED;
         }
     }
 
@@ -2729,6 +2793,8 @@
         }
 
         public ValueSpliterator<K,V> trySplit() {
+            if (est < 0)
+                getEstimate(); // force initialization
             int d = side;
             TreeMap.Entry<K,V> e = current, f = fence,
                     s = ((e == null || e == f) ? null :      // empty
@@ -2744,14 +2810,16 @@
             return null;
         }
 
-        public void forEach(Consumer<? super V> consumer) {
-            if (consumer == null)
+        public void forEach(Consumer<? super V> action) {
+            if (action == null)
                 throw new NullPointerException();
+            if (est < 0)
+                getEstimate(); // force initialization
             TreeMap.Entry<K,V> f = fence, e, p, pl;
             if ((e = current) != null && e != f) {
                 current = f; // exhaust
                 do {
-                    consumer.accept(e.value);
+                    action.accept(e.value);
                     if ((p = e.right) != null) {
                         while ((pl = p.left) != null)
                             p = pl;
@@ -2766,21 +2834,23 @@
             }
         }
 
-        public boolean tryAdvance(Consumer<? super V> consumer) {
+        public boolean tryAdvance(Consumer<? super V> action) {
             TreeMap.Entry<K,V> e;
-            if (consumer == null)
+            if (action == null)
                 throw new NullPointerException();
+            if (est < 0)
+                getEstimate(); // force initialization
             if ((e = current) == null || e == fence)
                 return false;
             current = successor(e);
-            consumer.accept(e.value);
+            action.accept(e.value);
             if (tree.modCount != expectedModCount)
                 throw new ConcurrentModificationException();
             return true;
         }
 
         public int characteristics() {
-            return super.characteristics() | Spliterator.ORDERED;
+            return (side == 0 ? Spliterator.SIZED : 0);
         }
     }
 
@@ -2794,6 +2864,8 @@
         }
 
         public EntrySpliterator<K,V> trySplit() {
+            if (est < 0)
+                getEstimate(); // force initialization
             int d = side;
             TreeMap.Entry<K,V> e = current, f = fence,
                     s = ((e == null || e == f) ? null :      // empty
@@ -2809,14 +2881,16 @@
             return null;
         }
 
-        public void forEach(Consumer<? super Map.Entry<K,V>> consumer) {
-            if (consumer == null)
+        public void forEach(Consumer<? super Map.Entry<K,V>> action) {
+            if (action == null)
                 throw new NullPointerException();
+            if (est < 0)
+                getEstimate(); // force initialization
             TreeMap.Entry<K,V> f = fence, e, p, pl;
             if ((e = current) != null && e != f) {
                 current = f; // exhaust
                 do {
-                    consumer.accept(e);
+                    action.accept(e);
                     if ((p = e.right) != null) {
                         while ((pl = p.left) != null)
                             p = pl;
@@ -2831,21 +2905,24 @@
             }
         }
 
-        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> consumer) {
+        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
             TreeMap.Entry<K,V> e;
-            if (consumer == null)
+            if (action == null)
                 throw new NullPointerException();
+            if (est < 0)
+                getEstimate(); // force initialization
             if ((e = current) == null || e == fence)
                 return false;
             current = successor(e);
-            consumer.accept(e);
+            action.accept(e);
             if (tree.modCount != expectedModCount)
                 throw new ConcurrentModificationException();
             return true;
         }
 
         public int characteristics() {
-            return super.characteristics() | Spliterator.DISTINCT | Spliterator.ORDERED;
+            return (side == 0 ? Spliterator.SIZED : 0) |
+                Spliterator.DISTINCT | Spliterator.ORDERED;
         }
     }
 }
--- a/src/share/classes/java/util/TreeSet.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/TreeSet.java	Wed Feb 20 12:03:58 2013 +0100
@@ -24,7 +24,6 @@
  */
 
 package java.util;
-import java.util.function.Supplier;
 import java.util.stream.Stream;
 import java.util.stream.Streams;
 
@@ -536,27 +535,16 @@
         tm.readTreeSet(size, s, PRESENT);
     }
 
+    Spliterator<E> spliterator() {
+        return TreeMap.keySpliteratorFor(m);
+    }
+
     public Stream<E> stream() {
-        int characteristics = Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
-        Supplier<Spliterator<E>> sks = TreeMap.supplierOfKeySpliteratorFor(m);
-        if (sks != null)
-            return Streams.stream
-                (sks, characteristics | Spliterator.SIZED);
-        else
-            return Streams.stream
-                (() -> Streams.spliteratorUnknownSize(iterator(), characteristics), characteristics);
-
+        return Streams.stream(spliterator());
     }
 
     public Stream<E> parallelStream() {
-        int characteristics = Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
-        Supplier<Spliterator<E>> sks = TreeMap.supplierOfKeySpliteratorFor(m);
-        if (sks != null)
-            return Streams.parallelStream
-                (sks, characteristics | Spliterator.SIZED);
-        else
-            return Streams.parallelStream
-                (() -> Streams.spliteratorUnknownSize(iterator(), characteristics), characteristics);
+        return Streams.parallelStream(spliterator());
     }
 
     private static final long serialVersionUID = -2479143000061671589L;
--- a/src/share/classes/java/util/Vector.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/Vector.java	Wed Feb 20 12:03:58 2013 +0100
@@ -1309,15 +1309,107 @@
         modCount++;
     }
 
-    @Override
-    public Stream<E> stream() {
-        return Streams.stream(() -> Arrays.spliterator((E[]) elementData, 0, elementCount),
-                              Spliterator.ORDERED | Spliterator.SIZED);
+    Spliterator<E> spliterator() { // to be made public later
+        return new VectorSpliterator<>(this, 0, -1, 0);
     }
 
-    @Override
+    public Stream<E> stream() {
+        return Streams.stream(spliterator());
+    }
+
     public Stream<E> parallelStream() {
-        return Streams.parallelStream(() -> Arrays.spliterator((E[]) elementData, 0, elementCount),
-                                      Spliterator.ORDERED | Spliterator.SIZED);
+        return Streams.parallelStream(spliterator());
     }
+
+    /** Similar to ArrayList Spliterator */
+    static final class VectorSpliterator<E> implements Spliterator<E> {
+        private final Vector<E> list;
+        private int index; // current index, modified on advance/split
+        private int fence; // -1 until used; then one past last index
+        private int expectedModCount; // initialized when fence set
+
+        /** Create new spliterator covering the given  range */
+        VectorSpliterator(Vector<E> list, int origin, int fence,
+                             int expectedModCount) {
+            this.list = list;
+            this.index = origin;
+            this.fence = fence;
+            this.expectedModCount = expectedModCount;
+        }
+
+        private int getFence() { // initialize fence to size on first use
+            int hi;
+            Vector<E> lst;
+            if ((hi = fence) < 0) {
+                if ((lst = list) == null)
+                    hi = fence = 0;
+                else {
+                    synchronized(lst) {
+                        expectedModCount = lst.modCount;
+                        hi = fence = lst.elementCount;
+                    }
+                }
+            }
+            return hi;
+        }
+
+        public VectorSpliterator<E> trySplit() {
+            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+            return (lo >= mid) ? null : // divide range in half unless too small
+                new VectorSpliterator<E>(list, lo, index = mid,
+                                         expectedModCount);
+        }
+
+        public boolean tryAdvance(Consumer<? super E> action) {
+            int hi = getFence(), i = index, lmc;
+            if (i < hi) {
+                index = i + 1;
+                @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
+                action.accept(e);
+                synchronized(list) { lmc = list.modCount; }
+                if (lmc != expectedModCount)
+                    throw new ConcurrentModificationException();
+                return true;
+            }
+            return false;
+        }
+
+        public void forEach(Consumer<? super E> action) {
+            int i, hi, mc, lmc; // hoist accesses and checks from loop
+            Vector<E> lst; Object[] a;
+            if (action == null)
+                throw new NullPointerException();
+            if ((lst = list) != null) {
+                synchronized(lst) {
+                    a = lst.elementData;
+                    if ((hi = fence) < 0) {
+                        mc = lst.modCount;
+                        hi = lst.elementCount;
+                    }
+                    else
+                        mc = expectedModCount;
+                }
+                if (a != null && (i = index) >= 0 && (index = hi) <= a.length) {
+                    for (; i < hi; ++i) {
+                        @SuppressWarnings("unchecked") E e = (E) a[i];
+                        action.accept(e);
+                    }
+                    synchronized(lst) { lmc = lst.modCount; }
+                    if (lmc == mc)
+                        return;
+                }
+            }
+            throw new ConcurrentModificationException();
+        }
+
+        public long estimateSize() {
+            return (long) (getFence() - index);
+        }
+
+        public int characteristics() {
+            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
+        }
+    }
+
+
 }
--- a/src/share/classes/java/util/WeakHashMap.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/WeakHashMap.java	Wed Feb 20 12:03:58 2013 +0100
@@ -902,16 +902,16 @@
             WeakHashMap.this.clear();
         }
 
+        Spliterator<K> spliterator() {
+            return new KeySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
+        }
+
         public Stream<K> stream() {
-            return Streams.stream
-                (() -> keySpliterator(),
-                 Spliterator.SIZED | Spliterator.DISTINCT);
+            return Streams.stream(spliterator());
         }
 
         public Stream<K> parallelStream() {
-            return Streams.parallelStream
-                (() -> keySpliterator(),
-                 Spliterator.SIZED | Spliterator.DISTINCT);
+            return Streams.parallelStream(spliterator());
         }
 
     }
@@ -951,16 +951,16 @@
             WeakHashMap.this.clear();
         }
 
+        Spliterator<V> spliterator() {
+            return new ValueSpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
+        }
+
         public Stream<V> stream() {
-            return Streams.stream
-                (() -> valueSpliterator(),
-                 Spliterator.SIZED);
+            return Streams.stream(spliterator());
         }
 
         public Stream<V> parallelStream() {
-            return Streams.parallelStream
-                (() -> valueSpliterator(),
-                 Spliterator.SIZED);
+            return Streams.parallelStream(spliterator());
         }
 
     }
@@ -1024,28 +1024,18 @@
             return deepCopy().toArray(a);
         }
 
+        Spliterator<Map.Entry<K,V>> spliterator() {
+            return new EntrySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
+        }
+
         public Stream<Map.Entry<K,V>> stream() {
-            return Streams.stream
-                (() -> entrySpliterator(),
-                 Spliterator.SIZED | Spliterator.DISTINCT);
+            return Streams.stream(spliterator());
         }
+
         public Stream<Map.Entry<K,V>> parallelStream() {
-            return Streams.parallelStream
-                    (() -> entrySpliterator(),
-                     Spliterator.SIZED | Spliterator.DISTINCT);
+            return Streams.parallelStream(spliterator());
         }
-    }
 
-    KeySpliterator<K,V> keySpliterator() {
-        return new KeySpliterator<>(this, 0, table.length, size(), modCount);
-    }
-
-    ValueSpliterator<K,V> valueSpliterator() {
-        return new ValueSpliterator<>(this, 0, table.length, size(), modCount);
-    }
-
-    EntrySpliterator<K,V> entrySpliterator() {
-        return new EntrySpliterator<>(this, 0, table.length, size(), modCount);
     }
 
     /**
@@ -1055,10 +1045,10 @@
     static class WeakHashMapSpliterator<K,V> {
         final WeakHashMap<K,V> map;
         WeakHashMap.Entry<K,V> current; // current node
-        int index;                      // current index, modified on advance/split
-        final int fence;                // one past last index
-        int est;                        // size estimate
-        final int expectedModCount;     // for comodification checks
+        int index;             // current index, modified on advance/split
+        int fence;             // -1 until first use; then one past last index
+        int est;               // size estimate
+        int expectedModCount;  // for comodification checks
 
         WeakHashMapSpliterator(WeakHashMap<K,V> m, int origin,
                                int fence, int est,
@@ -1070,9 +1060,20 @@
             this.expectedModCount = expectedModCount;
         }
 
-        public final long estimateSize() { return (long) est; }
-        public int characteristics() {
-            return est == map.size ? Spliterator.SIZED : 0;
+        final int getFence() { // initialize fence and size on first use
+            int hi;
+            if ((hi = fence) < 0) {
+                WeakHashMap<K,V> m = map;
+                est = m.size();
+                expectedModCount = m.modCount;
+                hi = fence = m.table.length;
+            }
+            return hi;
+        }
+
+        public final long estimateSize() { 
+            getFence(); // force init
+            return (long) est; 
         }
     }
 
@@ -1085,56 +1086,61 @@
         }
 
         public KeySpliterator<K,V> trySplit() {
-            int lo = index;
-            int mid = (lo + fence) >>> 1;
-            return (lo >= mid || current != null) ? null :
-                new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
+            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+            return (lo >= mid) ? null :
+                new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
                                         expectedModCount);
         }
 
-        public void forEach(Consumer<? super K> consumer) {
-            WeakHashMap.Entry<K,V>[] a;
-            int i, hi;
-            if (consumer == null)
+        public void forEach(Consumer<? super K> action) {
+            int i, hi, mc;
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = map.table).length >= (hi = fence) &&
-                (i = index) >= 0 && i < hi) {
+            WeakHashMap<K,V> m = map;
+            WeakHashMap.Entry<K,V>[] tab = m.table;
+            if ((hi = fence) < 0) {
+                mc = expectedModCount = m.modCount;
+                hi = fence = tab.length;
+            }
+            else
+                mc = expectedModCount;
+            if (tab.length >= hi && (i = index) >= 0 && i < hi) {
                 index = hi;
                 WeakHashMap.Entry<K,V> p = current;
                 do {
-                    Object x;
                     if (p == null)
-                        p = a[i++];
+                        p = tab[i++];
                     else {
-                        if ((x = p.get()) != null) {
+                        Object x = p.get();
+                        p = p.next;
+                        if (x != null) {
                             @SuppressWarnings("unchecked") K k =
                                 (K) WeakHashMap.unmaskNull(x);
-                            consumer.accept(k);
+                            action.accept(k);
                         }
-                        p = p.next;
                     }
                 } while (p != null || i < hi);
-                if (map.modCount != expectedModCount)
-                    throw new ConcurrentModificationException();
             }
+            if (m.modCount != mc)
+                throw new ConcurrentModificationException();
         }
 
-        public boolean tryAdvance(Consumer<? super K> consumer) {
-            WeakHashMap.Entry<K,V>[] a;
+        public boolean tryAdvance(Consumer<? super K> action) {
             int hi;
-            if (consumer == null)
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = map.table).length >= (hi = fence) && index >= 0) {
+            WeakHashMap.Entry<K,V>[] tab = map.table;
+            if (tab.length >= (hi = getFence()) && index >= 0) {
                 while (current != null || index < hi) {
                     if (current == null)
-                        current = a[index++];
+                        current = tab[index++];
                     else {
                         Object x = current.get();
                         current = current.next;
                         if (x != null) {
                             @SuppressWarnings("unchecked") K k =
                                 (K) WeakHashMap.unmaskNull(x);
-                            consumer.accept(k);
+                            action.accept(k);
                             if (map.modCount != expectedModCount)
                                 throw new ConcurrentModificationException();
                             return true;
@@ -1145,9 +1151,8 @@
             return false;
         }
 
-        @Override
         public int characteristics() {
-            return super.characteristics() | Spliterator.DISTINCT;
+            return Spliterator.DISTINCT;
         }
     }
 
@@ -1155,57 +1160,62 @@
         extends WeakHashMapSpliterator<K,V>
         implements Spliterator<V> {
         ValueSpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
-                       int expectedModCount) {
+                         int expectedModCount) {
             super(m, origin, fence, est, expectedModCount);
         }
 
         public ValueSpliterator<K,V> trySplit() {
-            int lo = index;
-            int mid = (lo + fence) >>> 1;
-            return (lo >= mid || current != null) ? null :
-                new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
+            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+            return (lo >= mid) ? null :
+                new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1,
                                           expectedModCount);
         }
 
-        public void forEach(Consumer<? super V> consumer) {
-            WeakHashMap.Entry<K,V>[] a;
-            int i, hi;
-            if (consumer == null)
+        public void forEach(Consumer<? super V> action) {
+            int i, hi, mc;
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = map.table).length >= (hi = fence) &&
-                (i = index) >= 0 && i < hi) {
+            WeakHashMap<K,V> m = map;
+            WeakHashMap.Entry<K,V>[] tab = m.table;
+            if ((hi = fence) < 0) {
+                mc = expectedModCount = m.modCount;
+                hi = fence = tab.length;
+            }
+            else
+                mc = expectedModCount;
+            if (tab.length >= hi && (i = index) >= 0 && i < hi) {
                 index = hi;
                 WeakHashMap.Entry<K,V> p = current;
                 do {
-                    Object x;
                     if (p == null)
-                        p = a[i++];
+                        p = tab[i++];
                     else {
-                        if ((x = p.get()) != null)
-                            consumer.accept(p.value);
+                        Object x = p.get();
+                        V v = p.value;
                         p = p.next;
+                        if (x != null)
+                            action.accept(v);
                     }
                 } while (p != null || i < hi);
-                if (map.modCount != expectedModCount)
-                    throw new ConcurrentModificationException();
             }
+            if (m.modCount != mc)
+                throw new ConcurrentModificationException();
         }
 
-        public boolean tryAdvance(Consumer<? super V> consumer) {
-            WeakHashMap.Entry<K,V>[] a;
+        public boolean tryAdvance(Consumer<? super V> action) {
             int hi;
-            if (consumer == null)
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = map.table).length >= (hi = fence) && index >= 0) {
+            WeakHashMap.Entry<K,V>[] tab = map.table;
+            if (tab.length >= (hi = getFence()) && index >= 0) {
                 while (current != null || index < hi) {
                     if (current == null)
-                        current = a[index++];
+                        current = tab[index++];
                     else {
-                        WeakHashMap.Entry<K,V> p = current;
-                        Object x = p.get();
+                        Object x = current.get();
                         current = current.next;
                         if (x != null) {
-                            consumer.accept(p.value);
+                            action.accept(current.value);
                             if (map.modCount != expectedModCount)
                                 throw new ConcurrentModificationException();
                             return true;
@@ -1215,6 +1225,10 @@
             }
             return false;
         }
+
+        public int characteristics() {
+            return 0;
+        }
     }
 
     static final class EntrySpliterator<K,V>
@@ -1226,61 +1240,66 @@
         }
 
         public EntrySpliterator<K,V> trySplit() {
-            int lo = index;
-            int mid = (lo + fence) >>> 1;
+            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
             return (lo >= mid) ? null :
-                new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
+                new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
                                           expectedModCount);
         }
 
-        public void forEach(Consumer<? super Map.Entry<K,V>> consumer) {
-            WeakHashMap.Entry<K,V>[] a;
-            int i, hi;
-            if (consumer == null)
+
+        public void forEach(Consumer<? super Map.Entry<K,V>> action) {
+            int i, hi, mc;
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = map.table).length >= (hi = fence) &&
-                (i = index) >= 0 && i < hi) {
+            WeakHashMap<K,V> m = map;
+            WeakHashMap.Entry<K,V>[] tab = m.table;
+            if ((hi = fence) < 0) {
+                mc = expectedModCount = m.modCount;
+                hi = fence = tab.length;
+            }
+            else
+                mc = expectedModCount;
+            if (tab.length >= hi && (i = index) >= 0 && i < hi) {
                 index = hi;
                 WeakHashMap.Entry<K,V> p = current;
                 do {
-                    Object x;
                     if (p == null)
-                        p = a[i++];
+                        p = tab[i++];
                     else {
-                        if ((x = p.get()) != null) {
+                        Object x = p.get();
+                        V v = p.value;
+                        p = p.next;
+                        if (x != null) {
                             @SuppressWarnings("unchecked") K k =
                                 (K) WeakHashMap.unmaskNull(x);
-                            V v = p.value;
-                            consumer.accept
-                                    (new AbstractMap.SimpleImmutableEntry<>(k, v));
+                            action.accept
+                                (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
                         }
-                        p = p.next;
                     }
                 } while (p != null || i < hi);
-                if (map.modCount != expectedModCount)
-                    throw new ConcurrentModificationException();
             }
+            if (m.modCount != mc)
+                throw new ConcurrentModificationException();
         }
 
-        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> consumer) {
-            WeakHashMap.Entry<K,V>[] a;
+        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
             int hi;
-            if (consumer == null)
+            if (action == null)
                 throw new NullPointerException();
-            if ((a = map.table).length >= (hi = fence) && index >= 0) {
+            WeakHashMap.Entry<K,V>[] tab = map.table;
+            if (tab.length >= (hi = getFence()) && index >= 0) {
                 while (current != null || index < hi) {
                     if (current == null)
-                        current = a[index++];
+                        current = tab[index++];
                     else {
-                        WeakHashMap.Entry<K,V> p = current;
-                        Object x = p.get();
+                        Object x = current.get();
+                        V v = current.value;
                         current = current.next;
                         if (x != null) {
                             @SuppressWarnings("unchecked") K k =
                                 (K) WeakHashMap.unmaskNull(x);
-                            V v = p.value;
-                            consumer.accept
-                                    (new AbstractMap.SimpleImmutableEntry<>(k, v));
+                            action.accept
+                                (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
                             if (map.modCount != expectedModCount)
                                 throw new ConcurrentModificationException();
                             return true;
@@ -1291,9 +1310,8 @@
             return false;
         }
 
-        @Override
         public int characteristics() {
-            return super.characteristics() | Spliterator.DISTINCT;
+            return Spliterator.DISTINCT;
         }
     }
 
--- a/src/share/classes/java/util/concurrent/ArrayBlockingQueue.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/concurrent/ArrayBlockingQueue.java	Wed Feb 20 12:03:58 2013 +0100
@@ -34,8 +34,17 @@
  */
 
 package java.util.concurrent;
-import java.util.concurrent.locks.*;
-import java.util.*;
+import java.util.concurrent.locks.Condition;
+import java.util.concurrent.locks.ReentrantLock;
+import java.util.AbstractQueue;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.lang.ref.WeakReference;
+import java.util.Spliterator;
+import java.util.stream.Stream;
+import java.util.stream.Streams;
 
 /**
  * A bounded {@linkplain BlockingQueue blocking queue} backed by an
@@ -102,32 +111,29 @@
 
     /** Main lock guarding all access */
     final ReentrantLock lock;
+
     /** Condition for waiting takes */
     private final Condition notEmpty;
+
     /** Condition for waiting puts */
     private final Condition notFull;
 
+    /**
+     * Shared state for currently active iterators, or null if there
+     * are known not to be any.  Allows queue operations to update
+     * iterator state.
+     */
+    transient Itrs itrs = null;
+
     // Internal helper methods
 
     /**
-     * Circularly increment i.
-     */
-    final int inc(int i) {
-        return (++i == items.length) ? 0 : i;
-    }
-
-    /**
      * Circularly decrement i.
      */
     final int dec(int i) {
         return ((i == 0) ? items.length : i) - 1;
     }
 
-    @SuppressWarnings("unchecked")
-    static <E> E cast(Object item) {
-        return (E) item;
-    }
-
     /**
      * Returns item at index i.
      */
@@ -150,10 +156,14 @@
      * Inserts element at current put position, advances, and signals.
      * Call only when holding lock.
      */
-    private void insert(E x) {
+    private void enqueue(E x) {
+        // assert lock.getHoldCount() == 1;
+        // assert items[putIndex] == null;
+        final Object[] items = this.items;
         items[putIndex] = x;
-        putIndex = inc(putIndex);
-        ++count;
+        if (++putIndex == items.length)
+            putIndex = 0;
+        count++;
         notEmpty.signal();
     }
 
@@ -161,43 +171,62 @@
      * Extracts element at current take position, advances, and signals.
      * Call only when holding lock.
      */
-    private E extract() {
+    private E dequeue() {
+        // assert lock.getHoldCount() == 1;
+        // assert items[takeIndex] != null;
         final Object[] items = this.items;
         @SuppressWarnings("unchecked")
         E x = (E) items[takeIndex];
         items[takeIndex] = null;
-        takeIndex = inc(takeIndex);
-        --count;
+        if (++takeIndex == items.length)
+            takeIndex = 0;
+        count--;
+        if (itrs != null)
+            itrs.elementDequeued();
         notFull.signal();
         return x;
     }
 
     /**
-     * Deletes item at position i.
-     * Utility for remove and iterator.remove.
+     * Deletes item at array index removeIndex.
+     * Utility for remove(Object) and iterator.remove.
      * Call only when holding lock.
      */
-    void removeAt(int i) {
+    void removeAt(final int removeIndex) {
+        // assert lock.getHoldCount() == 1;
+        // assert items[removeIndex] != null;
+        // assert removeIndex >= 0 && removeIndex < items.length;
         final Object[] items = this.items;
-        // if removing front item, just advance
-        if (i == takeIndex) {
+        if (removeIndex == takeIndex) {
+            // removing front item; just advance
             items[takeIndex] = null;
-            takeIndex = inc(takeIndex);
+            if (++takeIndex == items.length)
+                takeIndex = 0;
+            count--;
+            if (itrs != null)
+                itrs.elementDequeued();
         } else {
+            // an "interior" remove
+
             // slide over all others up through putIndex.
-            for (;;) {
-                int nexti = inc(i);
-                if (nexti != putIndex) {
-                    items[i] = items[nexti];
-                    i = nexti;
+            final int putIndex = this.putIndex;
+            for (int i = removeIndex;;) {
+                int next = i + 1;
+                if (next == items.length)
+                    next = 0;
+                if (next != putIndex) {
+                    items[i] = items[next];
+                    i = next;
                 } else {
                     items[i] = null;
-                    putIndex = i;
+                    this.putIndex = i;
                     break;
                 }
             }
+            count--;
+            if (itrs != null)
+                itrs.removedAt(removeIndex);
         }
-        --count;
         notFull.signal();
     }
 
@@ -302,7 +331,7 @@
             if (count == items.length)
                 return false;
             else {
-                insert(e);
+                enqueue(e);
                 return true;
             }
         } finally {
@@ -324,7 +353,7 @@
         try {
             while (count == items.length)
                 notFull.await();
-            insert(e);
+            enqueue(e);
         } finally {
             lock.unlock();
         }
@@ -351,7 +380,7 @@
                     return false;
                 nanos = notFull.awaitNanos(nanos);
             }
-            insert(e);
+            enqueue(e);
             return true;
         } finally {
             lock.unlock();
@@ -362,7 +391,7 @@
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            return (count == 0) ? null : extract();
+            return (count == 0) ? null : dequeue();
         } finally {
             lock.unlock();
         }
@@ -374,7 +403,7 @@
         try {
             while (count == 0)
                 notEmpty.await();
-            return extract();
+            return dequeue();
         } finally {
             lock.unlock();
         }
@@ -390,7 +419,7 @@
                     return null;
                 nanos = notEmpty.awaitNanos(nanos);
             }
-            return extract();
+            return dequeue();
         } finally {
             lock.unlock();
         }
@@ -400,7 +429,7 @@
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            return (count == 0) ? null : itemAt(takeIndex);
+            return itemAt(takeIndex); // null when queue is empty
         } finally {
             lock.unlock();
         }
@@ -469,11 +498,17 @@
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            for (int i = takeIndex, k = count; k > 0; i = inc(i), k--) {
-                if (o.equals(items[i])) {
-                    removeAt(i);
-                    return true;
-                }
+            if (count > 0) {
+                final int putIndex = this.putIndex;
+                int i = takeIndex;
+                do {
+                    if (o.equals(items[i])) {
+                        removeAt(i);
+                        return true;
+                    }
+                    if (++i == items.length)
+                        i = 0;
+                } while (i != putIndex);
             }
             return false;
         } finally {
@@ -495,9 +530,16 @@
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            for (int i = takeIndex, k = count; k > 0; i = inc(i), k--)
-                if (o.equals(items[i]))
-                    return true;
+            if (count > 0) {
+                final int putIndex = this.putIndex;
+                int i = takeIndex;
+                do {
+                    if (o.equals(items[i]))
+                        return true;
+                    if (++i == items.length)
+                        i = 0;
+                } while (i != putIndex);
+            }
             return false;
         } finally {
             lock.unlock();
@@ -518,18 +560,23 @@
      * @return an array containing all of the elements in this queue
      */
     public Object[] toArray() {
-        final Object[] items = this.items;
+        Object[] a;
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
             final int count = this.count;
-            Object[] a = new Object[count];
-            for (int i = takeIndex, k = 0; k < count; i = inc(i), k++)
-                a[k] = items[i];
-            return a;
+            a = new Object[count];
+            int n = items.length - takeIndex;
+            if (count <= n)
+                System.arraycopy(items, takeIndex, a, 0, count);
+            else {
+                System.arraycopy(items, takeIndex, a, 0, n);
+                System.arraycopy(items, 0, a, n, count - n);
+            }
         } finally {
             lock.unlock();
         }
+        return a;
     }
 
     /**
@@ -553,8 +600,7 @@
      * The following code can be used to dump the queue into a newly
      * allocated array of {@code String}:
      *
-     * <pre>
-     *     String[] y = x.toArray(new String[0]);</pre>
+     *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
      *
      * Note that {@code toArray(new Object[0])} is identical in function to
      * {@code toArray()}.
@@ -579,14 +625,19 @@
             if (len < count)
                 a = (T[])java.lang.reflect.Array.newInstance(
                     a.getClass().getComponentType(), count);
-            for (int i = takeIndex, k = 0; k < count; i = inc(i), k++)
-                a[k] = (T) items[i];
+            int n = items.length - takeIndex;
+            if (count <= n)
+                System.arraycopy(items, takeIndex, a, 0, count);
+            else {
+                System.arraycopy(items, takeIndex, a, 0, n);
+                System.arraycopy(items, 0, a, n, count - n);
+            }
             if (len > count)
                 a[count] = null;
-            return a;
         } finally {
             lock.unlock();
         }
+        return a;
     }
 
     public String toString() {
@@ -597,14 +648,17 @@
             if (k == 0)
                 return "[]";
 
+            final Object[] items = this.items;
             StringBuilder sb = new StringBuilder();
             sb.append('[');
-            for (int i = takeIndex; ; i = inc(i)) {
+            for (int i = takeIndex; ; ) {
                 Object e = items[i];
                 sb.append(e == this ? "(this Collection)" : e);
                 if (--k == 0)
                     return sb.append(']').toString();
                 sb.append(',').append(' ');
+                if (++i == items.length)
+                    i = 0;
             }
         } finally {
             lock.unlock();
@@ -620,12 +674,22 @@
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            for (int i = takeIndex, k = count; k > 0; i = inc(i), k--)
-                items[i] = null;
-            count = 0;
-            putIndex = 0;
-            takeIndex = 0;
-            notFull.signalAll();
+            int k = count;
+            if (k > 0) {
+                final int putIndex = this.putIndex;
+                int i = takeIndex;
+                do {
+                    items[i] = null;
+                    if (++i == items.length)
+                        i = 0;
+                } while (i != putIndex);
+                takeIndex = putIndex;
+                count = 0;
+                if (itrs != null)
+                    itrs.queueIsEmpty();
+                for (; k > 0 && lock.hasWaiters(notFull); k--)
+                    notFull.signal();
+            }
         } finally {
             lock.unlock();
         }
@@ -638,34 +702,7 @@
      * @throws IllegalArgumentException      {@inheritDoc}
      */
     public int drainTo(Collection<? super E> c) {
-        checkNotNull(c);
-        if (c == this)
-            throw new IllegalArgumentException();
-        final Object[] items = this.items;
-        final ReentrantLock lock = this.lock;
-        lock.lock();
-        try {
-            int i = takeIndex;
-            int n = 0;
-            int max = count;
-            while (n < max) {
-                @SuppressWarnings("unchecked")
-                E x = (E) items[i];
-                c.add(x);
-                items[i] = null;
-                i = inc(i);
-                ++n;
-            }
-            if (n > 0) {
-                count = 0;
-                putIndex = 0;
-                takeIndex = 0;
-                notFull.signalAll();
-            }
-            return n;
-        } finally {
-            lock.unlock();
-        }
+        return drainTo(c, Integer.MAX_VALUE);
     }
 
     /**
@@ -684,23 +721,35 @@
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            int i = takeIndex;
-            int n = 0;
-            int max = (maxElements < count) ? maxElements : count;
-            while (n < max) {
-                @SuppressWarnings("unchecked")
-                E x = (E) items[i];
-                c.add(x);
-                items[i] = null;
-                i = inc(i);
-                ++n;
+            int n = Math.min(maxElements, count);
+            int take = takeIndex;
+            int i = 0;
+            try {
+                while (i < n) {
+                    @SuppressWarnings("unchecked")
+                    E x = (E) items[take];
+                    c.add(x);
+                    items[take] = null;
+                    if (++take == items.length)
+                        take = 0;
+                    i++;
+                }
+                return n;
+            } finally {
+                // Restore invariants even if c.add() threw
+                if (i > 0) {
+                    count -= i;
+                    takeIndex = take;
+                    if (itrs != null) {
+                        if (count == 0)
+                            itrs.queueIsEmpty();
+                        else if (i > take)
+                            itrs.takeIndexWrapped();
+                    }
+                    for (; i > 0 && lock.hasWaiters(notFull); i--)
+                        notFull.signal();
+                }
             }
-            if (n > 0) {
-                count -= n;
-                takeIndex = i;
-                notFull.signalAll();
-            }
-            return n;
         } finally {
             lock.unlock();
         }
@@ -710,12 +759,12 @@
      * Returns an iterator over the elements in this queue in proper sequence.
      * The elements will be returned in order from first (head) to last (tail).
      *
-     * <p>The returned {@code Iterator} is a "weakly consistent" iterator that
+     * <p>The returned 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.
+     * 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.
      *
      * @return an iterator over the elements in this queue in proper sequence
      */
@@ -724,88 +773,643 @@
     }
 
     /**
-     * Iterator for ArrayBlockingQueue. To maintain weak consistency
-     * with respect to puts and takes, we (1) read ahead one slot, so
-     * as to not report hasNext true but then not have an element to
-     * return -- however we later recheck this slot to use the most
-     * current value; (2) ensure that each array slot is traversed at
-     * most once (by tracking "remaining" elements); (3) skip over
-     * null slots, which can occur if takes race ahead of iterators.
-     * However, for circular array-based queues, we cannot rely on any
-     * well established definition of what it means to be weakly
-     * consistent with respect to interior removes since these may
-     * require slot overwrites in the process of sliding elements to
-     * cover gaps. So we settle for resiliency, operating on
-     * established apparent nexts, which may miss some elements that
-     * have moved between calls to next.
+     * Shared data between iterators and their queue, allowing queue
+     * modifications to update iterators when elements are removed.
+     *
+     * This adds a lot of complexity for the sake of correctly
+     * handling some uncommon operations, but the combination of
+     * circular-arrays and supporting interior removes (i.e., those
+     * not at head) would cause iterators to sometimes lose their
+     * places and/or (re)report elements they shouldn't.  To avoid
+     * this, when a queue has one or more iterators, it keeps iterator
+     * state consistent by:
+     *
+     * (1) keeping track of the number of "cycles", that is, the
+     *     number of times takeIndex has wrapped around to 0.
+     * (2) notifying all iterators via the callback removedAt whenever
+     *     an interior element is removed (and thus other elements may
+     *     be shifted).
+     *
+     * These suffice to eliminate iterator inconsistencies, but
+     * unfortunately add the secondary responsibility of maintaining
+     * the list of iterators.  We track all active iterators in a
+     * simple linked list (accessed only when the queue's lock is
+     * held) of weak references to Itr.  The list is cleaned up using
+     * 3 different mechanisms:
+     *
+     * (1) Whenever a new iterator is created, do some O(1) checking for
+     *     stale list elements.
+     *
+     * (2) Whenever takeIndex wraps around to 0, check for iterators
+     *     that have been unused for more than one wrap-around cycle.
+     *
+     * (3) Whenever the queue becomes empty, all iterators are notified
+     *     and this entire data structure is discarded.
+     *
+     * So in addition to the removedAt callback that is necessary for
+     * correctness, iterators have the shutdown and takeIndexWrapped
+     * callbacks that help remove stale iterators from the list.
+     *
+     * Whenever a list element is examined, it is expunged if either
+     * the GC has determined that the iterator is discarded, or if the
+     * iterator reports that it is "detached" (does not need any
+     * further state updates).  Overhead is maximal when takeIndex
+     * never advances, iterators are discarded before they are
+     * exhausted, and all removals are interior removes, in which case
+     * all stale iterators are discovered by the GC.  But even in this
+     * case we don't increase the amortized complexity.
+     *
+     * Care must be taken to keep list sweeping methods from
+     * reentrantly invoking another such method, causing subtle
+     * corruption bugs.
+     */
+    class Itrs {
+
+        /**
+         * Node in a linked list of weak iterator references.
+         */
+        private class Node extends WeakReference<Itr> {
+            Node next;
+
+            Node(Itr iterator, Node next) {
+                super(iterator);
+                this.next = next;
+            }
+        }
+
+        /** Incremented whenever takeIndex wraps around to 0 */
+        int cycles = 0;
+
+        /** Linked list of weak iterator references */
+        private Node head;
+
+        /** Used to expunge stale iterators */
+        private Node sweeper = null;
+
+        private static final int SHORT_SWEEP_PROBES = 4;
+        private static final int LONG_SWEEP_PROBES = 16;
+
+        Itrs(Itr initial) {
+            register(initial);
+        }
+
+        /**
+         * Sweeps itrs, looking for and expunging stale iterators.
+         * If at least one was found, tries harder to find more.
+         * Called only from iterating thread.
+         *
+         * @param tryHarder whether to start in try-harder mode, because
+         * there is known to be at least one iterator to collect
+         */
+        void doSomeSweeping(boolean tryHarder) {
+            // assert lock.getHoldCount() == 1;
+            // assert head != null;
+            int probes = tryHarder ? LONG_SWEEP_PROBES : SHORT_SWEEP_PROBES;
+            Node o, p;
+            final Node sweeper = this.sweeper;
+            boolean passedGo;   // to limit search to one full sweep
+
+            if (sweeper == null) {
+                o = null;
+                p = head;
+                passedGo = true;
+            } else {
+                o = sweeper;
+                p = o.next;
+                passedGo = false;
+            }
+
+            for (; probes > 0; probes--) {
+                if (p == null) {
+                    if (passedGo)
+                        break;
+                    o = null;
+                    p = head;
+                    passedGo = true;
+                }
+                final Itr it = p.get();
+                final Node next = p.next;
+                if (it == null || it.isDetached()) {
+                    // found a discarded/exhausted iterator
+                    probes = LONG_SWEEP_PROBES; // "try harder"
+                    // unlink p
+                    p.clear();
+                    p.next = null;
+                    if (o == null) {
+                        head = next;
+                        if (next == null) {
+                            // We've run out of iterators to track; retire
+                            itrs = null;
+                            return;
+                        }
+                    }
+                    else
+                        o.next = next;
+                } else {
+                    o = p;
+                }
+                p = next;
+            }
+
+            this.sweeper = (p == null) ? null : o;
+        }
+
+        /**
+         * Adds a new iterator to the linked list of tracked iterators.
+         */
+        void register(Itr itr) {
+            // assert lock.getHoldCount() == 1;
+            head = new Node(itr, head);
+        }
+
+        /**
+         * Called whenever takeIndex wraps around to 0.
+         *
+         * Notifies all iterators, and expunges any that are now stale.
+         */
+        void takeIndexWrapped() {
+            // assert lock.getHoldCount() == 1;
+            cycles++;
+            for (Node o = null, p = head; p != null;) {
+                final Itr it = p.get();
+                final Node next = p.next;
+                if (it == null || it.takeIndexWrapped()) {
+                    // unlink p
+                    // assert it == null || it.isDetached();
+                    p.clear();
+                    p.next = null;
+                    if (o == null)
+                        head = next;
+                    else
+                        o.next = next;
+                } else {
+                    o = p;
+                }
+                p = next;
+            }
+            if (head == null)   // no more iterators to track
+                itrs = null;
+        }
+
+        /**
+         * Called whenever an interior remove (not at takeIndex) occured.
+         *
+         * Notifies all iterators, and expunges any that are now stale.
+         */
+        void removedAt(int removedIndex) {
+            for (Node o = null, p = head; p != null;) {
+                final Itr it = p.get();
+                final Node next = p.next;
+                if (it == null || it.removedAt(removedIndex)) {
+                    // unlink p
+                    // assert it == null || it.isDetached();
+                    p.clear();
+                    p.next = null;
+                    if (o == null)
+                        head = next;
+                    else
+                        o.next = next;
+                } else {
+                    o = p;
+                }
+                p = next;
+            }
+            if (head == null)   // no more iterators to track
+                itrs = null;
+        }
+
+        /**
+         * Called whenever the queue becomes empty.
+         *
+         * Notifies all active iterators that the queue is empty,
+         * clears all weak refs, and unlinks the itrs datastructure.
+         */
+        void queueIsEmpty() {
+            // assert lock.getHoldCount() == 1;
+            for (Node p = head; p != null; p = p.next) {
+                Itr it = p.get();
+                if (it != null) {
+                    p.clear();
+                    it.shutdown();
+                }
+            }
+            head = null;
+            itrs = null;
+        }
+
+        /**
+         * Called whenever an element has been dequeued (at takeIndex).
+         */
+        void elementDequeued() {
+            // assert lock.getHoldCount() == 1;
+            if (count == 0)
+                queueIsEmpty();
+            else if (takeIndex == 0)
+                takeIndexWrapped();
+        }
+    }
+
+    /**
+     * Iterator for ArrayBlockingQueue.
+     *
+     * To maintain weak consistency with respect to puts and takes, we
+     * read ahead one slot, so as to not report hasNext true but then
+     * not have an element to return.
+     *
+     * We switch into "detached" mode (allowing prompt unlinking from
+     * itrs without help from the GC) when all indices are negative, or
+     * when hasNext returns false for the first time.  This allows the
+     * iterator to track concurrent updates completely accurately,
+     * except for the corner case of the user calling Iterator.remove()
+     * after hasNext() returned false.  Even in this case, we ensure
+     * that we don't remove the wrong element by keeping track of the
+     * expected element to remove, in lastItem.  Yes, we may fail to
+     * remove lastItem from the queue if it moved due to an interleaved
+     * interior remove while in detached mode.
      */
     private class Itr implements Iterator<E> {
-        private int remaining; // Number of elements yet to be returned
-        private int nextIndex; // Index of element to be returned by next
-        private E nextItem;    // Element to be returned by next call to next
-        private E lastItem;    // Element returned by last call to next
-        private int lastRet;   // Index of last element returned, or -1 if none
+        /** Index to look for new nextItem; NONE at end */
+        private int cursor;
+
+        /** Element to be returned by next call to next(); null if none */
+        private E nextItem;
+
+        /** Index of nextItem; NONE if none, REMOVED if removed elsewhere */
+        private int nextIndex;
+
+        /** Last element returned; null if none or not detached. */
+        private E lastItem;
+
+        /** Index of lastItem, NONE if none, REMOVED if removed elsewhere */
+        private int lastRet;
+
+        /** Previous value of takeIndex, or DETACHED when detached */
+        private int prevTakeIndex;
+
+        /** Previous value of iters.cycles */
+        private int prevCycles;
+
+        /** Special index value indicating "not available" or "undefined" */
+        private static final int NONE = -1;
+
+        /**
+         * Special index value indicating "removed elsewhere", that is,
+         * removed by some operation other than a call to this.remove().
+         */
+        private static final int REMOVED = -2;
+
+        /** Special value for prevTakeIndex indicating "detached mode" */
+        private static final int DETACHED = -3;
 
         Itr() {
+            // assert lock.getHoldCount() == 0;
+            lastRet = NONE;
             final ReentrantLock lock = ArrayBlockingQueue.this.lock;
             lock.lock();
             try {
-                lastRet = -1;
-                if ((remaining = count) > 0)
+                if (count == 0) {
+                    // assert itrs == null;
+                    cursor = NONE;
+                    nextIndex = NONE;
+                    prevTakeIndex = DETACHED;
+                } else {
+                    final int takeIndex = ArrayBlockingQueue.this.takeIndex;
+                    prevTakeIndex = takeIndex;
                     nextItem = itemAt(nextIndex = takeIndex);
+                    cursor = incCursor(takeIndex);
+                    if (itrs == null) {
+                        itrs = new Itrs(this);
+                    } else {
+                        itrs.register(this); // in this order
+                        itrs.doSomeSweeping(false);
+                    }
+                    prevCycles = itrs.cycles;
+                    // assert takeIndex >= 0;
+                    // assert prevTakeIndex == takeIndex;
+                    // assert nextIndex >= 0;
+                    // assert nextItem != null;
+                }
             } finally {
                 lock.unlock();
             }
         }
 
-        public boolean hasNext() {
-            return remaining > 0;
+        boolean isDetached() {
+            // assert lock.getHoldCount() == 1;
+            return prevTakeIndex < 0;
         }
 
-        public E next() {
+        private int incCursor(int index) {
+            // assert lock.getHoldCount() == 1;
+            if (++index == items.length)
+                index = 0;
+            if (index == putIndex)
+                index = NONE;
+            return index;
+        }
+
+        /**
+         * Returns true if index is invalidated by the given number of
+         * dequeues, starting from prevTakeIndex.
+         */
+        private boolean invalidated(int index, int prevTakeIndex,
+                                    long dequeues, int length) {
+            if (index < 0)
+                return false;
+            int distance = index - prevTakeIndex;
+            if (distance < 0)
+                distance += length;
+            return dequeues > distance;
+        }
+
+        /**
+         * Adjusts indices to incorporate all dequeues since the last
+         * operation on this iterator.  Call only from iterating thread.
+         */
+        private void incorporateDequeues() {
+            // assert lock.getHoldCount() == 1;
+            // assert itrs != null;
+            // assert !isDetached();
+            // assert count > 0;
+
+            final int cycles = itrs.cycles;
+            final int takeIndex = ArrayBlockingQueue.this.takeIndex;
+            final int prevCycles = this.prevCycles;
+            final int prevTakeIndex = this.prevTakeIndex;
+
+            if (cycles != prevCycles || takeIndex != prevTakeIndex) {
+                final int len = items.length;
+                // how far takeIndex has advanced since the previous
+                // operation of this iterator
+                long dequeues = (cycles - prevCycles) * len
+                    + (takeIndex - prevTakeIndex);
+
+                // Check indices for invalidation
+                if (invalidated(lastRet, prevTakeIndex, dequeues, len))
+                    lastRet = REMOVED;
+                if (invalidated(nextIndex, prevTakeIndex, dequeues, len))
+                    nextIndex = REMOVED;
+                if (invalidated(cursor, prevTakeIndex, dequeues, len))
+                    cursor = takeIndex;
+
+                if (cursor < 0 && nextIndex < 0 && lastRet < 0)
+                    detach();
+                else {
+                    this.prevCycles = cycles;
+                    this.prevTakeIndex = takeIndex;
+                }
+            }
+        }
+
+        /**
+         * Called when itrs should stop tracking this iterator, either
+         * because there are no more indices to update (cursor < 0 &&
+         * nextIndex < 0 && lastRet < 0) or as a special exception, when
+         * lastRet >= 0, because hasNext() is about to return false for the
+         * first time.  Call only from iterating thread.
+         */
+        private void detach() {
+            // Switch to detached mode
+            // assert lock.getHoldCount() == 1;
+            // assert cursor == NONE;
+            // assert nextIndex < 0;
+            // assert lastRet < 0 || nextItem == null;
+            // assert lastRet < 0 ^ lastItem != null;
+            if (prevTakeIndex >= 0) {
+                // assert itrs != null;
+                prevTakeIndex = DETACHED;
+                // try to unlink from itrs (but not too hard)
+                itrs.doSomeSweeping(true);
+            }
+        }
+
+        /**
+         * For performance reasons, we would like not to acquire a lock in
+         * hasNext in the common case.  To allow for this, we only access
+         * fields (i.e. nextItem) that are not modified by update operations
+         * triggered by queue modifications.
+         */
+        public boolean hasNext() {
+            // assert lock.getHoldCount() == 0;
+            if (nextItem != null)
+                return true;
+            noNext();
+            return false;
+        }
+
+        private void noNext() {
             final ReentrantLock lock = ArrayBlockingQueue.this.lock;
             lock.lock();
             try {
-                if (remaining <= 0)
-                    throw new NoSuchElementException();
-                lastRet = nextIndex;
-                E x = itemAt(nextIndex);  // check for fresher value
-                if (x == null) {
-                    x = nextItem;         // we are forced to report old value
-                    lastItem = null;      // but ensure remove fails
+                // assert cursor == NONE;
+                // assert nextIndex == NONE;
+                if (!isDetached()) {
+                    // assert lastRet >= 0;
+                    incorporateDequeues(); // might update lastRet
+                    if (lastRet >= 0) {
+                        lastItem = itemAt(lastRet);
+                        // assert lastItem != null;
+                        detach();
+                    }
                 }
-                else
-                    lastItem = x;
-                while (--remaining > 0 && // skip over nulls
-                       (nextItem = itemAt(nextIndex = inc(nextIndex))) == null)
-                    ;
-                return x;
+                // assert isDetached();
+                // assert lastRet < 0 ^ lastItem != null;
             } finally {
                 lock.unlock();
             }
         }
 
-        public void remove() {
+        public E next() {
+            // assert lock.getHoldCount() == 0;
+            final E x = nextItem;
+            if (x == null)
+                throw new NoSuchElementException();
             final ReentrantLock lock = ArrayBlockingQueue.this.lock;
             lock.lock();
             try {
-                int i = lastRet;
-                if (i == -1)
-                    throw new IllegalStateException();
-                lastRet = -1;
-                E x = lastItem;
-                lastItem = null;
-                // only remove if item still at index
-                if (x != null && x == items[i]) {
-                    boolean removingHead = (i == takeIndex);
-                    removeAt(i);
-                    if (!removingHead)
-                        nextIndex = dec(nextIndex);
+                if (!isDetached())
+                    incorporateDequeues();
+                // assert nextIndex != NONE;
+                // assert lastItem == null;
+                lastRet = nextIndex;
+                final int cursor = this.cursor;
+                if (cursor >= 0) {
+                    nextItem = itemAt(nextIndex = cursor);
+                    // assert nextItem != null;
+                    this.cursor = incCursor(cursor);
+                } else {
+                    nextIndex = NONE;
+                    nextItem = null;
                 }
             } finally {
                 lock.unlock();
             }
+            return x;
         }
+
+        public void remove() {
+            // assert lock.getHoldCount() == 0;
+            final ReentrantLock lock = ArrayBlockingQueue.this.lock;
+            lock.lock();
+            try {
+                if (!isDetached())
+                    incorporateDequeues(); // might update lastRet or detach
+                final int lastRet = this.lastRet;
+                this.lastRet = NONE;
+                if (lastRet >= 0) {
+                    if (!isDetached())
+                        removeAt(lastRet);
+                    else {
+                        final E lastItem = this.lastItem;
+                        // assert lastItem != null;
+                        this.lastItem = null;
+                        if (itemAt(lastRet) == lastItem)
+                            removeAt(lastRet);
+                    }
+                } else if (lastRet == NONE)
+                    throw new IllegalStateException();
+                // else lastRet == REMOVED and the last returned element was
+                // previously asynchronously removed via an operation other
+                // than this.remove(), so nothing to do.
+
+                if (cursor < 0 && nextIndex < 0)
+                    detach();
+            } finally {
+                lock.unlock();
+                // assert lastRet == NONE;
+                // assert lastItem == null;
+            }
+        }
+
+        /**
+         * Called to notify the iterator that the queue is empty, or that it
+         * has fallen hopelessly behind, so that it should abandon any
+         * further iteration, except possibly to return one more element
+         * from next(), as promised by returning true from hasNext().
+         */
+        void shutdown() {
+            // assert lock.getHoldCount() == 1;
+            cursor = NONE;
+            if (nextIndex >= 0)
+                nextIndex = REMOVED;
+            if (lastRet >= 0) {
+                lastRet = REMOVED;
+                lastItem = null;
+            }
+            prevTakeIndex = DETACHED;
+            // Don't set nextItem to null because we must continue to be
+            // able to return it on next().
+            //
+            // Caller will unlink from itrs when convenient.
+        }
+
+        private int distance(int index, int prevTakeIndex, int length) {
+            int distance = index - prevTakeIndex;
+            if (distance < 0)
+                distance += length;
+            return distance;
+        }
+
+        /**
+         * Called whenever an interior remove (not at takeIndex) occured.
+         *
+         * @return true if this iterator should be unlinked from itrs
+         */
+        boolean removedAt(int removedIndex) {
+            // assert lock.getHoldCount() == 1;
+            if (isDetached())
+                return true;
+
+            final int cycles = itrs.cycles;
+            final int takeIndex = ArrayBlockingQueue.this.takeIndex;
+            final int prevCycles = this.prevCycles;
+            final int prevTakeIndex = this.prevTakeIndex;
+            final int len = items.length;
+            int cycleDiff = cycles - prevCycles;
+            if (removedIndex < takeIndex)
+                cycleDiff++;
+            final int removedDistance =
+                (cycleDiff * len) + (removedIndex - prevTakeIndex);
+            // assert removedDistance >= 0;
+            int cursor = this.cursor;
+            if (cursor >= 0) {
+                int x = distance(cursor, prevTakeIndex, len);
+                if (x == removedDistance) {
+                    if (cursor == putIndex)
+                        this.cursor = cursor = NONE;
+                }
+                else if (x > removedDistance) {
+                    // assert cursor != prevTakeIndex;
+                    this.cursor = cursor = dec(cursor);
+                }
+            }
+            int lastRet = this.lastRet;
+            if (lastRet >= 0) {
+                int x = distance(lastRet, prevTakeIndex, len);
+                if (x == removedDistance)
+                    this.lastRet = lastRet = REMOVED;
+                else if (x > removedDistance)
+                    this.lastRet = lastRet = dec(lastRet);
+            }
+            int nextIndex = this.nextIndex;
+            if (nextIndex >= 0) {
+                int x = distance(nextIndex, prevTakeIndex, len);
+                if (x == removedDistance)
+                    this.nextIndex = nextIndex = REMOVED;
+                else if (x > removedDistance)
+                    this.nextIndex = nextIndex = dec(nextIndex);
+            }
+            else if (cursor < 0 && nextIndex < 0 && lastRet < 0) {
+                this.prevTakeIndex = DETACHED;
+                return true;
+            }
+            return false;
+        }
+
+        /**
+         * Called whenever takeIndex wraps around to zero.
+         *
+         * @return true if this iterator should be unlinked from itrs
+         */
+        boolean takeIndexWrapped() {
+            // assert lock.getHoldCount() == 1;
+            if (isDetached())
+                return true;
+            if (itrs.cycles - prevCycles > 1) {
+                // All the elements that existed at the time of the last
+                // operation are gone, so abandon further iteration.
+                shutdown();
+                return true;
+            }
+            return false;
+        }
+
+//         /** Uncomment for debugging. */
+//         public String toString() {
+//             return ("cursor=" + cursor + " " +
+//                     "nextIndex=" + nextIndex + " " +
+//                     "lastRet=" + lastRet + " " +
+//                     "nextItem=" + nextItem + " " +
+//                     "lastItem=" + lastItem + " " +
+//                     "prevCycles=" + prevCycles + " " +
+//                     "prevTakeIndex=" + prevTakeIndex + " " +
+//                     "size()=" + size() + " " +
+//                     "remainingCapacity()=" + remainingCapacity());
+//         }
+    }
+
+    Spliterator<E> spliterator() { // cheaper to use snapshot than track array
+        return Collections.arraySnapshotSpliterator
+            (this, Spliterator.ORDERED | Spliterator.NONNULL |
+             Spliterator.CONCURRENT);
+    }
+
+    public Stream<E> stream() {
+        return Streams.stream(spliterator());
+    }
+
+    public Stream<E> parallelStream() {
+        return Streams.parallelStream(spliterator());
     }
 
 }
--- a/src/share/classes/java/util/concurrent/ConcurrentHashMap.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/concurrent/ConcurrentHashMap.java	Wed Feb 20 12:03:58 2013 +0100
@@ -124,9 +124,9 @@
  * <p>A ConcurrentHashMap can be used as scalable frequency map (a
  * form of histogram or multiset) by using {@link
  * java.util.concurrent.atomic.LongAdder} values and initializing via
- * {@link #computeIfAbsent}. For example, to add a count to a {@code
- * ConcurrentHashMap<String,LongAdder> freqs}, you can use {@code
- * freqs.computeIfAbsent(k -> new LongAdder()).increment();}
+ * {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
+ * to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
+ * {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
  *
  * <p>This class and its views and iterators implement all of the
  * <em>optional</em> methods of the {@link Map} and {@link Iterator}
@@ -178,9 +178,9 @@
  * <li> Reductions to scalar doubles, longs, and ints, using a
  * given basis value.</li>
  *
+ * </ul>
  * </li>
  * </ul>
- * </ul>
  *
  * <p>The concurrency properties of bulk operations follow
  * from those of ConcurrentHashMap: Any non-null result returned
@@ -243,8 +243,8 @@
  * @param <K> the type of keys maintained by this map
  * @param <V> the type of mapped values
  */
-public class ConcurrentHashMap<K, V>
-    implements ConcurrentMap<K, V>, Serializable {
+public class ConcurrentHashMap<K,V>
+    implements ConcurrentMap<K,V>, Serializable {
     private static final long serialVersionUID = 7249069246763182397L;
 
     /*
@@ -2217,7 +2217,7 @@
      */
     @SuppressWarnings("serial") static class Traverser<K,V,R>
         extends CountedCompleter<R> {
-        final ConcurrentHashMap<K, V> map;
+        final ConcurrentHashMap<K,V> map;
         Node<V> next;        // the next entry to use
         K nextKey;           // cached key field of next
         V nextVal;           // cached val field of next
@@ -2228,7 +2228,7 @@
         int baseSize;        // initial table size
         int batch;           // split control
         /** Creates iterator for all entries in the table. */
-        Traverser(ConcurrentHashMap<K, V> map) {
+        Traverser(ConcurrentHashMap<K,V> map) {
             this.map = map;
             Node<V>[] t;
             if ((t = tab = map.table) != null)
@@ -2287,7 +2287,7 @@
                 if (e != null)                  // advance past used/skipped node
                     e = e.next;
                 while (e == null) {             // get to next non-null bin
-                    ConcurrentHashMap<K, V> m;
+                    ConcurrentHashMap<K,V> m;
                     Node<V>[] t; int b, i, n; Object ek; //  must use locals
                     if ((t = tab) != null)
                         n = t.length;
@@ -2356,10 +2356,6 @@
 
         // spliterator support
 
-        public int characteristics() {
-            return Spliterator.CONCURRENT | Spliterator.NONNULL;
-        }
-
         public long estimateSize() {
             return batch;
         }
@@ -2458,8 +2454,8 @@
      * @return the new set
      */
     public static <K> KeySetView<K,Boolean> newKeySet() {
-        return new KeySetView<K,Boolean>(new ConcurrentHashMap<K,Boolean>(),
-                                      Boolean.TRUE);
+        return new KeySetView<K,Boolean>
+            (new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
     }
 
     /**
@@ -2576,7 +2572,7 @@
     /**
      * Legacy method testing if some key maps into the specified value
      * in this table.  This method is identical in functionality to
-     * {@link #containsValue}, and exists solely to ensure
+     * {@link #containsValue(Object)}, and exists solely to ensure
      * full compatibility with class {@link java.util.Hashtable},
      * which supported this method prior to introduction of the
      * Java Collections framework.
@@ -2805,12 +2801,11 @@
     /**
      * Returns a {@link Set} view of the keys in this map, using the
      * given common mapped value for any additions (i.e., {@link
-     * Collection#add} and {@link Collection#addAll}). This is of
-     * course only appropriate if it is acceptable to use the same
-     * value for all additions from this view.
+     * Collection#add} and {@link Collection#addAll(Collection)}).
+     * This is of course only appropriate if it is acceptable to use
+     * the same value for all additions from this view.
      *
-     * @param mappedValue the mapped value to use for any
-     * additions.
+     * @param mappedValue the mapped value to use for any additions
      * @return the set view
      * @throws NullPointerException if the mappedValue is null
      */
@@ -2824,6 +2819,8 @@
      * Returns a {@link Collection} view of the values contained in this map.
      * The collection is backed by the map, so changes to the map are
      * reflected in the collection, and vice-versa.
+     *
+     * @return the collection view
      */
     public ValuesView<K,V> values() {
         ValuesView<K,V> vs = values;
@@ -2845,6 +2842,8 @@
      * 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.
+     *
+     * @return the set view
      */
     public Set<Map.Entry<K,V>> entrySet() {
         EntrySetView<K,V> es = entrySet;
@@ -2957,8 +2956,8 @@
     @SuppressWarnings("serial") static final class KeyIterator<K,V>
         extends Traverser<K,V,Object>
         implements Spliterator<K>, Iterator<K>, Enumeration<K> {
-        KeyIterator(ConcurrentHashMap<K, V> map) { super(map); }
-        KeyIterator(ConcurrentHashMap<K, V> map, Traverser<K,V,Object> it) {
+        KeyIterator(ConcurrentHashMap<K,V> map) { super(map); }
+        KeyIterator(ConcurrentHashMap<K,V> map, Traverser<K,V,Object> it) {
             super(map, it);
         }
         public KeyIterator<K,V> trySplit() {
@@ -2991,13 +2990,19 @@
             block.accept(nextKey);
             return true;
         }
+
+        public int characteristics() {
+            return Spliterator.DISTINCT | Spliterator.CONCURRENT | 
+                Spliterator.NONNULL;
+        }
+
     }
 
     @SuppressWarnings("serial") static final class ValueIterator<K,V>
         extends Traverser<K,V,Object>
         implements Spliterator<V>, Iterator<V>, Enumeration<V> {
-        ValueIterator(ConcurrentHashMap<K, V> map) { super(map); }
-        ValueIterator(ConcurrentHashMap<K, V> map, Traverser<K,V,Object> it) {
+        ValueIterator(ConcurrentHashMap<K,V> map) { super(map); }
+        ValueIterator(ConcurrentHashMap<K,V> map, Traverser<K,V,Object> it) {
             super(map, it);
         }
         public ValueIterator<K,V> trySplit() {
@@ -3034,13 +3039,16 @@
             return true;
         }
 
+        public int characteristics() {
+            return Spliterator.CONCURRENT | Spliterator.NONNULL;
+        }
     }
 
     @SuppressWarnings("serial") static final class EntryIterator<K,V>
         extends Traverser<K,V,Object>
         implements Spliterator<Map.Entry<K,V>>, Iterator<Map.Entry<K,V>> {
-        EntryIterator(ConcurrentHashMap<K, V> map) { super(map); }
-        EntryIterator(ConcurrentHashMap<K, V> map, Traverser<K,V,Object> it) {
+        EntryIterator(ConcurrentHashMap<K,V> map) { super(map); }
+        EntryIterator(ConcurrentHashMap<K,V> map, Traverser<K,V,Object> it) {
             super(map, it);
         }
         public EntryIterator<K,V> trySplit() {
@@ -3076,16 +3084,20 @@
             return true;
         }
 
+        public int characteristics() {
+            return Spliterator.DISTINCT | Spliterator.CONCURRENT | 
+                Spliterator.NONNULL;
+        }
     }
 
     /**
      * Exported Entry for iterators
      */
-    static final class MapEntry<K,V> implements Map.Entry<K, V> {
+    static final class MapEntry<K,V> implements Map.Entry<K,V> {
         final K key; // non-null
         V val;       // non-null
-        final ConcurrentHashMap<K, V> map;
-        MapEntry(K key, V val, ConcurrentHashMap<K, V> map) {
+        final ConcurrentHashMap<K,V> map;
+        MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
             this.key = key;
             this.val = val;
             this.map = map;
@@ -3277,7 +3289,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case the action is not applied).
+     * which case the action is not applied)
      * @param action the action
      */
     public <U> void forEachSequentially
@@ -3321,7 +3333,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case it is not combined).
+     * which case it is not combined)
      * @param reducer a commutative associative combining function
      * @return the result of accumulating the given transformation
      * of all (key, value) pairs
@@ -3434,7 +3446,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case the action is not applied).
+     * which case the action is not applied)
      * @param action the action
      */
     public <U> void forEachKeySequentially
@@ -3499,7 +3511,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case it is not combined).
+     * which case it is not combined)
      * @param reducer a commutative associative combining function
      * @return the result of accumulating the given transformation
      * of all keys
@@ -3612,7 +3624,8 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case the action is not applied).
+     * which case the action is not applied)
+     * @param action the action
      */
     public <U> void forEachValueSequentially
         (Function<? super V, ? extends U> transformer,
@@ -3672,7 +3685,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case it is not combined).
+     * which case it is not combined)
      * @param reducer a commutative associative combining function
      * @return the result of accumulating the given transformation
      * of all values
@@ -3786,7 +3799,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case the action is not applied).
+     * which case the action is not applied)
      * @param action the action
      */
     public <U> void forEachEntrySequentially
@@ -3849,7 +3862,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case it is not combined).
+     * which case it is not combined)
      * @param reducer a commutative associative combining function
      * @return the result of accumulating the given transformation
      * of all entries
@@ -3961,7 +3974,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case the action is not applied).
+     * which case the action is not applied)
      * @param action the action
      */
     public <U> void forEachInParallel
@@ -3996,7 +4009,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case it is not combined).
+     * which case it is not combined)
      * @param reducer a commutative associative combining function
      * @return the result of accumulating the given transformation
      * of all (key, value) pairs
@@ -4084,7 +4097,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case the action is not applied).
+     * which case the action is not applied)
      * @param action the action
      */
     public <U> void forEachKeyInParallel
@@ -4133,7 +4146,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case it is not combined).
+     * which case it is not combined)
      * @param reducer a commutative associative combining function
      * @return the result of accumulating the given transformation
      * of all keys
@@ -4221,7 +4234,8 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case the action is not applied).
+     * which case the action is not applied)
+     * @param action the action
      */
     public <U> void forEachValueInParallel
         (Function<? super V, ? extends U> transformer,
@@ -4268,7 +4282,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case it is not combined).
+     * which case it is not combined)
      * @param reducer a commutative associative combining function
      * @return the result of accumulating the given transformation
      * of all values
@@ -4356,7 +4370,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case the action is not applied).
+     * which case the action is not applied)
      * @param action the action
      */
     public <U> void forEachEntryInParallel
@@ -4404,7 +4418,7 @@
      *
      * @param transformer a function returning the transformation
      * for an element, or null if there is no transformation (in
-     * which case it is not combined).
+     * which case it is not combined)
      * @param reducer a commutative associative combining function
      * @return the result of accumulating the given transformation
      * of all entries
@@ -4482,10 +4496,11 @@
     /**
      * Base class for views.
      */
-    abstract static class CHMView<K, V> implements java.io.Serializable {
+    abstract static class CHMCollectionView<K,V,E>
+            implements Collection<E>, java.io.Serializable {
         private static final long serialVersionUID = 7249069246763182397L;
-        final ConcurrentHashMap<K, V> map;
-        CHMView(ConcurrentHashMap<K, V> map)  { this.map = map; }
+        final ConcurrentHashMap<K,V> map;
+        CHMCollectionView(ConcurrentHashMap<K,V> map)  { this.map = map; }
 
         /**
          * Returns the map backing this view.
@@ -4494,12 +4509,25 @@
          */
         public ConcurrentHashMap<K,V> getMap() { return map; }
 
-        public final int size()                 { return map.size(); }
-        public final boolean isEmpty()          { return map.isEmpty(); }
-        public final void clear()               { map.clear(); }
+        /**
+         * Removes all of the elements from this view, by removing all
+         * the mappings from the map backing this view.
+         */
+        public final void clear()      { map.clear(); }
+        public final int size()        { return map.size(); }
+        public final boolean isEmpty() { return map.isEmpty(); }
 
         // implementations below rely on concrete classes supplying these
-        public abstract Iterator<?> iterator();
+        // abstract methods
+        /**
+         * Returns 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.
+         */
+        public abstract Iterator<E> iterator();
         public abstract boolean contains(Object o);
         public abstract boolean remove(Object o);
 
@@ -4507,13 +4535,12 @@
 
         public final Object[] toArray() {
             long sz = map.mappingCount();
-            if (sz > (long)(MAX_ARRAY_SIZE))
+            if (sz > MAX_ARRAY_SIZE)
                 throw new OutOfMemoryError(oomeMsg);
             int n = (int)sz;
             Object[] r = new Object[n];
             int i = 0;
-            Iterator<?> it = iterator();
-            while (it.hasNext()) {
+            for (E e : this) {
                 if (i == n) {
                     if (n >= MAX_ARRAY_SIZE)
                         throw new OutOfMemoryError(oomeMsg);
@@ -4523,14 +4550,15 @@
                         n += (n >>> 1) + 1;
                     r = Arrays.copyOf(r, n);
                 }
-                r[i++] = it.next();
+                r[i++] = e;
             }
             return (i == n) ? r : Arrays.copyOf(r, i);
         }
 
-        @SuppressWarnings("unchecked") public final <T> T[] toArray(T[] a) {
+        @SuppressWarnings("unchecked")
+        public final <T> T[] toArray(T[] a) {
             long sz = map.mappingCount();
-            if (sz > (long)(MAX_ARRAY_SIZE))
+            if (sz > MAX_ARRAY_SIZE)
                 throw new OutOfMemoryError(oomeMsg);
             int m = (int)sz;
             T[] r = (a.length >= m) ? a :
@@ -4538,8 +4566,7 @@
                 .newInstance(a.getClass().getComponentType(), m);
             int n = r.length;
             int i = 0;
-            Iterator<?> it = iterator();
-            while (it.hasNext()) {
+            for (E e : this) {
                 if (i == n) {
                     if (n >= MAX_ARRAY_SIZE)
                         throw new OutOfMemoryError(oomeMsg);
@@ -4549,7 +4576,7 @@
                         n += (n >>> 1) + 1;
                     r = Arrays.copyOf(r, n);
                 }
-                r[i++] = (T)it.next();
+                r[i++] = (T)e;
             }
             if (a == r && i < n) {
                 r[i] = null; // null-terminate
@@ -4558,17 +4585,21 @@
             return (i == n) ? r : Arrays.copyOf(r, i);
         }
 
-        public final int hashCode() {
-            int h = 0;
-            for (Iterator<?> it = iterator(); it.hasNext();)
-                h += it.next().hashCode();
-            return h;
-        }
-
+        /**
+         * Returns a string representation of this collection.
+         * The string representation consists of the string representations
+         * of the collection's elements in the order they are returned by
+         * its iterator, enclosed in square brackets ({@code "[]"}).
+         * Adjacent elements are separated by the characters {@code ", "}
+         * (comma and space).  Elements are converted to strings as by
+         * {@link String#valueOf(Object)}.
+         *
+         * @return a string representation of this collection
+         */
         public final String toString() {
             StringBuilder sb = new StringBuilder();
             sb.append('[');
-            Iterator<?> it = iterator();
+            Iterator<E> it = iterator();
             if (it.hasNext()) {
                 for (;;) {
                     Object e = it.next();
@@ -4583,8 +4614,7 @@
 
         public final boolean containsAll(Collection<?> c) {
             if (c != this) {
-                for (Iterator<?> it = c.iterator(); it.hasNext();) {
-                    Object e = it.next();
+                for (Object e : c) {
                     if (e == null || !contains(e))
                         return false;
                 }
@@ -4594,7 +4624,7 @@
 
         public final boolean removeAll(Collection<?> c) {
             boolean modified = false;
-            for (Iterator<?> it = iterator(); it.hasNext();) {
+            for (Iterator<E> it = iterator(); it.hasNext();) {
                 if (c.contains(it.next())) {
                     it.remove();
                     modified = true;
@@ -4605,7 +4635,7 @@
 
         public final boolean retainAll(Collection<?> c) {
             boolean modified = false;
-            for (Iterator<?> it = iterator(); it.hasNext();) {
+            for (Iterator<E> it = iterator(); it.hasNext();) {
                 if (!c.contains(it.next())) {
                     it.remove();
                     modified = true;
@@ -4616,18 +4646,53 @@
 
     }
 
+    abstract static class CHMSetView<K,V,E>
+            extends CHMCollectionView<K,V,E>
+            implements Set<E>, java.io.Serializable {
+        private static final long serialVersionUID = 7249069246763182397L;
+        CHMSetView(ConcurrentHashMap<K,V> map) { super(map); }
+
+        // Implement Set API
+
+        /**
+         * Implements {@link Set#hashCode()}.
+         * @return the hash code value for this set
+         */
+        public final int hashCode() {
+            int h = 0;
+            for (E e : this)
+                h += e.hashCode();
+            return h;
+        }
+
+        /**
+         * Implements {@link Set#equals(Object)}.
+         * @param o object to be compared for equality with this set
+         * @return {@code true} if the specified object is equal to this set
+        */
+        public final boolean equals(Object o) {
+            Set<?> c;
+            return ((o instanceof Set) &&
+                    ((c = (Set<?>)o) == this ||
+                     (containsAll(c) && c.containsAll(this))));
+        }
+    }
+
     /**
      * A view of a ConcurrentHashMap as a {@link Set} of keys, in
      * which additions may optionally be enabled by mapping to a
-     * common value.  This class cannot be directly instantiated. See
-     * {@link #keySet}, {@link #keySet(Object)}, {@link #newKeySet()},
-     * {@link #newKeySet(int)}.
+     * common value.  This class cannot be directly instantiated.
+     * See {@link #keySet() keySet()},
+     * {@link #keySet(Object) keySet(V)},
+     * {@link #newKeySet() newKeySet()},
+     * {@link #newKeySet(int) newKeySet(int)}.
      */
-    public static class KeySetView<K,V> extends CHMView<K,V>
-        implements Set<K>, java.io.Serializable {
+    public static class KeySetView<K,V>
+            extends CHMSetView<K,V,K>
+            implements Set<K>, java.io.Serializable {
         private static final long serialVersionUID = 7249069246763182397L;
         private final V value;
-        KeySetView(ConcurrentHashMap<K, V> map, V value) {  // non-public
+        KeySetView(ConcurrentHashMap<K,V> map, V value) {  // non-public
             super(map);
             this.value = value;
         }
@@ -4637,66 +4702,84 @@
          * or {@code null} if additions are not supported.
          *
          * @return the default mapped value for additions, or {@code null}
-         * if not supported.
+         * if not supported
          */
         public V getMappedValue() { return value; }
 
-        // implement Set API
-
+        /**
+         * {@inheritDoc}
+         * @throws NullPointerException if the specified key is null
+         */
         public boolean contains(Object o) { return map.containsKey(o); }
-        public boolean remove(Object o)   { return map.remove(o) != null; }
 
         /**
-         * Returns 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.
+         * Removes the key from this map view, by removing the key (and its
+         * corresponding value) from the backing map.  This method does
+         * nothing if the key is not in the map.
          *
-         * @return an iterator over the keys of this map
+         * @param  o the key to be removed from the backing map
+         * @return {@code true} if the backing map contained the specified key
+         * @throws NullPointerException if the specified key is null
          */
-        public Iterator<K> iterator()     { return new KeyIterator<K,V>(map); }
+        public boolean remove(Object o) { return map.remove(o) != null; }
+
+        /**
+         * @return an iterator over the keys of the backing map
+         */
+        public Iterator<K> iterator() { return new KeyIterator<K,V>(map); }
+
+        /**
+         * Adds the specified key to this set view by mapping the key to
+         * the default mapped value in the backing map, if defined.
+         *
+         * @param e key to be added
+         * @return {@code true} if this set changed as a result of the call
+         * @throws NullPointerException if the specified key is null
+         * @throws UnsupportedOperationException if no default mapped value
+         * for additions was provided
+         */
         public boolean add(K e) {
             V v;
             if ((v = value) == null)
                 throw new UnsupportedOperationException();
-            if (e == null)
-                throw new NullPointerException();
             return map.internalPut(e, v, true) == null;
         }
+
+        /**
+         * Adds all of the elements in the specified collection to this set,
+         * as if by calling {@link #add} on each one.
+         *
+         * @param c the elements to be inserted into this set
+         * @return {@code true} if this set changed as a result of the call
+         * @throws NullPointerException if the collection or any of its
+         * elements are {@code null}
+         * @throws UnsupportedOperationException if no default mapped value
+         * for additions was provided
+         */
         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 (map.internalPut(e, v, true) == null)
                     added = true;
             }
             return added;
         }
-        public boolean equals(Object o) {
-            Set<?> c;
-            return ((o instanceof Set) &&
-                    ((c = (Set<?>)o) == this ||
-                     (containsAll(c) && c.containsAll(this))));
-        }
 
         public Stream<K> stream() {
-            return Streams.stream(new KeyIterator<>(map));
+            return Streams.stream(new KeyIterator<>(map, null));
         }
         public Stream<K> parallelStream() {
-            return Streams.parallelStream(new KeyIterator<>(map));
+            return Streams.parallelStream(new KeyIterator<K,V>(map, null));
         }
     }
 
     /**
      * A view of a ConcurrentHashMap as a {@link Collection} of
      * values, in which additions are disabled. This class cannot be
-     * directly instantiated. See {@link #values},
+     * directly instantiated. See {@link #values()}.
      *
      * <p>The view's {@code iterator} is a "weakly consistent" iterator
      * that will never throw {@link ConcurrentModificationException},
@@ -4704,15 +4787,17 @@
      * construction of the iterator, and may (but is not guaranteed to)
      * reflect any modifications subsequent to construction.
      */
-    public static final class ValuesView<K,V> extends CHMView<K,V>
-        implements Collection<V> {
+    public static final class ValuesView<K,V>
+            extends CHMCollectionView<K,V,V>
+            implements Collection<V>, java.io.Serializable {
         private static final long serialVersionUID = 2249069246763182397L;
-        ValuesView(ConcurrentHashMap<K, V> map)   { super(map); }
-        public final boolean contains(Object o) { return map.containsValue(o); }
+        ValuesView(ConcurrentHashMap<K,V> map) { super(map); }
+        public final boolean contains(Object o) {
+            return map.containsValue(o);
+        }
         public final boolean remove(Object o) {
             if (o != null) {
-                Iterator<V> it = new ValueIterator<K,V>(map);
-                while (it.hasNext()) {
+                for (Iterator<V> it = iterator(); it.hasNext();) {
                     if (o.equals(it.next())) {
                         it.remove();
                         return true;
@@ -4723,31 +4808,27 @@
         }
 
         /**
-         * Returns 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.
-         *
-         * @return an iterator over the values of this map
+         * @return an iterator over the values of the backing map
          */
         public final Iterator<V> iterator() {
             return new ValueIterator<K,V>(map);
         }
+
+        /** Always throws {@link UnsupportedOperationException}. */
         public final boolean add(V e) {
             throw new UnsupportedOperationException();
         }
+        /** Always throws {@link UnsupportedOperationException}. */
         public final boolean addAll(Collection<? extends V> c) {
             throw new UnsupportedOperationException();
         }
 
         public Stream<V> stream() {
-            return Streams.stream(new ValueIterator<>(map));
+            return Streams.stream(new ValueIterator<K,V>(map, null));
         }
 
         public Stream<V> parallelStream() {
-            return Streams.parallelStream(new ValueIterator<>(map, null));
+            return Streams.parallelStream(new ValueIterator<K,V>(map, null));
         }
 
     }
@@ -4755,12 +4836,14 @@
     /**
      * A view of a ConcurrentHashMap as a {@link Set} of (key, value)
      * entries.  This class cannot be directly instantiated. See
-     * {@link #entrySet}.
+     * {@link #entrySet()}.
      */
-    public static final class EntrySetView<K,V> extends CHMView<K,V>
-        implements Set<Map.Entry<K,V>> {
+    public static final class EntrySetView<K,V>
+            extends CHMSetView<K,V,Map.Entry<K,V>>
+            implements Set<Map.Entry<K,V>>, java.io.Serializable {
         private static final long serialVersionUID = 2249069246763182397L;
-        EntrySetView(ConcurrentHashMap<K, V> map) { super(map); }
+        EntrySetView(ConcurrentHashMap<K,V> map) { super(map); }
+
         public final boolean contains(Object o) {
             Object k, v, r; Map.Entry<?,?> e;
             return ((o instanceof Map.Entry) &&
@@ -4778,26 +4861,31 @@
         }
 
         /**
-         * Returns 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.
-         *
-         * @return an iterator over the entries of this map
+         * @return an iterator over the entries of the backing map
          */
         public final Iterator<Map.Entry<K,V>> iterator() {
             return new EntryIterator<K,V>(map);
         }
 
+        /**
+         * Adds the specified mapping to this view.
+         *
+         * @param e mapping to be added
+         * @return {@code true} if this set changed as a result of the call
+         * @throws NullPointerException if the entry, its key, or its
+         * value is null
+         */
         public final boolean add(Entry<K,V> e) {
-            K key = e.getKey();
-            V value = e.getValue();
-            if (key == null || value == null)
-                throw new NullPointerException();
-            return map.internalPut(key, value, false) == null;
-        }
+            return map.internalPut(e.getKey(), e.getValue(), false) == null;
+        }
+        /**
+         * Adds all of the mappings in the specified collection to this
+         * set, as if by calling {@link #add(Map.Entry)} on each one.
+         * @param c the mappings to be inserted into this set
+         * @return {@code true} if this set changed as a result of the call
+         * @throws NullPointerException if the collection or any of its
+         * entries, keys, or values are null
+         */
         public final boolean addAll(Collection<? extends Entry<K,V>> c) {
             boolean added = false;
             for (Entry<K,V> e : c) {
@@ -4806,19 +4894,13 @@
             }
             return added;
         }
-        public boolean equals(Object o) {
-            Set<?> c;
-            return ((o instanceof Set) &&
-                    ((c = (Set<?>)o) == this ||
-                     (containsAll(c) && c.containsAll(this))));
-        }
 
         public Stream<Map.Entry<K,V>> stream() {
-            return Streams.stream(new EntryIterator<>(map));
+            return Streams.stream(new EntryIterator<K,V>(map, null));
         }
 
         public Stream<Map.Entry<K,V>> parallelStream() {
-            return Streams.parallelStream(new EntryIterator<>(map, null));
+            return Streams.parallelStream(new EntryIterator<K,V>(map, null));
         }
     }
 
@@ -4901,7 +4983,7 @@
          * @param map the map
          * @param transformer a function returning the transformation
          * for an element, or null if there is no transformation (in
-         * which case it is not combined).
+         * which case it is not combined)
          * @param reducer a commutative associative combining function
          * @return the task
          */
@@ -4969,6 +5051,7 @@
          * using the given reducer to combine values, and the given
          * basis as an identity value.
          *
+         * @param map the map
          * @param transformer a function returning the transformation
          * for an element
          * @param basis the identity (initial default value) for the reduction
@@ -5068,7 +5151,7 @@
          * @param map the map
          * @param transformer a function returning the transformation
          * for an element, or null if there is no transformation (in
-         * which case it is not combined).
+         * which case it is not combined)
          * @param reducer a commutative associative combining function
          * @return the task
          */
@@ -5160,6 +5243,7 @@
          *
          * @param map the map
          * @param action the action
+         * @return the task
          */
         public static <K,V> ForkJoinTask<Void> forEachValue
             (ConcurrentHashMap<K,V> map,
@@ -5177,6 +5261,7 @@
          * for an element, or null if there is no transformation (in
          * which case the action is not applied)
          * @param action the action
+         * @return the task
          */
         public static <K,V,U> ForkJoinTask<Void> forEachValue
             (ConcurrentHashMap<K,V> map,
@@ -5234,7 +5319,7 @@
          * @param map the map
          * @param transformer a function returning the transformation
          * for an element, or null if there is no transformation (in
-         * which case it is not combined).
+         * which case it is not combined)
          * @param reducer a commutative associative combining function
          * @return the task
          */
@@ -5326,6 +5411,7 @@
          *
          * @param map the map
          * @param action the action
+         * @return the task
          */
         public static <K,V> ForkJoinTask<Void> forEachEntry
             (ConcurrentHashMap<K,V> map,
@@ -5343,6 +5429,7 @@
          * for an element, or null if there is no transformation (in
          * which case the action is not applied)
          * @param action the action
+         * @return the task
          */
         public static <K,V,U> ForkJoinTask<Void> forEachEntry
             (ConcurrentHashMap<K,V> map,
@@ -5400,7 +5487,7 @@
          * @param map the map
          * @param transformer a function returning the transformation
          * for an element, or null if there is no transformation (in
-         * which case it is not combined).
+         * which case it is not combined)
          * @param reducer a commutative associative combining function
          * @return the task
          */
--- a/src/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java	Wed Feb 20 12:03:58 2013 +0100
@@ -38,10 +38,14 @@
 import java.util.AbstractCollection;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.Deque;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
 import java.util.Queue;
+import java.util.Spliterator;
+import java.util.stream.Stream;
+import java.util.stream.Streams;
 
 /**
  * An unbounded concurrent {@linkplain Deque deque} based on linked nodes.
@@ -816,7 +820,7 @@
      * Creates an array list and fills it with elements of this list.
      * Used by toArray.
      *
-     * @return the arrayList
+     * @return the array list
      */
     private ArrayList<E> toArrayList() {
         ArrayList<E> list = new ArrayList<E>();
@@ -1385,6 +1389,20 @@
         Node<E> nextNode(Node<E> p) { return pred(p); }
     }
 
+    Spliterator<E> spliterator() {
+        return Collections.iteratorBasedSpliterator
+            (iterator(), Spliterator.ORDERED | Spliterator.NONNULL |
+             Spliterator.CONCURRENT);
+    }
+
+    public Stream<E> stream() {
+        return Streams.stream(spliterator());
+    }
+
+    public Stream<E> parallelStream() {
+        return Streams.parallelStream(spliterator());
+    }
+
     /**
      * Saves this deque to a stream (that is, serializes it).
      *
--- a/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java	Wed Feb 20 12:03:58 2013 +0100
@@ -38,9 +38,14 @@
 import java.util.AbstractQueue;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
 import java.util.Queue;
+import java.util.Spliterator;
+import java.util.stream.Stream;
+import java.util.stream.Streams;
+import java.util.function.Consumer;
 
 /**
  * An unbounded thread-safe {@linkplain Queue queue} based on linked nodes.
@@ -295,7 +300,7 @@
     }
 
     /**
-     * Try to CAS head to p. If successful, repoint old head to itself
+     * Tries to CAS head to p. If successful, repoint old head to itself
      * as sentinel for succ(), below.
      */
     final void updateHead(Node<E> h, Node<E> p) {
@@ -792,6 +797,104 @@
         tail = t;
     }
 
+    static final class CLQSpliterator<E> implements Spliterator<E> {
+        static final int MAX_BATCH = 1 << 10;  // saturate batch size
+        final ConcurrentLinkedQueue<E> queue;
+        Node<E> current;    // current node; null until initialized
+        int batch;          // batch size for splits
+        boolean exhausted;  // true when no more nodes
+        CLQSpliterator(ConcurrentLinkedQueue<E> queue) {
+            this.queue = queue;
+        }
+
+        /*
+         * Split into arrays of arithmetically increasing batch sizes,
+         * giving up at MAX_BATCH.  This will only improve parallel
+         * performance if per-element forEach actions are more costly
+         * than transfering them into an array. If not, we limit
+         * slowdowns by eventually returning null split.
+         */
+        public Spliterator<E> trySplit() {
+            Node<E> p; int n;
+            final ConcurrentLinkedQueue<E> q = this.queue;
+            if (!exhausted && (n = batch + 1) > 0 && n <= MAX_BATCH &&
+                ((p = current) != null || (p = q.first()) != null)) {
+                Object[] a = new Object[batch = n];
+                int i = 0;
+                do {
+                    if ((a[i] = p.item) != null)
+                        ++i;
+                    if (p == (p = p.next))
+                        p = q.first();
+                } while (p != null && i < n);
+                if ((current = p) == null)
+                    exhausted = true;
+                return Collections.arraySnapshotSpliterator
+                    (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |
+                     Spliterator.CONCURRENT);
+            }
+            return null;
+        }
+
+        public void forEach(Consumer<? super E> action) {
+            Node<E> p;
+            if (action == null) throw new NullPointerException();
+            final ConcurrentLinkedQueue<E> q = this.queue;
+            if (!exhausted &&
+                ((p = current) != null || (p = q.first()) != null)) {
+                exhausted = true;
+                do {
+                    E e = p.item;
+                    if (p == (p = p.next))
+                        p = q.first();
+                    if (e != null)
+                        action.accept(e);
+                } while (p != null);
+            }
+        }
+
+        public boolean tryAdvance(Consumer<? super E> action) {
+            Node<E> p;
+            if (action == null) throw new NullPointerException();
+            final ConcurrentLinkedQueue<E> q = this.queue;
+            if (!exhausted &&
+                ((p = current) != null || (p = q.first()) != null)) {
+                E e;
+                do {
+                    e = p.item;
+                    if (p == (p = p.next))
+                        p = q.first();
+                } while (e == null && p != null);
+                if ((current = p) == null)
+                    exhausted = true;
+                if (e != null) {
+                    action.accept(e);
+                    return true;
+                }
+            }
+            return false;
+        }
+
+        public int characteristics() {
+            return Spliterator.ORDERED | Spliterator.NONNULL |
+                Spliterator.CONCURRENT;
+        }
+    }
+
+
+    Spliterator<E> spliterator() {
+        return new CLQSpliterator<E>(this);
+    }
+
+    public Stream<E> stream() {
+        return Streams.stream(spliterator());
+    }
+
+    public Stream<E> parallelStream() {
+        return Streams.parallelStream(spliterator());
+    }
+
+
     /**
      * Throws NullPointerException if argument is null.
      *
--- a/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java	Wed Feb 20 12:03:58 2013 +0100
@@ -40,7 +40,6 @@
 import java.util.stream.Streams;
 import java.util.function.Consumer;
 
-
 /**
  * A scalable concurrent {@link ConcurrentNavigableMap} implementation.
  * The map is sorted according to the {@linkplain Comparable natural
@@ -86,7 +85,7 @@
  * elements.
  *
  * <p>A {@link Set} projection of a ConcurrentSkipListMap may be
- * created (using {@link #newKeySet()}}), or viewed (using {@link
+ * created (using {@link #newKeySet()}), or viewed (using {@link
  * #keySet(Object)} when only keys are of interest, and the mapped
  * values are (perhaps transiently) not used or all take the same
  * mapping value.
@@ -100,7 +99,6 @@
  * @param <V> the type of mapped values
  * @since 1.6
  */
-@SuppressWarnings("unchecked")
 public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
     implements ConcurrentNavigableMap<K,V>,
                Cloneable,
@@ -505,6 +503,7 @@
          * @return this node's value if it isn't a marker or header or
          * is deleted, else null.
          */
+        @SuppressWarnings("unchecked")
         V getValidValue() {
             Object v = value;
             if (v == this || v == BASE_HEADER)
@@ -641,6 +640,7 @@
      * Compares using comparator or natural ordering. Used in cases
      * where it isn't worthwhile to use multiple code paths.
      */
+    @SuppressWarnings("unchecked")
     int compare(K k1, K k2) throws ClassCastException {
         Comparator<? super K> cmp = comparator;
         if (cmp != null)
@@ -816,9 +816,10 @@
                 }
                 if (v == n || b.value == null)  // b is deleted
                     break;
+                @SuppressWarnings("unchecked") V vv = (V)v;
                 int c = key.compareTo(n.key);
                 if (c == 0)
-                    return (V)v;
+                    return vv;
                 if (c < 0)
                     return null;
                 b = n;
@@ -864,9 +865,11 @@
                         n = f;
                         continue;
                     }
+
                     if (c == 0) {
-                        if (onlyIfAbsent || n.casValue(v, value))
-                            return (V)v;
+                        @SuppressWarnings("unchecked") V vv = (V)v;
+                        if (onlyIfAbsent || n.casValue(vv, value))
+                            return vv;
                         else
                             break; // restart if lost race to replace value
                     }
@@ -886,6 +889,7 @@
      * 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();
@@ -1040,7 +1044,8 @@
                     if (head.right == null)
                         tryReduceLevel();
                 }
-                return (V)v;
+                @SuppressWarnings("unchecked") V vv = (V)v;
+                return vv;
             }
         }
     }
@@ -1121,7 +1126,8 @@
             if (!n.appendMarker(f) || !b.casNext(n, f))
                 findFirst(); // retry
             clearIndexToFirst();
-            return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, (V)v);
+            @SuppressWarnings("unchecked") V vv = (V)v;
+            return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, vv);
         }
     }
 
@@ -1149,6 +1155,7 @@
      * Specialized variant of doRemove.
      * @return null if empty, else snapshot of last entry
      */
+    @SuppressWarnings("unchecked")
     Map.Entry<K,V> doRemoveLastEntry() {
         for (;;) {
             Node<K,V> b = findPredecessorOfLast();
@@ -1410,9 +1417,10 @@
                 }
                 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 (V)v;
+                    return vv;
                 if (c < 0)
                     return null;
                 b = n;
@@ -1446,8 +1454,9 @@
                         continue;
                     }
                     if (c == 0) {
-                        if (onlyIfAbsent || n.casValue(v, value))
-                            return (V)v;
+                        @SuppressWarnings("unchecked") V vv = (V)v;
+                        if (onlyIfAbsent || n.casValue(vv, value))
+                            return vv;
                         else
                             break; // restart if lost race to replace value
                     }
@@ -1502,7 +1511,8 @@
                     if (head.right == null)
                         tryReduceLevel();
                 }
-                return (V)v;
+                @SuppressWarnings("unchecked") V vv = (V)v;
+                return vv;
             }
         }
     }
@@ -1757,6 +1767,7 @@
     /**
      * Reconstitutes this map from a stream (that is, deserializes it).
      */
+    @SuppressWarnings("unchecked")
     private void readObject(final java.io.ObjectInputStream s)
         throws java.io.IOException, ClassNotFoundException {
         // Read in the Comparator and any hidden stuff
@@ -2004,9 +2015,9 @@
     /**
      * Returns a {@link Set} view of the keys in this map, using the
      * given common mapped value for any additions (i.e., {@link
-     * Collection#add} and {@link Collection#addAll}). This is of
-     * course only appropriate if it is acceptable to use the same
-     * value for all additions from this view.
+     * Collection#add} and {@link Collection#addAll(Collection)}).
+     * This is of course only appropriate if it is acceptable to use
+     * the same value for all additions from this view.
      *
      * @param mappedValue the mapped value to use for any
      * additions.
@@ -2168,6 +2179,7 @@
             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);
@@ -2197,14 +2209,15 @@
             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)
                 return null;
-            Object v = n.value;
+            @SuppressWarnings("unchecked") V v = (V)n.value;
             if (v != null && n.casValue(v, value))
-                return (V)v;
+                return v;
         }
     }
 
@@ -2473,7 +2486,8 @@
                     break;
                 Object x = next.value;
                 if (x != null && x != next) {
-                    nextValue = (V) x;
+                    @SuppressWarnings("unchecked") V vv = (V)x;
+                    nextValue = vv;
                     break;
                 }
             }
@@ -2494,7 +2508,8 @@
                     break;
                 Object x = next.value;
                 if (x != null && x != next) {
-                    nextValue = (V) x;
+                    @SuppressWarnings("unchecked") V vv = (V)x;
+                    nextValue = vv;
                     break;
                 }
             }
@@ -2591,6 +2606,7 @@
             Map.Entry<E,?> e = m.pollLastEntry();
             return (e == null) ? null : e.getKey();
         }
+        @SuppressWarnings("unchecked")
         public Iterator<E> iterator() {
             if (m instanceof ConcurrentSkipListMap)
                 return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
@@ -2641,25 +2657,20 @@
         public NavigableSet<E> descendingSet() {
             return new KeySet<E>(m.descendingMap());
         }
+        @SuppressWarnings("unchecked")
+        Spliterator<E> spliterator() {
+            if (m instanceof ConcurrentSkipListMap)
+                return ((ConcurrentSkipListMap<E,?>)m).keySpliterator();
+            else
+                return (Spliterator<E>)((SubMap<E,?>)m).keyIterator();
+        }
 
         public Stream<E> stream() {
-            if (m instanceof ConcurrentSkipListMap)
-                return Streams.stream
-                    (((ConcurrentSkipListMap<E,?>)m).keySpliterator());
-            else
-                return Streams.stream
-                    (Streams.spliteratorUnknownSize(iterator(),
-                     Spliterator.CONCURRENT | Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED));
+            return Streams.stream(spliterator());
         }
 
         public Stream<E> parallelStream() {
-            if (m instanceof ConcurrentSkipListMap)
-                return Streams.parallelStream
-                    (((ConcurrentSkipListMap<E,?>)m).keySpliterator());
-            else
-                return Streams.parallelStream
-                    (Streams.spliteratorUnknownSize(iterator(),
-                     Spliterator.CONCURRENT | Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED));
+            return Streams.parallelStream(spliterator());
         }
     }
 
@@ -2668,6 +2679,7 @@
         Values(ConcurrentNavigableMap<?, E> map) {
             m = map;
         }
+        @SuppressWarnings("unchecked")
         public Iterator<E> iterator() {
             if (m instanceof ConcurrentSkipListMap)
                 return ((ConcurrentSkipListMap<?,E>)m).valueIterator();
@@ -2688,25 +2700,20 @@
         }
         public Object[] toArray()     { return toList(this).toArray();  }
         public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
+        @SuppressWarnings("unchecked")
+        Spliterator<E> spliterator() {
+            if (m instanceof ConcurrentSkipListMap)
+                return ((ConcurrentSkipListMap<?,E>)m).valueSpliterator();
+            else
+                return (Spliterator<E>)((SubMap<?,E>)m).valueIterator();
+        }
 
         public Stream<E> stream() {
-            if (m instanceof ConcurrentSkipListMap)
-                return Streams.stream
-                    (((ConcurrentSkipListMap<?,E>)m).valueSpliterator());
-            else
-                return Streams.stream
-                    (Streams.spliteratorUnknownSize(iterator(),
-                     Spliterator.CONCURRENT | Spliterator.ORDERED));
+            return Streams.stream(spliterator());
         }
 
         public Stream<E> parallelStream() {
-            if (m instanceof ConcurrentSkipListMap)
-                return Streams.parallelStream
-                    (((ConcurrentSkipListMap<?,E>)m).valueSpliterator());
-            else
-                return Streams.parallelStream
-                    (Streams.spliteratorUnknownSize(iterator(),
-                     Spliterator.CONCURRENT | Spliterator.ORDERED));
+            return Streams.parallelStream(spliterator());
         }
     }
 
@@ -2715,7 +2722,7 @@
         EntrySet(ConcurrentNavigableMap<K1, V1> map) {
             m = map;
         }
-
+        @SuppressWarnings("unchecked")
         public Iterator<Map.Entry<K1,V1>> iterator() {
             if (m instanceof ConcurrentSkipListMap)
                 return ((ConcurrentSkipListMap<K1,V1>)m).entryIterator();
@@ -2762,25 +2769,21 @@
         }
         public Object[] toArray()     { return toList(this).toArray();  }
         public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
-
-        @Override public Stream<Map.Entry<K1,V1>> stream() {
+        @SuppressWarnings("unchecked")
+        Spliterator<Map.Entry<K1,V1>> spliterator() {
             if (m instanceof ConcurrentSkipListMap)
-                return Streams.stream
-                    (((ConcurrentSkipListMap<K1,V1>)m).entrySpliterator());
+                return ((ConcurrentSkipListMap<K1,V1>)m).entrySpliterator();
             else
-                return Streams.stream
-                    (Streams.spliteratorUnknownSize(iterator(),
-                     Spliterator.CONCURRENT | Spliterator.DISTINCT | Spliterator.ORDERED));
+                return (Spliterator<Map.Entry<K1,V1>>)
+                    ((SubMap<K1,V1>)m).entryIterator();
         }
+        
+        public Stream<Map.Entry<K1,V1>> stream() {
+            return Streams.stream(spliterator());
+        }
 
         public Stream<Map.Entry<K1,V1>> parallelStream() {
-            if (m instanceof ConcurrentSkipListMap)
-                return Streams.parallelStream
-                    (((ConcurrentSkipListMap<K1,V1>)m).entrySpliterator());
-            else
-                return Streams.parallelStream
-                    (Streams.spliteratorUnknownSize(iterator(),
-                     Spliterator.CONCURRENT | Spliterator.DISTINCT | Spliterator.ORDERED));
+            return Streams.parallelStream(spliterator());
         }
 
     }
@@ -3055,13 +3058,13 @@
 
         public boolean containsKey(Object key) {
             if (key == null) throw new NullPointerException();
-            K k = (K)key;
+            @SuppressWarnings("unchecked") K k = (K)key;
             return inBounds(k) && m.containsKey(k);
         }
 
         public V get(Object key) {
             if (key == null) throw new NullPointerException();
-            K k = (K)key;
+            @SuppressWarnings("unchecked") K k = (K)key;
             return (!inBounds(k)) ? null : m.get(k);
         }
 
@@ -3071,7 +3074,7 @@
         }
 
         public V remove(Object key) {
-            K k = (K)key;
+            @SuppressWarnings("unchecked") K k = (K)key;
             return (!inBounds(k)) ? null : m.remove(k);
         }
 
@@ -3120,7 +3123,7 @@
         }
 
         public boolean remove(Object key, Object value) {
-            K k = (K)key;
+            @SuppressWarnings("unchecked") K k = (K)key;
             return inBounds(k) && m.remove(k, value);
         }
 
@@ -3324,8 +3327,9 @@
 
         /**
          * Variant of main Iter class to traverse through submaps.
+         * Also serves as back-up Spliterator for views
          */
-        abstract class SubMapIter<T> implements Iterator<T> {
+        abstract class SubMapIter<T> implements Iterator<T>, Spliterator<T> {
             /** the last node returned by next() */
             Node<K,V> lastReturned;
             /** the next node to return from next(); */
@@ -3340,10 +3344,11 @@
                         break;
                     Object x = next.value;
                     if (x != null && x != next) {
+                        @SuppressWarnings("unchecked") V vv = (V)x;
                         if (! inBounds(next.key))
                             next = null;
                         else
-                            nextValue = (V) x;
+                            nextValue = vv;
                         break;
                     }
                 }
@@ -3370,10 +3375,11 @@
                         break;
                     Object x = next.value;
                     if (x != null && x != next) {
+                        @SuppressWarnings("unchecked") V vv = (V)x;
                         if (tooHigh(next.key))
                             next = null;
                         else
-                            nextValue = (V) x;
+                            nextValue = vv;
                         break;
                     }
                 }
@@ -3388,10 +3394,11 @@
                         break;
                     Object x = next.value;
                     if (x != null && x != next) {
+                        @SuppressWarnings("unchecked") V vv = (V)x;
                         if (tooLow(next.key))
                             next = null;
                         else
-                            nextValue = (V) x;
+                            nextValue = vv;
                         break;
                     }
                 }
@@ -3405,6 +3412,18 @@
                 lastReturned = null;
             }
 
+            public boolean tryAdvance(Consumer<? super T> action) {
+                if (hasNext()) {
+                    action.accept(next());
+                    return true;
+                }
+                return false;
+            }
+
+            public void forEach(Consumer<? super T> action) {
+                while (hasNext())
+                    action.accept(next());
+            }
         }
 
         final class SubMapValueIterator extends SubMapIter<V> {
@@ -3413,6 +3432,9 @@
                 advance();
                 return v;
             }
+            public int characteristics() {
+                return 0;
+            }
         }
 
         final class SubMapKeyIterator extends SubMapIter<K> {
@@ -3421,6 +3443,13 @@
                 advance();
                 return n.key;
             }
+            public int characteristics() {
+                return Spliterator.DISTINCT | Spliterator.ORDERED |
+                    Spliterator.SORTED;
+            }
+            public final Comparator<? super K>  getComparator() {
+                return SubMap.this.comparator();
+            }
         }
 
         final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
@@ -3430,6 +3459,9 @@
                 advance();
                 return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
             }
+            public int characteristics() {
+                return Spliterator.DISTINCT;
+            }
         }
     }
 
@@ -3437,7 +3469,7 @@
      * A view of a ConcurrentSkipListMap as a {@link Set} of keys, in
      * which additions may optionally be enabled by mapping to a
      * common value.  This class cannot be directly instantiated. See
-     * {@link #keySet}, {@link #keySet(Object)}, {@link #newKeySet()},
+     * {@link #keySet()}, {@link #keySet(Object)}, {@link #newKeySet()},
      * {@link #newKeySet(Comparator)}.
      */
     public static class KeySetView<K,V> extends AbstractSet<K>
@@ -3450,10 +3482,10 @@
          */
 
         private static final long serialVersionUID = 7249069246763182397L;
-        private final ConcurrentSkipListMap<K, V> m;
+        private final ConcurrentSkipListMap<K,V> m;
         private final V value;
 
-        KeySetView(ConcurrentSkipListMap<K, V> map, V value) {  // non-public
+        KeySetView(ConcurrentSkipListMap<K,V> map, V value) {  // non-public
             this.m = map;
             this.value = value;
         }
@@ -3563,12 +3595,16 @@
             return new KeySet<K>(m.descendingMap());
         }
 
+        Spliterator<K> spliterator() {
+            return m.keySpliterator();
+        }
+
         public Stream<K> stream() {
-            return Streams.stream(m.keySpliterator());
+            return Streams.stream(spliterator());
         }
 
         public Stream<K> parallelStream() {
-            return Streams.parallelStream(m.keySpliterator());
+            return Streams.parallelStream(spliterator());
         }
 
     }
@@ -3625,6 +3661,7 @@
         }
 
         /** 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)
@@ -3637,9 +3674,6 @@
 
         public final long estimateSize() { return (long)est; }
 
-        public int characteristics() {
-            return (est == 0 && current == null ? Spliterator.SIZED : 0) | Spliterator.CONCURRENT | Spliterator.NONNULL;
-        }
     }
 
     // factory methods
@@ -3663,6 +3697,7 @@
             super(comparator, row, origin, fence, est);
         }
 
+        @SuppressWarnings("unchecked")
         public KeySpliterator<K,V> trySplit() {
             Node<K,V> e;
             Comparator<? super K> cmp = comparator;
@@ -3693,10 +3728,11 @@
             return null;
         }
 
-        public void forEach(Consumer<? super K> block) {
-            if (block == null) throw new NullPointerException();
+        public void forEach(Consumer<? super K> action) {
+            if (action == null) throw new NullPointerException();
             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;
@@ -3708,12 +3744,12 @@
                      (f != null && cmp.compare(f, k) <= 0)))
                     break;
                 if ((v = e.value) != null && v != e)
-                    block.accept(k);
+                    action.accept(k);
             }
         }
 
-        public boolean tryAdvance(Consumer<? super K> block) {
-            if (block == null) throw new NullPointerException();
+        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) {
                 K k; Object v;
@@ -3723,7 +3759,7 @@
                 }
                 if ((v = e.value) != null && v != e) {
                     current = e.next;
-                    block.accept(k);
+                    action.accept(k);
                     return true;
                 }
             }
@@ -3732,7 +3768,13 @@
         }
 
         public int characteristics() {
-            return super.characteristics() | Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
+            return  Spliterator.DISTINCT | Spliterator.SORTED | 
+                Spliterator.ORDERED | Spliterator.CONCURRENT | 
+                Spliterator.NONNULL;
+        }
+
+        public final Comparator<? super K>  getComparator() {
+            return comparator;
         }
     }
 
@@ -3744,6 +3786,7 @@
             super(comparator, row, origin, fence, est);
         }
 
+        @SuppressWarnings("unchecked")
         public ValueSpliterator<K,V> trySplit() {
             Node<K,V> e;
             Comparator<? super K> cmp = comparator;
@@ -3774,10 +3817,11 @@
             return null;
         }
 
-        public void forEach(Consumer<? super V> block) {
-            if (block == null) throw new NullPointerException();
+        public void forEach(Consumer<? super V> action) {
+            if (action == null) throw new NullPointerException();
             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;
@@ -3788,13 +3832,15 @@
                     (cf != null ? (cf.compareTo(k) <= 0) :
                      (f != null && cmp.compare(f, k) <= 0)))
                     break;
-                if ((v = e.value) != null && v != e)
-                    block.accept((V)v);
+                if ((v = e.value) != null && v != e) {
+                    @SuppressWarnings("unchecked") V vv = (V)v;
+                    action.accept(vv);
+                }
             }
         }
 
-        public boolean tryAdvance(Consumer<? super V> block) {
-            if (block == null) throw new NullPointerException();
+        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) {
@@ -3805,7 +3851,8 @@
                 }
                 if ((v = e.value) != null && v != e) {
                     current = e.next;
-                    block.accept((V)v);
+                    @SuppressWarnings("unchecked") V vv = (V)v;
+                    action.accept(vv);
                     return true;
                 }
             }
@@ -3814,7 +3861,7 @@
         }
 
         public int characteristics() {
-            return super.characteristics() | Spliterator.ORDERED;
+            return Spliterator.CONCURRENT | Spliterator.NONNULL;
         }
     }
 
@@ -3826,6 +3873,7 @@
             super(comparator, row, origin, fence, est);
         }
 
+        @SuppressWarnings("unchecked")
         public EntrySpliterator<K,V> trySplit() {
             Node<K,V> e;
             Comparator<? super K> cmp = comparator;
@@ -3857,10 +3905,11 @@
             return null;
         }
 
-        public void forEach(Consumer<? super Map.Entry<K,V>> block) {
-            if (block == null) throw new NullPointerException();
+        public void forEach(Consumer<? super Map.Entry<K,V>> action) {
+            if (action == null) throw new NullPointerException();
             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;
@@ -3872,14 +3921,16 @@
                      (cf.compareTo(k) <= 0) :
                      (f != null && cmp.compare(f, k) <= 0)))
                     break;
-                if ((v = e.value) != null && v != e)
-                    block.accept
-                        (new AbstractMap.SimpleImmutableEntry<K,V>(k, (V)v));
+                if ((v = e.value) != null && v != e) {
+                    @SuppressWarnings("unchecked") V vv = (V)v;
+                    action.accept
+                        (new AbstractMap.SimpleImmutableEntry<K,V>(k, vv));
+                }
             }
         }
 
-        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> block) {
-            if (block == null) throw new NullPointerException();
+        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) {
                 K k; Object v;
@@ -3889,8 +3940,9 @@
                 }
                 if ((v = e.value) != null && v != e) {
                     current = e.next;
-                    block.accept
-                        (new AbstractMap.SimpleImmutableEntry<K,V>(k, (V)v));
+                    @SuppressWarnings("unchecked") V vv = (V)v;
+                    action.accept
+                        (new AbstractMap.SimpleImmutableEntry<K,V>(k, vv));
                     return true;
                 }
             }
@@ -3899,7 +3951,9 @@
         }
 
         public int characteristics() {
-            return super.characteristics() | Spliterator.DISTINCT | Spliterator.ORDERED;
+            return  Spliterator.DISTINCT | Spliterator.SORTED | 
+                Spliterator.ORDERED | Spliterator.CONCURRENT | 
+                Spliterator.NONNULL;
         }
     }
 
--- a/src/share/classes/java/util/concurrent/ConcurrentSkipListSet.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/concurrent/ConcurrentSkipListSet.java	Wed Feb 20 12:03:58 2013 +0100
@@ -34,7 +34,15 @@
  */
 
 package java.util.concurrent;
-import java.util.*;
+import java.util.AbstractSet;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NavigableSet;
+import java.util.Set;
+import java.util.SortedSet;
 import java.util.Spliterator;
 import java.util.stream.Stream;
 import java.util.stream.Streams;
@@ -473,24 +481,20 @@
         return new ConcurrentSkipListSet<E>(m.descendingMap());
     }
 
-    public Stream<E> stream() {
+    @SuppressWarnings("unchecked")
+    Spliterator<E> spliterator() {
         if (m instanceof ConcurrentSkipListMap)
-            return Streams.stream
-                (((ConcurrentSkipListMap<E,?>)m).keySpliterator());
+            return ((ConcurrentSkipListMap<E,?>)m).keySpliterator();
         else
-            return Streams.stream
-                (Streams.spliteratorUnknownSize(iterator(),
-                 Spliterator.CONCURRENT | Spliterator.NONNULL | Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED));
+            return (Spliterator<E>)((ConcurrentSkipListMap.SubMap<E,?>)m).keyIterator();
     }
 
+    public Stream<E> stream() {
+        return Streams.stream(spliterator());
+    }
+    
     public Stream<E> parallelStream() {
-        if (m instanceof ConcurrentSkipListMap)
-            return Streams.parallelStream
-                (((ConcurrentSkipListMap<E,?>)m).keySpliterator());
-        else
-            return Streams.parallelStream
-                (Streams.spliteratorUnknownSize(iterator(),
-                 Spliterator.CONCURRENT | Spliterator.NONNULL | Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED));
+        return Streams.parallelStream(spliterator());
     }
 
     // Support for resetting map in clone
--- a/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/concurrent/CopyOnWriteArrayList.java	Wed Feb 20 12:03:58 2013 +0100
@@ -44,20 +44,20 @@
  */
 
 package java.util.concurrent;
+import java.util.AbstractList;
 import java.util.Arrays;
 import java.util.Collection;
+import java.util.Collections;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
 import java.util.List;
-import java.util.AbstractList;
-import java.util.Iterator;
 import java.util.ListIterator;
+import java.util.NoSuchElementException;
 import java.util.RandomAccess;
-import java.util.NoSuchElementException;
-import java.util.ConcurrentModificationException;
 import java.util.Spliterator;
+import java.util.concurrent.locks.ReentrantLock;
 import java.util.stream.Stream;
 import java.util.stream.Streams;
-import java.util.function.Consumer;
-import java.util.concurrent.locks.ReentrantLock;
 
 /**
  * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
@@ -1011,17 +1011,17 @@
         return new COWIterator<E>(elements, index);
     }
 
+    Spliterator<E> spliterator() {
+        return Collections.arraySnapshotSpliterator
+            (getArray(), Spliterator.IMMUTABLE | Spliterator.ORDERED);
+    }
+
     public Stream<E> stream() {
-        Object[] a = getArray();
-        int n = a.length;
-        return Streams.stream
-            (new COWSpliterator<>(a, 0, n));
+        return Streams.stream(spliterator());
+
     }
     public Stream<E> parallelStream() {
-        Object[] a = getArray();
-        int n = a.length;
-        return Streams.parallelStream
-            (new COWSpliterator<>(a, 0, n));
+        return Streams.parallelStream(spliterator());
     }
 
     static final class COWIterator<E> implements ListIterator<E> {
@@ -1295,7 +1295,7 @@
             }
         }
 
-        public Stream<E> stream() {
+        Spliterator<E> spliterator() {
             int lo = offset;
             int hi = offset + size;
             Object[] a = expectedArray;
@@ -1303,25 +1303,19 @@
                 throw new ConcurrentModificationException();
             if (lo < 0 || hi > a.length)
                 throw new IndexOutOfBoundsException();
-            return Streams.stream
-                (new COWSpliterator<>(a, lo, hi));
+            return Collections.arraySnapshotSpliterator
+                (a, lo, hi, Spliterator.IMMUTABLE | Spliterator.ORDERED);
+        }
+
+        public Stream<E> stream() {
+            return Streams.stream(spliterator());
         }
 
         public Stream<E> parallelStream() {
-            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();
-            return Streams.parallelStream
-                (new COWSpliterator<>(a, lo, hi));
+            return Streams.parallelStream(spliterator());
         }
-
     }
 
-
     private static class COWSubListIterator<E> implements ListIterator<E> {
         private final ListIterator<E> it;
         private final int offset;
@@ -1376,55 +1370,6 @@
         }
     }
 
-    /** Index-based split-by-two Spliterator */
-    static class COWSpliterator<E> implements Spliterator<E> {
-        private final Object[] array;
-        private int index;        // current index, modified on advance/split
-        private final int fence;  // one past last index
-
-        /** Create new spliterator covering the given array and range */
-        COWSpliterator(Object[] array, int origin, int fence) {
-            this.array = array; this.index = origin; this.fence = fence;
-        }
-
-        public COWSpliterator<E> trySplit() {
-            int lo = index, mid = (lo + fence) >>> 1;
-            return (lo >= mid) ? null :
-                new COWSpliterator<E>(array, lo, index = mid);
-        }
-
-        public void forEach(Consumer<? super E> block) {
-            Object[] a; int i, hi; // hoist accesses and checks from loop
-            if (block == null)
-                throw new NullPointerException();
-            if ((a = array).length >= (hi = fence) &&
-                (i = index) >= 0 && i < hi) {
-                index = hi;
-                do {
-                    @SuppressWarnings("unchecked") E e = (E) a[i];
-                    block.accept(e);
-                } while (++i < hi);
-            }
-        }
-
-        public boolean tryAdvance(Consumer<? super E> block) {
-            if (index >= 0 && index < fence) {
-                @SuppressWarnings("unchecked") E e = (E) array[index++];
-                block.accept(e);
-                return true;
-            }
-            return false;
-        }
-
-        public long estimateSize() { return (long)(fence - index); }
-
-        @Override
-        public int characteristics() {
-            return Spliterator.CONCURRENT | Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
-        }
-    }
-
-
     // Support for resetting lock while deserializing
     private void resetLock() {
         UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock());
--- a/src/share/classes/java/util/concurrent/CopyOnWriteArraySet.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/concurrent/CopyOnWriteArraySet.java	Wed Feb 20 12:03:58 2013 +0100
@@ -35,6 +35,7 @@
 
 package java.util.concurrent;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.Set;
 import java.util.AbstractSet;
 import java.util.Iterator;
@@ -388,29 +389,17 @@
         return k == len;
     }
 
+    Spliterator<E> spliterator() {
+        return Collections.arraySnapshotSpliterator
+            (al.getArray(), Spliterator.IMMUTABLE | 
+             Spliterator.DISTINCT | Spliterator.ORDERED);
+    }
+
     public Stream<E> stream() {
-        Object[] a = al.getArray();
-        int n = a.length;
-        return Streams.stream
-            (new COWSpliterator<>(a, 0, n));
+        return Streams.stream(spliterator());
     }
     public Stream<E> parallelStream() {
-        Object[] a = al.getArray();
-        int n = a.length;
-        return Streams.parallelStream
-            (new COWSpliterator<>(a, 0, n));
-    }
-
-    static final class COWSpliterator<E> extends CopyOnWriteArrayList.COWSpliterator<E> {
-        /** Create new spliterator covering the given array and range */
-        COWSpliterator(Object[] array, int origin, int fence) {
-            super(array, origin, fence);
-        }
-
-        @Override
-        public int characteristics() {
-            return super.characteristics() | Spliterator.DISTINCT;
-        }
+        return Streams.parallelStream(spliterator());
     }
 
     /**
--- a/src/share/classes/java/util/concurrent/LinkedBlockingDeque.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/concurrent/LinkedBlockingDeque.java	Wed Feb 20 12:03:58 2013 +0100
@@ -37,16 +37,21 @@
 
 import java.util.AbstractQueue;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
 import java.util.concurrent.locks.Condition;
 import java.util.concurrent.locks.ReentrantLock;
+import java.util.Spliterator;
+import java.util.stream.Stream;
+import java.util.stream.Streams;
+import java.util.function.Consumer;
 
 /**
  * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
  * linked nodes.
  *
- * <p> The optional capacity bound constructor argument serves as a
+ * <p>The optional capacity bound constructor argument serves as a
  * way to prevent excessive expansion. The capacity, if unspecified,
  * is equal to {@link Integer#MAX_VALUE}.  Linked nodes are
  * dynamically created upon each insertion unless this would bring the
@@ -1143,6 +1148,21 @@
     private class Itr extends AbstractItr {
         Node<E> firstNode() { return first; }
         Node<E> nextNode(Node<E> n) { return n.next; }
+        // minimal, unsplittable Spliterator implementation
+        public boolean tryAdvance(Consumer<? super E> action) {
+            if (hasNext()) {
+                action.accept(next());
+                return true;
+            }
+            return false;
+        }
+        public void forEach(Consumer<? super E> action) {
+            while (hasNext())
+                action.accept(next());
+        }
+        public int characteristics() {
+            return Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.CONCURRENT;
+        }
     }
 
     /** Descending iterator */
@@ -1151,6 +1171,126 @@
         Node<E> nextNode(Node<E> n) { return n.prev; }
     }
 
+    static final class LBDSpliterator<E> implements Spliterator<E> {
+        // Similar idea to ConcurrentLinkedQueue spliterator
+        static final int MAX_BATCH = 1 << 11;  // saturate batch size
+        final LinkedBlockingDeque<E> queue;
+        Node<E> current;    // current node; null until initialized
+        int batch;          // batch size for splits
+        boolean exhausted;  // true when no more nodes
+        long est;           // size estimate
+        LBDSpliterator(LinkedBlockingDeque<E> queue) { 
+            this.queue = queue;
+            this.est = queue.size();
+        }
+
+        public long estimateSize() { return est; }
+
+        public Spliterator<E> trySplit() {
+            int n;
+            final LinkedBlockingDeque<E> q = this.queue;
+            final ReentrantLock lock = q.lock;
+            if (!exhausted && (n = batch + 1) > 0 && n <= MAX_BATCH) {
+                Object[] a = new Object[batch = n];
+                int i = 0;
+                Node<E> p = current;
+                lock.lock();
+                try {
+                    if (p != null || (p = q.first) != null) {
+                        do {
+                            if ((a[i] = p.item) != null)
+                                ++i;
+                        } while ((p = p.next) != null && i < n);
+                    }
+                } finally {
+                    lock.unlock();
+                }
+                if ((current = p) == null) {
+                    est = 0L;
+                    exhausted = true;
+                }
+                else if ((est -= i) <= 0L)
+                    est = 1L;
+                return Collections.arraySnapshotSpliterator
+                    (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |
+                     Spliterator.CONCURRENT);
+            }
+            return null;
+        }
+
+        public void forEach(Consumer<? super E> action) {
+            if (action == null) throw new NullPointerException();
+            final LinkedBlockingDeque<E> q = this.queue;
+            final ReentrantLock lock = q.lock;
+            if (!exhausted) {
+                exhausted = true;
+                Node<E> p = current;
+                do {
+                    E e = null;
+                    lock.lock();
+                    try {
+                        if (p == null)
+                            p = q.first;
+                        while (p != null) {
+                            e = p.item;
+                            p = p.next;
+                            if (e != null)
+                                break;
+                        }
+                    } finally {
+                        lock.unlock();
+                    }
+                    if (e != null)
+                        action.accept(e);
+                } while (p != null);
+            }
+        }
+
+        public boolean tryAdvance(Consumer<? super E> action) {
+            if (action == null) throw new NullPointerException();
+            final LinkedBlockingDeque<E> q = this.queue;
+            final ReentrantLock lock = q.lock;
+            if (!exhausted) {
+                E e = null;
+                lock.lock();
+                try {
+                    if (current == null)
+                        current = q.first;
+                    while (current != null) {
+                        e = current.item;
+                        current = current.next;
+                        if (e != null)
+                            break;
+                    }
+                } finally {
+                    lock.unlock();
+                }
+                if (e != null) {
+                    action.accept(e);
+                    return true;
+                }
+                exhausted = true;
+            }
+            return false;
+        }
+
+        public int characteristics() {
+            return Spliterator.ORDERED | Spliterator.NONNULL |
+                Spliterator.CONCURRENT;
+        }
+    }
+
+    Spliterator<E> spliterator() {
+        return new LBDSpliterator<E>(this);
+    }
+    public Stream<E> stream() {
+        return Streams.stream(spliterator());
+    }
+
+    public Stream<E> parallelStream() {
+        return Streams.parallelStream(spliterator());
+    }
+
     /**
      * Saves this deque to a stream (that is, serializes it).
      *
--- a/src/share/classes/java/util/concurrent/LinkedBlockingQueue.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/concurrent/LinkedBlockingQueue.java	Wed Feb 20 12:03:58 2013 +0100
@@ -40,8 +40,13 @@
 import java.util.concurrent.locks.ReentrantLock;
 import java.util.AbstractQueue;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
+import java.util.Spliterator;
+import java.util.stream.Stream;
+import java.util.stream.Streams;
+import java.util.function.Consumer;
 
 /**
  * An optionally-bounded {@linkplain BlockingQueue blocking queue} based on
@@ -56,7 +61,7 @@
  * Linked queues typically have higher throughput than array-based queues but
  * less predictable performance in most concurrent applications.
  *
- * <p> The optional capacity bound constructor argument serves as a
+ * <p>The optional capacity bound constructor argument serves as a
  * way to prevent excessive queue expansion. The capacity, if unspecified,
  * is equal to {@link Integer#MAX_VALUE}.  Linked nodes are
  * dynamically created upon each insertion unless this would bring the
@@ -216,7 +221,7 @@
     }
 
     /**
-     * Lock to prevent both puts and takes.
+     * Locks to prevent both puts and takes.
      */
     void fullyLock() {
         putLock.lock();
@@ -224,7 +229,7 @@
     }
 
     /**
-     * Unlock to allow both puts and takes.
+     * Unlocks to allow both puts and takes.
      */
     void fullyUnlock() {
         takeLock.unlock();
@@ -362,7 +367,7 @@
      * necessary up to the specified wait time for space to become available.
      *
      * @return {@code true} if successful, or {@code false} if
-     *         the specified waiting time elapses before space is available.
+     *         the specified waiting time elapses before space is available
      * @throws InterruptedException {@inheritDoc}
      * @throws NullPointerException {@inheritDoc}
      */
@@ -782,6 +787,7 @@
          * item to hand out so that if hasNext() reports true, we will
          * still have it to return even if lost race with a take etc.
          */
+
         private Node<E> current;
         private Node<E> lastRet;
         private E currentElement;
@@ -855,6 +861,124 @@
         }
     }
 
+    static final class LBQSpliterator<E> implements Spliterator<E> {
+        // Similar idea to ConcurrentLinkedQueue spliterator
+        static final int MAX_BATCH = 1 << 11;  // saturate batch size
+        final LinkedBlockingQueue<E> queue;
+        Node<E> current;    // current node; null until initialized
+        int batch;          // batch size for splits
+        boolean exhausted;  // true when no more nodes
+        long est;           // size estimate
+        LBQSpliterator(LinkedBlockingQueue<E> queue) {
+            this.queue = queue;
+            this.est = queue.size();
+        }
+
+        public long estimateSize() { return est; }
+
+        public Spliterator<E> trySplit() {
+            int n;
+            final LinkedBlockingQueue<E> q = this.queue;
+            if (!exhausted && (n = batch + 1) > 0 && n <= MAX_BATCH) {
+                Object[] a = new Object[batch = n];
+                int i = 0;
+                Node<E> p = current;
+                q.fullyLock();
+                try {
+                    if (p != null || (p = q.head.next) != null) {
+                        do {
+                            if ((a[i] = p.item) != null)
+                                ++i;
+                        } while ((p = p.next) != null && i < n);
+                    }
+                } finally {
+                    q.fullyUnlock();
+                }
+                if ((current = p) == null) {
+                    est = 0L;
+                    exhausted = true;
+                }
+                else if ((est -= i) <= 0L)
+                    est = 1L;
+                return Collections.arraySnapshotSpliterator
+                    (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |
+                     Spliterator.CONCURRENT);
+            }
+            return null;
+        }
+
+        public void forEach(Consumer<? super E> action) {
+            if (action == null) throw new NullPointerException();
+            final LinkedBlockingQueue<E> q = this.queue;
+            if (!exhausted) {
+                exhausted = true;
+                Node<E> p = current;
+                do {
+                    E e = null;
+                    q.fullyLock();
+                    try {
+                        if (p == null)
+                            p = q.head.next;
+                        while (p != null) {
+                            e = p.item;
+                            p = p.next;
+                            if (e != null)
+                                break;
+                        }
+                    } finally {
+                        q.fullyUnlock();
+                    }
+                    if (e != null)
+                        action.accept(e);
+                } while (p != null);
+            }
+        }
+
+        public boolean tryAdvance(Consumer<? super E> action) {
+            if (action == null) throw new NullPointerException();
+            final LinkedBlockingQueue<E> q = this.queue;
+            if (!exhausted) {
+                E e = null;
+                q.fullyLock();
+                try {
+                    if (current == null)
+                        current = q.head.next;
+                    while (current != null) {
+                        e = current.item;
+                        current = current.next;
+                        if (e != null)
+                            break;
+                    }
+                } finally {
+                    q.fullyUnlock();
+                }
+                if (e != null) {
+                    action.accept(e);
+                    return true;
+                }
+                exhausted = true;
+            }
+            return false;
+        }
+
+        public int characteristics() {
+            return Spliterator.ORDERED | Spliterator.NONNULL |
+                Spliterator.CONCURRENT;
+        }
+    }
+
+    Spliterator<E> spliterator() {
+        return new LBQSpliterator<E>(this);
+    }
+
+    public Stream<E> stream() {
+        return Streams.stream(spliterator());
+    }
+
+    public Stream<E> parallelStream() {
+        return Streams.parallelStream(spliterator());
+    }
+
     /**
      * Saves this queue to a stream (that is, serializes it).
      *
--- a/src/share/classes/java/util/concurrent/LinkedTransferQueue.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/concurrent/LinkedTransferQueue.java	Wed Feb 20 12:03:58 2013 +0100
@@ -37,11 +37,15 @@
 
 import java.util.AbstractQueue;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
 import java.util.Queue;
-import java.util.concurrent.TimeUnit;
 import java.util.concurrent.locks.LockSupport;
+import java.util.Spliterator;
+import java.util.stream.Stream;
+import java.util.stream.Streams;
+import java.util.function.Consumer;
 
 /**
  * An unbounded {@link TransferQueue} based on linked nodes.
@@ -777,6 +781,24 @@
     }
 
     /**
+     * Version of firstOfMode used by Spliterator
+     */
+    final Node firstDataNode() {
+        for (Node p = head; p != null;) {
+            Object item = p.item;
+            if (p.isData) {
+                if (item != null && item != p)
+                    return p;
+            }
+            else if (item == null)
+                break;
+            if (p == (p = p.next))
+                p = head;
+        }
+        return null;
+    }
+
+    /**
      * Returns the item in the first unmatched node with isData; or
      * null if none.  Used by peek.
      */
@@ -909,6 +931,107 @@
                 unsplice(lastPred, lastRet);
         }
     }
+    
+    // Very similar to ConcurrentLinkedQueue spliterator
+    static final class LTQSpliterator<E> implements Spliterator<E> {
+        static final int MAX_BATCH = 1 << 10;  // saturate batch size
+        final LinkedTransferQueue<E> queue;
+        Node current;    // current node; null until initialized
+        int batch;          // batch size for splits
+        boolean exhausted;  // true when no more nodes
+        LTQSpliterator(LinkedTransferQueue<E> queue) { 
+            this.queue = queue;
+        }
+
+        /*
+         * Split into arrays of arithmetically increasing batch sizes,
+         * giving up at MAX_BATCH.  Treat the result as a
+         * CopyOnWriteArrayList array snapshot.  This will only
+         * improve parallel performance if per-element forEach actions
+         * are more costly than transfering them into an array. If
+         * not, we limit slowdowns by eventually returning null split.
+         */
+        public Spliterator<E> trySplit() {
+            Node p; int n;
+            final LinkedTransferQueue<E> q = this.queue;
+            if (!exhausted && (n = batch + 1) > 0 && n <= MAX_BATCH &&
+                ((p = current) != null || (p = q.firstDataNode()) != null)) {
+                Object[] a = new Object[batch = n];
+                int i = 0;
+                do {
+                    if ((a[i] = p.item) != null)
+                        ++i;
+                    if (p == (p = p.next)) 
+                        p = q.firstDataNode();
+                } while (p != null && i < n);
+                if ((current = p) == null)
+                    exhausted = true;
+                return Collections.arraySnapshotSpliterator
+                    (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |
+                     Spliterator.CONCURRENT);
+            }
+            return null;
+        }
+
+        @SuppressWarnings("unchecked")
+        public void forEach(Consumer<? super E> action) {
+            Node p;
+            if (action == null) throw new NullPointerException();
+            final LinkedTransferQueue<E> q = this.queue;
+            if (!exhausted &&
+                ((p = current) != null || (p = q.firstDataNode()) != null)) {
+                exhausted = true;
+                do {
+                    Object e = p.item;
+                    if (p == (p = p.next)) 
+                        p = q.firstDataNode();
+                    if (e != null)
+                        action.accept((E)e);
+                } while (p != null);
+            }
+        }
+
+        @SuppressWarnings("unchecked")
+        public boolean tryAdvance(Consumer<? super E> action) {
+            Node p;
+            if (action == null) throw new NullPointerException();
+            final LinkedTransferQueue<E> q = this.queue;
+            if (!exhausted &&
+                ((p = current) != null || (p = q.firstDataNode()) != null)) {
+                Object e;
+                do {
+                    e = p.item;
+                    if (p == (p = p.next)) 
+                        p = q.firstDataNode();
+                } while (e == null && p != null);
+                if ((current = p) == null)
+                    exhausted = true;
+                if (e != null) {
+                    action.accept((E)e);
+                    return true;
+                }
+            }
+            return false;
+        }
+
+        public int characteristics() {
+            return Spliterator.ORDERED | Spliterator.NONNULL |
+                Spliterator.CONCURRENT;
+        }
+    }
+
+
+    Spliterator<E> spliterator() {
+        return new LTQSpliterator<E>(this);
+    }
+
+    public Stream<E> stream() {
+        return Streams.stream(spliterator());
+    }
+
+    public Stream<E> parallelStream() {
+        return Streams.parallelStream(spliterator());
+    }
 
     /* -------------- Removal methods -------------- */
 
--- a/src/share/classes/java/util/concurrent/PriorityBlockingQueue.java	Wed Feb 20 10:31:03 2013 +0100
+++ b/src/share/classes/java/util/concurrent/PriorityBlockingQueue.java	Wed Feb 20 12:03:58 2013 +0100
@@ -40,6 +40,7 @@
 import java.util.AbstractQueue;
 import java.util.Arrays;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.Comparator;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
@@ -49,7 +50,6 @@
 import java.util.Spliterator;
 import java.util.stream.Stream;
 import java.util.stream.Streams;
-import java.util.function.Consumer;
 
 /**
  * An unbounded {@linkplain BlockingQueue blocking queue} that uses
@@ -947,12 +947,9 @@
         }
     }
 
-    // wrapping constructor in method avoids transient javac problems
-    final PBQSpliterator<E> spliterator() {
-        Object[] a = toArray();
-        return new PBQSpliterator<>(a, 0, a.length);
+    Spliterator<E> spliterator() {
+        return Collections.arraySnapshotSpliterator(this, 0);
     }
-
     public Stream<E> stream() {
         return Streams.stream(spliterator());
     }
@@ -960,54 +957,6 @@
         return Streams.parallelStream(spliterator());
     }
 
-    /** Index-based split-by-two Spliterator */
-    static final class PBQSpliterator<E> implements Spliterator<E> {
-        private final Object[] array;
-        private int index;        // current index, modified on advance/split
-        private final int fence;  // one past last index
-
-        /** Create new spliterator covering the given array and range */
-        PBQSpliterator(Object[] array, int origin, int fence) {
-            this.array = array; this.index = origin; this.fence = fence;
-        }
-
-        public PBQSpliterator<E> trySplit() {
-            int lo = index, mid = (lo + fence) >>> 1;
-            return (lo >= mid) ? null :
-                new PBQSpliterator<E>(array, lo, index = mid);
-        }
-
-        public void forEach(Consumer<? super E> block) {
-            Object[] a; int i, hi; // hoist accesses and checks from loop
-            if (block == null)
-                throw new NullPointerException();
-            if ((a = array).length >= (hi = fence) &&
-                (i = index) >= 0 && i < hi) {
-                index = hi;
-                do {
-                    @SuppressWarnings("unchecked") E e = (E) a[i];
-                    block.accept(e);
-                } while (++i < hi);
-            }
-        }
-
-        public boolean tryAdvance(Consumer<? super E> block) {
-            if (index >= 0 && index < fence) {
-                @SuppressWarnings("unchecked") E e = (E) array[index++];
-                block.accept(e);
-                return true;
-            }
-            return false;
-        }
-
-        public long estimateSize() { return (long)(fence - index); }
-
-        public int characteristics() {
-            return Spliterator.CONCURRENT | Spliterator.NONNULL |
-                   Spliterator.SIZED | Spliterator.SUBSIZED;
-        }
-    }
-
     // Unsafe mechanics
     private static final sun.misc.Unsafe UNSAFE;
     private static final long allocationSpinLockOffset;