Robust/src/ClassLibrary/MGC/gnu/ArrayBlockingQueue.java

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