You can use the entire buffer and not waste one slot by doing:
push: buf[writeidx % bufsize] = x;
writeidx++;
pop: x = buf[readidx % bufsize];
readidx++;
Unsigned integers, you get size by doing: writeidx - readidx; Then you check size==0 or size==bufsize to detect empty/full.
He has a companion post about a "magic" ring buffer that uses a virtual memory mapping to make a ring buffer where you can always address the entire sizes as contiguous memory, but I think it has a bit of minor bit rot in the linked implementations. https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buff...
Keep in mind that one of the reasons behind the arbitrary "power of two" requirement is that the method proposed by the author abuses a single atomic integer to hold two shorts representing the indices for the head and tail elements.
I don't think it makes much sense to talk about overhead given this method requires doing a bunch of bitmasks to operate over the high and low short.
Larger CPUs can do many such operations during every clock cycle and even in very small CPUs they are usually single-cycle operations.
Depending on the CPU, integer divisions are 10 to 100 times slower, so in a completely different range of overhead.
Modular arithmetic makes it work. Try a few examples close to UINT_MAX if you want to convince yourself.
With non-power-2 bufsize you need some extra logic for write/readix++, but the rest of the code can stay the same.
If bufsize is a power of 2, doing the modulo would be exactly the same as just using a smaller integer type (like 8 bits on a microcontroller). What we want is the integer wraparound to never coincide with the buffer position wrapping. For that we would need a size that has some other factor than 2, and thus a "real" modulo operation in the indexing (which is slow).
Or is there an error in my thinking?
edit: Duh, I understand now. If the counter has at least twice the range as the buffer size, the subtraction will always give the correct number of elements used. Power of 2 or not doesn't matter.
Not having to do the subtraction could still give a performance benefit, and if the buffer elements aren't very large, one wasted slot is worth the tradeoff.
On a desktop/laptop computer, wasting a queue slot matters very little, but it may be useful to achieve the maximum speed, so this method does not seem preferable.
On the other hand, in many microcontroller applications there is no other read/write RAM, but a few kilobytes of internal MCU RAM. So the amount of used RAM may be the most important resource and there may be many FIFO queues for various peripheral interfaces.
For such MCU applications, it is valuable to be aware of this alternative FIFO queue implementation, as it may be the best choice.
Ring buffers work exactly the same way