Is this thread safe list using lock is perfect?

Viewed 100

Below is the example source code of thread safe list using lock from c++ concurrency in action 2nd.

template<typename T>
class threadsafe_list
{
    struct node
    {
        std::mutex m;
        std::shared_ptr<T> data;
        std::unique_ptr<node> next;
        node():
            next()
        {}
        node(T const& value):
            data(std::make_shared<T>(value))
        {}
    };
    node head;
public:
    threadsafe_list()
    {}
    ~threadsafe_list()
    {
        remove_if([](node const&){return true;});
    }
    threadsafe_list(threadsafe_list const& other)=delete;
    threadsafe_list& operator=(threadsafe_list const& other)=delete;
    void push_front(T const& value)
    {
        std::unique_ptr<node> new_node(new node(value));
        std::lock_guard<std::mutex> lk(head.m);
        new_node->next=std::move(head.next);
        head.next=std::move(new_node);
    }
    template<typename Function>
    void for_each(Function f)
    {
        node* current=&head;
        std::unique_lock<std::mutex> lk(head.m);
        while(node* const next=current->next.get())
        {
            std::unique_lock<std::mutex> next_lk(next->m);
            lk.unlock();
            f(*next->data);
            current=next;
            lk=std::move(next_lk);
        }
    }
    template<typename Predicate>
    std::shared_ptr<T> find_first_if(Predicate p) // (1) is it safe ?
    {
        node* current=&head;
        std::unique_lock<std::mutex> lk(head.m);
        while(node* const next=current->next.get())
        {
            std::unique_lock<std::mutex> next_lk(next->m);
            lk.unlock();
            if(p(*next->data))
            {
                return next->data;
            }
            current=next;
            lk=std::move(next_lk);
        }
        return std::shared_ptr<T>();
    }
    template<typename Predicate>
    void remove_if(Predicate p)
    {
        node* current=&head;
        std::unique_lock<std::mutex> lk(head.m);
        while(node* const next=current->next.get())
        {
            std::unique_lock<std::mutex> next_lk(next->m);
            if(p(*next->data)) 
            {
                std::unique_ptr<node> old_next=std::move(current->next);
                current->next=std::move(next->next);
                next_lk.unlock();
            }
            else
            {
                lk.unlock();
                current=next;
                lk=std::move(next_lk);
            }
        }
    }
};

I understand how this code works. But I don't think this code is perfect. I put marks on the place to argue with.

(1) find_first_if returns shared_ptr instead of copied value of T. It gives chance of concurrency issue. I'll explain more. If user get the shared_ptr of data using find_first_if, then user can access the data through this pointer even while node is being modified. Is this safe action? I don't think so. My suggestion is that it should return copied value of T, which results in T find_first_if(Predicate p) {...}. Am I correct?

Edit : I separated the other questions from original one and create another post to focus on one subject

1 Answers
  1. It is actually necessary, not to prevent leaks but stack overflow. Because the nodes own each other, the destructor of each will recursively call destructors of all the following nodes. So destructing a long list would easily blow up the stack.

  2. Yes, that is incorrect, you should consult the documentation for Predicate. Even better would be to use C++14 [](const auto&){return true;} but due to lack of make_unique, the code might have been written with C++11 only.

  3. Yes, the exposed data is not protected by any lock anymore. Copy might be expensive and what about move-only types? Again, this should be properly documented in the method.

Related