1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.tomcat.dbcp.pool2.impl;
18
19 import java.io.Serializable;
20 import java.util.AbstractQueue;
21 import java.util.Collection;
22 import java.util.Deque;
23 import java.util.Iterator;
24 import java.util.NoSuchElementException;
25 import java.util.concurrent.TimeUnit;
26 import java.util.concurrent.locks.Condition;
27
28 /**
29 * An optionally-bounded {@linkplain java.util.concurrent.BlockingDeque blocking
30 * deque} based on linked nodes.
31 *
32 * <p> The optional capacity bound constructor argument serves as a
33 * way to prevent excessive expansion. The capacity, if unspecified,
34 * is equal to {@link Integer#MAX_VALUE}. Linked nodes are
35 * dynamically created upon each insertion unless this would bring the
36 * deque above capacity.
37 * </p>
38 *
39 * <p>Most operations run in constant time (ignoring time spent
40 * blocking). Exceptions include {@link #remove(Object) remove},
41 * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link
42 * #removeLastOccurrence removeLastOccurrence}, {@link #contains
43 * contains}, {@link #iterator iterator.remove()}, and the bulk
44 * operations, all of which run in linear time.
45 * </p>
46 *
47 * <p>This class and its iterator implement all of the
48 * <em>optional</em> methods of the {@link Collection} and {@link
49 * Iterator} interfaces.
50 * </p>
51 *
52 * <p>This class is a member of the
53 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
54 * Java Collections Framework</a>.
55 * </p>
56 *
57 * @param <E> the type of elements held in this collection
58 *
59 * Note: This was copied from Apache Harmony and modified to suit the needs of
60 * Commons Pool.
61 *
62 * @since 2.0
63 */
64 class LinkedBlockingDeque<E> extends AbstractQueue<E>
65 implements Deque<E>, Serializable {
66
67 /*
68 * Implemented as a simple doubly-linked list protected by a
69 * single lock and using conditions to manage blocking.
70 *
71 * To implement weakly consistent iterators, it appears we need to
72 * keep all Nodes GC-reachable from a predecessor dequeued Node.
73 * That would cause two problems:
74 * - allow a rogue Iterator to cause unbounded memory retention
75 * - cause cross-generational linking of old Nodes to new Nodes if
76 * a Node was tenured while live, which generational GCs have a
77 * hard time dealing with, causing repeated major collections.
78 * However, only non-deleted Nodes need to be reachable from
79 * dequeued Nodes, and reachability does not necessarily have to
80 * be of the kind understood by the GC. We use the trick of
81 * linking a Node that has just been dequeued to itself. Such a
82 * self-link implicitly means to jump to "first" (for next links)
83 * or "last" (for prev links).
84 */
85
86 /*
87 * We have "diamond" multiple interface/abstract class inheritance
88 * here, and that introduces ambiguities. Often we want the
89 * BlockingDeque javadoc combined with the AbstractQueue
90 * implementation, so a lot of method specs are duplicated here.
91 */
92
93 private static final long serialVersionUID = -387911632671998426L;
94
95 /**
96 * Doubly-linked list node class.
97 *
98 * @param <E> node item type
99 */
100 private static final class Node<E> {
101 /**
102 * The item, or null if this node has been removed.
103 */
104 E item;
105
106 /**
107 * One of:
108 * - the real predecessor Node
109 * - this Node, meaning the predecessor is tail
110 * - null, meaning there is no predecessor
111 */
112 Node<E> prev;
113
114 /**
115 * One of:
116 * - the real successor Node
117 * - this Node, meaning the successor is head
118 * - null, meaning there is no successor
119 */
120 Node<E> next;
121
122 /**
123 * Create a new list node.
124 *
125 * @param x The list item
126 * @param p Previous item
127 * @param n Next item
128 */
129 Node(final E x, final Node<E> p, final Node<E> n) {
130 item = x;
131 prev = p;
132 next = n;
133 }
134 }
135
136 /**
137 * Pointer to first node.
138 * Invariant: (first == null && last == null) ||
139 * (first.prev == null && first.item != null)
140 */
141 private transient Node<E> first; // @GuardedBy("lock")
142
143 /**
144 * Pointer to last node.
145 * Invariant: (first == null && last == null) ||
146 * (last.next == null && last.item != null)
147 */
148 private transient Node<E> last; // @GuardedBy("lock")
149
150 /** Number of items in the deque */
151 private transient int count; // @GuardedBy("lock")
152
153 /** Maximum number of items in the deque */
154 private final int capacity;
155
156 /** Main lock guarding all access */
157 private final InterruptibleReentrantLock lock;
158
159 /** Condition for waiting takes */
160 private final Condition notEmpty;
161
162 /** Condition for waiting puts */
163 private final Condition notFull;
164
165 /**
166 * Creates a {@code LinkedBlockingDeque} with a capacity of
167 * {@link Integer#MAX_VALUE}.
168 */
169 public LinkedBlockingDeque() {
170 this(Integer.MAX_VALUE);
171 }
172
173 /**
174 * Creates a {@code LinkedBlockingDeque} with a capacity of
175 * {@link Integer#MAX_VALUE} and the given fairness policy.
176 * @param fairness true means threads waiting on the deque should be served
177 * as if waiting in a FIFO request queue
178 */
179 public LinkedBlockingDeque(final boolean fairness) {
180 this(Integer.MAX_VALUE, fairness);
181 }
182
183 /**
184 * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity.
185 *
186 * @param capacity the capacity of this deque
187 * @throws IllegalArgumentException if {@code capacity} is less than 1
188 */
189 public LinkedBlockingDeque(final int capacity) {
190 this(capacity, false);
191 }
192
193 /**
194 * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity
195 * and fairness policy.
196 *
197 * @param capacity the capacity of this deque
198 * @param fairness true means threads waiting on the deque should be served
199 * as if waiting in a FIFO request queue
200 * @throws IllegalArgumentException if {@code capacity} is less than 1
201 */
202 public LinkedBlockingDeque(final int capacity, final boolean fairness) {
203 if (capacity <= 0) {
204 throw new IllegalArgumentException();
205 }
206 this.capacity = capacity;
207 lock = new InterruptibleReentrantLock(fairness);
208 notEmpty = lock.newCondition();
209 notFull = lock.newCondition();
210 }
211
212 /**
213 * Creates a {@code LinkedBlockingDeque} with a capacity of
214 * {@link Integer#MAX_VALUE}, initially containing the elements of
215 * the given collection, added in traversal order of the
216 * collection's iterator.
217 *
218 * @param c the collection of elements to initially contain
219 * @throws NullPointerException if the specified collection or any
220 * of its elements are null
221 */
222 public LinkedBlockingDeque(final Collection<? extends E> c) {
223 this(Integer.MAX_VALUE);
224 lock.lock(); // Never contended, but necessary for visibility
225 try {
226 for (final E e : c) {
227 if (e == null) {
228 throw new NullPointerException();
229 }
230 if (!linkLast(e)) {
231 throw new IllegalStateException("Deque full");
232 }
233 }
234 } finally {
235 lock.unlock();
236 }
237 }
238
239
240 // Basic linking and unlinking operations, called only while holding lock
241
242 /**
243 * Links provided element as first element, or returns false if full.
244 *
245 * @param e The element to link as the first element.
246 *
247 * @return {@code true} if successful, otherwise {@code false}
248 */
249 private boolean linkFirst(final E e) {
250 // assert lock.isHeldByCurrentThread();
251 if (count >= capacity) {
252 return false;
253 }
254 final Node<E> f = first;
255 final Node<E> x = new Node<>(e, null, f);
256 first = x;
257 if (last == null) {
258 last = x;
259 } else {
260 f.prev = x;
261 }
262 ++count;
263 notEmpty.signal();
264 return true;
265 }
266
267 /**
268 * Links provided element as last element, or returns false if full.
269 *
270 * @param e The element to link as the last element.
271 *
272 * @return {@code true} if successful, otherwise {@code false}
273 */
274 private boolean linkLast(final E e) {
275 // assert lock.isHeldByCurrentThread();
276 if (count >= capacity) {
277 return false;
278 }
279 final Node<E> l = last;
280 final Node<E> x = new Node<>(e, l, null);
281 last = x;
282 if (first == null) {
283 first = x;
284 } else {
285 l.next = x;
286 }
287 ++count;
288 notEmpty.signal();
289 return true;
290 }
291
292 /**
293 * Removes and returns the first element, or null if empty.
294 *
295 * @return The first element or {@code null} if empty
296 */
297 private E unlinkFirst() {
298 // assert lock.isHeldByCurrentThread();
299 final Node<E> f = first;
300 if (f == null) {
301 return null;
302 }
303 final Node<E> n = f.next;
304 final E item = f.item;
305 f.item = null;
306 f.next = f; // help GC
307 first = n;
308 if (n == null) {
309 last = null;
310 } else {
311 n.prev = null;
312 }
313 --count;
314 notFull.signal();
315 return item;
316 }
317
318 /**
319 * Removes and returns the last element, or null if empty.
320 *
321 * @return The first element or {@code null} if empty
322 */
323 private E unlinkLast() {
324 // assert lock.isHeldByCurrentThread();
325 final Node<E> l = last;
326 if (l == null) {
327 return null;
328 }
329 final Node<E> p = l.prev;
330 final E item = l.item;
331 l.item = null;
332 l.prev = l; // help GC
333 last = p;
334 if (p == null) {
335 first = null;
336 } else {
337 p.next = null;
338 }
339 --count;
340 notFull.signal();
341 return item;
342 }
343
344 /**
345 * Unlinks the provided node.
346 *
347 * @param x The node to unlink
348 */
349 private void unlink(final Node<E> x) {
350 // assert lock.isHeldByCurrentThread();
351 final Node<E> p = x.prev;
352 final Node<E> n = x.next;
353 if (p == null) {
354 unlinkFirst();
355 } else if (n == null) {
356 unlinkLast();
357 } else {
358 p.next = n;
359 n.prev = p;
360 x.item = null;
361 // Don't mess with x's links. They may still be in use by
362 // an iterator.
363 --count;
364 notFull.signal();
365 }
366 }
367
368 // BlockingDeque methods
369
370 /**
371 * {@inheritDoc}
372 */
373 @Override
374 public void addFirst(final E e) {
375 if (!offerFirst(e)) {
376 throw new IllegalStateException("Deque full");
377 }
378 }
379
380 /**
381 * {@inheritDoc}
382 */
383 @Override
384 public void addLast(final E e) {
385 if (!offerLast(e)) {
386 throw new IllegalStateException("Deque full");
387 }
388 }
389
390 /**
391 * {@inheritDoc}
392 */
393 @Override
394 public boolean offerFirst(final E e) {
395 if (e == null) {
396 throw new NullPointerException();
397 }
398 lock.lock();
399 try {
400 return linkFirst(e);
401 } finally {
402 lock.unlock();
403 }
404 }
405
406 /**
407 * {@inheritDoc}
408 */
409 @Override
410 public boolean offerLast(final E e) {
411 if (e == null) {
412 throw new NullPointerException();
413 }
414 lock.lock();
415 try {
416 return linkLast(e);
417 } finally {
418 lock.unlock();
419 }
420 }
421
422 /**
423 * Links the provided element as the first in the queue, waiting until there
424 * is space to do so if the queue is full.
425 *
426 * @param e element to link
427 *
428 * @throws NullPointerException if e is null
429 * @throws InterruptedException if the thread is interrupted whilst waiting
430 * for space
431 */
432 public void putFirst(final E e) throws InterruptedException {
433 if (e == null) {
434 throw new NullPointerException();
435 }
436 lock.lock();
437 try {
438 while (!linkFirst(e)) {
439 notFull.await();
440 }
441 } finally {
442 lock.unlock();
443 }
444 }
445
446 /**
447 * Links the provided element as the last in the queue, waiting until there
448 * is space to do so if the queue is full.
449 *
450 * @param e element to link
451 *
452 * @throws NullPointerException if e is null
453 * @throws InterruptedException if the thread is interrupted whilst waiting
454 * for space
455 */
456 public void putLast(final E e) throws InterruptedException {
457 if (e == null) {
458 throw new NullPointerException();
459 }
460 lock.lock();
461 try {
462 while (!linkLast(e)) {
463 notFull.await();
464 }
465 } finally {
466 lock.unlock();
467 }
468 }
469
470 /**
471 * Links the provided element as the first in the queue, waiting up to the
472 * specified time to do so if the queue is full.
473 *
474 * @param e element to link
475 * @param timeout length of time to wait
476 * @param unit units that timeout is expressed in
477 *
478 * @return {@code true} if successful, otherwise {@code false}
479 *
480 * @throws NullPointerException if e is null
481 * @throws InterruptedException if the thread is interrupted whilst waiting
482 * for space
483 */
484 public boolean offerFirst(final E e, final long timeout, final TimeUnit unit)
485 throws InterruptedException {
486 if (e == null) {
487 throw new NullPointerException();
488 }
489 long nanos = unit.toNanos(timeout);
490 lock.lockInterruptibly();
491 try {
492 while (!linkFirst(e)) {
493 if (nanos <= 0) {
494 return false;
495 }
496 nanos = notFull.awaitNanos(nanos);
497 }
498 return true;
499 } finally {
500 lock.unlock();
501 }
502 }
503
504 /**
505 * Links the provided element as the last in the queue, waiting up to the
506 * specified time to do so if the queue is full.
507 *
508 * @param e element to link
509 * @param timeout length of time to wait
510 * @param unit units that timeout is expressed in
511 *
512 * @return {@code true} if successful, otherwise {@code false}
513 *
514 * @throws NullPointerException if e is null
515 * @throws InterruptedException if the thread is interrupted whist waiting
516 * for space
517 */
518 public boolean offerLast(final E e, final long timeout, final TimeUnit unit)
519 throws InterruptedException {
520 if (e == null) {
521 throw new NullPointerException();
522 }
523 long nanos = unit.toNanos(timeout);
524 lock.lockInterruptibly();
525 try {
526 while (!linkLast(e)) {
527 if (nanos <= 0) {
528 return false;
529 }
530 nanos = notFull.awaitNanos(nanos);
531 }
532 return true;
533 } finally {
534 lock.unlock();
535 }
536 }
537
538 /**
539 * {@inheritDoc}
540 */
541 @Override
542 public E removeFirst() {
543 final E x = pollFirst();
544 if (x == null) {
545 throw new NoSuchElementException();
546 }
547 return x;
548 }
549
550 /**
551 * {@inheritDoc}
552 */
553 @Override
554 public E removeLast() {
555 final E x = pollLast();
556 if (x == null) {
557 throw new NoSuchElementException();
558 }
559 return x;
560 }
561
562 @Override
563 public E pollFirst() {
564 lock.lock();
565 try {
566 return unlinkFirst();
567 } finally {
568 lock.unlock();
569 }
570 }
571
572 @Override
573 public E pollLast() {
574 lock.lock();
575 try {
576 return unlinkLast();
577 } finally {
578 lock.unlock();
579 }
580 }
581
582 /**
583 * Unlinks the first element in the queue, waiting until there is an element
584 * to unlink if the queue is empty.
585 *
586 * @return the unlinked element
587 * @throws InterruptedException if the current thread is interrupted
588 */
589 public E takeFirst() throws InterruptedException {
590 lock.lock();
591 try {
592 E x;
593 while ( (x = unlinkFirst()) == null) {
594 notEmpty.await();
595 }
596 return x;
597 } finally {
598 lock.unlock();
599 }
600 }
601
602 /**
603 * Unlinks the last element in the queue, waiting until there is an element
604 * to unlink if the queue is empty.
605 *
606 * @return the unlinked element
607 * @throws InterruptedException if the current thread is interrupted
608 */
609 public E takeLast() throws InterruptedException {
610 lock.lock();
611 try {
612 E x;
613 while ( (x = unlinkLast()) == null) {
614 notEmpty.await();
615 }
616 return x;
617 } finally {
618 lock.unlock();
619 }
620 }
621
622 /**
623 * Unlinks the first element in the queue, waiting up to the specified time
624 * to do so if the queue is empty.
625 *
626 * @param timeout length of time to wait
627 * @param unit units that timeout is expressed in
628 *
629 * @return the unlinked element
630 * @throws InterruptedException if the current thread is interrupted
631 */
632 public E pollFirst(final long timeout, final TimeUnit unit)
633 throws InterruptedException {
634 long nanos = unit.toNanos(timeout);
635 lock.lockInterruptibly();
636 try {
637 E x;
638 while ( (x = unlinkFirst()) == null) {
639 if (nanos <= 0) {
640 return null;
641 }
642 nanos = notEmpty.awaitNanos(nanos);
643 }
644 return x;
645 } finally {
646 lock.unlock();
647 }
648 }
649
650 /**
651 * Unlinks the last element in the queue, waiting up to the specified time
652 * to do so if the queue is empty.
653 *
654 * @param timeout length of time to wait
655 * @param unit units that timeout is expressed in
656 *
657 * @return the unlinked element
658 * @throws InterruptedException if the current thread is interrupted
659 */
660 public E pollLast(final long timeout, final TimeUnit unit)
661 throws InterruptedException {
662 long nanos = unit.toNanos(timeout);
663 lock.lockInterruptibly();
664 try {
665 E x;
666 while ( (x = unlinkLast()) == null) {
667 if (nanos <= 0) {
668 return null;
669 }
670 nanos = notEmpty.awaitNanos(nanos);
671 }
672 return x;
673 } finally {
674 lock.unlock();
675 }
676 }
677
678 /**
679 * {@inheritDoc}
680 */
681 @Override
682 public E getFirst() {
683 final E x = peekFirst();
684 if (x == null) {
685 throw new NoSuchElementException();
686 }
687 return x;
688 }
689
690 /**
691 * {@inheritDoc}
692 */
693 @Override
694 public E getLast() {
695 final E x = peekLast();
696 if (x == null) {
697 throw new NoSuchElementException();
698 }
699 return x;
700 }
701
702 @Override
703 public E peekFirst() {
704 lock.lock();
705 try {
706 return first == null ? null : first.item;
707 } finally {
708 lock.unlock();
709 }
710 }
711
712 @Override
713 public E peekLast() {
714 lock.lock();
715 try {
716 return last == null ? null : last.item;
717 } finally {
718 lock.unlock();
719 }
720 }
721
722 @Override
723 public boolean removeFirstOccurrence(final Object o) {
724 if (o == null) {
725 return false;
726 }
727 lock.lock();
728 try {
729 for (Node<E> p = first; p != null; p = p.next) {
730 if (o.equals(p.item)) {
731 unlink(p);
732 return true;
733 }
734 }
735 return false;
736 } finally {
737 lock.unlock();
738 }
739 }
740
741 @Override
742 public boolean removeLastOccurrence(final Object o) {
743 if (o == null) {
744 return false;
745 }
746 lock.lock();
747 try {
748 for (Node<E> p = last; p != null; p = p.prev) {
749 if (o.equals(p.item)) {
750 unlink(p);
751 return true;
752 }
753 }
754 return false;
755 } finally {
756 lock.unlock();
757 }
758 }
759
760 // BlockingQueue methods
761
762 /**
763 * {@inheritDoc}
764 */
765 @Override
766 public boolean add(final E e) {
767 addLast(e);
768 return true;
769 }
770
771 /**
772 * {@inheritDoc}
773 */
774 @Override
775 public boolean offer(final E e) {
776 return offerLast(e);
777 }
778
779 /**
780 * Links the provided element as the last in the queue, waiting until there
781 * is space to do so if the queue is full.
782 *
783 * <p>This method is equivalent to {@link #putLast(Object)}.
784 *
785 * @param e element to link
786 *
787 * @throws NullPointerException if e is null
788 * @throws InterruptedException if the thread is interrupted whilst waiting
789 * for space
790 */
791 public void put(final E e) throws InterruptedException {
792 putLast(e);
793 }
794
795 /**
796 * Links the provided element as the last in the queue, waiting up to the
797 * specified time to do so if the queue is full.
798 * <p>
799 * This method is equivalent to {@link #offerLast(Object, long, TimeUnit)}
800 *
801 * @param e element to link
802 * @param timeout length of time to wait
803 * @param unit units that timeout is expressed in
804 *
805 * @return {@code true} if successful, otherwise {@code false}
806 *
807 * @throws NullPointerException if e is null
808 * @throws InterruptedException if the thread is interrupted whilst waiting
809 * for space
810 */
811 public boolean offer(final E e, final long timeout, final TimeUnit unit)
812 throws InterruptedException {
813 return offerLast(e, timeout, unit);
814 }
815
816 /**
817 * Retrieves and removes the head of the queue represented by this deque.
818 * This method differs from {@link #poll poll} only in that it throws an
819 * exception if this deque is empty.
820 *
821 * <p>This method is equivalent to {@link #removeFirst() removeFirst}.
822 *
823 * @return the head of the queue represented by this deque
824 * @throws NoSuchElementException if this deque is empty
825 */
826 @Override
827 public E remove() {
828 return removeFirst();
829 }
830
831 @Override
832 public E poll() {
833 return pollFirst();
834 }
835
836 /**
837 * Unlinks the first element in the queue, waiting until there is an element
838 * to unlink if the queue is empty.
839 *
840 * <p>This method is equivalent to {@link #takeFirst()}.
841 *
842 * @return the unlinked element
843 * @throws InterruptedException if the current thread is interrupted
844 */
845 public E take() throws InterruptedException {
846 return takeFirst();
847 }
848
849 /**
850 * Unlinks the first element in the queue, waiting up to the specified time
851 * to do so if the queue is empty.
852 *
853 * <p>This method is equivalent to {@link #pollFirst(long, TimeUnit)}.
854 *
855 * @param timeout length of time to wait
856 * @param unit units that timeout is expressed in
857 *
858 * @return the unlinked element
859 * @throws InterruptedException if the current thread is interrupted
860 */
861 public E poll(final long timeout, final TimeUnit unit) throws InterruptedException {
862 return pollFirst(timeout, unit);
863 }
864
865 /**
866 * Retrieves, but does not remove, the head of the queue represented by
867 * this deque. This method differs from {@link #peek peek} only in that
868 * it throws an exception if this deque is empty.
869 *
870 * <p>This method is equivalent to {@link #getFirst() getFirst}.
871 *
872 * @return the head of the queue represented by this deque
873 * @throws NoSuchElementException if this deque is empty
874 */
875 @Override
876 public E element() {
877 return getFirst();
878 }
879
880 @Override
881 public E peek() {
882 return peekFirst();
883 }
884
885 /**
886 * Returns the number of additional elements that this deque can ideally
887 * (in the absence of memory or resource constraints) accept without
888 * blocking. This is always equal to the initial capacity of this deque
889 * less the current {@code size} of this deque.
890 *
891 * <p>Note that you <em>cannot</em> always tell if an attempt to insert
892 * an element will succeed by inspecting {@code remainingCapacity}
893 * because it may be the case that another thread is about to
894 * insert or remove an element.
895 *
896 * @return The number of additional elements the queue is able to accept
897 */
898 public int remainingCapacity() {
899 lock.lock();
900 try {
901 return capacity - count;
902 } finally {
903 lock.unlock();
904 }
905 }
906
907 /**
908 * Drains the queue to the specified collection.
909 *
910 * @param c The collection to add the elements to
911 *
912 * @return number of elements added to the collection
913 *
914 * @throws UnsupportedOperationException if the add operation is not
915 * supported by the specified collection
916 * @throws ClassCastException if the class of the elements held by this
917 * collection prevents them from being added to the specified
918 * collection
919 * @throws NullPointerException if c is null
920 * @throws IllegalArgumentException if c is this instance
921 */
922 public int drainTo(final Collection<? super E> c) {
923 return drainTo(c, Integer.MAX_VALUE);
924 }
925
926 /**
927 * Drains no more than the specified number of elements from the queue to the
928 * specified collection.
929 *
930 * @param c collection to add the elements to
931 * @param maxElements maximum number of elements to remove from the queue
932 *
933 * @return number of elements added to the collection
934 * @throws UnsupportedOperationException if the add operation is not
935 * supported by the specified collection
936 * @throws ClassCastException if the class of the elements held by this
937 * collection prevents them from being added to the specified
938 * collection
939 * @throws NullPointerException if c is null
940 * @throws IllegalArgumentException if c is this instance
941 */
942 public int drainTo(final Collection<? super E> c, final int maxElements) {
943 if (c == null) {
944 throw new NullPointerException();
945 }
946 if (c == this) {
947 throw new IllegalArgumentException();
948 }
949 lock.lock();
950 try {
951 final int n = Math.min(maxElements, count);
952 for (int i = 0; i < n; i++) {
953 c.add(first.item); // In this order, in case add() throws.
954 unlinkFirst();
955 }
956 return n;
957 } finally {
958 lock.unlock();
959 }
960 }
961
962 // Stack methods
963
964 /**
965 * {@inheritDoc}
966 */
967 @Override
968 public void push(final E e) {
969 addFirst(e);
970 }
971
972 /**
973 * {@inheritDoc}
974 */
975 @Override
976 public E pop() {
977 return removeFirst();
978 }
979
980 // Collection methods
981
982 /**
983 * Removes the first occurrence of the specified element from this deque.
984 * If the deque does not contain the element, it is unchanged.
985 * More formally, removes the first element {@code e} such that
986 * {@code o.equals(e)} (if such an element exists).
987 * Returns {@code true} if this deque contained the specified element
988 * (or equivalently, if this deque changed as a result of the call).
989 *
990 * <p>This method is equivalent to
991 * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}.
992 *
993 * @param o element to be removed from this deque, if present
994 * @return {@code true} if this deque changed as a result of the call
995 */
996 @Override
997 public boolean remove(final Object o) {
998 return removeFirstOccurrence(o);
999 }
1000
1001 /**
1002 * Returns the number of elements in this deque.
1003 *
1004 * @return the number of elements in this deque
1005 */
1006 @Override
1007 public int size() {
1008 lock.lock();
1009 try {
1010 return count;
1011 } finally {
1012 lock.unlock();
1013 }
1014 }
1015
1016 /**
1017 * Returns {@code true} if this deque contains the specified element.
1018 * More formally, returns {@code true} if and only if this deque contains
1019 * at least one element {@code e} such that {@code o.equals(e)}.
1020 *
1021 * @param o object to be checked for containment in this deque
1022 * @return {@code true} if this deque contains the specified element
1023 */
1024 @Override
1025 public boolean contains(final Object o) {
1026 if (o == null) {
1027 return false;
1028 }
1029 lock.lock();
1030 try {
1031 for (Node<E> p = first; p != null; p = p.next) {
1032 if (o.equals(p.item)) {
1033 return true;
1034 }
1035 }
1036 return false;
1037 } finally {
1038 lock.unlock();
1039 }
1040 }
1041
1042 /*
1043 * TODO: Add support for more efficient bulk operations.
1044 *
1045 * We don't want to acquire the lock for every iteration, but we
1046 * also want other threads a chance to interact with the
1047 * collection, especially when count is close to capacity.
1048 */
1049
1050 // /**
1051 // * Adds all of the elements in the specified collection to this
1052 // * queue. Attempts to addAll of a queue to itself result in
1053 // * {@code IllegalArgumentException}. Further, the behavior of
1054 // * this operation is undefined if the specified collection is
1055 // * modified while the operation is in progress.
1056 // *
1057 // * @param c collection containing elements to be added to this queue
1058 // * @return {@code true} if this queue changed as a result of the call
1059 // * @throws ClassCastException
1060 // * @throws NullPointerException
1061 // * @throws IllegalArgumentException
1062 // * @throws IllegalStateException
1063 // * @see #add(Object)
1064 // */
1065 // public boolean addAll(Collection<? extends E> c) {
1066 // if (c == null)
1067 // throw new NullPointerException();
1068 // if (c == this)
1069 // throw new IllegalArgumentException();
1070 // final ReentrantLock lock = this.lock;
1071 // lock.lock();
1072 // try {
1073 // boolean modified = false;
1074 // for (E e : c)
1075 // if (linkLast(e))
1076 // modified = true;
1077 // return modified;
1078 // } finally {
1079 // lock.unlock();
1080 // }
1081 // }
1082
1083 /**
1084 * Returns an array containing all of the elements in this deque, in
1085 * proper sequence (from first to last element).
1086 *
1087 * <p>The returned array will be "safe" in that no references to it are
1088 * maintained by this deque. (In other words, this method must allocate
1089 * a new array). The caller is thus free to modify the returned array.
1090 *
1091 * <p>This method acts as bridge between array-based and collection-based
1092 * APIs.
1093 *
1094 * @return an array containing all of the elements in this deque
1095 */
1096 @Override
1097 public Object[] toArray() {
1098 lock.lock();
1099 try {
1100 final Object[] a = new Object[count];
1101 int k = 0;
1102 for (Node<E> p = first; p != null; p = p.next) {
1103 a[k++] = p.item;
1104 }
1105 return a;
1106 } finally {
1107 lock.unlock();
1108 }
1109 }
1110
1111 /**
1112 * {@inheritDoc}
1113 */
1114 @SuppressWarnings("unchecked")
1115 @Override
1116 public <T> T[] toArray(T[] a) {
1117 lock.lock();
1118 try {
1119 if (a.length < count) {
1120 a = (T[])java.lang.reflect.Array.newInstance
1121 (a.getClass().getComponentType(), count);
1122 }
1123 int k = 0;
1124 for (Node<E> p = first; p != null; p = p.next) {
1125 a[k++] = (T)p.item;
1126 }
1127 if (a.length > k) {
1128 a[k] = null;
1129 }
1130 return a;
1131 } finally {
1132 lock.unlock();
1133 }
1134 }
1135
1136 @Override
1137 public String toString() {
1138 lock.lock();
1139 try {
1140 return super.toString();
1141 } finally {
1142 lock.unlock();
1143 }
1144 }
1145
1146 /**
1147 * Atomically removes all of the elements from this deque.
1148 * The deque will be empty after this call returns.
1149 */
1150 @Override
1151 public void clear() {
1152 lock.lock();
1153 try {
1154 for (Node<E> f = first; f != null;) {
1155 f.item = null;
1156 final Node<E> n = f.next;
1157 f.prev = null;
1158 f.next = null;
1159 f = n;
1160 }
1161 first = last = null;
1162 count = 0;
1163 notFull.signalAll();
1164 } finally {
1165 lock.unlock();
1166 }
1167 }
1168
1169 /**
1170 * Returns an iterator over the elements in this deque in proper sequence.
1171 * The elements will be returned in order from first (head) to last (tail).
1172 * The returned {@code Iterator} is a "weakly consistent" iterator that
1173 * will never throw {@link java.util.ConcurrentModificationException
1174 * ConcurrentModificationException},
1175 * and guarantees to traverse elements as they existed upon
1176 * construction of the iterator, and may (but is not guaranteed to)
1177 * reflect any modifications subsequent to construction.
1178 *
1179 * @return an iterator over the elements in this deque in proper sequence
1180 */
1181 @Override
1182 public Iterator<E> iterator() {
1183 return new Itr();
1184 }
1185
1186 /**
1187 * {@inheritDoc}
1188 */
1189 @Override
1190 public Iterator<E> descendingIterator() {
1191 return new DescendingItr();
1192 }
1193
1194 /**
1195 * Base class for Iterators for LinkedBlockingDeque
1196 */
1197 private abstract class AbstractItr implements Iterator<E> {
1198 /**
1199 * The next node to return in next()
1200 */
1201 Node<E> next;
1202
1203 /**
1204 * nextItem holds on to item fields because once we claim that
1205 * an element exists in hasNext(), we must return item read
1206 * under lock (in advance()) even if it was in the process of
1207 * being removed when hasNext() was called.
1208 */
1209 E nextItem;
1210
1211 /**
1212 * Node returned by most recent call to next. Needed by remove.
1213 * Reset to null if this element is deleted by a call to remove.
1214 */
1215 private Node<E> lastRet;
1216
1217 /**
1218 * Obtain the first node to be returned by the iterator.
1219 *
1220 * @return first node
1221 */
1222 abstract Node<E> firstNode();
1223
1224 /**
1225 * For a given node, obtain the next node to be returned by the
1226 * iterator.
1227 *
1228 * @param n given node
1229 *
1230 * @return next node
1231 */
1232 abstract Node<E> nextNode(Node<E> n);
1233
1234 /**
1235 * Create a new iterator. Sets the initial position.
1236 */
1237 AbstractItr() {
1238 // set to initial position
1239 lock.lock();
1240 try {
1241 next = firstNode();
1242 nextItem = next == null ? null : next.item;
1243 } finally {
1244 lock.unlock();
1245 }
1246 }
1247
1248 /**
1249 * Returns the successor node of the given non-null, but
1250 * possibly previously deleted, node.
1251 *
1252 * @param n node whose successor is sought
1253 * @return successor node
1254 */
1255 private Node<E> succ(Node<E> n) {
1256 // Chains of deleted nodes ending in null or self-links
1257 // are possible if multiple interior nodes are removed.
1258 for (;;) {
1259 final Node<E> s = nextNode(n);
1260 if (s == null) {
1261 return null;
1262 } else if (s.item != null) {
1263 return s;
1264 } else if (s == n) {
1265 return firstNode();
1266 } else {
1267 n = s;
1268 }
1269 }
1270 }
1271
1272 /**
1273 * Advances next.
1274 */
1275 void advance() {
1276 lock.lock();
1277 try {
1278 // assert next != null;
1279 next = succ(next);
1280 nextItem = next == null ? null : next.item;
1281 } finally {
1282 lock.unlock();
1283 }
1284 }
1285
1286 @Override
1287 public boolean hasNext() {
1288 return next != null;
1289 }
1290
1291 @Override
1292 public E next() {
1293 if (next == null) {
1294 throw new NoSuchElementException();
1295 }
1296 lastRet = next;
1297 final E x = nextItem;
1298 advance();
1299 return x;
1300 }
1301
1302 @Override
1303 public void remove() {
1304 final Node<E> n = lastRet;
1305 if (n == null) {
1306 throw new IllegalStateException();
1307 }
1308 lastRet = null;
1309 lock.lock();
1310 try {
1311 if (n.item != null) {
1312 unlink(n);
1313 }
1314 } finally {
1315 lock.unlock();
1316 }
1317 }
1318 }
1319
1320 /** Forward iterator */
1321 private class Itr extends AbstractItr {
1322 @Override
1323 Node<E> firstNode() { return first; }
1324 @Override
1325 Node<E> nextNode(final Node<E> n) { return n.next; }
1326 }
1327
1328 /** Descending iterator */
1329 private class DescendingItr extends AbstractItr {
1330 @Override
1331 Node<E> firstNode() { return last; }
1332 @Override
1333 Node<E> nextNode(final Node<E> n) { return n.prev; }
1334 }
1335
1336 /**
1337 * Saves the state of this deque to a stream (that is, serialize it).
1338 *
1339 * @serialData The capacity (int), followed by elements (each an
1340 * {@code Object}) in the proper order, followed by a null
1341 * @param s the stream
1342 */
1343 private void writeObject(final java.io.ObjectOutputStream s)
1344 throws java.io.IOException {
1345 lock.lock();
1346 try {
1347 // Write out capacity and any hidden stuff
1348 s.defaultWriteObject();
1349 // Write out all elements in the proper order.
1350 for (Node<E> p = first; p != null; p = p.next) {
1351 s.writeObject(p.item);
1352 }
1353 // Use trailing null as sentinel
1354 s.writeObject(null);
1355 } finally {
1356 lock.unlock();
1357 }
1358 }
1359
1360 /**
1361 * Reconstitutes this deque from a stream (that is,
1362 * deserialize it).
1363 * @param s the stream
1364 */
1365 private void readObject(final java.io.ObjectInputStream s)
1366 throws java.io.IOException, ClassNotFoundException {
1367 s.defaultReadObject();
1368 count = 0;
1369 first = null;
1370 last = null;
1371 // Read in all elements and place in queue
1372 for (;;) {
1373 @SuppressWarnings("unchecked")
1374 final
1375 E item = (E)s.readObject();
1376 if (item == null) {
1377 break;
1378 }
1379 add(item);
1380 }
1381 }
1382
1383 // Monitoring methods
1384
1385 /**
1386 * Returns true if there are threads waiting to take instances from this deque. See disclaimer on accuracy in
1387 * {@link java.util.concurrent.locks.ReentrantLock#hasWaiters(Condition)}.
1388 *
1389 * @return true if there is at least one thread waiting on this deque's notEmpty condition.
1390 */
1391 public boolean hasTakeWaiters() {
1392 lock.lock();
1393 try {
1394 return lock.hasWaiters(notEmpty);
1395 } finally {
1396 lock.unlock();
1397 }
1398 }
1399
1400 /**
1401 * Returns the length of the queue of threads waiting to take instances from this deque. See disclaimer on accuracy
1402 * in {@link java.util.concurrent.locks.ReentrantLock#getWaitQueueLength(Condition)}.
1403 *
1404 * @return number of threads waiting on this deque's notEmpty condition.
1405 */
1406 public int getTakeQueueLength() {
1407 lock.lock();
1408 try {
1409 return lock.getWaitQueueLength(notEmpty);
1410 } finally {
1411 lock.unlock();
1412 }
1413 }
1414
1415 /**
1416 * Interrupts the threads currently waiting to take an object from the pool. See disclaimer on accuracy in
1417 * {@link java.util.concurrent.locks.ReentrantLock#getWaitingThreads(Condition)}.
1418 */
1419 public void interuptTakeWaiters() {
1420 lock.lock();
1421 try {
1422 lock.interruptWaiters(notEmpty);
1423 } finally {
1424 lock.unlock();
1425 }
1426 }
1427 }
1428