1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.  Oracle designates this
   7  * particular file as subject to the "Classpath" exception as provided
   8  * by Oracle in the LICENSE file that accompanied this code.
   9  *
  10  * This code is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * version 2 for more details (a copy is included in the LICENSE file that
  14  * accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License version
  17  * 2 along with this work; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  19  *
  20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  21  * or visit www.oracle.com if you need additional information or have any
  22  * questions.
  23  */
  24 
  25 /*
  26  * This file is available under and governed by the GNU General Public
  27  * License version 2 only, as published by the Free Software Foundation.
  28  * However, the following notice accompanied the original version of this
  29  * file:
  30  *
  31  * Written by Doug Lea with assistance from members of JCP JSR-166
  32  * Expert Group and released to the public domain, as explained at
  33  * http://creativecommons.org/publicdomain/zero/1.0/
  34  */
  35 
  36 package java.util.concurrent;
  37 import java.util.concurrent.locks.*;
  38 import java.util.*;
  39 
  40 /**
  41  * A bounded {@linkplain BlockingQueue blocking queue} backed by an
  42  * array.  This queue orders elements FIFO (first-in-first-out).  The
  43  * <em>head</em> of the queue is that element that has been on the
  44  * queue the longest time.  The <em>tail</em> of the queue is that
  45  * element that has been on the queue the shortest time. New elements
  46  * are inserted at the tail of the queue, and the queue retrieval
  47  * operations obtain elements at the head of the queue.
  48  *
  49  * <p>This is a classic &quot;bounded buffer&quot;, in which a
  50  * fixed-sized array holds elements inserted by producers and
  51  * extracted by consumers.  Once created, the capacity cannot be
  52  * changed.  Attempts to {@code put} an element into a full queue
  53  * will result in the operation blocking; attempts to {@code take} an
  54  * element from an empty queue will similarly block.
  55  *
  56  * <p>This class supports an optional fairness policy for ordering
  57  * waiting producer and consumer threads.  By default, this ordering
  58  * is not guaranteed. However, a queue constructed with fairness set
  59  * to {@code true} grants threads access in FIFO order. Fairness
  60  * generally decreases throughput but reduces variability and avoids
  61  * starvation.
  62  *
  63  * <p>This class and its iterator implement all of the
  64  * <em>optional</em> methods of the {@link Collection} and {@link
  65  * Iterator} interfaces.
  66  *
  67  * <p>This class is a member of the
  68  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  69  * Java Collections Framework</a>.
  70  *
  71  * @since 1.5
  72  * @author Doug Lea
  73  * @param <E> the type of elements held in this collection
  74  */
  75 public class ArrayBlockingQueue<E> extends AbstractQueue<E>
  76         implements BlockingQueue<E>, java.io.Serializable {
  77 
  78     /**
  79      * Serialization ID. This class relies on default serialization
  80      * even for the items array, which is default-serialized, even if
  81      * it is empty. Otherwise it could not be declared final, which is
  82      * necessary here.
  83      */
  84     private static final long serialVersionUID = -817911632652898426L;
  85 
  86     /** The queued items */
  87     final Object[] items;
  88 
  89     /** items index for next take, poll, peek or remove */
  90     int takeIndex;
  91 
  92     /** items index for next put, offer, or add */
  93     int putIndex;
  94 
  95     /** Number of elements in the queue */
  96     int count;
  97 
  98     /*
  99      * Concurrency control uses the classic two-condition algorithm
 100      * found in any textbook.
 101      */
 102 
 103     /** Main lock guarding all access */
 104     final ReentrantLock lock;
 105     /** Condition for waiting takes */
 106     private final Condition notEmpty;
 107     /** Condition for waiting puts */
 108     private final Condition notFull;
 109 
 110     // Internal helper methods
 111 
 112     /**
 113      * Circularly increment i.
 114      */
 115     final int inc(int i) {
 116         return (++i == items.length) ? 0 : i;
 117     }
 118 
 119     /**
 120      * Circularly decrement i.
 121      */
 122     final int dec(int i) {
 123         return ((i == 0) ? items.length : i) - 1;
 124     }
 125 
 126     @SuppressWarnings("unchecked")
 127     static <E> E cast(Object item) {
 128         return (E) item;
 129     }
 130 
 131     /**
 132      * Returns item at index i.
 133      */
 134     @SuppressWarnings("unchecked")
 135     final E itemAt(int i) {
 136         return (E) items[i];
 137     }
 138 
 139     /**
 140      * Throws NullPointerException if argument is null.
 141      *
 142      * @param v the element
 143      */
 144     private static void checkNotNull(Object v) {
 145         if (v == null)
 146             throw new NullPointerException();
 147     }
 148 
 149     /**
 150      * Inserts element at current put position, advances, and signals.
 151      * Call only when holding lock.
 152      */
 153     private void insert(E x) {
 154         items[putIndex] = x;
 155         putIndex = inc(putIndex);
 156         ++count;
 157         notEmpty.signal();
 158     }
 159 
 160     /**
 161      * Extracts element at current take position, advances, and signals.
 162      * Call only when holding lock.
 163      */
 164     private E extract() {
 165         final Object[] items = this.items;
 166         @SuppressWarnings("unchecked") E x = (E) items[takeIndex];
 167         items[takeIndex] = null;
 168         takeIndex = inc(takeIndex);
 169         --count;
 170         notFull.signal();
 171         return x;
 172     }
 173 
 174     /**
 175      * Deletes item at position i.
 176      * Utility for remove and iterator.remove.
 177      * Call only when holding lock.
 178      */
 179     void removeAt(int i) {
 180         final Object[] items = this.items;
 181         // if removing front item, just advance
 182         if (i == takeIndex) {
 183             items[takeIndex] = null;
 184             takeIndex = inc(takeIndex);
 185         } else {
 186             // slide over all others up through putIndex.
 187             for (;;) {
 188                 int nexti = inc(i);
 189                 if (nexti != putIndex) {
 190                     items[i] = items[nexti];
 191                     i = nexti;
 192                 } else {
 193                     items[i] = null;
 194                     putIndex = i;
 195                     break;
 196                 }
 197             }
 198         }
 199         --count;
 200         notFull.signal();
 201     }
 202 
 203     /**
 204      * Creates an {@code ArrayBlockingQueue} with the given (fixed)
 205      * capacity and default access policy.
 206      *
 207      * @param capacity the capacity of this queue
 208      * @throws IllegalArgumentException if {@code capacity < 1}
 209      */
 210     public ArrayBlockingQueue(int capacity) {
 211         this(capacity, false);
 212     }
 213 
 214     /**
 215      * Creates an {@code ArrayBlockingQueue} with the given (fixed)
 216      * capacity and the specified access policy.
 217      *
 218      * @param capacity the capacity of this queue
 219      * @param fair if {@code true} then queue accesses for threads blocked
 220      *        on insertion or removal, are processed in FIFO order;
 221      *        if {@code false} the access order is unspecified.
 222      * @throws IllegalArgumentException if {@code capacity < 1}
 223      */
 224     public ArrayBlockingQueue(int capacity, boolean fair) {
 225         if (capacity <= 0)
 226             throw new IllegalArgumentException();
 227         this.items = new Object[capacity];
 228         lock = new ReentrantLock(fair);
 229         notEmpty = lock.newCondition();
 230         notFull =  lock.newCondition();
 231     }
 232 
 233     /**
 234      * Creates an {@code ArrayBlockingQueue} with the given (fixed)
 235      * capacity, the specified access policy and initially containing the
 236      * elements of the given collection,
 237      * added in traversal order of the collection's iterator.
 238      *
 239      * @param capacity the capacity of this queue
 240      * @param fair if {@code true} then queue accesses for threads blocked
 241      *        on insertion or removal, are processed in FIFO order;
 242      *        if {@code false} the access order is unspecified.
 243      * @param c the collection of elements to initially contain
 244      * @throws IllegalArgumentException if {@code capacity} is less than
 245      *         {@code c.size()}, or less than 1.
 246      * @throws NullPointerException if the specified collection or any
 247      *         of its elements are null
 248      */
 249     public ArrayBlockingQueue(int capacity, boolean fair,
 250                               Collection<? extends E> c) {
 251         this(capacity, fair);
 252 
 253         final ReentrantLock lock = this.lock;
 254         lock.lock(); // Lock only for visibility, not mutual exclusion
 255         try {
 256             int i = 0;
 257             try {
 258                 for (E e : c) {
 259                     checkNotNull(e);
 260                     items[i++] = e;
 261                 }
 262             } catch (ArrayIndexOutOfBoundsException ex) {
 263                 throw new IllegalArgumentException();
 264             }
 265             count = i;
 266             putIndex = (i == capacity) ? 0 : i;
 267         } finally {
 268             lock.unlock();
 269         }
 270     }
 271 
 272     /**
 273      * Inserts the specified element at the tail of this queue if it is
 274      * possible to do so immediately without exceeding the queue's capacity,
 275      * returning {@code true} upon success and throwing an
 276      * {@code IllegalStateException} if this queue is full.
 277      *
 278      * @param e the element to add
 279      * @return {@code true} (as specified by {@link Collection#add})
 280      * @throws IllegalStateException if this queue is full
 281      * @throws NullPointerException if the specified element is null
 282      */
 283     public boolean add(E e) {
 284         return super.add(e);
 285     }
 286 
 287     /**
 288      * Inserts the specified element at the tail of this queue if it is
 289      * possible to do so immediately without exceeding the queue's capacity,
 290      * returning {@code true} upon success and {@code false} if this queue
 291      * is full.  This method is generally preferable to method {@link #add},
 292      * which can fail to insert an element only by throwing an exception.
 293      *
 294      * @throws NullPointerException if the specified element is null
 295      */
 296     public boolean offer(E e) {
 297         checkNotNull(e);
 298         final ReentrantLock lock = this.lock;
 299         lock.lock();
 300         try {
 301             if (count == items.length)
 302                 return false;
 303             else {
 304                 insert(e);
 305                 return true;
 306             }
 307         } finally {
 308             lock.unlock();
 309         }
 310     }
 311 
 312     /**
 313      * Inserts the specified element at the tail of this queue, waiting
 314      * for space to become available if the queue is full.
 315      *
 316      * @throws InterruptedException {@inheritDoc}
 317      * @throws NullPointerException {@inheritDoc}
 318      */
 319     public void put(E e) throws InterruptedException {
 320         checkNotNull(e);
 321         final ReentrantLock lock = this.lock;
 322         lock.lockInterruptibly();
 323         try {
 324             while (count == items.length)
 325                 notFull.await();
 326             insert(e);
 327         } finally {
 328             lock.unlock();
 329         }
 330     }
 331 
 332     /**
 333      * Inserts the specified element at the tail of this queue, waiting
 334      * up to the specified wait time for space to become available if
 335      * the queue is full.
 336      *
 337      * @throws InterruptedException {@inheritDoc}
 338      * @throws NullPointerException {@inheritDoc}
 339      */
 340     public boolean offer(E e, long timeout, TimeUnit unit)
 341         throws InterruptedException {
 342 
 343         checkNotNull(e);
 344         long nanos = unit.toNanos(timeout);
 345         final ReentrantLock lock = this.lock;
 346         lock.lockInterruptibly();
 347         try {
 348             while (count == items.length) {
 349                 if (nanos <= 0)
 350                     return false;
 351                 nanos = notFull.awaitNanos(nanos);
 352             }
 353             insert(e);
 354             return true;
 355         } finally {
 356             lock.unlock();
 357         }
 358     }
 359 
 360     public E poll() {
 361         final ReentrantLock lock = this.lock;
 362         lock.lock();
 363         try {
 364             return (count == 0) ? null : extract();
 365         } finally {
 366             lock.unlock();
 367         }
 368     }
 369 
 370     public E take() throws InterruptedException {
 371         final ReentrantLock lock = this.lock;
 372         lock.lockInterruptibly();
 373         try {
 374             while (count == 0)
 375                 notEmpty.await();
 376             return extract();
 377         } finally {
 378             lock.unlock();
 379         }
 380     }
 381 
 382     public E poll(long timeout, TimeUnit unit) throws InterruptedException {
 383         long nanos = unit.toNanos(timeout);
 384         final ReentrantLock lock = this.lock;
 385         lock.lockInterruptibly();
 386         try {
 387             while (count == 0) {
 388                 if (nanos <= 0)
 389                     return null;
 390                 nanos = notEmpty.awaitNanos(nanos);
 391             }
 392             return extract();
 393         } finally {
 394             lock.unlock();
 395         }
 396     }
 397 
 398     public E peek() {
 399         final ReentrantLock lock = this.lock;
 400         lock.lock();
 401         try {
 402             return (count == 0) ? null : itemAt(takeIndex);
 403         } finally {
 404             lock.unlock();
 405         }
 406     }
 407 
 408     // this doc comment is overridden to remove the reference to collections
 409     // greater in size than Integer.MAX_VALUE
 410     /**
 411      * Returns the number of elements in this queue.
 412      *
 413      * @return the number of elements in this queue
 414      */
 415     public int size() {
 416         final ReentrantLock lock = this.lock;
 417         lock.lock();
 418         try {
 419             return count;
 420         } finally {
 421             lock.unlock();
 422         }
 423     }
 424 
 425     // this doc comment is a modified copy of the inherited doc comment,
 426     // without the reference to unlimited queues.
 427     /**
 428      * Returns the number of additional elements that this queue can ideally
 429      * (in the absence of memory or resource constraints) accept without
 430      * blocking. This is always equal to the initial capacity of this queue
 431      * less the current {@code size} of this queue.
 432      *
 433      * <p>Note that you <em>cannot</em> always tell if an attempt to insert
 434      * an element will succeed by inspecting {@code remainingCapacity}
 435      * because it may be the case that another thread is about to
 436      * insert or remove an element.
 437      */
 438     public int remainingCapacity() {
 439         final ReentrantLock lock = this.lock;
 440         lock.lock();
 441         try {
 442             return items.length - count;
 443         } finally {
 444             lock.unlock();
 445         }
 446     }
 447 
 448     /**
 449      * Removes a single instance of the specified element from this queue,
 450      * if it is present.  More formally, removes an element {@code e} such
 451      * that {@code o.equals(e)}, if this queue contains one or more such
 452      * elements.
 453      * Returns {@code true} if this queue contained the specified element
 454      * (or equivalently, if this queue changed as a result of the call).
 455      *
 456      * <p>Removal of interior elements in circular array based queues
 457      * is an intrinsically slow and disruptive operation, so should
 458      * be undertaken only in exceptional circumstances, ideally
 459      * only when the queue is known not to be accessible by other
 460      * threads.
 461      *
 462      * @param o element to be removed from this queue, if present
 463      * @return {@code true} if this queue changed as a result of the call
 464      */
 465     public boolean remove(Object o) {
 466         if (o == null) return false;
 467         final Object[] items = this.items;
 468         final ReentrantLock lock = this.lock;
 469         lock.lock();
 470         try {
 471             for (int i = takeIndex, k = count; k > 0; i = inc(i), k--) {
 472                 if (o.equals(items[i])) {
 473                     removeAt(i);
 474                     return true;
 475                 }
 476             }
 477             return false;
 478         } finally {
 479             lock.unlock();
 480         }
 481     }
 482 
 483     /**
 484      * Returns {@code true} if this queue contains the specified element.
 485      * More formally, returns {@code true} if and only if this queue contains
 486      * at least one element {@code e} such that {@code o.equals(e)}.
 487      *
 488      * @param o object to be checked for containment in this queue
 489      * @return {@code true} if this queue contains the specified element
 490      */
 491     public boolean contains(Object o) {
 492         if (o == null) return false;
 493         final Object[] items = this.items;
 494         final ReentrantLock lock = this.lock;
 495         lock.lock();
 496         try {
 497             for (int i = takeIndex, k = count; k > 0; i = inc(i), k--)
 498                 if (o.equals(items[i]))
 499                     return true;
 500             return false;
 501         } finally {
 502             lock.unlock();
 503         }
 504     }
 505 
 506     /**
 507      * Returns an array containing all of the elements in this queue, in
 508      * proper sequence.
 509      *
 510      * <p>The returned array will be "safe" in that no references to it are
 511      * maintained by this queue.  (In other words, this method must allocate
 512      * a new array).  The caller is thus free to modify the returned array.
 513      *
 514      * <p>This method acts as bridge between array-based and collection-based
 515      * APIs.
 516      *
 517      * @return an array containing all of the elements in this queue
 518      */
 519     public Object[] toArray() {
 520         final Object[] items = this.items;
 521         final ReentrantLock lock = this.lock;
 522         lock.lock();
 523         try {
 524             final int count = this.count;
 525             Object[] a = new Object[count];
 526             for (int i = takeIndex, k = 0; k < count; i = inc(i), k++)
 527                 a[k] = items[i];
 528             return a;
 529         } finally {
 530             lock.unlock();
 531         }
 532     }
 533 
 534     /**
 535      * Returns an array containing all of the elements in this queue, in
 536      * proper sequence; the runtime type of the returned array is that of
 537      * the specified array.  If the queue fits in the specified array, it
 538      * is returned therein.  Otherwise, a new array is allocated with the
 539      * runtime type of the specified array and the size of this queue.
 540      *
 541      * <p>If this queue fits in the specified array with room to spare
 542      * (i.e., the array has more elements than this queue), the element in
 543      * the array immediately following the end of the queue is set to
 544      * {@code null}.
 545      *
 546      * <p>Like the {@link #toArray()} method, this method acts as bridge between
 547      * array-based and collection-based APIs.  Further, this method allows
 548      * precise control over the runtime type of the output array, and may,
 549      * under certain circumstances, be used to save allocation costs.
 550      *
 551      * <p>Suppose {@code x} is a queue known to contain only strings.
 552      * The following code can be used to dump the queue into a newly
 553      * allocated array of {@code String}:
 554      *
 555      * <pre>
 556      *     String[] y = x.toArray(new String[0]);</pre>
 557      *
 558      * Note that {@code toArray(new Object[0])} is identical in function to
 559      * {@code toArray()}.
 560      *
 561      * @param a the array into which the elements of the queue are to
 562      *          be stored, if it is big enough; otherwise, a new array of the
 563      *          same runtime type is allocated for this purpose
 564      * @return an array containing all of the elements in this queue
 565      * @throws ArrayStoreException if the runtime type of the specified array
 566      *         is not a supertype of the runtime type of every element in
 567      *         this queue
 568      * @throws NullPointerException if the specified array is null
 569      */
 570     @SuppressWarnings("unchecked")
 571     public <T> T[] toArray(T[] a) {
 572         final Object[] items = this.items;
 573         final ReentrantLock lock = this.lock;
 574         lock.lock();
 575         try {
 576             final int count = this.count;
 577             final int len = a.length;
 578             if (len < count)
 579                 a = (T[])java.lang.reflect.Array.newInstance(
 580                     a.getClass().getComponentType(), count);
 581             for (int i = takeIndex, k = 0; k < count; i = inc(i), k++)
 582                 a[k] = (T) items[i];
 583             if (len > count)
 584                 a[count] = null;
 585             return a;
 586         } finally {
 587             lock.unlock();
 588         }
 589     }
 590 
 591     public String toString() {
 592         final ReentrantLock lock = this.lock;
 593         lock.lock();
 594         try {
 595             int k = count;
 596             if (k == 0)
 597                 return "[]";
 598 
 599             StringBuilder sb = new StringBuilder();
 600             sb.append('[');
 601             for (int i = takeIndex; ; i = inc(i)) {
 602                 Object e = items[i];
 603                 sb.append(e == this ? "(this Collection)" : e);
 604                 if (--k == 0)
 605                     return sb.append(']').toString();
 606                 sb.append(',').append(' ');
 607             }
 608         } finally {
 609             lock.unlock();
 610         }
 611     }
 612 
 613     /**
 614      * Atomically removes all of the elements from this queue.
 615      * The queue will be empty after this call returns.
 616      */
 617     public void clear() {
 618         final Object[] items = this.items;
 619         final ReentrantLock lock = this.lock;
 620         lock.lock();
 621         try {
 622             for (int i = takeIndex, k = count; k > 0; i = inc(i), k--)
 623                 items[i] = null;
 624             count = 0;
 625             putIndex = 0;
 626             takeIndex = 0;
 627             notFull.signalAll();
 628         } finally {
 629             lock.unlock();
 630         }
 631     }
 632 
 633     /**
 634      * @throws UnsupportedOperationException {@inheritDoc}
 635      * @throws ClassCastException            {@inheritDoc}
 636      * @throws NullPointerException          {@inheritDoc}
 637      * @throws IllegalArgumentException      {@inheritDoc}
 638      */
 639     public int drainTo(Collection<? super E> c) {
 640         checkNotNull(c);
 641         if (c == this)
 642             throw new IllegalArgumentException();
 643         final Object[] items = this.items;
 644         final ReentrantLock lock = this.lock;
 645         lock.lock();
 646         try {
 647             int i = takeIndex;
 648             int n = 0;
 649             int max = count;
 650             while (n < max) {
 651                 @SuppressWarnings("unchecked") E x = (E) items[i];
 652                 c.add(x);
 653                 items[i] = null;
 654                 i = inc(i);
 655                 ++n;
 656             }
 657             if (n > 0) {
 658                 count = 0;
 659                 putIndex = 0;
 660                 takeIndex = 0;
 661                 notFull.signalAll();
 662             }
 663             return n;
 664         } finally {
 665             lock.unlock();
 666         }
 667     }
 668 
 669     /**
 670      * @throws UnsupportedOperationException {@inheritDoc}
 671      * @throws ClassCastException            {@inheritDoc}
 672      * @throws NullPointerException          {@inheritDoc}
 673      * @throws IllegalArgumentException      {@inheritDoc}
 674      */
 675     public int drainTo(Collection<? super E> c, int maxElements) {
 676         checkNotNull(c);
 677         if (c == this)
 678             throw new IllegalArgumentException();
 679         if (maxElements <= 0)
 680             return 0;
 681         final Object[] items = this.items;
 682         final ReentrantLock lock = this.lock;
 683         lock.lock();
 684         try {
 685             int i = takeIndex;
 686             int n = 0;
 687             int max = (maxElements < count) ? maxElements : count;
 688             while (n < max) {
 689                 @SuppressWarnings("unchecked") E x = (E) items[i];
 690                 c.add(x);
 691                 items[i] = null;
 692                 i = inc(i);
 693                 ++n;
 694             }
 695             if (n > 0) {
 696                 count -= n;
 697                 takeIndex = i;
 698                 notFull.signalAll();
 699             }
 700             return n;
 701         } finally {
 702             lock.unlock();
 703         }
 704     }
 705 
 706     /**
 707      * Returns an iterator over the elements in this queue in proper sequence.
 708      * The elements will be returned in order from first (head) to last (tail).
 709      *
 710      * <p>The returned {@code Iterator} is a "weakly consistent" iterator that
 711      * will never throw {@link java.util.ConcurrentModificationException
 712      * ConcurrentModificationException},
 713      * and guarantees to traverse elements as they existed upon
 714      * construction of the iterator, and may (but is not guaranteed to)
 715      * reflect any modifications subsequent to construction.
 716      *
 717      * @return an iterator over the elements in this queue in proper sequence
 718      */
 719     public Iterator<E> iterator() {
 720         return new Itr();
 721     }
 722 
 723     /**
 724      * Iterator for ArrayBlockingQueue. To maintain weak consistency
 725      * with respect to puts and takes, we (1) read ahead one slot, so
 726      * as to not report hasNext true but then not have an element to
 727      * return -- however we later recheck this slot to use the most
 728      * current value; (2) ensure that each array slot is traversed at
 729      * most once (by tracking "remaining" elements); (3) skip over
 730      * null slots, which can occur if takes race ahead of iterators.
 731      * However, for circular array-based queues, we cannot rely on any
 732      * well established definition of what it means to be weakly
 733      * consistent with respect to interior removes since these may
 734      * require slot overwrites in the process of sliding elements to
 735      * cover gaps. So we settle for resiliency, operating on
 736      * established apparent nexts, which may miss some elements that
 737      * have moved between calls to next.
 738      */
 739     private class Itr implements Iterator<E> {
 740         private int remaining; // Number of elements yet to be returned
 741         private int nextIndex; // Index of element to be returned by next
 742         private E nextItem;    // Element to be returned by next call to next
 743         private E lastItem;    // Element returned by last call to next
 744         private int lastRet;   // Index of last element returned, or -1 if none
 745 
 746         Itr() {
 747             final ReentrantLock lock = ArrayBlockingQueue.this.lock;
 748             lock.lock();
 749             try {
 750                 lastRet = -1;
 751                 if ((remaining = count) > 0)
 752                     nextItem = itemAt(nextIndex = takeIndex);
 753             } finally {
 754                 lock.unlock();
 755             }
 756         }
 757 
 758         public boolean hasNext() {
 759             return remaining > 0;
 760         }
 761 
 762         public E next() {
 763             final ReentrantLock lock = ArrayBlockingQueue.this.lock;
 764             lock.lock();
 765             try {
 766                 if (remaining <= 0)
 767                     throw new NoSuchElementException();
 768                 lastRet = nextIndex;
 769                 E x = itemAt(nextIndex);  // check for fresher value
 770                 if (x == null) {
 771                     x = nextItem;         // we are forced to report old value
 772                     lastItem = null;      // but ensure remove fails
 773                 }
 774                 else
 775                     lastItem = x;
 776                 while (--remaining > 0 && // skip over nulls
 777                        (nextItem = itemAt(nextIndex = inc(nextIndex))) == null)
 778                     ;
 779                 return x;
 780             } finally {
 781                 lock.unlock();
 782             }
 783         }
 784 
 785         public void remove() {
 786             final ReentrantLock lock = ArrayBlockingQueue.this.lock;
 787             lock.lock();
 788             try {
 789                 int i = lastRet;
 790                 if (i == -1)
 791                     throw new IllegalStateException();
 792                 lastRet = -1;
 793                 E x = lastItem;
 794                 lastItem = null;
 795                 // only remove if item still at index
 796                 if (x != null && x == items[i]) {
 797                     boolean removingHead = (i == takeIndex);
 798                     removeAt(i);
 799                     if (!removingHead)
 800                         nextIndex = dec(nextIndex);
 801                 }
 802             } finally {
 803                 lock.unlock();
 804             }
 805         }
 806     }
 807 
 808 }