class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer {
    //基于CLH队列变形实现的线程阻塞队列
    static final class Node {

        //线程已被取消。
        static final int CANCELLED =  1;
        //successor线程需要被唤醒。
        static final int SIGNAL    = -1;
        //线程正处在CONDITION队列中，condition队列是和阻塞队列不同的队列，只是使用了相同的node方便管理。
        static final int CONDITION = -2;
        /**
         * waitStatus value to indicate the next acquireShared should
         * unconditionally propagate
         */
        static final int PROPAGATE = -3;
        //CANCELLED/SIGNAL/CONDITION/PROPAGATE/0.
        volatile int waitStatus;
        
        // sync queue 中的前序节点、后续节点及Node上的thread。
        volatile Node prev;
        volatile Node next;
        volatile Thread thread;
        
        
        //仅仅起到标记作用。在sync queue中给nextWaiter赋值。
        static final Node SHARED = new Node();
        static final Node EXCLUSIVE = null;
        
        // 在sync queue中，标记该node是SHARED还是EXCLUSIVE。
        // 在condition条件队列中，指向下一个节点。
        Node nextWaiter;

        final boolean isShared() {
            return nextWaiter == SHARED;
        }
        
        final Node predecessor() throws NullPointerException {
            Node p = prev;
            if (p == null)
                throw new NullPointerException();
            else
                return p;
        }
        
        // Used to establish initial head or SHARED marker
        Node() {    
        }
        // Used by addWaiter
        Node(Thread thread, Node mode) {
            this.nextWaiter = mode;
            this.thread = thread;
        }
        // Used by Condition
        Node(Thread thread, int waitStatus) {
            this.waitStatus = waitStatus;
            this.thread = thread;
        }
    }
    private transient volatile Node head;
    private transient volatile Node tail;
    
    
    //AQS提供了一下三个函数操作state
    private volatile int state;
    protected final int getState() {
        return state;
    }
    protected final void setState(int newState) {
        state = newState;
    }
    protected final boolean compareAndSetState(int expect, int update) {
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }
    
    
    private Node enq(final Node node)
    private void setHead(Node node)
    private void unparkSuccessor(Node node)
    private void doReleaseShared()
    final boolean acquireQueued(final Node node, int arg) 
    private void doAcquireInterruptibly(int arg)
    private boolean doAcquireNanos(int arg, long nanosTimeout)
    private void doAcquireShared(int arg) 
    private void doAcquireSharedInterruptibly(int arg)
    private boolean doAcquireSharedNanos(int arg, long nanosTimeout)
    
    // 需要子类去实现的方法
    protected boolean tryAcquire(int arg)
    protected boolean tryRelease(int arg) 
    protected int tryAcquireShared(int arg) 
    protected boolean tryReleaseShared(int arg)
    protected boolean isHeldExclusively()
    
    // 对外提供的public方法
    public final void acquire(int arg)
    public final void acquireInterruptibly(int arg)
    public final boolean tryAcquireNanos(int arg, long nanosTimeout)
    public final boolean release(int arg)
    public final void acquireShared(int arg)
    public final void acquireSharedInterruptibly(int arg)
    public final boolean tryAcquireSharedNanos(int arg, long nanosTimeout)
    public final boolean releaseShared(int arg) 
    ...
}

public final void acquire(int arg) {
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();//acquireQueued返回的是从park中醒来后的中断状态，如果是true，则同样调用interrupt传递中断状态。
}

private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode);
    // Try the fast path of enq; backup to full enq on failure
    Node pred = tail;
    if (pred != null) {
        node.prev = pred;
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    enq(node);
    return node;
}
private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        if (t == null) { // Must initialize
            if (compareAndSetHead(new Node())) // 如果队列为空，创建一个空Node作为头结点。
                tail = head;
        } else {
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null; // 移除前head
                failed = false;
                return interrupted;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

private final boolean parkAndCheckInterrupt() {
    LockSupport.park(this);//在此阻塞，等待unpark。
    return Thread.interrupted();//当从park中醒来时，返回中断状态。
}

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

public final void acquireShared(int arg) {
    if (tryAcquireShared(arg) < 0)
        doAcquireShared(arg);
}

private void doAcquireShared(int arg) {
    final Node node = addWaiter(Node.SHARED);
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head) {
                int r = tryAcquireShared(arg);
                if (r >= 0) {
                    setHeadAndPropagate(node, r);
                    p.next = null; // help GC
                    if (interrupted)
                        selfInterrupt();
                    failed = false;
                    return;
                }
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

private void setHeadAndPropagate(Node node, int propagate) {
    Node h = head; // Record old head for check below
    setHead(node);
    if (propagate > 0 || h == null || h.waitStatus < 0 ||
        (h = head) == null || h.waitStatus < 0) {
        Node s = node.next;
        if (s == null || s.isShared())
            doReleaseShared();
    }
}

public final boolean releaseShared(int arg) {
    if (tryReleaseShared(arg)) {
        doReleaseShared();
        return true;
    }
    return false;
}

private void doReleaseShared() {

    for (;;) {
        Node h = head;
        if (h != null && h != tail) {
            int ws = h.waitStatus;
            if (ws == Node.SIGNAL) {
                if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0)) // 保证多线程释放时，同一个head的后继线程unparkSuccessor只被执行一次。
                    continue;            
                unparkSuccessor(h); // 唤醒head的下一个节点线程。
            }
            else if (ws == 0 &&
                     !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                continue;                
        }
        if (h == head) // 只有当头结点==未改变==时，退出循环 (如果头结点改变，继续释放下一个node)
            break;
    }
    
}

public abstract class AbstractOwnableSynchronizer
    implements java.io.Serializable {

    private static final long serialVersionUID = 3737899427754241961L;

    protected AbstractOwnableSynchronizer() { }

    private transient Thread exclusiveOwnerThread;

    protected final void setExclusiveOwnerThread(Thread thread) {
        exclusiveOwnerThread = thread;
    }

    protected final Thread getExclusiveOwnerThread() {
        return exclusiveOwnerThread;
    }
}

public interface Condition {
    void await() throws InterruptedException;
    void awaitUninterruptibly();
    long awaitNanos(long nanosTimeout) throws InterruptedException;
    boolean await(long time, TimeUnit unit) throws InterruptedException;
    boolean awaitUntil(Date deadline) throws InterruptedException;
    void signal();
    void signalAll();
}

public class FoodQueue<T> {

    //队列大小
    private  int size;

    //list 充当队列
    private List<T> food;

    //锁
    private Lock lock=new ReentrantLock();

    //保证队列大小不<0 的condition
    private Condition notEmpty=lock.newCondition();

    //保证队列大小不>size的condition
    private Condition notFull=lock.newCondition();

    public  FoodQueue(int size){
        this.size=size;
        food=new ArrayList<T>();
    }
    
    public void product(T t) throws Exception {
        lock.lock();
        try{

            //如果队列满了，就不能生产了，等待消费者消费数据
            while (size==food.size()){
                notFull.await();
            }

            //队列已经有空位置了，放入数据
            food.add(t);

            //队列已经有数据了，也就是不为空了，可以通知消费者消费了
            notEmpty.signal();
        }finally {
            lock.unlock();
        }

    }

    public T consume() throws  Exception{
        lock.lock();
        try{

            //队列为空，需要等待生产者生产数据
            while (food.size()==0){
                notEmpty.await();
            }
            //生产者生产了数据，可以拿掉一个数据
            T t=food.remove(0);

            //通知消费者可以继续生产了
            notFull.signal();
            return t;
        }finally {
            lock.unlock();
        }

    }
}