On Sun, 2 Aug 2009, Dave Tweed wrote:

> sergio masci wrote:
> > On Thu, 30 Jul 2009, Dave Tweed wrote:
> > > There is one ambiguity -- when the indices are equal, is the FIFO
> > > completely full or completely empty? This means that you can't
> > > actually completely fill the FIFO in a simple implementation.
> > 
> > This means that the fifo buffer can only ever store a max of 
> > ('buffer_length' - 1) items (in other words one item becomes a guard 
> > item).
> 
> Isn't that exactly what I said???

Yes Dave but it's not what I said.

I was explaining what happens when the head cannot be incremented such 
that it is equal to the tail. What I actually said was:

<quote>
There is no ambiguity when the indices are equal (and no need for a 
special 'full' flag) if you observe two simple rules:
(1)... (tail == head) means empty
(2)... head cannot be incremented to be equal to tail

This means that the fifo buffer can only ever store a max of 
('buffer_length' - 1) items (in other words one item becomes a guard 
item).
</quote>

> 
> My point was, that if you add a simple boolean flag to the FIFO structure,
> you CAN completely fill it, and this actually has negligible impact on the
> overall code size, and does NOT affect its thread-safe properties.

Ok, so please show how you would do this.

> 
> > NOTE: the way a temporary index is used to protect the location of fifo 
> > item while it is being manipulated and consequently these routines are
> > *** INTERRUPT SAFE ***
> 
> Actually, your temporary variable has nothing to do with making the
> routines thread/interrupt-safe. I don't know the complete specs of the
> language you're using, but using the variable appears to be just a
> performance optimization (to avoid having to recalculate the updated
> value at the end of fifo_write()) and/or a workaround for the limited
> expression-handling capabilities of the compiler.

These functions were originally written in assembler many years ago, then 
they got converted to C. They were converted to this other language as a 
simple 1 to 1 translation. I simply went to where I knew I could cut and 
past (into the previous post) with the minimum of effort.

The reason the temporary variable is used is to ensure that the compiler 
doesn't do some strange optimisation on the fifo head / tail index when 
incrementing it which would break the atomic update of the fifo variable.

> 
> You could just as well have called fifo_full() from fifo_write(), and
> fifo_empty() from fifo_read().

Yes I could, but experience has shown that the overhead overwhelms the 
actual code in the function. At one point I resorted to using macros in C 
to reduce the overhead then I came to my senses and ended up with what you 
see now.

As a mater of interest what limitted expression-handling capabilities do 
you see this code trying to get around (with the use of the temporary 
variable).


Friendly Regards
Sergio Masci
-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist