Alex Rivera | Logout

Simplified algorithm for calculating remaining space in a circular buffer?

Asked 2009-01-16T14:33:23.717
11

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;
c++ circular-buffer
Edit
Report

1 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.

answered 2009-01-16T14:51:28.500

Your Answer