Removed node detection in locked buffer fiole

I was working on a C ++ 11 fifo locked buffer. And I almost figured it out. However, one small detail is better than me. The buffer has a head that points to:

std::shared_ptr<node<T>> m_head;


A type:

    struct node
        node(const T data)
            data(new T(data)),
        std::shared_ptr<T> data;
        std::shared_ptr<node<T>> next;


And then there is the result:

    void produce(const T &&data)
        //bool indicating whether a notification should be sent after adding
        bool l_notifyUponAdding;

        //the new node to be added at the end of the array
        std::shared_ptr<node<T>> l_newNode(new node<T>(std::forward<const T&&>(data)));
        //pointer to the last node
        std::shared_ptr<node<T>> l_lastNode(std::atomic_load(&m_head));
        //value to compare the next of the last node with
        std::shared_ptr<node<T>> l_expectedNullPointer;
        //notify if this isn't the only node
        l_notifyUponAdding = !l_lastNode;

        if (!l_lastNode)//if there are no nodes, add this as the only node
        if (std::atomic_compare_exchange_strong(&m_head, &l_expectedNullPointer, l_newNode))

            while (l_lastNode->next)
                l_lastNode = std::atomic_load(&l_lastNode)->next;
        } while (!std::atomic_compare_exchange_weak(&l_lastNode->next, &l_expectedNullPointer, l_newNode));

        //adding failed since another thread already did this. 
        l_lastNode = l_expectedNullPointer;

        if (l_notifyUponAdding)


And consume:

        std::shared_ptr<T> consume(bool blockingCall = false)
            //Check if the head is null if it is:
            if (!std::atomic_load(&m_head))
                if (blockingCall)//And this is a blocking call,
                        m_newDataWaiter.wait(m_newDataWaiterLock, [this]{return std::atomic_load(&(this->m_head)) == nullptr; });//we block until
                    } while (!std::atomic_load(&m_head));// the load yields a head that is not null(to avoid unnecessary calls on spurious wake ups)
                else//And this is not a blocking call we 
                    return nullptr;

        //If we've found a valid head we will now try to make the node pointed to by head the new head. 
        std::shared_ptr<node<T>> l_poppee = atomic_load(&m_head);
        std::shared_ptr<node<T>> l_newHead = atomic_load(&m_head);

        //note that l_poppee gets updated if the compare exchange fails
        while (l_poppee && !std::atomic_compare_exchange_weak(&m_head, &l_poppee, l_poppee->next))


        if (l_poppee)
            return l_poppee->data;
            return std::shared_ptr<T>();



Everything seems to work well. However, I believe there is one drawback. If all nodes are consumed at runtime produce

. The data will be added to the last item. Although the item has already been removed.

To be more precise, if this line is executed:

if (std::atomic_compare_exchange_strong(&m_head, &l_expectedNullPointer, l_newNode))


And the loaded node was not null. The next element of the last node will be changed. Regardless of whether nodes are removed at this time or not. Nodes will not be physically removed if a product function is called because of shared pointers.

However, the main pointer will be set to NULL. And so the new node will be removed as soon as the product function is deduced.

Does anyone know a solution to this problem :)?


source to share

1 answer

This case is always resolved in non-blocking lists by keeping a dummy node in the list. The head always points to the dummy node, which is the first node in the list.

When the queue becomes empty, both heads and tails point to the dummy node.

See for more details , so I am not misrepresenting the concept as it is easy to pick from the article.



All Articles