c++ - Deleted node detection in lockless fifo buffer -

i've been working on lockless c++11 fifo buffer. , i've got it. 1 small detail has gotten better of me. buffer has head pointed by:

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

of type:

    struct node     {         node(const t data)             :             data(new t(data)),             next(nullptr)         {}         std::shared_ptr<t> data;         std::shared_ptr<node<t>> next;     }; 

and there produce:

    void produce(const t &&data)     {         //bool indicating whether notification should sent after adding         bool l_notifyuponadding;          //the new node added @ end of array         std::shared_ptr<node<t>> l_newnode(new node<t>(std::forward<const t&&>(data)));         //pointer last node         std::shared_ptr<node<t>> l_lastnode(std::atomic_load(&m_head));         //value compare next of last node         std::shared_ptr<node<t>> l_expectednullpointer;         //notify if isn't node         l_notifyuponadding = !l_lastnode;          if (!l_lastnode)//if there no nodes, add node         if (std::atomic_compare_exchange_strong(&m_head, &l_expectednullpointer, l_newnode))             return;                  {             l_expectednullpointer.reset();             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 thread did this.          l_lastnode = l_expectednullpointer;           if (l_notifyuponadding)             m_newdatawaiter.notify_one();         }     

and consume:

        std::shared_ptr<t> consume(bool blockingcall = false)         {             //check if head null if is:             if (!std::atomic_load(&m_head))             {                 if (blockingcall)//and 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));// load yields head not null(to avoid unnecessary calls on spurious wake ups)                 }                 else//and not blocking call                  {                     return nullptr;                 }             }          //if we've found valid head try make node pointed head 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 l_poppee gets updated if 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;         else             return std::shared_ptr<t>();     } 

functions.

all seems work well. reckon there 1 flaw. if nodes consumed whilst executing produce. data added last element. though element has been deleted.

to more precise, if line has been executed:

if (std::atomic_compare_exchange_strong(&m_head, &l_expectednullpointer, l_newnode)) 

and loaded node wasn't zero. next element of last node changed. regardless of whether nodes being deleted in meantime or not. nodes not physically deleted long produce function being excuted, because of shared pointers.

however, main pointer set null. , therefore new node deleted produce function exited.

would happen know solution problem:)?

this case solved in lock-free lists keeping dummy node in list. head points dummy node first node in list.

when queue becomes empty, both head , tail point dummy node.

you can @ http://www.research.ibm.com/people/m/michael/podc-1996.pdf details, don't misrepresent concept picked article.