ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/PriorityQueue.java
(Generate patch)

Comparing jsr166/src/main/java/util/PriorityQueue.java (file contents):
Revision 1.127 by jsr166, Sun May 6 23:09:28 2018 UTC vs.
Revision 1.132 by jsr166, Fri Aug 30 18:05:39 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 85 | Line 87 | import jdk.internal.misc.SharedSecrets;
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;
# Line 281 | Line 284 | public class PriorityQueue<E> extends Ab
284      }
285  
286      /**
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 –    /**
287       * Increases the capacity of the array.
288       *
289       * @param minCapacity the desired minimum capacity
# Line 296 | Line 291 | public class PriorityQueue<E> extends Ab
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
303 <        if (newCapacity - MAX_ARRAY_SIZE > 0)
304 <            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  
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 –
301      /**
302       * Inserts the specified element into this priority queue.
303       *
# Line 771 | Line 756 | public class PriorityQueue<E> extends Ab
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
# Line 794 | Line 780 | public class PriorityQueue<E> extends Ab
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
# Line 802 | Line 789 | public class PriorityQueue<E> extends Ab
789          // Read in (and discard) array length
790          s.readInt();
791  
792 <        SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
792 >        jsr166.Platform.checkArray(s, Object[].class, size);
793          final Object[] es = queue = new Object[Math.max(size, 1)];
794  
795          // Read in all elements.
# Line 901 | Line 888 | public class PriorityQueue<E> extends Ab
888      }
889  
890      /**
891 +     * @throws NullPointerException {@inheritDoc}
892 +     */
893 +    public boolean removeIf(Predicate<? super E> filter) {
894 +        Objects.requireNonNull(filter);
895 +        return bulkRemove(filter);
896 +    }
897 +
898 +    /**
899 +     * @throws NullPointerException {@inheritDoc}
900 +     */
901 +    public boolean removeAll(Collection<?> c) {
902 +        Objects.requireNonNull(c);
903 +        return bulkRemove(e -> c.contains(e));
904 +    }
905 +
906 +    /**
907 +     * @throws NullPointerException {@inheritDoc}
908 +     */
909 +    public boolean retainAll(Collection<?> c) {
910 +        Objects.requireNonNull(c);
911 +        return bulkRemove(e -> !c.contains(e));
912 +    }
913 +
914 +    // A tiny bit set implementation
915 +
916 +    private static long[] nBits(int n) {
917 +        return new long[((n - 1) >> 6) + 1];
918 +    }
919 +    private static void setBit(long[] bits, int i) {
920 +        bits[i >> 6] |= 1L << i;
921 +    }
922 +    private static boolean isClear(long[] bits, int i) {
923 +        return (bits[i >> 6] & (1L << i)) == 0;
924 +    }
925 +
926 +    /** Implementation of bulk remove methods. */
927 +    private boolean bulkRemove(Predicate<? super E> filter) {
928 +        final int expectedModCount = ++modCount;
929 +        final Object[] es = queue;
930 +        final int end = size;
931 +        int i;
932 +        // Optimize for initial run of survivors
933 +        for (i = 0; i < end && !filter.test((E) es[i]); i++)
934 +            ;
935 +        if (i >= end) {
936 +            if (modCount != expectedModCount)
937 +                throw new ConcurrentModificationException();
938 +            return false;
939 +        }
940 +        // Tolerate predicates that reentrantly access the collection for
941 +        // read (but writers still get CME), so traverse once to find
942 +        // elements to delete, a second pass to physically expunge.
943 +        final int beg = i;
944 +        final long[] deathRow = nBits(end - beg);
945 +        deathRow[0] = 1L;   // set bit 0
946 +        for (i = beg + 1; i < end; i++)
947 +            if (filter.test((E) es[i]))
948 +                setBit(deathRow, i - beg);
949 +        if (modCount != expectedModCount)
950 +            throw new ConcurrentModificationException();
951 +        int w = beg;
952 +        for (i = beg; i < end; i++)
953 +            if (isClear(deathRow, i - beg))
954 +                es[w++] = es[i];
955 +        for (i = size = w; i < end; i++)
956 +            es[i] = null;
957 +        heapify();
958 +        return true;
959 +    }
960 +
961 +    /**
962       * @throws NullPointerException {@inheritDoc}
963       */
964      public void forEach(Consumer<? super E> action) {

Diff Legend

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