concept push in category c++

This is an excerpt from Manning's book C++ Concurrency in Action, Second Edition. Login to get full access to this book.

push() is relatively simple 5. You construct a counted_node_ptr that refers to a freshly allocated node with associated data and set the next value of the node to the current value of head. You can then use compare_exchange_weak() to set the value of head, as in the previous listings. The counts are set up so the internal_count is zero, and the external_count is one. Because this is a new node, there’s currently only one external reference to the node (the head pointer itself).

Using the reference-counting scheme avoids this particular race, but it’s not the only race in push(). If you look at the revised version of push() in listing 7.15, you’ll see a pattern you saw in the stack: load an atomic pointer 1 and dereference that pointer 2. In the meantime, another thread could update the pointer 3, eventually leading to the node being deallocated (in pop()). If the node is deallocated before you dereference the pointer, you have undefined behavior. Ouch! It’s tempting to add an external count in tail the same as you did for head, but each node already has an external count in the next pointer of the previous node in the queue. Having two external counts for the same node requires a modification to the reference-counting scheme to avoid deleting the node too early. You can address this by also counting the number of external counters inside the node structure and decreasing this number when each external counter is destroyed (as well as adding the corresponding external count to the internal count). If the internal count is zero and there are no external counters, you know the node can safely be deleted. This is a technique I first encountered through Joe Seigh’s Atomic Ptr Plus Project (http://atomic-ptr-plus.sourceforge.net/). The following listing shows how push() looks under this scheme.

Listing 7.16. Implementing push() for a lock-free queue with a reference-counted tail

template<typename T>
class lock_free_queue
{
private:
    struct node;
    struct counted_node_ptr
    {
        int external_count;
        node* ptr;
    };
    std::atomic<counted_node_ptr> head;
    std::atomic<counted_node_ptr> tail;                      #1
    struct node_counter
    {
        unsigned internal_count:30;
        unsigned external_counters:2;                        #2
    };
    struct node
    {
        std::atomic<T*> data;
        std::atomic<node_counter> count;                     #3
        counted_node_ptr next;
        node()
        {
            node_counter new_count;
            new_count.internal_count=0;
            new_count.external_counters=2;                   #4
            count.store(new_count);

            next.ptr=nullptr;
            next.external_count=0;
        }
    };
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);          #5
            T* old_data=nullptr;
            if(old_tail.ptr->data.compare_exchange_strong(   #6
               old_data,new_data.get()))
            {
                old_tail.ptr->next=new_next;
                old_tail=tail.exchange(new_next);
                free_external_counter(old_tail);             #7
                new_data.release();
                break;
            }
            old_tail.ptr->release_ref();
        }
    }
};


!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":11,\"ch\":61},{\"line\":11,\"ch\":63}],[{\"line\":15,\"ch\":61},{\"line\":15,\"ch\":63}],[{\"line\":20,\"ch\":61},{\"line\":20,\"ch\":63}],[{\"line\":26,\"ch\":61},{\"line\":26,\"ch\":63}],[{\"line\":43,\"ch\":61},{\"line\":43,\"ch\":63}],[{\"line\":45,\"ch\":61},{\"line\":45,\"ch\":63}],[{\"line\":50,\"ch\":61},{\"line\":50,\"ch\":63}]]"}
!@%STYLE%@!

copy

The node is initialized with the internal_count set to zero and the external_counters set to 2 4, because every new node starts out referenced from tail and from the next pointer of the previous node once you’ve added it to the queue. push() itself is similar to listing 7.15, except that before you dereference the value loaded from tail in order to call to compare_exchange_strong() on the data member of the node 6, you call a new function increase_external_count() to increase the count 5, and then afterward you call free_external_counter() on the old tail value 7.

With the push() side dealt with, let’s take a look at pop(). This is shown in the following listing and blends the reference-counting logic from the pop() implementation in listing 7.12 with the queue-pop logic from listing 7.14.