public class ReentrantLock implements Lock, java.io.Serializable {
    private final Sync sync;
    
    public void unlock() {
        sync.release(1);
    }
    
    abstract static class Sync extends AbstractQueuedSynchronizer { 
        protected final boolean tryRelease(int releases) {}  // 见下文
    }
}

/** AbstractQueuedSynchronizer.java **/
    public final boolean release(int arg) {
        if (tryRelease(arg)) {  // 尝试释放资源
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);  // 唤醒头节点的后续节点
            return true;
        }
        return false;
    }
    
    protected boolean tryRelease(int arg) {
        throw new UnsupportedOperationException();
    }

/** ReentrantLock#Sync.java **/
abstract static class Sync extends AbstractQueuedSynchronizer { 
    protected final boolean tryRelease(int releases) {
        int c = getState() - releases;
        // 当前线程不是独占的，抛异常
        if (Thread.currentThread() != getExclusiveOwnerThread())
            throw new IllegalMonitorStateException();
        boolean free = false;
        if (c == 0) {  // 之前acquire(1)，现在releases(1)
            free = true;
            setExclusiveOwnerThread(null);
        }
        setState(c);
        return free;         
    }
}

/** AbstractQueuedSynchronizer.java **/
    private void unparkSuccessor(Node node) {
        int ws = node.waitStatus;
        if (ws < 0)
            compareAndSetWaitStatus(node, ws, 0);  // 节点置为无状态

        // 找到后续节点，如果是null或者是CANCELLED状态的话，从尾节点向前找
        Node s = node.next;
        if (s == null || s.waitStatus > 0) {
            s = null;
            for (Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0)
                    s = t;
        }
        if (s != null)
            LockSupport.unpark(s.thread);
    }

public class ReentrantLock implements Lock, java.io.Serializable {
    private final Sync sync;
  
    public ReentrantLock() {
      sync = new NonfairSync(); 
    }
  
    public ReentrantLock(boolean fair) { 
      sync = fair ? new FairSync() : new NonfairSync(); 
    }
  
    public void lock() { 
      sync.lock(); 
    }

    abstract static class Sync extends AbstractQueuedSynchronizer { 
      abstract void lock(); 
    }
    
    static final class FairSync extends Sync {
        final void lock() {
            acquire(1);
        }
      
        protected final boolean tryAcquire(int acquires) {}  // 见下文
    }
    
    static final class NonfairSync extends Sync {
        final void lock() {
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }
      
        protected final boolean tryAcquire(int acquires) {}  // 见下文
    }       
}

/** AbstractQueuedSynchronizer.java **/
    public final void acquire(int arg) {
        // tryAcquire失败，将独占模式节点入队，再从队列中获取
        if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg))  
            selfInterrupt();
    }

    protected boolean tryAcquire(int arg) {
        throw new UnsupportedOperationException();
    }

/** ReentrantLock#FairSync.java 公平锁tryAcquire实现 **/
static final class FairSync extends Sync {
    protected final boolean tryAcquire(int acquires) {
        final Thread current = Thread.currentThread();
        int c = getState();  // volatile int state
        if (c == 0) {
            // 公平锁：需要先看看是不是有线程比当前线程等的更久，没有的话再acquire资源
            if (!hasQueuedPredecessors() && compareAndSetState(0, acquires)) {
                setExclusiveOwnerThread(current);  // 设置当前线程独占
                return true;
            }
        }
        // 如果当前线程独占，无需等待再次进入
        else if (current == getExclusiveOwnerThread()) {
            int nextc = c + acquires;
            if (nextc < 0)
                throw new Error("Maximum lock count exceeded");
            setState(nextc);
            return true;
        }
        return false;
    }
}

/** ReentrantLock#NonfairSync.java 非公平锁tryAcquire实现 **/
static final class NonfairSync extends Sync {
    protected final boolean tryAcquire(int acquires) {
        return nonfairTryAcquire(acquires);  // 父类Sync中的nonfairTryAcquire方法
    }
}

abstract static class Sync extends AbstractQueuedSynchronizer {
    final boolean nonfairTryAcquire(int acquires) {
        final Thread current = Thread.currentThread();
        int c = getState();
        if (c == 0) {
            // 非公平锁：不用hasQueuedPredecessors，直接acquire资源
            if (compareAndSetState(0, acquires)) {
                setExclusiveOwnerThread(current);  // 设置当前线程独占
                return true;
            }
        }
        // 如果当前线程独占，无需等待再次进入
        else if (current == getExclusiveOwnerThread()) {
            int nextc = c + acquires;
            if (nextc < 0) // overflow
                throw new Error("Maximum lock count exceeded");
            setState(nextc);
            return true;
        }
        return false;
    }
}

/** AbstractQueuedSynchronizer.java **/    
    private Node addWaiter(Node mode) {
        Node node = new Node(Thread.currentThread(), mode);  // 节点与当前线程关联，并设置模式
        // 尝试快速方式入队
        Node pred = tail;
        if (pred != null) {
            node.prev = pred;
            // 如果多个线程尝试入队，操作必须是原子的，将尾节点设置为node
            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()))
                    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();
            // 当前节点满足条件：是第二个节点，并且acquire成功
            if (p == head && tryAcquire(arg)) {
                // 设置为头节点，这里不用CAS，因为已经acquire到资源
                setHead(node);  
                p.next = null; // help GC，回收旧的头节点
                failed = false;
                return interrupted;
            }
            // 当前节点不满足条件，调整节点，如果可以的话，休眠线程
            if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt())
                interrupted = true;  // 只要有一次中断，就将中断标志设置为true
        }
    } finally {  // return前，先检查failed，如果出现异常则取消该节点的acquire
        if (failed)
            cancelAcquire(node);
    }
}

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL)  // 先前节点状态已经是SIGNAL，当前节点位置安全，可以休眠
        return true;
    if (ws > 0) {  
        // 先前节点状态是CANCELLED，将当前节点调整到最近的一个非CANCELLED节点后
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        // 先前节点状态不是CANCELLED，CAS为SIGNAL
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    // 此时只是将先前节点状态修改，但考虑到并发情况，也有其他线程在做同样的事情，需要再次自旋检查
    return false;
}

private final boolean parkAndCheckInterrupt() {
    LockSupport.park(this);  // 阻塞线程，被unpark或被interrupt可以唤醒
    return Thread.interrupted();  // 返回线程是否被中断过
}

private void cancelAcquire(Node node) {
    if (node == null)
        return;
    node.thread = null;
    // 跳过CANCELLED状态的先前节点，调整该节点pred域
    Node pred = node.prev;
    while (pred.waitStatus > 0)
        node.prev = pred = pred.prev;
    Node predNext = pred.next;  // 先前节点的后续节点

    node.waitStatus = Node.CANCELLED;
  
    // 如果该节点是队尾，将先前节点设置为队尾，然后将其next域置空
    if (node == tail && compareAndSetTail(node, pred)) {
        compareAndSetNext(pred, predNext, null);
    } else {  
        // 不是队尾
        // 先前节点同时如下满足条件：不是头节点、状态是SIGNAL或者可以变为SIGNAL、绑定了线程
        // 将其pred节点的next域置为该节点的后续节点
        int ws;
        if (pred != head &&
            ((ws = pred.waitStatus) == Node.SIGNAL ||
             (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
            pred.thread != null) {
            Node next = node.next;
            if (next != null && next.waitStatus <= 0)
                compareAndSetNext(pred, predNext, next);
        } else {
            unparkSuccessor(node);  // 唤醒后续节点
        }

        node.next = node; // help GC，使CANCELLED状态的节点不可达，被GC回收
    }
}

/** AbstractQueuedSynchronizer#Node.java **/
static final class Node {
    // 处于共享模式
    static final Node SHARED = new Node();

    // 处于独占模式
    static final Node EXCLUSIVE = null;

    // 表示线程取消。（因为中断或者超时，不会再参与到竞争中，状态也不再改变）
    static final int CANCELLED =  1;
  
    // 表示后续线程等待释放。（因为后续节点被阻塞，处于等待状态，需要当前节点释放或者取消，之后会通知后续节点）
    static final int SIGNAL    = -1;
  
    // 表示线程正在等待条件。（线程正处于Condition队列中等待条件，直到状态转变为0，才会被用于同步队列中）
    static final int CONDITION = -2;
  
    // 表示下一次共享式acquire将无条件传播。(共享式release会传播到其他节点，在doReleaseShared方法中)
    static final int PROPAGATE = -3;
    
    // 等待状态，初始化为0，非负数表示节点无需被通知
    volatile int waitStatus;

    // 注意：该节点的先前节点如果是CANCELLED的，就往前找第一个非CANCELLED的，肯定能找到一个，因为至少头节点就不是CANCELLED。
    volatile Node prev;

    // 注意：只有该节点成为尾节点时才会给先前节点的next域赋值。也就是说，next为null不代表这是尾节点。
    volatile Node next;

    // 节点绑定线程
    volatile Thread thread;

    // 等待conditon的下一个节点（独占模式），或者SHARED(共享模式)
    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;
    }

    Node() {}

    Node(Thread thread, Node mode) {
        // addWaiter方法使用
        this.nextWaiter = mode;
        this.thread = thread;
    }

    Node(Thread thread, int waitStatus) { 
        this.waitStatus = waitStatus;
        this.thread = thread;
    }
}

// 头节点，通过setHead方法修改，等待状态不能是CANCELLED
private transient volatile Node head;

// 尾节点，入队时增加
private transient volatile Node tail;

// 同步状态
private volatile int state;

static final long spinForTimeoutThreshold = 1000L;

protected final int getState() {
    return state;
}

protected final void setState(int newState) {
    state = newState;
}

private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long stateOffset;
private static final long waitStatusOffset;
// ...省略 headOffset、tailOffset、nextOffset

static {
    try {
        stateOffset = unsafe.objectFieldOffset
            (AbstractQueuedSynchronizer.class.getDeclaredField("state"));
        waitStatusOffset = unsafe.objectFieldOffset
            (Node.class.getDeclaredField("waitStatus"));
        // ...省略 headOffset、tailOffset、nextOffset
      
    } catch (Exception ex) { throw new Error(ex); }
}

// CAS同步状态
protected final boolean compareAndSetState(int expect, int update) {
    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}
 
// 入队时如果队空CAS头节点
private final boolean compareAndSetHead(Node update) {
    return unsafe.compareAndSwapObject(this, headOffset, null, update);
}

// 入队时CAS尾节点
private final boolean compareAndSetTail(Node expect, Node update) {
    return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
}

// CAS节点等待状态
private static final boolean compareAndSetWaitStatus(Node node,
                                                     int expect,
                                                     int update) {
    return unsafe.compareAndSwapInt(node, waitStatusOffset,
                                    expect, update);
}

// CAS节点next域
private static final boolean compareAndSetNext(Node node,
                                               Node expect,
                                               Node update) {
    return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
}

Field f = Unsafe.class.getDeclaredField("theUnsafe"); //Internal reference
f.setAccessible(true);
Unsafe unsafe = (Unsafe) f.get(null);

// 当前日期，输出：Fri May 10 14:15:23 CST 2019
System.out.println(new Date()); 

// 格式化日期，输出：2019-05-10 14:18:03
System.out.println(new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date()));  

// 字符串日期解析，输出：Sun May 05 12:30:05 CST 2019
String dateStr = "2019-05-05 12:30:05";
System.out.println(new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").parse(dateStr));