Simplified algorithm for calculating remaining space in a circular buffer?

Question

I was wonder if there is a simpler (single) way to calculate the remaining space in a circular buffer than this?

int remaining = (end > start)
                ? end-start
                : bufferSize - start + end;

Answer 1

Lose the conditional:

int remaining = (end + bufferSize - start - 1) % bufferSize + 1

Edit: The -1 and +1 are for the case when end == start. In that case, this method will assume the buffer is empty. Depending on the specific implementation of your buffer, you may need to adjust these to avoid an off-by-1 situation.

Answer 2

If you're worried about poorly-predicted conditionals slowing down your CPU's pipeline, you could use this:

int remaining = (end - start) + (-((int) (end <= start)) & bufferSize);

But that's likely to be premature optimisation (unless you have really identified this as a hotspot). Stick with your current technique, which is much more readable.

Answer 3

According to the C++ Standard, section 5.6, paragraph 4:

The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined.

A footnote suggests that rounding the quotient towards zero is preferred, which would leave the remainder negative.

Therefore, the (end - start) % bufferSize approaches do not work reliably. C++ does not have modular arithmetic (except in the sense offered by unsigned integral types).

The approach recommended by j_random_hacker is different, and looks good, but I don't know that it's any actual improvement in simplicity or speed. The conversion of a boolean to an int is ingenious, but requires mental parsing, and that fiddling could be more expensive than the use of ?:, depending on compiler and machine.

I think you've got the simplest and best version right there, and I wouldn't change it.

Answer 4

Hmmm....

int remaining = (end - start + bufferSize) % bufferSize;

13 tokens, do I win?