// 初版思路
class NaiveLock {
    volatile int state = 0;          // 0=未锁, 1=已锁
    Queue<Thread> queue = new ...    // 等待队列

    void lock() {
        while (!CAS(&state, 0, 1)) { // 没抢到锁
            queue.enqueue(currentThread());  // 入队
            park();                           // 阻塞
        }
    }

    void unlock() {
        state = 0;                    // 释放锁
        Thread t = queue.dequeue();   // 从队列取一个
        unpark(t);                    // 唤醒
    }
}

// AQS.java:988
public final void acquire(int arg) {
    if (!tryAcquire(arg))                // ① 子类实现：能不能获取？
        acquire(null, arg, false, false, false, 0L); // ② 排队去
}

// AQS.java:1058
public final boolean release(int arg) {
    if (tryRelease(arg)) {               // ① 子类实现：能不能释放？
        signalNext(head);                // ② 唤醒后继
        return true;
    }
    return false;
}

// AQS.java:467-522 (JDK 21)
abstract static class Node {
    volatile Node prev;        // 前驱
    volatile Node next;        // 后继
    Thread waiter;             // 被包装的线程
    volatile int status;       // 节点状态
}

static final class ExclusiveNode extends Node { }   // 独占模式
static final class SharedNode extends Node { }       // 共享模式

static final class ConditionNode extends Node implements ForkJoinPool.ManagedBlocker {
    ConditionNode nextWaiter;  // 条件队列中的下一个节点
}

static final int WAITING   = 1;           // 线程正在等待被 unpark
static final int CANCELLED = 0x80000000;  // 节点已取消（负值）
static final int COND      = 2;           // 在条件队列中

// acquire 方法的入队部分（JDK 21, L738-744）
node.waiter = current;
node.setPrevRelaxed(t);       // ① 先设 prev
if (!casTail(t, node))         // ② CAS 抢 tail
    node.setPrevRelaxed(null); // ③ 失败回退
else
    t.next = node;             // ④ 成功后补 next

// acquire 方法 JDK 21, L716-720
node.prev = null;      // 断前驱
head = node;           // 设自己为 head
pred.next = null;      // 断旧 head 的 next
node.waiter = null;    // 清 thread 引用

private volatile int state;

// JDK 8
public final void acquire(int arg) {
    if (!tryAcquire(arg)) {
        Node node = addWaiter(Node.EXCLUSIVE);  // ① 入队
        boolean interrupted = acquireQueued(node, arg); // ② 自旋
        if (interrupted) selfInterrupt();
    }
}

// JDK 8 acquireQueued
for (;;) {
    final Node p = node.predecessor();
    if (p == head && tryAcquire(arg)) {  // 前驱是 head 才抢
        setHead(node);
        p.next = null;
        return interrupted;
    }
    // 重点在这儿：➀ 设前驱为 SIGNAL → ➁ park
    if (shouldParkAfterFailedAcquire(p, node))
        interrupted |= parkAndCheckInterrupt();
}

// JDK 8 shouldParkAfterFailedAcquire
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL)          // 前驱已经是 SIGNAL → 可以 park
        return true;
    if (ws > 0) {                   // 前驱被取消 → 跳过取消的前驱
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {                        // 前驱是 0 或 PROPAGATE → 设 SIGNAL
        pred.compareAndSetWaitStatus(ws, Node.SIGNAL);
    }
    return false;                   // 返回 false，外层会自旋再试一次
}

// AQS.java:670 (JDK 21)
final int acquire(Node node, int arg, boolean shared,
                  boolean interruptible, boolean timed, long time) {
    Thread current = Thread.currentThread();
    byte spins = 0, postSpins = 0;
    boolean interrupted = false, first = false;
    Node pred = null;

    for (;;) {
        // ① 检查前驱
        if (!first && ...) { if (pred.status < 0) cleanQueue(); ... }
        // ② 抢锁
        if (first || pred == null) { /* tryAcquire */ }
        // ③ 未初始化? 初始化
        else if (tail == null) { tryInitializeHead(); }
        // ④ 没创建节点? 创建
        else if (node == null) { node = new ExclusiveNode(); }
        // ⑤ 没入队? 入队
        else if (pred == null) { /* setPrevRelaxed → casTail */ }
        // ⑥ 入队后先空转几次（减少不公平）
        else if (first && spins != 0) { --spins; Thread.onSpinWait(); }
        // ⑦ 设自己的 WAITING 标志
        else if (node.status == 0) { node.status = WAITING; }
        // ⑧ park
        else { LockSupport.park(this); node.clearStatus(); }
    }
}

// AQS.java:650
private static void signalNextIfShared(Node h) {
    Node s;
    if (h != null && (s = h.next) != null &&
        (s instanceof SharedNode) && s.status != 0) {
        s.getAndUnsetStatus(WAITING);
        LockSupport.unpark(s.waiter);
    }
}

if (shared)
    signalNextIfShared(node);  // 唤醒继任共享节点

// AQS.java:822
private int cancelAcquire(Node node, boolean interrupted,
                          boolean interruptible) {
    if (node != null) {
        node.waiter = null;
        node.status = CANCELLED;    // 设取消标记
        if (node.prev != null)
            cleanQueue();           // 委托清理
    }
    // ...处理中断...
}

// AQS.java:785
private void cleanQueue() {
    for (;;) {
        for (Node q = tail, s = null, p, n;;) {
            if (q == null || (p = q.prev) == null)
                return;
            if (q.status < 0) {        // 取消节点
                // CAS 把前驱的 next 和 后继的 prev 链起来
                if ((s == null ? casTail(q, p) : s.casPrev(q, p)) && ...)
                    p.casNext(q, s);   // 尝试修复 next（失败了也没事）
                break;
            }
            // ...
            s = q;
            q = q.prev;                // 从 tail 向前遍历
        }
    }
}

// AQS.java:1559 (enableWait)
private int enableWait(ConditionNode node) {
    node.waiter = Thread.currentThread();
    node.setStatusRelaxed(COND | WAITING);  // = 3
    // ...入条件队列尾部...
    int savedState = getState();
    if (release(savedState))       // 释放所有重入！
        return savedState;
}

// AQS.java:1506 (doSignal)
private void doSignal(ConditionNode first, boolean all) {
    while (first != null) {
        ConditionNode next = first.nextWaiter;
        if ((firstWaiter = next) == null)
            lastWaiter = null;
        // 📌 原子清除 COND 位。还在 → 入同步队列；已不在 → 节点被取消了
        if ((first.getAndUnsetStatus(COND) & COND) != 0) {
            enqueue(first);   // 入同步队列
            if (!all) break;
        }
        first = next;  // 当前节点已取消，处理下一个
    }
}

// AQS.java:606
final void enqueue(ConditionNode node) {
    for (Node t;;) {
        if ((t = tail) == null && (t = tryInitializeHead()) == null) {
            unpark = true; break;       // OOME，直接 unpark
        }
        node.setPrevRelaxed(t);
        if (casTail(t, node)) {
            t.next = node;
            if (t.status < 0)           // 前驱已取消 → 直接 unpark
                unpark = true;
            break;
        }
    }
    if (unpark) LockSupport.unpark(node.waiter);
}

// JDK 8 AbstractQueuedSynchronizer.Node
static final class Node {
    volatile int waitStatus;
    volatile Node prev;
    volatile Node next;
    volatile Thread thread;
    Node nextWaiter;        // ⚠️ 双重语义！

    static final Node SHARED = new Node();  // 标记共享
    static final Node EXCLUSIVE = null;     // 标记独占
}

// JDK 21 AQS.Node
abstract static class Node {
    volatile Node prev;
    volatile Node next;
    Thread waiter;              // waiter 不再是 volatile（被 volatile 守卫包围）
    volatile int status;
}
// 子类：
static final class ExclusiveNode extends Node { }
static final class SharedNode extends Node { }
static final class ConditionNode extends Node implements ForkJoinPool.ManagedBlocker {
    ConditionNode nextWaiter;
}

// JDK 8
static final int CANCELLED =  1;
static final int SIGNAL    = -1;
static final int CONDITION = -2;
static final int PROPAGATE = -3;

// JDK 21
static final int WAITING   = 1;          // must be 1
static final int CANCELLED = 0x80000000; // must be negative
static final int COND      = 2;          // in a condition wait

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

// JDK 21 acquire 方法中
if (first) {
    // ...setHead...
    if (shared)
        signalNextIfShared(node);  // 每次都检查下一个是不是 SharedNode
}

// JDK 8
public final void acquire(int arg) {
    if (!tryAcquire(arg)) {
        Node node = addWaiter(Node.EXCLUSIVE);  // ① 入队
        boolean interrupted = acquireQueued(node, arg); // ② 自旋
        if (interrupted)
            selfInterrupt();
    }
}

// ① addWaiter —— 创建节点 + 入队
private Node addWaiter(Node mode) {
    Node node = new Node(mode);           // 传入 EXCLUSIVE/SHARED
    for (;;) {
        Node oldTail = tail;
        if (oldTail != null) {
            node.setPrevRelaxed(oldTail);
            if (compareAndSetTail(oldTail, node)) {
                oldTail.next = node;
                return node;
            }
        } else {
            initializeSyncQueue();        // 初始化队列
        }
    }
}

// ② acquireQueued —— 自旋获取
final boolean acquireQueued(final Node node, int arg) {
    boolean interrupted = false;
    try {
        for (;;) {
            final Node p = node.predecessor();
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null;
                return interrupted;
            }
            // ③ shouldParkAfterFailedAcquire
            if (shouldParkAfterFailedAcquire(p, node))
                interrupted |= parkAndCheckInterrupt();
        }
    } catch (Throwable t) {
        cancelAcquire(node);
        throw t;
    }
}

// ③ shouldParkAfterFailedAcquire —— 设前驱 SIGNAL
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL)
        return true;
    if (ws > 0) {
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else {
        pred.compareAndSetWaitStatus(ws, Node.SIGNAL);
    }
    return false;
}

// JDK 21 —— 单方法六阶段
final int acquire(Node node, int arg, boolean shared,
                  boolean interruptible, boolean timed, long time) {
    Thread current = Thread.currentThread();
    byte spins = 0, postSpins = 0;
    boolean interrupted = false, first = false;
    Node pred = null;

    for (;;) {
        // ① 检查前驱状态
        if (!first && (pred = ...) != null && !(first = (head == pred))) {
            if (pred.status < 0) { cleanQueue(); continue; }
            else if (pred.prev == null) { Thread.onSpinWait(); continue; }
        }
        // ② 尝试获取
        if (first || pred == null) {
            if (shared ? tryAcquireShared(arg) >= 0 : tryAcquire(arg)) {
                if (first) { /* setHead + signalNextIfShared */ }
                return 1;
            }
        }
        // ③ 队列未初始化
        else if ((t = tail) == null) { tryInitializeHead(); }
        // ④ 节点未创建
        else if (node == null) { node = new (shared ? SharedNode : ExclusiveNode)(); }
        // ⑤ 入队
        else if (pred == null) { setPrevRelaxed(t); casTail(t, node); t.next = node; }
        // ⑥ 首次自旋
        else if (first && spins != 0) { --spins; Thread.onSpinWait(); }
        // ⑦ 设 WAITING
        else if (node.status == 0) { node.status = WAITING; }
        // ⑧ park
        else { LockSupport.park(this); node.clearStatus(); }
    }
}

// JDK 8
private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0)
        node.compareAndSetWaitStatus(ws, 0);  // ① 清状态

    Node s = node.next;
    if (s == null || s.waitStatus > 0) {       // ② next 不可靠？从 tail 扫！
        s = null;
        for (Node p = tail; p != node && p != null; p = p.prev)
            if (p.waitStatus <= 0)
                s = p;
    }
    if (s != null)
        LockSupport.unpark(s.thread);
}

// JDK 21
private static void signalNext(Node h) {
    Node s;
    if (h != null && (s = h.next) != null && s.status != 0) {
        s.getAndUnsetStatus(WAITING);   // ① 原子清除 WAITING
        LockSupport.unpark(s.waiter);
    }
}

// 底层是 Unsafe.getAndBitwiseAndInt
// 等价于 atomic 的 getAndBitwiseAnd
final int getAndUnsetStatus(int v) {
    return U.getAndBitwiseAndInt(this, STATUS, ~v);
}

// JDK 8 cancelAcquire（部分代码）
private void cancelAcquire(Node node) {
    node.thread = null;
    Node pred = node.prev;
    while (pred.waitStatus > 0)      // 跳过取消前驱
        node.prev = pred = pred.prev;
    Node predNext = pred.next;

    node.waitStatus = Node.CANCELLED;

    if (node == tail && compareAndSetTail(node, pred)) {
        pred.compareAndSetNext(predNext, null);  // 作为 tail 的取消
    } else {
        if (pred != head) {
            // 跳过自己的链表拼接
            pred.compareAndSetNext(predNext, node.next);
        } else {
            unparkSuccessor(node);   // 前驱是 head，唤醒自己的后继
        }
    }
    node.next = node;  // 帮助 GC
}

// JDK 21
private int cancelAcquire(Node node, boolean interrupted, boolean interruptible) {
    if (node != null) {
        node.waiter = null;
        node.status = CANCELLED;        // 只设标记
        if (node.prev != null)
            cleanQueue();               // 委托清理
    }
    if (interrupted) {
        if (interruptible) return CANCELLED;
        else Thread.currentThread().interrupt();
    }
    return 0;
}

// JDK 21 cleanQueue（核心片段）
for (Node q = tail, s = null, p, n;;) {
    if (q == null || (p = q.prev) == null) return;  // 到头了
    if (q.status < 0) {    // 发现取消节点
        if ((s == null ? casTail(q, p) : s.casPrev(q, p)) && q.prev == p)
            p.casNext(q, s);   // 修复 next（失败了也无所谓）
        if (p.prev == null) signalNext(p);
        break;
    }
    // ...
    s = q;
    q = q.prev;    // 从 tail 向前遍历
}

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

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))
                    continue;
                unparkSuccessor(h);
            } else if (ws == 0 &&
                       !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                continue;
        }
        // ... 退出条件
    }
}

// JDK 21 — 在 acquire 获锁后的 setHead 中
if (shared)
    signalNextIfShared(node);  // 唤醒下一个共享节点

private static void signalNextIfShared(Node h) {
    Node s;
    if (h != null && (s = h.next) != null &&
        (s instanceof SharedNode) && s.status != 0) {
        s.getAndUnsetStatus(WAITING);
        LockSupport.unpark(s.waiter);
    }
}

// JDK 8 ConditionObject.await
public final void await() throws InterruptedException {
    if (Thread.interrupted()) throw new InterruptedException();
    Node node = addConditionWaiter();       // ① 入条件队列
    int savedState = fullyRelease(node);    // ② 释放全部 state
    int interruptMode = 0;
    while (!isOnSyncQueue(node)) {
        LockSupport.park(this);            // ③ 阻塞
        if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
            break;
    }
    if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
        interruptMode = REINTERRUPT;
    // ... 清理取消节点
}

// JDK 21 ConditionObject.awaitUninterruptibly（简化版）
public final void awaitUninterruptibly() {
    ConditionNode node = newConditionNode();
    if (node == null) return;
    int savedState = enableWait(node);        // ① 入条件队列 + 释放锁
    while (!canReacquire(node)) {             // ② 等待 signal
        if (Thread.interrupted()) interrupted = true;
        else if ((node.status & COND) != 0) {
            ForkJoinPool.managedBlock(node);  // ③ 阻塞（支持 FJP！）
        } else Thread.onSpinWait();
    }
    acquire(node, savedState, false, false, false, 0L);  // ④ 重新竞争
    // ... 清理
}

// JDK 8
final boolean isOnSyncQueue(Node node) {
    if (node.waitStatus == Node.CONDITION || node.prev == null)
        return false;
    if (node.next != null)  // 如果有 next，一定在同步队列
        return true;
    return findNodeFromTail(node);  // 否则从 tail 扫描
}

// JDK 21
private boolean canReacquire(ConditionNode node) {
    Node p;
    return node != null && (p = node.prev) != null &&
        (p.next == node || isEnqueued(node));
}

// JDK 21 ConditionNode
public final boolean isReleasable() {
    return status <= 1 || Thread.currentThread().isInterrupted();
}
public final boolean block() {
    while (!isReleasable()) LockSupport.park();
    return true;
}

// JDK 21 acquire 方法中
else if (node == null) {
    try {
        node = (shared) ? new SharedNode() : new ExclusiveNode();
    } catch (OutOfMemoryError oome) {
        return acquireOnOOME(shared, arg);  // OOME 不抛异常，回退自旋！
    }
}

// JDK 21
private int acquireOnOOME(boolean shared, int arg) {
    for (long nanos = 1L;;) {
        if (shared ? (tryAcquireShared(arg) >= 0) : tryAcquire(arg))
            return 1;
        U.park(false, nanos);
        if (nanos < 1L << 30) nanos <<= 1;  // 指数退避，最多约 1 秒
    }
}