JDK8 ArrayBlockingQueue迭代器源码解析

àì夳堔傛蜴生んèń 2023-03-01 12:37 10阅读 0赞

### 文章目录 ###

*  前言
 *  Itr成员
 *  Itr构造器以及public方法
 *  Itrs对Itr的管理
 *  ArrayBlockingQueue里对Itrs的调用
 *   *  itrs.elementDequeued()
     *  itrs.removedAt(removeIndex)
     *  为什么Itrs会去掉失效的迭代器
 *  总结

# 前言 #

ArrayBlockingQueue的迭代器也是弱一致性的，体现在于队列元素被删除后，迭代器的next()也会照常返回这个元素。

# Itr成员 #

/** Previous value of takeIndex, or DETACHED when detached */
            private int prevTakeIndex;
    
            /** Previous value of iters.cycles */
            private int prevCycles;

这两个成员在创建迭代器时候被赋值，它用来保存创建时**队首的快照**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70]

*  从上图可以看出，即使take完全一样，和当初创建迭代器的队列相比，现在整个队列已经不包含迭代器刚创建时的每个元素了。
 *  开始时：`cycles = 0 takeIndex = 2`。结束时：`cycles = 1 takeIndex = 2`。通过前后两种情况得知，整个队列已经不是当初那个队列了。
 *  如果你在开始时，持有一个索引位置的元素。在结束时，无论你那个索引是啥，你持有的那个元素肯定已经过时了。

/** 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;

迭代器调用next就返回一个元素，但ArrayBlockingQueue的迭代器是在调用next之前就准备好`nextItem`。所以，在迭代器初始化、每次调用next时，都会准备好next相关数据，以便下一次next调用时可以直接返回`nextItem`。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 1]

*  迭代器初始化时，准备好了next的两个成员，都是指向的1节点。
 *  第一次调用next()时，队列已经改变，但还可以继续遍历下去。虽然此时1节点已经被删除，但既然已经准备好了，那还是返回1节点。只是之后调用remove()将不会执行删除动作了，因为1节点已经被删除了。
    
     *  因为队列已经改变，next的两个成员需要从新的队首开始。

# Itr构造器以及public方法 #

Itr() { 
                // assert lock.getHoldCount() == 0;
                lastRet = NONE;//刚初始化肯定没有调用next返回过，所以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);//准备好next的两个成员
                        cursor = incCursor(takeIndex);//cursor就是nextIndex的后继索引
    
    					//全局管理迭代器的相关操作
                        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();
                }
            }

如果队列为空，那么创建出的迭代器就是失效的。看看队列非空的情况吧：

*  lastRet最开始就设置为NONE，因为刚创建还没有调用过next()呢。
 *  nextIndex、nextItem都根据当前的队首来设置。
 *  cursor则为nextIndex的后继索引，具体看`incCursor`的逻辑，其实就是索引按照循环数组的方式右移，但不能到达putIndex。
 *  prevCycles、prevTakeIndex根据当前队列的队首，存储快照信息。

private int incCursor(int index) { 
        // assert lock.getHoldCount() == 1;
        if (++index == items.length)
            index = 0;
        // 遍历范围是[takeIndex, putIndex)，所以到达putIndex时，设置为无效值
        if (index == putIndex)
            index = NONE;
        return index;
    }

public boolean hasNext() { 
                // assert lock.getHoldCount() == 0;
                // 此方法不用加锁，因为队列的改变不会影响nextItem
                if (nextItem != null)
                    return true;
                // nextItem为null
                noNext();
                return false;
            }

hasNext()不用加锁，因为队列的改变不会影响nextItem，这也意味着迭代器不会在乎nextItem在队列是否被删除，下一次必定会返回。

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; 检查索引成员后，它要么是个正数，要么是REMOVE
                    // assert lastItem == null; next()返回了最后一个可遍历元素后，它才可能非null
                    
                    lastRet = nextIndex;//如果没被检查赋值为REMOVE，那这里就是正数
                    final int cursor = this.cursor;//暂存检查后的cursor
                    if (cursor >= 0) { //检查后还是正数，那么通过它获得next相关成员
                        nextItem = itemAt(nextIndex = cursor);
                        // assert nextItem != null;
                        this.cursor = incCursor(cursor);//前进cursor
                    } else { //如果是负数，不是因为incorporateDequeues干的，而是上一次的next()的incCursor干的
                        //说明此次next()返回的是最后一个可遍历元素，所以把next相关成员设为无效值
                        nextIndex = NONE;
                        nextItem = null;
                    }
                } finally { 
                    lock.unlock();
                }
                return x;
            }

*  不管怎样，之前保存的nextItem肯定会返回。只要它非null。
 *  各个索引成员会收到`incorporateDequeues`的检查，它们可能改变。
 *  将nextIndex赋值给lastRet，将cursor赋值给next的两个成员，再右移cursor。
 *  右移cursor时，可能导致cursor更新为NONE，这代表下一次next()返回的最后一个可遍历元素。
    
     *  下一次next()进入`if (cursor >= 0)`的else分支，让两个next成员为无效值，下下次无法调用next()了，因为抛出异常![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 2]  
        上图解释了最后两次next()后的状态。在最后这个状态，要想让迭代器变失效，最后一次调用next()后，再调用一次remove()或者hasNext()才能让迭代器失效（prevTakeIndex == DETACHED）。

`isDetached()`只是当prevTakeIndex == DETACHED时返回true，上一段也说了，除非到了最后，`isDetached()`是不可能返回true的。所以我们直接看`incorporateDequeues`是如何检查索引的。

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;
                    // 得到新旧队首之间出队了多少次，通过循环数组的计算方式
                    long dequeues = (cycles - prevCycles) * len
                        + (takeIndex - prevTakeIndex);
    
                    // Check indices for invalidation
                    if (invalidated(lastRet, prevTakeIndex, dequeues, len))
                        lastRet = REMOVED;//已经返回的，置为REMOVED
                    if (invalidated(nextIndex, prevTakeIndex, dequeues, len))
                        nextIndex = REMOVED;//即将返回的，也置为REMOVED
                    if (invalidated(cursor, prevTakeIndex, dequeues, len))
                        cursor = takeIndex;//cursor当前不会返回，所以更新为最新队首
    
                    //此函数中不可能让cursor为0，因为最多可能赋值为ArrayBlockingQueue.this.takeIndex
                    if (cursor < 0 && nextIndex < 0 && lastRet < 0)
                        detach();//使迭代器失效
                    else { //否则更新迭代器的队首快照
                        this.prevCycles = cycles;
                        this.prevTakeIndex = takeIndex;
                    }
                }
            }

回忆最开始讲解队首快照的地方，`dequeues`现在就是新队首相对旧队首的移动次数（也就是出队次数），只要`dequeues >= length`，那么很显然，之前持有的任何索引都会过时。

`incorporateDequeues`的最后，除非迭代器失效，那么一定会更新 新队首快照的。

//检查传入index参数，相对于旧队首的移动次数
            private boolean invalidated(int index, int prevTakeIndex,
                                        long dequeues, int length) { 
                if (index < 0)
                    return false;
                int distance = index - prevTakeIndex;
                if (distance < 0)//说明index从循环数组的另一端出来了，但我们需要得到正数
                    distance += length;
                //如果 新队首相对旧队首的移动次数 > index参数相对于旧队首的移动次数，
                //说明从旧队首变成新队首的期间，index参数已经过时
                return dequeues > distance;
            }

现在任何索引相对于旧队首的移动次数都必定是`< length`的（从队首出发移动到队尾，移动次数也只有length - 1）。

*  如果`dequeues >= length`，那么此`invalidated`函数肯定返回true，因为整个队列相对上一次的快照已经完全不一样了。
 *  如果`dequeues < length`，那么真假都可能返回。因为队列中尚且存有上一次快照的某几个元素（当然，极端情况是，和上一次快照一模一样）。

之前提到，最后一次调用next()后，再调用一次remove()或者hasNext()才能让迭代器失效（prevTakeIndex == DETACHED）。假设最后一次调用next()后的状态为：

*  cursor为NONE。
 *  nextItem、nextIndex都为无效值（null、NONE）。
 *  lastRet为正数（假设最后一次调用next()时，通过`incorporateDequeues`检查发现nextIndex没有被删除，所以`lastRet = nextIndex`赋值的是正数。相反，如果通过`incorporateDequeues`检查发现nextIndex已经被删除，`lastRet = nextIndex`赋值的会是负数，这种情况分析会更简单，所以不需要讲解，看前一种情况即可）。

先看下调用hasNext()接下来会发生什么：

很显然，只有最后一次调用next()后，`hasNext`才可能去调用`noNext()`并返回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();
                }
            }

即使假设最后一次调用next()后，lastRet为正数。在之后的`noNext()`的`incorporateDequeues`检查中，也可能将这个lastRet变成REMOVE。我们还是假设`noNext()`的`incorporateDequeues`不会使得lastRet变成REMOVE，那么保存`lastItem`，然后才令迭代器失效。

*  如果`noNext()`的`incorporateDequeues`检查中，不会使得lastRet变成REMOVE，那么`incorporateDequeues`中不会执行`detach`（迭代器失效），但`noNext`还是会执行`detach`。
 *  如果`noNext()`的`incorporateDequeues`检查中，使得lastRet变成REMOVE，那么`incorporateDequeues`中会执行`detach`。那么`noNext`就不会有后续动作了。
 *  总之，最后一次调用next()后，再调用一次hasNext()肯定能让迭代器失效。
    
     *  考虑lastRet没有过时的情况，即使迭代器失效，lastRet和lastItem都会保存着有效值的。
     *  考虑lastRet过时的情况，当然迭代器也会失效，lastRet为变成REMOVE，lastItem还是为null。

`remove`函数是依赖`lastRet`实现的，此函数可以删除上一次返回过的元素，如果这个元素还存在的话。

public void remove() { 
                // assert lock.getHoldCount() == 0;
                final ReentrantLock lock = ArrayBlockingQueue.this.lock;
                lock.lock();
                try { 
                    if (!isDetached())
                        incorporateDequeues(); 
                    final int lastRet = this.lastRet;//暂存lastRet，因为之后置为NONE
                    this.lastRet = NONE;
                    if (lastRet >= 0) { //如果暂存的lastRet是没有过时的
                        //如果迭代器没有失效
                        if (!isDetached())
                            removeAt(lastRet);//调用外部类的函数
                        //如果迭代器失效了
                        else { //这种情况是之前发生过：最后一次调用next()后，再调用一次hasNext()
                            final E lastItem = this.lastItem;
                            // assert lastItem != null;
                            this.lastItem = null;
                            if (itemAt(lastRet) == lastItem)//迭代器已经失效，没法通过prevTakeIndex判断了，直接对比好了
                                removeAt(lastRet);//调用外部类的函数
                        }
                    } else if (lastRet == NONE)//不允许连续两次调用remove
                        throw new IllegalStateException();
                    // else lastRet == REMOVED 
                    // 如果暂存的lastRet是REMOVED，那就什么也不干
    
                    if (cursor < 0 && nextIndex < 0)//lastRet肯定为NONE了，只看另外两个就好，决定是否失效迭代器
                        detach();
                } finally { 
                    lock.unlock();
                    // assert lastRet == NONE;
                    // assert lastItem == null;
                }
            }

总之，只有当lastRet在检查后还是为非负数时，才会执行删除动作。

# Itrs对Itr的管理 #

从`Itrs`的成员可知，它是用来管理每个用户创建的迭代器的，内部类Node通过弱引用来封装迭代器，因为迭代器的生命周期不应该由Itrs来控制。

class Itrs { 
    
            private class Node extends WeakReference<Itr> { 
                Node next;
    
                Node(Itr iterator, Node next) { 
                    super(iterator);
                    this.next = next;
                }
            }
    
            /** 每当takeIndex重新回到0，这个成员就加1 */
            int cycles = 0;
    
            /** 维持一个迭代器节点的单链表，靠持有它的头节点 */
            private Node head;
    
            /** 上一次扫描的最后一个节点 */
            private Node sweeper = null;
    
            private static final int SHORT_SWEEP_PROBES = 4;
            private static final int LONG_SWEEP_PROBES = 16;
        }

ArrayBlockingQueue有一个`Itrs itrs = null`成员，它在用户创建第一个迭代器时，被初始化。在`Itr`的构造器中，有这么一段：

Itrs(Itr initial) { //Itrs的构造器
                register(initial);
            }
    					//Itr的构造器的一部分
                        if (itrs == null) { 
                            itrs = new Itrs(this);
                        } else { 
                            itrs.register(this); // in this order
                            itrs.doSomeSweeping(false);
                        }

所以每个迭代器创建都会执行到Itrs的`register`：

void register(Itr itr) { 
                // assert lock.getHoldCount() == 1;
                head = new Node(itr, head);
            }

逻辑就是通过头插法，把迭代器放到单链表的头节点上去。

void doSomeSweeping(boolean tryHarder) { 
                // assert lock.getHoldCount() == 1;
                // assert head != null;
                int probes = tryHarder ? LONG_SWEEP_PROBES : SHORT_SWEEP_PROBES;//决定扫描的长度
                Node o, p;//p是循环变量，o只是用来保存旧p
                final Node sweeper = this.sweeper;//上一次扫描的终点
                boolean passedGo;   // 如果当前扫描将从head开始，那么为true
    
                if (sweeper == null) { //上一次扫描到了尾节点，所以这次从head开始
                    o = null;
                    p = head;
                    passedGo = true;
                } else { //上一次扫描到了中间某个位置
                    o = sweeper;
                    p = o.next;
                    passedGo = false;
                }
    
                for (; probes > 0; probes--) { 
                    if (p == null) { //如果循环变量为null
                        if (passedGo)//这说明p是head，既然head为null，说明单链表为空，退出循环
                            break;
                        //上一次遍历了尾节点，所以接下来让p变成头节点
                        o = null;
                        p = head;
                        passedGo = true;
                    }
                    final Itr it = p.get();
                    final Node next = p.next;
                    //1. 如果迭代器已经被回收
                    //2. 如果迭代器已经失效（不能前进了，next不能返回值了）
                    if (it == null || it.isDetached()) { 
                        // found a discarded/exhausted iterator
                        probes = LONG_SWEEP_PROBES; // 循环次数重置为更大的16
                        // unlink p
                        p.clear();
                        p.next = null;
                        if (o == null) { //如果p是单链表的头节点
                            head = next;//把p的后继变成head
                            if (next == null) { //p后面已经没有节点了，那么清空操作
                                // We've run out of iterators to track; retire
                                itrs = null;
                                return;
                            }
                        }
                        else//如果p不是单链表的头节点
                            o.next = next;
                    } else { 
                        o = p;//保存旧p
                    }
                    p = next;//p后移
                }
                //循环结束后，记录遍历的最后一个节点
                this.sweeper = (p == null) ? null : o;
            }

逻辑看着复杂，其实就是遍历一个单链表，遍历一定的次数。每个节点就是一个用户创建出来的迭代器。

*  如果`final Itr it = p.get()`为null，说明这个迭代器用户已经不使用了，并且被GC回收了，那么我们也清理掉这个Node，以免内存泄漏。
 *  如果`it.isDetached()`迭代器已经失效。这种情况我们前面已经讲过，此时`cursor nextIndex nextItem`都肯定是无效值了（迭代器已经返回过了最后一个可遍历元素），但lastRet和lastItem可能是有效值。现在看起来，Itrs关心的是`cursor nextIndex nextItem`是否是无效值，如果是无效值，就不需要在Itrs里管理这个迭代器了。

# ArrayBlockingQueue里对Itrs的调用 #

要分析为什么Itrs会去掉失效的迭代器，得先去看ArrayBlockingQueue里对Itrs的调用都是些什么。

在`ArrayBlockingQueue#removeAt`中，有两处调用：

*  如果删除的刚好是队首（这刚好是一个出队动作，不算是内部删除），那么执行`itrs.elementDequeued()`。
 *  如果删除的不是队首，那都算是内部删除，那么执行`itrs.removedAt(removeIndex)`。

这两处调用说明队列执行删除操作时，可能会对所有的迭代器进行某种更新，以让这些迭代器“感受”到删除动作。

## itrs.elementDequeued() ##

先看看`elementDequeued`干了什么：

void elementDequeued() { 
                // assert lock.getHoldCount() == 1;
                if (count == 0)//如果队列为空
                    queueIsEmpty();
                else if (takeIndex == 0)//如果队列非空，但takeIndex回到了0
                    takeIndexWrapped();
                //其他情况啥也不用干
            }

在`elementDequeued`中，如果队列为空：

//Itrs的函数
            void queueIsEmpty() { 
                // assert lock.getHoldCount() == 1;
                for (Node p = head; p != null; p = p.next) { //访问单链表每个节点
                    Itr it = p.get();
                    if (it != null) { 
                        p.clear();
                        it.shutdown();//
                    }
                }
                head = null;
                itrs = null;
            }
    //Itr的函数
            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.
            }

如果队列为空，主要操作在`shutdown`里，把所有成员都变成无效值，除了nextItem，保证下一次next()能够返回它。

在`elementDequeued`中，如果队列非空，但takeIndex回到了0：

//Itrs的函数
            void takeIndexWrapped() { 
                // assert lock.getHoldCount() == 1;
                cycles++;//循环次数加1
                for (Node o = null, p = head; p != null;) { //遍历单链表每个节点
                	//检查每个节点是否需要从单链表中清除，做的事情和doSomeSweeping一模一样
                    final Itr it = p.get();
                    final Node next = p.next;
                    if (it == null || it.takeIndexWrapped()) { //调用了迭代器的takeIndexWrapped
                        // unlink p
                        // assert it == null || it.isDetached();
                        p.clear();
                        p.next = null;
                        if (o == null)
                            head = next;
                        else
                            o.next = next;
                    } else { 
                        o = p;
                    }
                    p = next;
                }
                if (head == null)   // no more iterators to track
                    itrs = null;
            }
    //Itr的函数
            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;
            }

清理掉已经失效的迭代器，或者通过prevCycles来发现失效的迭代器。

## itrs.removedAt(removeIndex) ##

void removedAt(int removedIndex) { 
                for (Node o = null, p = head; p != null;) { //遍历单链表每个节点
                	//检查每个节点是否需要从单链表中清除，做的事情和doSomeSweeping一模一样
                    final Itr it = p.get();
                    final Node next = p.next;
                    if (it == null || it.removedAt(removedIndex)) { //调用了迭代器的removedAt
                        // unlink p
                        // assert it == null || it.isDetached();
                        p.clear();
                        p.next = null;
                        if (o == null)
                            head = next;
                        else
                            o.next = next;
                    } else { 
                        o = p;
                    }
                    p = next;
                }
                if (head == null)   // no more iterators to track
                    itrs = null;
            }

迭代器的removedAt返回了true，也可以代表迭代器失效了。

//队列有一个内部删除动作时，会调用到每个迭代器的removedAt
            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);
                //removedDistance代表删除索引相对于上一次队首快照，移动了多少次
    
                //检测cursor是否已经过时
                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);
                    }
                }
                //检测lastRet是否已经过时
                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);
                    //x < removedDistance时，不做任何事，因为
                }
                //检测nextIndex是否已经过时
                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;
            }

这里面的逻辑和`incorporateDequeues`类似，这三个索引成员`cursor nextIndex lastRet`都需要被检查。![在这里插入图片描述][20200726192200343.jpg]  
检查逻辑很简单：

*  如果索引在被删除节点索引的前面，那么什么也不用做。
 *  如果索引刚好是被删除节点索引，那么标记为REMOVE。
 *  如果索引在被删除节点索引的后面，那么需要前移。比如上图的z索引。
 *  所谓的前面 后面，都是考虑了循环数组的。

但有一个地方很难理解，`if (removedIndex < takeIndex) cycleDiff++;`，为什么这里比较的不是prevTakeIndex而是takeIndex，明明最后的计算距离公式都是`(cycleDiff * len) + (removedIndex - prevTakeIndex)`。我直接画图解释。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 3]  
原因就是cycles之差只能体现循环数组的轮数，但不能体现出当前队列是否处于“队列前一半在数组后面，队列后一半在数组前面”这种状态。而处于这种状态，是需要再加cycles的，以得到正确距离。  
如上图，cycles不加1，最终removedDistance算出来居然是1。实际应该是7。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 4]  
如上情况，公式为：轮数1 \* 长度6 + (1-2) = 5。此处的轮数，也执行了`if (removedIndex < takeIndex) cycleDiff++;`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 5]  
如上情况，公式为：轮数1 \* 长度6 + (1-4) = 2。

## 为什么Itrs会去掉失效的迭代器 ##

如果`it.isDetached()`迭代器已经失效，此时`cursor nextIndex nextItem`都肯定是无效值了，最多lastRet和lastItem可能是有效值（无效值的情况更不用考虑，这种情况的迭代器完全没有用了）。

原因就是：

*  `cursor nextIndex nextItem`都肯定是无效值了，不需要做改变了。
 *  lastRet和lastItem是有效值，是为了之后调用迭代器的remove。也就是说这个迭代器的作用只剩下了`Itr#remove`的作用，那么Itrs也不需要管理它了。

# 总结 #

*  ArrayBlockingQueue的迭代器的整体设计很复杂，主要在于它需要去保证自己总是能保持 队首队尾索引，并以队首队尾索引为基础进行下一次的遍历。
 *  迭代器使用了一种“队首快照”的办法，用于发现 返回元素 相较与上一次快照时，实际上它已经被删除的情况。使得lastRet为REMOVE，从而让`Itr#remove`不会执行删除动作。
 *  还考虑内部删除节点的情景，这种情况需要 索引左移。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70]: /images/20230208/a6dcdea97dc24b9ab397670af5420009.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 1]: /images/20230208/8a55b3dad0a845dc8b0c0ea0500cb5d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 2]: /images/20230208/84a1bf7173aa44f68477ad421efd2c97.png
[20200726192200343.jpg]: /images/20230208/55f7e703771347dc8f292999b0e891eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 3]: /images/20230208/824136993de4456f9ce139dc970f3333.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 4]: /images/20230208/843ba473159345fd8d56bc7ae1071318.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 5]: /images/20230208/a942cdef0f244c039f1f09164d72bafd.png