LinkedBlockingDeque


1   /*
2    * @(#)LinkedBlockingDeque.java 1.4 06/04/21
3    *
4    * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5    * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6    */
7   
8   package java.util.concurrent;
9   import java.util.*;
10  import java.util.concurrent.locks.*;
11  
12  /**
13   * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
14   * linked nodes.
15   *
16   * <p> The optional capacity bound constructor argument serves as a
17   * way to prevent excessive expansion. The capacity, if unspecified,
18   * is equal to {@link Integer#MAX_VALUE}.  Linked nodes are
19   * dynamically created upon each insertion unless this would bring the
20   * deque above capacity.
21   *
22   * <p>Most operations run in constant time (ignoring time spent
23   * blocking).  Exceptions include {@link #remove(Object) remove},
24   * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link
25   * #removeLastOccurrence removeLastOccurrence}, {@link #contains
26   * contains}, {@link #iterator iterator.remove()}, and the bulk
27   * operations, all of which run in linear time.
28   *
29   * <p>This class and its iterator implement all of the
30   * <em>optional</em> methods of the {@link Collection} and {@link
31   * Iterator} interfaces.
32   *
33   * <p>This class is a member of the
34   * <a HREF="{@docRoot}/../technotes/guides/collections/index.html">
35   * Java Collections Framework</a>.
36   *
37   * @since 1.6
38   * @author  Doug Lea
39   * @param <E> the type of elements held in this collection
40   */
41  public class LinkedBlockingDeque<E>
42      extends AbstractQueue<E>
43      implements BlockingDeque  <E>,  java.io.Serializable   {
44  
45      /*
46       * Implemented as a simple doubly-linked list protected by a
47       * single lock and using conditions to manage blocking.
48       */
49  
50      /*
51       * We have "diamond" multiple interface/abstract class inheritance
52       * here, and that introduces ambiguities. Often we want the
53       * BlockingDeque javadoc combined with the AbstractQueue
54       * implementation, so a lot of method specs are duplicated here.
55       */
56  
57      private static final long serialVersionUID = -387911632671998426L;
58  
59      /** Doubly-linked list node class */
60      static final class Node<E> {
61      E item;
62          Node<E> prev;
63          Node<E> next;
64          Node(E x, Node<E> p, Node<E> n) {
65              item = x;
66              prev = p;
67              next = n;
68          }
69      }
70  
71      /** Pointer to first node */
72      private transient Node<E> first;
73      /** Pointer to last node */
74      private transient Node<E> last;
75      /** Number of items in the deque */
76      private transient int count;
77      /** Maximum number of items in the deque */
78      private final int capacity;
79      /** Main lock guarding all access */
80      private final ReentrantLock lock = new ReentrantLock();
81      /** Condition for waiting takes */
82      private final Condition notEmpty = lock.newCondition();
83      /** Condition for waiting puts */
84      private final Condition notFull = lock.newCondition();
85  
86      /**
87       * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
88       * {@link Integer#MAX_VALUE}.
89       */
90      public LinkedBlockingDeque() {
91          this(Integer.MAX_VALUE);
92      }
93  
94      /**
95       * Creates a <tt>LinkedBlockingDeque</tt> with the given (fixed) capacity.
96       *
97       * @param capacity the capacity of this deque
98       * @throws IllegalArgumentException if <tt>capacity</tt> is less than 1
99       */
100     public LinkedBlockingDeque(int capacity) {
101         if (capacity <= 0) throw new IllegalArgumentException  ();
102         this.capacity = capacity;
103     }
104 
105     /**
106      * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
107      * {@link Integer#MAX_VALUE}, initially containing the elements of
108      * the given collection, added in traversal order of the
109      * collection's iterator.
110      *
111      * @param c the collection of elements to initially contain
112      * @throws NullPointerException if the specified collection or any
113      *         of its elements are null
114      */
115     public LinkedBlockingDeque(Collection<? extends E> c) {
116         this(Integer.MAX_VALUE);
117         for (E e : c)
118             add(e);
119     }
120 
121 
122     // Basic linking and unlinking operations, called only while holding lock
123 
124     /**
125      * Links e as first element, or returns false if full.
126      */
127     private boolean linkFirst(E e) {
128         if (count >= capacity)
129             return false;
130         ++count;
131         Node<E> f = first;
132         Node<E> x = new Node<E>(e, null, f);
133         first = x;
134         if (last == null)
135             last = x;
136         else
137             f.prev = x;
138         notEmpty.signal();
139         return true;
140     }
141 
142     /**
143      * Links e as last element, or returns false if full.
144      */
145     private boolean linkLast(E e) {
146         if (count >= capacity)
147             return false;
148         ++count;
149         Node<E> l = last;
150         Node<E> x = new Node<E>(e, l, null);
151         last = x;
152         if (first == null)
153             first = x;
154         else
155             l.next = x;
156         notEmpty.signal();
157         return true;
158     }
159 
160     /**
161      * Removes and returns first element, or null if empty.
162      */
163     private E unlinkFirst() {
164         Node<E> f = first;
165         if (f == null)
166             return null;
167         Node<E> n = f.next;
168         first = n;
169         if (n == null)
170             last = null;
171         else
172             n.prev = null;
173         --count;
174         notFull.signal();
175         return f.item;
176     }
177 
178     /**
179      * Removes and returns last element, or null if empty.
180      */
181     private E unlinkLast() {
182         Node<E> l = last;
183         if (l == null)
184             return null;
185         Node<E> p = l.prev;
186         last = p;
187         if (p == null)
188             first = null;
189         else
190             p.next = null;
191         --count;
192         notFull.signal();
193         return l.item;
194     }
195 
196     /**
197      * Unlink e
198      */
199     private void unlink(Node<E> x) {
200         Node<E> p = x.prev;
201         Node<E> n = x.next;
202         if (p == null) {
203             if (n == null)
204                 first = last = null;
205             else {
206                 n.prev = null;
207                 first = n;
208             }
209         } else if (n == null) {
210             p.next = null;
211             last = p;
212         } else {
213             p.next = n;
214             n.prev = p;
215         }
216         --count;
217         notFull.signalAll();
218     }
219 
220     // BlockingDeque methods
221 
222     /**
223      * @throws IllegalStateException {@inheritDoc}
224      * @throws NullPointerException  {@inheritDoc}
225      */
226     public void addFirst(E e) {
227         if (!offerFirst(e))
228             throw new IllegalStateException  ("Deque full");
229     }
230 
231     /**
232      * @throws IllegalStateException {@inheritDoc}
233      * @throws NullPointerException  {@inheritDoc}
234      */
235     public void addLast(E e) {
236         if (!offerLast(e))
237             throw new IllegalStateException  ("Deque full");
238     }
239 
240     /**
241      * @throws NullPointerException {@inheritDoc}
242      */
243     public boolean offerFirst(E e) {
244         if (e == null) throw new NullPointerException  ();
245         lock.lock();
246         try {
247             return linkFirst(e);
248         } finally {
249             lock.unlock();
250         }
251     }
252 
253     /**
254      * @throws NullPointerException {@inheritDoc}
255      */
256     public boolean offerLast(E e) {
257         if (e == null) throw new NullPointerException  ();
258         lock.lock();
259         try {
260             return linkLast(e);
261         } finally {
262             lock.unlock();
263         }
264     }
265 
266     /**
267      * @throws NullPointerException {@inheritDoc}
268      * @throws InterruptedException {@inheritDoc}
269      */
270     public void putFirst(E e) throws InterruptedException   {
271         if (e == null) throw new NullPointerException  ();
272         lock.lock();
273         try {
274             while (!linkFirst(e))
275                 notFull.await();
276         } finally {
277             lock.unlock();
278         }
279     }
280 
281     /**
282      * @throws NullPointerException {@inheritDoc}
283      * @throws InterruptedException {@inheritDoc}
284      */
285     public void putLast(E e) throws InterruptedException   {
286         if (e == null) throw new NullPointerException  ();
287         lock.lock();
288         try {
289             while (!linkLast(e))
290                 notFull.await();
291         } finally {
292             lock.unlock();
293         }
294     }
295 
296     /**
297      * @throws NullPointerException {@inheritDoc}
298      * @throws InterruptedException {@inheritDoc}
299      */
300     public boolean offerFirst(E e, long timeout, TimeUnit   unit)
301         throws InterruptedException   {
302         if (e == null) throw new NullPointerException  ();
303     long nanos = unit.toNanos(timeout);
304         lock.lockInterruptibly();
305         try {
306             for (;;) {
307                 if (linkFirst(e))
308                     return true;
309                 if (nanos <= 0)
310                     return false;
311                 nanos = notFull.awaitNanos(nanos);
312             }
313         } finally {
314             lock.unlock();
315         }
316     }
317 
318     /**
319      * @throws NullPointerException {@inheritDoc}
320      * @throws InterruptedException {@inheritDoc}
321      */
322     public boolean offerLast(E e, long timeout, TimeUnit   unit)
323         throws InterruptedException   {
324         if (e == null) throw new NullPointerException  ();
325     long nanos = unit.toNanos(timeout);
326         lock.lockInterruptibly();
327         try {
328             for (;;) {
329                 if (linkLast(e))
330                     return true;
331                 if (nanos <= 0)
332                     return false;
333                 nanos = notFull.awaitNanos(nanos);
334             }
335         } finally {
336             lock.unlock();
337         }
338     }
339 
340     /**
341      * @throws NoSuchElementException {@inheritDoc}
342      */
343     public E removeFirst() {
344         E x = pollFirst();
345         if (x == null) throw new NoSuchElementException();
346         return x;
347     }
348 
349     /**
350      * @throws NoSuchElementException {@inheritDoc}
351      */
352     public E removeLast() {
353         E x = pollLast();
354         if (x == null) throw new NoSuchElementException();
355         return x;
356     }
357 
358     public E pollFirst() {
359         lock.lock();
360         try {
361             return unlinkFirst();
362         } finally {
363             lock.unlock();
364         }
365     }
366 
367     public E pollLast() {
368         lock.lock();
369         try {
370             return unlinkLast();
371         } finally {
372             lock.unlock();
373         }
374     }
375 
376     public E takeFirst() throws InterruptedException   {
377         lock.lock();
378         try {
379             E x;
380             while ( (x = unlinkFirst()) == null)
381                 notEmpty.await();
382             return x;
383         } finally {
384             lock.unlock();
385         }
386     }
387 
388     public E takeLast() throws InterruptedException   {
389         lock.lock();
390         try {
391             E x;
392             while ( (x = unlinkLast()) == null)
393                 notEmpty.await();
394             return x;
395         } finally {
396             lock.unlock();
397         }
398     }
399 
400     public E pollFirst(long timeout, TimeUnit   unit)
401         throws InterruptedException   {
402     long nanos = unit.toNanos(timeout);
403         lock.lockInterruptibly();
404         try {
405             for (;;) {
406                 E x = unlinkFirst();
407                 if (x != null)
408                     return x;
409                 if (nanos <= 0)
410                     return null;
411                 nanos = notEmpty.awaitNanos(nanos);
412             }
413         } finally {
414             lock.unlock();
415         }
416     }
417 
418     public E pollLast(long timeout, TimeUnit   unit)
419         throws InterruptedException   {
420     long nanos = unit.toNanos(timeout);
421         lock.lockInterruptibly();
422         try {
423             for (;;) {
424                 E x = unlinkLast();
425                 if (x != null)
426                     return x;
427                 if (nanos <= 0)
428                     return null;
429                 nanos = notEmpty.awaitNanos(nanos);
430             }
431         } finally {
432             lock.unlock();
433         }
434     }
435 
436     /**
437      * @throws NoSuchElementException {@inheritDoc}
438      */
439     public E getFirst() {
440         E x = peekFirst();
441         if (x == null) throw new NoSuchElementException();
442         return x;
443     }
444 
445     /**
446      * @throws NoSuchElementException {@inheritDoc}
447      */
448     public E getLast() {
449         E x = peekLast();
450         if (x == null) throw new NoSuchElementException();
451         return x;
452     }
453 
454     public E peekFirst() {
455         lock.lock();
456         try {
457             return (first == null) ? null : first.item;
458         } finally {
459             lock.unlock();
460         }
461     }
462 
463     public E peekLast() {
464         lock.lock();
465         try {
466             return (last == null) ? null : last.item;
467         } finally {
468             lock.unlock();
469         }
470     }
471 
472     public boolean removeFirstOccurrence(Object   o) {
473         if (o == null) return false;
474         lock.lock();
475         try {
476             for (Node<E> p = first; p != null; p = p.next) {
477                 if (o.equals(p.item)) {
478                     unlink(p);
479                     return true;
480                 }
481             }
482             return false;
483         } finally {
484             lock.unlock();
485         }
486     }
487 
488     public boolean removeLastOccurrence(Object   o) {
489         if (o == null) return false;
490         lock.lock();
491         try {
492             for (Node<E> p = last; p != null; p = p.prev) {
493                 if (o.equals(p.item)) {
494                     unlink(p);
495                     return true;
496                 }
497             }
498             return false;
499         } finally {
500             lock.unlock();
501         }
502     }
503 
504     // BlockingQueue methods
505 
506     /**
507      * Inserts the specified element at the end of this deque unless it would
508      * violate capacity restrictions.  When using a capacity-restricted deque,
509      * it is generally preferable to use method {@link #offer(Object) offer}.
510      *
511      * <p>This method is equivalent to {@link #addLast}.
512      *
513      * @throws IllegalStateException if the element cannot be added at this
514      *         time due to capacity restrictions
515      * @throws NullPointerException if the specified element is null
516      */
517     public boolean add(E e) {
518     addLast(e);
519     return true;
520     }
521 
522     /**
523      * @throws NullPointerException if the specified element is null
524      */
525     public boolean offer(E e) {
526     return offerLast(e);
527     }
528 
529     /**
530      * @throws NullPointerException {@inheritDoc}
531      * @throws InterruptedException {@inheritDoc}
532      */
533     public void put(E e) throws InterruptedException   {
534     putLast(e);
535     }
536 
537     /**
538      * @throws NullPointerException {@inheritDoc}
539      * @throws InterruptedException {@inheritDoc}
540      */
541     public boolean offer(E e, long timeout, TimeUnit   unit)
542         throws InterruptedException   {
543     return offerLast(e, timeout, unit);
544     }
545 
546     /**
547      * Retrieves and removes the head of the queue represented by this deque.
548      * This method differs from {@link #poll poll} only in that it throws an
549      * exception if this deque is empty.
550      *
551      * <p>This method is equivalent to {@link #removeFirst() removeFirst}.
552      *
553      * @return the head of the queue represented by this deque
554      * @throws NoSuchElementException if this deque is empty
555      */
556     public E remove() {
557     return removeFirst();
558     }
559 
560     public E poll() {
561     return pollFirst();
562     }
563 
564     public E take() throws InterruptedException   {
565     return takeFirst();
566     }
567 
568     public E poll(long timeout, TimeUnit   unit) throws InterruptedException   {
569     return pollFirst(timeout, unit);
570     }
571 
572     /**
573      * Retrieves, but does not remove, the head of the queue represented by
574      * this deque.  This method differs from {@link #peek peek} only in that
575      * it throws an exception if this deque is empty.
576      *
577      * <p>This method is equivalent to {@link #getFirst() getFirst}.
578      *
579      * @return the head of the queue represented by this deque
580      * @throws NoSuchElementException if this deque is empty
581      */
582     public E element() {
583     return getFirst();
584     }
585 
586     public E peek() {
587     return peekFirst();
588     }
589 
590     /**
591      * Returns the number of additional elements that this deque can ideally
592      * (in the absence of memory or resource constraints) accept without
593      * blocking. This is always equal to the initial capacity of this deque
594      * less the current <tt>size</tt> of this deque.
595      *
596      * <p>Note that you <em>cannot</em> always tell if an attempt to insert
597      * an element will succeed by inspecting <tt>remainingCapacity</tt>
598      * because it may be the case that another thread is about to
599      * insert or remove an element.
600      */
601     public int remainingCapacity() {
602         lock.lock();
603         try {
604             return capacity - count;
605         } finally {
606             lock.unlock();
607         }
608     }
609 
610     /**
611      * @throws UnsupportedOperationException {@inheritDoc}
612      * @throws ClassCastException            {@inheritDoc}
613      * @throws NullPointerException          {@inheritDoc}
614      * @throws IllegalArgumentException      {@inheritDoc}
615      */
616     public int drainTo(Collection<? super E> c) {
617         if (c == null)
618             throw new NullPointerException  ();
619         if (c == this)
620             throw new IllegalArgumentException  ();
621         lock.lock();
622         try {
623             for (Node<E> p = first; p != null; p = p.next)
624                 c.add(p.item);
625             int n = count;
626             count = 0;
627             first = last = null;
628             notFull.signalAll();
629             return n;
630         } finally {
631             lock.unlock();
632         }
633     }
634 
635     /**
636      * @throws UnsupportedOperationException {@inheritDoc}
637      * @throws ClassCastException            {@inheritDoc}
638      * @throws NullPointerException          {@inheritDoc}
639      * @throws IllegalArgumentException      {@inheritDoc}
640      */
641     public int drainTo(Collection<? super E> c, int maxElements) {
642         if (c == null)
643             throw new NullPointerException  ();
644         if (c == this)
645             throw new IllegalArgumentException  ();
646         lock.lock();
647         try {
648             int n = 0;
649             while (n < maxElements && first != null) {
650                 c.add(first.item);
651                 first.prev = null;
652                 first = first.next;
653                 --count;
654                 ++n;
655             }
656             if (first == null)
657                 last = null;
658             notFull.signalAll();
659             return n;
660         } finally {
661             lock.unlock();
662         }
663     }
664 
665     // Stack methods
666 
667     /**
668      * @throws IllegalStateException {@inheritDoc}
669      * @throws NullPointerException  {@inheritDoc}
670      */
671     public void push(E e) {
672     addFirst(e);
673     }
674 
675     /**
676      * @throws NoSuchElementException {@inheritDoc}
677      */
678     public E pop() {
679     return removeFirst();
680     }
681 
682     // Collection methods
683 
684     /**
685      * Removes the first occurrence of the specified element from this deque.
686      * If the deque does not contain the element, it is unchanged.
687      * More formally, removes the first element <tt>e</tt> such that
688      * <tt>o.equals(e)</tt> (if such an element exists).
689      * Returns <tt>true</tt> if this deque contained the specified element
690      * (or equivalently, if this deque changed as a result of the call).
691      *
692      * <p>This method is equivalent to
693      * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}.
694      *
695      * @param o element to be removed from this deque, if present
696      * @return <tt>true</tt> if this deque changed as a result of the call
697      */
698     public boolean remove(Object   o) {
699     return removeFirstOccurrence(o);
700     }
701 
702     /**
703      * Returns the number of elements in this deque.
704      *
705      * @return the number of elements in this deque
706      */
707     public int size() {
708         lock.lock();
709         try {
710             return count;
711         } finally {
712             lock.unlock();
713         }
714     }
715 
716     /**
717      * Returns <tt>true</tt> if this deque contains the specified element.
718      * More formally, returns <tt>true</tt> if and only if this deque contains
719      * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
720      *
721      * @param o object to be checked for containment in this deque
722      * @return <tt>true</tt> if this deque contains the specified element
723      */
724     public boolean contains(Object   o) {
725         if (o == null) return false;
726         lock.lock();
727         try {
728             for (Node<E> p = first; p != null; p = p.next)
729                 if (o.equals(p.item))
730                     return true;
731             return false;
732         } finally {
733             lock.unlock();
734         }
735     }
736 
737     /**
738      * Variant of removeFirstOccurrence needed by iterator.remove.
739      * Searches for the node, not its contents.
740      */
741     boolean removeNode(Node<E> e) {
742         lock.lock();
743         try {
744             for (Node<E> p = first; p != null; p = p.next) {
745                 if (p == e) {
746                     unlink(p);
747                     return true;
748                 }
749             }
750             return false;
751         } finally {
752             lock.unlock();
753         }
754     }
755 
756     /**
757      * Returns an array containing all of the elements in this deque, in
758      * proper sequence (from first to last element).
759      *
760      * <p>The returned array will be "safe" in that no references to it are
761      * maintained by this deque.  (In other words, this method must allocate
762      * a new array).  The caller is thus free to modify the returned array.
763      *
764      * <p>This method acts as bridge between array-based and collection-based
765      * APIs.
766      *
767      * @return an array containing all of the elements in this deque
768      */
769     public Object  [] toArray() {
770         lock.lock();
771         try {
772             Object  [] a = new Object  [count];
773             int k = 0;
774             for (Node<E> p = first; p != null; p = p.next)
775                 a[k++] = p.item;
776             return a;
777         } finally {
778             lock.unlock();
779         }
780     }
781 
782     /**
783      * Returns an array containing all of the elements in this deque, in
784      * proper sequence; the runtime type of the returned array is that of
785      * the specified array.  If the deque fits in the specified array, it
786      * is returned therein.  Otherwise, a new array is allocated with the
787      * runtime type of the specified array and the size of this deque.
788      *
789      * <p>If this deque fits in the specified array with room to spare
790      * (i.e., the array has more elements than this deque), the element in
791      * the array immediately following the end of the deque is set to
792      * <tt>null</tt>.
793      *
794      * <p>Like the {@link #toArray()} method, this method acts as bridge between
795      * array-based and collection-based APIs.  Further, this method allows
796      * precise control over the runtime type of the output array, and may,
797      * under certain circumstances, be used to save allocation costs.
798      *
799      * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
800      * The following code can be used to dump the deque into a newly
801      * allocated array of <tt>String</tt>:
802      *
803      * <pre>
804      *     String[] y = x.toArray(new String[0]);</pre>
805      *
806      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
807      * <tt>toArray()</tt>.
808      *
809      * @param a the array into which the elements of the deque are to
810      *          be stored, if it is big enough; otherwise, a new array of the
811      *          same runtime type is allocated for this purpose
812      * @return an array containing all of the elements in this deque
813      * @throws ArrayStoreException if the runtime type of the specified array
814      *         is not a supertype of the runtime type of every element in
815      *         this deque
816      * @throws NullPointerException if the specified array is null
817      */
818     public <T> T[] toArray(T[] a) {
819         lock.lock();
820         try {
821             if (a.length < count)
822                 a = (T[])java.lang.reflect.Array.newInstance(
823                     a.getClass().getComponentType(),
824                     count
825                     );
826 
827             int k = 0;
828             for (Node<E> p = first; p != null; p = p.next)
829                 a[k++] = (T)p.item;
830             if (a.length > k)
831                 a[k] = null;
832             return a;
833         } finally {
834             lock.unlock();
835         }
836     }
837 
838     public String   toString() {
839         lock.lock();
840         try {
841             return super.toString();
842         } finally {
843             lock.unlock();
844         }
845     }
846 
847     /**
848      * Atomically removes all of the elements from this deque.
849      * The deque will be empty after this call returns.
850      */
851     public void clear() {
852         lock.lock();
853         try {
854             first = last = null;
855             count = 0;
856             notFull.signalAll();
857         } finally {
858             lock.unlock();
859         }
860     }
861 
862     /**
863      * Returns an iterator over the elements in this deque in proper sequence.
864      * The elements will be returned in order from first (head) to last (tail).
865      * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
866      * will never throw {@link ConcurrentModificationException},
867      * and guarantees to traverse elements as they existed upon
868      * construction of the iterator, and may (but is not guaranteed to)
869      * reflect any modifications subsequent to construction.
870      *
871      * @return an iterator over the elements in this deque in proper sequence
872      */
873     public Iterator<E> iterator() {
874         return new Itr();
875     }
876 
877     /**
878      * Returns an iterator over the elements in this deque in reverse
879      * sequential order.  The elements will be returned in order from
880      * last (tail) to first (head).
881      * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
882      * will never throw {@link ConcurrentModificationException},
883      * and guarantees to traverse elements as they existed upon
884      * construction of the iterator, and may (but is not guaranteed to)
885      * reflect any modifications subsequent to construction.
886      */
887     public Iterator<E> descendingIterator() {
888         return new DescendingItr();
889     }
890 
891     /**
892      * Base class for Iterators for LinkedBlockingDeque
893      */
894     private abstract class AbstractItr implements Iterator<E> {
895         /**
896          * The next node to return in next
897          */
898          Node<E> next;
899 
900         /**
901          * nextItem holds on to item fields because once we claim that
902          * an element exists in hasNext(), we must return item read
903          * under lock (in advance()) even if it was in the process of
904          * being removed when hasNext() was called.
905          */
906         E nextItem;
907 
908         /**
909          * Node returned by most recent call to next. Needed by remove.
910          * Reset to null if this element is deleted by a call to remove.
911          */
912         private Node<E> lastRet;
913 
914         AbstractItr() {
915             advance(); // set to initial position
916         }
917 
918         /**
919          * Advances next, or if not yet initialized, sets to first node.
920          * Implemented to move forward vs backward in the two subclasses.
921          */
922         abstract void advance();
923 
924         public boolean hasNext() {
925             return next != null;
926         }
927 
928         public E next() {
929             if (next == null)
930                 throw new NoSuchElementException();
931             lastRet = next;
932             E x = nextItem;
933             advance();
934             return x;
935         }
936 
937         public void remove() {
938             Node<E> n = lastRet;
939             if (n == null)
940                 throw new IllegalStateException  ();
941             lastRet = null;
942             // Note: removeNode rescans looking for this node to make
943             // sure it was not already removed. Otherwise, trying to
944             // re-remove could corrupt list.
945             removeNode(n);
946         }
947     }
948 
949     /** Forward iterator */
950     private class Itr extends AbstractItr {
951         void advance() {
952             final ReentrantLock lock = LinkedBlockingDeque.this.lock;
953             lock.lock();
954             try {
955                 next = (next == null)? first : next.next;
956                 nextItem = (next == null)? null : next.item;
957             } finally {
958                 lock.unlock();
959             }
960         }
961     }
962 
963     /**
964      * Descending iterator for LinkedBlockingDeque
965      */
966     private class DescendingItr extends AbstractItr {
967         void advance() {
968             final ReentrantLock lock = LinkedBlockingDeque.this.lock;
969             lock.lock();
970             try {
971                 next = (next == null)? last : next.prev;
972                 nextItem = (next == null)? null : next.item;
973             } finally {
974                 lock.unlock();
975             }
976         }
977     }
978 
979     /**
980      * Save the state of this deque to a stream (that is, serialize it).
981      *
982      * @serialData The capacity (int), followed by elements (each an
983      * <tt>Object</tt>) in the proper order, followed by a null
984      * @param s the stream
985      */
986     private void writeObject(java.io.ObjectOutputStream   s)
987         throws java.io.IOException   {
988         lock.lock();
989         try {
990             // Write out capacity and any hidden stuff
991             s.defaultWriteObject();
992             // Write out all elements in the proper order.
993             for (Node<E> p = first; p != null; p = p.next)
994                 s.writeObject(p.item);
995             // Use trailing null as sentinel
996             s.writeObject(null);
997         } finally {
998             lock.unlock();
999         }
1000    }
1001
1002    /**
1003     * Reconstitute this deque from a stream (that is,
1004     * deserialize it).
1005     * @param s the stream
1006     */
1007    private void readObject(java.io.ObjectInputStream   s)
1008        throws java.io.IOException  , ClassNotFoundException   {
1009        s.defaultReadObject();
1010        count = 0;
1011        first = null;
1012        last = null;
1013        // Read in all elements and place in queue
1014        for (;;) {
1015            E item = (E)s.readObject();
1016            if (item == null)
1017                break;
1018            add(item);
1019        }
1020    }
1021
1022}
1023
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags