--- jsr166/src/main/java/util/PriorityQueue.java 2018/05/06 19:35:51 1.124
+++ jsr166/src/main/java/util/PriorityQueue.java 2019/05/22 17:36:58 1.131
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2003, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2003, 2019, 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,7 +26,9 @@
package java.util;
import java.util.function.Consumer;
-import jdk.internal.misc.SharedSecrets;
+import java.util.function.Predicate;
+// OPENJDK import jdk.internal.access.SharedSecrets;
+import jdk.internal.util.ArraysSupport;
/**
* An unbounded priority {@linkplain Queue queue} based on a priority heap.
@@ -74,7 +76,7 @@ import jdk.internal.misc.SharedSecrets;
* ({@code peek}, {@code element}, and {@code size}).
*
*
This class is a member of the
- *
+ *
* Java Collections Framework.
*
* @since 1.5
@@ -242,9 +244,14 @@ public class PriorityQueue extends Ab
initElementsFromCollection(c);
}
+ /** Ensures that queue[0] exists, helping peek() and poll(). */
+ private static Object[] ensureNonEmpty(Object[] es) {
+ return (es.length > 0) ? es : new Object[1];
+ }
+
private void initFromPriorityQueue(PriorityQueue extends E> c) {
if (c.getClass() == PriorityQueue.class) {
- this.queue = c.toArray();
+ this.queue = ensureNonEmpty(c.toArray());
this.size = c.size();
} else {
initFromCollection(c);
@@ -261,7 +268,7 @@ public class PriorityQueue extends Ab
for (Object e : es)
if (e == null)
throw new NullPointerException();
- this.queue = es;
+ this.queue = ensureNonEmpty(es);
this.size = len;
}
@@ -276,14 +283,6 @@ public class PriorityQueue extends Ab
}
/**
- * The maximum size of array to allocate.
- * Some VMs reserve some header words in an array.
- * Attempts to allocate larger arrays may result in
- * OutOfMemoryError: Requested array size exceeds VM limit
- */
- private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
-
- /**
* Increases the capacity of the array.
*
* @param minCapacity the desired minimum capacity
@@ -291,23 +290,13 @@ public class PriorityQueue extends Ab
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
- int newCapacity = oldCapacity + ((oldCapacity < 64) ?
- (oldCapacity + 2) :
- (oldCapacity >> 1));
- // overflow-conscious code
- if (newCapacity - MAX_ARRAY_SIZE > 0)
- newCapacity = hugeCapacity(minCapacity);
+ int newCapacity = ArraysSupport.newLength(oldCapacity,
+ minCapacity - oldCapacity, /* minimum growth */
+ oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
+ /* preferred growth */);
queue = Arrays.copyOf(queue, newCapacity);
}
- private static int hugeCapacity(int minCapacity) {
- if (minCapacity < 0) // overflow
- throw new OutOfMemoryError();
- return (minCapacity > MAX_ARRAY_SIZE) ?
- Integer.MAX_VALUE :
- MAX_ARRAY_SIZE;
- }
-
/**
* Inserts the specified element into this priority queue.
*
@@ -343,7 +332,7 @@ public class PriorityQueue extends Ab
}
public E peek() {
- return (size == 0) ? null : (E) queue[0];
+ return (E) queue[0];
}
private int indexOf(Object o) {
@@ -579,15 +568,22 @@ public class PriorityQueue extends Ab
}
public E poll() {
- if (size == 0)
- return null;
- int s = --size;
- modCount++;
- E result = (E) queue[0];
- E x = (E) queue[s];
- queue[s] = null;
- if (s != 0)
- siftDown(0, x);
+ final Object[] es;
+ final E result;
+
+ if ((result = (E) ((es = queue)[0])) != null) {
+ modCount++;
+ final int n;
+ final E x = (E) es[(n = --size)];
+ es[n] = null;
+ if (n > 0) {
+ final Comparator super E> cmp;
+ if ((cmp = comparator) == null)
+ siftDownComparable(0, x, es, n);
+ else
+ siftDownUsingComparator(0, x, es, n, cmp);
+ }
+ }
return result;
}
@@ -605,17 +601,18 @@ public class PriorityQueue extends Ab
*/
E removeAt(int i) {
// assert i >= 0 && i < size;
+ final Object[] es = queue;
modCount++;
int s = --size;
if (s == i) // removed last element
- queue[i] = null;
+ es[i] = null;
else {
- E moved = (E) queue[s];
- queue[s] = null;
+ E moved = (E) es[s];
+ es[s] = null;
siftDown(i, moved);
- if (queue[i] == moved) {
+ if (es[i] == moved) {
siftUp(i, moved);
- if (queue[i] != moved)
+ if (es[i] != moved)
return moved;
}
}
@@ -727,8 +724,8 @@ public class PriorityQueue extends Ab
private void heapify() {
final Object[] es = queue;
int n = size, i = (n >>> 1) - 1;
- Comparator super E> cmp = comparator;
- if (cmp == null)
+ final Comparator super E> cmp;
+ if ((cmp = comparator) == null)
for (; i >= 0; i--)
siftDownComparable(i, (E) es[i], es, n);
else
@@ -789,11 +786,10 @@ public class PriorityQueue extends Ab
// Read in (and discard) array length
s.readInt();
- SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
- queue = new Object[size];
+ jsr166.Platform.checkArray(s, Object[].class, size);
+ final Object[] es = queue = new Object[Math.max(size, 1)];
// Read in all elements.
- final Object[] es = queue;
for (int i = 0, n = size; i < n; i++)
es[i] = s.readObject();
@@ -889,6 +885,77 @@ public class PriorityQueue extends Ab
}
/**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean removeIf(Predicate super E> filter) {
+ Objects.requireNonNull(filter);
+ return bulkRemove(filter);
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean removeAll(Collection> c) {
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> c.contains(e));
+ }
+
+ /**
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean retainAll(Collection> c) {
+ Objects.requireNonNull(c);
+ return bulkRemove(e -> !c.contains(e));
+ }
+
+ // A tiny bit set implementation
+
+ private static long[] nBits(int n) {
+ return new long[((n - 1) >> 6) + 1];
+ }
+ private static void setBit(long[] bits, int i) {
+ bits[i >> 6] |= 1L << i;
+ }
+ private static boolean isClear(long[] bits, int i) {
+ return (bits[i >> 6] & (1L << i)) == 0;
+ }
+
+ /** Implementation of bulk remove methods. */
+ private boolean bulkRemove(Predicate super E> filter) {
+ final int expectedModCount = ++modCount;
+ final Object[] es = queue;
+ final int end = size;
+ int i;
+ // Optimize for initial run of survivors
+ for (i = 0; i < end && !filter.test((E) es[i]); i++)
+ ;
+ if (i >= end) {
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return false;
+ }
+ // Tolerate predicates that reentrantly access the collection for
+ // read (but writers still get CME), so traverse once to find
+ // elements to delete, a second pass to physically expunge.
+ final int beg = i;
+ final long[] deathRow = nBits(end - beg);
+ deathRow[0] = 1L; // set bit 0
+ for (i = beg + 1; i < end; i++)
+ if (filter.test((E) es[i]))
+ setBit(deathRow, i - beg);
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ int w = beg;
+ for (i = beg; i < end; i++)
+ if (isClear(deathRow, i - beg))
+ es[w++] = es[i];
+ for (i = size = w; i < end; i++)
+ es[i] = null;
+ heapify();
+ return true;
+ }
+
+ /**
* @throws NullPointerException {@inheritDoc}
*/
public void forEach(Consumer super E> action) {