This project is a multi-threaded queue for storing a finite number of elements using a lock-free circular buffered queue.

• Storage; essential pop and push operations.
• Reading thread blocks if the queue is empty.
• Writing thread blocks if the queue is full.
• Reading and writing threads block for a set amount of time. Functions return a boolean indicating the success of the operation.
• The project does not use std::queue but instead a circular buffer.
• The project does not use std::mutex but instead atomic operations.
• Documented using Doxygen.
• Includes tests in googletest.
• Uses CMake for building.

The following table list the tools and respective versions used during the development of this project. Other versions probably will work as well, but they haven't been tested.

Note: googletest should be automatically downloaded by CMake and not require an external download.

From the directory that contains the CMakeLists.txt, run the following commands:

• $ cmake -G 'Unix Makefiles' -S . -B build
• $ cd build && make

The project uses the Doxygen style documentation and includes a Doxyfile for aiding. We can generate the documentation using the following command in the root directory:

• doxygen Doxyfile

From within the build directory, run the command:

• $ ./test_pairs

Sometimes the tests will fail not because of the logic of the functions but because the push and pop operations have a timeout behaviour. As such, it isn't easy to assert the expected behaviour correctly.

We calculate the worst possible outcome and compare it with the test's execution as a workaround. We then see if it is within an acceptable margin of error. We can change this margin by editing the acceptableMargin variable in file /tests/single.cpp, which, for now, is set to a 2% margin of error.

One possibility would be to increase the number of tries before giving up, which quickly raises the test times. Another possibility was to wrap the timeout portions of the code with a preprocessor macro that could be toggled during compilations. This approach wasn't used because CMake does not support multiple configurations per project when using 'Unix Makefiles' and these were prefered as they simplify requirements for using the project.

Because I want to reuse this code in other projects, the design of the container was affected by a few personal decisions:

• I wanted to avoid a container that used mutexes to implement multithreading. We based the project's design on the UniQ Multithreading Libray, which implements a lock-free circular buffered queue, with a few modifications of my own.
• I wanted to avoid memory allocations; as such, the container uses a compile-time constant for dictating its storage size. My uses don't require a resizeable container, so this approach should reduce memory consumption as the container can reside in a stack variable.
• The container's capacity has to be a power of 2. This constraint helps to ensure the internal indexes' values are always below the storage's capacity, and this method simplifies the implementation.

• Using std::optional for each storage element: The issue was distinguishing whether the storage was empty or full when the insert and extract indexes held the same value. The implemented solution was to use an optional to validate if each element does, in fact, exist. The issue is that it creates an additional overhead that scales with the size of the container.
  • An alternative could be to use a boolean that registers if the container is full when the insertion index catches up to the removal index. We did not do this to simplify the code and avoid more checks.