Array index subtraction and wrapping

[wearyofallthiscrap]

(I'm posting this via Google, I apologize if the From: line is
completely
broken.)

I'm trying to track down a bug in some code which handles memory
buffers.
I'm not accustomed to using C, and there's an idiom which is confusing
me.

The buffer uses head (writing) and tail (reading) offsets.
Calculating the
size is being done with lines like this:

end = (head + (buffer_size - tail)) % buffer_size;
size = end;

Now, I understand (I think) why the math is ordered the way it is, to
avoid any potential integer overflow when "head + buffer_size" would
have
been calculated. What I don't understand is why

size = head - tail;

would not have been sufficient? What's the point of "wrapping" the
numbers around the buffer, so to speak?

 

[Eric Sosman]

(I'm posting this via Google, I apologize if the From: line is
completely
broken.)

I'm trying to track down a bug in some code which handles memory
buffers.
I'm not accustomed to using C, and there's an idiom which is confusing
me.

The buffer uses head (writing) and tail (reading) offsets.
Calculating the
size is being done with lines like this:

end = (head + (buffer_size - tail)) % buffer_size;
size = end;

Now, I understand (I think) why the math is ordered the way it is, to
avoid any potential integer overflow when "head + buffer_size" would
have
been calculated. What I don't understand is why

size = head - tail;

would not have been sufficient? What's the point of "wrapping" the
numbers around the buffer, so to speak?

For concreteness, let's imagine buffer_size == 100.
To begin, we'll suppose that 90 items have been inserted
in the buffer, so head == 90, and the first 50 of them
have been read, so tail = 50. (I'm assuming that head
is the index where the next inserted item will go and
tail is the index from which the next removed item will
be taken; the actual boundary conventions in your code
may be different.) How many items are still in the
buffer? head - tail == 40, as you suggest.

Now insert 30 more items. The first ten go into
positions [90] through [99], but then what? Probably,
head wraps around to zero and re-uses positions [0]
through [19] for the rest. So now we have head == 20,
tail == 50. How many items are now in the buffer? We
had 40, we added 30 more, so there are now 70. But
what is the value of head - tail? It is -30, which is
a peculiar number of items ...

This arrangement where a pair of array indices or
a pair of pointers chase each other around and around
a fixed-size array but are never allowed to cross is
known as a "circular buffer," by analogy with what
happens as you go around a circle counting degrees
as you go: 357, 358, 359, 0, 1, 2, ... The successor
of the last slot in the array is the first slot. Most
often there are two "active" positions -- like your head
and tail -- but sometimes there may be three or more.
(I've never seen more than four used, but I bet someone
has.)

 

[CBFalconer]

(I'm posting this via Google, I apologize if the From: line is
completely
broken.)

I'm trying to track down a bug in some code which handles memory
buffers. I'm not accustomed to using C, and there's an idiom
which is confusing me.

The buffer uses head (writing) and tail (reading) offsets.
Calculating the size is being done with lines like this:

end = (head + (buffer_size - tail)) % buffer_size;
size = end;

size = (tail - end) % buffer_size;

Now, I understand (I think) why the math is ordered the way it is,
to avoid any potential integer overflow when "head + buffer_size"
would have been calculated. What I don't understand is why

size = tail - head; /* corrected, cbf */

would not have been sufficient? What's the point of "wrapping"
the numbers around the buffer, so to speak?

Because tail may be greater than end. In future, show complete
code, not snippets.

 

[wearyofallthiscrap]

size = (tail - end) % buffer_size;

Um, no, the code I posted is copy and pasted from the source
file open in another window. It really does look exactly as I
posted. Yes, I know how it could be simplified. I left it
as it was coded because the names seemed meaningful.


No, unless you're reversing things midway, he original form was
in fact the question I wanted to ask. See Eric Sosman's reply
for what's going on -- and thank you, Eric, for the pointer! I
now know more about circular buffers than I had ever thought.


-Ti