class spinlock_mutex {
    std::atomic_flag flag;

public:
    spinlock_mutex() : flag(ATOMIC_FLAG_INIT) {}

    void lock() {
        while (flag.test_and_set(std::memory_order_acquire));
    }

    void unlock() {
        flag.clear(std::memory_order_release);
    }
};

template<typename T>
class lock_free_stack
{
private:
    struct node
    {
        std::shared_ptr<T> data;
        node* next;
        node(T const& data_):
            data(std::make_shared<T>(data_))
        {}
    };
    std::atomic<node*> head;

public:
    void push(T const& data)
    {
        node* const new_node = new node(data);
        new_node->next = head.load();
        while (!head.compare_exchange_weak(new_node->next, new_node));
    }

    std::shared_ptr<T> pop()
    {
        node* old_head = head.load();
        while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
        // 这里 old_head->data 其实可以加上 std::move
        return old_head ? old_head->data : std::shared_ptr<T>();
    }
};

// first -> ... -> last -> nullptr
void chain_pending_nodes(node* first, node* last) {
    last->next = to_be_deleted;
    while (!to_be_deleted.compare_exchange_weak(last->next, first));
}
// 工具函数，找到链表的尾结点并调用前一个重载
void chain_pending_nodes(node* nodes) {
    node* last = nodes;
    while (node* const next = last->next) {
        last = next;
    }
    chain_pending_nodes(nodes, last);
}

std::shared_ptr<T> pop()
{
    node* old_head = head.load();
    while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
    auto ret = old_head ? std::move(old_head->data) : std::shared_ptr<T>();
    try_reclaim(old_head); // 尝试回收
    return ret;
}

std::shared_ptr<T> pop()
{
    ++threads_in_pop;
    node* old_head = head.load();
    while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
    auto ret = old_head ? std::move(old_head->data) : std::shared_ptr<T>();
    try_reclaim(old_head); // 尝试回收，--threads_in_pop 在这里面做
    return ret;
}

void try_reclaim(node* old_head) {
    if (threads_in_pop == 1) {
        node* nodes_to_delete = to_be_deleted.exchange(nullptr);
        if (!--threads_in_pop) {
            // 这里可以安全清理结点：
            // 计数归零要么是其他线程没来过，要么来了又走了。
            // 无论如何，只要当前在 pop() 中的线程只有本线程，则说明可以安全回收。
            // 这里的情形和双重校验锁有点相似，需要检查两次！
            // delete_nodes 实现很简单，就是对（可能为空的）链表一直删到底。
            delete_nodes(nodes_to_delete);
        } else if (nodes_to_delete) {
            // 这里清理结点不安全，需要将结点放回去：
            // threads_in_pop 减少后仍不为 0，这说明有新的线程进 pop() 了。
            // 其他线程可能在 if 判断结束后、exchange 之前把新结点加入到了回收链表中，
            // 这些结点可能还会被其他线程访问，因此删除不安全。
            chain_pending_nodes(nodes_to_delete);
        }
        // threads_in_pop == 1 成立，表明当前结点可以安全删除。
        // delete 语句放到 if 的下一行会更好理解，但 delete 比较耗时，我们希望能抓住
        // threads_in_pop == 1 这个条件还成立的机会，所以把 delete 放在了最后。
        delete old_head; 
    } else {
        chain_pending_node(old_head); // 不能安全删除，放到回收链表中。
        --threads_in_pop;
    }
}

std::shared_ptr<T> pop()
{
    std::atomic<void*>& hp = get_hazard_pointer_for_current_thread();
    node* old_head = head.load();
    do {
        node* temp;
        do {
            temp = old_head;
            hp.store(old_head);
            old_head = head.load();
        } while (old_head != temp);
        // 1. 内外双循环的必要性：
        // 外循环的 while 语句要访问 old_head->next，因此 old_head 必须是有效指针。
        // 内循环的 while 判断 old_head != temp 是为了保证存储 hp 的过程中 head 没有变化。
        // 一旦 hp 成功存储，这个指针就被保护了，old_head 也就不会被别的线程删除。
        // 2. 在循环中一般会用 compare_exchange_weak，但是这里用 compare_exchange_strong
        // 是不想让假性失败导致高开销的重试（在循环中有几个原子操作）。
    } while (old_head && !head.compare_exchange_strong(old_head, old_head->next));
    // 上面是在有保护的情况下取走 head
    // -------------------------------
    // 下面是尝试回收当前指针和回收链表中的其他指针
    hp.store(nullptr);
    std::shared_ptr<T> res;
    if (old_head) {
        res.swap(old_head->data);
        // outstanding_hazard_pointers_for 遍历全局记录，对每个记录简单调用 load() 来检查
        // 是否 old_head 还在使用中。如果扫过去一遍没有找到，则 old_head 不可能被使用。这是因为
        // 本线程已经把 old_head 取下来了，之前没有正在使用它的线程不可能再访问到它了。
        // 时间复杂度：O(最大工作线程数)
        if (outstanding_hazard_pointers_for(old_head)) {
            // 将该结点加入待删除列表。
            // 书上是将该结点再次封装到一个新的类型中，该类型在析构函数中会将结点指针转换回原来的
            // T* 类型，然后调用 delete 操作符。这个逻辑也可以手动来写。
            reclaim_later(old_head);
        } else {
            delete old_head;
        }
        // 将回收链表头和 nullptr 交换，然后遍历每个结点，对每个结点调用
        // outstanding_hazard_pointers_for，能回收就回收，不能回收就将结点重新放到回收链表中。
        // 时间复杂度：O(最大工作线程数 * 回收队列长度) = O(最大工作线程数^2)
        delete_nodes_with_no_hazards();
    }
    return res;
}

unsigned const max_hazard_pointers=100;
struct hazard_pointer
{
    std::atomic<std::thread::id> id;
    std::atomic<void*> pointer; // 只关心指针地址，这里的 pointer 隐去了类型
};
hazard_pointer hazard_pointers[max_hazard_pointers];

class hp_owner
{
    hazard_pointer* hp;
public:
    hp_owner(hp_owner const&) = delete;
    hp_owner operator=(hp_owner const&) = delete;
    hp_owner() : hp(nullptr)
    {
        for (unsigned i = 0; i < max_hazard_pointers; ++i) {
            std::thread::id old_id;
            if (hazard_pointers[i].id.compare_exchange_strong(
                old_id, std::this_thread::get_id()))
            {
                hp = &hazard_pointers[i];
                break;
            }
        }
        if (!hp) {
            throw std::runtime_error("No hazard pointers available");
        }
    }
    std::atomic<void*>& get_pointer()
    {
        return hp->pointer;
    }
    ~hp_owner()
    {
        hp->pointer.store(nullptr);
        hp->id.store(std::thread::id());
    }
};

std::atomic<void*>& get_hazard_pointer_for_current_thread()
{
    thread_local static hp_owner hazard;
    return hazard.get_pointer();
}

template<typename T>
class lock_free_stack
{
private:
    struct node;
    struct counted_node_ptr
    {
        int external_count;
        node* ptr;
    };

    struct node
    {
        std::shared_ptr<T> data;
        std::atomic<int> internal_count;
        counted_node_ptr next;

        node(T const& data_):
            data(std::make_shared<T>(data_)),
            internal_count(0)
        {}
    };

    std::atomic<counted_node_ptr> head; // 不一定无锁

public:
    ~lock_free_stack()
    {
        while(pop());
    }

    void push(T const& data)
    {
        counted_node_ptr new_node;
        new_node.ptr = new node(data);
        new_node.external_count = 1;
        new_node.ptr->next = head.load();
        while(!head.compare_exchange_weak(new_node.ptr->next, new_node));
    }
};

template<typename T>
class lock_free_stack
{
private:
    // other parts as in listing 7.11
    void increase_head_count(counted_node_ptr& old_counter)
    {
        counted_node_ptr new_counter;
        do
        {
            new_counter = old_counter;
            ++new_counter.external_count;
        }
        // 在将增加了外部计数的 counter 放回 head 之前要先检查 head 是否改变。
        // 如果失败了那么 head 的当前值写回到 old_counter 中，再次重试直到成功。
        while (!head.compare_exchange_strong(old_counter, new_counter));
        old_counter.external_count = new_counter.external_count;
    }

public:
    std::shared_ptr<T> pop()
    {
        counted_node_ptr old_head = head.load();
        for (;;)
        {
            increase_head_count(old_head);
            node* const ptr = old_head.ptr;
            if (!ptr)
            {
                return std::shared_ptr<T>();
            }
            // 如果失败了，head 的当前值会更新到 old_head 当中，
            // 这就是为什么 for 循环内部不需要加载 head 值。
            if (head.compare_exchange_strong(old_head, ptr->next))
            {
                std::shared_ptr<T> res;
                res.swap(ptr->data);
                // 修改计数，检查是否需要回收结点。
                // 内部计数和外部计数其实是一个整体，它们的总和表示真实引用，这里的
                // internal_count + external_count + offset 应该等于 0。为什么
                // 这个 offset 要取 -2？因为外部计数初始值是 1 表明链表对结点的引用，
                // 另外此线程在进入循环时就将外部计数加 1 了，表明 pop() 过程对结点的
                // 引用，现在要把这两部分都减掉。
                int const count_increase = old_head.external_count - 2;
                if (ptr->internal_count.fetch_add(count_increase) == -count_increase)
                {
                    delete ptr;
                }
                return res;
            }
            // 如果失败，说明这个 head 被其他结点取下了，开始新的循环重新取一个结点。
            // 不过因为本节点和其他节点读到了同样的 head，可能导致这个 head 没有被
            // 正常回收，所以这里减少内部计数看看结点是否需要回收。
            else if (ptr->internal_count.fetch_sub(1) == 1)
            {
                delete ptr;
            }
        }
    }
};

void push(T const& data) {
    counted_node_ptr new_node;
    new_node.ptr = new node(data);
    new_node.external_count = 1;
    new_node.ptr->next = head.load(std::memory_order_relaxed);     // A
    while (!head.compare_exchange_weak(new_node.ptr->next, new_node,
                                       std::memory_order_release,  // B
                                       std::memory_order_relaxed));// C
}

void increase_head_count(counted_node_ptr & old_counter) {
    counted_node_ptr new_counter;
    do {
        new_counter = old_counter;
        ++new_counter.external_count;
    } while (!head.compare_exchange_strong(old_counter, new_counter,
                                           std::memory_order_acquire,   // A
                                           std::memory_order_relaxed)); // B
    old_counter.external_count = new_counter.external_count;
}

std::shared_ptr<T> pop()
{
    counted_node_ptr old_head = head.load(std::memory_order_relaxed);
    for(;;)
    {
        increase_head_count(old_head);
        node* const ptr = old_head.ptr;
        if (!ptr)
        {
            return std::shared_ptr<T>();
        }
        if (head.compare_exchange_strong(old_head, ptr->next,
                                        std::memory_order_relaxed)) // A
        {
            std::shared_ptr<T> res;
            res.swap(ptr->data);
            int const count_increase = old_head.external_count - 2;
            if(ptr->internal_count.fetch_add(count_increase,
                   std::memory_order_release) == -count_increase) // B
            {
                delete ptr;
            }
            return res;
        }
        else if (ptr->internal_count.fetch_add(-1,
                     std::memory_order_relaxed) == 1) // C
        {
            ptr->internal_count.load(std::memory_order_acquire); // D
            delete ptr;
        }
    }
}

// 线程 1
if (head.compare_exchange_strong(old_head, ptr->next,
                                 std::memory_order_relaxed))
{
    int const count_increase = old_head.external_count - 2;
    if(ptr->internal_count.fetch_add(count_increase,
           std::memory_order_release) == -count_increase) // t0
    {
        delete ptr; // 还有其他线程在使用，因此没进来
    }
    std::shared_ptr<T> res;
    res.swap(ptr->data); // t2: ptr->data 和上面的指令没有相关性，因此可以重排
    return res;
}
// 线程 2
else if (ptr->internal_count.fetch_add(-1,
             std::memory_order_relaxed) == 1)
{
    // ptr->internal_count.load(std::memory_order_acquire); // 假设没有做同步
    // 同步是需要两个线程配合的，这里注释掉一个就能破坏同步
    delete ptr; // t1
}

P.S. x 表示结点的 data 非空
A) ✔
head          head
+---+         +---+   +---+
|   |   ==>   | x |-->|   |
+---+         +---+   +---+
tail                   tail

B) ❌
head          head
+---+         +---+   +---+
|   |   ==>   |   |-->| x |
+---+         +---+   +---+
tail                   tail

void push(T new_value)
{
    std::unique_ptr<T> new_data(new T(new_value));
    counted_node_ptr new_next;
    new_next.ptr=new node;
    new_next.external_count=1;
    counted_node_ptr old_tail=tail.load();
    for(;;)
    {
        increase_external_count(tail,old_tail);    
        T* old_data=nullptr;
        if(old_tail.ptr->data.compare_exchange_strong(   
           old_data,new_data.get()))          // A 先尝试把 data 放上去
        {
            old_tail.ptr->next=new_next;      // 放上去之后才修改 next
            old_tail=tail.exchange(new_next); // B
            free_external_counter(old_tail);
            new_data.release();
            break;
        }
        old_tail.ptr->release_ref();
    }
}

// 无锁栈（只展示了数据成员）
struct node
{
    std::shared_ptr<T> data;
    std::atomic<int> internal_count;
    counted_node_ptr next;
};

// 无锁队列（只展示了数据成员）
struct node
{
    std::atomic<T*> data;               // 原子化
    std::atomic<node_counter> count;    // int 变成 node_counter，包含新的外部计数器计数
    std::atomic<counted_node_ptr> next; // 原子化
};

template<typename T>
class lock_free_queue
{
private:
    void set_new_tail(counted_node_ptr &old_tail,
                      counted_node_ptr const &new_tail)
    {
        node* const current_tail_ptr = old_tail.ptr;
        while (!tail.compare_exchange_weak(old_tail, new_tail) &&
               old_tail.ptr == current_tail_ptr);
        if (old_tail.ptr == current_tail_ptr)
            free_external_counter(old_tail);
        else
            current_tail_ptr->release_ref();
    }

public:
    void push(T new_value)
    {
        std::unique_ptr<T> new_data(new T(new_value));
        counted_node_ptr new_next;
        new_next.ptr = new node;
        new_next.external_count = 1;
        counted_node_ptr old_tail = tail.load();

        for (;;)
        {
            increase_external_count(tail, old_tail);
            T* old_data = nullptr;
            if (old_tail.ptr->data.compare_exchange_strong(old_data, new_data.get()))
            {
                counted_node_ptr old_next = {0};
                if (!old_tail.ptr->next.compare_exchange_strong(old_next, new_next))
                {
                    delete new_next.ptr;
                    new_next = old_next;
                }
                // set_new_tail 可能会失败，如果失败说明其他线程成功了。从结果来说 tail
                // 一定会被更新，因此 old_tail 不再被 tail 引用。区别是如果是本线程成功
                // 本线程就要负责清理外部计数，否则只减小内部计数。
                set_new_tail(old_tail, new_next);
                new_data.release();
                break;
            }
            else
            {
                counted_node_ptr old_next = {0};
                // 尽管放 data 失败了，还是可以尝试把 next 放上的。
                // 是谁放的 next 无所谓，因为稳定后的 tail 结点是 dummy 的，里面没放数据。
                if (old_tail.ptr->next.compare_exchange_strong(old_next, new_next))
                {
                    old_next = new_next;
                    // 如果已经成功放上了，就申请一个新的结点，保证 new_next.ptr 可以用于
                    // 下一轮的重试。
                    new_next.ptr = new node;
                }
                set_new_tail(old_tail, old_next);
            }
        }
    }
};