35 |
35 |
36 package java.util.concurrent; |
36 package java.util.concurrent; |
37 |
37 |
38 import java.util.concurrent.locks.Condition; |
38 import java.util.concurrent.locks.Condition; |
39 import java.util.concurrent.locks.ReentrantLock; |
39 import java.util.concurrent.locks.ReentrantLock; |
40 import java.util.*; |
40 import java.util.AbstractQueue; |
|
41 import java.util.Arrays; |
|
42 import java.util.Collection; |
|
43 import java.util.Comparator; |
|
44 import java.util.Iterator; |
|
45 import java.util.NoSuchElementException; |
|
46 import java.util.PriorityQueue; |
|
47 import java.util.Queue; |
|
48 import java.util.SortedSet; |
|
49 import java.util.Spliterator; |
|
50 import java.util.function.Consumer; |
41 |
51 |
42 /** |
52 /** |
43 * An unbounded {@linkplain BlockingQueue blocking queue} that uses |
53 * An unbounded {@linkplain BlockingQueue blocking queue} that uses |
44 * the same ordering rules as class {@link PriorityQueue} and supplies |
54 * the same ordering rules as class {@link PriorityQueue} and supplies |
45 * blocking retrieval operations. While this queue is logically |
55 * blocking retrieval operations. While this queue is logically |
340 * simplify use in light of possible comparator exceptions. |
350 * simplify use in light of possible comparator exceptions. |
341 * |
351 * |
342 * @param k the position to fill |
352 * @param k the position to fill |
343 * @param x the item to insert |
353 * @param x the item to insert |
344 * @param array the heap array |
354 * @param array the heap array |
345 * @param n heap size |
|
346 */ |
355 */ |
347 private static <T> void siftUpComparable(int k, T x, Object[] array) { |
356 private static <T> void siftUpComparable(int k, T x, Object[] array) { |
348 Comparable<? super T> key = (Comparable<? super T>) x; |
357 Comparable<? super T> key = (Comparable<? super T>) x; |
349 while (k > 0) { |
358 while (k > 0) { |
350 int parent = (k - 1) >>> 1; |
359 int parent = (k - 1) >>> 1; |
934 } finally { |
943 } finally { |
935 q = null; |
944 q = null; |
936 } |
945 } |
937 } |
946 } |
938 |
947 |
|
948 // Similar to Collections.ArraySnapshotSpliterator but avoids |
|
949 // commitment to toArray until needed |
|
950 static final class PBQSpliterator<E> implements Spliterator<E> { |
|
951 final PriorityBlockingQueue<E> queue; |
|
952 Object[] array; |
|
953 int index; |
|
954 int fence; |
|
955 |
|
956 PBQSpliterator(PriorityBlockingQueue<E> queue, Object[] array, |
|
957 int index, int fence) { |
|
958 this.queue = queue; |
|
959 this.array = array; |
|
960 this.index = index; |
|
961 this.fence = fence; |
|
962 } |
|
963 |
|
964 final int getFence() { |
|
965 int hi; |
|
966 if ((hi = fence) < 0) |
|
967 hi = fence = (array = queue.toArray()).length; |
|
968 return hi; |
|
969 } |
|
970 |
|
971 public Spliterator<E> trySplit() { |
|
972 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; |
|
973 return (lo >= mid) ? null : |
|
974 new PBQSpliterator<E>(queue, array, lo, index = mid); |
|
975 } |
|
976 |
|
977 @SuppressWarnings("unchecked") |
|
978 public void forEachRemaining(Consumer<? super E> action) { |
|
979 Object[] a; int i, hi; // hoist accesses and checks from loop |
|
980 if (action == null) |
|
981 throw new NullPointerException(); |
|
982 if ((a = array) == null) |
|
983 fence = (a = queue.toArray()).length; |
|
984 if ((hi = fence) <= a.length && |
|
985 (i = index) >= 0 && i < (index = hi)) { |
|
986 do { action.accept((E)a[i]); } while (++i < hi); |
|
987 } |
|
988 } |
|
989 |
|
990 public boolean tryAdvance(Consumer<? super E> action) { |
|
991 if (action == null) |
|
992 throw new NullPointerException(); |
|
993 if (getFence() > index && index >= 0) { |
|
994 @SuppressWarnings("unchecked") E e = (E) array[index++]; |
|
995 action.accept(e); |
|
996 return true; |
|
997 } |
|
998 return false; |
|
999 } |
|
1000 |
|
1001 public long estimateSize() { return (long)(getFence() - index); } |
|
1002 |
|
1003 public int characteristics() { |
|
1004 return Spliterator.NONNULL | Spliterator.SIZED | Spliterator.SUBSIZED; |
|
1005 } |
|
1006 } |
|
1007 |
|
1008 public Spliterator<E> spliterator() { |
|
1009 return new PBQSpliterator<E>(this, null, 0, -1); |
|
1010 } |
|
1011 |
939 // Unsafe mechanics |
1012 // Unsafe mechanics |
940 private static final sun.misc.Unsafe UNSAFE; |
1013 private static final sun.misc.Unsafe UNSAFE; |
941 private static final long allocationSpinLockOffset; |
1014 private static final long allocationSpinLockOffset; |
942 static { |
1015 static { |
943 try { |
1016 try { |