Programmer's Blog

Programmer's reference

[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
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: