typedef enum memory_order {
    memory_order_relaxed,
    memory_order_consume,
    memory_order_acquire,
    memory_order_release,
    memory_order_acq_rel,
    memory_order_seq_cst
} memory_order;

#include <iostream>
#include <thread>
#include <atomic>
std::atomic<size_t> x{0};
std::atomic<size_t> y{0};
size_t r1, r2;
int main()
{
    // 线程 1 ：
    std::thread t1(
        [](){
            r1 = y.load(std::memory_order_relaxed); // A
            x.store(r1, std::memory_order_relaxed); // B
        }
    );

    // 线程 2 ：
    std::thread t2(
        [](){
            r2 = x.load(std::memory_order_relaxed); // C 
            y.store(42, std::memory_order_relaxed); // D
        }
    );
    t1.join();
    t2.join();
    std::cout << "x - y: " << x << ", " << y << std::endl;
    std::cout << "r1 - r2: " << r1 << ", " << r2 << std::endl;
    return 0;
}

#include <vector>
#include <iostream>
#include <thread>
#include <atomic>
 
std::atomic<int> cnt = {0};
 
void f()
{
    for (int n = 0; n < 1000; ++n) {
        cnt.fetch_add(1, std::memory_order_relaxed);
    }
}
 
int main()
{
    std::vector<std::thread> v;
    for (int n = 0; n < 10; ++n) {
        v.emplace_back(f);
    }
    for (auto& t : v) {
        t.join();
    }
    std::cout << "Final counter value is " << cnt << '\n';
}

#include <thread>
#include <atomic>
#include <cassert>
#include <string>
 
std::atomic<std::string*> ptr;
int data;
 
void producer()
{
    std::string* p  = new std::string("Hello");
    data = 42;
    ptr.store(p, std::memory_order_release);
}
 
void consumer()
{
    std::string* p2;
    while (!(p2 = ptr.load(std::memory_order_acquire)))
        ;
    assert(*p2 == "Hello"); // 绝无问题
    assert(data == 42); // 绝无问题
}
 
int main()
{
    std::thread t1(producer);
    std::thread t2(consumer);
    t1.join(); t2.join();
}

#include <thread>
#include <atomic>
#include <cassert>
#include <vector>
 
std::vector<int> data;
std::atomic<int> flag = {0};
 
void thread_1()
{
    data.push_back(42);
    flag.store(1, std::memory_order_release);
}
 
void thread_2()
{
    int expected=1;
    while (!flag.compare_exchange_strong(expected, 2, std::memory_order_acq_rel)) {
        expected = 1;
    }
}
 
void thread_3()
{
    while (flag.load(std::memory_order_acquire) < 2)
        ;
    assert(data.at(0) == 42); // 决不出错
}
 
int main()
{
    std::thread a(thread_1);
    std::thread b(thread_2);
    std::thread c(thread_3);
    a.join(); b.join(); c.join();
}

#include <thread>
#include <atomic>
#include <cassert>
#include <string>
 
std::atomic<std::string*> ptr;
int data;
 
void producer()
{
    std::string* p  = new std::string("Hello");
    data = 42;
    ptr.store(p, std::memory_order_release);
}
 
void consumer()
{
    std::string* p2;
    while (!(p2 = ptr.load(std::memory_order_consume)))
        ;
    assert(*p2 == "Hello"); // 绝无出错： *p2 从 ptr 携带依赖
    assert(data == 42); // 可能也可能不会出错： data 不从 ptr 携带依赖
}
 
int main()
{
    std::thread t1(producer);
    std::thread t2(consumer);
    t1.join(); t2.join();
}

#include <thread>
#include <atomic>
#include <cassert>
#include <iostream>
 
std::atomic<bool> x = {false};
std::atomic<bool> y = {false};
std::atomic<int> z = {0};
 
void write_x()
{
    x.store(true, std::memory_order_seq_cst);
}
 
void write_y()
{
    y.store(true, std::memory_order_seq_cst);
}
 
void read_x_then_y()
{
    while (!x.load(std::memory_order_seq_cst))
        ;
    if (y.load(std::memory_order_seq_cst)) {
        ++z;
    }
}
 
void read_y_then_x()
{
    while (!y.load(std::memory_order_seq_cst))
        ;
    if (x.load(std::memory_order_seq_cst)) {
        ++z;
    }
}
 
int main()
{
    std::thread a(write_x);
    std::thread b(write_y);
    std::thread c(read_x_then_y);
    std::thread d(read_y_then_x);
    a.join(); b.join(); c.join(); d.join();
    std::cout << z << std::endl;
    assert(z.load() != 0);  // 决不发生
}

/* Naive lock-free stack which suffers from ABA problem.*/
class Stack {
  std::atomic<Obj*> top_ptr;
  //
  // Pops the top object and returns a pointer to it.
  //
  Obj* Pop() {
    while (1) {
      Obj* ret_ptr = top_ptr;
      if (!ret_ptr) return nullptr;
      // For simplicity, suppose that we can ensure that this dereference is safe
      // (i.e., that no other thread has popped the stack in the meantime).
      Obj* next_ptr = ret_ptr->next;
      // If the top node is still ret, then assume no one has changed the stack.
      // (That statement is not always true because of the ABA problem)
      // Atomically replace top with next.
      if (top_ptr.compare_exchange_weak(ret_ptr, next_ptr)) {
        return ret_ptr;
      }
      // The stack has changed, start over.
    }
  }
  //
  // Pushes the object specified by obj_ptr to stack.
  //
  void Push(Obj* obj_ptr) {
    while (1) {
      Obj* next_ptr = top_ptr;
      obj_ptr->next = next_ptr;
      // If the top node is still next, then assume no one has changed the stack.
      // (That statement is not always true because of the ABA problem)
      // Atomically replace top with obj.
      if (top_ptr.compare_exchange_weak(next_ptr, obj_ptr)) {
        return;
      }
      // The stack has changed, start over.
    }
  }
};

{ // Thread 2 runs pop:
  ret = A;
  next = B;
  compare_exchange_weak(A, B)  // Success, top = B
  return A;
} // Now the stack is top → B → C
{ // Thread 2 runs pop again:
  ret = B;
  next = C;
  compare_exchange_weak(B, C)  // Success, top = C
  return B;
} // Now the stack is top → C
delete B;
{ // Thread 2 now pushes A back onto the stack:
  A->next = C;
  compare_exchange_weak(C, A)  // Success, top = A
}

#include <thread>
#include <atomic>
#include <cassert>
#include <string>
#include <iostream>

template<typename T>
struct Node
{
    Node(){}
    Node(const T &value) : data(value), next(nullptr) { }
    T data;
    Node *next = nullptr;
};

/*头插和头pop的方法
*/
template<typename T>
class LockFreeStack
{
    std::atomic<Node<T> *> head{nullptr};
    std::atomic<int> size{0};
public:
    void PushFront(const T &value)
    {
        auto *node = new Node<T>(value);
        node->next = head.load();
        while(!head.compare_exchange_weak(node->next, node)); //②
        size.fetch_add(1);
    }
    bool PopFront(T &value)
    {
        Node<T>* temp = head.load();//留一个快照snapshot
        do {
            if (temp == nullptr) return false;//这句判断要在循环里面
        } while (!head.compare_exchange_weak(temp,temp->next));
        value = temp->data;//? before or after and tail behind this is a question
        delete temp;
        size.fetch_sub(1);
        return true;
    }
    int32_t Size() { return size.load(); }
};

#include <thread>
#include <atomic>
#include <cassert>
#include <string>
#include <iostream>
#include <chrono>
#include <mutex>
using namespace std;
template<typename T>
struct Node
{
    Node(){}
    Node(const T &value) : data(value), next(nullptr) { }
    T data;
    Node *next = nullptr;
};

/*头插和头pop的方法
*/
template<typename T>
class LockFreeStack
{
    std::atomic<Node<T> *> head{nullptr};
    std::atomic<int> size{0};
public:
    void PushFront(const T &value)
    {
        auto *node = new Node<T>(value);
        node->next = head.load();
        while(!head.compare_exchange_weak(node->next, node)); //②
        size.fetch_add(1);
    }
    bool PopFront(T &value)
    {
        Node<T>* temp = head.load();//留一个快照snapshot
        do {
            if (temp == nullptr) return false;//这句判断要在循环里面
        } while (!head.compare_exchange_weak(temp, temp->next));
        value = temp->data;//? before or after and tail behind this is a question
        delete temp;
        size.fetch_sub(1);
        return true;
    }
    int32_t Size() { return size.load(); }
};
template<typename T>
class WithLockStack
{
    std::mutex mtx;
    Node<T>* head{nullptr};
    int size{0};
public:
    void PushFront(const T &value)
    {
        auto *node = new Node<T>(value);
        {
            std::lock_guard<std::mutex> lock(mtx);
            node->next = head;
            head = node;
            size++;
        }
    }
    bool PopFront(T &value){
        Node<T>* temp = head;
        {
            std::lock_guard<std::mutex> lock(mtx);
            if(head== nullptr) return false;
            head = head->next;
            value = temp->data;
            free(temp);
            size--;
        }
        return true;
    }
};
int main()
{
    const int SIZE = 1000000;
    //有锁测试
    auto start = chrono::steady_clock::now();
    WithLockStack<int> wl_stack;
    for(int i = 0; i < SIZE; ++i)
    {
        wl_stack.PushFront(i);
    }
    auto end = chrono::steady_clock::now();
    chrono::duration<double, std::micro> micro = end - start;
    cout << "with lock stack costs micro:" << micro.count() << endl;

    //无锁测试
    atomic<int> x{0};
    start = chrono::steady_clock::now();
    LockFreeStack<int> lf_stack;
    for(int i = 0; i < SIZE; ++i)
    {
        lf_stack.PushFront(i);
    }
    end = chrono::steady_clock::now();
    micro = end - start;
    cout << "free lock stack costs micro:" << micro.count() << endl;
    return 0;
}