0001 /*
0002 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0003 *
0004 * This code is free software; you can redistribute it and/or modify it
0005 * under the terms of the GNU General Public License version 2 only, as
0006 * published by the Free Software Foundation. Sun designates this
0007 * particular file as subject to the "Classpath" exception as provided
0008 * by Sun in the LICENSE file that accompanied this code.
0009 *
0010 * This code is distributed in the hope that it will be useful, but WITHOUT
0011 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0012 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0013 * version 2 for more details (a copy is included in the LICENSE file that
0014 * accompanied this code).
0015 *
0016 * You should have received a copy of the GNU General Public License version
0017 * 2 along with this work; if not, write to the Free Software Foundation,
0018 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0019 *
0020 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0021 * CA 95054 USA or visit www.sun.com if you need additional information or
0022 * have any questions.
0023 */
0024
0025 /*
0026 * This file is available under and governed by the GNU General Public
0027 * License version 2 only, as published by the Free Software Foundation.
0028 * However, the following notice accompanied the original version of this
0029 * file:
0030 *
0031 * Written by Doug Lea with assistance from members of JCP JSR-166
0032 * Expert Group and released to the public domain, as explained at
0033 * http://creativecommons.org/licenses/publicdomain
0034 */
0035
0036 package java.util.concurrent;
0037
0038 import java.util.*;
0039 import java.util.concurrent.locks.*;
0040
0041 /**
0042 * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
0043 * linked nodes.
0044 *
0045 * <p> The optional capacity bound constructor argument serves as a
0046 * way to prevent excessive expansion. The capacity, if unspecified,
0047 * is equal to {@link Integer#MAX_VALUE}. Linked nodes are
0048 * dynamically created upon each insertion unless this would bring the
0049 * deque above capacity.
0050 *
0051 * <p>Most operations run in constant time (ignoring time spent
0052 * blocking). Exceptions include {@link #remove(Object) remove},
0053 * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link
0054 * #removeLastOccurrence removeLastOccurrence}, {@link #contains
0055 * contains}, {@link #iterator iterator.remove()}, and the bulk
0056 * operations, all of which run in linear time.
0057 *
0058 * <p>This class and its iterator implement all of the
0059 * <em>optional</em> methods of the {@link Collection} and {@link
0060 * Iterator} interfaces.
0061 *
0062 * <p>This class is a member of the
0063 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
0064 * Java Collections Framework</a>.
0065 *
0066 * @since 1.6
0067 * @author Doug Lea
0068 * @param <E> the type of elements held in this collection
0069 */
0070 public class LinkedBlockingDeque<E> extends AbstractQueue<E> implements
0071 BlockingDeque<E>, java.io.Serializable {
0072
0073 /*
0074 * Implemented as a simple doubly-linked list protected by a
0075 * single lock and using conditions to manage blocking.
0076 */
0077
0078 /*
0079 * We have "diamond" multiple interface/abstract class inheritance
0080 * here, and that introduces ambiguities. Often we want the
0081 * BlockingDeque javadoc combined with the AbstractQueue
0082 * implementation, so a lot of method specs are duplicated here.
0083 */
0084
0085 private static final long serialVersionUID = -387911632671998426L;
0086
0087 /** Doubly-linked list node class */
0088 static final class Node<E> {
0089 E item;
0090 Node<E> prev;
0091 Node<E> next;
0092
0093 Node(E x, Node<E> p, Node<E> n) {
0094 item = x;
0095 prev = p;
0096 next = n;
0097 }
0098 }
0099
0100 /** Pointer to first node */
0101 private transient Node<E> first;
0102 /** Pointer to last node */
0103 private transient Node<E> last;
0104 /** Number of items in the deque */
0105 private transient int count;
0106 /** Maximum number of items in the deque */
0107 private final int capacity;
0108 /** Main lock guarding all access */
0109 private final ReentrantLock lock = new ReentrantLock();
0110 /** Condition for waiting takes */
0111 private final Condition notEmpty = lock.newCondition();
0112 /** Condition for waiting puts */
0113 private final Condition notFull = lock.newCondition();
0114
0115 /**
0116 * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
0117 * {@link Integer#MAX_VALUE}.
0118 */
0119 public LinkedBlockingDeque() {
0120 this (Integer.MAX_VALUE);
0121 }
0122
0123 /**
0124 * Creates a <tt>LinkedBlockingDeque</tt> with the given (fixed) capacity.
0125 *
0126 * @param capacity the capacity of this deque
0127 * @throws IllegalArgumentException if <tt>capacity</tt> is less than 1
0128 */
0129 public LinkedBlockingDeque(int capacity) {
0130 if (capacity <= 0)
0131 throw new IllegalArgumentException();
0132 this .capacity = capacity;
0133 }
0134
0135 /**
0136 * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
0137 * {@link Integer#MAX_VALUE}, initially containing the elements of
0138 * the given collection, added in traversal order of the
0139 * collection's iterator.
0140 *
0141 * @param c the collection of elements to initially contain
0142 * @throws NullPointerException if the specified collection or any
0143 * of its elements are null
0144 */
0145 public LinkedBlockingDeque(Collection<? extends E> c) {
0146 this (Integer.MAX_VALUE);
0147 for (E e : c)
0148 add(e);
0149 }
0150
0151 // Basic linking and unlinking operations, called only while holding lock
0152
0153 /**
0154 * Links e as first element, or returns false if full.
0155 */
0156 private boolean linkFirst(E e) {
0157 if (count >= capacity)
0158 return false;
0159 ++count;
0160 Node<E> f = first;
0161 Node<E> x = new Node<E>(e, null, f);
0162 first = x;
0163 if (last == null)
0164 last = x;
0165 else
0166 f.prev = x;
0167 notEmpty.signal();
0168 return true;
0169 }
0170
0171 /**
0172 * Links e as last element, or returns false if full.
0173 */
0174 private boolean linkLast(E e) {
0175 if (count >= capacity)
0176 return false;
0177 ++count;
0178 Node<E> l = last;
0179 Node<E> x = new Node<E>(e, l, null);
0180 last = x;
0181 if (first == null)
0182 first = x;
0183 else
0184 l.next = x;
0185 notEmpty.signal();
0186 return true;
0187 }
0188
0189 /**
0190 * Removes and returns first element, or null if empty.
0191 */
0192 private E unlinkFirst() {
0193 Node<E> f = first;
0194 if (f == null)
0195 return null;
0196 Node<E> n = f.next;
0197 first = n;
0198 if (n == null)
0199 last = null;
0200 else
0201 n.prev = null;
0202 --count;
0203 notFull.signal();
0204 return f.item;
0205 }
0206
0207 /**
0208 * Removes and returns last element, or null if empty.
0209 */
0210 private E unlinkLast() {
0211 Node<E> l = last;
0212 if (l == null)
0213 return null;
0214 Node<E> p = l.prev;
0215 last = p;
0216 if (p == null)
0217 first = null;
0218 else
0219 p.next = null;
0220 --count;
0221 notFull.signal();
0222 return l.item;
0223 }
0224
0225 /**
0226 * Unlink e
0227 */
0228 private void unlink(Node<E> x) {
0229 Node<E> p = x.prev;
0230 Node<E> n = x.next;
0231 if (p == null) {
0232 if (n == null)
0233 first = last = null;
0234 else {
0235 n.prev = null;
0236 first = n;
0237 }
0238 } else if (n == null) {
0239 p.next = null;
0240 last = p;
0241 } else {
0242 p.next = n;
0243 n.prev = p;
0244 }
0245 --count;
0246 notFull.signalAll();
0247 }
0248
0249 // BlockingDeque methods
0250
0251 /**
0252 * @throws IllegalStateException {@inheritDoc}
0253 * @throws NullPointerException {@inheritDoc}
0254 */
0255 public void addFirst(E e) {
0256 if (!offerFirst(e))
0257 throw new IllegalStateException("Deque full");
0258 }
0259
0260 /**
0261 * @throws IllegalStateException {@inheritDoc}
0262 * @throws NullPointerException {@inheritDoc}
0263 */
0264 public void addLast(E e) {
0265 if (!offerLast(e))
0266 throw new IllegalStateException("Deque full");
0267 }
0268
0269 /**
0270 * @throws NullPointerException {@inheritDoc}
0271 */
0272 public boolean offerFirst(E e) {
0273 if (e == null)
0274 throw new NullPointerException();
0275 lock.lock();
0276 try {
0277 return linkFirst(e);
0278 } finally {
0279 lock.unlock();
0280 }
0281 }
0282
0283 /**
0284 * @throws NullPointerException {@inheritDoc}
0285 */
0286 public boolean offerLast(E e) {
0287 if (e == null)
0288 throw new NullPointerException();
0289 lock.lock();
0290 try {
0291 return linkLast(e);
0292 } finally {
0293 lock.unlock();
0294 }
0295 }
0296
0297 /**
0298 * @throws NullPointerException {@inheritDoc}
0299 * @throws InterruptedException {@inheritDoc}
0300 */
0301 public void putFirst(E e) throws InterruptedException {
0302 if (e == null)
0303 throw new NullPointerException();
0304 lock.lock();
0305 try {
0306 while (!linkFirst(e))
0307 notFull.await();
0308 } finally {
0309 lock.unlock();
0310 }
0311 }
0312
0313 /**
0314 * @throws NullPointerException {@inheritDoc}
0315 * @throws InterruptedException {@inheritDoc}
0316 */
0317 public void putLast(E e) throws InterruptedException {
0318 if (e == null)
0319 throw new NullPointerException();
0320 lock.lock();
0321 try {
0322 while (!linkLast(e))
0323 notFull.await();
0324 } finally {
0325 lock.unlock();
0326 }
0327 }
0328
0329 /**
0330 * @throws NullPointerException {@inheritDoc}
0331 * @throws InterruptedException {@inheritDoc}
0332 */
0333 public boolean offerFirst(E e, long timeout, TimeUnit unit)
0334 throws InterruptedException {
0335 if (e == null)
0336 throw new NullPointerException();
0337 long nanos = unit.toNanos(timeout);
0338 lock.lockInterruptibly();
0339 try {
0340 for (;;) {
0341 if (linkFirst(e))
0342 return true;
0343 if (nanos <= 0)
0344 return false;
0345 nanos = notFull.awaitNanos(nanos);
0346 }
0347 } finally {
0348 lock.unlock();
0349 }
0350 }
0351
0352 /**
0353 * @throws NullPointerException {@inheritDoc}
0354 * @throws InterruptedException {@inheritDoc}
0355 */
0356 public boolean offerLast(E e, long timeout, TimeUnit unit)
0357 throws InterruptedException {
0358 if (e == null)
0359 throw new NullPointerException();
0360 long nanos = unit.toNanos(timeout);
0361 lock.lockInterruptibly();
0362 try {
0363 for (;;) {
0364 if (linkLast(e))
0365 return true;
0366 if (nanos <= 0)
0367 return false;
0368 nanos = notFull.awaitNanos(nanos);
0369 }
0370 } finally {
0371 lock.unlock();
0372 }
0373 }
0374
0375 /**
0376 * @throws NoSuchElementException {@inheritDoc}
0377 */
0378 public E removeFirst() {
0379 E x = pollFirst();
0380 if (x == null)
0381 throw new NoSuchElementException();
0382 return x;
0383 }
0384
0385 /**
0386 * @throws NoSuchElementException {@inheritDoc}
0387 */
0388 public E removeLast() {
0389 E x = pollLast();
0390 if (x == null)
0391 throw new NoSuchElementException();
0392 return x;
0393 }
0394
0395 public E pollFirst() {
0396 lock.lock();
0397 try {
0398 return unlinkFirst();
0399 } finally {
0400 lock.unlock();
0401 }
0402 }
0403
0404 public E pollLast() {
0405 lock.lock();
0406 try {
0407 return unlinkLast();
0408 } finally {
0409 lock.unlock();
0410 }
0411 }
0412
0413 public E takeFirst() throws InterruptedException {
0414 lock.lock();
0415 try {
0416 E x;
0417 while ((x = unlinkFirst()) == null)
0418 notEmpty.await();
0419 return x;
0420 } finally {
0421 lock.unlock();
0422 }
0423 }
0424
0425 public E takeLast() throws InterruptedException {
0426 lock.lock();
0427 try {
0428 E x;
0429 while ((x = unlinkLast()) == null)
0430 notEmpty.await();
0431 return x;
0432 } finally {
0433 lock.unlock();
0434 }
0435 }
0436
0437 public E pollFirst(long timeout, TimeUnit unit)
0438 throws InterruptedException {
0439 long nanos = unit.toNanos(timeout);
0440 lock.lockInterruptibly();
0441 try {
0442 for (;;) {
0443 E x = unlinkFirst();
0444 if (x != null)
0445 return x;
0446 if (nanos <= 0)
0447 return null;
0448 nanos = notEmpty.awaitNanos(nanos);
0449 }
0450 } finally {
0451 lock.unlock();
0452 }
0453 }
0454
0455 public E pollLast(long timeout, TimeUnit unit)
0456 throws InterruptedException {
0457 long nanos = unit.toNanos(timeout);
0458 lock.lockInterruptibly();
0459 try {
0460 for (;;) {
0461 E x = unlinkLast();
0462 if (x != null)
0463 return x;
0464 if (nanos <= 0)
0465 return null;
0466 nanos = notEmpty.awaitNanos(nanos);
0467 }
0468 } finally {
0469 lock.unlock();
0470 }
0471 }
0472
0473 /**
0474 * @throws NoSuchElementException {@inheritDoc}
0475 */
0476 public E getFirst() {
0477 E x = peekFirst();
0478 if (x == null)
0479 throw new NoSuchElementException();
0480 return x;
0481 }
0482
0483 /**
0484 * @throws NoSuchElementException {@inheritDoc}
0485 */
0486 public E getLast() {
0487 E x = peekLast();
0488 if (x == null)
0489 throw new NoSuchElementException();
0490 return x;
0491 }
0492
0493 public E peekFirst() {
0494 lock.lock();
0495 try {
0496 return (first == null) ? null : first.item;
0497 } finally {
0498 lock.unlock();
0499 }
0500 }
0501
0502 public E peekLast() {
0503 lock.lock();
0504 try {
0505 return (last == null) ? null : last.item;
0506 } finally {
0507 lock.unlock();
0508 }
0509 }
0510
0511 public boolean removeFirstOccurrence(Object o) {
0512 if (o == null)
0513 return false;
0514 lock.lock();
0515 try {
0516 for (Node<E> p = first; p != null; p = p.next) {
0517 if (o.equals(p.item)) {
0518 unlink(p);
0519 return true;
0520 }
0521 }
0522 return false;
0523 } finally {
0524 lock.unlock();
0525 }
0526 }
0527
0528 public boolean removeLastOccurrence(Object o) {
0529 if (o == null)
0530 return false;
0531 lock.lock();
0532 try {
0533 for (Node<E> p = last; p != null; p = p.prev) {
0534 if (o.equals(p.item)) {
0535 unlink(p);
0536 return true;
0537 }
0538 }
0539 return false;
0540 } finally {
0541 lock.unlock();
0542 }
0543 }
0544
0545 // BlockingQueue methods
0546
0547 /**
0548 * Inserts the specified element at the end of this deque unless it would
0549 * violate capacity restrictions. When using a capacity-restricted deque,
0550 * it is generally preferable to use method {@link #offer(Object) offer}.
0551 *
0552 * <p>This method is equivalent to {@link #addLast}.
0553 *
0554 * @throws IllegalStateException if the element cannot be added at this
0555 * time due to capacity restrictions
0556 * @throws NullPointerException if the specified element is null
0557 */
0558 public boolean add(E e) {
0559 addLast(e);
0560 return true;
0561 }
0562
0563 /**
0564 * @throws NullPointerException if the specified element is null
0565 */
0566 public boolean offer(E e) {
0567 return offerLast(e);
0568 }
0569
0570 /**
0571 * @throws NullPointerException {@inheritDoc}
0572 * @throws InterruptedException {@inheritDoc}
0573 */
0574 public void put(E e) throws InterruptedException {
0575 putLast(e);
0576 }
0577
0578 /**
0579 * @throws NullPointerException {@inheritDoc}
0580 * @throws InterruptedException {@inheritDoc}
0581 */
0582 public boolean offer(E e, long timeout, TimeUnit unit)
0583 throws InterruptedException {
0584 return offerLast(e, timeout, unit);
0585 }
0586
0587 /**
0588 * Retrieves and removes the head of the queue represented by this deque.
0589 * This method differs from {@link #poll poll} only in that it throws an
0590 * exception if this deque is empty.
0591 *
0592 * <p>This method is equivalent to {@link #removeFirst() removeFirst}.
0593 *
0594 * @return the head of the queue represented by this deque
0595 * @throws NoSuchElementException if this deque is empty
0596 */
0597 public E remove() {
0598 return removeFirst();
0599 }
0600
0601 public E poll() {
0602 return pollFirst();
0603 }
0604
0605 public E take() throws InterruptedException {
0606 return takeFirst();
0607 }
0608
0609 public E poll(long timeout, TimeUnit unit)
0610 throws InterruptedException {
0611 return pollFirst(timeout, unit);
0612 }
0613
0614 /**
0615 * Retrieves, but does not remove, the head of the queue represented by
0616 * this deque. This method differs from {@link #peek peek} only in that
0617 * it throws an exception if this deque is empty.
0618 *
0619 * <p>This method is equivalent to {@link #getFirst() getFirst}.
0620 *
0621 * @return the head of the queue represented by this deque
0622 * @throws NoSuchElementException if this deque is empty
0623 */
0624 public E element() {
0625 return getFirst();
0626 }
0627
0628 public E peek() {
0629 return peekFirst();
0630 }
0631
0632 /**
0633 * Returns the number of additional elements that this deque can ideally
0634 * (in the absence of memory or resource constraints) accept without
0635 * blocking. This is always equal to the initial capacity of this deque
0636 * less the current <tt>size</tt> of this deque.
0637 *
0638 * <p>Note that you <em>cannot</em> always tell if an attempt to insert
0639 * an element will succeed by inspecting <tt>remainingCapacity</tt>
0640 * because it may be the case that another thread is about to
0641 * insert or remove an element.
0642 */
0643 public int remainingCapacity() {
0644 lock.lock();
0645 try {
0646 return capacity - count;
0647 } finally {
0648 lock.unlock();
0649 }
0650 }
0651
0652 /**
0653 * @throws UnsupportedOperationException {@inheritDoc}
0654 * @throws ClassCastException {@inheritDoc}
0655 * @throws NullPointerException {@inheritDoc}
0656 * @throws IllegalArgumentException {@inheritDoc}
0657 */
0658 public int drainTo(Collection<? super E> c) {
0659 if (c == null)
0660 throw new NullPointerException();
0661 if (c == this )
0662 throw new IllegalArgumentException();
0663 lock.lock();
0664 try {
0665 for (Node<E> p = first; p != null; p = p.next)
0666 c.add(p.item);
0667 int n = count;
0668 count = 0;
0669 first = last = null;
0670 notFull.signalAll();
0671 return n;
0672 } finally {
0673 lock.unlock();
0674 }
0675 }
0676
0677 /**
0678 * @throws UnsupportedOperationException {@inheritDoc}
0679 * @throws ClassCastException {@inheritDoc}
0680 * @throws NullPointerException {@inheritDoc}
0681 * @throws IllegalArgumentException {@inheritDoc}
0682 */
0683 public int drainTo(Collection<? super E> c, int maxElements) {
0684 if (c == null)
0685 throw new NullPointerException();
0686 if (c == this )
0687 throw new IllegalArgumentException();
0688 lock.lock();
0689 try {
0690 int n = 0;
0691 while (n < maxElements && first != null) {
0692 c.add(first.item);
0693 first.prev = null;
0694 first = first.next;
0695 --count;
0696 ++n;
0697 }
0698 if (first == null)
0699 last = null;
0700 notFull.signalAll();
0701 return n;
0702 } finally {
0703 lock.unlock();
0704 }
0705 }
0706
0707 // Stack methods
0708
0709 /**
0710 * @throws IllegalStateException {@inheritDoc}
0711 * @throws NullPointerException {@inheritDoc}
0712 */
0713 public void push(E e) {
0714 addFirst(e);
0715 }
0716
0717 /**
0718 * @throws NoSuchElementException {@inheritDoc}
0719 */
0720 public E pop() {
0721 return removeFirst();
0722 }
0723
0724 // Collection methods
0725
0726 /**
0727 * Removes the first occurrence of the specified element from this deque.
0728 * If the deque does not contain the element, it is unchanged.
0729 * More formally, removes the first element <tt>e</tt> such that
0730 * <tt>o.equals(e)</tt> (if such an element exists).
0731 * Returns <tt>true</tt> if this deque contained the specified element
0732 * (or equivalently, if this deque changed as a result of the call).
0733 *
0734 * <p>This method is equivalent to
0735 * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}.
0736 *
0737 * @param o element to be removed from this deque, if present
0738 * @return <tt>true</tt> if this deque changed as a result of the call
0739 */
0740 public boolean remove(Object o) {
0741 return removeFirstOccurrence(o);
0742 }
0743
0744 /**
0745 * Returns the number of elements in this deque.
0746 *
0747 * @return the number of elements in this deque
0748 */
0749 public int size() {
0750 lock.lock();
0751 try {
0752 return count;
0753 } finally {
0754 lock.unlock();
0755 }
0756 }
0757
0758 /**
0759 * Returns <tt>true</tt> if this deque contains the specified element.
0760 * More formally, returns <tt>true</tt> if and only if this deque contains
0761 * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
0762 *
0763 * @param o object to be checked for containment in this deque
0764 * @return <tt>true</tt> if this deque contains the specified element
0765 */
0766 public boolean contains(Object o) {
0767 if (o == null)
0768 return false;
0769 lock.lock();
0770 try {
0771 for (Node<E> p = first; p != null; p = p.next)
0772 if (o.equals(p.item))
0773 return true;
0774 return false;
0775 } finally {
0776 lock.unlock();
0777 }
0778 }
0779
0780 /**
0781 * Variant of removeFirstOccurrence needed by iterator.remove.
0782 * Searches for the node, not its contents.
0783 */
0784 boolean removeNode(Node<E> e) {
0785 lock.lock();
0786 try {
0787 for (Node<E> p = first; p != null; p = p.next) {
0788 if (p == e) {
0789 unlink(p);
0790 return true;
0791 }
0792 }
0793 return false;
0794 } finally {
0795 lock.unlock();
0796 }
0797 }
0798
0799 /**
0800 * Returns an array containing all of the elements in this deque, in
0801 * proper sequence (from first to last element).
0802 *
0803 * <p>The returned array will be "safe" in that no references to it are
0804 * maintained by this deque. (In other words, this method must allocate
0805 * a new array). The caller is thus free to modify the returned array.
0806 *
0807 * <p>This method acts as bridge between array-based and collection-based
0808 * APIs.
0809 *
0810 * @return an array containing all of the elements in this deque
0811 */
0812 public Object[] toArray() {
0813 lock.lock();
0814 try {
0815 Object[] a = new Object[count];
0816 int k = 0;
0817 for (Node<E> p = first; p != null; p = p.next)
0818 a[k++] = p.item;
0819 return a;
0820 } finally {
0821 lock.unlock();
0822 }
0823 }
0824
0825 /**
0826 * Returns an array containing all of the elements in this deque, in
0827 * proper sequence; the runtime type of the returned array is that of
0828 * the specified array. If the deque fits in the specified array, it
0829 * is returned therein. Otherwise, a new array is allocated with the
0830 * runtime type of the specified array and the size of this deque.
0831 *
0832 * <p>If this deque fits in the specified array with room to spare
0833 * (i.e., the array has more elements than this deque), the element in
0834 * the array immediately following the end of the deque is set to
0835 * <tt>null</tt>.
0836 *
0837 * <p>Like the {@link #toArray()} method, this method acts as bridge between
0838 * array-based and collection-based APIs. Further, this method allows
0839 * precise control over the runtime type of the output array, and may,
0840 * under certain circumstances, be used to save allocation costs.
0841 *
0842 * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
0843 * The following code can be used to dump the deque into a newly
0844 * allocated array of <tt>String</tt>:
0845 *
0846 * <pre>
0847 * String[] y = x.toArray(new String[0]);</pre>
0848 *
0849 * Note that <tt>toArray(new Object[0])</tt> is identical in function to
0850 * <tt>toArray()</tt>.
0851 *
0852 * @param a the array into which the elements of the deque are to
0853 * be stored, if it is big enough; otherwise, a new array of the
0854 * same runtime type is allocated for this purpose
0855 * @return an array containing all of the elements in this deque
0856 * @throws ArrayStoreException if the runtime type of the specified array
0857 * is not a supertype of the runtime type of every element in
0858 * this deque
0859 * @throws NullPointerException if the specified array is null
0860 */
0861 public <T> T[] toArray(T[] a) {
0862 lock.lock();
0863 try {
0864 if (a.length < count)
0865 a = (T[]) java.lang.reflect.Array.newInstance(a
0866 .getClass().getComponentType(), count);
0867
0868 int k = 0;
0869 for (Node<E> p = first; p != null; p = p.next)
0870 a[k++] = (T) p.item;
0871 if (a.length > k)
0872 a[k] = null;
0873 return a;
0874 } finally {
0875 lock.unlock();
0876 }
0877 }
0878
0879 public String toString() {
0880 lock.lock();
0881 try {
0882 return super .toString();
0883 } finally {
0884 lock.unlock();
0885 }
0886 }
0887
0888 /**
0889 * Atomically removes all of the elements from this deque.
0890 * The deque will be empty after this call returns.
0891 */
0892 public void clear() {
0893 lock.lock();
0894 try {
0895 first = last = null;
0896 count = 0;
0897 notFull.signalAll();
0898 } finally {
0899 lock.unlock();
0900 }
0901 }
0902
0903 /**
0904 * Returns an iterator over the elements in this deque in proper sequence.
0905 * The elements will be returned in order from first (head) to last (tail).
0906 * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
0907 * will never throw {@link ConcurrentModificationException},
0908 * and guarantees to traverse elements as they existed upon
0909 * construction of the iterator, and may (but is not guaranteed to)
0910 * reflect any modifications subsequent to construction.
0911 *
0912 * @return an iterator over the elements in this deque in proper sequence
0913 */
0914 public Iterator<E> iterator() {
0915 return new Itr();
0916 }
0917
0918 /**
0919 * Returns an iterator over the elements in this deque in reverse
0920 * sequential order. The elements will be returned in order from
0921 * last (tail) to first (head).
0922 * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
0923 * will never throw {@link ConcurrentModificationException},
0924 * and guarantees to traverse elements as they existed upon
0925 * construction of the iterator, and may (but is not guaranteed to)
0926 * reflect any modifications subsequent to construction.
0927 */
0928 public Iterator<E> descendingIterator() {
0929 return new DescendingItr();
0930 }
0931
0932 /**
0933 * Base class for Iterators for LinkedBlockingDeque
0934 */
0935 private abstract class AbstractItr implements Iterator<E> {
0936 /**
0937 * The next node to return in next
0938 */
0939 Node<E> next;
0940
0941 /**
0942 * nextItem holds on to item fields because once we claim that
0943 * an element exists in hasNext(), we must return item read
0944 * under lock (in advance()) even if it was in the process of
0945 * being removed when hasNext() was called.
0946 */
0947 E nextItem;
0948
0949 /**
0950 * Node returned by most recent call to next. Needed by remove.
0951 * Reset to null if this element is deleted by a call to remove.
0952 */
0953 private Node<E> lastRet;
0954
0955 AbstractItr() {
0956 advance(); // set to initial position
0957 }
0958
0959 /**
0960 * Advances next, or if not yet initialized, sets to first node.
0961 * Implemented to move forward vs backward in the two subclasses.
0962 */
0963 abstract void advance();
0964
0965 public boolean hasNext() {
0966 return next != null;
0967 }
0968
0969 public E next() {
0970 if (next == null)
0971 throw new NoSuchElementException();
0972 lastRet = next;
0973 E x = nextItem;
0974 advance();
0975 return x;
0976 }
0977
0978 public void remove() {
0979 Node<E> n = lastRet;
0980 if (n == null)
0981 throw new IllegalStateException();
0982 lastRet = null;
0983 // Note: removeNode rescans looking for this node to make
0984 // sure it was not already removed. Otherwise, trying to
0985 // re-remove could corrupt list.
0986 removeNode(n);
0987 }
0988 }
0989
0990 /** Forward iterator */
0991 private class Itr extends AbstractItr {
0992 void advance() {
0993 final ReentrantLock lock = LinkedBlockingDeque.this .lock;
0994 lock.lock();
0995 try {
0996 next = (next == null) ? first : next.next;
0997 nextItem = (next == null) ? null : next.item;
0998 } finally {
0999 lock.unlock();
1000 }
1001 }
1002 }
1003
1004 /**
1005 * Descending iterator for LinkedBlockingDeque
1006 */
1007 private class DescendingItr extends AbstractItr {
1008 void advance() {
1009 final ReentrantLock lock = LinkedBlockingDeque.this .lock;
1010 lock.lock();
1011 try {
1012 next = (next == null) ? last : next.prev;
1013 nextItem = (next == null) ? null : next.item;
1014 } finally {
1015 lock.unlock();
1016 }
1017 }
1018 }
1019
1020 /**
1021 * Save the state of this deque to a stream (that is, serialize it).
1022 *
1023 * @serialData The capacity (int), followed by elements (each an
1024 * <tt>Object</tt>) in the proper order, followed by a null
1025 * @param s the stream
1026 */
1027 private void writeObject(java.io.ObjectOutputStream s)
1028 throws java.io.IOException {
1029 lock.lock();
1030 try {
1031 // Write out capacity and any hidden stuff
1032 s.defaultWriteObject();
1033 // Write out all elements in the proper order.
1034 for (Node<E> p = first; p != null; p = p.next)
1035 s.writeObject(p.item);
1036 // Use trailing null as sentinel
1037 s.writeObject(null);
1038 } finally {
1039 lock.unlock();
1040 }
1041 }
1042
1043 /**
1044 * Reconstitute this deque from a stream (that is,
1045 * deserialize it).
1046 * @param s the stream
1047 */
1048 private void readObject(java.io.ObjectInputStream s)
1049 throws java.io.IOException, ClassNotFoundException {
1050 s.defaultReadObject();
1051 count = 0;
1052 first = null;
1053 last = null;
1054 // Read in all elements and place in queue
1055 for (;;) {
1056 E item = (E) s.readObject();
1057 if (item == null)
1058 break;
1059 add(item);
1060 }
1061 }
1062
1063 }
|