Multithreaded lock-free queue implementation

Question

My partner and I are beginning to believe there could be a desync possibility in the lock free queue we have written, but we would like some fresh eyes on the subject. What are your thoughts on our design?

// nolockqueue.hpp:
#ifndef NOLOCKQUEUE_HPP
#define NOLOCKQUEUE_HPP
template<typename T>
class noLockQueue {
public:
 noLockQueue();
 ~noLockQueue();
 void push(const T dataVar);
 bool pop(T &dataVar);
private:
 struct node {
 node(T dataPassed) : dataVar(dataPassed), next(NULL) {};
 T dataVar;
 node* next;
 };
 node* topOfList;
 node* bottomOfList;
};
template<typename T>
noLockQueue<T>::noLockQueue() {
 topOfList = NULL;
 bottomOfList = NULL;
}
template<typename T>
noLockQueue<T>::~noLockQueue() {
 node* temp;
 while (topOfList != NULL) {
 temp = topOfList->next;
 delete topOfList;
 topOfList = temp;
 }
 if (bottomOfList != NULL)
 throw("Not All Nodes Deleted - nolockqueue/38/.cpp"); // TODO: Strange error to throw.
}
template<typename T>
void noLockQueue<T>::push(const T dataVar) {
 if (topOfList == NULL) {
 topOfList = bottomOfList = new node(dataVar);
 return;
 } else {
 bottomOfList->next = new node(dataVar);
 bottomOfList = bottomOfList->next;
 }
}
template<typename T>
bool noLockQueue<T>::pop(T &dataVar) {
 if (topOfList == NULL)
 return false;
 dataVar = topOfList->dataVar;
 node* temp = topOfList->next;
 delete topOfList;
 topOfList = temp;
 return true;
}
#endif
// main.cpp (purely a test unit):
#include <iostream>
#include <thread>
#include "nolockqueue.hpp"
#include <windows.h> // For Sleep().
noLockQueue<int> queue;
void threadFunc() {
 int var = 0;
 Sleep(10);
 while (queue.pop(var)) {
 std::cout << "\nPopped: " << var;
 Sleep(1);
 }
}
int main(int argc, char* argv[]) {
 std::thread myThread(threadFunc);
 for (int i = 0; i < 1000; ++i) {
 queue.push(i);
 std::cout << "\nPushed: " << i;
 Sleep(1);
 }
 myThread.join();
 std::cin >> argc;
 return 0;
}

Answer 1

This is not a lock-free queue, but a locking-agnostic queue. That means, it is not safe to use on multiple threads. The reason this works in your implementation is because the push calls alter the end of the queue and the pop calls alter the beginning (so conflicts are more or less, avoided).

If you tried adding elements from multiple threads at the same time (for example), you would leak elements.

Since bottomOfList is never changed in the destructor, if it is initialized, you will always get to throw the exception.

Consider splitting pop into a const T& top() const and a void pop(); This would allow for an exception-safe implementation of the operations.

Answer 2

A few words on coding style:

The naming you've chosen for your types is a bit unusual. User defined types more commonly use CamelCase notation, with the first letter upper-case. So your noLockQueue and the internal node would be better as NoLockQueue and Node.

Use of NULL: You never, ever use NULL in C++. nullptr is a much superior option.

Your code is not following the Rule of Three. This is an important aspect that should be looked into to make this container more usable.

Architecture:

void push(const T dataVar) is taking its parameter by const value. This is about the worst way to pass a param if T is a complex object type. It will disable move and it will be performing two copies, one for the param and one when you store it into the container. Ideally, you should provide two variants of push(), one that takes the param by const reference and one that takes a move reference:

void push(const T & dataVar); // const ref
void push(T && dataVar); // move ref

That's how std::vector::push_back() is implemented, for instance.

Ideally, pop() should not take any parameters. Provide a const T & front() const method to get the head of the queue (or back() to get the other end, depends on how you need it to operate).

Some minor details:

Extra semicolon at the end here (constructor of node):

node(T dataPassed) : dataVar(dataPassed), next(NULL) {}; // <--- Some compilers will complain

Useless return statement on void function:

if (topOfList == NULL) {
 topOfList = bottomOfList = new node(dataVar);
 return; // <--- Not needed
} else {
 bottomOfList->next = new node(dataVar);
 bottomOfList = bottomOfList->next;
}
// The function ends here

This is no longer necessary:

#include <windows.h> // For Sleep().

Use std::this_thread::sleep_for() from <thread>.

• TorbenC: Thank you very much for the architectural overview. Very much appreciated my friend.