One thread is limited to one action (i.e. there is a push-thread and a pop-thread and the push-thread can't pop and vice versa). By "zero copy" I mean no copying of data (mostly C++ structures) will take place during push and pop operations.

Mostly I am trying to get feedback about two things:

1. My strategy of copying pointers rather than data by allocating all the memory initially in the constructor and then just copying pointers rather than entire structures during push and pop operations. I know this is extremely unorthodox, but for me memory is not a constraint and I need speed and avoid expensive copies. Is my implementation inherently unsafe in some way? Are there any other simpler way of doing this?




2. Is my queue threadsafe if the push operation is limited to one of the threads and pop to another one? What am I missing here? In the sample test run in the implementation file below it performs fine. If my queue isn't threadsafe, how may I break it?

#ifndef CIRCULARPTRQUEUE_H_
#define CIRCULARPTRQUEUE_H_

#include <atomic>
#include <vector>
#include <cstddef>

template<typename T, size_t queueSize>
class CircularPtrQueue

private:

 size_t m_queue_capacity_ = queueSize;

 T** m_queue_buffer_; 
 //A pointer to an array of the templated type.

 std::atomic<bool> isEmpty[queueSize]; 
 //Used for tracking in which locations of 
 //the above array data has been saved. 

 size_t m_write_position_;
 size_t m_read_position_;

public:

 CircularPtrQueue()
 
 m_queue_buffer_ = new T*[m_queue_capacity_]; 
 //Allocate enough memory in advance for the queue.

 for(size_t i = 0; i < m_queue_capacity_; i++)
 
 m_queue_buffer_[i] = new T();
 //Allocate memory for the respective objects.
 isEmpty[i] = true;
 

 m_write_position_ = 0;
 m_read_position_ = 0;
 

 T* GetWritablePushPtrToData()
 
 if(isEmpty[m_write_position_] == false)
 
 return nullptr;
 
 return m_queue_buffer_[m_write_position_];
 

 void IncrementPositionAfterWrite()
 
 isEmpty[m_write_position_] = false;
 if(m_write_position_ == m_queue_capacity_ - 1)
 
 m_write_position_ = 0; 
 
 else
 
 m_write_position_++;
 
 

 T* PopAndGetPtrToData()
 
 if(isEmpty[m_read_position_] == true)
 
 return nullptr;
 
 else
 
 return m_queue_buffer_[m_read_position_];
 //Will be returning this pointer so that client can read the data.
 
 

 void IncrementPositionAfterRead()
 
 if(isEmpty[m_read_position_] == false)
 
 isEmpty[m_read_position_] = true;
 if(m_read_position_ == m_queue_capacity_ - 1)
 
 m_read_position_ = 0;
 
 else
 
 m_read_position_++;
 
 
 

 CircularPtrQueue& operator=(const CircularPtrQueue&) = delete;
 CircularPtrQueue(const CircularPtrQueue&) = delete;

 ~CircularPtrQueue()
 
 for(size_t i = 0; i < m_queue_capacity_; i++)
 
 delete m_queue_buffer_[i];
 
 

;


#endif

And here is the test file:

#include "circularptrqueue.h"
#include <tuple>
#include <iostream>
#include <thread>
#include <chrono>

#define QUEUE_SIZE 100000
#define NUM_CONSUMERS 1

struct data

 long int timestamp;
 std::tuple<long int, int, unsigned short int> glue;
;

void writer(CircularPtrQueue<struct data, QUEUE_SIZE>& cptr_q, int& writerNullCount)

 for(unsigned int i = 0; i < QUEUE_SIZE; i++)
 
 struct data* writable_ptr = cptr_q.GetWritablePushPtrToData();
 if(writable_ptr == nullptr)
 
 writerNullCount++;
 
 else
 
 writable_ptr->timestamp = i;
 writable_ptr->glue = std::make_tuple(11,12,13);
 cptr_q.IncrementPositionAfterWrite();
 
 


void reader(CircularPtrQueue<struct data, QUEUE_SIZE>& cptr_q, int& readerNullCount)

 while(true)
 
 struct data* popped_value = cptr_q.PopAndGetPtrToData();

 if(popped_value == nullptr)
 
 readerNullCount++;
 
 else
 
 std::cout << "Popped val timestamp: " << popped_value->timestamp << std::endl;
 cptr_q.IncrementPositionAfterRead();
 
 


int main()

 CircularPtrQueue<struct data, QUEUE_SIZE> struct_circular_queue_mt;

 int readerNullCount = 0, writerNullCount = 0;

 std::thread writer_thread(writer, std::ref(struct_circular_queue_mt), std::ref(writerNullCount));
 std::thread reader_thread(reader, std::ref(struct_circular_queue_mt), std::ref(readerNullCount));

 reader_thread.join();
 writer_thread.join();

 std::cout << "Reader Null Count: " << readerNullCount << " Writer Null Count: " << writerNullCount << std::endl;

You should be able to compile with:

g++ -std=c++11 -g -o circularptrqueuetest main.cpp -lpthread

As to question 1: Yes, what you are doing is unsafe. Yes, there are better alternatives.

Why is allocating memory manually unsafe? The most simple reason is: You might forget to free it (in which case you cause a memory leak), or accidentally free it twice (in which case you cause undefined behavior), or use a pointer to manually allocated memory after free (also causing undefined behavior). Let's see whether any of these points apply to your code.

~CircularPtrQueue()

 for(size_t i = 0; i < m_queue_capacity_; i++)
 
 delete m_queue_buffer_[i];
 

Bingo! You're leaking memory! But how? Let's look at how m_queue_buffer_ is defined and initialized:

T** m_queue_buffer_;

//...

m_queue_buffer_ = new T*[m_queue_capacity_]; 

//...

for(size_t i = 0; i < m_queue_capacity_; i++)

 m_queue_buffer_[i] = new T();

 //...
 

What is evident from this is that variable points to an array on the heap containing pointers to objects on the heap. However, your destructor only takes care of the objects the contents of the array point to, not of the array itself. The fix is simple: Just add delete m_queue_buffer_; at the end.

Speaking of which...

Don't do manual memory management in C++ unless you really, positively, absolutely have to.

Take this as a lesson. Your program leaks memory, which is one of the least bad things that can happen when working with manual memory management. The potential to shoot yourself in the foot is much, much greater, and C++ offers a variety of auxiliary classes and containers to prevent you from leaving your toes somewhere during program execution.

Knowing this, let's look for help in the standard library. Your use case is something like this: You want an array on the heap, the size of which is fixed and which contains owning pointers to objects on the heap. What standard containers offer such functionality? Well, since your size is known at compile time, std::array would be one possibility, although in that case, the contents would live wherever the enclosing object lives (i.e. if you have your queue on the stack, all of the memory for this array is also going to be allocated on the stack), which comes with a risk of stack overflow. Thus, let's make this an std::unique_ptr<std::array<T*, queueSize>>. Another alternative would be to use the arguably most common standard container, std::vector, which is completely dynamic (i.e. can change its size at runtime) but usually doesn't incur any additional costs when accessed like a normal array.

The decision about which one should be taken depends largely on whether you want to keep queueSize as a template parameter. In my opinion, doing so is almost completely useless since you don't really do anything at compile time with it and it hinders interoperability. Instead, I would just have the constructor take the desired size as an argument and initialize the underlying container dynamically, in which case std::array becomes unfit since the size is no longer determinable at compile time. Ultimately, the choice is yours; however, you should ask yourself whether you can provide any real justification for restricting the use of your queue to cases where the required size is known at compile time (which is not the majority of cases as far as I can judge). Even in that case, the benefit that std::array provides is largely marginalized to the fact that you're allocating it on the heap.

But even after that choice, we're still not done here. Another reason that raw pointers are largely discouraged in modern C++ is the problem of ownership semantics. What are ownership semantics? Well, basically it means expressing which part of your code owns which values, and which part only uses or borrows values from other parts in the code directly. There are different approaches to this for different parts of the problem, but for the owning-pointer-to-heap problem, C++ offers std::unique_ptr and std::shared_ptr since C++11. The benefit of these pointers is twofold: Firstly, they express how the object they contain is being owned (single ownership for std::unique_ptr, shared ownership for std::shared_ptr) and secondly, they provide safety through RAII abstraction of the memory allocation process. Both pointers automatically free the memory they point to when being destructed.

In your case, the ownership relations are clear: Every object in your queue is a part of the queue and only of the queue, i.e. the queue owns it uniquely. The container just hands out pointers to single elements so that such elements can be used by other parts of your code, while not giving up and transferring the ownership over these elements. Accordingly, this is a perfect use case for std::unique_ptr. The element type of the container you choose should be std::unique_ptr<T>, and those elements should be initialized using std::make_unique<T>(...) (or new T(...) if C++14 is not available to you).

As to question 2: No, your queue is not threadsafe.

The problem is that you are handing out pointers to the same data to different threads without synchronizing any accesses to these pointers, which constitutes a race condition, which is undefined behavior.
Citing from the most recent working draft of the C++ standard before the release of C++14:

Two expression evaluations conflict if one of them modifies a memory location and the other one
accesses or modifies the same memory location.

This means that you have to synchronize the accesses to the contents of your queue, either by wrapping them in std::atomic, or by handing out a mutex together with your queue. The std::atomic approach is likely more robust, as you can't forget to take the lock before accessing, but requires your T to be trivially copyable, which can impose quite strict limitations.

Design issues

Apart from your program having undefined behavior currently, the thing that I most dislike about it is that your queue offers basically no usable interface.

First of all, if I wanted to extract the size of a queue, I'd currently need an ugly template hack to get the second template parameter, whereas you actually should provide a constexpr getter. Secondly, the mechanism you devised of "get a single pointer to an element, then increment the position of an internal offset to the next element" is about as clunky an interface as I have ever seen. Neither can I get more than one element at once, nor can I go backwards, nor can I do random accesses, although the underlying container supplies all of this functionality.

For a start, you should offer an iterator interface. Iterators are one of the core mechanisms of the STL, and enable your queue to work with most of the algorithms it provides (you'd likely need two different iterator types, though, one for read-only and one for write-only).

Another feature that I'd really like to see is an interface separation. Basically, your class offers two different interfaces: One is read-only, the other is write-only. However, these interfaces are mixed together in a single class, which potentially allows somebody to do illegal actions, such as writing from a read-only thread. To prevent this, and enforce separation of concerns, it would be really nice if you had two interface-like classes (i.e. CircularPtrQueue_reader and CircularPtrQueue_writer) which only export their corresponding half of the whole interface.

Another point I want to touch on is the whole issue of copying and moving. As is, you simply deleted move constructor and move assignment operator, but this is lazy interface design in my opinion. There is no reason why copy should be forbidden (unless you can provide one), and even much less reasons why move should be forbidden. Neither of those two things seems particularly hard to implement for a data structure like this.

Finally, I can not really come to peace with the design decision to force a double pointer indirection for the sake of avoiding copies. Of course, there are cases in which this is totally fine and appropriate, but in those cases you'd simply make the content type of the container std::unique_ptr<yourdatatype> and would have basically the same solution to the issue as you have right now. Since you seem to be very focused on performance, here is a point that might convince you: Forcing a pointer means forcing another level of indirection. Chances are, all those objects you create with new ... are living in different parts of the heap, which makes it nearly impossible for the cpu and data prefetcher to get all those values into cache in time, meaning you are probably going to end up waiting a lot of cycles on memory. The more your data structure is fragmented, the bigger the chance that you will completely kill your cache and end up taking more time just waiting for data than it would actually have taken to copy all of those bytes over. In addition, if you consider move semantics, you can actually avoid a lot (if not all) of those copies and turn them into (comparatively) cheap moves.

(Disclaimer: I haven't done any benchmarks on this. This is how the situation might pan out on a modern x86_64 processor, but I don't guarantee that any of the possible effects I've listed will be observable.)

Other things you should (probably) take care of

1. Whether size_t exists in the global namespace is entirely left to the implementation. As such, your program might not compile with a conforming standard library (although, to the best of my knowledge, all big standard library providers provide those functions). To circumvent this, utilize the std:: versions of every C type and function you use.


2. It would be nice of you to order your includes alphabetically to facilitate include checking.


3. Some of your comments don't add much to the code, omit those. For example, //Allocate memory for the respective objects. is something that is perfectly clear from the corresponding code line. Also, it is a lot more common to see comments before the line they refer as opposed to after, so you may want to change your comment style.


4. 
   #define is not the C++ way to define constants. Use const, constexpr and static with file-scope variables where appropriate. This allows you to have typed constants as well.


5. There is no need to write struct data out in lines like struct data* writable_ptr = cptr_q.GetWritablePushPtrToData();; data suffices (structs in C++ are not like structs in C).


6. Don't use std::endl. It causes unnecessary performance degradation through flushing where a simple 'n' would suffice.


7. You don't need to write out int in type names such as long int or unsigned int; long and unsigned are enough. While there is inherently nothing wrong with adding the int part, most people just omit it. Ultimately, it's your choice.


8. Since reader never terminates, you have some dead code at the end of main, which you should remove. Of course, it would be better if reader actually terminated.


9. The command line command you supplied to compile your program does not include warning flags. Compiler warning flags are oftentimes very useful in catching stupid bugs early, and not providing warning flags on Code Review always makes me suspicious that you either don't know about them, don't use them, or are trying to hide the fact that your code produces warnings, neither of which are particularly good (clang does accept your code without any utterances, however, so I assume that you did actually compile at least once with warnings enabled). Also, -g is not strictly necessary to compile your program, so I'd have omitted it here.


10. Boolean checks such as if(isEmpty[m_read_position_] == true) can simply be reduced to if (isEmpty[m_read_position_]). There is no need to compare with true and false since the value you get is already a bool.

I'm a little sorry that this answer turned into a huge wall of text. Yet, there are still some things I didn't list here for brevity's sake (especially in the design section) that seemed of lesser importance to me.

A lot of the content of this answer is not directly related to the two questions you posed, but I still hope that you will listen to the things I explained in those sections as well.