/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

else {
    Node<K,V> e; K k;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

transient Object[] elementData;

/**
  * Appends the specified element to the end of this list.
  *
  * @param e element to be appended to this list
  * @return <tt>true</tt> (as specified by {@link Collection#add})
  */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/*
  * Private remove method that skips bounds checking and does not
  * return the value removed.
  */
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                          numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

@SuppressWarnings("unchecked")
public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

// modCount是ArrayList中的属性值，是集合添加元素、删除元素的次数，expectedModCount是迭代器中的属性值，是预期的修改次数。实际修改值与期望值不同
final void checkForComodification() {
  if (modCount != expectedModCount)
      throw new ConcurrentModificationException();
}

for (int i = 0; i < list.size(); i++){
  if(list[i] == 'xxx'){
    list.remove(i);
  }
}

for (int i = 0; i < list.size(); i++){
  if(list[i] == 'xxx'){
    list.remove(i);
    i--;
  }
}

2020-06-01 14:37:49 [ERROR] [task-3] xxx -失败！
java.util.ConcurrentModificationException: null
  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:859) ~[na:1.7.0_80]
  at java.util.ArrayList$Itr.next(ArrayList.java:831) ~[na:1.7.0_80]
2020-06-01 14:37:49 [ERROR] [qtp1073067421-33398] xxx -失败！
java.util.ConcurrentModificationException: null
  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:859) ~[na:1.7.0_80]
  at java.util.ArrayList$Itr.next(ArrayList.java:831) ~[na:1.7.0_80]

// 支持中断的 API
void lockInterruptibly() 
  throws InterruptedException;
// 支持超时的 API
boolean tryLock(long time, TimeUnit unit) 
  throws InterruptedException;
// 支持非阻塞获取锁的 API
boolean tryLock();

public ThreadPoolExecutor(int corePoolSize,
                          int maximumPoolSize,
                          long keepAliveTime,
                          TimeUnit unit,
                          BlockingQueue<Runnable> workQueue,
                          ThreadFactory threadFactory,
                          RejectedExecutionHandler handler) {
    if (corePoolSize < 0 ||
        maximumPoolSize <= 0 ||
        maximumPoolSize < corePoolSize ||
        keepAliveTime < 0)
        throw new IllegalArgumentException();
    if (workQueue == null || threadFactory == null || handler == null)
        throw new NullPointerException();
    this.acc = System.getSecurityManager() == null ?
        null :
    AccessController.getContext();
    this.corePoolSize = corePoolSize;
    this.maximumPoolSize = maximumPoolSize;
    this.workQueue = workQueue;
    this.keepAliveTime = unit.toNanos(keepAliveTime);
    this.threadFactory = threadFactory;
    this.handler = handler;
}

int corePoolSize,
int maximumPoolSize,
long keepAliveTime,
TimeUnit unit,
BlockingQueue<Runnable> workQueue,
ThreadFactory threadFactory,
RejectedExecutionHandler handler

public void execute(Runnable command) {
    if (command == null)
        throw new NullPointerException();
    /*
         * Proceed in 3 steps:
         *
         * 1. If fewer than corePoolSize threads are running, try to
         * start a new thread with the given command as its first
         * task.  The call to addWorker atomically checks runState and
         * workerCount, and so prevents false alarms that would add
         * threads when it shouldn't, by returning false.
         *
         * 2. If a task can be successfully queued, then we still need
         * to double-check whether we should have added a thread
         * (because existing ones died since last checking) or that
         * the pool shut down since entry into this method. So we
         * recheck state and if necessary roll back the enqueuing if
         * stopped, or start a new thread if there are none.
         *
         * 3. If we cannot queue task, then we try to add a new
         * thread.  If it fails, we know we are shut down or saturated
         * and so reject the task.
         */
    int c = ctl.get();
    if (workerCountOf(c) < corePoolSize) {
        if (addWorker(command, true))
            return;
        c = ctl.get();
    }
    if (isRunning(c) && workQueue.offer(command)) {
        int recheck = ctl.get();
        if (! isRunning(recheck) && remove(command))
            reject(command);
        else if (workerCountOf(recheck) == 0)
            addWorker(null, false);
    }
    else if (!addWorker(command, false))
        reject(command);
}

throw new RejectedExecutionException("Task " + r.toString() +
                                                 " rejected from " +
                                                 e.toString());

int c = ctl.get();
if (workerCountOf(c) < corePoolSize) {
    if (addWorker(command, true))
        return;
    c = ctl.get();
}

private final AtomicInteger ctl = new AtomicInteger(ctlOf(RUNNING, 0));
private static int ctlOf(int rs, int wc) { return rs | wc; }

private static int workerCountOf(int c)  { 
    return c & CAPACITY; 
}

00011111 11111111 11111111 11111111

private boolean addWorker(Runnable firstTask, boolean core) {
    retry:
    for (;;) {
        int c = ctl.get();
        int rs = runStateOf(c);

        // Check if queue empty only if necessary.
        if (rs >= SHUTDOWN &&
            ! (rs == SHUTDOWN &&
               firstTask == null &&
               ! workQueue.isEmpty()))
            return false;

        for (;;) {
            int wc = workerCountOf(c);
            if (wc >= CAPACITY ||
                wc >= (core ? corePoolSize : maximumPoolSize))
                return false;
            if (compareAndIncrementWorkerCount(c))
                break retry;
            c = ctl.get();  // Re-read ctl
            if (runStateOf(c) != rs)
                continue retry;
            // else CAS failed due to workerCount change; retry inner loop
        }
    }

    boolean workerStarted = false;
    boolean workerAdded = false;
    Worker w = null;
    try {
        w = new Worker(firstTask);
        final Thread t = w.thread;
        if (t != null) {
            final ReentrantLock mainLock = this.mainLock;
            mainLock.lock();
            try {
                // Recheck while holding lock.
                // Back out on ThreadFactory failure or if
                // shut down before lock acquired.
                int rs = runStateOf(ctl.get());

                if (rs < SHUTDOWN ||
                    (rs == SHUTDOWN && firstTask == null)) {
                    if (t.isAlive()) // precheck that t is startable
                        throw new IllegalThreadStateException();
                    workers.add(w);
                    int s = workers.size();
                    if (s > largestPoolSize)
                        largestPoolSize = s;
                    workerAdded = true;
                }
            } finally {
                mainLock.unlock();
            }
            if (workerAdded) {
                t.start();
                workerStarted = true;
            }
        }
    } finally {
        if (! workerStarted)
            addWorkerFailed(w);
    }
    return workerStarted;
}

private static int runStateOf(int c)     { return c & ~CAPACITY; }

11100000 00000000 00000000 00000000

if (rs >= SHUTDOWN &&
    ! (rs == SHUTDOWN &&
       firstTask == null &&
       ! workQueue.isEmpty()))
    return false;

rs >= SHUTDOW

! (rs == SHUTDOWN && firstTask == null && ! workQueue.isEmpty())

for (;;) {
    // 第一步，拿到当前的有效线程数
    int wc = workerCountOf(c);
    // 如果当前有效线程数已经大于等于允许的最大线程数，不允许创建
    // 如果正准备创建的线程是core的线程且大于线程池初始化时设定的线程数，不允许创建
    // 如果正准备创建的线程不是core但大于线程池初始化时设定的最大线程数，不允许创建
    if (wc >= CAPACITY ||
        wc >= (core ? corePoolSize : maximumPoolSize))
        return false;
    // 利用CAS做自增操作，如果成功了，就跳出循环体开始下一步操作，如果失败则重试
    if (compareAndIncrementWorkerCount(c))
        break retry;
    // 重新读取当前的runstate，如果当前的runstate和循环体中的runstate有变化，则重新去判断是否需要创建线程
    c = ctl.get();  // Re-read ctl
    if (runStateOf(c) != rs)
        continue retry;
    // else CAS failed due to workerCount change; retry inner loop
}

   // 标记线程是否启动
boolean workerStarted = false;
// 标记线程是否被添加
   boolean workerAdded = false;
   Worker w = null;
   try {
       w = new Worker(firstTask);
       final Thread t = w.thread;
       if (t != null) {
           final ReentrantLock mainLock = this.mainLock;
           // 获取锁
           mainLock.lock();
           try {
               // Recheck while holding lock.
               // Back out on ThreadFactory failure or if
               // shut down before lock acquired.
               int rs = runStateOf(ctl.get());
      // 再检查一下当前线程池的状态
               // rs < SHUTDOWN 表示线程池的状态为RUNNING就直接创建线程
               // rs == SHUTDOWN && firstTask == null 当前线程已经处于SHUTDOWN且当前没有新建的任务（也就是为了把任务队列执行完）
               if (rs < SHUTDOWN ||
                   (rs == SHUTDOWN && firstTask == null)) {
                   // 如果正准备创建的线程已经处于alive状态，则抛出异常
                   if (t.isAlive()) // precheck that t is startable
                       throw new IllegalThreadStateException();
                   // 否则放到workers中（包含线程池中所有的工作线程，将新构造的工作线程加入到工作线程集合中）
                   workers.add(w);
                   int s = workers.size();
                   if (s > largestPoolSize)
                       largestPoolSize = s;
                   workerAdded = true;
               }
           } finally {
               mainLock.unlock();
           }
           if (workerAdded) {
               t.start();
               workerStarted = true;
           }
       }
   } finally {
       if (! workerStarted)
           addWorkerFailed(w);
   }

   // 检查当前线程池状态，如果为RUNNING状态，则尝试将任务放到任务队列中  
if (isRunning(c) && workQueue.offer(command)) {
       int recheck = ctl.get();
       // 放置成功以后，再次检查当前的线程池状态，如果当前线程池状态非RUNNING，则尝试将刚刚放入的任务从任务队列中移除
       if (! isRunning(recheck) && remove(command))
           reject(command);
       // 如果当前线程数状态为RUNNING，但是workerCount的值又等于0则传入空任务结束此次创建
       else if (workerCountOf(recheck) == 0)
           addWorker(null, false);
   }

else if (!addWorker(command, false))
    reject(command);

final void runWorker(Worker w) {
    Thread wt = Thread.currentThread(); // 得到当前线程
    Runnable task = w.firstTask; // 得到Worker中的任务task，也就是用户传入的task
    w.firstTask = null; // 将Worker中的任务置空
    w.unlock(); // allow interrupts。 
    boolean completedAbruptly = true; // 标识当前Worker异常结束，默认是异常结束
    try {
        // 如果worker中的任务不为空，执行执行任务
        // 否则使用getTask获得任务。一直循环，除非得到的任务为空才退出
        while (task != null || (task = getTask()) != null) {
            // 如果拿到了任务，给自己上锁，表示当前Worker已经要开始执行任务了，
            // 已经不是处于闲置Worker(闲置Worker的解释请看下面的线程池关闭)
            w.lock();  
            // 在执行任务之前先做一些处理。 
            // 1. 如果线程池已经处于STOP状态并且当前线程没有被中断，中断线程 
            // 2. 如果线程池还处于RUNNING或SHUTDOWN状态，并且当前线程已经被中断了，
            // 重新检查一下线程池状态，如果处于STOP状态并且没有被中断，那么中断线程
            if ((runStateAtLeast(ctl.get(), STOP) ||
                 (Thread.interrupted() &&
                  runStateAtLeast(ctl.get(), STOP))) &&
                !wt.isInterrupted())
                wt.interrupt();
            try {
                // 任务执行前需要做什么，ThreadPoolExecutor是个空实现，子类可以自行扩展
                beforeExecute(wt, task); 
                Throwable thrown = null;
                try {
                    // 真正的开始执行任务，这里run的时候可能会被中断，比如线程池调用了shutdownNow方法
                    task.run(); 
                } catch (RuntimeException x) { // 任务执行发生的异常全部抛出，不在runWorker中处理
                    thrown = x; throw x;
                } catch (Error x) {
                    thrown = x; throw x;
                } catch (Throwable x) {
                    thrown = x; throw new Error(x);
                } finally {
                    // 任务执行结束需要做什么，ThreadPoolExecutor是个空实现，子类可以自行扩展
                    afterExecute(task, thrown); 
                }
            } finally {
                task = null;
                w.completedTasks++; // 记录执行任务的个数
                w.unlock(); // 执行完任务之后，解锁，Worker变成闲置Worker，等待执行下一个任务
            }
        }
        completedAbruptly = false; // 正常结束
    } finally {
        processWorkerExit(w, completedAbruptly); // Worker退出时执行
    }
}

// 存储队列元素的数组，是个循环数组
final Object[] items;

// 拿数据的索引，用于take，poll，peek，remove方法
int takeIndex;

// 放数据的索引，用于put，offer，add方法
int putIndex;

// 元素个数
int count;

// 可重入锁
final ReentrantLock lock;
// notEmpty条件对象，由lock创建
private final Condition notEmpty;
// notFull条件对象，由lock创建
private final Condition notFull;

// 构造函数要求指定队列大小capacity
/**
* capacity和fair，capacity同第一个构造方法，代表队列大小。fair代表该队列的访问策略是否公平。如果为     
* true，则按照 FIFO 顺序访问插入或移除时受阻塞线程的队列；如果为 false，则访问顺序是不确定的。这里fair参
* 数被设置为ReentrantLock的入参，就可以通过ReentrantLock来保证线程访问是否公平。而此构造方法创建了两个
* Condition，也就是条件，分别是notEmpty和notFull，Condition可以调用wait()和signal()来控制当前现
* 成等待或者唤醒
*/
// 默认fair为false
public ArrayBlockingQueue(int capacity, boolean fair,
                             Collection<? extends E> c) {
       this(capacity, fair);
       final ReentrantLock lock = this.lock;
       lock.lock(); // Lock only for visibility, not mutual exclusion
       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;
       } finally {
           lock.unlock();
       }
   }

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();
}

public boolean add(E e) {
  return super.add(e);
}

public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw  IllegalStateException("Queue full");
}

public boolean offer(E e) {
       // 不允许元素为空，为空会抛出NullPointerException异常
       checkNotNull(e);
       // 获取锁
       final ReentrantLock lock = this.lock;
       lock.lock();
       try {
           // 元素个数和当前存储队列元素的数组大小相等，就不会再加了，所以会返回false
           if (count == items.length)
               return false;
           else {
               // 入队操作
               enqueue(e);
               return true;
           }
       } finally {
           // 释放锁
           lock.unlock();
       }
   }

private void enqueue(E x) {
       // assert lock.getHoldCount() == 1;
       // assert items[putIndex] == null;
       final Object[] items = this.items;
       items[putIndex] = x;
       // 放数据索引+1，如果数据索引已经与存储队列的元素数量相同则变为0
       if (++putIndex == items.length)
           putIndex = 0;
       // 元素个数+1
       count++;
       // 使用条件对象notEmpty通知，比如使用take方法的时，队列中没有数据被阻塞。这个时候队列中新增了一条数据，需要调用signal通知
       notEmpty.signal();
   }

public void put(E e) throws InterruptedException {
       // 元素为空抛出NPE异常
       checkNotNull(e);
       final ReentrantLock lock = this.lock;
       // 加锁，保证调用put方法的时候只有一个线程
       lock.lockInterruptibly();
       try {
           // 如果队列满了，阻塞当前线程并加入到条件对象notFull的等待队列里
           while (count == items.length)
               // 线程阻塞并被挂起，同时释放锁
               notFull.await();
           // 入队
           enqueue(e);
       } finally {
           lock.unlock();
       }
   }

private void insert(E x) {
    items[putIndex] = x;
    putIndex = inc(putIndex);
    ++count;
    notEmpty.signal(); 
}

public E poll() {
    // 加锁，保证调用poll方法的时候只有一个线程
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        // 如果count=0，也就是队列中没有元素了，这时候会返回null，否则调用dequeue取元素
        return (count == 0) ? null : dequeue();
    } finally {
        lock.unlock();
    }
}

private E dequeue() {
    // assert lock.getHoldCount() == 1;
    // assert items[takeIndex] != null;
    final Object[] items = this.items;
    @SuppressWarnings("unchecked")
    // takeIndex是用于拿数据的索引
    E x = (E) items[takeIndex];
    // 取出数据以后，这个元素位置为null
    items[takeIndex] = null;
    // 如果当前拿数据的索引大小已经和元素数组大小相等则置为0，这里的takeIndex之所以自增是因为FIFO原则
    if (++takeIndex == items.length)
        takeIndex = 0;
    // 一个数据被取出，此时元素个数-1
    count--;
    // TODO
    if (itrs != null)
        itrs.elementDequeued();
    // 使用对象notFull通知，如使用put方法放置数据的时候队列满了，被阻塞，这个时候dequeue取出一条数据，队列没满，则可以继续放入
    notFull.signal();
    return x;
}

public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        // 如果队列为空，阻塞当前线程，并加入到条件对象notEmpty的等待队列里
        while (count == 0)
            // 线程阻塞并被挂起，同时释放锁
            notEmpty.await();
        return dequeue();
    } finally {
        lock.unlock();
    }
}

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;
            // 通过元素类型遍历,找到类型相同的索引位置，i<=元素总大小
            do {
                if (o.equals(items[i])) {
                    removeAt(i);
                    return true;
                }
                if (++i == items.length)
                    i = 0;
              // 因为putIndex就是最后一个放数据的位置，所以拿数据的索引不能等于它
              // 但是有没有想过为什么不可以写<=呢？
            } while (i != putIndex);
        }
        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;
    // 如果要删除数据的索引位置就是拿数据索引位置，直接将takeIndex索引位置上的数据，然后takeIndex+1
    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.
        // 如果要删除数据的索引位置不是takeIndex，则需要移动元素位置，更新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);
    }
    // 删除以后通知阻塞线程，比如put方法
    notFull.signal();
}

  /** The capacity bound, or Integer.MAX_VALUE if none */
// 容量大小
  private final int capacity;

  /** Current number of elements */
// 元素个数
  private final AtomicInteger count = new AtomicInteger();

  /**
   * Head of linked list.
   * Invariant: head.item == null
   */
// 头节点
  transient Node<E> head;

  /**
   * Tail of linked list.
   * Invariant: last.next == null
   */
// 尾节点
  private transient Node<E> last;

  /** Lock held by take, poll, etc */
// 读锁
  private final ReentrantLock takeLock = new ReentrantLock();

  /** Wait queue for waiting takes */
// 读锁的条件对象
  private final Condition notEmpty = takeLock.newCondition();

  /** Lock held by put, offer, etc */
// 写锁
  private final ReentrantLock putLock = new ReentrantLock();

  /** Wait queue for waiting puts */
// 写锁的条件对象
  private final Condition notFull = putLock.newCondition();

public LinkedBlockingQueue(Collection<? extends E> c) {
    this(Integer.MAX_VALUE);
    final ReentrantLock putLock = this.putLock;
    putLock.lock(); // Never contended, but necessary for visibility
    try {
        int n = 0;
        for (E e : c) {
            if (e == null)
                throw new NullPointerException();
            if (n == capacity)
                throw new IllegalStateException("Queue full");
            enqueue(new Node<E>(e));
            ++n;
        }
        count.set(n);
    } finally {
        putLock.unlock();
    }
}

public LinkedBlockingQueue(int capacity) {
    if (capacity <= 0) throw new IllegalArgumentException();
    this.capacity = capacity;
    // last和head节点都是null
    last = head = new Node<E>(null);
}

private void enqueue(Node<E> node) {
    // assert putLock.isHeldByCurrentThread();
    // assert last.next == null;
    last = last.next = node;
}
static class Node<E> {
    E item;

    /**
     * One of:
     * - the real successor Node
     * - this Node, meaning the successor is head.next
     * - null, meaning there is no successor (this is the last node)
     */
    Node<E> next;

    Node(E x) { item = x; }
}

private void enqueue(Node<E> paramNode){
     this.last = (this.last.next = paramNode);
   }

public boolean add(E e) {
      if (offer(e))
          return true;
      else
          throw new IllegalStateException("Queue full");
  }

public boolean offer(E e) {
    // 不允许空元素
    if (e == null) throw new NullPointerException();
    final AtomicInteger count = this.count;
    // 如果满了就返回false，but这个大小可是2^31-1=2147483647
    if (count.get() == capacity)
        return false;
    int c = -1;
    Node<E> node = new Node<E>(e);
    // 拿到写锁
    final ReentrantLock putLock = this.putLock;
    // 对写操作加锁
    putLock.lock();
    try {
        if (count.get() < capacity) {
            enqueue(node);
            // 元素个数+1
            c = count.getAndIncrement();
            if (c + 1 < capacity)
                // 如果容量还没满，在对象notFull唤醒正在等待的线程，表示可以再往队列里加数据了
                notFull.signal();
        }
    } finally {
        putLock.unlock();
    }
    if (c == 0)
        signalNotEmpty();
  // todo
    return c >= 0;
}

public void put(E e) throws InterruptedException {
    if (e == null) throw new NullPointerException();
    // Note: convention in all put/take/etc is to preset local var
    // holding count negative to indicate failure unless set.
    int c = -1;
    Node<E> node = new Node<E>(e);
    // 拿到写锁
    final ReentrantLock putLock = this.putLock;
    final AtomicInteger count = this.count;
    // 对写操作加锁
    putLock.lockInterruptibly();
    try {
        /*
         * Note that count is used in wait guard even though it is
         * not protected by lock. This works because count can
         * only decrease at this point (all other puts are shut
         * out by lock), and we (or some other waiting put) are
         * signalled if it ever changes from capacity. Similarly
         * for all other uses of count in other wait guards.
         */
        // 如果当前容量已经满了，则阻塞并挂起当前线程
        while (count.get() == capacity) {
            notFull.await();
        }
        // 入队操作
        enqueue(node);
        // 元素+1
        c = count.getAndIncrement();
        if (c + 1 < capacity)
            // 如果容量还没满，在放锁的条件对象notFull唤醒正在等待的线程
            notFull.signal();
    } finally {
        putLock.unlock();
    }
    if (c == 0)
        signalNotEmpty();
}

public E poll() {
    final AtomicInteger count = this.count;
    if (count.get() == 0)
        return null;
    E x = null;
    int c = -1;
    final ReentrantLock takeLock = this.takeLock;
    takeLock.lock();
    try {
        if (count.get() > 0) {
            x = dequeue();
            c = count.getAndDecrement();
            if (c > 1)
                notEmpty.signal();
        }
    } finally {
        takeLock.unlock();
    }
    if (c == capacity)
        signalNotFull();
    // 成功就会返回实际的元素，否则返回null
    return x;
}

private E dequeue() {
    // assert takeLock.isHeldByCurrentThread();
    // assert head.item == null;
    Node<E> h = head;
    Node<E> first = h.next;
    h.next = h; // help GC
    head = first;
    E x = first.item;
    first.item = null;
    return x;
}

public E take() throws InterruptedException {
    E x;
    int c = -1;
    final AtomicInteger count = this.count;
    final ReentrantLock takeLock = this.takeLock;
    takeLock.lockInterruptibly();
    try {
        while (count.get() == 0) {
            // 阻塞等待
            notEmpty.await();
        }
        x = dequeue();
        c = count.getAndDecrement();
        if (c > 1)
            notEmpty.signal();
    } finally {
        takeLock.unlock();
    }
    if (c == capacity)
        signalNotFull();
    return x;
}

public boolean remove(Object o) {
    if (o == null) return false;
    // remove操作的位置不固定，所以需要对两个锁都进行加锁
    fullyLock();
    try {
        for (Node<E> trail = head, p = trail.next;
             p != null;
             trail = p, p = p.next) {
            // 判断是否找到对象
            if (o.equals(p.item)) {
                // 修改节点的链接信息，同时调用notFull的signal方法
                unlink(p, trail);
                return true;
            }
        }
        return false;
    } finally {
        fullyUnlock();
    }
}

void fullyLock() {
    putLock.lock();
    takeLock.lock();
}
void unlink(Node<E> p, Node<E> trail) {
  // assert isFullyLocked();
  // p.next is not changed, to allow iterators that are
  // traversing p to maintain their weak-consistency guarantee.
  p.item = null;
  trail.next = p.next;
  if (last == p)
    last = trail;
  // 判断当前元素总数是否等于最大值
  if (count.getAndDecrement() == capacity)
    notFull.signal();
}
void fullyUnlock() {
  takeLock.unlock();
  putLock.unlock();
}

public static class AbortPolicy implements RejectedExecutionHandler {
    /**
     * Creates an {@code AbortPolicy}.
     */
    public AbortPolicy() { }

    /**
     * Always throws RejectedExecutionException.
     *
     * @param r the runnable task requested to be executed
     * @param e the executor attempting to execute this task
     * @throws RejectedExecutionException always
     */
    public void rejectedExecution(Runnable r, ThreadPoolExecutor e) {
        throw new RejectedExecutionException("Task " + r.toString() +
                                             " rejected from " +
                                             e.toString());
    }
}