forked from kangjianwei/LearningJDK
-
Notifications
You must be signed in to change notification settings - Fork 0
/
PriorityBlockingQueue.java
1443 lines (1229 loc) · 52.1 KB
/
PriorityBlockingQueue.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
/*
* This file is available under and governed by the GNU General Public
* License version 2 only, as published by the Free Software Foundation.
* However, the following notice accompanied the original version of this
* file:
*
* Written by Doug Lea with assistance from members of JCP JSR-166
* Expert Group and released to the public domain, as explained at
* http://creativecommons.org/publicdomain/zero/1.0/
*/
package java.util.concurrent;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.util.AbstractQueue;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.SortedSet;
import java.util.Spliterator;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.Consumer;
import java.util.function.Predicate;
import jdk.internal.misc.SharedSecrets;
/**
* An unbounded {@linkplain BlockingQueue blocking queue} that uses
* the same ordering rules as class {@link PriorityQueue} and supplies
* blocking retrieval operations. While this queue is logically
* unbounded, attempted additions may fail due to resource exhaustion
* (causing {@code OutOfMemoryError}). This class does not permit
* {@code null} elements. A priority queue relying on {@linkplain
* Comparable natural ordering} also does not permit insertion of
* non-comparable objects (doing so results in
* {@code ClassCastException}).
*
* <p>This class and its iterator implement all of the <em>optional</em>
* methods of the {@link Collection} and {@link Iterator} interfaces.
* The Iterator provided in method {@link #iterator()} and the
* Spliterator provided in method {@link #spliterator()} are <em>not</em>
* guaranteed to traverse the elements of the PriorityBlockingQueue in
* any particular order. If you need ordered traversal, consider using
* {@code Arrays.sort(pq.toArray())}. Also, method {@code drainTo} can
* be used to <em>remove</em> some or all elements in priority order and
* place them in another collection.
*
* <p>Operations on this class make no guarantees about the ordering
* of elements with equal priority. If you need to enforce an
* ordering, you can define custom classes or comparators that use a
* secondary key to break ties in primary priority values. For
* example, here is a class that applies first-in-first-out
* tie-breaking to comparable elements. To use it, you would insert a
* {@code new FIFOEntry(anEntry)} instead of a plain entry object.
*
* <pre> {@code
* class FIFOEntry<E extends Comparable<? super E>>
* implements Comparable<FIFOEntry<E>> {
* static final AtomicLong seq = new AtomicLong(0);
* final long seqNum;
* final E entry;
* public FIFOEntry(E entry) {
* seqNum = seq.getAndIncrement();
* this.entry = entry;
* }
* public E getEntry() { return entry; }
* public int compareTo(FIFOEntry<E> other) {
* int res = entry.compareTo(other.entry);
* if (res == 0 && other.entry != this.entry)
* res = (seqNum < other.seqNum ? -1 : 1);
* return res;
* }
* }}</pre>
*
* <p>This class is a member of the
* <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
* Java Collections Framework</a>.
*
* @param <E> the type of elements held in this queue
*
* @author Doug Lea
* @since 1.5
*/
/*
* 顺序无界(队列容量支持扩容到Integer.MAX_VALUE)优先阻塞队列,线程安全(锁)
*
* 该容器可以看做是PriorityQueue的一个线程安全的版本
*
* 具体说明参见PriorityQueue
*/
@SuppressWarnings("unchecked")
public class PriorityBlockingQueue<E> extends AbstractQueue<E> implements BlockingQueue<E>, Serializable {
/*
* The implementation uses an array-based binary heap, with public
* operations protected with a single lock. However, allocation
* during resizing uses a simple spinlock (used only while not
* holding main lock) in order to allow takes to operate
* concurrently with allocation. This avoids repeated
* postponement of waiting consumers and consequent element
* build-up. The need to back away from lock during allocation
* makes it impossible to simply wrap delegated
* java.util.PriorityQueue operations within a lock, as was done
* in a previous version of this class. To maintain
* interoperability, a plain PriorityQueue is still used during
* serialization, which maintains compatibility at the expense of
* transiently doubling overhead.
*/
/**
* Default array capacity.
*/
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
// 存储队列元素
private transient Object[] queue;
/**
* The number of elements in the priority queue.
*/
// 队列长度
private transient int size;
/**
* The comparator, or null if priority queue uses elements'
* natural ordering.
*/
// 外部比较器,支持以自定义的顺序来比较元素。如果没有设置,则使用元素自身实现的内部比较器
private transient Comparator<? super E> comparator;
/**
* Spinlock for allocation, acquired via CAS.
*/
// 标记是否正在扩容
private transient volatile int allocationSpinLock;
/**
* Lock used for all public operations.
*/
private final ReentrantLock lock = new ReentrantLock();
/**
* Condition for blocking when empty.
*/
private final Condition notEmpty = lock.newCondition();
// VarHandle mechanics
private static final VarHandle ALLOCATIONSPINLOCK;
static {
try {
MethodHandles.Lookup l = MethodHandles.lookup();
ALLOCATIONSPINLOCK = l.findVarHandle(PriorityBlockingQueue.class, "allocationSpinLock", int.class);
} catch(ReflectiveOperationException e) {
throw new ExceptionInInitializerError(e);
}
}
/*▼ 构造器 ████████████████████████████████████████████████████████████████████████████████┓ */
/**
* Creates a {@code PriorityBlockingQueue} with the default
* initial capacity (11) that orders its elements according to
* their {@linkplain Comparable natural ordering}.
*/
public PriorityBlockingQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
/**
* Creates a {@code PriorityBlockingQueue} with the specified
* initial capacity that orders its elements according to their
* {@linkplain Comparable natural ordering}.
*
* @param initialCapacity the initial capacity for this priority queue
*
* @throws IllegalArgumentException if {@code initialCapacity} is less
* than 1
*/
public PriorityBlockingQueue(int initialCapacity) {
this(initialCapacity, null);
}
/**
* Creates a {@code PriorityBlockingQueue} with the specified initial
* capacity that orders its elements according to the specified
* comparator.
*
* @param initialCapacity the initial capacity for this priority queue
* @param comparator the comparator that will be used to order this
* priority queue. If {@code null}, the {@linkplain Comparable
* natural ordering} of the elements will be used.
*
* @throws IllegalArgumentException if {@code initialCapacity} is less
* than 1
*/
public PriorityBlockingQueue(int initialCapacity, Comparator<? super E> comparator) {
if(initialCapacity<1) {
throw new IllegalArgumentException();
}
this.comparator = comparator;
this.queue = new Object[Math.max(1, initialCapacity)];
}
/**
* Creates a {@code PriorityBlockingQueue} containing the elements
* in the specified collection. If the specified collection is a
* {@link SortedSet} or a {@link PriorityQueue}, this
* priority queue will be ordered according to the same ordering.
* Otherwise, this priority queue will be ordered according to the
* {@linkplain Comparable natural ordering} of its elements.
*
* @param c the collection whose elements are to be placed
* into this priority queue
*
* @throws ClassCastException if elements of the specified collection
* cannot be compared to one another according to the priority
* queue's ordering
* @throws NullPointerException if the specified collection or any
* of its elements are null
*/
public PriorityBlockingQueue(Collection<? extends E> c) {
// 是否需要重建堆
boolean heapify = true; // true if not known to be in heap order
// 是否需要筛选空值
boolean screen = true; // true if must screen for nulls
if(c instanceof SortedSet<?>) {
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
// SortedSet已经有序了,不需要重建堆
heapify = false;
} else if(c instanceof PriorityBlockingQueue<?>) {
PriorityBlockingQueue<? extends E> pq = (PriorityBlockingQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
// 来自于PriorityBlockingQueue的元素已经排除了空值,所以不需要再筛选
screen = false;
// 如果是从PriorityBlockingQueue初始化的,也不需要重建堆
if(pq.getClass() == PriorityBlockingQueue.class) { // exact match
heapify = false;
}
}
// 获取容器中的元素
Object[] es = c.toArray();
int n = es.length;
// If c.toArray incorrectly doesn't return Object[], copy it.
if(es.getClass() != Object[].class) {
es = Arrays.copyOf(es, n, Object[].class);
}
// 必要时,筛选空值
if(screen && (n == 1 || this.comparator != null)) {
for(Object e : es) {
if(e == null) {
throw new NullPointerException();
}
}
}
this.queue = ensureNonEmpty(es);
this.size = n;
// 必要时,重建小顶堆
if(heapify) {
heapify();
}
}
/*▲ 构造器 ████████████████████████████████████████████████████████████████████████████████┛ */
/*▼ 入队 ████████████████████████████████████████████████████████████████████████████████┓ */
/**
* Inserts the specified element into this priority queue.
* As the queue is unbounded, this method will never return {@code false}.
*
* @param e the element to add
*
* @return {@code true} (as specified by {@link Queue#offer})
*
* @throws ClassCastException if the specified element cannot be compared
* with elements currently in the priority queue according to the
* priority queue's ordering
* @throws NullPointerException if the specified element is null
*/
// 入队,线程安全,无法入队时扩容,不阻塞
public boolean offer(E e) {
if(e == null) {
throw new NullPointerException();
}
final ReentrantLock lock = this.lock;
lock.lock();
int n, cap;
Object[] es;
// 扩容
while((n = size) >= (cap = (es = queue).length)) {
tryGrow(es, cap);
}
try {
/* 插入。需要从小顶堆的结点n开始,向【上】查找一个合适的位置插入e */
final Comparator<? super E> cmp;
if((cmp = comparator) == null) {
siftUpComparable(n, e, es);
} else {
siftUpUsingComparator(n, e, es, cmp);
}
// 队列长度增一
size = n + 1;
// 唤醒出队线程
notEmpty.signal();
} finally {
lock.unlock();
}
return true;
}
/**
* Inserts the specified element into this priority queue.
* As the queue is unbounded, this method will never block or
* return {@code false}.
*
* @param e the element to add
* @param timeout This parameter is ignored as the method never blocks
* @param unit This parameter is ignored as the method never blocks
*
* @return {@code true} (as specified by
* {@link BlockingQueue#offer(Object, long, TimeUnit) BlockingQueue.offer})
*
* @throws ClassCastException if the specified element cannot be compared
* with elements currently in the priority queue according to the
* priority queue's ordering
* @throws NullPointerException if the specified element is null
*/
// 入队,线程安全,无法入队时扩容,不阻塞
public boolean offer(E e, long timeout, TimeUnit unit) {
return offer(e); // never need to block
}
/**
* Inserts the specified element into this priority queue.
* As the queue is unbounded, this method will never block.
*
* @param e the element to add
*
* @throws ClassCastException if the specified element cannot be compared
* with elements currently in the priority queue according to the
* priority queue's ordering
* @throws NullPointerException if the specified element is null
*/
// 入队,线程安全,无法入队时扩容,不阻塞
public void put(E e) {
offer(e); // never need to block
}
/**
* Inserts the specified element into this priority queue.
*
* @param e the element to add
*
* @return {@code true} (as specified by {@link Collection#add})
*
* @throws ClassCastException if the specified element cannot be compared
* with elements currently in the priority queue according to the
* priority queue's ordering
* @throws NullPointerException if the specified element is null
*/
// 入队/添加,线程安全,无法入队时扩容,不阻塞
public boolean add(E e) {
return offer(e);
}
/*▲ 入队 ████████████████████████████████████████████████████████████████████████████████┛ */
/*▼ 出队 ████████████████████████████████████████████████████████████████████████████████┓ */
// 出队,线程安全,无法出队时返回null,不阻塞
public E poll() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return dequeue();
} finally {
lock.unlock();
}
}
// 出队,线程安全,无法出队时阻塞一段时间,超时后无法出队则返回null
public E poll(long timeout, TimeUnit unit) throws InterruptedException {
long nanos = unit.toNanos(timeout);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
E result;
try {
while((result = dequeue()) == null && nanos>0) {
nanos = notEmpty.awaitNanos(nanos);
}
} finally {
lock.unlock();
}
return result;
}
// 出队,线程安全,无法出队时阻塞
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
E result;
try {
while((result = dequeue()) == null) {
notEmpty.await();
}
} finally {
lock.unlock();
}
return result;
}
/**
* Removes a single instance of the specified element from this queue,
* if it is present. More formally, removes an element {@code e} such
* that {@code o.equals(e)}, if this queue contains one or more such
* elements. Returns {@code true} if and only if this queue contained
* the specified element (or equivalently, if this queue changed as a
* result of the call).
*
* @param o element to be removed from this queue, if present
*
* @return {@code true} if this queue changed as a result of the call
*/
// 移除,非线程安全,移除成功则返回true
public boolean remove(Object o) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
// 获取指定元素在队列中的索引,不在队列中时返回-1
int i = indexOf(o);
// 如果元素不在队列中,返回false
if(i == -1) {
return false;
}
// 移除队列索引i处的元素
removeAt(i);
return true;
} finally {
lock.unlock();
}
}
/**
* Removes the ith element from queue.
*/
// 移除队列索引i处的元素
private void removeAt(int i) {
final Object[] es = queue;
final int n = size - 1;
// 如果移除的是队尾元素
if(n == i) { // removed last element
es[i] = null;
} else {
/* 如果不是移除队尾元素,则需要将队尾元素防止在新的小顶堆中的合适位置 */
// 摘下队尾元素
E moved = (E) es[n];
es[n] = null;
final Comparator<? super E> cmp;
/* 插入。需要从小顶堆的结点i开始,向【下】查找一个合适的位置插入moved */
if((cmp = comparator) == null) {
siftDownComparable(i, moved, es, n);
} else {
siftDownUsingComparator(i, moved, es, n, cmp);
}
/*
* 如果待moved是以i为根结点的小顶堆上的最小值,
* 那么不能保证moved比结点i的父结点元素更大,
* 此时需要向上搜寻moved的一个合适的插入位置
*/
if(es[i] == moved) {
/* 插入。需要从小顶堆的结点i开始,向【上】查找一个合适的位置插入x */
if(cmp == null) {
siftUpComparable(i, moved, es);
} else {
siftUpUsingComparator(i, moved, es, cmp);
}
}
}
size = n;
}
/**
* @throws NullPointerException {@inheritDoc}
*/
// 移除所有满足过滤条件的元素(线程安全)
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
return bulkRemove(filter);
}
/**
* @throws NullPointerException {@inheritDoc}
*/
// (匹配则移除)移除队列中所有与给定容器中的元素匹配的元素(线程安全)
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return bulkRemove(e -> c.contains(e));
}
/**
* @throws NullPointerException {@inheritDoc}
*/
// (不匹配则移除)移除队列中所有与给定容器中的元素不匹配的元素(线程安全)
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return bulkRemove(e -> !c.contains(e));
}
/**
* Atomically removes all of the elements from this queue.
* The queue will be empty after this call returns.
*/
// 清空,即移除所有元素(线程安全)
public void clear() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
final Object[] es = queue;
for(int i = 0, n = size; i<n; i++) {
es[i] = null;
}
size = 0;
} finally {
lock.unlock();
}
}
/**
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
// 将队列中所有元素移除,并转移到给定的容器当中(线程安全)
public int drainTo(Collection<? super E> c) {
return drainTo(c, Integer.MAX_VALUE);
}
/**
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
// 将队列中前maxElements个元素移除,并转移到给定的容器当中(线程安全)
public int drainTo(Collection<? super E> c, int maxElements) {
Objects.requireNonNull(c);
if(c == this) {
throw new IllegalArgumentException();
}
if(maxElements<=0) {
return 0;
}
final ReentrantLock lock = this.lock;
lock.lock();
try {
int n = Math.min(size, maxElements);
for(int i = 0; i<n; i++) {
// 任务添加到容器中
c.add((E) queue[0]); // In this order, in case add() throws.
// 移除队头任务
dequeue();
}
return n;
} finally {
lock.unlock();
}
}
/*▲ 出队 ████████████████████████████████████████████████████████████████████████████████┛ */
/*▼ 取值 ████████████████████████████████████████████████████████████████████████████████┓ */
// 获取队头元素
public E peek() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return (E) queue[0];
} finally {
lock.unlock();
}
}
/*▲ 取值 ████████████████████████████████████████████████████████████████████████████████┛ */
/*▼ 包含查询 ████████████████████████████████████████████████████████████████████████████████┓ */
/**
* Returns {@code true} if this queue contains the specified element.
* More formally, returns {@code true} if and only if this queue contains
* at least one element {@code e} such that {@code o.equals(e)}.
*
* @param o object to be checked for containment in this queue
*
* @return {@code true} if this queue contains the specified element
*/
// 判断队列中是否包含元素o
public boolean contains(Object o) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return indexOf(o) != -1;
} finally {
lock.unlock();
}
}
/*▲ 包含查询 ████████████████████████████████████████████████████████████████████████████████┛ */
/*▼ 视图 ████████████████████████████████████████████████████████████████████████████████┓ */
/**
* Returns an array containing all of the elements in this queue.
* The returned array elements are in no particular order.
*
* <p>The returned array will be "safe" in that no references to it are
* maintained by this queue. (In other words, this method must allocate
* a new array). The caller is thus free to modify the returned array.
*
* <p>This method acts as bridge between array-based and collection-based
* APIs.
*
* @return an array containing all of the elements in this queue
*/
public Object[] toArray() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return Arrays.copyOf(queue, size);
} finally {
lock.unlock();
}
}
/**
* Returns an array containing all of the elements in this queue; the
* runtime type of the returned array is that of the specified array.
* The returned array elements are in no particular order.
* If the queue fits in the specified array, it is returned therein.
* Otherwise, a new array is allocated with the runtime type of the
* specified array and the size of this queue.
*
* <p>If this queue fits in the specified array with room to spare
* (i.e., the array has more elements than this queue), the element in
* the array immediately following the end of the queue is set to
* {@code null}.
*
* <p>Like the {@link #toArray()} method, this method acts as bridge between
* array-based and collection-based APIs. Further, this method allows
* precise control over the runtime type of the output array, and may,
* under certain circumstances, be used to save allocation costs.
*
* <p>Suppose {@code x} is a queue known to contain only strings.
* The following code can be used to dump the queue into a newly
* allocated array of {@code String}:
*
* <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
*
* Note that {@code toArray(new Object[0])} is identical in function to
* {@code toArray()}.
*
* @param a the array into which the elements of the queue are to
* be stored, if it is big enough; otherwise, a new array of the
* same runtime type is allocated for this purpose
*
* @return an array containing all of the elements in this queue
*
* @throws ArrayStoreException if the runtime type of the specified array
* is not a supertype of the runtime type of every element in
* this queue
* @throws NullPointerException if the specified array is null
*/
public <T> T[] toArray(T[] a) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
int n = size;
if(a.length<n)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(queue, size, a.getClass());
System.arraycopy(queue, 0, a, 0, n);
if(a.length>n)
a[n] = null;
return a;
} finally {
lock.unlock();
}
}
/*▲ 视图 ████████████████████████████████████████████████████████████████████████████████┛ */
/*▼ 迭代 ████████████████████████████████████████████████████████████████████████████████┓ */
/**
* @throws NullPointerException {@inheritDoc}
*/
// 遍历所有元素,并执行相应的择取操作
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final ReentrantLock lock = this.lock;
lock.lock();
try {
final Object[] es = queue;
for(int i = 0, n = size; i<n; i++) {
action.accept((E) es[i]);
}
} finally {
lock.unlock();
}
}
/**
* Returns an iterator over the elements in this queue. The
* iterator does not return the elements in any particular order.
*
* <p>The returned iterator is
* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
*
* @return an iterator over the elements in this queue
*/
// 返回当前队列的迭代器
public Iterator<E> iterator() {
return new Itr(toArray());
}
/**
* Returns a {@link Spliterator} over the elements in this queue.
* The spliterator does not traverse elements in any particular order
* (the {@link Spliterator#ORDERED ORDERED} characteristic is not reported).
*
* <p>The returned spliterator is
* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
*
* <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and
* {@link Spliterator#NONNULL}.
*
* @return a {@code Spliterator} over the elements in this queue
*
* @implNote The {@code Spliterator} additionally reports {@link Spliterator#SUBSIZED}.
* @since 1.8
*/
// 返回描述此队列中元素的Spliterator
public Spliterator<E> spliterator() {
return new PBQSpliterator();
}
/*▲ 迭代 ████████████████████████████████████████████████████████████████████████████████┛ */
/*▼ 杂项 ████████████████████████████████████████████████████████████████████████████████┓ */
// 返回队列中元素数量
public int size() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return size;
} finally {
lock.unlock();
}
}
/**
* Always returns {@code Integer.MAX_VALUE} because
* a {@code PriorityBlockingQueue} is not capacity constrained.
*
* @return {@code Integer.MAX_VALUE} always
*/
// 计算队列剩余空间,返回Integer.MAX_VALUE代表无限
public int remainingCapacity() {
return Integer.MAX_VALUE;
}
/**
* Returns the comparator used to order the elements in this queue,
* or {@code null} if this queue uses the {@linkplain Comparable
* natural ordering} of its elements.
*
* @return the comparator used to order the elements in this queue,
* or {@code null} if this queue uses the natural
* ordering of its elements
*/
// 返回该队列使用的外部比较器
public Comparator<? super E> comparator() {
return comparator;
}
/*▲ 杂项 ████████████████████████████████████████████████████████████████████████████████┛ */
/*▼ 序列化 ████████████████████████████████████████████████████████████████████████████████┓ */
private static final long serialVersionUID = 5595510919245408276L;
/**
* A plain PriorityQueue used only for serialization,
* to maintain compatibility with previous versions
* of this class. Non-null only during serialization/deserialization.
*/
// 用于序列化
private PriorityQueue<E> q;
/**
* Saves this queue to a stream (that is, serializes it).
*
* For compatibility with previous version of this class, elements
* are first copied to a java.util.PriorityQueue, which is then
* serialized.
*
* @param s the stream
*
* @throws java.io.IOException if an I/O error occurs
*/
private void writeObject(ObjectOutputStream s) throws java.io.IOException {
lock.lock();
try {
// avoid zero capacity argument
q = new PriorityQueue<E>(Math.max(size, 1), comparator);
q.addAll(this);
s.defaultWriteObject();
} finally {
q = null;
lock.unlock();
}
}
/**
* Reconstitutes this queue from a stream (that is, deserializes it).
*
* @param s the stream
*
* @throws ClassNotFoundException if the class of a serialized object
* could not be found
* @throws java.io.IOException if an I/O error occurs
*/
private void readObject(ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
try {
s.defaultReadObject();
int sz = q.size();
SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, sz);
this.queue = new Object[Math.max(1, sz)];
comparator = q.comparator();
addAll(q);
} finally {
q = null;
}
}
/*▲ 序列化 ████████████████████████████████████████████████████████████████████████████████┛ */
/*▼ 小顶堆 ████████████████████████████████████████████████████████████████████████████████┓ */
/**
* Inserts item x at position k, maintaining heap invariant by
* promoting x up the tree until it is greater than or equal to
* its parent, or is the root.
*
* To simplify and speed up coercions and comparisons, the
* Comparable and Comparator versions are separated into different
* methods that are otherwise identical. (Similarly for siftDown.)
*
* @param i the position to fill
* @param x the item to insert
* @param es the heap array
*/
// 插入。需要从小顶堆的结点i开始,向【上】查找一个合适的位置插入x
private static <T> void siftUpComparable(int i, T x, Object[] es) {
// 类型转换,要求待插入元素必须实现Comparable接口
Comparable<? super T> key = (Comparable<? super T>) x;
while(i>0) {
// 获取父结点索引
int parent = (i - 1) >>> 1;
// 父结点
Object e = es[parent];
// 如果待插入元素大于父节点中的元素,则退出循环
if(key.compareTo((T) e) >= 0) {
break;
}
// 子结点保存父结点中的元素
es[i] = e;
// 向上搜寻合适的插入位置
i = parent;
}
// 将元素key插入到合适的位置
es[i] = key;
}
// 插入。需要从小顶堆的结点i开始,向【上】查找一个合适的位置插入x