Programmer's Blog

Programmer's reference

[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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: