Linked List Based MPMC Blocking Queue

Overview

This exercise asks you to implement a Multi-Producer Multi-Consumer (MPMC) queue using a linked list, protected by mutexes and condition variables.

This type of queue is common in real-world concurrent systems where:

• Multiple threads produce data (e.g., incoming market feeds, logging, I/O)
• Multiple threads consume data (e.g., processing workers)

Key Concepts

• Use std::mutex to guard the queue from concurrent access.
• Use std::condition_variable to block consumers when the queue is empty.
• Handle wakeups correctly using cv.wait(lock, predicate).
• Manage node memory using a simple singly-linked list with a dummy node.

> ⚠️ This is a blocking implementation. The pop() method should block if the queue is empty until an item becomes available.

Requirements

• push(const T&) should be thread-safe and non-blocking.
• pop() should block if the queue is empty, and return the next available value once available.
• Your implementation must support multiple producers and consumers operating concurrently.

Bonus (Optional):

• Add a shutdown() method to wake waiting threads and cleanly exit.

Implement a thread-safe blocking queue using a linked list with multiple producers and consumers.

#include <mutex>
#include <condition_variable>

template <typename T>
class MPMCQueue {
private:
    struct Node {
        T value;
        Node* next;
        Node(const T& val) : value(val), next(nullptr) {}
    };

    Node* head_;
    Node* tail_;
    std::mutex mtx_;
    std::condition_variable cv_;

public:
    MPMCQueue() {
        head_ = tail_ = new Node(T{});
    }

    ~MPMCQueue() {
        while (head_) {
            Node* tmp = head_;
            head_ = head_->next;
            delete tmp;
        }
    }

    void push(const T& val) {
        // TODO: Implement thread-safe push
    }

    T pop() {
        // TODO: Implement thread-safe, blocking pop
        return T{};
    }
};