Programmer's Blog

Programmer's reference

Monthly Archives: March 2017

[C++]single consumer lock_free_queue implementation

#include \<iostream\>
#include \<atomic\>
#include \<thread\>
#include \<chrono\>
#include \<mutex\>

template\
class lock_free_queue
{
private:
    struct node
    {
        std::shared_ptr\<T\> data;
        node* next;
        node(): next(nullptr) {}
    };

    std::atomic\<node*\> head;
    std::atomic\<node*\> tail;
    node* pop_head()
    {
        node* const old_head=head.load();
        if(old_head==tail.load())
        {
            return nullptr;
        }
    head.store(old_head-\>next);
    return old_head;
    }

public:
    lock_free_queue():
    head(new node),tail(head.load()) {}
    lock_free_queue(const lock_free_queue& other)=delete;
    lock_free_queue& operator=(const lock_free_queue& other)=delete;
    ~lock_free_queue()
    {
        while(node* const old_head=head.load())
        {
            head.store(old_head-\>next);
            delete old_head;
        }
    }
    std::shared_ptr\<T\> pop()
    {
        node* old_head=pop_head();
        if(!old_head)
        {
            return std::shared_ptr\<T\>();
        }
        std::shared_ptr\<T\> const res(old_head-\>data);
        delete old_head;
        return res;
    }

    void push(T new_value)
    {
        std::shared_ptr\<T\> new_data(std::make_shared\<T\>(new_value));
        node* p=new node;
        node* const old_tail=tail.load();
        old_tail-\>data.swap(new_data);
        old_tail-\>next=p;
        tail.store(p);
    }
};

int main()
{
    lock_free_queue\<int\> queue;
    queue.push(1);
    queue.push(2);
    queue.push(3);
    std::cout \<\< *queue.pop() \<\< "\n";
    std::cout \<\< *queue.pop() \<\< "\n";
    queue.push(4);
    std::cout \<\< *queue.pop() \<\< "\n";
    std::cout \<\< *queue.pop() \<\< "\n";
}

//result: 1 2 3 4

[C++]Simple lock-free stack implementation

#include \<iostream\>
#include \<atomic\>

using namespace std;

template \<typename T\>
struct node
{
    T data;
    node* next;
    node* previous;
    node(const T& data) : data(data), next(nullptr), previous(nullptr) {}
};

template \<T\>
class stack
{
    std::atomic\<node\<T\>*\> head;
public:
    void push(const T& data)
    {
        node\<T\>* new_node = new node\<T\>(data);

        new_node->previous = head.load(std::memory_order_relaxed);
        new_node->next = head.load(std::memory_order_relaxed);

        while(!head.compare_exchange_weak(new_node->next, new_node,
        std::memory_order_release,
        std::memory_order_relaxed));
    }

    T pop_front()
    {
        node\<T*\> read_node;
        read_node = head.load(std::memory_order_relaxed);
        T ret = read_node->data;

        while(!head.compare_exchange_weak(read_node, read_node->previous,
        std::memory_order_release,
        std::memory_order_relaxed));

        return ret;
    }
};

int main()
{
    stack\<int\> s;
    s.push(1);
    s.push(2);
    s.push(3);

    cout << s.pop_front() << "\n";
    cout << s.pop_front() << "\n";

    s.push(4);
    cout << s.pop_front() << "\n";
    cout << s.pop_front() << "\n";

} 

//result: 3 2 4 1