阻塞队列 — ArrayBlockingQueue源码分析
2020-11-22 本文已影响0人
一角钱技术
点赞再看，养成习惯，公众号搜一搜【一角钱技术】关注更多原创技术文章。
本文 GitHub org_hejianhui/JavaStudy 已收录，有我的系列文章。
前言
ArrayBlockingQueue 由数组支持的有界阻塞队列，队列基于数组实现，容量大小在创建 ArrayBlockingQueue 对象时已经定义好。 此队列按照先进先出（FIFO）的原则对元素进行排序。支持公平锁和非公平锁，默认采用非公平锁。其数据结构如下图：
注：每一个线程在获取锁的时候可能都会排队等待，如果在等待时间上，先获取锁的线程和请求一定先被满足，那么这个锁就是公平的。反之，这个锁就是不公平的。公平的获取锁，也就是当前等待时间最长的线程先获取锁
队列创建
BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<>(5);
应用场景
在线程池中有比较多的应用，生产者消费者场景。
- 先进先出队列（队列头的是最先进队的元素；队列尾的是最后进队的元素）
- 有界队列（即初始化时指定的容量，就是队列最大的容量，不会出现扩容，容量满，则阻塞进队操作；容量空，则阻塞出队操作）
- 队列不支持空元素
- 公平性 (fairness)可以在构造函数中指定。
此类支持对等待的生产者线程和使用者线程进行排序的可选公平策略。默认情况下，不保证是这种排序。然而，通过在构造函数将公平性 (fairness) 设置为 true 而构造的队列允许按照 FIFO 顺序访问线程。公平性通常会降低吞吐量，但也减少了可变性和避免了“不平衡性”。
工作原理
ArrayBlockingQueue是对BlockingQueue的一个数组实现，它使用一把全局的锁并行对queue的读写操作，同时使用两个Condition阻塞容量为空时的取操作和容量满时的写操作。
基于 ReentrantLock 保证线程安全，根据 Condition 实现队列满时的阻塞。
final ReentrantLock lock;
private final Condition notEmpty;
private final Condition notFull;
Lock的作用是提供独占锁机制，来保护竞争资源；而Condition是为了更加精细的对锁进行控制，它依赖于Lock，通过某个条件对多线程进行控制。
notEmpty表示“锁的非空条件”。当某线程想从队列中取数据时，而此时又没有数据，则该线程通过notEmpty.await()进行等待；当其它线程向队列中插入了元素之后，就调用notEmpty.signal()唤醒“之前通过notEmpty.await()进入等待状态的线程”。
同理，notFull表示“锁的满条件”。当某线程想向队列中插入元素，而此时队列已满时，该线程等待；当其它线程从队列中取出元素之后，就唤醒该等待的线程。
试图向已满队列中放入元素会导致放入操作受阻塞，直到BlockingQueue里有新的唤空间才会被醒继续操作；
试图从空队列中检索元素将导致类似阻塞，直到BlocingkQueue进了新货才会被唤醒。
源码分析
以下源码分析基于JDK1.8
定义
ArrayBlockingQueue的类继承关系如下：
其包含的方法定义如下：
成员属性
/** 真正存入数据的数组 */
final Object[] items;
/** take，poll，peek or remove 的下一个索引 */
int takeIndex;
/** put，offer，or add 下一个索引 */
int putIndex;
/** 队列中元素个数 */
int count;
/** 可重入锁 */
final ReentrantLock lock;
/** 如果数组是空的，在该Condition上等待 */
private final Condition notEmpty;
/** 如果数组是满的，在该Condition上等待 */
private final Condition notFull;
/** 遍历器实现 */
transient Itrs itrs = null;
构造函数
/**
* 构造函数，设置队列的初始容量
*/
public ArrayBlockingQueue(int capacity) {
this(capacity, false);
}
/**
* 构造函数，
* capacity and the specified access policy.
*
* @param capacity 设置数组大小
* @param fair 设置是否为公平锁
* @throws IllegalArgumentException if {@code capacity < 1}
*/
public ArrayBlockingQueue(int capacity, boolean fair) {
if (capacity <= 0)
throw new IllegalArgumentException();
this.items = new Object[capacity];
// 是否为公平锁，如果是的话，那么先到的线程先获得锁对象
// 否则，由操作系统调度由哪个线程获得锁，一般为false，性能会比较高
lock = new ReentrantLock(fair);
notEmpty = lock.newCondition();
notFull = lock.newCondition();
}
/**
* 构造函数，带有初始内容的队列
*/
public ArrayBlockingQueue(int capacity, boolean fair,
Collection<? extends E> c) {
this(capacity, fair);
final ReentrantLock lock = this.lock;
//加锁的目的是为了其他CPU能够立即看到修改
//加锁和解锁底层都是CAS，会强制修改写回主存，对其他CPU可见
lock.lock(); // 要给数组设置内容，先上锁
try {
int i = 0;
try {
for (E e : c) {
checkNotNull(e);
items[i++] = e; // 依次拷贝内容
}
} catch (ArrayIndexOutOfBoundsException ex) {
throw new IllegalArgumentException();
}
count = i;
putIndex = (i == capacity) ? 0 : i; // 如果 putIndex大于数组大小，那么从0重写开始
} finally {
lock.unlock(); // 最后一定要释放锁
}
}
入队方法
add / offer / put，这三个方法都是往队列中添加元素，说明如下：
- add方法依赖于offer方法，如果队列满了则抛出异常，否则添加成功返回true；
- offer方法有两个重载版本，只有一个参数的版本，如果队列满了就返回false，否则加入到队列中，返回true，add方法就是调用此版本的offer方法；另一个带时间参数的版本，如果队列满了则等待，可指定等待的时间，如果这期间中断了则抛出异常，如果等待超时了则返回false，否则加入到队列中返回true；
- put方法跟带时间参数的offer方法逻辑一样，不过没有等待的时间限制，会一直等待直到队列有空余位置了，再插入到队列中，返回true
/**
* 添加一个元素，其实super.add里面调用了offer方法
*/
public boolean add(E e) {
return super.add(e);
}
/**
* 加入成功返回 true，否则返回 false
*/
public boolean offer(E e) {
// 创建插入的元素是否为null，是的话抛出NullPointerException异常
checkNotNull(e);
// 获取“该阻塞队列的独占锁”
final ReentrantLock lock = this.lock;
lock.lock(); // 上锁
try {
// 如果队列已满，则返回false。
if (count == items.length) // 超过数组的容量
return false;
else {
// 如果队列未满，则插入e，并返回true。
enqueue(e);
return true;
}
} finally {
// 释放锁
lock.unlock();
}
}
/**
* 如果队列已满的话，就会等待
*/
public void put(E e) throws InterruptedException {
checkNotNull(e);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly(); //和lock方法的区别是让它在阻塞时可以抛出异常跳出
try {
while (count == items.length)
notFull.await(); // 这里就是阻塞了，要注意：如果运行到这里，那么它会释放上面的锁，一直等到 notify
enqueue(e);
} finally {
lock.unlock();
}
}
/**
* 带有超时事件的插入方法，unit 表示是按秒、分、时哪一种
*/
public boolean offer(E e, long timeout, TimeUnit unit)
throws InterruptedException {
checkNotNull(e);
long nanos = unit.toNanos(timeout);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == items.length) {
if (nanos <= 0)
return false;
nanos = notFull.awaitNanos(nanos); // 带有超时等待的阻塞方法
}
enqueue(e); // 入队
return true;
} finally {
lock.unlock();
}
}
出队方法
poll / take / peek，这几个方法都是获取队列顶的元素，具体说明如下：
- poll方法有两个重载版本，第一个版本，如果队列是空的，返回null，否则移除并返回队列头部元素；另一个带时间参数的版本，如果栈为空则等待，可以指定等待的时间，如果等待超时了则返回null，如果被中断了则抛出异常，否则移除并返回栈顶元素
- take方法同带时间参数的poll方法，但是不能指定等待时间，会一直等待直到队列中有元素为止，然后移除并返回栈顶元素
- peek方法只是返回队列头部元素，不移除
// 实现的方法，如果当前队列为空，返回null
public E poll() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return (count == 0) ? null : dequeue();
} finally {
lock.unlock();
}
}
// 实现的方法，如果当前队列为空，一直阻塞
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == 0)
notEmpty.await(); // 队列为空，阻塞方法
return dequeue();
} finally {
lock.unlock();
}
}
// 带有超时事件的取元素方法，否则返回null
public E poll(long timeout, TimeUnit unit) throws InterruptedException {
long nanos = unit.toNanos(timeout);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == 0) {
if (nanos <= 0)
return null;
nanos = notEmpty.awaitNanos(nanos); // 超时等待
}
return dequeue(); // 取得元素
} finally {
lock.unlock();
}
}
// 只是看一个队列最前面的元素，取出是不擅长队列中原来的元素，队列为空时返回null
public E peek() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return itemAt(takeIndex); // 队列为空时返回null
} finally {
lock.unlock();
}
}
删除元素方法
remove / clear /drainT，这三个方法用于从队列中移除元素，具体说明如下：
- remove方法用于移除某个元素，如果栈为空或者没有找到该元素则返回false，否则从栈中移除该元素；移除时，如果该元素位于栈顶则直接移除，如果位于栈中间，则需要将该元素后面的其他元素往前面挪动，移除后需要唤醒因为栈满了而阻塞的线程
- clear方法用于整个栈，同时将takeIndex置为putIndex，保证栈中的元素先进先出；最后会唤醒最多count个线程，因为正常一个线程插入一个元素，如果唤醒超过count个线程，可能导致部分线程因为栈满了又再次被阻塞
- drainTo方法有两个重载版本，一个是不带个数，将所有的元素都移除并拷贝到指定的集合中；一个带个数，将指定个数的元素移除并拷贝到指定的集合中，两者的底层实现都是同一个方法。移除后需要重置takeIndex和count，并唤醒最多移除个数的因为栈满而阻塞的线程。
/**
* 从队列中删除一个元素的方法。删除成功返回true，否则返回false
*/
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;
//从takeIndex开始往后遍历直到等于putIndex
do {
if (o.equals(items[i])) {
removeAt(i); // 真正删除的方法
return true;
}
//走到数组末尾了又从头开始，put时也按照这个规则来
if (++i == items.length)
i = 0;
} while (i != putIndex); // 一直不断的循环取出来做判断
}
//如果数组为空，返回false
return false;
} finally {
lock.unlock();
}
}
/**
* 指定删除索引上的元素.
*/
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) {
//如果移除的就是栈顶的元素
items[takeIndex] = null;
if (++takeIndex == items.length)
takeIndex = 0;
//元素个数减1
count--;
if (itrs != null)
itrs.elementDequeued();
} else {
// an "interior" remove
// 如果移除的是栈中间的某个元素，需要将该元素后面的元素往前挪动
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 {
//如果下一个元素的索引等于putIndex，说明i就是栈中最后一个元素了，直接将该元素置为null
items[i] = null;
//重置putIndex为i
this.putIndex = i;
break;
}
}
count--;
if (itrs != null)
//通知itrs节点移除了
itrs.removedAt(removeIndex);
}
//唤醒因为栈满了而等待的线程
notFull.signal(); // 有一个元素删除成功，那肯定队列不满
}
/**
* 清空队列
*/
public void clear() {
final Object[] items = this.items;
final ReentrantLock lock = this.lock;
lock.lock();
try {
int k = count;
if (k > 0) {
final int putIndex = this.putIndex;
int i = takeIndex;
//从takeIndex开始遍历直到i等于putIndex，将数组元素置为null
do {
items[i] = null;
if (++i == items.length)
i = 0;
} while (i != putIndex);
//注意此处没有将这两个index置为0，只是让他们相等，因为只要相等就可以实现栈先进先出了
takeIndex = putIndex;
count = 0;
if (itrs != null)
itrs.queueIsEmpty();
//如果有因为栈满了而等待的线程，则将其唤醒
//注意这里没有使用signalAll而是通过for循环来signal多次，单纯从唤醒线程来看是可以使用signalAll的，效果跟这里的for循环是一样的
//如果有等待的线程，说明count就是当前线程的最大容量了，这里清空了，最多只能put count次，一个线程只能put 1次，只唤醒最多count个线程就避免了
//线程被唤醒后再次因为栈满了而阻塞
for (; k > 0 && lock.hasWaiters(notFull); k--)
notFull.signal();
}
} finally {
lock.unlock();
}
}
/**
* 取出所有元素到集合
*/
public int drainTo(Collection<? super E> c) {
return drainTo(c, Integer.MAX_VALUE);
}
/**
* 取出所有元素到集合
*/
public int drainTo(Collection<? super E> c, int maxElements) {
//校验参数合法
checkNotNull(c);
if (c == this)
throw new IllegalArgumentException();
if (maxElements <= 0)
return 0;
final Object[] items = this.items;
final ReentrantLock lock = this.lock;
lock.lock();
try {
//取两者之间的最小值
int n = Math.min(maxElements, count);
int take = takeIndex;
int i = 0;
try {
//从takeIndex开始遍历，取出元素然后添加到c中，直到满足个数要求为止
while (i < n) {
@SuppressWarnings("unchecked")
E x = (E) items[take];
c.add(x);
items[take] = null;
if (++take == items.length)
take = 0;
i++;
}
return n;
} finally {
// Restore invariants even if c.add() threw
if (i > 0) {
//取完了，修改count减去i
count -= i;
takeIndex = take;
if (itrs != null) {
if (count == 0)
//通知itrs 栈空了
itrs.queueIsEmpty();
else if (i > take)
//说明take中间变成0了，通知itrs
itrs.takeIndexWrapped();
}
//唤醒在因为栈满而等待的线程，最多唤醒i个，同上避免线程被唤醒了因为栈又满了而阻塞
for (; i > 0 && lock.hasWaiters(notFull); i--)
notFull.signal();
}
}
} finally {
lock.unlock();
}
}
iterator / Itr / Itrs
Itr和Itrs都是ArrayBlockingQueue的两个内部类，如下：
iterator方法返回一个迭代器实例，用于实现for循环遍历和部分Collection接口，该方法的实现如下：
public Iterator<E> iterator() {
return new Itr();
}
Itr() {
// assert lock.getHoldCount() == 0;
lastRet = NONE;
final ReentrantLock lock = ArrayBlockingQueue.this.lock;
lock.lock();
try {
if (count == 0) {
//NONE和DETACHED都是常量
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，将当前线程注册到Itrs
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();
}
}
Itrs(Itr initial) {
register(initial);
}
//根据index计算cursor
private int incCursor(int index) {
// assert lock.getHoldCount() == 1;
if (++index == items.length)
index = 0;
if (index == putIndex)
index = NONE;
return index;
}
/**
* 创建一个新的Itr实例时，会调用此方法将该实例添加到Node链表中
*/
void register(Itr itr) {
//创建一个新节点将其插入到head节点的前面
head = new Node(itr, head);
}
doSomeSweeping / register
Itrs内部维护了一个Itr实例链表，register方法用于将一个新的Itr实例加入到链表头，doSomeSweeping方法用于清除该链表中无效的Itr实例，查找这类实例是通过for循环实现的，初始for循环的次数是通过参数tryHandler控制的，如果为true，则循环16次，如果为false，则循环4次，在循环的过程中找到了一个无效的Itr实例，则需要再遍历16次，直到所有节点都遍历完成。注意这里的无效指的这个Itr实例已经同Itrs datached了，当ArrayBlockingQueue执行Itrs的回调方法时就不会处理这种Itr实例了，即Itr实例无法感知到ArrayBlockingQueue的改变了，这时基于Itr实例遍历的结果可能就不准确了。
/**
* 创建一个新的Itr实例时，会调用此方法将该实例添加到Node链表中
*/
void register(Itr itr) {
//创建一个新节点将其插入到head节点的前面
head = new Node(itr, head);
}
/**
* 用于清除该链表中无效的Itr实例
*/
void doSomeSweeping(boolean tryHarder) {
// assert lock.getHoldCount() == 1;
// assert head != null;
//probes表示循环查找的次数
int probes = tryHarder ? LONG_SWEEP_PROBES : SHORT_SWEEP_PROBES;
Node o, p;
final Node sweeper = this.sweeper;
boolean passedGo; // to limit search to one full sweep
//o表示上一个有效节点，p表示当前遍历的节点，如果o为空，则p是head，否则是o的下一个节点
//进入此方法，sweeper可能为null，head不会为null
if (sweeper == null) {
o = null;
p = head;
passedGo = true;
} else {
o = sweeper;
p = o.next;
passedGo = false;
}
for (; probes > 0; probes--) {
if (p == null) {
if (passedGo)
break;//sweeper为null时，passedGo为true，终止循环，将sweeper赋值
//passedGo为false，sweeper不为null，因为p为null，还是将其置为true，即只能循环一次
o = null;
p = head;
passedGo = true;
}
//获取关联的Itr
final Itr it = p.get();
final Node next = p.next;
if (it == null || it.isDetached()) {
//如果it为null或者已经解除关联了
//只要找到了一个无效节点，则需要再遍历LONG_SWEEP_PROBES次，直到所有节点遍历完为止
probes = LONG_SWEEP_PROBES; // "try harder"
//将关联的Itr置为null
p.clear();
p.next = null;
if (o == null) {//sweeper为null或者sweeper的next为null时
//没有找到有效节点，重置head，将next之前的节点都移除
head = next;
if (next == null) {
//next为null，没有待处理的节点了，所以Itr都退出了，将itrs置为null
itrs = null;
return;
}
} else
//将next作为o的下一个节点，即将p移除了
o.next = next;
} else {
//p对应的Itr实例是有效的，将o置为p
o = p;
}
//处理下一个节点
p = next;
}
//重置sweeper，p等于null说明节点都遍历完了，sweeper为null
//如果p不等于null，说明还有未遍历的节点，将sweeper置为0，下一次遍历时可以重新从该节点开始遍历
this.sweeper = (p == null) ? null : o;
}
queueIsEmpty / elementDequeued / takeIndexWrapped / removedAt
这四个方法都是在某种条件下，由ArrayBlockingQueue回调Itrs的方法，具体如下：
- queueIsEmpty方法用于因为元素移除栈空了时调用的，会将Itr链表中的所有元素对Itr实例的引用置为null，将Itr实例的各属性置为null或者特殊index值
- takeIndexWrapped方法用于takeIndex变成0了后调用，会增加cycles计数，如果当前cycles属性减去Itr实例的prevCycles属性大于1，则说明Itr初始化时栈中的元素都被移除了，此时再遍历无意义，将这类节点从Itr实例链表中移除，将对Itr的引用置为null，将Itr实例的各属性置为null或者特殊index值
- removedAt方法用于从栈中注意不是栈顶移除元素时调用的，会重新计算cursor，lastRet，nextIndex等属性，如果计算出来的属性小于0，则将这个节点从Itr实例链表中移除，将Itr实例的各属性置为null或者特殊index值
- elementDequeued方法时元素从栈顶移除时调用，如果当前栈空了则调用queueIsEmpty方法，如果takeIndex变成0了，则调用takeIndexWrapped方法
/**
* 从栈顶移除一个元素时回调的
*/
void elementDequeued() {
// assert lock.getHoldCount() == 1;
if (count == 0)
queueIsEmpty(); //如果栈空了
else if (takeIndex == 0)
takeIndexWrapped();
}
/**
* 栈变成空的以后回调此方法
*/
void queueIsEmpty() {
// assert lock.getHoldCount() == 1;
//遍历链表
for (Node p = head; p != null; p = p.next) {
Itr it = p.get();
if (it != null) {
//将引用清除
p.clear();
//通知Itr队列空了，将各参数置为null或者特殊index值
it.shutdown();
}
}
//重置为null
head = null;
itrs = null;
}
/**
* 当takeIndex变成0的时候回调的
*/
void takeIndexWrapped() {
// assert lock.getHoldCount() == 1;
cycles++;
//遍历链表，o表示上一个有效节点，p表示当前遍历的节点
for (Node o = null, p = head; p != null;) {
final Itr it = p.get();
final Node next = p.next;
if (it == null || it.takeIndexWrapped()) {
// unlink p
// assert it == null || it.isDetached();
p.clear();
p.next = null;
if (o == null)
//之前的节点是无效节点，重置head，把next之前的节点都移除了
head = next;
else
//移除p这一个节点
o.next = next;
} else {
//保存上一个有效节点
o = p;
}
//处理下一个节点
p = next;
}
//没有有效节点，itrs置为null
if (head == null) // no more iterators to track
itrs = null;
}
/**
* 栈中某个元素被移除时调用
*/
void removedAt(int removedIndex)
//遍历链表
for (Node o = null, p = head; p != null;) {
final Itr it = p.get();
final Node next = p.next;
//removedAt方法判断这个节点是否被移除了
if (it == null || it.removedAt(removedIndex)) {
// unlink p
// assert it == null || it.isDetached();
//将p从链表中移除
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) {
// cycles不一致了，则原来栈中的元素可能都没了
shutdown();
return true;
}
return false;
}
void shutdown() {
// assert lock.getHoldCount() == 1;
//nextItem没有被置为null，通过next方法还可以返回
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.
}
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;
//按照特定的逻辑重新计算cursor，lastRet，nextIndex等属性
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;
}
private int distance(int index, int prevTakeIndex, int length) {
int distance = index - prevTakeIndex;
if (distance < 0)
distance += length;
return distance;
}
next / hasNext / remove
这三个方法时Itr对Iterator接口的实现，如下：
public boolean hasNext() {
// assert lock.getHoldCount() == 0;
if (nextItem != null)
return true;
//如果没有下一个元素了
noNext();
return false;
}
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();
//如果isDetached为true还会继续执行
// assert nextIndex != NONE;
// assert lastItem == null;
lastRet = nextIndex;
final int cursor = this.cursor;
if (cursor >= 0) {
//获取指定cursor的元素
nextItem = itemAt(nextIndex = cursor);
//重新计算cursor，如果等于putIndex就将其置为None
this.cursor = incCursor(cursor);
} else {
//已经遍历到putIndex处了，上次incCursor计算时将其变成负值
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())
//移除lastRet处的元素
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(); //将当前Itr标记为无效并尝试清理掉
} finally {
lock.unlock();
// assert lastRet == NONE;
// assert lastItem == null;
}
}
private void noNext() {
final ReentrantLock lock = ArrayBlockingQueue.this.lock;
lock.lock();
try {
// assert cursor == NONE;
// assert nextIndex == NONE;
if (!isDetached()) {
// assert lastRet >= 0;
//如果当前Itr还是有效的
incorporateDequeues(); // might update lastRet
if (lastRet >= 0) {
lastItem = itemAt(lastRet);
// assert lastItem != null;
detach();
}
}
// assert isDetached();
// assert lastRet < 0 ^ lastItem != null;
} finally {
lock.unlock();
}
}
boolean isDetached() {
// assert lock.getHoldCount() == 1;
return prevTakeIndex < 0;
}
/**
* 校验并调整相关属性
*/
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);
// 校验各属性是否有效
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;
}
}
}
/**
* 校验这个index是否有效，返回true表示无效
*/
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;
}
private void detach() {
if (prevTakeIndex >= 0) {
// 将当前Itr标记为无效的
prevTakeIndex = DETACHED;
//尝试将当前Itr从链表中移除
itrs.doSomeSweeping(true);
}
}
//根据index计算cursor
private int incCursor(int index) {
// assert lock.getHoldCount() == 1;
if (++index == items.length)
index = 0;
if (index == putIndex)
index = NONE;
return index;
}
总结
ArrayBlockingQueue是一个阻塞队列，内部由ReentrantLock来实现线程安全，由Condition的await和signal来实现等待唤醒的功能。它的数据结构是数组，准确的说是一个循环数组（可以类比一个圆环），所有的下标在到达最大长度时自动从0继续开始。
PS：以上代码提交在 Github ：https://github.com/Niuh-Study/niuh-juc-final.git
文章持续更新，可以公众号搜一搜「 一角钱技术 」第一时间阅读， 本文 GitHub org_hejianhui/JavaStudy 已经收录，欢迎 Star。
