CAS 与原子操作：AtomicInteger 到 LongAdder

// 原子操作：不可被中断
boolean CAS(int* addr, int expected, int newValue) {
    if (*addr == expected) {
        *addr = newValue;
        return true;   // 交换成功
    } else {
        return false;   // 值已被其他线程修改
    }
}

Unsafe unsafe = Unsafe.getUnsafe();
int offset = unsafe.objectFieldOffset(MyClass.class.getDeclaredField("count"));

// 对 obj.count 执行 CAS：如果当前值等于 0，则改为 1
boolean success = unsafe.compareAndSwapInt(obj, offset, 0, 1);

// 典型用法：CAS 自旋循环（spin loop）
int oldVal;
do {
    oldVal = obj.count;  // 读取当前值
} while (!unsafe.compareAndSwapInt(obj, offset, oldVal, oldVal + 1));
// 如果 CAS 失败（别人在我读和写之间改了值），重试

public class AtomicInteger extends Number implements java.io.Serializable {
    private static final Unsafe U = Unsafe.getUnsafe();
    private static final long VALUE
        = U.objectFieldOffset(AtomicInteger.class, "value");
    private volatile int value;  // ★ volatile 保证多线程可见性

    public AtomicInteger(int initialValue) { value = initialValue; }
    public final int get() { return value; }  // volatile 读，无需加锁
}

public final int getAndIncrement() {
    return U.getAndAddInt(this, VALUE, 1);
}

// Unsafe.getAndAddInt 的实现（JDK 8 中在 AtomicInteger 内部展开）：
public final int getAndAddInt(Object o, long offset, int delta) {
    int v;
    do {
        v = getIntVolatile(o, offset);  // ① 读当前值（volatile 语义）
    } while (!compareAndSwapInt(o, offset, v, v + delta));
    // ② CAS: 如果当前值仍为 v，则改为 v+1
    // ③ 失败说明别人改了，回到 ① 重新读
    return v;  // 返回旧值
}

// compareAndSet：直接暴露 CAS 语义
public final boolean compareAndSet(int expectedValue, int newValue) {
    return U.compareAndSetInt(this, VALUE, expectedValue, newValue);
}

// incrementAndGet：等价于 ++i，返回新值
public final int incrementAndGet() {
    return U.getAndAddInt(this, VALUE, 1) + 1;
}

// getAndSet：原子设置新值并返回旧值
public final int getAndSet(int newValue) {
    return U.getAndSetInt(this, VALUE, newValue);
}

// updateAndGet：函数式更新（JDK 8+）
public final int updateAndGet(IntUnaryOperator updateFunction) {
    int prev, next;
    do {
        prev = get();
        next = updateFunction.applyAsInt(prev);
    } while (!compareAndSet(prev, next));
    return next;
}

// 初始状态：共享变量 V = A

Thread-1:  读取 V = A
           // 被挂起，还没执行 CAS...

Thread-2:  读取 V = A
           CAS(A → B)  成功, V = B
           CAS(B → A)  成功, V = A  // 改回去了！

Thread-1:  执行 CAS(A → C)
           // 内存值 = A == expected(A) → CAS 成功！
           // 但实际上 V 经历过 A→B→A 的变化

// 栈：top → A → B → C
Thread-1: pop()
  读取 top = A, A.next = B
  // 准备 CAS(top, A, B) 使 top 指向 B，被挂起

Thread-2: pop() A
  CAS(top, A, B) 成功, top = B  // 弹出 A
  pop() B
  CAS(top, B, C) 成功, top = C  // 弹出 B
  push() A
  CAS(top, C, A) 成功, top = A  // 重新压入 A（A.next 仍指向 B，但 B 已弹出）

Thread-1: 恢复执行
  CAS(top, A, B) → top 当前值 = A → CAS 成功！
  top = B  // 但 B 已被 Thread-2 弹出并可能回收！
  // 栈变成 top → B（已被释放的节点），A.next 仍指向 B
  // 链表结构被破坏，可能访问已回收内存！

// AtomicStampedReference：值 + 整数版本号
AtomicStampedReference<String> ref
    = new AtomicStampedReference<>("A", 1);  // 初始值"A"，版本1

int stamp = ref.getStamp();  // 记录当前版本号
String val = ref.getReference();  // 记录当前值

// Thread-2 执行 A→B→A，版本号递增
ref.compareAndSet("A", "B", stamp, stamp + 1);     // stamp: 1→2
ref.compareAndSet("B", "A", stamp + 1, stamp + 2); // stamp: 2→3

// Thread-1 尝试 CAS，版本不匹配 → 失败！ABA 被检测出来
boolean ok = ref.compareAndSet(val, "C", stamp, stamp + 1);
// stamp(1) != currentStamp(3) → CAS 失败，ABA 问题解决

// AtomicMarkableReference：值 + boolean 标记
// 适用于只关心"有没有被改过"，不关心改了几次的场景
AtomicMarkableReference<Node> ref
    = new AtomicMarkableReference<>(node, false);

boolean[] markHolder = new boolean[1];
Node val = ref.get(markHolder);  // 同时读取值和标记

// compareAndSet(expectedRef, newRef, expectedMark, newMark)
ref.compareAndSet(val, newNode, false, true);

public final class Unsafe {
    // 获取字段在对象中的内存偏移量
    public native long objectFieldOffset(Field f);

    // 三种基本类型的 CAS 操作（native 方法，直接映射到 CPU 指令）
    public final native boolean compareAndSwapInt(
        Object o, long offset, int expected, int update);
    public final native boolean compareAndSwapLong(
        Object o, long offset, long expected, long update);
    public final native boolean compareAndSwapObject(
        Object o, long offset, Object expected, Object update);

    // volatile 语义的读写
    public native int getIntVolatile(Object o, long offset);
    public native void putIntVolatile(Object o, long offset, int val);

    // 线程调度
    public native void park(boolean isAbsolute, long time);
    public native void unpark(Object thread);
}

// java.lang.invoke.VarHandle（JDK 9 引入）
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;

class Counter {
    private int count;

    // 创建 VarHandle
    private static final VarHandle COUNT;
    static {
        try {
            COUNT = MethodHandles.lookup()
                .findVarHandle(Counter.class, "count", int.class);
        } catch (Exception e) { throw new Error(e); }
    }

    public void increment() {
        // 等价于 Unsafe.compareAndSwapInt 的自旋
        int v;
        do {
            v = (int) COUNT.getVolatile(this);
        } while (!COUNT.compareAndSet(this, v, v + 1));
    }
}

public class LongAdder extends Striped64 {
    // 继承自 Striped64 的核心字段：
    transient volatile Cell[] cells;   // 分段数组（惰性初始化）
    transient volatile long base;      // 无竞争时直接 CAS 更新 base
    transient volatile int cellsBusy;  // 自旋锁，保护 cells 扩容/初始化

    // Cell 内部类（伪共享优化：通过 @Contended 填充缓存行）
    static final class Cell {
        volatile long value;
        Cell(long x) { value = x; }
        final boolean cas(long cmp, long val) {
            return U.compareAndSetLong(this, VALUE, cmp, val);
        }
    }
}

public void add(long x) {
    Cell[] cs; long b, v; int m; Cell c;
    // ① cells 已初始化 → 尝试更新当前线程对应的 Cell
    if ((cs = cells) != null || !casBase(b = base, b + x)) {
        boolean uncontended = true;
        int h = getProbe();  // 线程的 hash 探测值
        if (cs == null || (m = cs.length - 1) < 0 ||
            (c = cs[h & m]) == null ||
            !(uncontended = c.cas(v = c.value, v + x)))
            // ② Cell 为空或 CAS 竞争失败 → 进入长路径
            longAccumulate(x, null, uncontended);
    }
    // ③ base CAS 成功：无竞争时的快速路径，直接返回
}

// longAccumulate：竞争时的慢路径
final void longAccumulate(long x, ...) {
    for (;;) {
        if (cells 未初始化)  初始化 cells;
        else if (对应 Cell 为空) 创建新 Cell;
        else if (Cell CAS 失败) 尝试 cells 扩容（翻倍，减少冲突）;
        else 对 base 做 CAS 重试;
    }
}