--- 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 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 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 cmp = comparator; - if (cmp == null) + final Comparator 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 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 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 action) {