ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/PriorityQueue.java

Comparing jsr166/src/main/java/util/PriorityQueue.java (file contents):
Revision 1.126 by jsr166, Sun May 6 23:07:56 2018 UTC vs.
Revision 1.131 by jsr166, Wed May 22 17:36:58 2019 UTC

#	Line 1 | Line 1
1		/*
2	<	* Copyright (c) 2003, 2018, Oracle and/or its affiliates. All rights reserved.
2	>	* Copyright (c) 2003, 2019, Oracle and/or its affiliates. All rights reserved.
3		* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5		* This code is free software; you can redistribute it and/or modify it
#	Line 26 | Line 26
26		package java.util;
27
28		import java.util.function.Consumer;
29	<	import jdk.internal.misc.SharedSecrets;
29	>	import java.util.function.Predicate;
30	>	// OPENJDK import jdk.internal.access.SharedSecrets;
31	>	import jdk.internal.util.ArraysSupport;
32
33		/**
34		* An unbounded priority {@linkplain Queue queue} based on a priority heap.
#	Line 74 | Line 76 | import jdk.internal.misc.SharedSecrets;
76		* ({@code peek}, {@code element}, and {@code size}).
77		*
78		* <p>This class is a member of the
79	<	* <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework">
79	>	* <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
80		* Java Collections Framework</a>.
81		*
82		* @since 1.5
#	Line 281 | Line 283 | public class PriorityQueue<E> extends Ab
283		}
284
285		/**
284	–	* The maximum size of array to allocate.
285	–	* Some VMs reserve some header words in an array.
286	–	* Attempts to allocate larger arrays may result in
287	–	* OutOfMemoryError: Requested array size exceeds VM limit
288	–	*/
289	–	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
290	–
291	–	/**
286		* Increases the capacity of the array.
287		*
288		* @param minCapacity the desired minimum capacity
#	Line 296 | Line 290 | public class PriorityQueue<E> extends Ab
290		private void grow(int minCapacity) {
291		int oldCapacity = queue.length;
292		// Double size if small; else grow by 50%
293	<	int newCapacity = oldCapacity + ((oldCapacity < 64) ?
294	<	(oldCapacity + 2) :
295	<	(oldCapacity >> 1));
296	<	// overflow-conscious code
303	<	if (newCapacity - MAX_ARRAY_SIZE > 0)
304	<	newCapacity = hugeCapacity(minCapacity);
293	>	int newCapacity = ArraysSupport.newLength(oldCapacity,
294	>	minCapacity - oldCapacity, /* minimum growth */
295	>	oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
296	>	/* preferred growth */);
297		queue = Arrays.copyOf(queue, newCapacity);
298		}
299
308	–	private static int hugeCapacity(int minCapacity) {
309	–	if (minCapacity < 0) // overflow
310	–	throw new OutOfMemoryError();
311	–	return (minCapacity > MAX_ARRAY_SIZE) ?
312	–	Integer.MAX_VALUE :
313	–	MAX_ARRAY_SIZE;
314	–	}
315	–
300		/**
301		* Inserts the specified element into this priority queue.
302		*
#	Line 623 | Line 607 | public class PriorityQueue<E> extends Ab
607		if (s == i) // removed last element
608		es[i] = null;
609		else {
610	<	E moved = (E) queue[s];
610	>	E moved = (E) es[s];
611		es[s] = null;
612		siftDown(i, moved);
613		if (es[i] == moved) {
#	Line 802 | Line 786 | public class PriorityQueue<E> extends Ab
786		// Read in (and discard) array length
787		s.readInt();
788
789	<	SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
789	>	jsr166.Platform.checkArray(s, Object[].class, size);
790		final Object[] es = queue = new Object[Math.max(size, 1)];
791
792		// Read in all elements.
#	Line 901 | Line 885 | public class PriorityQueue<E> extends Ab
885		}
886
887		/**
888	+	* @throws NullPointerException {@inheritDoc}
889	+	*/
890	+	public boolean removeIf(Predicate<? super E> filter) {
891	+	Objects.requireNonNull(filter);
892	+	return bulkRemove(filter);
893	+	}
894	+
895	+	/**
896	+	* @throws NullPointerException {@inheritDoc}
897	+	*/
898	+	public boolean removeAll(Collection<?> c) {
899	+	Objects.requireNonNull(c);
900	+	return bulkRemove(e -> c.contains(e));
901	+	}
902	+
903	+	/**
904	+	* @throws NullPointerException {@inheritDoc}
905	+	*/
906	+	public boolean retainAll(Collection<?> c) {
907	+	Objects.requireNonNull(c);
908	+	return bulkRemove(e -> !c.contains(e));
909	+	}
910	+
911	+	// A tiny bit set implementation
912	+
913	+	private static long[] nBits(int n) {
914	+	return new long[((n - 1) >> 6) + 1];
915	+	}
916	+	private static void setBit(long[] bits, int i) {
917	+	bits[i >> 6] |= 1L << i;
918	+	}
919	+	private static boolean isClear(long[] bits, int i) {
920	+	return (bits[i >> 6] & (1L << i)) == 0;
921	+	}
922	+
923	+	/** Implementation of bulk remove methods. */
924	+	private boolean bulkRemove(Predicate<? super E> filter) {
925	+	final int expectedModCount = ++modCount;
926	+	final Object[] es = queue;
927	+	final int end = size;
928	+	int i;
929	+	// Optimize for initial run of survivors
930	+	for (i = 0; i < end && !filter.test((E) es[i]); i++)
931	+	;
932	+	if (i >= end) {
933	+	if (modCount != expectedModCount)
934	+	throw new ConcurrentModificationException();
935	+	return false;
936	+	}
937	+	// Tolerate predicates that reentrantly access the collection for
938	+	// read (but writers still get CME), so traverse once to find
939	+	// elements to delete, a second pass to physically expunge.
940	+	final int beg = i;
941	+	final long[] deathRow = nBits(end - beg);
942	+	deathRow[0] = 1L;   // set bit 0
943	+	for (i = beg + 1; i < end; i++)
944	+	if (filter.test((E) es[i]))
945	+	setBit(deathRow, i - beg);
946	+	if (modCount != expectedModCount)
947	+	throw new ConcurrentModificationException();
948	+	int w = beg;
949	+	for (i = beg; i < end; i++)
950	+	if (isClear(deathRow, i - beg))
951	+	es[w++] = es[i];
952	+	for (i = size = w; i < end; i++)
953	+	es[i] = null;
954	+	heapify();
955	+	return true;
956	+	}
957	+
958	+	/**
959		* @throws NullPointerException {@inheritDoc}
960		*/
961		public void forEach(Consumer<? super E> action) {

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines