changeset 8344:98a7bb7baa76

8011426: java.util collection Spliterator implementations Summary: Spliterator implementations for collection classes in java.util. Reviewed-by: mduigou, briangoetz Contributed-by: Doug Lea <dl@cs.oswego.edu>, Paul Sandoz <paul.sandoz@oracle.com>
author psandoz
date Wed, 17 Apr 2013 11:34:31 +0200
parents 2a78d8f1fec1
children d62a39940550 62fb9e2b5da1
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/LinkedHashSet.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 test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java
diffstat 14 files changed, 2236 insertions(+), 159 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/ArrayDeque.java	Wed Apr 17 14:39:04 2013 -0400
+++ b/src/share/classes/java/util/ArrayDeque.java	Wed Apr 17 11:34:31 2013 +0200
@@ -33,7 +33,9 @@
  */
 
 package java.util;
-import java.io.*;
+
+import java.io.Serializable;
+import java.util.function.Consumer;
 
 /**
  * Resizable-array implementation of the {@link Deque} interface.  Array
@@ -44,16 +46,16 @@
  * {@link Stack} when used as a stack, and faster than {@link LinkedList}
  * when used as a queue.
  *
- * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
+ * <p>Most {@code ArrayDeque} operations run in amortized constant time.
  * Exceptions include {@link #remove(Object) remove}, {@link
  * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
  * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
  * iterator.remove()}, and the bulk operations, all of which run in linear
  * time.
  *
- * <p>The iterators returned by this class's <tt>iterator</tt> method are
+ * <p>The iterators returned by this class's {@code iterator} method are
  * <i>fail-fast</i>: If the deque is modified at any time after the iterator
- * is created, in any way except through the iterator's own <tt>remove</tt>
+ * is created, in any way except through the iterator's own {@code remove}
  * method, the iterator will generally throw a {@link
  * ConcurrentModificationException}.  Thus, in the face of concurrent
  * modification, the iterator fails quickly and cleanly, rather than risking
@@ -63,7 +65,7 @@
  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  * as it is, generally speaking, impossible to make any hard guarantees in the
  * presence of unsynchronized concurrent modification.  Fail-fast iterators
- * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
+ * throw {@code ConcurrentModificationException} on a best-effort basis.
  * Therefore, it would be wrong to write a program that depended on this
  * exception for its correctness: <i>the fail-fast behavior of iterators
  * should be used only to detect bugs.</i>
@@ -93,20 +95,20 @@
      * other.  We also guarantee that all array cells not holding
      * deque elements are always null.
      */
-    private transient E[] elements;
+    transient Object[] elements; // non-private to simplify nested class access
 
     /**
      * The index of the element at the head of the deque (which is the
      * element that would be removed by remove() or pop()); or an
      * arbitrary number equal to tail if the deque is empty.
      */
-    private transient int head;
+    transient int head;
 
     /**
      * The index at which the next element would be added to the tail
      * of the deque (via addLast(E), add(E), or push(E)).
      */
-    private transient int tail;
+    transient int tail;
 
     /**
      * The minimum capacity that we'll use for a newly created deque.
@@ -117,11 +119,10 @@
     // ******  Array allocation and resizing utilities ******
 
     /**
-     * Allocate empty array to hold the given number of elements.
+     * Allocates empty array to hold the given number of elements.
      *
      * @param numElements  the number of elements to hold
      */
-    @SuppressWarnings("unchecked")
     private void allocateElements(int numElements) {
         int initialCapacity = MIN_INITIAL_CAPACITY;
         // Find the best power of two to hold elements.
@@ -138,11 +139,11 @@
             if (initialCapacity < 0)   // Too many elements, must back off
                 initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
         }
-        elements = (E[]) new Object[initialCapacity];
+        elements = new Object[initialCapacity];
     }
 
     /**
-     * Double the capacity of this deque.  Call only when full, i.e.,
+     * Doubles the capacity of this deque.  Call only when full, i.e.,
      * when head and tail have wrapped around to become equal.
      */
     private void doubleCapacity() {
@@ -153,8 +154,7 @@
         int newCapacity = n << 1;
         if (newCapacity < 0)
             throw new IllegalStateException("Sorry, deque too big");
-        @SuppressWarnings("unchecked")
-        E[] a = (E[]) new Object[newCapacity];
+        Object[] a = new Object[newCapacity];
         System.arraycopy(elements, p, a, 0, r);
         System.arraycopy(elements, 0, a, r, p);
         elements = a;
@@ -184,9 +184,8 @@
      * Constructs an empty array deque with an initial capacity
      * sufficient to hold 16 elements.
      */
-    @SuppressWarnings("unchecked")
     public ArrayDeque() {
-        elements = (E[]) new Object[16];
+        elements = new Object[16];
     }
 
     /**
@@ -252,7 +251,7 @@
      * Inserts the specified element at the front of this deque.
      *
      * @param e the element to add
-     * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
+     * @return {@code true} (as specified by {@link Deque#offerFirst})
      * @throws NullPointerException if the specified element is null
      */
     public boolean offerFirst(E e) {
@@ -264,7 +263,7 @@
      * Inserts the specified element at the end of this deque.
      *
      * @param e the element to add
-     * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
+     * @return {@code true} (as specified by {@link Deque#offerLast})
      * @throws NullPointerException if the specified element is null
      */
     public boolean offerLast(E e) {
@@ -294,7 +293,9 @@
 
     public E pollFirst() {
         int h = head;
-        E result = elements[h]; // Element is null if deque empty
+        @SuppressWarnings("unchecked")
+        E result = (E) elements[h];
+        // Element is null if deque empty
         if (result == null)
             return null;
         elements[h] = null;     // Must null out slot
@@ -304,7 +305,8 @@
 
     public E pollLast() {
         int t = (tail - 1) & (elements.length - 1);
-        E result = elements[t];
+        @SuppressWarnings("unchecked")
+        E result = (E) elements[t];
         if (result == null)
             return null;
         elements[t] = null;
@@ -316,48 +318,53 @@
      * @throws NoSuchElementException {@inheritDoc}
      */
     public E getFirst() {
-        E x = elements[head];
-        if (x == null)
+        @SuppressWarnings("unchecked")
+        E result = (E) elements[head];
+        if (result == null)
             throw new NoSuchElementException();
-        return x;
+        return result;
     }
 
     /**
      * @throws NoSuchElementException {@inheritDoc}
      */
     public E getLast() {
-        E x = elements[(tail - 1) & (elements.length - 1)];
-        if (x == null)
+        @SuppressWarnings("unchecked")
+        E result = (E) elements[(tail - 1) & (elements.length - 1)];
+        if (result == null)
             throw new NoSuchElementException();
-        return x;
+        return result;
     }
 
+    @SuppressWarnings("unchecked")
     public E peekFirst() {
-        return elements[head]; // elements[head] is null if deque empty
+        // elements[head] is null if deque empty
+        return (E) elements[head];
     }
 
+    @SuppressWarnings("unchecked")
     public E peekLast() {
-        return elements[(tail - 1) & (elements.length - 1)];
+        return (E) elements[(tail - 1) & (elements.length - 1)];
     }
 
     /**
      * Removes the first occurrence of the specified element in this
      * deque (when traversing the deque from head to tail).
      * If the deque does not contain the element, it is unchanged.
-     * More formally, removes the first element <tt>e</tt> such that
-     * <tt>o.equals(e)</tt> (if such an element exists).
-     * Returns <tt>true</tt> if this deque contained the specified element
+     * More formally, removes the first element {@code e} such that
+     * {@code o.equals(e)} (if such an element exists).
+     * Returns {@code true} if this deque contained the specified element
      * (or equivalently, if this deque changed as a result of the call).
      *
      * @param o element to be removed from this deque, if present
-     * @return <tt>true</tt> if the deque contained the specified element
+     * @return {@code true} if the deque contained the specified element
      */
     public boolean removeFirstOccurrence(Object o) {
         if (o == null)
             return false;
         int mask = elements.length - 1;
         int i = head;
-        E x;
+        Object x;
         while ( (x = elements[i]) != null) {
             if (o.equals(x)) {
                 delete(i);
@@ -372,20 +379,20 @@
      * Removes the last occurrence of the specified element in this
      * deque (when traversing the deque from head to tail).
      * If the deque does not contain the element, it is unchanged.
-     * More formally, removes the last element <tt>e</tt> such that
-     * <tt>o.equals(e)</tt> (if such an element exists).
-     * Returns <tt>true</tt> if this deque contained the specified element
+     * More formally, removes the last element {@code e} such that
+     * {@code o.equals(e)} (if such an element exists).
+     * Returns {@code true} if this deque contained the specified element
      * (or equivalently, if this deque changed as a result of the call).
      *
      * @param o element to be removed from this deque, if present
-     * @return <tt>true</tt> if the deque contained the specified element
+     * @return {@code true} if the deque contained the specified element
      */
     public boolean removeLastOccurrence(Object o) {
         if (o == null)
             return false;
         int mask = elements.length - 1;
         int i = (tail - 1) & mask;
-        E x;
+        Object x;
         while ( (x = elements[i]) != null) {
             if (o.equals(x)) {
                 delete(i);
@@ -404,7 +411,7 @@
      * <p>This method is equivalent to {@link #addLast}.
      *
      * @param e the element to add
-     * @return <tt>true</tt> (as specified by {@link Collection#add})
+     * @return {@code true} (as specified by {@link Collection#add})
      * @throws NullPointerException if the specified element is null
      */
     public boolean add(E e) {
@@ -418,7 +425,7 @@
      * <p>This method is equivalent to {@link #offerLast}.
      *
      * @param e the element to add
-     * @return <tt>true</tt> (as specified by {@link Queue#offer})
+     * @return {@code true} (as specified by {@link Queue#offer})
      * @throws NullPointerException if the specified element is null
      */
     public boolean offer(E e) {
@@ -443,12 +450,12 @@
     /**
      * Retrieves and removes the head of the queue represented by this deque
      * (in other words, the first element of this deque), or returns
-     * <tt>null</tt> if this deque is empty.
+     * {@code null} if this deque is empty.
      *
      * <p>This method is equivalent to {@link #pollFirst}.
      *
      * @return the head of the queue represented by this deque, or
-     *         <tt>null</tt> if this deque is empty
+     *         {@code null} if this deque is empty
      */
     public E poll() {
         return pollFirst();
@@ -470,12 +477,12 @@
 
     /**
      * Retrieves, but does not remove, the head of the queue represented by
-     * this deque, or returns <tt>null</tt> if this deque is empty.
+     * this deque, or returns {@code null} if this deque is empty.
      *
      * <p>This method is equivalent to {@link #peekFirst}.
      *
      * @return the head of the queue represented by this deque, or
-     *         <tt>null</tt> if this deque is empty
+     *         {@code null} if this deque is empty
      */
     public E peek() {
         return peekFirst();
@@ -530,7 +537,7 @@
      */
     private boolean delete(int i) {
         checkInvariants();
-        final E[] elements = this.elements;
+        final Object[] elements = this.elements;
         final int mask = elements.length - 1;
         final int h = head;
         final int t = tail;
@@ -579,9 +586,9 @@
     }
 
     /**
-     * Returns <tt>true</tt> if this deque contains no elements.
+     * Returns {@code true} if this deque contains no elements.
      *
-     * @return <tt>true</tt> if this deque contains no elements
+     * @return {@code true} if this deque contains no elements
      */
     public boolean isEmpty() {
         return head == tail;
@@ -628,7 +635,8 @@
         public E next() {
             if (cursor == fence)
                 throw new NoSuchElementException();
-            E result = elements[cursor];
+            @SuppressWarnings("unchecked")
+            E result = (E) elements[cursor];
             // This check doesn't catch all possible comodifications,
             // but does catch the ones that corrupt traversal
             if (tail != fence || result == null)
@@ -647,6 +655,20 @@
             }
             lastRet = -1;
         }
+
+        public void forEachRemaining(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+            Object[] a = elements;
+            int m = a.length - 1, f = fence, i = cursor;
+            cursor = f;
+            while (i != f) {
+                @SuppressWarnings("unchecked") E e = (E)a[i];
+                i = (i + 1) & m;
+                if (e == null)
+                    throw new ConcurrentModificationException();
+                action.accept(e);
+            }
+        }
     }
 
     private class DescendingIterator implements Iterator<E> {
@@ -667,7 +689,8 @@
             if (cursor == fence)
                 throw new NoSuchElementException();
             cursor = (cursor - 1) & (elements.length - 1);
-            E result = elements[cursor];
+            @SuppressWarnings("unchecked")
+            E result = (E) elements[cursor];
             if (head != fence || result == null)
                 throw new ConcurrentModificationException();
             lastRet = cursor;
@@ -686,19 +709,19 @@
     }
 
     /**
-     * Returns <tt>true</tt> if this deque contains the specified element.
-     * More formally, returns <tt>true</tt> if and only if this deque contains
-     * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
+     * Returns {@code true} if this deque contains the specified element.
+     * More formally, returns {@code true} if and only if this deque contains
+     * at least one element {@code e} such that {@code o.equals(e)}.
      *
      * @param o object to be checked for containment in this deque
-     * @return <tt>true</tt> if this deque contains the specified element
+     * @return {@code true} if this deque contains the specified element
      */
     public boolean contains(Object o) {
         if (o == null)
             return false;
         int mask = elements.length - 1;
         int i = head;
-        E x;
+        Object x;
         while ( (x = elements[i]) != null) {
             if (o.equals(x))
                 return true;
@@ -710,15 +733,15 @@
     /**
      * Removes a single instance of the specified element from this deque.
      * If the deque does not contain the element, it is unchanged.
-     * More formally, removes the first element <tt>e</tt> such that
-     * <tt>o.equals(e)</tt> (if such an element exists).
-     * Returns <tt>true</tt> if this deque contained the specified element
+     * More formally, removes the first element {@code e} such that
+     * {@code o.equals(e)} (if such an element exists).
+     * 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 <tt>true</tt> if this deque contained the specified element
+     * @return {@code true} if this deque contained the specified element
      */
     public boolean remove(Object o) {
         return removeFirstOccurrence(o);
@@ -770,22 +793,21 @@
      * <p>If this deque fits in the specified array with room to spare
      * (i.e., the array has more elements than this deque), the element in
      * the array immediately following the end of the deque is set to
-     * <tt>null</tt>.
+     * {@code null}.
      *
      * <p>Like the {@link #toArray()} method, this method acts as bridge between
      * array-based and collection-based APIs.  Further, this method allows
      * precise control over the runtime type of the output array, and may,
      * under certain circumstances, be used to save allocation costs.
      *
-     * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
+     * <p>Suppose {@code x} is a deque known to contain only strings.
      * The following code can be used to dump the deque into a newly
-     * allocated array of <tt>String</tt>:
+     * 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 <tt>toArray(new Object[0])</tt> is identical in function to
-     * <tt>toArray()</tt>.
+     * Note that {@code toArray(new Object[0])} is identical in function to
+     * {@code toArray()}.
      *
      * @param a the array into which the elements of the deque are to
      *          be stored, if it is big enough; otherwise, a new array of the
@@ -818,28 +840,25 @@
     public ArrayDeque<E> clone() {
         try {
             @SuppressWarnings("unchecked")
-                ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
+            ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
             result.elements = Arrays.copyOf(elements, elements.length);
             return result;
-
         } catch (CloneNotSupportedException e) {
             throw new AssertionError();
         }
     }
 
-    /**
-     * Appease the serialization gods.
-     */
     private static final long serialVersionUID = 2340985798034038923L;
 
     /**
-     * Serialize this deque.
+     * Saves this deque to a stream (that is, serializes it).
      *
-     * @serialData The current size (<tt>int</tt>) of the deque,
+     * @serialData The current size ({@code int}) of the deque,
      * followed by all of its elements (each an object reference) in
      * first-to-last order.
      */
-    private void writeObject(ObjectOutputStream s) throws IOException {
+    private void writeObject(java.io.ObjectOutputStream s)
+            throws java.io.IOException {
         s.defaultWriteObject();
 
         // Write out size
@@ -852,11 +871,10 @@
     }
 
     /**
-     * Deserialize this deque.
+     * Reconstitutes this deque from a stream (that is, deserializes it).
      */
-    @SuppressWarnings("unchecked")
-    private void readObject(ObjectInputStream s)
-            throws IOException, ClassNotFoundException {
+    private void readObject(java.io.ObjectInputStream s)
+            throws java.io.IOException, ClassNotFoundException {
         s.defaultReadObject();
 
         // Read in size and allocate array
@@ -867,6 +885,88 @@
 
         // Read in all elements in the proper order.
         for (int i = 0; i < size; i++)
-            elements[i] = (E)s.readObject();
+            elements[i] = s.readObject();
     }
+
+    public Spliterator<E> spliterator() {
+        return new DeqSpliterator<E>(this, -1, -1);
+    }
+
+    static final class DeqSpliterator<E> implements Spliterator<E> {
+        private final ArrayDeque<E> deq;
+        private int fence;  // -1 until first use
+        private int index;  // current index, modified on traverse/split
+
+        /** 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 t = getFence(), h = index, n = deq.elements.length;
+            if (h != t && ((h + 1) & (n - 1)) != t) {
+                if (h > t)
+                    t += n;
+                int m = ((h + t) >>> 1) & (n - 1);
+                return new DeqSpliterator<>(deq, h, index = m);
+            }
+            return null;
+        }
+
+        public void forEachRemaining(Consumer<? super E> consumer) {
+            if (consumer == null)
+                throw new NullPointerException();
+            Object[] a = deq.elements;
+            int m = a.length - 1, f = getFence(), i = index;
+            index = f;
+            while (i != f) {
+                @SuppressWarnings("unchecked") E e = (E)a[i];
+                i = (i + 1) & m;
+                if (e == null)
+                    throw new ConcurrentModificationException();
+                consumer.accept(e);
+            }
+        }
+
+        public boolean tryAdvance(Consumer<? super E> consumer) {
+            if (consumer == null)
+                throw new NullPointerException();
+            Object[] a = deq.elements;
+            int m = a.length - 1, f = getFence(), i = index;
+            if (i != fence) {
+                @SuppressWarnings("unchecked") E e = (E)a[i];
+                index = (i + 1) & m;
+                if (e == null)
+                    throw new ConcurrentModificationException();
+                consumer.accept(e);
+                return true;
+            }
+            return false;
+        }
+
+        public long estimateSize() {
+            int n = getFence() - index;
+            if (n < 0)
+                n += deq.elements.length;
+            return (long) n;
+        }
+
+        @Override
+        public int characteristics() {
+            return Spliterator.ORDERED | Spliterator.SIZED |
+                Spliterator.NONNULL | Spliterator.SUBSIZED;
+        }
+    }
+
 }
--- a/src/share/classes/java/util/ArrayList.java	Wed Apr 17 14:39:04 2013 -0400
+++ b/src/share/classes/java/util/ArrayList.java	Wed Apr 17 11:34:31 2013 +0200
@@ -29,6 +29,10 @@
 import java.util.function.Predicate;
 import java.util.function.UnaryOperator;
 
+import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.function.UnaryOperator;
+
 /**
  * Resizable-array implementation of the <tt>List</tt> interface.  Implements
  * all optional list operations, and permits all elements, including
@@ -124,7 +128,7 @@
      * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
      * DEFAULT_CAPACITY when the first element is added.
      */
-    private transient Object[] elementData;
+    transient Object[] elementData; // non-private to simplify nested class access
 
     /**
      * The size of the ArrayList (the number of elements it contains).
@@ -857,6 +861,27 @@
             }
         }
 
+        @Override
+        @SuppressWarnings("unchecked")
+        public void forEachRemaining(Consumer<? super E> consumer) {
+            Objects.requireNonNull(consumer);
+            final int size = ArrayList.this.size;
+            int i = cursor;
+            if (i >= size) {
+                return;
+            }
+            final Object[] elementData = ArrayList.this.elementData;
+            if (i >= elementData.length) {
+                throw new ConcurrentModificationException();
+            }
+            while (i != size && modCount == expectedModCount) {
+                consumer.accept((E) elementData[i++]);
+            }
+            // update once at end of iteration to reduce heap write traffic
+            lastRet = cursor = i;
+            checkForComodification();
+        }
+
         final void checkForComodification() {
             if (modCount != expectedModCount)
                 throw new ConcurrentModificationException();
@@ -1092,6 +1117,26 @@
                     return (E) elementData[offset + (lastRet = i)];
                 }
 
+                @SuppressWarnings("unchecked")
+                public void forEachRemaining(Consumer<? super E> consumer) {
+                    Objects.requireNonNull(consumer);
+                    final int size = SubList.this.size;
+                    int i = cursor;
+                    if (i >= size) {
+                        return;
+                    }
+                    final Object[] elementData = ArrayList.this.elementData;
+                    if (offset + i >= elementData.length) {
+                        throw new ConcurrentModificationException();
+                    }
+                    while (i != size && modCount == expectedModCount) {
+                        consumer.accept((E) elementData[offset + (i++)]);
+                    }
+                    // update once at end of iteration to reduce heap write traffic
+                    lastRet = cursor = i;
+                    checkForComodification();
+                }
+
                 public int nextIndex() {
                     return cursor;
                 }
@@ -1171,6 +1216,12 @@
             if (ArrayList.this.modCount != this.modCount)
                 throw new ConcurrentModificationException();
         }
+
+        public Spliterator<E> spliterator() {
+            checkForComodification();
+            return new ArrayListSpliterator<E>(ArrayList.this, offset,
+                                               offset + this.size, this.modCount);
+        }
     }
 
     @Override
@@ -1188,6 +1239,128 @@
         }
     }
 
+    public Spliterator<E> spliterator() {
+        return new ArrayListSpliterator<>(this, 0, -1, 0);
+    }
+
+    /** Index-based split-by-two, lazily initialized Spliterator */
+    static final class ArrayListSpliterator<E> implements Spliterator<E> {
+
+        /*
+         * 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 spliterators 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 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; // OK if null unless traversed
+            this.index = origin;
+            this.fence = fence;
+            this.expectedModCount = 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 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> action) {
+            if (action == null)
+                throw new NullPointerException();
+            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;
+            }
+            return false;
+        }
+
+        public void forEachRemaining(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();
+        }
+
+        public long estimateSize() {
+            return (long) (getFence() - index);
+        }
+
+        public int characteristics() {
+            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
+        }
+    }
+
     @Override
     public boolean removeIf(Predicate<? super E> filter) {
         Objects.requireNonNull(filter);
--- a/src/share/classes/java/util/Collections.java	Wed Apr 17 14:39:04 2013 -0400
+++ b/src/share/classes/java/util/Collections.java	Wed Apr 17 11:34:31 2013 +0200
@@ -1088,6 +1088,11 @@
                 public void remove() {
                     throw new UnsupportedOperationException();
                 }
+                @Override
+                public void forEachRemaining(Consumer<? super E> action) {
+                    // Use backing collection version
+                    i.forEachRemaining(action);
+                }
             };
         }
 
@@ -1114,6 +1119,7 @@
             throw new UnsupportedOperationException();
         }
 
+        // Override default methods in Collection
         @Override
         public void forEach(Consumer<? super E> action) {
             c.forEach(action);
@@ -1122,6 +1128,11 @@
         public boolean removeIf(Predicate<? super E> filter) {
             throw new UnsupportedOperationException();
         }
+        @Override
+        public Spliterator<E> spliterator() {
+            return (Spliterator<E>)c.spliterator();
+        }
+
     }
 
     /**
@@ -1285,6 +1296,11 @@
                 public void add(E e) {
                     throw new UnsupportedOperationException();
                 }
+
+                @Override
+                public void forEachRemaining(Consumer<? super E> action) {
+                    i.forEachRemaining(action);
+                }
             };
         }
 
@@ -1664,7 +1680,8 @@
      * through the returned collection.<p>
      *
      * It is imperative that the user manually synchronize on the returned
-     * collection when iterating over it:
+     * collection when traversing it via {@link Iterator} or
+     * {@link Spliterator}:
      * <pre>
      *  Collection c = Collections.synchronizedCollection(myCollection);
      *     ...
@@ -1761,18 +1778,22 @@
         public String toString() {
             synchronized (mutex) {return c.toString();}
         }
-        private void writeObject(ObjectOutputStream s) throws IOException {
-            synchronized (mutex) {s.defaultWriteObject();}
-        }
-
+        // Override default methods in Collection
         @Override
-        public void forEach(Consumer<? super E> action) {
-            synchronized (mutex) {c.forEach(action);}
+        public void forEach(Consumer<? super E> consumer) {
+            synchronized (mutex) {c.forEach(consumer);}
         }
         @Override
         public boolean removeIf(Predicate<? super E> filter) {
             synchronized (mutex) {return c.removeIf(filter);}
         }
+        @Override
+        public Spliterator<E> spliterator() {
+            return c.spliterator(); // Must be manually synched by user!
+        }
+        private void writeObject(ObjectOutputStream s) throws IOException {
+            synchronized (mutex) {s.defaultWriteObject();}
+        }
     }
 
     /**
@@ -2533,14 +2554,15 @@
             return c.addAll(checkedCopyOf(coll));
         }
 
+        // Override default methods in Collection
         @Override
-        public void forEach(Consumer<? super E> action) {
-            c.forEach(action);
-        }
+        public void forEach(Consumer<? super E> action) {c.forEach(action);}
         @Override
         public boolean removeIf(Predicate<? super E> filter) {
             return c.removeIf(filter);
         }
+        @Override
+        public Spliterator<E> spliterator() {return c.spliterator();}
     }
 
     /**
@@ -2796,6 +2818,11 @@
                     typeCheck(e);
                     i.add(e);
                 }
+
+                @Override
+                public void forEachRemaining(Consumer<? super E> action) {
+                    i.forEachRemaining(action);
+                }
             };
         }
 
@@ -3334,6 +3361,10 @@
         public boolean hasNext() { return false; }
         public E next() { throw new NoSuchElementException(); }
         public void remove() { throw new IllegalStateException(); }
+        @Override
+        public void forEachRemaining(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+        }
     }
 
     /**
@@ -3474,6 +3505,7 @@
             return a;
         }
 
+        // Override default methods in Collection
         @Override
         public void forEach(Consumer<? super E> action) {
             Objects.requireNonNull(action);
@@ -3483,6 +3515,8 @@
             Objects.requireNonNull(filter);
             return false;
         }
+        @Override
+        public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
 
         // Preserves singleton property
         private Object readResolve() {
@@ -3592,15 +3626,20 @@
             throw new NoSuchElementException();
         }
 
+        // Override default methods in Collection
         @Override
         public void forEach(Consumer<? super E> action) {
             Objects.requireNonNull(action);
         }
+
         @Override
         public boolean removeIf(Predicate<? super E> filter) {
             Objects.requireNonNull(filter);
             return false;
         }
+
+        @Override
+        public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
     }
 
     /**
@@ -3671,10 +3710,6 @@
         public int hashCode() { return 1; }
 
         @Override
-        public void forEach(Consumer<? super E> action) {
-            Objects.requireNonNull(action);
-        }
-        @Override
         public boolean removeIf(Predicate<? super E> filter) {
             Objects.requireNonNull(filter);
             return false;
@@ -3688,6 +3723,15 @@
             Objects.requireNonNull(c);
         }
 
+        // Override default methods in Collection
+        @Override
+        public void forEach(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+        }
+
+        @Override
+        public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
+
         // Preserves singleton property
         private Object readResolve() {
             return EMPTY_LIST;
@@ -3843,6 +3887,60 @@
             public void remove() {
                 throw new UnsupportedOperationException();
             }
+            @Override
+            public void forEachRemaining(Consumer<? super E> action) {
+                Objects.requireNonNull(action);
+                if (hasNext) {
+                    action.accept(e);
+                    hasNext = false;
+                }
+            }
+        };
+    }
+
+    /**
+     * Creates a {@code Spliterator} with only the specified element
+     *
+     * @param <T> Type of elements
+     * @return A singleton {@code Spliterator}
+     */
+    static <T> Spliterator<T> singletonSpliterator(final T element) {
+        return new Spliterator<T>() {
+            long est = 1;
+
+            @Override
+            public Spliterator<T> trySplit() {
+                return null;
+            }
+
+            @Override
+            public boolean tryAdvance(Consumer<? super T> consumer) {
+                Objects.requireNonNull(consumer);
+                if (est > 0) {
+                    est--;
+                    consumer.accept(element);
+                    return true;
+                }
+                return false;
+            }
+
+            @Override
+            public void forEachRemaining(Consumer<? super T> consumer) {
+                tryAdvance(consumer);
+            }
+
+            @Override
+            public long estimateSize() {
+                return est;
+            }
+
+            @Override
+            public int characteristics() {
+                int value = (element != null) ? Spliterator.NONNULL : 0;
+
+                return value | Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.IMMUTABLE |
+                       Spliterator.DISTINCT | Spliterator.ORDERED;
+            }
         };
     }
 
@@ -3867,11 +3965,16 @@
 
         public boolean contains(Object o) {return eq(o, element);}
 
+        // Override default methods for Collection
         @Override
         public void forEach(Consumer<? super E> action) {
             action.accept(element);
         }
         @Override
+        public Spliterator<E> spliterator() {
+            return singletonSpliterator(element);
+        }
+        @Override
         public boolean removeIf(Predicate<? super E> filter) {
             throw new UnsupportedOperationException();
         }
@@ -3916,6 +4019,7 @@
             return element;
         }
 
+        // Override default methods for Collection
         @Override
         public void forEach(Consumer<? super E> action) {
             action.accept(element);
@@ -3931,6 +4035,10 @@
         @Override
         public void sort(Comparator<? super E> c) {
         }
+        @Override
+        public Spliterator<E> spliterator() {
+            return singletonSpliterator(element);
+        }
     }
 
     /**
@@ -4529,6 +4637,7 @@
         public boolean retainAll(Collection<?> c)   {return s.retainAll(c);}
         // addAll is the only inherited implementation
 
+        // Override default methods in Collection
         @Override
         public void forEach(Consumer<? super E> action) {
             s.forEach(action);
@@ -4538,6 +4647,9 @@
             return s.removeIf(filter);
         }
 
+        @Override
+        public Spliterator<E> spliterator() {return s.spliterator();}
+
         private static final long serialVersionUID = 2454657854757543876L;
 
         private void readObject(java.io.ObjectInputStream stream)
@@ -4597,10 +4709,11 @@
         public boolean retainAll(Collection<?> c)   {return q.retainAll(c);}
         // We use inherited addAll; forwarding addAll would be wrong
 
+        // Override default methods in Collection
         @Override
-        public void forEach(Consumer<? super E> action) {
-            q.forEach(action);
-        }
+        public void forEach(Consumer<? super E> action) {q.forEach(action);}
+        @Override
+        public Spliterator<E> spliterator() {return q.spliterator();}
         @Override
         public boolean removeIf(Predicate<? super E> filter) {
             return q.removeIf(filter);
--- a/src/share/classes/java/util/HashMap.java	Wed Apr 17 14:39:04 2013 -0400
+++ b/src/share/classes/java/util/HashMap.java	Wed Apr 17 11:34:31 2013 +0200
@@ -1230,6 +1230,14 @@
         public void clear() {
             HashMap.this.clear();
         }
+
+        public Spliterator<K> spliterator() {
+            if (HashMap.this.getClass() == HashMap.class)
+                return new KeySpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
+            else
+                return Spliterators.spliterator
+                        (this, Spliterator.SIZED | Spliterator.DISTINCT);
+        }
     }
 
     /**
@@ -1263,6 +1271,14 @@
         public void clear() {
             HashMap.this.clear();
         }
+
+        public Spliterator<V> spliterator() {
+            if (HashMap.this.getClass() == HashMap.class)
+                return new ValueSpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
+            else
+                return Spliterators.spliterator
+                        (this, Spliterator.SIZED);
+        }
     }
 
     /**
@@ -1310,6 +1326,14 @@
         public void clear() {
             HashMap.this.clear();
         }
+
+        public 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 Spliterators.spliterator
+                        (this, Spliterator.SIZED | Spliterator.DISTINCT);
+        }
     }
 
     /**
@@ -1406,4 +1430,257 @@
     // These methods are used when serializing HashSets
     int   capacity()     { return table.length; }
     float loadFactor()   { return loadFactor;   }
+
+    /**
+     * Standin until HM overhaul; based loosely on Weak and Identity HM.
+     */
+    static class HashMapSpliterator<K,V> {
+        final HashMap<K,V> map;
+        HashMap.Entry<K,V> current; // current node
+        int index;                  // current index, modified on advance/split
+        int fence;                  // one past last index
+        int est;                    // size estimate
+        int expectedModCount;       // for comodification checks
+
+        HashMapSpliterator(HashMap<K,V> m, int origin,
+                               int fence, int est,
+                               int expectedModCount) {
+            this.map = m;
+            this.index = origin;
+            this.fence = fence;
+            this.est = est;
+            this.expectedModCount = expectedModCount;
+        }
+
+        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;
+        }
+    }
+
+    static final class KeySpliterator<K,V>
+        extends HashMapSpliterator<K,V>
+        implements Spliterator<K> {
+        KeySpliterator(HashMap<K,V> m, int origin, int fence, int est,
+                       int expectedModCount) {
+            super(m, origin, fence, est, expectedModCount);
+        }
+
+        public KeySpliterator<K,V> trySplit() {
+            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 forEachRemaining(Consumer<? super K> action) {
+            int i, hi, mc;
+            if (action == null)
+                throw new NullPointerException();
+            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 = tab[i++];
+                    else {
+                        action.accept(p.getKey());
+                        p = p.next;
+                    }
+                } while (p != null || i < hi);
+                if (m.modCount != mc)
+                    throw new ConcurrentModificationException();
+            }
+        }
+
+        @SuppressWarnings("unchecked")
+        public boolean tryAdvance(Consumer<? super K> action) {
+            int hi;
+            if (action == null)
+                throw new NullPointerException();
+            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 = tab[index++];
+                    else {
+                        K k = current.getKey();
+                        current = current.next;
+                        action.accept(k);
+                        if (map.modCount != expectedModCount)
+                            throw new ConcurrentModificationException();
+                        return true;
+                    }
+                }
+            }
+            return false;
+        }
+
+        public int characteristics() {
+            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
+                Spliterator.DISTINCT;
+        }
+    }
+
+    static final class ValueSpliterator<K,V>
+        extends HashMapSpliterator<K,V>
+        implements Spliterator<V> {
+        ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est,
+                         int expectedModCount) {
+            super(m, origin, fence, est, expectedModCount);
+        }
+
+        public ValueSpliterator<K,V> trySplit() {
+            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 forEachRemaining(Consumer<? super V> action) {
+            int i, hi, mc;
+            if (action == null)
+                throw new NullPointerException();
+            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 = tab[i++];
+                    else {
+                        action.accept(p.getValue());
+                        p = p.next;
+                    }
+                } while (p != null || i < hi);
+                if (m.modCount != mc)
+                    throw new ConcurrentModificationException();
+            }
+        }
+
+        @SuppressWarnings("unchecked")
+        public boolean tryAdvance(Consumer<? super V> action) {
+            int hi;
+            if (action == null)
+                throw new NullPointerException();
+            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 = tab[index++];
+                    else {
+                        V v = current.getValue();
+                        current = current.next;
+                        action.accept(v);
+                        if (map.modCount != expectedModCount)
+                            throw new ConcurrentModificationException();
+                        return true;
+                    }
+                }
+            }
+            return false;
+        }
+
+        public int characteristics() {
+            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);
+        }
+    }
+
+    static final class EntrySpliterator<K,V>
+        extends HashMapSpliterator<K,V>
+        implements Spliterator<Map.Entry<K,V>> {
+        EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
+                         int expectedModCount) {
+            super(m, origin, fence, est, expectedModCount);
+        }
+
+        public EntrySpliterator<K,V> trySplit() {
+            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 forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
+            int i, hi, mc;
+            if (action == null)
+                throw new NullPointerException();
+            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 = tab[i++];
+                    else {
+                        action.accept(p);
+                        p = p.next;
+                    }
+                } while (p != null || i < hi);
+                if (m.modCount != mc)
+                    throw new ConcurrentModificationException();
+            }
+        }
+
+        @SuppressWarnings("unchecked")
+        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
+            int hi;
+            if (action == null)
+                throw new NullPointerException();
+            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 = tab[index++];
+                    else {
+                        HashMap.Entry<K,V> e = current;
+                        current = current.next;
+                        action.accept(e);
+                        if (map.modCount != expectedModCount)
+                            throw new ConcurrentModificationException();
+                        return true;
+                    }
+                }
+            }
+            return false;
+        }
+
+        public int characteristics() {
+            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
+                Spliterator.DISTINCT;
+        }
+    }
 }
--- a/src/share/classes/java/util/HashSet.java	Wed Apr 17 14:39:04 2013 -0400
+++ b/src/share/classes/java/util/HashSet.java	Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -311,4 +311,8 @@
             map.put(e, PRESENT);
         }
     }
+
+    public Spliterator<E> spliterator() {
+        return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
+    }
 }
--- a/src/share/classes/java/util/IdentityHashMap.java	Wed Apr 17 14:39:04 2013 -0400
+++ b/src/share/classes/java/util/IdentityHashMap.java	Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2000, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -24,8 +24,10 @@
  */
 
 package java.util;
+
 import java.io.*;
 import java.lang.reflect.Array;
+import java.util.function.Consumer;
 
 /**
  * This class implements the <tt>Map</tt> interface with a hash table, using
@@ -162,19 +164,19 @@
     /**
      * The table, resized as necessary. Length MUST always be a power of two.
      */
-    private transient Object[] table;
+    transient Object[] table; // non-private to simplify nested class access
 
     /**
      * The number of key-value mappings contained in this identity hash map.
      *
      * @serial
      */
-    private int size;
+    int size;
 
     /**
      * The number of modifications, to support fast-fail iterators
      */
-    private transient int modCount;
+    transient int modCount;
 
     /**
      * The next size value at which to resize (capacity * load factor).
@@ -184,7 +186,7 @@
     /**
      * Value representing null keys inside tables.
      */
-    private static final Object NULL_KEY = new Object();
+    static final Object NULL_KEY = new Object();
 
     /**
      * Use NULL_KEY for key if it is null.
@@ -196,7 +198,7 @@
     /**
      * Returns internal representation of null key back to caller as null.
      */
-    private static Object unmaskNull(Object key) {
+    static final Object unmaskNull(Object key) {
         return (key == NULL_KEY ? null : key);
     }
 
@@ -1012,7 +1014,7 @@
             return result;
         }
         public Object[] toArray() {
-            return toArray(new Object[size()]);
+            return toArray(new Object[0]);
         }
         @SuppressWarnings("unchecked")
         public <T> T[] toArray(T[] a) {
@@ -1042,6 +1044,10 @@
             }
             return a;
         }
+
+        public Spliterator<K> spliterator() {
+            return new KeySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+        }
     }
 
     /**
@@ -1095,7 +1101,7 @@
             IdentityHashMap.this.clear();
         }
         public Object[] toArray() {
-            return toArray(new Object[size()]);
+            return toArray(new Object[0]);
         }
         @SuppressWarnings("unchecked")
         public <T> T[] toArray(T[] a) {
@@ -1124,6 +1130,10 @@
             }
             return a;
         }
+
+        public Spliterator<V> spliterator() {
+            return new ValueSpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+        }
     }
 
     /**
@@ -1211,7 +1221,7 @@
         }
 
         public Object[] toArray() {
-            return toArray(new Object[size()]);
+            return toArray(new Object[0]);
         }
 
         @SuppressWarnings("unchecked")
@@ -1242,6 +1252,10 @@
             }
             return a;
         }
+
+        public Spliterator<Map.Entry<K,V>> spliterator() {
+            return new EntrySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+        }
     }
 
 
@@ -1322,4 +1336,223 @@
         tab[i] = k;
         tab[i + 1] = value;
     }
+
+    /**
+     * 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
+        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> map, int origin,
+                                   int fence, int est, int expectedModCount) {
+            this.map = map;
+            this.index = origin;
+            this.fence = fence;
+            this.est = est;
+            this.expectedModCount = expectedModCount;
+        }
+
+        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>
+        extends IdentityHashMapSpliterator<K,V>
+        implements Spliterator<K> {
+        KeySpliterator(IdentityHashMap<K,V> map, int origin, int fence, int est,
+                       int expectedModCount) {
+            super(map, origin, fence, est, expectedModCount);
+        }
+
+        public KeySpliterator<K,V> trySplit() {
+            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);
+        }
+
+        @SuppressWarnings("unchecked")
+        public void forEachRemaining(Consumer<? super K> action) {
+            if (action == null)
+                throw new NullPointerException();
+            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();
+        }
+
+        @SuppressWarnings("unchecked")
+        public boolean tryAdvance(Consumer<? super K> action) {
+            if (action == null)
+                throw new NullPointerException();
+            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 (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
+        }
+    }
+
+    static final class ValueSpliterator<K,V>
+        extends IdentityHashMapSpliterator<K,V>
+        implements Spliterator<V> {
+        ValueSpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
+                         int expectedModCount) {
+            super(m, origin, fence, est, expectedModCount);
+        }
+
+        public ValueSpliterator<K,V> trySplit() {
+            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 forEachRemaining(Consumer<? super V> action) {
+            if (action == null)
+                throw new NullPointerException();
+            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];
+                        action.accept(v);
+                    }
+                }
+                if (m.modCount == expectedModCount)
+                    return;
+            }
+            throw new ConcurrentModificationException();
+        }
+
+        public boolean tryAdvance(Consumer<? super V> action) {
+            if (action == null)
+                throw new NullPointerException();
+            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>
+        extends IdentityHashMapSpliterator<K,V>
+        implements Spliterator<Map.Entry<K,V>> {
+        EntrySpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
+                         int expectedModCount) {
+            super(m, origin, fence, est, expectedModCount);
+        }
+
+        public EntrySpliterator<K,V> trySplit() {
+            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 forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
+            if (action == null)
+                throw new NullPointerException();
+            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];
+                        action.accept
+                            (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
+
+                    }
+                }
+                if (m.modCount == expectedModCount)
+                    return;
+            }
+            throw new ConcurrentModificationException();
+        }
+
+        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
+            if (action == null)
+                throw new NullPointerException();
+            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 (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
+        }
+    }
+
 }
--- a/src/share/classes/java/util/LinkedHashSet.java	Wed Apr 17 14:39:04 2013 -0400
+++ b/src/share/classes/java/util/LinkedHashSet.java	Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2000, 2006, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -168,4 +168,18 @@
         super(Math.max(2*c.size(), 11), .75f, true);
         addAll(c);
     }
+
+    /**
+     * Creates a {@code Spliterator}, over the elements in this set, that
+     * reports {@code SIZED}, {@code DISTINCT} and {@code ORDERED}.
+     * Overriding implementations are expected to document if the
+     * {@code Spliterator} reports any additional and relevant characteristic
+     * values.
+     *
+     * @return a {@code Spliterator} over the elements in this set
+     */
+    @Override
+    public Spliterator<E> spliterator() {
+        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
+    }
 }
--- a/src/share/classes/java/util/LinkedList.java	Wed Apr 17 14:39:04 2013 -0400
+++ b/src/share/classes/java/util/LinkedList.java	Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -25,6 +25,8 @@
 
 package java.util;
 
+import java.util.function.Consumer;
+
 /**
  * Doubly-linked list implementation of the {@code List} and {@code Deque}
  * interfaces.  Implements all optional list operations, and permits all
@@ -948,6 +950,16 @@
             expectedModCount++;
         }
 
+        public void forEachRemaining(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+            while (modCount == expectedModCount && nextIndex < size) {
+                action.accept(next.item);
+                next = next.next;
+                nextIndex++;
+            }
+            checkForComodification();
+        }
+
         final void checkForComodification() {
             if (modCount != expectedModCount)
                 throw new ConcurrentModificationException();
@@ -1135,4 +1147,103 @@
         for (int i = 0; i < size; i++)
             linkLast((E)s.readObject());
     }
+
+    public Spliterator<E> spliterator() {
+        return new LLSpliterator<E>(this, -1, 0);
+    }
+
+    /** A customized variant of Spliterators.IteratorSpliterator */
+    static final class LLSpliterator<E> implements Spliterator<E> {
+        static final int BATCH_UNIT = 1 << 10;  // batch array size increment
+        static final int MAX_BATCH = 1 << 25;  // max batch array 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 s = getEst();
+            if (s > 1 && (p = current) != null) {
+                int n = batch + BATCH_UNIT;
+                if (n > s)
+                    n = s;
+                if (n > MAX_BATCH)
+                    n = MAX_BATCH;
+                Object[] a;
+                try {
+                    a = new Object[n];
+                } catch (OutOfMemoryError oome) {
+                    return null;
+                }
+                int j = 0;
+                do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
+                current = p;
+                batch = j;
+                est = s - j;
+                return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
+            }
+            return null;
+        }
+
+        public void forEachRemaining(Consumer<? super E> action) {
+            Node<E> p; int n;
+            if (action == null) throw new NullPointerException();
+            if ((n = getEst()) > 0 && (p = current) != null) {
+                current = null;
+                est = 0;
+                do {
+                    E e = p.item;
+                    p = p.next;
+                    action.accept(e);
+                } while (p != null && --n > 0);
+            }
+            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) {
+                --est;
+                E e = p.item;
+                current = p.next;
+                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 Apr 17 14:39:04 2013 -0400
+++ b/src/share/classes/java/util/PriorityQueue.java	Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -25,6 +25,8 @@
 
 package java.util;
 
+import java.util.function.Consumer;
+
 /**
  * An unbounded priority {@linkplain Queue queue} based on a priority heap.
  * The elements of the priority queue are ordered according to their
@@ -56,7 +58,7 @@
  * the priority queue in any particular order. If you need ordered
  * traversal, consider using {@code Arrays.sort(pq.toArray())}.
  *
- * <p> <strong>Note that this implementation is not synchronized.</strong>
+ * <p><strong>Note that this implementation is not synchronized.</strong>
  * Multiple threads should not access a {@code PriorityQueue}
  * instance concurrently if any of the threads modifies the queue.
  * Instead, use the thread-safe {@link
@@ -92,7 +94,7 @@
      * heap and each descendant d of n, n <= d.  The element with the
      * lowest value is in queue[0], assuming the queue is nonempty.
      */
-    private transient Object[] queue;
+    transient Object[] queue; // non-private to simplify nested class access
 
     /**
      * The number of elements in the priority queue.
@@ -109,7 +111,7 @@
      * The number of times this priority queue has been
      * <i>structurally modified</i>.  See AbstractList for gory details.
      */
-    private transient int modCount = 0;
+    transient int modCount = 0; // non-private to simplify nested class access
 
     /**
      * Creates a {@code PriorityQueue} with the default initial
@@ -332,9 +334,7 @@
 
     @SuppressWarnings("unchecked")
     public E peek() {
-        if (size == 0)
-            return null;
-        return (E) queue[0];
+        return (size == 0) ? null : (E) queue[0];
     }
 
     private int indexOf(Object o) {
@@ -431,15 +431,14 @@
      * precise control over the runtime type of the output array, and may,
      * under certain circumstances, be used to save allocation costs.
      *
-     * <p>Suppose <tt>x</tt> is a queue known to contain only strings.
+     * <p>Suppose {@code x} is a queue known to contain only strings.
      * The following code can be used to dump the queue into a newly
-     * allocated array of <tt>String</tt>:
+     * 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 <tt>toArray(new Object[0])</tt> is identical in function to
-     * <tt>toArray()</tt>.
+     * Note that {@code toArray(new Object[0])} is identical in function to
+     * {@code toArray()}.
      *
      * @param a the array into which the elements of the queue are to
      *          be stored, if it is big enough; otherwise, a new array of the
@@ -452,6 +451,7 @@
      */
     @SuppressWarnings("unchecked")
     public <T> T[] toArray(T[] a) {
+        final int size = this.size;
         if (a.length < size)
             // Make a new array of a's runtime type, but my contents:
             return (T[]) Arrays.copyOf(queue, size, a.getClass());
@@ -569,15 +569,14 @@
         size = 0;
     }
 
+    @SuppressWarnings("unchecked")
     public E poll() {
         if (size == 0)
             return null;
         int s = --size;
         modCount++;
-        @SuppressWarnings("unchecked")
-            E result = (E) queue[0];
-        @SuppressWarnings("unchecked")
-            E x = (E) queue[s];
+        E result = (E) queue[0];
+        E x = (E) queue[s];
         queue[s] = null;
         if (s != 0)
             siftDown(0, x);
@@ -596,15 +595,15 @@
      * position before i. This fact is used by iterator.remove so as to
      * avoid missing traversing elements.
      */
+    @SuppressWarnings("unchecked")
     private E removeAt(int i) {
-        assert i >= 0 && i < size;
+        // assert i >= 0 && i < size;
         modCount++;
         int s = --size;
         if (s == i) // removed last element
             queue[i] = null;
         else {
-            @SuppressWarnings("unchecked")
-                E moved = (E) queue[s];
+            E moved = (E) queue[s];
             queue[s] = null;
             siftDown(i, moved);
             if (queue[i] == moved) {
@@ -649,12 +648,12 @@
         queue[k] = key;
     }
 
+    @SuppressWarnings("unchecked")
     private void siftUpUsingComparator(int k, E x) {
         while (k > 0) {
             int parent = (k - 1) >>> 1;
-            @SuppressWarnings("unchecked")
-                E e = (E) queue[parent];
-            if (comparator.compare(x, e) >= 0)
+            Object e = queue[parent];
+            if (comparator.compare(x, (E) e) >= 0)
                 break;
             queue[k] = e;
             k = parent;
@@ -738,8 +737,7 @@
     }
 
     /**
-     * Saves the state of the instance to a stream (that
-     * is, serializes it).
+     * Saves this queue to a stream (that is, serializes it).
      *
      * @serialData The length of the array backing the instance is
      *             emitted (int), followed by all of its elements
@@ -747,7 +745,7 @@
      * @param s the stream
      */
     private void writeObject(java.io.ObjectOutputStream s)
-        throws java.io.IOException{
+        throws java.io.IOException {
         // Write out element count, and any hidden stuff
         s.defaultWriteObject();
 
@@ -783,4 +781,99 @@
         // spec has never explained what that might be.
         heapify();
     }
+
+    public final Spliterator<E> spliterator() {
+        return new PriorityQueueSpliterator<E>(this, 0, -1, 0);
+    }
+
+    static final class PriorityQueueSpliterator<E> implements Spliterator<E> {
+        /*
+         * 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 int fence;            // -1 until first use
+        private int expectedModCount; // initialized when fence set
+
+        /** Creates new spliterator covering the given range */
+        PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,
+                             int expectedModCount) {
+            this.pq = pq;
+            this.index = origin;
+            this.fence = fence;
+            this.expectedModCount = 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 PriorityQueueSpliterator<E> trySplit() {
+            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+            return (lo >= mid) ? null :
+                new PriorityQueueSpliterator<E>(pq, lo, index = mid,
+                                                expectedModCount);
+        }
+
+        @SuppressWarnings("unchecked")
+        public void forEachRemaining(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) {
+            if (action == null)
+                throw new NullPointerException();
+            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;
+            }
+            return false;
+        }
+
+        public long estimateSize() {
+            return (long) (getFence() - index);
+        }
+
+        public int characteristics() {
+            return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL;
+        }
+    }
 }
--- a/src/share/classes/java/util/TreeMap.java	Wed Apr 17 14:39:04 2013 -0400
+++ b/src/share/classes/java/util/TreeMap.java	Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -25,6 +25,8 @@
 
 package java.util;
 
+import java.util.function.Consumer;
+
 /**
  * A Red-Black tree based {@link NavigableMap} implementation.
  * The map is sorted according to the {@linkplain Comparable natural
@@ -971,6 +973,10 @@
         public void clear() {
             TreeMap.this.clear();
         }
+
+        public Spliterator<V> spliterator() {
+            return new ValueSpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
+        }
     }
 
     class EntrySet extends AbstractSet<Map.Entry<K,V>> {
@@ -1007,6 +1013,10 @@
         public void clear() {
             TreeMap.this.clear();
         }
+
+        public Spliterator<Map.Entry<K,V>> spliterator() {
+            return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
+        }
     }
 
     /*
@@ -1090,6 +1100,10 @@
         public NavigableSet<E> descendingSet() {
             return new KeySet<>(m.descendingMap());
         }
+
+        public Spliterator<E> spliterator() {
+            return keySpliteratorFor(m);
+        }
     }
 
     /**
@@ -1389,6 +1403,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();
 
@@ -1650,19 +1666,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) {
@@ -1677,7 +1680,47 @@
             }
         }
 
-        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 Spliterator<K> trySplit() {
+                return null;
+            }
+            public void forEachRemaining(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 long estimateSize() {
+                return Long.MAX_VALUE;
+            }
+            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);
@@ -1688,6 +1731,26 @@
             public void remove() {
                 removeDescending();
             }
+            public Spliterator<K> trySplit() {
+                return null;
+            }
+            public void forEachRemaining(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 long estimateSize() {
+                return Long.MAX_VALUE;
+            }
+            public int characteristics() {
+                return Spliterator.DISTINCT | Spliterator.ORDERED;
+            }
         }
     }
 
@@ -1747,6 +1810,10 @@
             return new SubMapKeyIterator(absLowest(), absHighFence());
         }
 
+        Spliterator<K> keySpliterator() {
+            return new SubMapKeyIterator(absLowest(), absHighFence());
+        }
+
         Iterator<K> descendingKeyIterator() {
             return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
         }
@@ -1828,6 +1895,10 @@
             return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
         }
 
+        Spliterator<K> keySpliterator() {
+            return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
+        }
+
         Iterator<K> descendingKeyIterator() {
             return new SubMapKeyIterator(absLowest(), absHighFence());
         }
@@ -2444,4 +2515,407 @@
             level++;
         return level;
     }
+
+    /**
+     * Currently, we support Spliterator-based versions only for the
+     * full map, in either plain of descending form, otherwise relying
+     * on defaults because size estimation for submaps would dominate
+     * costs. The type tests needed to check these for key views are
+     * not very nice but avoid disrupting existing class
+     * structures. Callers must use plain default spliterators if this
+     * returns null.
+     */
+    static <K> Spliterator<K> keySpliteratorFor(NavigableMap<K,?> m) {
+        if (m instanceof TreeMap) {
+            @SuppressWarnings("unchecked") TreeMap<K,Object> t =
+                (TreeMap<K,Object>) m;
+            return t.keySpliterator();
+        }
+        if (m instanceof DescendingSubMap) {
+            @SuppressWarnings("unchecked") DescendingSubMap<K,?> dm =
+                (DescendingSubMap<K,?>) m;
+            TreeMap<K,?> tm = dm.m;
+            if (dm == tm.descendingMap) {
+                @SuppressWarnings("unchecked") TreeMap<K,Object> t =
+                    (TreeMap<K,Object>) tm;
+                return t.descendingKeySpliterator();
+            }
+        }
+        @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);
+    }
+
+    /**
+     * Base class for spliterators.  Iteration starts at a given
+     * origin and continues up to but not including a given fence (or
+     * null for end).  At top-level, for ascending cases, the first
+     * split uses the root as left-fence/right-origin. From there,
+     * right-hand splits replace the current fence with its left
+     * child, also serving as origin for the split-off spliterator.
+     * Left-hands are symmetric. Descending versions place the origin
+     * at the end and invert ascending split rules.  This base class
+     * is non-commital about directionality, or whether the top-level
+     * spliterator covers the whole tree. This means that the actual
+     * split mechanics are located in subclasses. Some of the subclass
+     * trySplit methods are identical (except for return types), but
+     * not nicely factorable.
+     *
+     * Currently, subclass versions exist only for the full map
+     * (including descending keys via its descendingMap).  Others are
+     * possible but currently not worthwhile because submaps require
+     * 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;
+        TreeMap.Entry<K,V> current; // traverser; initially first node in range
+        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)
+        int expectedModCount;       // for CME checks
+
+        TreeMapSpliterator(TreeMap<K,V> tree,
+                           TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+                           int side, int est, int expectedModCount) {
+            this.tree = tree;
+            this.current = origin;
+            this.fence = fence;
+            this.side = side;
+            this.est = est;
+            this.expectedModCount = expectedModCount;
+        }
+
+        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 final long estimateSize() {
+            return (long)getEstimate();
+        }
+    }
+
+    static final class KeySpliterator<K,V>
+        extends TreeMapSpliterator<K,V>
+        implements Spliterator<K> {
+        KeySpliterator(TreeMap<K,V> tree,
+                       TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+                       int side, int est, int expectedModCount) {
+            super(tree, origin, fence, side, est, expectedModCount);
+        }
+
+        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
+                     (d == 0)              ? tree.root : // was top
+                     (d >  0)              ? e.right :   // was right
+                     (d <  0 && f != null) ? f.left :    // was left
+                     null);
+            if (s != null && s != e && s != f &&
+                tree.compare(e.key, s.key) < 0) {        // e not already past s
+                side = 1;
+                return new KeySpliterator<>
+                    (tree, e, current = s, -1, est >>>= 1, expectedModCount);
+            }
+            return null;
+        }
+
+        public void forEachRemaining(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 {
+                    action.accept(e.key);
+                    if ((p = e.right) != null) {
+                        while ((pl = p.left) != null)
+                            p = pl;
+                    }
+                    else {
+                        while ((p = e.parent) != null && e == p.right)
+                            e = p;
+                    }
+                } while ((e = p) != null && e != f);
+                if (tree.modCount != expectedModCount)
+                    throw new ConcurrentModificationException();
+            }
+        }
+
+        public boolean tryAdvance(Consumer<? super K> action) {
+            TreeMap.Entry<K,V> e;
+            if (action == null)
+                throw new NullPointerException();
+            if (est < 0)
+                getEstimate(); // force initialization
+            if ((e = current) == null || e == fence)
+                return false;
+            current = successor(e);
+            action.accept(e.key);
+            if (tree.modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            return true;
+        }
+
+        public int characteristics() {
+            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>
+        extends TreeMapSpliterator<K,V>
+        implements Spliterator<K> {
+        DescendingKeySpliterator(TreeMap<K,V> tree,
+                                 TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+                                 int side, int est, int expectedModCount) {
+            super(tree, origin, fence, side, est, expectedModCount);
+        }
+
+        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
+                         (d == 0)              ? tree.root : // was top
+                         (d <  0)              ? e.left :    // was left
+                         (d >  0 && f != null) ? f.right :   // was right
+                         null);
+            if (s != null && s != e && s != f &&
+                tree.compare(e.key, s.key) > 0) {       // e not already past s
+                side = 1;
+                return new DescendingKeySpliterator<>
+                        (tree, e, current = s, -1, est >>>= 1, expectedModCount);
+            }
+            return null;
+        }
+
+        public void forEachRemaining(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 {
+                    action.accept(e.key);
+                    if ((p = e.left) != null) {
+                        while ((pr = p.right) != null)
+                            p = pr;
+                    }
+                    else {
+                        while ((p = e.parent) != null && e == p.left)
+                            e = p;
+                    }
+                } while ((e = p) != null && e != f);
+                if (tree.modCount != expectedModCount)
+                    throw new ConcurrentModificationException();
+            }
+        }
+
+        public boolean tryAdvance(Consumer<? super K> action) {
+            TreeMap.Entry<K,V> e;
+            if (action == null)
+                throw new NullPointerException();
+            if (est < 0)
+                getEstimate(); // force initialization
+            if ((e = current) == null || e == fence)
+                return false;
+            current = predecessor(e);
+            action.accept(e.key);
+            if (tree.modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            return true;
+        }
+
+        public int characteristics() {
+            return (side == 0 ? Spliterator.SIZED : 0) |
+                Spliterator.DISTINCT | Spliterator.ORDERED;
+        }
+    }
+
+    static final class ValueSpliterator<K,V>
+            extends TreeMapSpliterator<K,V>
+            implements Spliterator<V> {
+        ValueSpliterator(TreeMap<K,V> tree,
+                         TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+                         int side, int est, int expectedModCount) {
+            super(tree, origin, fence, side, est, expectedModCount);
+        }
+
+        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
+                         (d == 0)              ? tree.root : // was top
+                         (d >  0)              ? e.right :   // was right
+                         (d <  0 && f != null) ? f.left :    // was left
+                         null);
+            if (s != null && s != e && s != f &&
+                tree.compare(e.key, s.key) < 0) {        // e not already past s
+                side = 1;
+                return new ValueSpliterator<>
+                        (tree, e, current = s, -1, est >>>= 1, expectedModCount);
+            }
+            return null;
+        }
+
+        public void forEachRemaining(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 {
+                    action.accept(e.value);
+                    if ((p = e.right) != null) {
+                        while ((pl = p.left) != null)
+                            p = pl;
+                    }
+                    else {
+                        while ((p = e.parent) != null && e == p.right)
+                            e = p;
+                    }
+                } while ((e = p) != null && e != f);
+                if (tree.modCount != expectedModCount)
+                    throw new ConcurrentModificationException();
+            }
+        }
+
+        public boolean tryAdvance(Consumer<? super V> action) {
+            TreeMap.Entry<K,V> e;
+            if (action == null)
+                throw new NullPointerException();
+            if (est < 0)
+                getEstimate(); // force initialization
+            if ((e = current) == null || e == fence)
+                return false;
+            current = successor(e);
+            action.accept(e.value);
+            if (tree.modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            return true;
+        }
+
+        public int characteristics() {
+            return (side == 0 ? Spliterator.SIZED : 0);
+        }
+    }
+
+    static final class EntrySpliterator<K,V>
+        extends TreeMapSpliterator<K,V>
+        implements Spliterator<Map.Entry<K,V>> {
+        EntrySpliterator(TreeMap<K,V> tree,
+                         TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+                         int side, int est, int expectedModCount) {
+            super(tree, origin, fence, side, est, expectedModCount);
+        }
+
+        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
+                         (d == 0)              ? tree.root : // was top
+                         (d >  0)              ? e.right :   // was right
+                         (d <  0 && f != null) ? f.left :    // was left
+                         null);
+            if (s != null && s != e && s != f &&
+                tree.compare(e.key, s.key) < 0) {        // e not already past s
+                side = 1;
+                return new EntrySpliterator<>
+                        (tree, e, current = s, -1, est >>>= 1, expectedModCount);
+            }
+            return null;
+        }
+
+        public void forEachRemaining(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 {
+                    action.accept(e);
+                    if ((p = e.right) != null) {
+                        while ((pl = p.left) != null)
+                            p = pl;
+                    }
+                    else {
+                        while ((p = e.parent) != null && e == p.right)
+                            e = p;
+                    }
+                } while ((e = p) != null && e != f);
+                if (tree.modCount != expectedModCount)
+                    throw new ConcurrentModificationException();
+            }
+        }
+
+        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
+            TreeMap.Entry<K,V> e;
+            if (action == null)
+                throw new NullPointerException();
+            if (est < 0)
+                getEstimate(); // force initialization
+            if ((e = current) == null || e == fence)
+                return false;
+            current = successor(e);
+            action.accept(e);
+            if (tree.modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            return true;
+        }
+
+        public int characteristics() {
+            return (side == 0 ? Spliterator.SIZED : 0) |
+                   Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
+        }
+
+        @Override
+        public Comparator<? super Map.Entry<K, V>> getComparator() {
+            return tree.comparator != null ?
+                   Comparators.byKey(tree.comparator) : null;
+        }
+    }
 }
--- a/src/share/classes/java/util/TreeSet.java	Wed Apr 17 14:39:04 2013 -0400
+++ b/src/share/classes/java/util/TreeSet.java	Wed Apr 17 11:34:31 2013 +0200
@@ -533,5 +533,9 @@
         tm.readTreeSet(size, s, PRESENT);
     }
 
+    public Spliterator<E> spliterator() {
+        return TreeMap.keySpliteratorFor(m);
+    }
+
     private static final long serialVersionUID = -2479143000061671589L;
 }
--- a/src/share/classes/java/util/Vector.java	Wed Apr 17 14:39:04 2013 -0400
+++ b/src/share/classes/java/util/Vector.java	Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1994, 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1994, 2013, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -29,6 +29,8 @@
 import java.util.function.Predicate;
 import java.util.function.UnaryOperator;
 
+import java.util.function.Consumer;
+
 /**
  * The {@code Vector} class implements a growable array of
  * objects. Like an array, it contains components that can be
@@ -1155,6 +1157,28 @@
             lastRet = -1;
         }
 
+        @Override
+        public void forEachRemaining(Consumer<? super E> action) {
+            Objects.requireNonNull(action);
+            synchronized (Vector.this) {
+                final int size = Vector.this.elementCount;
+                int i = cursor;
+                if (i >= size) {
+                    return;
+                }
+                final Object[] elementData = Vector.this.elementData;
+                if (i >= elementData.length) {
+                    throw new ConcurrentModificationException();
+                }
+                while (i != size && modCount == expectedModCount) {
+                    action.accept((E) elementData[i++]);
+                }
+                // update once at end of iteration to reduce heap write traffic
+                lastRet = cursor = i;
+                checkForComodification();
+            }
+        }
+
         final void checkForComodification() {
             if (modCount != expectedModCount)
                 throw new ConcurrentModificationException();
@@ -1298,4 +1322,96 @@
         }
         modCount++;
     }
+
+    @Override
+    public Spliterator<E> spliterator() {
+        return new VectorSpliterator<>(this, null, 0, -1, 0);
+    }
+
+    /** Similar to ArrayList Spliterator */
+    static final class VectorSpliterator<E> implements Spliterator<E> {
+        private final Vector<E> list;
+        private Object[] array;
+        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, Object[] array, int origin, int fence,
+                          int expectedModCount) {
+            this.list = list;
+            this.array = array;
+            this.index = origin;
+            this.fence = fence;
+            this.expectedModCount = expectedModCount;
+        }
+
+        private int getFence() { // initialize on first use
+            int hi;
+            if ((hi = fence) < 0) {
+                synchronized(list) {
+                    array = list.elementData;
+                    expectedModCount = list.modCount;
+                    hi = fence = list.elementCount;
+                }
+            }
+            return hi;
+        }
+
+        public Spliterator<E> trySplit() {
+            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+            return (lo >= mid) ? null :
+                new VectorSpliterator<E>(list, array, lo, index = mid,
+                                         expectedModCount);
+        }
+
+        @SuppressWarnings("unchecked")
+        public boolean tryAdvance(Consumer<? super E> action) {
+            int i;
+            if (action == null)
+                throw new NullPointerException();
+            if (getFence() > (i = index)) {
+                index = i + 1;
+                action.accept((E)array[i]);
+                if (list.modCount != expectedModCount)
+                    throw new ConcurrentModificationException();
+                return true;
+            }
+            return false;
+        }
+
+        @SuppressWarnings("unchecked")
+        public void forEachRemaining(Consumer<? super E> action) {
+            int i, hi; // hoist accesses and checks from loop
+            Vector<E> lst; Object[] a;
+            if (action == null)
+                throw new NullPointerException();
+            if ((lst = list) != null) {
+                if ((hi = fence) < 0) {
+                    synchronized(lst) {
+                        expectedModCount = lst.modCount;
+                        a = array = lst.elementData;
+                        hi = fence = lst.elementCount;
+                    }
+                }
+                else
+                    a = array;
+                if (a != null && (i = index) >= 0 && (index = hi) <= a.length) {
+                    while (i < hi)
+                        action.accept((E) a[i++]);
+                    if (lst.modCount == expectedModCount)
+                        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 Apr 17 14:39:04 2013 -0400
+++ b/src/share/classes/java/util/WeakHashMap.java	Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1998, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -24,8 +24,10 @@
  */
 
 package java.util;
+
 import java.lang.ref.WeakReference;
 import java.lang.ref.ReferenceQueue;
+import java.util.function.Consumer;
 
 
 /**
@@ -898,6 +900,10 @@
         public void clear() {
             WeakHashMap.this.clear();
         }
+
+        public Spliterator<K> spliterator() {
+            return new KeySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
+        }
     }
 
     /**
@@ -934,6 +940,10 @@
         public void clear() {
             WeakHashMap.this.clear();
         }
+
+        public Spliterator<V> spliterator() {
+            return new ValueSpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
+        }
     }
 
     /**
@@ -994,5 +1004,288 @@
         public <T> T[] toArray(T[] a) {
             return deepCopy().toArray(a);
         }
+
+        public Spliterator<Map.Entry<K,V>> spliterator() {
+            return new EntrySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
+        }
     }
+
+    /**
+     * Similar form as other hash Spliterators, but skips dead
+     * elements.
+     */
+    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
+        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,
+                               int expectedModCount) {
+            this.map = m;
+            this.index = origin;
+            this.fence = fence;
+            this.est = est;
+            this.expectedModCount = expectedModCount;
+        }
+
+        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;
+        }
+    }
+
+    static final class KeySpliterator<K,V>
+        extends WeakHashMapSpliterator<K,V>
+        implements Spliterator<K> {
+        KeySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
+                       int expectedModCount) {
+            super(m, origin, fence, est, expectedModCount);
+        }
+
+        public KeySpliterator<K,V> trySplit() {
+            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 forEachRemaining(Consumer<? super K> action) {
+            int i, hi, mc;
+            if (action == null)
+                throw new NullPointerException();
+            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 {
+                    if (p == null)
+                        p = tab[i++];
+                    else {
+                        Object x = p.get();
+                        p = p.next;
+                        if (x != null) {
+                            @SuppressWarnings("unchecked") K k =
+                                (K) WeakHashMap.unmaskNull(x);
+                            action.accept(k);
+                        }
+                    }
+                } while (p != null || i < hi);
+            }
+            if (m.modCount != mc)
+                throw new ConcurrentModificationException();
+        }
+
+        public boolean tryAdvance(Consumer<? super K> action) {
+            int hi;
+            if (action == null)
+                throw new NullPointerException();
+            WeakHashMap.Entry<K,V>[] tab = map.table;
+            if (tab.length >= (hi = getFence()) && index >= 0) {
+                while (current != null || index < hi) {
+                    if (current == null)
+                        current = tab[index++];
+                    else {
+                        Object x = current.get();
+                        current = current.next;
+                        if (x != null) {
+                            @SuppressWarnings("unchecked") K k =
+                                (K) WeakHashMap.unmaskNull(x);
+                            action.accept(k);
+                            if (map.modCount != expectedModCount)
+                                throw new ConcurrentModificationException();
+                            return true;
+                        }
+                    }
+                }
+            }
+            return false;
+        }
+
+        public int characteristics() {
+            return Spliterator.DISTINCT;
+        }
+    }
+
+    static final class ValueSpliterator<K,V>
+        extends WeakHashMapSpliterator<K,V>
+        implements Spliterator<V> {
+        ValueSpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
+                         int expectedModCount) {
+            super(m, origin, fence, est, expectedModCount);
+        }
+
+        public ValueSpliterator<K,V> trySplit() {
+            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 forEachRemaining(Consumer<? super V> action) {
+            int i, hi, mc;
+            if (action == null)
+                throw new NullPointerException();
+            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 {
+                    if (p == null)
+                        p = tab[i++];
+                    else {
+                        Object x = p.get();
+                        V v = p.value;
+                        p = p.next;
+                        if (x != null)
+                            action.accept(v);
+                    }
+                } while (p != null || i < hi);
+            }
+            if (m.modCount != mc)
+                throw new ConcurrentModificationException();
+        }
+
+        public boolean tryAdvance(Consumer<? super V> action) {
+            int hi;
+            if (action == null)
+                throw new NullPointerException();
+            WeakHashMap.Entry<K,V>[] tab = map.table;
+            if (tab.length >= (hi = getFence()) && index >= 0) {
+                while (current != null || index < hi) {
+                    if (current == null)
+                        current = tab[index++];
+                    else {
+                        Object x = current.get();
+                        V v = current.value;
+                        current = current.next;
+                        if (x != null) {
+                            action.accept(v);
+                            if (map.modCount != expectedModCount)
+                                throw new ConcurrentModificationException();
+                            return true;
+                        }
+                    }
+                }
+            }
+            return false;
+        }
+
+        public int characteristics() {
+            return 0;
+        }
+    }
+
+    static final class EntrySpliterator<K,V>
+        extends WeakHashMapSpliterator<K,V>
+        implements Spliterator<Map.Entry<K,V>> {
+        EntrySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
+                       int expectedModCount) {
+            super(m, origin, fence, est, expectedModCount);
+        }
+
+        public EntrySpliterator<K,V> trySplit() {
+            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+            return (lo >= mid) ? null :
+                new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+                                          expectedModCount);
+        }
+
+
+        public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
+            int i, hi, mc;
+            if (action == null)
+                throw new NullPointerException();
+            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 {
+                    if (p == null)
+                        p = tab[i++];
+                    else {
+                        Object x = p.get();
+                        V v = p.value;
+                        p = p.next;
+                        if (x != null) {
+                            @SuppressWarnings("unchecked") K k =
+                                (K) WeakHashMap.unmaskNull(x);
+                            action.accept
+                                (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
+                        }
+                    }
+                } while (p != null || i < hi);
+            }
+            if (m.modCount != mc)
+                throw new ConcurrentModificationException();
+        }
+
+        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
+            int hi;
+            if (action == null)
+                throw new NullPointerException();
+            WeakHashMap.Entry<K,V>[] tab = map.table;
+            if (tab.length >= (hi = getFence()) && index >= 0) {
+                while (current != null || index < hi) {
+                    if (current == null)
+                        current = tab[index++];
+                    else {
+                        Object x = current.get();
+                        V v = current.value;
+                        current = current.next;
+                        if (x != null) {
+                            @SuppressWarnings("unchecked") K k =
+                                (K) WeakHashMap.unmaskNull(x);
+                            action.accept
+                                (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
+                            if (map.modCount != expectedModCount)
+                                throw new ConcurrentModificationException();
+                            return true;
+                        }
+                    }
+                }
+            }
+            return false;
+        }
+
+        public int characteristics() {
+            return Spliterator.DISTINCT;
+        }
+    }
+
 }
--- a/test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java	Wed Apr 17 14:39:04 2013 -0400
+++ b/test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java	Wed Apr 17 11:34:31 2013 +0200
@@ -184,6 +184,8 @@
 
                 @Override
                 public boolean tryAdvance(Consumer<? super Integer> action) {
+                    if (action == null)
+                        throw new NullPointerException();
                     if (it.hasNext()) {
                         action.accept(it.next());
                         return true;
@@ -193,7 +195,7 @@
                     }
                 }
             }
-            db.add("new Spliterators.AbstractAdvancingSpliterator()",
+            db.add("new Spliterators.AbstractSpliterator()",
                    () -> new SpliteratorFromIterator(exp.iterator(), exp.size()));
 
             // Collections
@@ -370,7 +372,28 @@
                 db.addCollection(c -> Collections.singletonList(exp.get(0)));
             }
 
-            // @@@ Collections.synchronized/unmodifiable/checked wrappers
+            // Collections.synchronized/unmodifiable/checked wrappers
+            db.addCollection(Collections::unmodifiableCollection);
+            db.addCollection(c -> Collections.unmodifiableSet(new HashSet<>(c)));
+            db.addCollection(c -> Collections.unmodifiableSortedSet(new TreeSet<>(c)));
+            db.addList(c -> Collections.unmodifiableList(new ArrayList<>(c)));
+            db.addMap(Collections::unmodifiableMap);
+            db.addMap(m -> Collections.unmodifiableSortedMap(new TreeMap<>(m)));
+
+            db.addCollection(Collections::synchronizedCollection);
+            db.addCollection(c -> Collections.synchronizedSet(new HashSet<>(c)));
+            db.addCollection(c -> Collections.synchronizedSortedSet(new TreeSet<>(c)));
+            db.addList(c -> Collections.synchronizedList(new ArrayList<>(c)));
+            db.addMap(Collections::synchronizedMap);
+            db.addMap(m -> Collections.synchronizedSortedMap(new TreeMap<>(m)));
+
+            db.addCollection(c -> Collections.checkedCollection(c, Integer.class));
+            db.addCollection(c -> Collections.checkedQueue(new ArrayDeque<>(c), Integer.class));
+            db.addCollection(c -> Collections.checkedSet(new HashSet<>(c), Integer.class));
+            db.addCollection(c -> Collections.checkedSortedSet(new TreeSet<>(c), Integer.class));
+            db.addList(c -> Collections.checkedList(new ArrayList<>(c), Integer.class));
+            db.addMap(c -> Collections.checkedMap(c, Integer.class, Integer.class));
+            db.addMap(m -> Collections.checkedSortedMap(new TreeMap<>(m), Integer.class, Integer.class));
 
             // Maps
 
@@ -402,6 +425,13 @@
 
     @Test(dataProvider = "Spliterator<Integer>")
     @SuppressWarnings({"unchecked", "rawtypes"})
+    public void testNullPointerException(String description, Collection exp, Supplier<Spliterator> s) {
+        executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining(null));
+        executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance(null));
+    }
+
+    @Test(dataProvider = "Spliterator<Integer>")
+    @SuppressWarnings({"unchecked", "rawtypes"})
     public void testForEach(String description, Collection exp, Supplier<Spliterator> s) {
         testForEach(exp, s, (Consumer<Object> b) -> b);
     }
@@ -507,6 +537,8 @@
 
                 @Override
                 public boolean tryAdvance(IntConsumer action) {
+                    if (action == null)
+                        throw new NullPointerException();
                     if (index < a.length) {
                         action.accept(a[index++]);
                         return true;
@@ -553,6 +585,12 @@
     }
 
     @Test(dataProvider = "Spliterator.OfInt")
+    public void testIntNullPointerException(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) {
+        executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining((IntConsumer) null));
+        executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance((IntConsumer) null));
+    }
+
+    @Test(dataProvider = "Spliterator.OfInt")
     public void testIntForEach(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) {
         testForEach(exp, s, intBoxingConsumer());
     }
@@ -652,6 +690,8 @@
 
                 @Override
                 public boolean tryAdvance(LongConsumer action) {
+                    if (action == null)
+                        throw new NullPointerException();
                     if (index < a.length) {
                         action.accept(a[index++]);
                         return true;
@@ -705,6 +745,12 @@
     }
 
     @Test(dataProvider = "Spliterator.OfLong")
+    public void testLongNullPointerException(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) {
+        executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining((LongConsumer) null));
+        executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance((LongConsumer) null));
+    }
+
+    @Test(dataProvider = "Spliterator.OfLong")
     public void testLongForEach(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) {
         testForEach(exp, s, longBoxingConsumer());
     }
@@ -804,6 +850,8 @@
 
                 @Override
                 public boolean tryAdvance(DoubleConsumer action) {
+                    if (action == null)
+                        throw new NullPointerException();
                     if (index < a.length) {
                         action.accept(a[index++]);
                         return true;
@@ -857,6 +905,12 @@
     }
 
     @Test(dataProvider = "Spliterator.OfDouble")
+    public void testDoubleNullPointerException(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) {
+        executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining((DoubleConsumer) null));
+        executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance((DoubleConsumer) null));
+    }
+
+    @Test(dataProvider = "Spliterator.OfDouble")
     public void testDoubleForEach(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) {
         testForEach(exp, s, doubleBoxingConsumer());
     }
@@ -1057,8 +1111,8 @@
     }
 
     private static <T, S extends Spliterator<T>> void visit(int depth, int curLevel,
-                              List<T> dest, S spliterator, UnaryOperator<Consumer<T>> boxingAdapter,
-                              int rootCharacteristics, boolean useTryAdvance) {
+                                                            List<T> dest, S spliterator, UnaryOperator<Consumer<T>> boxingAdapter,
+                                                            int rootCharacteristics, boolean useTryAdvance) {
         if (curLevel < depth) {
             long beforeSize = spliterator.getExactSizeIfKnown();
             Spliterator<T> split = spliterator.trySplit();
@@ -1187,13 +1241,13 @@
                 assertTrue(leftSplit.estimateSize() < parentEstimateSize,
                            String.format("Left split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
                 assertTrue(parentAndRightSplit.estimateSize() < parentEstimateSize,
-                            String.format("Right split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
+                           String.format("Right split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
             }
             else {
                 assertTrue(leftSplit.estimateSize() <= parentEstimateSize,
-                    String.format("Left split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
+                           String.format("Left split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
                 assertTrue(parentAndRightSplit.estimateSize() <= parentEstimateSize,
-                    String.format("Right split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
+                           String.format("Right split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
             }
 
             long leftSize = leftSplit.getExactSizeIfKnown();
@@ -1254,4 +1308,22 @@
         });
         return result;
     }
+
+    private void executeAndCatch(Class<? extends Exception> expected, Runnable r) {
+        Exception caught = null;
+        try {
+            r.run();
+        }
+        catch (Exception e) {
+            caught = e;
+        }
+
+        assertNotNull(caught,
+                      String.format("No Exception was thrown, expected an Exception of %s to be thrown",
+                                    expected.getName()));
+        assertTrue(expected.isInstance(caught),
+                   String.format("Exception thrown %s not an instance of %s",
+                                 caught.getClass().getName(), expected.getName()));
+    }
+
 }