--- jsr166/src/main/java/util/PriorityQueue.java 2016/11/29 18:11:28 1.112 +++ jsr166/src/main/java/util/PriorityQueue.java 2018/05/06 02:08:36 1.122 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2003, 2018, 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 @@ -26,6 +26,7 @@ package java.util; import java.util.function.Consumer; +import jdk.internal.misc.SharedSecrets; /** * An unbounded priority {@linkplain Queue queue} based on a priority heap. @@ -73,7 +74,7 @@ import java.util.function.Consumer; * ({@code peek}, {@code element}, and {@code size}). * *

This class is a member of the - * + * * Java Collections Framework. * * @since 1.5 @@ -522,6 +523,8 @@ public class PriorityQueue extends Ab */ private int expectedModCount = modCount; + Itr() {} // prevent access constructor creation + public boolean hasNext() { return cursor < size || (forgetMeNot != null && !forgetMeNot.isEmpty()); @@ -631,7 +634,7 @@ public class PriorityQueue extends Ab * promoting x up the tree until it is greater than or equal to * its parent, or is the root. * - * To simplify and speed up coercions and comparisons. the + * To simplify and speed up coercions and comparisons, the * Comparable and Comparator versions are separated into different * methods that are otherwise identical. (Similarly for siftDown.) * @@ -731,8 +734,14 @@ public class PriorityQueue extends Ab */ @SuppressWarnings("unchecked") private void heapify() { - for (int i = (size >>> 1) - 1; i >= 0; i--) - siftDown(i, (E) queue[i]); + final Object[] es = queue; + int i = (size >>> 1) - 1; + if (comparator == null) + for (; i >= 0; i--) + siftDownComparable(i, (E) es[i]); + else + for (; i >= 0; i--) + siftDownUsingComparator(i, (E) es[i]); } /** @@ -787,6 +796,7 @@ public class PriorityQueue extends Ab // Read in (and discard) array length s.readInt(); + SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size); queue = new Object[size]; // Read in all elements. @@ -813,23 +823,16 @@ public class PriorityQueue extends Ab * @since 1.8 */ public final Spliterator spliterator() { - return new PriorityQueueSpliterator<>(this, 0, -1, 0); + return new PriorityQueueSpliterator(0, -1, 0); } - static final class PriorityQueueSpliterator implements Spliterator { - /* - * This is very similar to ArrayList Spliterator, except for - * extra null checks. - */ - private final PriorityQueue pq; + final class PriorityQueueSpliterator implements Spliterator { 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 pq, int origin, int fence, - int expectedModCount) { - this.pq = pq; + PriorityQueueSpliterator(int origin, int fence, int expectedModCount) { this.index = origin; this.fence = fence; this.expectedModCount = expectedModCount; @@ -838,72 +841,72 @@ public class PriorityQueue extends Ab private int getFence() { // initialize fence to size on first use int hi; if ((hi = fence) < 0) { - expectedModCount = pq.modCount; - hi = fence = pq.size; + expectedModCount = modCount; + hi = fence = size; } return hi; } - public PriorityQueueSpliterator trySplit() { + public PriorityQueueSpliterator trySplit() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid) ? null : - new PriorityQueueSpliterator<>(pq, lo, index = mid, - expectedModCount); + new PriorityQueueSpliterator(lo, index = mid, expectedModCount); } @SuppressWarnings("unchecked") public void forEachRemaining(Consumer action) { - int i, hi, mc; // hoist accesses and checks from loop - PriorityQueue 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; - } - } + if (fence < 0) { fence = size; expectedModCount = modCount; } + final Object[] a = queue; + int i, hi; E e; + for (i = index, index = hi = fence; i < hi; i++) { + if ((e = (E) a[i]) == null) + break; // must be CME + action.accept(e); } - throw new ConcurrentModificationException(); + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); } + @SuppressWarnings("unchecked") public boolean tryAdvance(Consumer 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) + if (fence < 0) { fence = size; expectedModCount = modCount; } + int i; + if ((i = index) < fence) { + index = i + 1; + E e; + if ((e = (E) queue[i]) == null + || modCount != expectedModCount) throw new ConcurrentModificationException(); action.accept(e); - if (pq.modCount != expectedModCount) - throw new ConcurrentModificationException(); return true; } return false; } public long estimateSize() { - return (long) (getFence() - index); + return getFence() - index; } public int characteristics() { return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL; } } + + /** + * @throws NullPointerException {@inheritDoc} + */ + @SuppressWarnings("unchecked") + public void forEach(Consumer action) { + Objects.requireNonNull(action); + final int expectedModCount = modCount; + final Object[] es = queue; + for (int i = 0, n = size; i < n; i++) + action.accept((E) es[i]); + if (expectedModCount != modCount) + throw new ConcurrentModificationException(); + } }