JavaInterview/datastructure/blockingqueueanddeque.md at master

BlockingQueue 和 BlockingDeque 内部实现分析

BlockingQueue 介绍

BlockingQueue 继承自 Queue 接口,下面看看阻塞队列提供的接口；

public interface BlockingQueue<E> extends Queue<E> {
    /**
     * 插入数据到队列尾部（如果立即可行且不会超过该队列的容量）
     * 在成功时返回 true，如果此队列已满，则抛IllegalStateException。(与offer方法的区别)
     */
    boolean add(E e);

    /**
     * 插入数据到队列尾部，如果没有空间，直接返回false;
     * 有空间直接插入，返回true。
     */
    boolean offer(E e);

    /**
     * 插入数据到队列尾部，如果队列没有空间，一直阻塞；
     * 有空间直接插入。
     */
    void put(E e) throws InterruptedException;

    /**
     * 插入数据到队列尾部，如果没有额外的空间，等待一定的时间，有空间即插入，返回true，
     * 到时间了，还是没有额外空间，返回false。
     */
    boolean offer(E e, long timeout, TimeUnit unit)
        throws InterruptedException;

    /**
     * 取出和删除队列中的头元素，如果没有数据，会一直阻塞到有数据
     */
    E take() throws InterruptedException;

    /**
     * 取出和删除队列中的头元素，如果没有数据，需要会阻塞一定的时间，过期了还没有数据，返回null
     */
    E poll(long timeout, TimeUnit unit)
        throws InterruptedException;
    
    //除了上述方法还有继承自Queue接口的方法 
    /**
     * 取出和删除队列头元素，如果是空队列直接返回null。
     */
    E poll();

    /**
     * 取出但不删除头元素，该方法与peek方法的区别是当队列为空时会抛出NoSuchElementException异常
     */
    E element();

    /**
     * 取出但不删除头元素，空队列直接返回null
     */
    E peek();

    /**
     * 返回队列总额外的空间
     */
    int remainingCapacity();

    /**
     * 删除队列中存在的元素
     */
    boolean remove(Object o);

   /**
    * 判断队列中是否存在当前元素
    */
    boolean contains(Object o);

}

插入方法

add(E e): 添加成功返回true，失败抛IllegalStateException异常

offer(E e): 成功返回 true，如果此队列已满，则返回 false。

put(E e): 将元素插入此队列的尾部，如果该队列已满，则一直阻塞

删除方法

remove(Object o): 移除指定元素,成功返回true，失败返回false

poll(): 获取并移除此队列的头元素，若队列为空，则返回 null

take(): 获取并移除此队列的头元素，若队列为空，则一直阻塞

检查方法

peek(): 获取但不移除此队列的头元素，没有元素则抛NoSuchElementException异常

element(): 获取但不移除此队列的头；若队列为空，则返回 null。

ArrayBlockingQueue

ArrayBlockingQueue() 是一个用数组实现的有界阻塞队列，内部按先进先出的原则对元素进行排序；其中 put 方法和 take 方法为添加和删除元素的阻塞方法。

ArrayBlockingQueue 实现的生产者消费者的 Demo，代码只是一个简单的 ArrayBlockingQueue 的使用，Consumer 消费者和 Producer 生产者通过 ArrayBlockingQueue 来获取（take）和添加（put）数据。具体代码请访问：ABQ demo。

ArrayBlockingQueue 内部的阻塞队列是通过 ReentrantLock 和 Condition 条件队列实现的，所以 ArrayBlockingQueue 中的元素存在公平和非公平访问的区别，这是因为 ReentrantLock 里面存在公平锁和非公平锁的原因， ReentrantLock 的具体分析会在 Lock 章节进行具体分析的；对于 Lock 是公平锁的时候，则被阻塞的队列可以按照阻塞的先后顺序访问队列，Lock 是非公平锁的时候，阻塞的线程将进入争夺锁资源的过程中，谁先抢到锁就可以先执行，没有固定的先后顺序。

下面对 ArrayBlockingQueue 构造方法进行分析：

/**
 * 创建一个具体容量的队列，默认是非公平队列
 */
public ArrayBlockingQueue(int capacity) {
    this(capacity, false);
}

/**
 * 创建一个具体容量、是否公平的队列 
 */
public ArrayBlockingQueue(int capacity, boolean fair) {
    if (capacity <= 0)
        throw new IllegalArgumentException();
    this.items = new Object[capacity];
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull =  lock.newCondition();
}

ArrayBlockingQueue 除了实现上述 BlockingQueue 接口的方法，其他方法介绍如下：

//返回队列剩余容量
public int remainingCapacity()

// 判断队列中是否存在当前元素o
public boolean contains(Object o) 

// 返回一个按正确顺序，包含队列中所有元素的数组
public Object[] toArray()

// 返回一个按正确顺序，包含队列中所有元素的数组；数组的运行时类型是指定数组的运行时类型
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a)


// 自动清空队列中的所有元素
public void clear()

// 移除队列中所有可用元素，并将他们加入到给定的 Collection 中    
public int drainTo(Collection<? super E> c)

// 从队列中最多移除指定数量的可用元素，并将他们加入到给定的 Collection 中    
public int drainTo(Collection<? super E> c, int maxElements)

// 返回此队列中按正确顺序进行迭代的，包含所有元素的迭代器
public Iterator<E> iterator()

ArrayBlockingQueue 源码和实现原理分析

内部成员变量分析

public class ArrayBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {

    /** 存储数据的数组 */
    final Object[] items;

    /** 获取数据的索引，用于下次 take, poll, peek or remove 等方法 */
    int takeIndex;

    /** 添加元素的索引， 用于下次 put, offer, or add 方法 */
    int putIndex;

    /** 队列元素的个数 */
    int count;

    /*
     * 并发控制使用任何教科书中的经典双条件算法
     */

    /** 控制并发访问的锁 */
    final ReentrantLock lock;

    /** 非空条件对象，用于通知 take 方法中在等待获取数据的线程，队列中已有数据，可以执行获取操作 */
    private final Condition notEmpty;

    /** 未满条件对象，用于通知 put 方法中在等待添加数据的线程，队列未满，可以执行添加操作 */
    private final Condition notFull;

    /** 迭代器 */
    transient Itrs itrs = null;
}

从上面成员变量中可以看出，内部使用数组对象 items 来存储所有的数据；通过同一个 ReentrantLock 来同时控制添加数据线程和移除数据线程的并发访问，这个与 LinkedBlockingQueue 有很大区别(下面会进行分析)。

对于 notEmpty 条件对象是用于存放等待调用(此时队列中没有数据) take 方法的线程，这些线程会加入到 notEmpty 条件对象的等待队列(单链表)中，同时当队列中有数据后会通过 notEmpty 条件对象唤醒等待队列(链表)中等待的线程(链表中第一个non-null 且 status 为 Condition 的线程)去 take 数据。

对于 notFull 条件对象是用于存放等待调用(此时队列容量已满) put 方法的线程，这些线程会加入到 notFull 条件对象的等待队列(单链表)中，同时当队列中数据被消费后会通过 notFull 条件对象唤醒等待队列(链表)中等待的线程去 put 数据。takeIndex 表示的是下一个(take、poll、peek、remove)方法被调用时获取数组元素的索引，putIndex 表示的是下一个(put、offer、add)被调用时添加元素的索引。

数据出队、入队操作如下：

添加(阻塞添加)的实现分析

/**
 * 在当前 put 位置插入数据，put 位置前进一位，
 * 同时唤醒 notEmpty 条件对象等待队列(链表)中第一个可用线程去 take 数据。
 * 当然这一系列动作只有该线程获取锁的时候才能进行，即只有获取锁的线程
 * 才能执行 enqueue 操作。
 */
// 元素统一入队操作
private void enqueue(E x) {
    // assert lock.getHoldCount() == 1;
    // assert items[putIndex] == null;
    final Object[] items = this.items;
    items[putIndex] = x; // putIndex 位置添加数据
    //putIndex 进行自增，当达到数组长度的时候，putIndex 重头再来，即设置为0
    //为什么呢？下面会具体介绍 
    if (++putIndex == items.length) 
        putIndex = 0;
    count++; //元素个数自增
    notEmpty.signal(); //添加完数据后，说明数组中有数据了，所以可以唤醒 notEmpty 条件对象等待队列(链表)中第一个可用线程去 take 数据
}

// 添加数据，数组中元素已满时，直接返回 false。
public boolean offer(E e) {
    checkNotNull(e);
    final ReentrantLock lock = this.lock;
    // 获取锁，保证线程安全
    lock.lock();
    try {
        // 当数组元素个数已满时，直接返回false
        if (count == items.length)
            return false;
        else {
            // 执行入队操作，enqueue 方法在上面分析了
            enqueue(e);
            return true;
        }
    } finally {
        // 释放锁，保证其他等待锁的线程可以获取到锁
        // 为什么放到 finally (避免死锁)
        lock.unlock();
    }
}

// add 方法其实就是调用了 offer 方法来实现，
// 与 offer 方法的区别就是 offer 方法数组满，抛出 IllegalStateException 异常。
public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");
}

offer 方法和 add 方法实现很简单，大家只需要知道其区别就好了；这里着重讲一下 enqueue 方法里面留下的疑问，为什么当 putIndex 到了数组最后一个元素之后，是重头再来，设置为0；首先，你要想到 ArrayBlockingQueue 整个入队和出队操作都是线程安全的，而且 ArrayBlockingQueue 也是先进先出的队列；所以想一想，是不是数据入队后，从第一个数组位置上开始添加数据，依次往后入队；数据出队也是从数组第一个位置出队，出队后该位置数据为空，依次出队，然后这些位置数据都为空；所以只要 count 的个数没有达到数组长度时，虽然 putIndex 达到了数组长度，说明数组前面的位置上已经有数据出队了，所以添加元素，是不是就从头开始就行了(想明白了其实就很简单了，哈哈)。因为我们有一个 count 成员变量来记录元素的个数，当队列已满时，put 操作是会阻塞，add 操作会抛出异常，offer 操作会直接返回false；因此我们也不用担心数据会覆盖。这个 putIndex 和 takeIndex 达到数据长度后都会重新设置为0，重头开始再获取数据，整个过程就是一个无限循环的过程。通过分析，我们发现有添加操作是不是有两种场景，一个是直接往后添加，一个是达到数据长度后，需要重头再来，

具体操作如下图：

下面看看阻塞添加方法(put)

/**
 * 插入数据到队列尾部，如果队列已满，阻塞等待空间
 */
public void put(E e) throws InterruptedException {
    checkNotNull(e);
    final ReentrantLock lock = this.lock;
    // 获取锁，期间线程可以打断，打断则不会添加
    lock.lockInterruptibly();
    try {
        // 通过上述分析，我们通过 count 来判断数组中元素个数
        while (count == items.length)
            notFull.await(); // 元素已满，线程挂起，线程加入 notFull 条件对象等待队列(链表)中，等待被唤醒
        enqueue(e); // 队列未满，直接执行入队操作
    } finally {
        lock.unlock();
    }
}

通过源码分析，发现 offer, add 都是无阻塞添加方法，两者的具体区别在上面分析过了；而 put 方法确实是一个阻塞方法，当队列已满的时候，线程会挂起，然后将该线程加入到 notFull 条件对象的等待队列(链表)中；notFull 条件对象有两种情况，第一种是当队列已满，新来的 put 数据的线程会加入到其等待队列(链表)中，第二种情况是，当队列有空间时，会移除队列中的线程，移除成功同时唤醒 put 线程，加入到获取 lock 的等待队列(双链表)的尾部。

具体操作，如下图：

通过以上分析，ArrayBlockingQueue 的 offer、 add、 put 方法已经都详细分析完毕，希望大家可以对其有深入的了解。

提取(阻塞提取)的实现分析

提取即移除数组中的元素，下面我们具体来分析 ArrayBlockingQueue 的提取数组中元素的操作。

同上分析，我们首先从 dequeue 方法分析开始。

/**
 * 提取 takeIndex 位置上的元素， 然后 takeIndex 前进一位，
 * 同时唤醒 notFull 等待队列(链表)中的第一个可用线程去 put 数据。
 * 这些操作都是在当前线程获取到锁的前提下进行的，
 * 同时也说明了 dequeue 方法线程安全的。
 */
private E dequeue() {
    // assert lock.getHoldCount() == 1;
    // assert items[takeIndex] != null;
    final Object[] items = this.items; 
    @SuppressWarnings("unchecked")
    E x = (E) items[takeIndex]; // 提取 takeIndex位置上的数据
    items[takeIndex] = null; // 同时清空数组在 takeIndex 位置上的数据
    // takeIndex 向前前进一位，如果前进后位置超过了数组的长度，则将其设置为0；
    // 为什么设置为0，理由在 putIndex 设置为0的时候介绍过了，原因是一样的。
    if (++takeIndex == items.length) 
        takeIndex = 0;
    count--; // 同时数组的元素个数进行减1
    if (itrs != null)
        itrs.elementDequeued(); // 同时更新迭代器中的元素，迭代器的具体分析会在下面单独整理
    notFull.signal(); // 提取完数据后，说明数组中有空位，所以可以唤醒 notFull 条件对象的等待队列(链表)中的第一个可用线程去 put 数据
    return x;
}

// 提取数据，数组中数据为空时，直接返回 null
public E poll() {
    final ReentrantLock lock = this.lock;
    lock.lock(); // 加锁，前面也分析过，要执行 dequeue操作时，当前线程必须获取锁，保证线程安全
    try {
        return (count == 0) ? null : dequeue(); // 元素个数为0时，直接返回 null，不为0时，元素出队
    } finally {
        // 释放锁，在 finally 中释放可以避免死锁
        lock.unlock();
    }
}

上面 poll() 方法分析得很清晰了，内部通过 dequeue 删除队列头元素。下面分析下 peek 方法，与 poll 有较大的区别。

// 返回数组上第 i 个元素
final E itemAt(int i) {
    return (E) items[i];
}

/**
 * 通过代码可以看到，peek 是获取元素，而不是提取， 不会删除 takeIndex 位置上的数据。
 * 内部通过 itemAt 方法实现，而不是 dequeue 方法。
 */
public E peek() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
     return itemAt(takeIndex); //当队列为空时，返回 null
    } finally {
     lock.unlock();
    }
}

通过上述代码，可以看出 peek 和 poll 的区别，peek 是获取元素，不会删除 takeIndex 位置原有的数据，takeIndex 也不会向前前进一位。

下面来分析下阻塞提取 take 方法：

// 从队列头部提取数据，队列中没有元素则阻塞，阻塞期间线程可中断
public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly(); //获取锁，期间线程可以打断，打断则不会提取
    try {
        // 元素为0时，当有线程提取元素，则将该线程加入到 notEmpty 条件对象的等待队列中，
        // 直到当队列中有数据之后，会唤醒该线程去提取数据。
        while (count == 0)
            notEmpty.await();
        return dequeue(); // 若有数据，直接调用 dequeue 提取数据
    } finally {
        lock.unlock();
    }
}

其实分析完阻塞添加 put 方法后，再来看 take 方法，发现也是非常简单的，队列中有元素，直接提取，没有元素则线程阻塞(可中断的阻塞)，将该线程加入到 notEmpty 条件对象的等待队列中；等有新的 put 线程添加了数据，分析发现，会在 put 操作中唤醒 notEmpty 条件对象的等待队列中的 take 线程，去执行 take 操作。

具体操作如下图：

通过以上分析，我们把 poll、take 提取元素的方法分析了，也把 peek 获取元素的方法分析了，我们使用的时候，根据具体的场景使用具体的方法。

分析完提取方法后，我们来分析一下 ArrayBlockingQueue 中的删除元素的 remove 方法。

void removeAt(final int removeIndex) {
    // assert lock.getHoldCount() == 1;
    // assert items[removeIndex] != null;
    // assert removeIndex >= 0 && removeIndex < items.length;
    final Object[] items = this.items;
    if (removeIndex == takeIndex) {
        // removing front item; just advance
        items[takeIndex] = null;
        if (++takeIndex == items.length)
            takeIndex = 0;
        count--;
        if (itrs != null)
            itrs.elementDequeued();
    } else {
        // an "interior" remove

        // slide over all others up through putIndex.
        final int putIndex = this.putIndex;
        for (int i = removeIndex;;) {
            int next = i + 1;
            if (next == items.length)
                next = 0;
            if (next != putIndex) {
                items[i] = items[next];
                i = next;
            } else {
                items[i] = null;
                this.putIndex = i;
                break;
            }
        }
        count--;
        if (itrs != null)
            itrs.removedAt(removeIndex);
    }
    notFull.signal();
}

public boolean remove(Object o) {
    if (o == null) return false;
    final Object[] items = this.items;
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        if (count > 0) {
            final int putIndex = this.putIndex;
            int i = takeIndex;
            do {
                if (o.equals(items[i])) {
                    removeAt(i);
                    return true;
                }
                if (++i == items.length)
                    i = 0;
            } while (i != putIndex);
        }
        return false;
    } finally {
        lock.unlock();
    }
}

ArrayBlockingQueue 的迭代器分析

private class Itr implements Iterator<E> {
    /** Index to look for new nextItem; NONE at end */
    private int cursor;

    /** Element to be returned by next call to next(); null if none */
    private E nextItem;

    /** Index of nextItem; NONE if none, REMOVED if removed elsewhere */
    private int nextIndex;

    /** Last element returned; null if none or not detached. */
    private E lastItem;

    /** Index of lastItem, NONE if none, REMOVED if removed elsewhere */
    private int lastRet;

    /** Previous value of takeIndex, or DETACHED when detached */
    private int prevTakeIndex;

    /** Previous value of iters.cycles */
    private int prevCycles;

    /** Special index value indicating "not available" or "undefined" */
    private static final int NONE = -1;

    /**
     * Special index value indicating "removed elsewhere", that is,
     * removed by some operation other than a call to this.remove().
     */
    private static final int REMOVED = -2;

    /** Special value for prevTakeIndex indicating "detached mode" */
    private static final int DETACHED = -3;

    Itr() {
        // assert lock.getHoldCount() == 0;
        lastRet = NONE;
        final ReentrantLock lock = ArrayBlockingQueue.this.lock;
        lock.lock();
        try {
            if (count == 0) {
                // assert itrs == null;
                cursor = NONE;
                nextIndex = NONE;
                prevTakeIndex = DETACHED;
            } else {
                final int takeIndex = ArrayBlockingQueue.this.takeIndex;
                prevTakeIndex = takeIndex;
                nextItem = itemAt(nextIndex = takeIndex);
                cursor = incCursor(takeIndex);
                if (itrs == null) {
                    itrs = new Itrs(this);
                } else {
                    itrs.register(this); // in this order
                    itrs.doSomeSweeping(false);
                }
                prevCycles = itrs.cycles;
                // assert takeIndex >= 0;
                // assert prevTakeIndex == takeIndex;
                // assert nextIndex >= 0;
                // assert nextItem != null;
            }
        } finally {
            lock.unlock();
        }
    }

    boolean isDetached() {
        // assert lock.getHoldCount() == 1;
        return prevTakeIndex < 0;
    }

    private int incCursor(int index) {
        // assert lock.getHoldCount() == 1;
        if (++index == items.length)
            index = 0;
        if (index == putIndex)
            index = NONE;
        return index;
    }

    /**
     * Returns true if index is invalidated by the given number of
     * dequeues, starting from prevTakeIndex.
     */
    private boolean invalidated(int index, int prevTakeIndex,
                                long dequeues, int length) {
        if (index < 0)
            return false;
        int distance = index - prevTakeIndex;
        if (distance < 0)
            distance += length;
        return dequeues > distance;
    }

    /**
     * Adjusts indices to incorporate all dequeues since the last
     * operation on this iterator.  Call only from iterating thread.
     */
    private void incorporateDequeues() {
        // assert lock.getHoldCount() == 1;
        // assert itrs != null;
        // assert !isDetached();
        // assert count > 0;

        final int cycles = itrs.cycles;
        final int takeIndex = ArrayBlockingQueue.this.takeIndex;
        final int prevCycles = this.prevCycles;
        final int prevTakeIndex = this.prevTakeIndex;

        if (cycles != prevCycles || takeIndex != prevTakeIndex) {
            final int len = items.length;
            // how far takeIndex has advanced since the previous
            // operation of this iterator
            long dequeues = (cycles - prevCycles) * len
                + (takeIndex - prevTakeIndex);

            // Check indices for invalidation
            if (invalidated(lastRet, prevTakeIndex, dequeues, len))
                lastRet = REMOVED;
            if (invalidated(nextIndex, prevTakeIndex, dequeues, len))
                nextIndex = REMOVED;
            if (invalidated(cursor, prevTakeIndex, dequeues, len))
                cursor = takeIndex;

            if (cursor < 0 && nextIndex < 0 && lastRet < 0)
                detach();
            else {
                this.prevCycles = cycles;
                this.prevTakeIndex = takeIndex;
            }
        }
    }

    /**
     * Called when itrs should stop tracking this iterator, either
     * because there are no more indices to update (cursor < 0 &&
     * nextIndex < 0 && lastRet < 0) or as a special exception, when
     * lastRet >= 0, because hasNext() is about to return false for the
     * first time.  Call only from iterating thread.
     */
    private void detach() {
        // Switch to detached mode
        // assert lock.getHoldCount() == 1;
        // assert cursor == NONE;
        // assert nextIndex < 0;
        // assert lastRet < 0 || nextItem == null;
        // assert lastRet < 0 ^ lastItem != null;
        if (prevTakeIndex >= 0) {
            // assert itrs != null;
            prevTakeIndex = DETACHED;
            // try to unlink from itrs (but not too hard)
            itrs.doSomeSweeping(true);
        }
    }

    /**
     * For performance reasons, we would like not to acquire a lock in
     * hasNext in the common case.  To allow for this, we only access
     * fields (i.e. nextItem) that are not modified by update operations
     * triggered by queue modifications.
     */
    public boolean hasNext() {
        // assert lock.getHoldCount() == 0;
        if (nextItem != null)
            return true;
        noNext();
        return false;
    }

    private void noNext() {
        final ReentrantLock lock = ArrayBlockingQueue.this.lock;
        lock.lock();
        try {
            // assert cursor == NONE;
            // assert nextIndex == NONE;
            if (!isDetached()) {
                // assert lastRet >= 0;
                incorporateDequeues(); // might update lastRet
                if (lastRet >= 0) {
                    lastItem = itemAt(lastRet);
                    // assert lastItem != null;
                    detach();
                }
            }
            // assert isDetached();
            // assert lastRet < 0 ^ lastItem != null;
        } finally {
            lock.unlock();
        }
    }

    public E next() {
        // assert lock.getHoldCount() == 0;
        final E x = nextItem;
        if (x == null)
            throw new NoSuchElementException();
        final ReentrantLock lock = ArrayBlockingQueue.this.lock;
        lock.lock();
        try {
            if (!isDetached())
                incorporateDequeues();
            // assert nextIndex != NONE;
            // assert lastItem == null;
            lastRet = nextIndex;
            final int cursor = this.cursor;
            if (cursor >= 0) {
                nextItem = itemAt(nextIndex = cursor);
                // assert nextItem != null;
                this.cursor = incCursor(cursor);
            } else {
                nextIndex = NONE;
                nextItem = null;
            }
        } finally {
            lock.unlock();
        }
        return x;
    }

    public void remove() {
        // assert lock.getHoldCount() == 0;
        final ReentrantLock lock = ArrayBlockingQueue.this.lock;
        lock.lock();
        try {
            if (!isDetached())
                incorporateDequeues(); // might update lastRet or detach
            final int lastRet = this.lastRet;
            this.lastRet = NONE;
            if (lastRet >= 0) {
                if (!isDetached())
                    removeAt(lastRet);
                else {
                    final E lastItem = this.lastItem;
                    // assert lastItem != null;
                    this.lastItem = null;
                    if (itemAt(lastRet) == lastItem)
                        removeAt(lastRet);
                }
            } else if (lastRet == NONE)
                throw new IllegalStateException();
            // else lastRet == REMOVED and the last returned element was
            // previously asynchronously removed via an operation other
            // than this.remove(), so nothing to do.

            if (cursor < 0 && nextIndex < 0)
                detach();
        } finally {
            lock.unlock();
            // assert lastRet == NONE;
            // assert lastItem == null;
        }
    }

    /**
     * Called to notify the iterator that the queue is empty, or that it
     * has fallen hopelessly behind, so that it should abandon any
     * further iteration, except possibly to return one more element
     * from next(), as promised by returning true from hasNext().
     */
    void shutdown() {
        // assert lock.getHoldCount() == 1;
        cursor = NONE;
        if (nextIndex >= 0)
            nextIndex = REMOVED;
        if (lastRet >= 0) {
            lastRet = REMOVED;
            lastItem = null;
        }
        prevTakeIndex = DETACHED;
        // Don't set nextItem to null because we must continue to be
        // able to return it on next().
        //
        // Caller will unlink from itrs when convenient.
    }

    private int distance(int index, int prevTakeIndex, int length) {
        int distance = index - prevTakeIndex;
        if (distance < 0)
            distance += length;
        return distance;
    }

    /**
     * Called whenever an interior remove (not at takeIndex) occurred.
     *
     * @return true if this iterator should be unlinked from itrs
     */
    boolean removedAt(int removedIndex) {
        // assert lock.getHoldCount() == 1;
        if (isDetached())
            return true;

        final int cycles = itrs.cycles;
        final int takeIndex = ArrayBlockingQueue.this.takeIndex;
        final int prevCycles = this.prevCycles;
        final int prevTakeIndex = this.prevTakeIndex;
        final int len = items.length;
        int cycleDiff = cycles - prevCycles;
        if (removedIndex < takeIndex)
            cycleDiff++;
        final int removedDistance =
            (cycleDiff * len) + (removedIndex - prevTakeIndex);
        // assert removedDistance >= 0;
        int cursor = this.cursor;
        if (cursor >= 0) {
            int x = distance(cursor, prevTakeIndex, len);
            if (x == removedDistance) {
                if (cursor == putIndex)
                    this.cursor = cursor = NONE;
            }
            else if (x > removedDistance) {
                // assert cursor != prevTakeIndex;
                this.cursor = cursor = dec(cursor);
            }
        }
        int lastRet = this.lastRet;
        if (lastRet >= 0) {
            int x = distance(lastRet, prevTakeIndex, len);
            if (x == removedDistance)
                this.lastRet = lastRet = REMOVED;
            else if (x > removedDistance)
                this.lastRet = lastRet = dec(lastRet);
        }
        int nextIndex = this.nextIndex;
        if (nextIndex >= 0) {
            int x = distance(nextIndex, prevTakeIndex, len);
            if (x == removedDistance)
                this.nextIndex = nextIndex = REMOVED;
            else if (x > removedDistance)
                this.nextIndex = nextIndex = dec(nextIndex);
        }
        else if (cursor < 0 && nextIndex < 0 && lastRet < 0) {
            this.prevTakeIndex = DETACHED;
            return true;
        }
        return false;
    }

    /**
     * Called whenever takeIndex wraps around to zero.
     *
     * @return true if this iterator should be unlinked from itrs
     */
    boolean takeIndexWrapped() {
        // assert lock.getHoldCount() == 1;
        if (isDetached())
            return true;
        if (itrs.cycles - prevCycles > 1) {
            // All the elements that existed at the time of the last
            // operation are gone, so abandon further iteration.
            shutdown();
            return true;
        }
        return false;
    }

//         /** Uncomment for debugging. */
//         public String toString() {
//             return ("cursor=" + cursor + " " +
//                     "nextIndex=" + nextIndex + " " +
//                     "lastRet=" + lastRet + " " +
//                     "nextItem=" + nextItem + " " +
//                     "lastItem=" + lastItem + " " +
//                     "prevCycles=" + prevCycles + " " +
//                     "prevTakeIndex=" + prevTakeIndex + " " +
//                     "size()=" + size() + " " +
//                     "remainingCapacity()=" + remainingCapacity());
//         }
}