#include<string>
#include<iostream>
#include<atomic>
#include<thread>
using namespace std;
/*
oldval fetch_add(value)	原子操作：递增,并返回旧值
oldval fetch_sub(value)	原子操作：递减,并返回旧值
curval load()	        原子操作：加载值(获取值)
void   store(value)	    原子操作：存储值(设置值)
oldval exchange(value)	原子操作：直接替换值(不涉及比较),并返回旧值
bool   compare_exchange_weak(T& expected, T desired) 原子操作：比较并交换（弱版本，可能虚假失败，需设计重试逻辑）
	1.若原子变量的‌值与expected相等  ，函数返回true表示比较并交换操作成功 ，并且原子变量的‌值替换为desired
	2.若原子变量的‌值与expected不相等，函数返回false表示比较并交换操作失败，并且将expected设置为原子变量的‌值(关键特性‌)
		expected更新为原子变量的‌值是compare_exchange_weak的核心特性，确保循环重试机制有效
		    适用于性能敏感场景，如自旋锁，无锁队列、栈、哈希表等，需频繁比较和交换操作
		    由于 compare_exchange_weak 可能出现虚假失败，通常会在循环中使用它，以确保操作最终能够成功
			int expected = shared_value.load();
    		while (!shared_value.compare_exchange_weak(expected, desired);) {
       			 // 伪失败时，expected已被更新为原子对象的当前值，继续重试
       			 std::this_thread::yield(); //这里可以添加一些额外的逻辑，比如记录重试次数，或让出CPU
   			 }
	3.可能虚假失败‌：原子的‌值与expected相等的情况下函数也返回false(如硬件指令重排、缓存一致性问题等)
		虚假失败时，原子变量的值不会被设置为新值desired
	4.通常比 compare_exchange_strong 更高效,
	5.适用于高性能循环（如无锁队列）
bool   compare_exchange_strong(T& expected, T desired) 原子操作：比较并交换（强版本，不可能虚假失败）
	1.功能同compare_exchange_weak，但是其无虚假失败‌
	2.适用于正确性优先场景，适用于单次尝试或需严格保证的场景
*/
template <class T>
void check()
{
    cout << typeid(T).name() << endl;
    cout << std::is_trivially_copyable<T>::value << endl;
    cout << std::is_copy_constructible<T>::value << endl;
    cout << std::is_move_constructible<T>::value << endl;
    cout << std::is_copy_assignable<T>::value << endl;
    cout << std::is_move_assignable<T>::value << endl;
    cout << std::is_same<T, typename std::remove_cv<T>::type>::value << endl;
}

int main()
{
    atomic<int> a(100);
    cout << "a=" << a.load()<<endl;
    a.store(111);//修改被封装的值
    cout << "a=" << a.load()<<endl;
    a.fetch_add(100);
    int t = a.exchange(13);//读取并修改被封装的值,返回之前的值
    cout << t << "," <<a.load()<<endl;
    a.fetch_sub(10);
    cout << "a=" << a.load()<<endl;//3
    a.fetch_or(5);//11|101=111=7
    cout << "a=" << a.load()<<endl;//7
    a.fetch_xor(6);//7=111^110=001
    cout << "a=" << a.load()<<endl;//1
    a++;
    cout << "a=" << a.load()<<endl;//2
    a--;
    cout << "a=" << a.load()<<endl;//1
     cout << "a is_lock_free=" << a.is_lock_free()<<endl;//1
    //比较并交换被封装的值(weak)与参数 expected 所指定的值是否相等
    {
        atomic<int> oldval(100);
        int comval = 100;
        int newval = 2000;
        oldval.compare_exchange_weak(comval, newval);//t==exp，则用val替换原子对象的旧值，oldval = newval
        cout << oldval.load() << "," << comval<<endl;
        oldval.store(100);
        int comval2 = 2000;
        oldval.compare_exchange_weak(comval2, newval);//t!=exp，则用原子对象的旧值替换exp，comval = oldval
        cout << oldval.load() << "," << comval2<<endl;
    }
    //比较并交换被封装的值(strong)与参数 expected 所指定的值是否相等
    {
        atomic<int> oldval(100);
        int comval = 100;
        int newval = 2000;
        oldval.compare_exchange_strong(comval, newval);//t==exp，则用val替换原子对象的旧值，oldval = newval
        cout << oldval.load() << "," << comval<<endl;
        oldval.store(100);
        int comval2 = 2000;
        oldval.compare_exchange_strong(comval2, newval);//t!=exp，则用原子对象的旧值替换exp，comval = oldval
        cout << oldval.load() << "," << comval2<<endl;
    }
}


/*
在解释具体内存序前，先明确下面关键术语：
1.指令重排：编译器 / CPU 为优化性能，可能打乱指令执行顺序（仅保证单线程语义不变）；
2.可见性：线程 A 对变量的修改，线程 B 能否看到（核心是 CPU 缓存同步）；
3.同步关系（synchronizes-with）：线程间的 “因果关系”，若 A 的操作同步于 B，则 A 的所有写操作对 B 可见。

内存序	              用于读/写操作  读写顺序控制	        线程可见性控制	   性能
memory_order_relaxed  用于读|写      无约束	            无依赖关系  	       最高
memory_order_acquire  用于读         后续操作不重排	    读操作后可见	       较高
memory_order_release  用于写         前续操作不重排	    写操作前可见	       较高
memory_order_acq_rel  用于"读-改-写"  读写前后操作不重排 	读写操作前后可见     较高
memory_order_seq_cst  用于读|写      全局有序	            全局可见	           最低
memory_order_consume（c++17弃用）  用于读         依赖关系  	        仅依赖操作可见	   较高

1.memory_order 不影响原子操作本身的可见性和互斥性
2.memory_order 约束的是 “操作的顺序性” 和 “临界区数据的可见性”

C++ 原子操作的 memory_order_release（释放）和 memory_order_acquire（获取组合，会建立跨线程的同步关系（synchronizes-with），核心规则是：
释放操作：对原子变量的store(..., release),会"发布"该线程中所有在它之前的非原子/原子写操作，确保这些写操作对后续 "获取" 该原子变量的线程可见。
获取操作：对原子变量的load(..., acquire),若读取到了release(释放)操作写入的值，则会"获取"该释放操作之前的所有写操作，确保这些写操作对当前线程可见


可以简单理解为：
release/acquire 的本质是“语义规则”，缓存同步是“硬件为了实现这个规则做的具体动作”,语义是因，缓存同步是果

release 强制将之前的非原子/原子写操作从本地缓存（L1）同步到 “共享域”（L2/L3 / 主存），让其他核心可见；
acquire 强制从 “共享域” 拉取最新值到本地缓存（L1），保证后续操作能看到最新数据。
memory_order_acq_rel，比如x.fetch_add(1, acq_rel)）：
读阶段（获取 x 的旧值）：强制从 “共享域” 拉取最新值到本地缓存（L1），保证后续操作能看到最新数据。
写阶段（写入 x 的新值）：强制将之前的非原子/原子写操作从本地缓存（L1）同步到 “共享域”（L2/L3 / 主存），让其他核心可见；

核心选择原则:
1.能弱则弱：优先用 relaxed → acquire/release → acq_rel → seq_cst，减少性能开销；
2.配对使用：release 必须与 acquire/acq_rel 配对，才能建立同步关系；
3.指针场景：原子指针的写用 release，读用 acquire（替代弃用的 consume）；
4.读 - 改 - 写：exchange/fetch_add 用 acq_rel（需同时读写同步）；
5.不确定则用 seq_cst：牺牲性能换正确性
*/

//自旋锁实现
class spinLock
{
public:
    void lock(){
        //不用memory_order_acq_rel原因：
        //1.它不需要 “让当前线程前置操作对其他线程可见”（加锁时线程还没进入临界区，前置操作都是非临界区代码，无可见性需求
        //2.它也不需要 “阻止前置操作重排到写之后”（加锁前的操作即使重排，也不影响临界区
        //3.acq_rel会给「写阶段」附加release 语义，这属于过度约束,既满足不了任何额外需求，还可能带来性能损耗。
        while(mutx.exchange(true,memory_order_acquire))//当前线程后续的所有操作，不会被编译器 / CPU 重排到 exchange 之前（避免临界区代码 “提前执行”）；
        {
            while(!mutx.load(memory_order_relaxed))
            {
                this_thread::yield();
            }
        }
    }
    void unlock(){
        //写阶段的release 语义保证：当前线程临界区的所有操作不会重排到 store 之后；
        mutx.store(false,memory_order_release);
    }
private:
    atomic<bool> mutx;
};

/*
//memory_order_acquire +  memory_order_release,保证了它们之间的临界区资源代码不会重排序到它们外面去，即保护临界区资源
spinLock s;

// 线程A：加锁后修改临界区数据
s.lock();////acquire语义保证,当前线程后续的所有操作，不会被重排到之前（避免临界区代码 “提前执行”）；
data = 100;  // 临界区写,
s.unlock(); //release 语义保证：当前线程临界区的所有操作不会重排到 store 之后；

// 线程B：加锁后读取临界区数据
s.lock();
cout << data << endl;  // 必然读到100
s.unlock();
*/
class SpinLock {
private:
    std::atomic<bool> locked{false};

public:
    void lock() {
        while (true) {
            bool expected = false;
            if (locked.compare_exchange_weak(expected, true)) {
                return;
            }
            // 短暂等待，避免过度占用CPU资源
            std::this_thread::yield();
        }
    }

    void unlock() {
        locked.store(false);
    }
};
//单生产者单消费者的无锁队列的实现模式
//必须保证只有一个线程调用try_push，只有一个线程调用try_pop
//生产者仅修改tail和buffer[current_tail]，消费者仅修改head和buffer[current_head]，两者操作的内存区域无重叠，无需处理竞争；
//唯一的同步点是ready原子变量：生产者写ready=true，消费者读ready=true，通过release/acquire保证可见性和顺序。
template<typename T, size_t Size>
class SPSCQueue {
    // 队列元素结构体，alignas(64) 避免伪共享（缓存行竞争）,CPU 缓存行通常是 64 字节
    struct alignas(64) Item {
        std::atomic<bool> ready{false};// 标记元素是否可读取（生产者写入完成）
        T value;// 实际存储的数据
    };

    Item buffer[Size];// 环形缓冲区，大小为模板参数Size
    alignas(64) std::atomic<size_t> head{0};// 头指针（消费者用）：指向下一个要读取的元素位置，alignas(64) 避免伪共享
    alignas(64) std::atomic<size_t> tail{0};// 尾指针（生产者用）：指向下一个要写入的元素位置，alignas(64) 避免伪共享

public:
    bool try_push(const T& value) {
        // 1. 读取当前尾指针（relaxed：无顺序/可见性约束，因为tail仅生产者修改）
        const size_t current_tail = tail.load(std::memory_order_relaxed);
        // 2. 计算下一个尾指针（环形缓冲区，取模实现循环）
        const size_t next_tail = (current_tail + 1) % Size;

        // 3. 检查队列是否已满：next_tail == head 表示缓冲区被占满
        //    load(acquire)：保证读到的head是最新值，且后续写入操作不重排到该读取前
        if (next_tail == head.load(std::memory_order_acquire)) {
            return false; // 队列已满，写入失败
        }

        // 4. 写入数据到当前尾指针位置（无竞争：仅生产者写该位置）
        buffer[current_tail].value = value;
        // 5. 标记该位置数据已就绪（release：保证第4步的value写入不重排到该store之后，
        //    且value的写入对消费者可见）
        buffer[current_tail].ready.store(true, std::memory_order_release);
        // 6. 更新尾指针（release：保证前面的写入操作都完成后，再更新tail，
        //    避免消费者提前看到tail更新但数据未就绪）
        tail.store(next_tail, std::memory_order_release);
        return true; // 写入成功
    }

    bool try_pop(T& value) {
        // 1. 读取当前头指针（relaxed：无约束，因为head仅消费者修改）
        const size_t current_head = head.load(std::memory_order_relaxed);

        // 2. 检查当前位置是否有就绪数据：ready=false 表示队列为空
        //    load(acquire)：保证读到的ready是最新值，且后续读取value的操作不重排到该读取前
        //如果仅用 current_head==current_tail 判空，会出现 **“误判空” 或 “读取未就绪数据”** 的问题
        //比如生产者已经写入 buffer[0]、设 ready=true，但还没更新tail
        if (!buffer[current_head].ready.load(std::memory_order_acquire)) {
            return false; // 队列为空，读取失败
        }

        // 3. 读取数据到输出参数（无竞争：仅消费者读该位置）
        value = buffer[current_head].value;
        // 4. 标记该位置数据已读取（relaxed：仅消费者修改ready，无需可见性/顺序约束）
        buffer[current_head].ready.store(false, std::memory_order_relaxed);
        // 5. 更新头指针（release：保证前面的读取/修改操作完成后，再更新head，
        //    避免生产者提前看到head更新但数据未读取完成）
        head.store((current_head + 1) % Size, std::memory_order_release);
        return true; // 读取成功
    }
};
无锁数据结构（如无锁链表）
struct Node {
  int data;
  std::atomic<Node *> next;
  Node(int value) : data(value), next(nullptr) {}
};

class LockFreeList {
private:
  std::atomic<Node *> head;

public:
  LockFreeList() : head(nullptr) {}

  void push(int value) {
    auto newNode = std::make_unique<Node>(value);
    Node *expected;
    do {
      expected = head.load();
      newNode->next.store(expected);
    } while (!head.compare_exchange_weak(expected, newNode.get()));
    newNode.release();
    std::cout << ">>>>>>>>>push value: " << value << std::endl;
  }

  bool pop(int &value) {
    Node *expected;
    do {
      expected = head.load();
      if (!expected) {
        return false;
      }
    } while (!head.compare_exchange_weak(expected, expected->next.load()));
    value = expected->data;
    delete expected;
    std::cout << "=======pop value: " << value << std::endl;
    return true;
  }
};

void testList(LockFreeList &list, int value) {
  list.push(value);
  int popped;
  list.pop(popped);
}

int main() {
  LockFreeList list;
  const int numThreads = 15;
  std::vector<std::thread> threads;

  for (int i = 0; i < numThreads; ++i) {
    threads.emplace_back(testList, std::ref(list), i);
  }

  for (auto &thread : threads) {
    thread.join();
  }

  return 0;
}