Lock-free multiple-consumer multiple-producer queue

The code below implements an intrusive lock-free queue that supports multiple concurrent producers and consumers.

Some features:

• Producers and consumers work on separate ends of the queue most of the time.

• The fast path for producers and consumers has 4 atomic ops.

• Version numbers are used to prevent the ABA problem.

• Threads assist other threads in completing their operations, they're never blocked waiting for another thread to do something.

I'm particularly interested in comments regarding the correctness of this design. Unless proven otherwise I'm assuming that this code is broken, although I've tried to the best of my ability to have a correct lock-free implementation.

```
#include
#include

struct LockfreeNode
{
std::atomic* next;
uintptr_t version;

LockfreeNode()
: next(nullptr)
, version(0)
{
}

LockfreeNode(std::atomic* next, uintptr_t version)
: next(next)
, version(version)
{
}
};

template
class LockfreeQueue
{
public:
typedef LockfreeNode Node;
typedef std::atomic AtomicNode;
typedef typename AtomicNode T::* NodeMemberPointer;

LockfreeQueue(NodeMemberPointer node)
: mNodeMember(node)
{
mSentinel = Node(&mSentinel, PreviousVersion(1));
mHead = Node(&mSentinel, 1);
mTail = Node(&mSentinel, 1);
}

void Queue(const T& element)
{
AtomicNode* node = ToNode(element);

QueueNode(node, 0);
}

T* Dequeue()
{
AtomicNode* result = DequeueNode();

return result ? ToElement(result) : nullptr;
}

private:
void QueueNode(AtomicNode* node, uintptr_t generation)
{
// Capture the tail to figure out what the last node is. The last node can be a
// regular node or it can be the sentinel.
//
// - Regular node:
//
// A->s->B->C N ; C is the last node, N is the new node
// 1 2 2 2
// ^ ^
// h t
// 2 2
//
// - Sentinel:
//
// B->C->D->s N
// 2 2 2 2
// ^

I just have some stylistic things for a start:

-
Since your custom types are in PascalCase, your function names should instead be in camelCase or in snake_case. This isn't a requirement, but it makes it easier to distinguish between them.

-
The naming convention used for the private members looks like a form of Hungarian Notation, which is quite disliked in strongly-typed languages such as C++. It is more common to prefix members with m_ instead, though you may not need to do that here.

-
Some functions such as NextVersion(), PreviousVersion(), and ToElement() don't modify the argument, so those arguments should be const& in order to avoid a copy.

StackExchange Code Review Q#24696, answer score: 3