Re: [RFC, 2.6] a simple FIFO implementation

[Stelian Pop]

On Thu, Sep 16, 2004 at 06:07:07PM +0200, Buddy Lucas wrote:

> > > Indeed, that would exactly be the reason *why* this would fail. ;-)
> > >
> > > The expression fifo->size - fifo->tail + fifo->head might be negative
> > > at some point, right? (fifo->head has wrapped to some small value and
> > > fifo->tail > fifo->size)
> > 
> > And what is the value of an unsigned int holding that 'negative' value ? :)
> > 
> 
> Which unsigned int?! ;-) The expression a - b is negative for unsigned
> ints a and b where a < b. So, your unsigned ints "total" and
> "remaining" won't be negative of
> course, but they won't reflect what is actually left in the buffer;
> they will equal the
> value of len (in some cases) after fifo->head has wrapped (because of the 
> unsignedness) and fifo->tail has not. Which would not be correct.

It is, thanks to modular arithmetic.

Let's imagine we use unsigned char instead of unsigned int (simpler
to explain), and we have a 200 bytes buffer.

At the beginning:
	head = tail = 0
We add 200 bytes:
	head = 0, tail = 200
We extract 200 bytes:
	head = 200, tail = 200
We add 200 bytes more:
	head = 200, tail = (200 + 200) % 256 = 144
Now the buffer length is:
	144 - 200 = (-56) % 256 = 200

Thanks to modular arithmetic magic, we get the correct answer: 200.

Stelian.
-- 
Stelian Pop <stelian@xxxxxxxxxx>
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/