non-blocking thread-safe queue in C++?

Question

Is there a thread-safe, non-blocking queue class in the C++?

Probably a basic question but I haven't been doing C++ for a long time...

EDIT: removed STL requirement.

Answer 1

Since the current C++ standard doesn't even acknowledge the existence of threads, there is most certainly nothing thread-safe in the STL or any other part of the standard library.

Answer 2

STL containers are not thread-safe, you should implement your treatment for concurrent access.
There is this project (C++) that aims to serve concurrent accesses : CPH STL
and paper about.

Answer 3

Short answer - no. STL does not concern itself with concurrency (at least on the specification level.) Current C++ standard says nothing about threads.

You can easily build such a queue on top of STL and Boost though - just wrap std::queue and boost::mutex in your custom class.

Answer 4

Assuming your CPU has a double-pointer-wide compare-and-swap (compxchg8b on 486 or higher, compxchg16b on most amd64 machines [not present on some early models by Intel])... There is an algorithm here.

Update: It's not hard to translate this to C++ if you aren't afraid of doing a bit of work. :P

This algorithm assumes a "pointer with tag" structure which looks like this:

// Be aware that copying this structure has to be done atomically...

template <class T>
struct pointer
{
   T *ptr;
   uintptr_t tag;
};

Then you want to wrap the instructions lock cmpxchg{8|16}b with some inline asm...

Maybe then you can write the queue node like this:

template <class T>
struct queue_node
{
    T value;
    pointer<queue_node<T> > next;
};

The rest is more or less a transcription of the algorithm I linked to...

Answer 5

You need to implement it yourself or use a library implementing it. To do it yourself, you may want to have a look at this:

Implementing a Thread-Safe Queue using Condition Variables

Answer 6

This seems to have been a popular subject on Dr. Dobb's last year:

• Lock-Free Queues
• Writing Lock-Free Code: A Corrected Queue