Hard
SPSC ring buffer with free-running head and tail indices
Exactly one producer thread calls push() and exactly one consumer thread calls pop(). The indices are never masked when stored; only the slot access is. Is this queue correct under the C++ memory model?
main.cpp
template <size_t N> // N is a power of two
struct Spsc {
int buf[N];
std::atomic<size_t> head{0}; // written only by the consumer
std::atomic<size_t> tail{0}; // written only by the producer
bool push(int v) {
size_t t = tail.load(std::memory_order_relaxed);
if (t - head.load(std::memory_order_relaxed) == N) return false; // full
buf[t & (N - 1)] = v;
tail.store(t + 1, std::memory_order_release);
return true;
}
bool pop(int& out) {
size_t h = head.load(std::memory_order_relaxed);
if (h == tail.load(std::memory_order_acquire)) return false; // empty
out = buf[h & (N - 1)];
head.store(h + 1, std::memory_order_relaxed);
return true;
}
};46 of 51 in Concurrency