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

Comparing jsr166/src/main/java/util/concurrent/PriorityBlockingQueue.java (file contents):
Revision 1.133 by jsr166, Sun May 6 16:26:03 2018 UTC vs.
Revision 1.134 by jsr166, Sun May 6 19:35:51 2018 UTC

# Line 235 | Line 235 | public class PriorityBlockingQueue<E> ex
235              if (pq.getClass() == PriorityBlockingQueue.class) // exact match
236                  heapify = false;
237          }
238 <        Object[] a = c.toArray();
239 <        int n = a.length;
238 >        Object[] es = c.toArray();
239 >        int n = es.length;
240          // If c.toArray incorrectly doesn't return Object[], copy it.
241 <        if (a.getClass() != Object[].class)
242 <            a = Arrays.copyOf(a, n, Object[].class);
241 >        if (es.getClass() != Object[].class)
242 >            es = Arrays.copyOf(es, n, Object[].class);
243          if (screen && (n == 1 || this.comparator != null)) {
244 <            for (Object elt : a)
245 <                if (elt == null)
244 >            for (Object e : es)
245 >                if (e == null)
246                      throw new NullPointerException();
247          }
248 <        this.queue = a;
248 >        this.queue = es;
249          this.size = n;
250          if (heapify)
251              heapify();
# Line 294 | Line 294 | public class PriorityBlockingQueue<E> ex
294       * Mechanics for poll().  Call only while holding lock.
295       */
296      private E dequeue() {
297 +        // assert lock.isHeldByCurrentThread();
298          int n = size - 1;
299          if (n < 0)
300              return null;
301          else {
302 <            Object[] array = queue;
303 <            E result = (E) array[0];
304 <            E x = (E) array[n];
305 <            array[n] = null;
306 <            Comparator<? super E> cmp = comparator;
307 <            if (cmp == null)
308 <                siftDownComparable(0, x, array, n);
309 <            else
310 <                siftDownUsingComparator(0, x, array, n, cmp);
302 >            final Object[] es = queue;
303 >            E result = (E) es[0];
304 >            E x = (E) es[n];
305 >            es[n] = null;
306 >            if (n > 0) {
307 >                Comparator<? super E> cmp = comparator;
308 >                if (cmp == null)
309 >                    siftDownComparable(0, x, es, n);
310 >                else
311 >                    siftDownUsingComparator(0, x, es, n, cmp);
312 >            }
313              size = n;
314              return result;
315          }
# Line 323 | Line 326 | public class PriorityBlockingQueue<E> ex
326       *
327       * @param k the position to fill
328       * @param x the item to insert
329 <     * @param array the heap array
329 >     * @param es the heap array
330       */
331 <    private static <T> void siftUpComparable(int k, T x, Object[] array) {
331 >    private static <T> void siftUpComparable(int k, T x, Object[] es) {
332          Comparable<? super T> key = (Comparable<? super T>) x;
333          while (k > 0) {
334              int parent = (k - 1) >>> 1;
335 <            Object e = array[parent];
335 >            Object e = es[parent];
336              if (key.compareTo((T) e) >= 0)
337                  break;
338 <            array[k] = e;
338 >            es[k] = e;
339              k = parent;
340          }
341 <        array[k] = key;
341 >        es[k] = key;
342      }
343  
344 <    private static <T> void siftUpUsingComparator(int k, T x, Object[] array,
345 <                                       Comparator<? super T> cmp) {
344 >    private static <T> void siftUpUsingComparator(
345 >        int k, T x, Object[] es, Comparator<? super T> cmp) {
346          while (k > 0) {
347              int parent = (k - 1) >>> 1;
348 <            Object e = array[parent];
348 >            Object e = es[parent];
349              if (cmp.compare(x, (T) e) >= 0)
350                  break;
351 <            array[k] = e;
351 >            es[k] = e;
352              k = parent;
353          }
354 <        array[k] = x;
354 >        es[k] = x;
355      }
356  
357      /**
# Line 358 | Line 361 | public class PriorityBlockingQueue<E> ex
361       *
362       * @param k the position to fill
363       * @param x the item to insert
364 <     * @param array the heap array
364 >     * @param es the heap array
365       * @param n heap size
366       */
367 <    private static <T> void siftDownComparable(int k, T x, Object[] array,
368 <                                               int n) {
369 <        if (n > 0) {
370 <            Comparable<? super T> key = (Comparable<? super T>)x;
371 <            int half = n >>> 1;           // loop while a non-leaf
372 <            while (k < half) {
373 <                int child = (k << 1) + 1; // assume left child is least
374 <                Object c = array[child];
375 <                int right = child + 1;
376 <                if (right < n &&
377 <                    ((Comparable<? super T>) c).compareTo((T) array[right]) > 0)
378 <                    c = array[child = right];
379 <                if (key.compareTo((T) c) <= 0)
380 <                    break;
381 <                array[k] = c;
379 <                k = child;
380 <            }
381 <            array[k] = key;
367 >    private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
368 >        // assert n > 0;
369 >        Comparable<? super T> key = (Comparable<? super T>)x;
370 >        int half = n >>> 1;           // loop while a non-leaf
371 >        while (k < half) {
372 >            int child = (k << 1) + 1; // assume left child is least
373 >            Object c = es[child];
374 >            int right = child + 1;
375 >            if (right < n &&
376 >                ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
377 >                c = es[child = right];
378 >            if (key.compareTo((T) c) <= 0)
379 >                break;
380 >            es[k] = c;
381 >            k = child;
382          }
383 +        es[k] = key;
384      }
385  
386 <    private static <T> void siftDownUsingComparator(int k, T x, Object[] array,
387 <                                                    int n,
388 <                                                    Comparator<? super T> cmp) {
389 <        if (n > 0) {
390 <            int half = n >>> 1;
391 <            while (k < half) {
392 <                int child = (k << 1) + 1;
393 <                Object c = array[child];
394 <                int right = child + 1;
395 <                if (right < n && cmp.compare((T) c, (T) array[right]) > 0)
396 <                    c = array[child = right];
397 <                if (cmp.compare(x, (T) c) <= 0)
398 <                    break;
399 <                array[k] = c;
399 <                k = child;
400 <            }
401 <            array[k] = x;
386 >    private static <T> void siftDownUsingComparator(
387 >        int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
388 >        // assert n > 0;
389 >        int half = n >>> 1;
390 >        while (k < half) {
391 >            int child = (k << 1) + 1;
392 >            Object c = es[child];
393 >            int right = child + 1;
394 >            if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
395 >                c = es[child = right];
396 >            if (cmp.compare(x, (T) c) <= 0)
397 >                break;
398 >            es[k] = c;
399 >            k = child;
400          }
401 +        es[k] = x;
402      }
403  
404      /**
# Line 408 | Line 407 | public class PriorityBlockingQueue<E> ex
407       * This classic algorithm due to Floyd (1964) is known to be O(size).
408       */
409      private void heapify() {
410 <        Object[] array = queue;
410 >        final Object[] es = queue;
411          int n = size, i = (n >>> 1) - 1;
412          Comparator<? super E> cmp = comparator;
413 <        if (cmp == null) {
413 >        if (cmp == null)
414              for (; i >= 0; i--)
415 <                siftDownComparable(i, (E) array[i], array, n);
416 <        }
418 <        else {
415 >                siftDownComparable(i, (E) es[i], es, n);
416 >        else
417              for (; i >= 0; i--)
418 <                siftDownUsingComparator(i, (E) array[i], array, n, cmp);
421 <        }
418 >                siftDownUsingComparator(i, (E) es[i], es, n, cmp);
419      }
420  
421      /**
# Line 595 | Line 592 | public class PriorityBlockingQueue<E> ex
592       * Removes the ith element from queue.
593       */
594      private void removeAt(int i) {
595 <        Object[] array = queue;
595 >        final Object[] es = queue;
596          int n = size - 1;
597          if (n == i) // removed last element
598 <            array[i] = null;
598 >            es[i] = null;
599          else {
600 <            E moved = (E) array[n];
601 <            array[n] = null;
600 >            E moved = (E) es[n];
601 >            es[n] = null;
602              Comparator<? super E> cmp = comparator;
603              if (cmp == null)
604 <                siftDownComparable(i, moved, array, n);
604 >                siftDownComparable(i, moved, es, n);
605              else
606 <                siftDownUsingComparator(i, moved, array, n, cmp);
607 <            if (array[i] == moved) {
606 >                siftDownUsingComparator(i, moved, es, n, cmp);
607 >            if (es[i] == moved) {
608                  if (cmp == null)
609 <                    siftUpComparable(i, moved, array);
609 >                    siftUpComparable(i, moved, es);
610                  else
611 <                    siftUpUsingComparator(i, moved, array, cmp);
611 >                    siftUpUsingComparator(i, moved, es, cmp);
612              }
613          }
614          size = n;
# Line 934 | Line 931 | public class PriorityBlockingQueue<E> ex
931          public void forEachRemaining(Consumer<? super E> action) {
932              Objects.requireNonNull(action);
933              final int hi = getFence(), lo = index;
934 <            final Object[] a = array;
934 >            final Object[] es = array;
935              index = hi;                 // ensure exhaustion
936              for (int i = lo; i < hi; i++)
937 <                action.accept((E) a[i]);
937 >                action.accept((E) es[i]);
938          }
939  
940          public boolean tryAdvance(Consumer<? super E> action) {

Diff Legend

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