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

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 2

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.