coding challenges · advanced

Thread-Safe Circular Buffer

Microsoft thread-safe FIFO circular buffer. A fixed std::vector ring with head_ (next write), tail_ (next read) advanced by (i+1)%cap, and an explicit count_ to distinguish full (count==cap) from empty (count==0). 'Never overwrite unread data' makes it a bounded blocking queue: push takes a unique_lock, waits on not_full_ with a predicate (guards spurious/lost wakeups), writes, increments, and notifies not_empty_; pop mirrors it, moving the element out by value under the lock and notifying not_full_. Two condition variables pair pops with producers and pushes with consumers. All ops O(1), bounded memory. Key bugs: bare wait() without a predicate, lock_guard instead of unique_lock, returning a reference into the ring. SPSC fast path drops the mutex for atomic head/tail with acquire/release ordering.

The code

// Thread-safe FIFO circular buffer. Fixed capacity at construction,
// blocks on full/empty, never overwrites unread data.
template<typename T>
class CircularBuffer {
    std::vector<T> buf_;
    const size_t   cap_;
    size_t head_ = 0, tail_ = 0, count_ = 0;
    mutable std::mutex            m_;
    std::condition_variable       not_full_, not_empty_;
public:
    explicit CircularBuffer(size_t cap) : buf_(cap), cap_(cap) {}

    void push(const T& item) {                       // blocks if full
        std::unique_lock<std::mutex> lk(m_);
        not_full_.wait(lk, [&]{ return count_ < cap_; });
        buf_[head_] = item;
        head_ = (head_ + 1) % cap_;                   // wrap
        ++count_;
        not_empty_.notify_one();
    }

    T pop() {                                         // blocks if empty
        std::unique_lock<std::mutex> lk(m_);
        not_empty_.wait(lk, [&]{ return count_ > 0; });
        T item = std::move(buf_[tail_]);
        tail_ = (tail_ + 1) % cap_;
        --count_;
        not_full_.notify_one();
        return item;
    }
};

What this lesson walks through

1. 01A ring: a fixed array with two wrapping cursors
2. 02push: write at head, wrap, count++
3. 03pop: read at tail, wrap, count--
4. 04The wrap + the full / empty ambiguity
5. 05Full ⇒ block (never overwrite) — O(1), bounded

Capacity is fixed. head_ marks the next write slot, tail_ the next read slot; both wrap with % cap, turning the array into a ring. count_ tracks how many items are stored.