Simplified algorithm for calculating the remaining space in a circular buffer?

Question

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

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

Answer 1

If you are worried about poorly predictable conventions slowing down your processor pipeline, you can use this:

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

But it can be premature optimization (if you really have not defined this as a hot spot). Stick to your current technique, which is much readable.

Answer 2

Mmm ...

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

13 tokens, will I win?

Answer 3

In accordance with the C ++ standard, section 5.6, paragraph 4:

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

The note suggests that rounding off quotient to zero should be preferred, leaving a negative balance.

Therefore, the approaches (end - start) % bufferSize do not work reliably. C ++ does not have modular arithmetic (except for the meaning suggested by unsigned integer types).

The approach recommended by j_random_hacker is different and looks good, but I do not know that this is a real improvement in simplicity or speed. Converting a boolean to int is inventive, but requires mental analysis, and that driving can be more expensive than using?:, Depending on the compiler and the machine.

I think that you have the simplest and best version, and I would not change it.

Answer 4

If the size of your circular buffer is two, you can do even better if start and end represent positions in the virtual stream instead of indices in the circular buffer memory. Assuming start and end are unsigned, this means:

 int remaining= bufferSize - (end - start); 

Actually getting the elements from the buffer is a bit more complicated, but the overhead is usually small enough with the size of a circular buffer of size 2 (just masking with bufferSize - 1 ) to make all the other logic of your circular buffer simpler and cleaner. In addition, you can use all the elements since you no longer worry about end==start !

Answer 5

Lose conditional:

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

Edit: -1 and +1 refer to the case where end == start . In this case, this method assumes that the buffer is empty. Depending on the specific implementation of your buffer, you may need to configure them to avoid an offside situation.

Answer 6

An elderly stream that I know, but thought it might be useful.

Not sure how fast this is implemented in C ++, but in rtl we do this if the size is n ^ 2

 remaining = (end[n] ^ start[n]) ? start[n-1:0] - end[n-1:0] : end[n-1:0] - start[n-1:0]; 

or

 remaining = if (end[n] ^ start[n]) { start[n-1:0] - end[n-1:0] } else { end[n-1:0] - start[n-1:0] };