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 |
28 |
|
import java.util.function.Consumer; |
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. |
87 |
|
public class PriorityQueue<E> extends AbstractQueue<E> |
88 |
|
implements java.io.Serializable { |
89 |
|
|
90 |
+ |
// OPENJDK @java.io.Serial |
91 |
|
private static final long serialVersionUID = -7720805057305804111L; |
92 |
|
|
93 |
|
private static final int DEFAULT_INITIAL_CAPACITY = 11; |
284 |
|
} |
285 |
|
|
286 |
|
/** |
285 |
– |
* The maximum size of array to allocate. |
286 |
– |
* Some VMs reserve some header words in an array. |
287 |
– |
* Attempts to allocate larger arrays may result in |
288 |
– |
* OutOfMemoryError: Requested array size exceeds VM limit |
289 |
– |
*/ |
290 |
– |
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; |
291 |
– |
|
292 |
– |
/** |
287 |
|
* Increases the capacity of the array. |
288 |
|
* |
289 |
|
* @param minCapacity the desired minimum capacity |
291 |
|
private void grow(int minCapacity) { |
292 |
|
int oldCapacity = queue.length; |
293 |
|
// Double size if small; else grow by 50% |
294 |
< |
int newCapacity = oldCapacity + ((oldCapacity < 64) ? |
295 |
< |
(oldCapacity + 2) : |
296 |
< |
(oldCapacity >> 1)); |
297 |
< |
// overflow-conscious code |
304 |
< |
if (newCapacity - MAX_ARRAY_SIZE > 0) |
305 |
< |
newCapacity = hugeCapacity(minCapacity); |
294 |
> |
int newCapacity = ArraysSupport.newLength(oldCapacity, |
295 |
> |
minCapacity - oldCapacity, /* minimum growth */ |
296 |
> |
oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1 |
297 |
> |
/* preferred growth */); |
298 |
|
queue = Arrays.copyOf(queue, newCapacity); |
299 |
|
} |
300 |
|
|
309 |
– |
private static int hugeCapacity(int minCapacity) { |
310 |
– |
if (minCapacity < 0) // overflow |
311 |
– |
throw new OutOfMemoryError(); |
312 |
– |
return (minCapacity > MAX_ARRAY_SIZE) ? |
313 |
– |
Integer.MAX_VALUE : |
314 |
– |
MAX_ARRAY_SIZE; |
315 |
– |
} |
316 |
– |
|
301 |
|
/** |
302 |
|
* Inserts the specified element into this priority queue. |
303 |
|
* |
756 |
|
* emitted (int), followed by all of its elements |
757 |
|
* (each an {@code Object}) in the proper order. |
758 |
|
*/ |
759 |
+ |
// OPENJDK @java.io.Serial |
760 |
|
private void writeObject(java.io.ObjectOutputStream s) |
761 |
|
throws java.io.IOException { |
762 |
|
// Write out element count, and any hidden stuff |
780 |
|
* could not be found |
781 |
|
* @throws java.io.IOException if an I/O error occurs |
782 |
|
*/ |
783 |
+ |
// OPENJDK @java.io.Serial |
784 |
|
private void readObject(java.io.ObjectInputStream s) |
785 |
|
throws java.io.IOException, ClassNotFoundException { |
786 |
|
// Read in size, and any hidden stuff |