c++ 无锁线程安全stack

c++ 无锁线程安全stack

最近看了本多线程的书, 记录下笔记

#include 
#include 
#include 
#include 
#include 
#include 

namespace lock_stack {
    template
    class lock_free_stack {
    private:
        struct node;

        struct counted_node_ptr {
            int external_count;
            node *ptr;
        };

        struct node {
            std::shared_ptr data;
            std::atomic internal_cont;
            counted_node_ptr next;

            node(T const &_data) :
                    data(std::make_shared(_data)),
                    internal_cont(0)
                    {};
        };

        std::atomic head;

        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_weak(old_counter, new_counter));
            old_counter.external_count = new_counter.external_count;
        }

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

        void print() {
            for (counted_node_ptr h = head.load(); h.external_count == 1; h = h.ptr->next) {
                std::cout << *h.ptr->data;
            }

            std::cout << std::endl;
        }

        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));
            std::cout << "push finish " << data << std::endl;
        }

        std::shared_ptr pop() {
            counted_node_ptr old_head = head.load();
            for(;;){
                increase_head_count(old_head);
                node *ptr = old_head.ptr;
                if (!ptr)
                    return std::shared_ptr();
                if (head.compare_exchange_strong(old_head, ptr->next)) {
                    std::shared_ptr res;
                    res.swap(ptr->data);

                    int const count_increase = old_head.external_count - 2;
                    if (ptr->internal_cont.fetch_add(count_increase) == -count_increase)
                        delete ptr;
                    return res;
                } else if (ptr->internal_cont == 1) {
                    delete ptr;
                }
            }
        }
    };

    void test() {
        lock_free_stack chain;

        std::vector th(10);
        for (int i = 0; i < th.size(); i++)
            th[i] = std::thread([i, &chain]() {
                chain.push(i);
            });
        for (auto &t : th)
            t.join();
        std::this_thread::sleep_for(std::chrono::seconds(1));
        chain.print();
        auto r = chain.pop();
        chain.print();
    }
} // namespace lock_stack