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.124 by jsr166, Sun May 6 19:35:51 2018 UTC vs.
Revision 1.133 by jsr166, Thu Oct 10 16:53:08 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 108 | Line 111 | public class PriorityQueue<E> extends Ab
111       * The comparator, or null if priority queue uses elements'
112       * natural ordering.
113       */
114 +    @SuppressWarnings("serial") // Conditionally serializable
115      private final Comparator<? super E> comparator;
116  
117      /**
# Line 242 | Line 246 | public class PriorityQueue<E> extends Ab
246          initElementsFromCollection(c);
247      }
248  
249 +    /** Ensures that queue[0] exists, helping peek() and poll(). */
250 +    private static Object[] ensureNonEmpty(Object[] es) {
251 +        return (es.length > 0) ? es : new Object[1];
252 +    }
253 +
254      private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
255          if (c.getClass() == PriorityQueue.class) {
256 <            this.queue = c.toArray();
256 >            this.queue = ensureNonEmpty(c.toArray());
257              this.size = c.size();
258          } else {
259              initFromCollection(c);
# Line 261 | Line 270 | public class PriorityQueue<E> extends Ab
270              for (Object e : es)
271                  if (e == null)
272                      throw new NullPointerException();
273 <        this.queue = es;
273 >        this.queue = ensureNonEmpty(es);
274          this.size = len;
275      }
276  
# Line 276 | Line 285 | public class PriorityQueue<E> extends Ab
285      }
286  
287      /**
279 –     * The maximum size of array to allocate.
280 –     * Some VMs reserve some header words in an array.
281 –     * Attempts to allocate larger arrays may result in
282 –     * OutOfMemoryError: Requested array size exceeds VM limit
283 –     */
284 –    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
285 –
286 –    /**
288       * Increases the capacity of the array.
289       *
290       * @param minCapacity the desired minimum capacity
# Line 291 | Line 292 | public class PriorityQueue<E> extends Ab
292      private void grow(int minCapacity) {
293          int oldCapacity = queue.length;
294          // Double size if small; else grow by 50%
295 <        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
296 <                                         (oldCapacity + 2) :
297 <                                         (oldCapacity >> 1));
298 <        // overflow-conscious code
298 <        if (newCapacity - MAX_ARRAY_SIZE > 0)
299 <            newCapacity = hugeCapacity(minCapacity);
295 >        int newCapacity = ArraysSupport.newLength(oldCapacity,
296 >                minCapacity - oldCapacity, /* minimum growth */
297 >                oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
298 >                                           /* preferred growth */);
299          queue = Arrays.copyOf(queue, newCapacity);
300      }
301  
303 –    private static int hugeCapacity(int minCapacity) {
304 –        if (minCapacity < 0) // overflow
305 –            throw new OutOfMemoryError();
306 –        return (minCapacity > MAX_ARRAY_SIZE) ?
307 –            Integer.MAX_VALUE :
308 –            MAX_ARRAY_SIZE;
309 –    }
310 –
302      /**
303       * Inserts the specified element into this priority queue.
304       *
# Line 343 | Line 334 | public class PriorityQueue<E> extends Ab
334      }
335  
336      public E peek() {
337 <        return (size == 0) ? null : (E) queue[0];
337 >        return (E) queue[0];
338      }
339  
340      private int indexOf(Object o) {
# Line 579 | Line 570 | public class PriorityQueue<E> extends Ab
570      }
571  
572      public E poll() {
573 <        if (size == 0)
574 <            return null;
575 <        int s = --size;
576 <        modCount++;
577 <        E result = (E) queue[0];
578 <        E x = (E) queue[s];
579 <        queue[s] = null;
580 <        if (s != 0)
581 <            siftDown(0, x);
573 >        final Object[] es;
574 >        final E result;
575 >
576 >        if ((result = (E) ((es = queue)[0])) != null) {
577 >            modCount++;
578 >            final int n;
579 >            final E x = (E) es[(n = --size)];
580 >            es[n] = null;
581 >            if (n > 0) {
582 >                final Comparator<? super E> cmp;
583 >                if ((cmp = comparator) == null)
584 >                    siftDownComparable(0, x, es, n);
585 >                else
586 >                    siftDownUsingComparator(0, x, es, n, cmp);
587 >            }
588 >        }
589          return result;
590      }
591  
# Line 605 | Line 603 | public class PriorityQueue<E> extends Ab
603       */
604      E removeAt(int i) {
605          // assert i >= 0 && i < size;
606 +        final Object[] es = queue;
607          modCount++;
608          int s = --size;
609          if (s == i) // removed last element
610 <            queue[i] = null;
610 >            es[i] = null;
611          else {
612 <            E moved = (E) queue[s];
613 <            queue[s] = null;
612 >            E moved = (E) es[s];
613 >            es[s] = null;
614              siftDown(i, moved);
615 <            if (queue[i] == moved) {
615 >            if (es[i] == moved) {
616                  siftUp(i, moved);
617 <                if (queue[i] != moved)
617 >                if (es[i] != moved)
618                      return moved;
619              }
620          }
# Line 727 | Line 726 | public class PriorityQueue<E> extends Ab
726      private void heapify() {
727          final Object[] es = queue;
728          int n = size, i = (n >>> 1) - 1;
729 <        Comparator<? super E> cmp = comparator;
730 <        if (cmp == null)
729 >        final Comparator<? super E> cmp;
730 >        if ((cmp = comparator) == null)
731              for (; i >= 0; i--)
732                  siftDownComparable(i, (E) es[i], es, n);
733          else
# Line 758 | Line 757 | public class PriorityQueue<E> extends Ab
757       *             emitted (int), followed by all of its elements
758       *             (each an {@code Object}) in the proper order.
759       */
760 +    // OPENJDK @java.io.Serial
761      private void writeObject(java.io.ObjectOutputStream s)
762          throws java.io.IOException {
763          // Write out element count, and any hidden stuff
# Line 781 | Line 781 | public class PriorityQueue<E> extends Ab
781       *         could not be found
782       * @throws java.io.IOException if an I/O error occurs
783       */
784 +    // OPENJDK @java.io.Serial
785      private void readObject(java.io.ObjectInputStream s)
786          throws java.io.IOException, ClassNotFoundException {
787          // Read in size, and any hidden stuff
# Line 789 | Line 790 | public class PriorityQueue<E> extends Ab
790          // Read in (and discard) array length
791          s.readInt();
792  
793 <        SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
794 <        queue = new Object[size];
793 >        jsr166.Platform.checkArray(s, Object[].class, size);
794 >        final Object[] es = queue = new Object[Math.max(size, 1)];
795  
796          // Read in all elements.
796 –        final Object[] es = queue;
797          for (int i = 0, n = size; i < n; i++)
798              es[i] = s.readObject();
799  
# Line 889 | Line 889 | public class PriorityQueue<E> extends Ab
889      }
890  
891      /**
892 +     * @throws NullPointerException {@inheritDoc}
893 +     */
894 +    public boolean removeIf(Predicate<? super E> filter) {
895 +        Objects.requireNonNull(filter);
896 +        return bulkRemove(filter);
897 +    }
898 +
899 +    /**
900 +     * @throws NullPointerException {@inheritDoc}
901 +     */
902 +    public boolean removeAll(Collection<?> c) {
903 +        Objects.requireNonNull(c);
904 +        return bulkRemove(e -> c.contains(e));
905 +    }
906 +
907 +    /**
908 +     * @throws NullPointerException {@inheritDoc}
909 +     */
910 +    public boolean retainAll(Collection<?> c) {
911 +        Objects.requireNonNull(c);
912 +        return bulkRemove(e -> !c.contains(e));
913 +    }
914 +
915 +    // A tiny bit set implementation
916 +
917 +    private static long[] nBits(int n) {
918 +        return new long[((n - 1) >> 6) + 1];
919 +    }
920 +    private static void setBit(long[] bits, int i) {
921 +        bits[i >> 6] |= 1L << i;
922 +    }
923 +    private static boolean isClear(long[] bits, int i) {
924 +        return (bits[i >> 6] & (1L << i)) == 0;
925 +    }
926 +
927 +    /** Implementation of bulk remove methods. */
928 +    private boolean bulkRemove(Predicate<? super E> filter) {
929 +        final int expectedModCount = ++modCount;
930 +        final Object[] es = queue;
931 +        final int end = size;
932 +        int i;
933 +        // Optimize for initial run of survivors
934 +        for (i = 0; i < end && !filter.test((E) es[i]); i++)
935 +            ;
936 +        if (i >= end) {
937 +            if (modCount != expectedModCount)
938 +                throw new ConcurrentModificationException();
939 +            return false;
940 +        }
941 +        // Tolerate predicates that reentrantly access the collection for
942 +        // read (but writers still get CME), so traverse once to find
943 +        // elements to delete, a second pass to physically expunge.
944 +        final int beg = i;
945 +        final long[] deathRow = nBits(end - beg);
946 +        deathRow[0] = 1L;   // set bit 0
947 +        for (i = beg + 1; i < end; i++)
948 +            if (filter.test((E) es[i]))
949 +                setBit(deathRow, i - beg);
950 +        if (modCount != expectedModCount)
951 +            throw new ConcurrentModificationException();
952 +        int w = beg;
953 +        for (i = beg; i < end; i++)
954 +            if (isClear(deathRow, i - beg))
955 +                es[w++] = es[i];
956 +        for (i = size = w; i < end; i++)
957 +            es[i] = null;
958 +        heapify();
959 +        return true;
960 +    }
961 +
962 +    /**
963       * @throws NullPointerException {@inheritDoc}
964       */
965      public void forEach(Consumer<? super E> action) {

Diff Legend

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