Consumerism (Hard version)

This is the hard version of MPMCQueue. The only difference between this and the easy version is the type constraints on elements stored in the queue. Solving one problem does not guarantee solving the other.

You may already be familiar with the lock-free MPSC (multi-producer, single-consumer) queue shown on our homepage. This problem tests whether you understand how to generalize those ideas to full MPMC concurrency.

Implement the class MPMCQueue, which is a lock-free multi-producer multi-consumer queue.

Constructor

MPMCQueue(capacity)

• capacity specifies the maximum amount of elements that may exist in the queue at any time.

• capacity must be a power of 2 and greater than 2. Throw an exception if it isn't.

Methods

push(element)

• Attempts to enqueue element.

• Returns true if the enqueue succeeds.

• Returns false if the queue is full at the operation's linearization point (no spurious failures).

pop(out)

• Attempts to dequeue an element and store it in out.

• Returns true if the dequeue succeeds.

• Returns false if the queue is empty at the operation’s linearization point (no spurious failures).

Notes

• The implementation must be lock-free (no std::mutex, no condition variables, etc.). Using a lock may result in a compilation error.

• Multiple producers and multiple consumers may call push/pop concurrently.

• You do not need to write any input/output parsing.

• Your submission will be tested with a multithreaded grader and heavy stress tests.

• Type constraints (hard version):

  • You may not assume the stored type T is default-constructible.

  • Your implementation must correctly construct and destroy elements stored in the queue.

• We run strong stress tests to catch common concurrency bugs, but this does not prove the absence of data races.

• Unlike the MPSCQueue implementation shown on the homepage, spurious failures for push are not allowed. This was intentionally omitted due to the addition of this question and its easy version.

  • The queue must accurately detect full and empty states under contention.

• You may assume the queue will not be destroyed during concurrent push or pop operations.

• As stated before, push must return false when the queue is full, and pop must return false when the queue is empty. The grader uses heavy stress tests to detect corruption (duplicates/missing) and deadlocks, but does not formally verify linearizability.