C++ thread safe doubly linked list

Question

I need the above data structure for an application I'm writing. I wondered if there is a library that already implements it or if I have to write it myself?

I don't really want to reinvent the wheel if it is not necessary.

I need this structure to be able to add and remove items using multiple threads without having to lock up the whole structure while doing so.

Answer 1

Link to a related research: Is a lock (wait) free doubly linked list possible?

As you are not requesting a lock-free container, I am not marking this as an exact duplicate.

Note: while the interface and performance characteristics looks like a double linked list, internally those structures are very complex, based on hash tables or other structures. There is nothing which would a a double linked list internally and would be lock free at the same time. I do not remember seeing a proof, but I think this is not possible.

---

Based on your additional information, I think you do not need a double linked list at all. You can use the Windows API single linked list instead. To add use InterlockedPushEntrySList, to remove for processing use InterlockedPopEntrySList.

Answer 2

There might be, but I think this was one of the lessons learned early in Java - data synchronicity is usually not at the container's member function level, but one step above. You should be using synchronisation objects before accessing a non-thread-safe list instead.

Consider:

ThreadSafeQueue tsq;
tsq.push_back(...); // add lots of data

...

// Find the first element that returns true for search_criteria(elem);
auto iter = tsq.find_if(search_criteria); 
// (1)                                  
if(iter != tsq.end()) // (2)
{
    tsq.erase(iter);
}

In this thread-safe queue, there are still two "gaps" where the queue can be changed by another thread. And, indeed, your iterator may be invalidated by those changes. Now compare:

Queue q;
q.push_back(...); // add lots of data

...

// Create some lock around a pre-existing mutex.
Lock lock(q_mutex);
// Find the first element that returns true for search_criteria(elem);
auto iter = q.find_if(search_criteria); 

if(iter != q.end())
{
    q.erase(iter);
}
// lock unlocks as it goes out of scope.

Here, because the lock has a larger granularity, it is possible to ensure consistency across the written algorithm.

Answer 3

would this http://www.boost.org/doc/libs/1_41_0/doc/html/boost/interprocess/message_queue.html work?

Answer 4

There are loads of papers on writing lock free queues using assembly/compiler intrinsics to perform atomic operations but it's really difficult to get it working.

So if you can use locks, maybe use something like this: Concurrent FIFO Queue with Boost